Database Reference
In-Depth Information
5. INTENSIONAL QUERY EVALUATION
denoted
u
1
,u
2
,u
3
,u
4
,u
5
; we write
Q
u
for the query at each node
u
.Therefore,
Q
W
=
Q
u
1
∧
Q
u
2
∧
Q
u
3
.To apply the
expression-conditioning
rule, we group as follows:
Q
W
=
Q
u
1
∨
(Q
u
2
∨
Q
u
3
)
.Then
the rule gives:
d
d
(Q
u
2
∧
Q
u
3
)
]
¬
Q
W
=¬
Q
u
1
∨
¬[¬
(Q
u
1
∨
(Q
u
2
∧
Q
u
3
))
∨
Thus, we need to compute the
d-DNNF
¬
recursively for three queries:
Q
u
1
,
Q
u
2
∧
Q
u
3
, and
Q
u
3
)
. The first query,
Q
u
1
, has a polynomial-size
d-DNNF
¬
because it is both
hierarchical and non-repeating. The second query
Q
u
2
∧
Q
u
3
is inversion-free query and, there-
fore, by
Proposition 5.19
, has a polynomial-size OBDD, and, hence, it also has a polynomial-size
d-DNNF
¬
. It remains to explain how to construct a
d-DNNF
¬
Q
u
1
∨
(Q
u
2
∧
for
Q
u
1
∨
(Q
u
2
∧
Q
u
3
)
(here
∨
is
not a disjoint-or):
Q
u
1
∨
(Q
u
2
∧
Q
u
3
)
=
(Q
u
1
∨
Q
u
2
)
∧
(Q
u
1
∨
Q
u
3
)
=
Q
u
4
∧
Q
0
=
Q
u
4
This query, too, is inversion-free (see the lattice in
Figure 4.1
and the notations in
Example 4.10
).
It is interesting to examine the CNF lattices of these three queries, which, according to
our disc
uss
ion, are th
e m
eet-closures of
M
={
u
1
}
,
K
={
u
2
,u
3
}
, and
N
={
u
1
∧
u
2
,u
1
∧
u
3
}=
{
u
4
,
0
}
:
M
={
u
1
,
1
}
,
K
={
u
5
,u
2
,u
3
,
1
}
, and
N
={
0
,u
4
,
1
}
. Notice that the co-atomic elements
u
4
,
1
; hence, we have completely eliminated 0. We say that we have “erased 0”.
of
N
are
{
}
We prove now that
R
d
-safety implies
R
6
-safety. Fix a lattice
L
. Every non-empty subset
S
⊆
L
−{
1
}
corresponds to a query,
u
∈
S
Q
u
. We define a no
nd
eterministic function
NE
that maps
a non-empty set
S
−{
1
⊆
L
}
to a set of elements
NE(S)
⊆
S
, as follows. If
S
={
v
}
is a singleton
set, then
NE(S)
={
v
}
. Otherwise, partition
S
non-deterministically into two disjoint, non-empty
sets
S
∪
NE(N)
. Thus,
NE(S)
is non-deterministic because it depends on our choice for partitioning
S
. The
intuition the following: in order for the query
u
∈
S
Q
u
to be
R
d
-safe, all lattice points in
NE(S)
must also be
R
d
-safe: they are “non-erasable”.
Call an element
z
∈
L erasable
if there exists a non-deterministic choice for
NE(L
∗
)
that does
not contain
z
. The intuition is that if
z
is erasable, then there exists a sequence of applications of
the expression-conditioning rule, which avoids computing
z
; in other words, it “erases”
z
from the
list of queries in the lattice for which it needs to compute the
d-DNNF
¬
, and, therefore,
Q
z
is not
required to be
R
d
=
M
∪
K
, define
N
={
v
∧
u
|
v
∈
M,u
∈
K
}
, and define
NE(S)
=
NE(M)
∪
NE(K)
where
μ
L
(z,
1
)
=
0 can be erased:
safe. We prove that only queries
Q
z
If z is erasable in L, then μ
L
(z,
1
)
=
0
.
Lemma 5.23
Proof.
We prove the follo
w
ing claim, by induction on the size of the set
S
:if
z
∈
NE(S)
,
z
=
1,
then
μ
S
(z,
1
)
=
0 (if
z
∈
S
, then we define
μ
S
(z,
1
)
=
0). The lemma follows by taking
S
=
L
∗
(the set of all co-atoms in
L
).
