Database Reference
In-Depth Information
and μ(u,
1
)
=
0, then we get stuck. However, the inversion formula is complete: if at least one query
Q
u
with
μ(u,
1
)
=
0 is hard for #P, then
Q
is hard as well; we will discuss this in
Theorem 4.23
.
For arbitrary queries in the Relational Calculus, the equivalence problem between two queries
is undecidable. We can still construct a CNF lattice for a query
Q
1
∧
...
∧
Q
k
, by using sound
but not necessarily complete query containment and query equivalence relationships. Implicit in
the
Definition 4.12
is the requirement “
u
≤
v
iff
Q
v
⇒
Q
u
”: now, we relax it to “
u
≤
v
implies
Q
v
⇒
Q
u
”.
One question is whether we could evaluate queries differently, by avoiding to use the Möbius
inversion formula. The following result proves that this is not the case.
Theorem 4.22
Let
L
be any finite lattice. Then there exists a UCQ query
Q
such that (a) its CNF
lattice is isomorphic to
L
,
L(Q)
L
, (b) the query
Q
0
is hard for #P, and (c) for any other lattice
element
u
=
0,
Q
u
is a safe query.
This implies that the query
Q
is safe iff
μ(
0
,
1
)
=
0. In other words, any algorithm that figures
out whether
Q
is computable in polynomial time or is hard for #P must, in effect, determine whether
μ(
0
,
1
)
=
0, in some arbitrary lattice
L
.
Proof.
Let
L
be a lattice, and
L
is called
join irreducible
if
r
=
0, and whenever
v
1
∨
v
2
=
r
, then either
v
1
=
r
or
v
2
=
r
. All atoms
3
∧
and
∨
its meet and join operator. An element
r
∈
are
join-irreducible, but the converse is not true, in general. Let
R
={
r
0
,r
1
,...,r
k
}
be all join irre-
ducible elements. For every
u
∈
L
denote
R
u
={
r
|
r
∈
R, r
≤
u
}
. The following properties follow
=
0; (3)
R
u
∨
v
=
immediately. (1)
u
R
v
.
Consider the query
H
k
defined in
Section 3.2
, and denote
h
ki
its components: that is,
H
k
=
h
k
0
∨
...
∨
h
kk
(here
≤
v
iff
R
u
⊇
R
v
; (2)
R
u
=
R
iff
u
R
u
∪
∨
refers to query union), where:
h
k
0
=
R(x
0
), S
1
(x
0
,y
0
)
h
ki
=
S
i
(x
i
,y
i
), S
i
+
1
(x
i
,y
i
)i
=
1
,k
−
1
h
kk
=
S
k
(x
k
,y
k
), T (y
k
)
For ever y
u
∈
L
define
Q
u
=
r
i
∈
R
u
h
ki
(here, too
refers to query union). The following are easy
to check: the CNF lattice of
Q
is isomorphic to
L
;
Q
0
=
H
k
; for any other element
u
=
0,
Q
u
is
the union of a strict subset of
h
k
0
,...,h
kk
, and therefore is a safe query. This proves the claim.
4.1.6 COMPLETENESS
Recall that a query
Q
is
safe
if it is possible to compute
P (Q)
on any database by applying the six
rules in
Subsection 4.1.2
. To be more precise, we denote those six rules
R
6
, and we we say that
Q
is
R
6
-safe, emphasizing that the safety definition is relative to the six rules. Clearly, every safe query is
tractable. But what about the converse? Safety is a syntactic property because it is defined in terms
3
An atom is an element that covers 0.
