Database Reference
In-Depth Information
Table 16.5: Database D
X
as the union of D
1
and D
2
produced by the partitioning
approach.
<
:
a
b
c
d
e
f
0
0
0
0
0
0
D
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
(
1
0
1
1
0
0
D
2
1
0
1
1
0
0
I
P
. Given the proper itemsets from C that support items in this subspace, one can
adjust these binary variables in a way that the revised border is preserved for the
corresponding items. In the same manner the borderline in the subspace of I
P
is
preserved. Especially for the itemsets in I
P
that also support items from I
P
, by
considering the previously assigned values of the u
qm
variables in the subspace of
I
P
one can proceed to properly assign the u
qm
variables in the subspace ofI
P
, so that
the newly formulated BIP has a solution. In the case that the current transactions in
D
X
are insufficient to accommodate for the holding of the new constraints imposed
by the itemsets in I
P
, database D
X
has to be appropriately expanded. However, this
expansion can be negated at a later point with the removal of the null transactions (as
in Section 16.3.4) after the overall hiding solution. Since the formulated CSP sets
the minimum possible u
qm
variables to '1', the borderline will be adjusted through
this process without causing any harm to the exact solution, apart from potentially
using a larger part of the extension. Due to the exponential execution time of the
integer programming solver the benefit of this decomposition is substantial since it
allows for reasonably low execution times, even when performing knowledge hiding
in very large databases.
16.4.2 An Example
In what follows, we present an example borrowed from [26], which demonstrates
the operation of the partitioning approach in the database of Table 16.1. Assume
that for this database we have I
P
=fa; b; c; eg and I
P
=InI
P
. The itemsets of C =
fe; f ; ab; bc; bd; acdg are then partitioned as follows: C =fe; ab; bcg[ff ; bd; acdg.
tion of the constraint regarding itemset facdg participating in the second CSP. Thus,
after the solution of the first CSP, database D
X
has to be extended. Suppose that a
SM = 2 is used. Then, the second CSP leads to database D
2
, as shown in Table
