Database Reference
In-Depth Information
These rules correspond one-to-one to the rules
R
6
in
Subsection 4.1.2
, except that inclusion-
exclusion is replaced with
expression-conditioning
. For every rule, we assume the same preconditions
as for the corresponding
R
6
rule. For example,
Q
1
,Q
2
must be independent in the
independent-
join
and
independent-union
rules, and
x
must be a separator variable in
independent-project
.Asa
consequence, all operations used in these rules are permitted by
d-DNNF
¬
's: all
∧
's are independent,
and all
's are disjoint.
R
d
-safety is a sufficient condition for membership in
UCQ(d-DNNF)
¬
, but it is open whether
it is also a necessary condition:
∨
Proposition 5.21
Let Q be a UCQ query that is
R
d
-safe (meaning that the rules
R
d
terminate on Q).
UCQ(d-DNNF)
¬
.
Then Q
∈
We explain now the
expression-conditioning
rule. For a query
Q
=
Q
1
∧
Q
2
, we have the
following derivation for
d
¬
Q
, where we write
∨
to indicate that a
∨
operation is disjoint:
¬
(Q
1
∧
Q
2
)
=¬
Q
1
∨¬
Q
2
=¬
d
Q
1
∨
[
Q
1
∧¬
Q
2
]
d
=¬
Q
1
∨
¬[¬
Q
1
∨
Q
2
]
d
d
Q
2
]
=¬
Q
1
∨
¬[
(
¬
Q
1
∧¬
Q
2
)
∨
d
d
Q
2
]
=¬
Q
1
∨
¬[¬
(Q
1
∨
Q
2
)
∨
(5.12)
=
i
Q
i
, where the
R
6
rules would normally apply Möbius' inversion formula on the CNF lattice
L
=
L(Q)
. The effect of the expression-conditioning rule is that it reduces
Q
to three subqueries,
namely
Q
1
,
Q
2
, and
Q
1
∨
Q
2
, whose CNF lattices are meet-sublattices of
L
, obtained as follows.
Let
Q
=
Q
1
∧
Q
2
, where
Q
1
=
Q
11
∧
Q
12
∧
...
and
Q
2
=
Q
21
∧
Q
22
∧
...
, and let
L
denote the
CNF lattice of
Q
. Denote
v
1
,...,v
m
,u
1
,...,u
k
the co-atoms of this lattice (see the lattice primer
in
Figure 4.2
), such that
v
1
,v
2
,...
are the co-atoms corr
es
ponding to
Q
11
,
Q
12
,
...
and
u
1
,u
2
,...
are the coatoms for
Q
21
,
Q
22
, …Recall (
Figure 4.2
) that
S
denotes the meet-closure of a set
S
This justifies the
expression-conditioning
rule. In general, this rule is applied to a query
Q
⊆
L
.
The CNF lattice of
Q
1
=
Q
11
∧
...
∧
Q
1
m
is
M
, where
M
={
v
1
,...,v
m
}
.
The CNF lattice of
Q
2
=
Q
21
∧
...
∧
Q
2
k
is
K
, where
K
={
u
1
,...,u
k
}
.
Q
1
∨
Q
2
=
i,j
(Q
1
i
∨
Q
2
j
)
The
CNF
lattice
of
is
N
,
where
N
={
v
i
∧
u
j
|
i
=
1
,m
;
j
=
1
,k
}
.
Here
v
i
∧
u
j
denotes
the
lattice-meet,
and
corresponds
to
the
query-union.
It follows immediately that the
expression-conditioning
rule terminates because each of the
three lattices above,
M,
K,
N
is a strict subset of
L
.
Example 5.22
For a simple illustration of the
expression-conditioning
rule, consider the query
Q
W
in
Figure 4.1
. We will refer to the notations introduced in
Example 4.14
. The lattice elements are
