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.
 
Search WWH ::




Custom Search