Database Reference
In-Depth Information
Figure 4.1:
The CNF lattices for
Q
W
. Note that the bottom of the lattice is the intractable query
H
3
,
but the Möbius function at that point is
μ
=
0, and since all other queries in the lattice are in polynomial
time,
Q
W
is in polynomial time.
=
Q
1
∧
Q
2
∧
Q
3
. Its
Example 4.14
(
Example 4.10
continued) We revisit now the query
Q
W
CNF lattice consists of the following elements:
Q
u
1
=
h
30
∨
h
32
Q
u
2
=
h
30
∨
h
33
Q
u
3
=
h
31
∨
h
33
Q
u
4
=
h
30
∨
h
32
∨
h
33
Q
u
5
=
h
30
∨
h
31
∨
h
33
Q
0
=
h
30
∨
h
31
∨
h
32
∨
h
33
The lattice and its associated Möbius function is shown in
Figure 4.1
. Notice that the Möbius
function for 0 is
μ(
0
,
1
)
=
0: thus we do not need the bottom query in the Möbius inversion rule.
The probability now becomes:
P (Q)
=
P(Q
u
1
)
+
P(Q
u
2
)
+
P(Q
u
3
)
−
P(Q
u
4
)
−
P(Q
u
5
)
Thus,
Q
W
is tractable, and can be computed using the Möbius rule. It's lineage, however, is quite
complex; we will return to it in
Section 5.4
.
Note that in order to construct the CNF lattice we need to be able to check if two queries
are equivalent (to eliminate duplicates). For UCQ queries, this problem is decidable, see
Figure 4.2
.
The CNF lattice is not unique because it depends on the representation
Q
=
Q
1
∧
...
∧
Q
k
of the
UCQ query; however, the co-atomic elements of the lattice are uniquely defined, and so is the set
of lattice elements
u
for which
μ(u,
1
)
=
0; hence, application of the Möbius' inversion formula
is independent of the representation of the query (
Figure 4.2
). The “magic” in Möbius inversion
formula only works if all hard queries
Q
u
in the lattice have
μ(u,
1
)
=
0. If at least one
Q
u
is hard
