Database Reference
In-Depth Information
5. INTENSIONAL QUERY EVALUATION
5.4.2 UNIONS OF CONJUNCTIVE QUERIES
On the contrary, for unions of conjunctive queries,
L
=
UCQ
, these classes can be shown to form
a strict hierarchy, except for the inclusion
UCQ(d-DNNF)
¬
UCQ(P )
, for which it is still open
whether it is strict.
[
Jha and Suciu
,
2011
]
Let
L
=
UCQ
be the language of unions of conjunctive
Theorem 5.14
queries. Then
(d-DNNF
¬
).
L
(RO)
L
(OBDD)
L
(FBDD)
L
We explain the theorem by illustrating each separation result: also refer to
Figure 5.5
and to
Figure 5.4
.
5.4.2.1
UCQ
(RO)
This class admits a simple syntactic characterization.
UCQ
H,NR
Proposition 5.15
UCQ(RO)
=
The inclusion
UCQ
H,NR
UCQ(RO)
follows from the proof of
Proposition 4.27
: that proof
actually shows that if a query is in
RC
H,NR
, then its lineage on any probabilistic database is a read-
once propositional formula. The proof of the opposite inclusion is given in [
Jha and Suciu
,
2011
].
In other words, we can check whether a query
Q
has a read-once lineage for all input databases,
by examining the query expression: if we can write
Q
such that it is both hierarchical and non-
repeating, then its lineage is always read-once; otherwise, there exists databases for which
Q
's lineage
is not read-once.
We illustrate the proposition with a few examples.
⊆
Example 5.16
Consider the Boolean query
Q
=
R(x),S(x,y)
(
Example 4.6
). It is both hierar-
chical and non-repeating; hence, its lineage is always read-once. To see this, denote
X
1
,...,X
n
the
Boolean variables associated with
R
-tuples, and
Y
11
,Y
12
,...,Y
nn
the Boolean variables associated
with the
S
-tuples. Thus,
X
i
represents the tuple
R(i)
and
Y
ij
represents the tuple
S(i,j)
. The lineage
is:
Q
=
X
1
Y
11
∨
X
1
Y
12
...X
1
Y
1
n
∨
X
2
Y
21
∨
...X
n
Y
nn
=
X
1
(Y
11
∨
Y
12
...)
∨
X
2
(Y
21
∨
Y
22
∨
...)
∨
...
For another example, consider
Q
U
=
R(x
1
), S(x
1
,y
1
)
∨
T(x
2
), S(x
2
,y
2
)
(
Example 4.7
). If we
write it as
∃
x.(R(x)
∨
T(x))
∧∃
y.S(x,y)
, then it is both hierarchical
and
read-once, and therefore
