Database Reference
In-Depth Information
, we denote by
Q
s
=
i
∈
s
Q
i
. Notice that, with these notations, the inclusion-exclusion formula becomes
P (Q)
=
Let
Q
1
,...,Q
k
be
k
queries, and let
Q
=
i
=
1
,k
Q
i
. For every subset
s
⊆[
k
]
−
s
=∅
1
)
|
s
|
P(Q
s
)
.
(
−
Definition 4.12
The CNF-lattice of the query
Q
=
Q
1
∧
...
∧
Q
k
is the lattice
(L,
≤
)
, where:
The elements of
L
are queries
Q
s
, for
s
⊆[
k
]
, up to logical equivalence.
The order relation
≤
is defined as follows:
Q
s
1
≤
Q
s
2
iff the logical implication
Q
s
2
⇒
Q
s
1
holds.
Thus, when constructing the CNF lattice, we start by forming all 2
k
,
but we eliminate duplicates: whenever two queries are logically equivalent
Q
s
1
≡
Q
s
2
, we only keep
one of them. The lattice
L
consists of all such queries, up to logical equivalence; in general,
queries
Q
s
for
s
⊆[
k
]
2
k
.
Note that
k
depends only on the query, not the database instance: thus, we can afford to compute
Q
s
for all the 2
k
possible sets
s
; we do not consider the database instance at all at this point. The
minimal element of the lattice corresponds to
s
=[
k
]
|
L
|≤
and is 0
≡
Q
1
∨
Q
2
∨
...
∨
Q
k
. The maximal
and is denoted 1. We note that the lattice meet operation
element of the lattice corresponds to
s
=∅
∧
corresponds to query union
∨
: in this topic,
∨
refers to query union (hence lattice-meet) unless
otherwise stated.
Given a lattice element
u
L
, we write
Q
u
for the query associated with
u
, for example,
Q
0
=
Q
1
∨
...
∨
Q
k
, where 0 is the minimal element of the lattice. The following is a classic
application of the Möbius function.
∈
Proposition 4.13
Möbius inversion formula
Let Q
=
Q
1
∧
Q
2
∧
...
∧
Q
k
and let (L,
≤
) be its
CNF lattice. Then:
μ(u,
1
)P (Q
u
)
P (Q)
=−
u<
1
We use formula to replace the earlier inclusion-exclusion formula
Eq. (4.7)
:
4.1.5.1 Rule 5: Möbius Inversion Formula (Replaces the Inclusion/Exlusion rule)
Suppose a query can be written as
Q
=
Q
1
∧
...
∧
Q
k
. Then its probability is:
μ(u,
1
)
·
P(Q
u
)
Möbius
P(Q
1
∧
Q
2
∧
...
∧
Q
k
)
=−
(4.9)
u<
1
:
μ(u,
1
)
=
0
Notice that we explicitly remove from the sum those terms where
μ(u,
1
)
=
0 because as we have
seen, there are cases when
P(Q
u
)
is hard to compute, yet
μ(u,
1
)
=
0.
