Database Reference
In-Depth Information
5. INTENSIONAL QUERY EVALUATION
possible. For a counterexample, consider the query
Q
V
∨
R(x
3
), T (y
3
)
(
Example 4.8
). The OBDD for the sub-query
R(x
1
), S(x
1
,y
1
)
needs to inspect the
S
-tuples in row-major order
S(
1
,
1
), S(
1
,
2
),...,S(
2
,
1
), S(
2
,
2
),...
, while the OBDD for the sub-
query
S(x
2
,y
2
), T (y
2
)
needs column-major order
S(
1
,
1
), S(
2
,
1
),...,S(
1
,
2
), S(
2
,
2
),...
, and
we can no longer synthesize the OBDD for their disjunction (the OBDD for the third subquery
R(x
3
), T (y
3
)
could read these variables in any order).
=
R(x
1
), S(x
1
,y
1
)
∨
S(x
2
,y
2
), T (y
2
)
5.4.2.3
UCQ(FBDD)
It is open whether this class admits a syntactic characterization. However, the following two prop-
erties are known:
Proposition 5.20
(1) The query Q
V
defined in
Example 4.8
admits a polynomial-size FBDD. (2) The
query Q
W
defined in
Example 4.14
does not have a polynomial-size FBDD.
We describe here the FBDD for
Q
V
. It has a spine inspecting the tuples
R(
1
), T (
1
), R(
2
), T (
2
),...
, in this order. Each 0-edge from this spine leads to the next tuple in
the sequence. Consider the 1-edge from
R(k)
: when
R(k)
is true, then the query
Q
V
is equiv-
alent to
Q
=
R(x
1
), S(x
1
,y
1
)
∨
T(y
3
)
. In other words, we can drop the query
S(x
2
,y
2
), T (y
2
)
because it logically implies
T(y
3
)
. But
Q
is inversion-free (in fact, it is even non-repeating); hence,
it has an OBDD of linear size. Thus, the 1-edge from
R(k)
leads to a subgraph that is an OBDD
for
Q
, where all tests for
R(
1
),...,R(k
1
)
have been removed, since they are known to be 0.
Similarly, the 1-edge from
T(k)
leads to an OBDD for
Q
=
R(x
3
)
∨
S(x
2
,y
2
), T (y
2
)
. Notice
that the two subgraphs, for
Q
and for
Q
, respectively, use
different
orders for
S(i,j)
; in other
words, we have constructed an FBDD, not an OBDD. Thus,
Q
V
is in
UCQ(FBDD)
, which proves
UCQ(OBDD)
−
UCQ(FBDD)
.
5.4.2.4
UCQ(d-DNNF)
¬
We give here a sufficient syntactic condition for for membership in this class: it is open whether this
condition is also necessary. For that, we describe a set of rules, called
R
d
, which, when applied to a
query
Q
, compute a polynomial size
d-DNNF
¬
,
d(Q)
, for the lineage
Q
.
Independent-join
d(Q
1
∧
Q
2
)
=
d(Q
1
)
∧
d(Q
2
)
d(
∃
x.Q)
=¬
(
a
∈
Independent-project
ADom
¬
d(Q
[
a/x
]
))
d(Q
1
∨
Q
2
)
=¬
(
¬
d(Q
1
)
∧¬
d(Q
2
))
Independent-union
Expression-conditioning
d(Q
1
∧
Q
2
)
=¬
(
¬
d(Q
1
)
∨¬
(
¬
d(Q
1
∨
Q
2
)
∨
d(Q
2
)))
d(Q)
=
d(Q
r
)
Attribute ranking
