Database Reference
In-Depth Information
Fig. 17.1: Decomposing large CSPs to smaller ones.
Table 17.1: The original database D
O
.
A
B
C
D
1
1
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
1
0
1
1
0
1
1
0
0
1
1
0
0
1
1
1
0
0
0
0
0
0
1
S
max
=fB; AB;CDg
(17.1)
Bd
+
(F
0
D
) =fA;C; Dg
(17.2)
V =fC; DgBd
+
(F
0
D
)
(17.3)
The intermediate form of this database is shown i
n Table 17.2
and the CSP formula-
tion based on the inline algorithm is presented in
Figure 17.2.
Table 17.3
highlights
the various constraints c
r
along with the variables that they control. As one can ob-
serve, the various constraints of the CSP can be clustered into disjoint sets based on
the variables that they involve. In this example, there are two such clusters of con-
straints, namely M
1
=fc
1
g, and M
2
=fc
2
; c
3
; c
4
g. Notice that none of the variables
in each cluster of constraints is contained in any other cluster. Thus, instead of solv-
ing the entire problem of
Figure 17.2,
one can equivalently solve the two subprob-
