Database Reference
In-Depth Information
Table 16.3: The intermediate form of database D
X
.
a
b
c
d
e
f
u
11
u
12
u
13
u
14
u
15
u
16
u
21
u
22
u
23
u
24
u
25
u
26
u
31
u
32
u
33
u
34
u
35
u
36
u
41
u
42
u
43
u
44
u
45
u
46
Algorithm 16.2 Relaxation Procedure in V =Bd
+
(F
0
D
).
1: procedure S
ELECT
R
EMOVE
(Constraints C
R
, V , D
O
)
2:
C
R
maxlen
S
argmax
i
fjR
i
jg
. C
R
i
$V
i
3:
cr
msup
min
C
R
maxlen
;i
(sup(R
i
2V;D
O
))
4:
for each c 2C
R
maxlen
do
5:
if sup(R
i
;D
O
) = cr
msup
then
6:
Remove (c)
. remove constraint
7: end if
8: end for
9: end procedure
Algorithm 16.2 applies a relaxation process that selectively removes inequalities
of type (16.3) up to a point that the resulting CSP is solvable. In this algorithm, C
R
is the set of constraints imposed by the itemsets of Bd
+
(F
0
D
) and jR
i
j denotes the
size of itemset R
i
in C
R
. In a realistic situation, only a small portion of constraints
will have to be discarded. Thus, emphasis is given in [26] on constraints involving
maximal size and minimum support itemsets, appearing in database D
O
.
16.3.6 Continuing the Running Example
the revised borders for the hiding of the sensitive itemsets in S = fe; ae; bcg,
when mfreq = 0:3, were computed. To proceed, one needs to identify the mini-
mum extension of D
O
, namely the minimum size of D
X
that facilitates sensitive
knowledge hiding. Using (16.1) for the sensitive itemset with the highest support
(here either feg or fbcg), we have that Q = 4. Excluding, for brevity, the use
picts database D
X
prior to the adjustment of the various u
qm
variables involved.
To produce the needed constraints, consider all the itemsets appearing in C, where
depicted in
Figure 16.4
is constructed, where the validity of all transactions of D
X
