Database Reference
In-Depth Information
Primer on Lattices
We follow [
Stanley
,
1997
]. Fix a finite lattice
(L,
≤
)
.
L
such that
y<z<x
;
x
is an
atom
if it covers 0;itisa
co-atom
if it is covered by 1.
L
∗
denotes the set of co-atoms.
x covers y
if
y<x
and there is no
z
∈
Definition 4.15
=
T
=
k
(
L
∗
,
. Then
a
μ
L
(z,
1
)
1
)
k
N
k
(z)
.
Denote
N
k
(z)
=|{
T
|
T
⊆
|
T
|=
k, z
}|
−
S
={
T
.
S
is a lattice
b
.
z
∈
L
is
called
co-atomic
if
z
∈
L
∗
.
L
is called a
co-atomic lattice
if all elements are co-atomic.
Th
e
m
eet closure
of
S
⊆
L
is
|
T
⊆
S
}
Definition 4.16
Since
N
k
(z)
is the same in
L
and in
L
∗
, it follows:
(a) If z
∈
L
∗
then μ
L
(z,
1
)
=
0
. (b) If z
∈
L
∗
then μ
L
(z,
1
)
=
μ
L
∗
(z,
1
).
Corollary 4.17
Primer on Unions of Conjunctive Queries
All queries are Boolean.
A CQ query
Q
is
disconnected
if
Q
≡
Q
1
∧
Q
2
, where
Q
1
≡
true
and
Q
2
≡
Definition 4.18
true
; otherwise,
Q
is called
connected
.
A UCQ query can be written in either DNF or CNF:
Definition 4.19
A UCQ query is in DNF if
Q
=
Q
i
•
where each
Q
i
isaCQ.
A
Disjunctive Query
(DQ), is
Q
i
where each
Q
i
is a connected CQ.
•
A UCQ query is in CNF if
Q
=
i
Q
i
•
where each
Q
i
is a DQ.
[
Abiteboul et al.
,
1995
]
Proposition 4.20
Given CQs Q, Q
: Q
⇒
Q
iff there exists a homomorphism h
:
Q
→
Q.
•
Given DNFs Q
=
Q
i
, Q
=
Q
j
: Q
⇒
Q
iff
∀
i.
∃
j such that Q
i
⇒
Q
j
.
•
•
Every UCQ query has a unique minimal DNF representation up to isomorphism.
[
Dalvi and Suciu
,
2010
] Assume all queries are without constants
c
.
Proposition 4.21
=
Q
i
, Q
=
Q
j
: Q
Q
iff
Q
j
.
•
Given CNFs Q
⇒
∀
j.
∃
i such that Q
i
⇒
•
Every UCQ Q has a unique minimal CNF representati
on
Q
0
up to isomorphism. Let L
=
L(Q)
and L
0
=
L
∗
.
L(Q
0
) be their CNF lattices. Then L(Q
0
)
=
By
Corollary 4.17
, we obtain the same result if we apply Möbius' inversion formula to a CNF
Q
or to its minimized CNF
Q
0
.
a
Stanley
[
1997
, Corollary 3.9.4];
N
k
(x)
is the number of
k
-sets of co-atoms whose meet is
z
.
b
Because it is a meet-lattice with a maximal element: 1
∈
S
, by taking
T
.
c
If
Q
has constants, then the first bullet fails:
Q
1
=
R(a)
,
Q
2
=
S(a)
,
Q
=∃
x.R(x),S(x)
, then
Q
1
∧
Q
2
⇒
Q
,yet
Q
i
⇒
Q
for
i
=
1
,
2.
=∅
Figure 4.2:
Primer on Lattice Theory and UCQ Queries in CNF.