Database Reference
In-Depth Information
Table 13.1: An example of a constraints-by-transactions matrix.
<
:
c/T
T
6
T
7
T
3
T
1
T
2
T
5
T
4
c
1
1
1
1
0
0
0
0
c
3
0
1
0
0
0
0
0
M=
c
2
0
0
0
1
0
1
0
c
5
0
0
0
1
0
1
1
c
4
0
0
0
0
1
0
1
minimize (x
1
+x
2
+x
3
+x
4
+x
5
+x
6
+x
7
)
<
:
x
3
+x
6
+x
7
2
x
7
1
x
1
+x
5
1
x
1
+x
4
+x
5
3
x
2
+x
4
2
x
1
; x
2
; x
3
; x
4
; x
5
; x
6
; x
7
2f0; 1g
subject to
Fig. 13.2: The original CSP formulation for the example.
constraints c
2
; c
4
; c
5
and transactions T
1
; T
2
; T
4
; T
5
. An example of the original CSP
along with its two independent blocks is presented in
Figures 13.2,
13.3
and
13.4,
respectively.
minimize (x
3
+x
6
+x
7
)
8
<
:
x
3
+x
6
+x
7
2
x
7
1
x
3
; x
6
; x
7
2f0; 1g
subject to
Fig. 13.3: The first independent block for the CSP of Figure 13.2.
Algorithm 13.1 (proposed in [47]) is a clustering strategy that can be employed
for the decomposition of the original CSP through the identification of its indepen-
dent blocks. The algorithm begins by considering that each sensitive itemset belongs
to a separate block and then merges different blocks that share supporting transac-
tions for their respective sensitive itemsets. Specifically, for each transaction in D
S
the algorithm identifies the sensitive itemsets that it supports and merges the corre-
sponding blocks into a single block. In the end, the independent blocks along with
the corresponding transactions and sensitive itemsets are returned to the user. The
