Database Reference
In-Depth Information
Figure 5.3:
The CNF lattices for a query denoted
Q
9
. The query is the conjunction of the co-atoms
in the lattice,
Q
9
=
Q
u
1
∧
Q
u
2
∧
Q
u
3
∧
Q
u
7
, and each latice element is indicated; for example,
Q
u
1
=
h
33
(the queries
h
3
i
were introduced in
Subsection 4.1.5
). The minimal element of the lattice, 0,
represents an intractable query, namely
Q
h
30
∨
0, and
since all other queries in the lattice are in polynomial time,
Q
9
is in polynomial time. Unlike the lattice for
Q
W
, here the bottom element is not “erasable”. It is conjectured that
Q
9
does not admit a polynomial-size
d-DNNF.
0
=
H
3
, but the Möbius function at that point is
μ
=
v,
1
: therefore, the claim hold vacuously. Otherwise,
let
S
=
M
∪
K
, and define
N
={
v
∧
u
|
v
∈
M,u
∈
K
}
If
S
={
v
}
, then
NE(S)
={
v
}
and
S
={
}
. We have
NE(S)
=
NE(M)
∪
NE(K)
∪
NE(N)
.If
z
∈
NE(S)
, then
z
∈
NE(M)
,
z
∈
NE(K)
, and
z
∈
NE
(
N)
. B
y
indu
c
tio
n h
yp
oth
es
is,
μ
M
(z,
1
)
=
μ
K
(z
,
1
)
=
μ
N
(z,
1
)
=
0. Next, we notice that (1)
M,K,N
⊆
S
, (2)
S
=
M
∪
K
∪
N
and (3)
M
N
.Then, we apply the definition of the Möbius function directly (
Definition 4.11
),
using a simple inclusion-exclusion formula:
∩
K
=
μ
S
(z,
1
)
=−
μ
S
(u,
1
)
u
∈
S,z<u
≤
1
(
u
∈
M,z<u
≤
1
μ
S
(u,
1
)
μ
S
(u,
1
)
μ
S
(u,
1
))
=−
+
−
u
∈
K,z<u
≤
1
u
∈
N,z<u
≤
1
=
μ
M
(z,
1
)
+
μ
K
(z,
1
)
−
μ
N
(z,
1
)
=−
0
−
0
+
0
=
0
The lemma implies immediately:
Proposition 5.24
For any UCQ query Q,ifQ is
R
d
-safe, then it is
R
6
-safe. The converse does not hold
in general: query Q
9
Figure 5.3
is
R
6
-safe but it is not
R
d
-safe.
