Database Reference
In-Depth Information
which must become infrequent in the sanitized outcome. It is easy to prove that if
these inequalities are incorporated to the CSP of Figure 14.2, then the produced CSP
is unsolvable. Thus, Algorithm 14.1 is used to alleviate the CSP from inequalities
of set V =fACE; ADEg. However, as mentioned earlier, the two-phase iterative al-
gorithm does not use the “batch” mode of operation of this algorithm (which would
remove both itemsets in V ) but instead, it uses the “one-by-one” mode of operation
that selects to remove one among the inequalities returned in the same “batch”. As
already stated, at this point the selection among the inequalities of the same batch
is arbitrary. Suppose that the inequality corresponding to itemset ACE of the re-
vised positive border is selected to be removed from the CSP. The resulting CSP is
then solvable. Among the alternative possible solutions assume that the one having
u
34
= u
53
= u
104
= 0 and u
23
= u
24
= u
33
= u
54
= u
103
= 1 is selected. Since the
criterion function of the CSP requires the maximization of the number of binary
variables that are set to '1', the solution that is produced has the minimum possible
variables set to '0'. This solution (having a distance of 3) is presented in
Table 15.3;
since it is not exact, we name our database D
H
and proceed to the second phase of
the iteration.
Table 15.4: Intermediate form of database D
H
.
A
B
C
D
E
1
0
1
0
u
15
1
0
1
1
1
u
31
0
1
0
u
35
u
41
1
u
43
0
1
1
0
u
53
1
1
u
61
0
u
63
1
1
u
71
0
1
0
u
75
1
1
u
83
0
u
85
1
0
1
0
u
95
u
101
0
1
0
u
105
since its support has dropped below the minimum support threshold. In an attempt
to constitute this itemset frequent again, the two-phase iterative algorithm creates
an intermediate form of database D
H
in which in all transactions that do not support
items A, C, or E, the corresponding zero entries are substituted with binary variables
As a following step, the inequalities for the itemsets of set C are produced by
taking into account the itemsets of sets H and Bd
(F
0
H
) =fAB; BC; BD; BE; CDg,
which are not foreign to I
H
=fA;C; Eg. Thus, we have the following set of pro-
duced inequalities:
