Database Reference
In-Depth Information
<
:
fabg : u
11
u
12
+u
21
u
22
+u
31
u
32
+u
41
u
42
0:2
facdg : u
11
u
13
u
14
+u
21
u
23
u
24
+
+u
31
u
33
u
34
+u
41
u
43
u
44
1:2
Bd
+
(F
0
D
)
8
<
:
feg : u
15
+u
25
+u
35
+u
45
< 0:2
ffg : u
16
+u
26
+u
36
+u
46
< 2:2
fbcg : u
12
u
13
+u
22
u
23
+u
32
u
33
+u
42
u
43
< 0:2
fbdg : u
12
u
14
+u
22
u
24
+u
32
u
34
+u
42
u
44
< 2:2
Bd
(F
0
D
)
<
:
u
11
+u
12
+u
13
+u
14
+u
15
+u
16
1
u
21
+u
22
+u
23
+u
24
+u
25
+u
26
1
u
31
+u
32
+u
33
+u
34
+u
35
+u
36
1
u
41
+u
42
+u
43
+u
44
+u
45
+u
46
1
T
q
2D
X
Fig. 16.4: The constraints in the CSP of the running example.
Table 16.4: Database D
X
after the solution of the CSP.
a
b
c
d
e
f
1
1
1
1
1
0
0
1
0
0
1
0
1
0
1
1
1
0
0
0
0
0
0
0
has to be ensured. Notice that if a safety margin was used, the last set of constraints
(regarding the validity of transactions in D
X
) would have been excluded from the
CSP to allow for the minimization of the size of D
X
at a later point. After formu-
lating the CSP the CDR approach of
Figure 16.2
is applied. Solving the produced
The hiding solution of
Table 16.1
is exact. Notice, that with a minimal extension
of 4 transactions, all the sensitive knowledge was hidden, leaving other patterns
unaffected in D. This solution is optimal with a distance of dist(D
O
;D) = 9.
To highlight some other aspects of the hybrid hiding methodology, consider the
hiding of S =fabcg in the same database D
O
. In this case, using (16.1) we have
that Q = 1. However, as it turns out, only one transaction is insufficient to provide
an exact solution to the formulated CSP. Suppose that a safety margin of 3 was
used, leading to the construction of 4 transactions in database D
X
. Due to the use
of the safety margin in the CSP formulation, the set of constraints corresponding to
the validity of the transactions in database D
X
are excluded, thus, the formulation
of the CSP. As one can notice, the last transaction of D
X
is null. Based on (16.8),
k = max(13; 0) so the empty transaction from D
X
can be safely removed, without
