Database Reference
In-Depth Information
r
(x )
1
x
(x )
2
}
m
x
x
E
x
by subquery (1)
(x )
m
x
P
1
x
x
E
x
}
P
}
E
x
B
E
x
B
m
c
c
c
c
c
c
. . .
T
c
F
c
T
c
F
c
1,1
1,1
m,1
m,1
n+1
n+1
c
c
c
c
T
c
F
c
T
c
F
c
1,n
1,n
m,n
m,n
T
c
E
c
F
c
E
F
c
E
c
T
c
E
c
x = true
1
x = false
m
Fig. 1.
Tree
t
plotted by subqueries (1) and (2)
T
i,j
=
T
c
if positive literal
x
i
occurs in
C
j
,
F
c
otherwise
,
F
i,j
=
T
c
if negative literal
¬x
i
occurs in
C
j
,
F
c
otherwise
.
Thus, if
T
i,j
=
T
c
, then clause
C
j
in
φ
becomes true by setting
x
i
=
true
,and
if
F
i,j
=
T
c
,then
C
j
becomes true by setting
x
i
=
false
.Thevalueof
x
i
is set
by subqueries (9) and (10), as follows. In
t
,thevalueof
x
i
is identified by the
labels of two bottom leaf nodes of subtree
P
i
, where one is labeled by
T
c
and
the other is labeled by
F
c
. For example,
x
1
=
true
and
x
m
=
false
in Fig. 1.
More precisely, let
t
T
i
and
t
F
i
be the subtrees plotted by subqueries (5) and (7),
respectively. If the left bottom leaf node of
t
T
i
(
t
F
i
) is labeled by
T
c
,then
x
i
is
considered to be
true
(resp.,
false
).
