Database Reference
In-Depth Information
H
0
H
1
H
2
UCQ
UCQ
H
3
Q
9
Necessary
and sufficient
characterization
UCQ(P)
UCQ(P)
?
UCQ(d-DNNF)
(
Q
W
)
Sufficient
Characterization
(Necessary
conjectured)
UCQ(FBDD)
Q(
Q
V
)
UCQ(OBDD)
UCQ(O
)
Q
J
Q
U
UCQ(RO)
Figure 5.4:
The query compilation hierarchy for Unions of Conjunctive Queries (UCQ).
UCQ(d-DNNF)
¬
. Note that the proposition only states that
Q
9
is
not
R
d
-safe, but it is not known whether
R
d
is a complete set of rules.
It is conjecture that
Q
9
∈
Proof.
We prove the statement by induction on
Q
. We show only the key induction step, which is
when
Q
=
i
Q
i
, and
L
is its CNF lattice. Let
Z
L
denote the nodes corresponding to
R
d
-unsafe
queries: if
Q
is
R
d
-safe, then all elements in
Z
are erasable. This implies that
⊆
∀
z
∈
Z
,
μ(z,
1
)
=
0.
Hence, we can apply Möbius' inversion formula to the lattice
L
, and refer only to queries that are
R
d
-safe; by induction hypothesis, these queries are also
R
6
-safe, implying that
Q
is
R
6
-safe.
We show that
Q
9
in
Figure 5.3
is
R
6
-safe, but is not
R
d
-safe. Indeed, the query at 0 is the
only hard query (since it is equivalent to
H
3
), and
μ(
0
,
1
)
0. On the other hand, we prove that 0
cannot be erased. Indeed, the coatoms of the lattice are
L
∗
={
u
1
,u
2
,u
3
,u
7
}
=
; given the symmetry
of
u
1
,u
2
,u
3
, there are only three ways to partition the coatoms into two disjoint sets
L
∗
=
M
∪
K
:
{
0
,u
4
,u
5
,u
6
,u
1
,u
2
,u
3
,
1
}
M
={
u
1
,u
2
,u
3
}
,
K
={
u
7
}
. In this case, the lattice
M
is
, and
μ
M
(
0
,
1
)
=−
1, proving that this query is
R
6
-unsafe, and, therefore,
R
d
-unsafe.
{
0
,u
3
,u
7
,
1
and has
μ
K
(
0
,
1
)
=
M
={
u
1
,u
2
}
,
K
={
u
3
,u
7
}
. In this case the lattice
K
is
}
1;
hence, by the same argument, is
R
d
-unsafe.
. Here, too,
K
={
0
,u
6
,u
2
,u
3
,u
7
,
1
}
, and
μ
K
(
0
,
1
)
=
1.
M
={
u
1
}
,
K
={
u
2
,u
3
,u
7
}
5.4.2.5
UCQ(P)
Finally, this class represents all tractable queries, which, by
Theorem 4.23
, are precisely the
R
6
-safe
queries. It is easy to see that
Q
9
is safe because the Möbius function for the bottom lattice element
is 0. Thus,
Q
9
is a candidate query for separating
UCQ(d-DNNF)
from
UCQ(P)
.
