Database Reference
In-Depth Information
Algorithm 16.1 Validation of Transactions in D
X
.
1: procedure V
ALIDATE
(D
O
, D
X
, Bd
+
(F
0
D
))
2: J fT
q
2D
X
j T
q
is nullg
3: min 1
4: for each (I 2Bd
+
(F
0
D
)) do
5: ds(I) sup(I;D)sup(I;D
O
)
6: if (ds(I) < min) then
7: min ds(I)
8: end if
9: end for
10: for (i = 0; i <jBd
+
(F
0
D
)j; i++) do
11: ds(I) int(ds(I)=min)
12: end for
13: Sds reverse_sort(ds)
14: Sds(jBd
+
(F
0
D
)j) 1
15: k jJj
16: while (k > 0) do
17: for (i = 0; i <jBd
+
(F
0
D
)j; i++) do
18: for ( j = Sds(i); j Sds(i+1); j-) do
19: if (k > 0) then
20: k k1
21: Sds(i) Sds(i)1
22: R
EPLACE
(J (k), T
fSds
i
g
)
23: else
return
24: end if
25: end for
26: end for
27: end while
28: end procedure
be attained if, for each transaction in database D
X
, a constraint is added to the CSP
to enforce its validity in the final solution. The new CSP formulation is depicted
in
Figure 16.3.
An immediate disadvantage of this approach is the increment in the
number of constraints of the produced CSP.
16.3.5 Treatment of Suboptimality in Hiding Solutions
Similarly to the inline approach of [23], there are certain problem instances where
exact hiding solutions do not exist and one must seek for a good approximate so-
lution. To identify such a solution, the difference of importance existing between
(16.3) and (16.4) is of crucial importance. Since the target of a hiding methodology
is to secure sensitive knowledge, the holding of (16.4) is of major importance. The
inherent difference in the significance of these two inequalities, along with the fact
that solving the system of all inequalities of the form (16.4) always has a feasible
solution, enables the relaxation of the problem when needed and the identification
of good approximate solutions.
