Computing Join Queries with Functional Dependencies

arXiv:1604.00111v2 [cs.DB] 7 Apr 2016

Mahmoud Abo Khamis
LogicBlox, Inc.
& SUNY Buffalo

Hung Q. Ngo
LogicBlox, Inc.
& SUNY Buffalo

Dan Suciu
LogicBlox, Inc.
& University of Washington

Abstract
Recently, Gottlob, Lee, Valiant, and Valiant (GLVV) presented an output size bound for join queries
with functional dependencies (FD), based on a linear program on polymatroids. GLVV bound strictly
generalizes the bound of Atserias, Grohe and Marx (AGM) for queries with no FD, in which case there
are known algorithms running within AGM bound and thus are worst-case optimal.
A main result of this paper is an algorithm for computing join queries with FDs, running within
GLVV bound up to a poly-log factor. In particular, our algorithm is worst-case optimal for any query
where the GLVV bound is tight. As an unexpected by-product, our algorithm manages to solve a harder
problem, where (some) input relations may have prescribed maximum degree bounds, of which both
functional dependencies and cardinality bounds are special cases.
We extend Gottlob et al. framework by replacing all variable subsets with the lattice of closed
sets (under the given FDs). This gives us new insights into the structure of the worst-case bound and
worst-case instances. While it is still open whether GLVV bound is tight in general, we show that it
is tight on distributive lattices and some other simple lattices. Distributive lattices capture a strict
superset of queries with no FD and with simple FDs. We also present two simpler algorithms which are
also worst-case optimal on distributive lattices within a single-log factor, but they do not match GLVV
bound on a general lattice. Our algorithms are designed based on a novel principle: we turn a proof of
a polymatroid-based output size bound into an algorithm.

1

Introduction

Several results published in the last ten years or so have lead to tight worst-case output size bounds
(AGM-bound [3, 13]) and the development of a new class of query processing algorithms running within
the bound’s time budget [18,19,23]. These new worst-case optimal algorithms are quite different from traditional query plans, in the sense that they no longer compute one pairwise join at a time, but instead process
˚
the query globally. The runtime is bounded by OpN ρ q, where N is the size of the database, while ρ˚ is
the value of the optimal fractional edge cover of the query. For example, they compute the triangle query
Qpx, y, zq :- Rpx, yq, Spy, zq, T pz, xq, in worst-case time OpN 3{2 q, while any traditional query plan requires
worst-case time ΩpN 2 q [19].
While the vast majority of database engines today still rely on traditional query plans, new, complex
data analytics engines increasingly switch to worst-case optimal algorithms: LogicBlox’ engine [2] is built
on a worst-case optimal algorithm called LeapFrog Triejoin [23] (LFTJ), the Myria data analytics platform
supports a variant of LFTJ [7], and the increased role of SIMD instructions in modern processors also favors
the new class of worst-case optimal algorithms [1].
When there are functional dependencies (FDs), however, the AGM-bound is no-longer tight. Gottlob,
Lee, Valiant, and Valiant [11] initiated the study of the worst-case output size of a query in the presence of
FDs and described an upper bound (reviewed in Section 2), called the GLVV-bound henceforth. It remains
open whether the GLVV bound is tight; at the present, it is the best known upper bound for the query size
in the presence of FDs. A recent result by Gogacz and Toruńczyk [10] proved a weaker statement, namely
that if we replace the polymatroidal constraints in the GLVV-bound with entropic constraints (of which
there are infinitely many), then the bound is tight.
Our paper proposes a novel approach to studying queries in the presence of FDs, by using lattice theory.
We present several theoretical results that clarify precisely where queries with FDs become more difficult
to study than those without. We describe a an algorithm which runs in time proportional to the GLVVbound, within a polylogarithmic factor. We also describe two special cases where the polylogarithmic factor
is reduced to a single log. Before discussing our results, we explain their significance.

1.1

Motivation

User-Defined Functions. UDF’s, or interpreted predicates, significantly affect the runtime of a query.
Consider:
Qpx, y, z, uq :- Rpx, yq, Spy, zq, T pz, uq, u “ f px, zq, x “ gpy, uq.
(1)
The predicates u “ f px, zq and x “ gpy, uq represent two user-defined functions, f and g; for example
f px, zq could be x ` z, or the concatenation of two strings x and z. Any UDF can be modeled as a relation
with a primary key, for example the function f can be viewed as a relation F px, z, uq of cardinality N 2
(with one entry for every x, z pair) satisfying the FD xz Ñ u; similarly g introduces the FD yu Ñ x. The
addition of these two FD’s significantly affects the output size and the query evaluation complexity: if we
first computed the intermediate query Rpx, yq, Spy, zq, T pz, uq then applied the two predicates u “ f px, zq
and x “ gpy, uq then the runtime can be as high as N 2 because the size of the intermediate query is N 2 when
R “ {pi, 1q | i P rN s}, S “ {p1, 1q}, T “ {p1, iq | i P rN s}. However, as we will show, the GLVV bound for the
size of Q is ď N 3{2 . Our new algorithms run in ÕpN 3{2 q, and thus reduce the running time asymptotically.
As shall be seen, this runtime is also worst-case optimal.
A related problem is querying relations with restricted access patterns [5]. In that setting, some of the
relations in the database can only be read by providing the values of one or more attributes. As shown above,
a user defined function f px, zq can be modeled as an infinite relation F pu, x, zq ” pu “ f px, zqq with the
restriction that F can be accessed only by providing inputs for the variables x and z. The work on querying
under restricted access patterns has focused on the answerability question (whether a query can or cannot
be answered). Our work extends that, by finding algorithms for answering the query within GLVV-bound.

2

Known Frequencies. Systems often know an upper bound on the frequencies (or degrees) in the database.
For example, consider the triangle query above, and assume that the binary graph defined by the relation
Rpx, yq has a bounded degree: all outdegrees are degpxq ď d1 and all indegrees are degpyq ď d2 . One can
model this scenario by introducing an artificial color c1 on outgoing edges, and a color c2 for incoming edges
of R:
Qpx, y, z, c1 , c2 q :- Rpx, c1 , c2 , yq, Spy, zq, T pz, xq, C1 pc1 q, C2 pc2 q,
xc1 Ñ y, yc2 Ñ x, xy Ñ c1 c2

(2)

where |R| “ |S| “ |T | “ N and |C1 | “ d1 , |C2 | “ d2 . Thus, each outgoing edge from x is colored with
some distinct color c1 , and similarly each incoming edge to y is colored with some distinct color c2 . The
new predicates C1 , C2 limit the number of colors to d1 , d2 respectively. We will show that the worst case
query output decreases from N 3{2 to minpN 3{2 , N d1 , N d2 q Alternatively, we can use the linear program and
algorithm in Sec 5.3 to capture queries with known maximum degree bounds. We note that another approach
to evaluate a limited class of queries over databases with known degrees has been recently described in [15].

1.2

Overview of the Results

Grohe and Marx [13] and later
Grohe and Marx [3] derived an elegant tight upper bound on the
Q Atserias,
wj
,
where
R1 , . . . , Rm are the input relations to the query, and pwj qm
output size of a join query: m
|R
|
j
j“1
j“1
is any fractional edge cover of the query’s hypergraph. This bound is known today as the AGM bound. A
simple example that gives a great intuition for this formula, due to Grohe [12], is the following. Suppose
we choose a subset of relations Rj1 , Rj2 , . . . that together contain all variables of the query, in other words
they form an integral cover of the query’s hypergraph. Then, obviously |Q| is upper bounded by the product
|Rj1 ||Rj2 | ¨ ¨ ¨ , because the output to Q is contained in the cross product of these relations. The AGM bound
simply generalizes this property from integral to fractional edge covers. They proved that the bound is tight
by describing a simple database instance for any query, such that the query’s output matches the bound. In
that instance, every relation is a cross product of sets, one set per variable; we call it a product instance.
An obvious open question was whether a query Q can be evaluated on any database instance D in
time that is no larger than the AGM bound of Q on databases with the same cardinalities as D; such an
algorithm is called worst-case optimal. Ngo, Porat, Ré, and Rudra [18] described the first worst-case optimal
algorithm; later Veldhuizen [23] proved that LFTJ, an algorithm already implemented at LogicBlox earlier,
is also worst-case optimal. A survey and unification of these two algorithms can be found in [19].
Neither the AGM bound nor the associated algorithms analytically exploit FDs in the database.1 Such
FDs can provably reduce the worst-case output of a query, but the upper bound and algorithms mentioned
above cannot use this information, and instead treat the query by ignoring the FDs. Gottlob et al. [11]
studied the upper bound of the query size in the presence of FDs, and established two classes of results.
The first was a characterization of this bound in the case when the FD’s are restricted to simple keys; as we
will show, this case can be solved entirely using the AGM bound by simply replacing each relation with its
closure. Next, they described a novel approach to reasoning about the worst-case output of a query, using
information theory. They viewed the query output as a multivariate probability space, and introduced two
constraints on the marginal entropies: a cardinality constraint for each input relation R, stating that the
entropy of its variables cannot exceed the uniform entropy HpvarspRqq ď log2 |R|, and one constraint for
each FD X Ñ Y , stating HpXY q “ HpXq. (Note that X and Y are sets of variables.) The largest answer
to the query Q is then given by the largest possible value of 2HpvarspQqq , over all choices of entropic functions
H that satisfy these constraints. But characterizing the space of all entropic functions H is a long standing
open problem in information theory [24]; to circumvent that, they relax the function H by allowing it to be
any function that satisfies Shannon inequalities. Such a function is called a polymatroid in the literature, and
we denote it with lower case h to distinguish it from entropic functions H. Thus, the problem in [11] can be
1 Algorithmically, LFTJ handles FDs by binding variables at the earliest trie level at which they are functionally determined.
For example, in Rpx, yq, Spy, zq, T pz, uq, u “ f px, zq, x “ gpy, uq with a key order rx, y, z, us, whenever z was bound the value of
u would be immediately computed by u “ f px, zq.

3

stated equivalently as: find the maximum value hpvarspQqq where h ranges over all polymatroids satisfying
the given constraints.
In this paper, we continue the study of query evaluation under general FDs. We establish both bounds
and algorithms. Our novelty is to model FDs as a lattice L of the closed sets of attributes, and to study
polymatroids on lattices. The function h is now any non-negative, monotone, sub-modular function (i.e.
hpXq ` hpY q ě hpX _ Y q ` hpX ^ Y q) that satisfies all cardinality constraints. FD constraints are enforced
automatically by the lattice structure and the upper bound on the query size is 2max hpvarspQqq . When there
are no FDs, the lattice is a Boolean algebra.
Our first question is whether the elegant AGM bound and worst-case product instance carries over to
arbitrary FDs. We answer this question completely, by proving that both sides of the AGM bound hold
iff the lattice has a special structure, which we call a normal lattice. Both upper and lower bounds require
minor extensions to be applicable to normal lattices. The standard AGM upper bound is given in terms
of fractional edge covers of the query’s hypergraph, but in a normal lattice one needs to consider a dual
hypergraph, whose nodes are L’s co-atoms. In a Boolean algebra, these two hypergraphs are isomorphic,
because of the bijection X ÞÑ pvarspQq ´ {X}q between variables and co-atoms, but in a general lattice they
can be significantly different. The notion of normal lattice seems novel, and strictly includes all distributive
lattices, which in turn include all lattices corresponding to simple FDs (each FD is of the form a Ñ b, where
a, b are attributes). The second minor change is that one needs to allow for a slight generalization of product
instances, to what we call quasi-product instances. Importantly, both these properties fail on non-normal
lattices; in particular, worst-case instances cannot be quasi-free.
The canonical example of a non-normal lattice is M3 (one of the two canonical non-distributive lattices,
see the right part of Fig. 3). Every lattice L that contains M3 as a sublattice such that max L “ max M3 is
non-normal; we conjecture that the converse also holds. Interestingly, the other canonical non-distributive
lattice N5 is normal.
Next, we examine algorithms whose runtime is bounded by the GLVV bound. We propose a novel methodology for designing such algorithms, starting from the observation that such an
Palgorithm must provide a proof
of the query’s upper bound, equivalently, a proof of an inequality of the form j wj hpvarspRj qq ě hpvarspQqq,
where R1 , R2 , . . . are the input relations. In the case of a Boolean algebra, Shearer’s lemma [8] is of this
form; in a normal lattice this corresponds to a fractional edge cover of the co-atomic hypergraph; and, for a
general lattice it is a general inequality. A key motivation behind NPRR [18] was to prove inequalities algorithmically. This paper completes the cycle by proceeding in the opposite direction: given a proof method
for such inequalities, we design algorithms whose steps correspond to the proof steps. We design three such
algorithms, corresponding to three methods for proving the above type of inequalities.
The first algorithm called the chain algorithm runs within the chain bound; the proof technique is adapted
from Radhakrishnan’s proof [20] of Shearer’s lemma to general lattices. Both the chain bound and algorithm
strictly generalize AGM-bound and worst-case optimal algorithms for join queries without FDs. The second
algorithm, called the sub-modular algorithm, runs within the sub-modularity bound; the proof technique is
that of Balister and Bollobás’s [4]. The third algorithm, called the conditional sub-modularity algorithm
(CSMA) runs within the general GLVV bound, up to a polylogarithmic factor; the proof technique is our
own, based on linear programming duality. In addition to being able to achieve the most general bound,
CSMA can be used straightforwardly to handle input relations with known maximum degree bounds. We
remark that GLVV bound is stronger than both the other two bounds. We show that they are tight, and
thus our algorithms are worst-case optimal, for distributive lattices.
Outline. The paper is organized as follows. Background material is reviewed in Sec. 2, and basic definitions
for our lattice-based approach are given in Sec. 3. We describe the main result on normal lattices in Sec. 4,
then present our three algorithms and bounds in Sec. 5.

4

2

Notations and Prior Results

For any positive integer n, rns denotes the set {1, . . . , n}. All log in the paper are of base 2. We fix a
relational schema R “ {R1 , . . . , Rm } whose attributes belong to a set of attributes X “ {x1 , . . . , xk }. We
refer to xi P X interchangeably as an attribute or a variable; similarly we refer to Rj as a relation, or
an input. We use lower case letters x P X to denote single variables, and upper case letters X Ď X to
denote sets of variables. The domain of variable x is denoted by Domainpxq. For each relation Rj we denote
varspRj q “ Xj Ď X its set of attributes, and sometimes blur the distinction between Rj and Xj , writing,
with some abuse, Rj Ď X. We consider full conjunctive queries without self-joins:
Qpx1 , . . . , xk q :- R1 pX1 q, . . . , Rm pXm q

(3)

We will drop variables from the head, since it is understood that all variables need to be listed.
A database instance D consists of one relational instance RjD for each relation symbol; we denote
P
D
the anNj “ |RjD |, N “ |D| “
j Nj , and use lower case for logs, nj “ log2 Nj . We denote Q
swer toQQ on the database instance D. A product database instance is a database instance such that
RjD “ xi PRj Domainpxi q for j P rms; the query answer on a product database is the cross product of all
Q
domains, QD “ ki“1 Domainpxi q.

The AGM Bound. A series of results over the last ten years [3, 13, 18, 19, 23] have established tight
connections between the maximum output size of a query and the runtime of a query evaluation algorithm.
The query hypergraph of a query Q is HQ “ pX, Rq; its nodes are the variables and its hyperedges are
the input relations (where each Rj P R is viewed as a set of variables). Consider the following two linear
programs (LP’s), called weighted fractional edge cover LP and vertex packing LP, respectively:
(Weighted) P
Fractional Edge Cover
minimize
w n
Pj j j
ě 1, @i P rks
j:xi PRj wj
wj ě 0, @j P rms

(Weighted)P
Fractional Vertex Packing
maximize
v
Pi i
ď nj , @j P rms
i:xi PRj vi
vi ě 0,
@i P rks

We call a feasible solution to the first LP a fractional edge cover, and to the second a fractional vertex
packing. The traditional (unweighted) notions correspond to nj “ 1, @j.
Theorem 2.1 (AGM bound). [3, 13] (1) Let pwj qm
Then, for any input
j“1 be a fractional edge cover.
P
wj nj
D
j
. In other words,
database D s.t. |Rj | ď Nj for all j P rms, the output size of Q is bounded by 2
Q
w
|QD | ď j Nj j . (2) Let vi , i P rks be a fractional vertex packing, and let D be the product database instance
Q
where Di “ r2vi s. Then, |QD | “ i 2vi .

(In the statement above, we ignore the issue of integrality of the vi for the sake of clarity. There is a bit
of loss when vi are not integers, but this fact does not affect the asymptotics of the lowerbound [3].) By
strong duality, these two LPs have the same optimal objective value, denoted by ρ˚ pQ, pNj qm
j“1 q [12]. Let
pwj˚ qm
be
the
optimal
edge
cover.
The
AGM
bound
of
the
query
Q
is
j“1
˚

ρ
AGMpQ, pNj qm
j“1 q “ 2

pQ,pNj qm
j“1 q

“

Y

w˚

Nj j ,

j

or just AGMpQq when the cardinalities pNj qm
j“1 are clear from the context. The query’s output size is
always ď AGMpQq, and this bound is tight, because on the
database described above, the output
Q product
w
is AGMpQq. It is easy to check that AGMpQq “ minw j Nj j , where w ranges over the vertices of the
edge cover polytope. For example, for Q “ Rpx, yq, Spy, zq, T pz, xq the edge cover polytope has vertices

p 12 , 12 , 12 q, p1, 1, 0q, p1, 0, 1q, p0, 1, 1q , thus,
p
AGMpQq “ minp NR NS NT , NR NS , NR NT , NS NT q
(4)
5

Several query evaluation algorithms have been described in the literature with runtime2 ÕpN `AGMpQqq:
NPRR [18], LFTJ [23], Generic-join [19].
Functional Dependencies. A query with functional dependencies is a pair pQ, FDq, where Q is a query
and FD is a set of functional dependencies (fd), which are expressions of the form U Ñ V where U, V Ď X. An
fd can be either defined by some relation Rj pXj q, in which case we call it guarded (in particular U, V Ď Xj ),
or can be defined by a UDF (as we saw in Sec. 1.1), and then we call it unguarded. A simple fd is of the
form u Ñ v where both u, v are variables, and a simple key is a simple fd guarded in some Rj s.t. u is a key
for Rj .
Output size bounds in the presence of a set of fd’s was studied in [11]. Their bound is defined only in
terms of the maximum cardinality, maxj Nj , but in this paper we generalize the discussion to all cardinalities
pNj qj . The key technique introduced in [11] consists of using information theory to upper bound the size of
the query, as reviewed next.
Qk
Let QD be the query answer over some instance D. Define a probability distribution over i“1 Di by
randomly drawing one tuple from QD with probability 1{|QD | each. Under this distribution, the joint entropy
of the k random variables X is HpXq “ log2 |QD |. Each subset of variables X Ď X defines a (marginal)
distribution, with entropy HpXq. If X “ Xj (“ varspRj q), then H must satisfy the following cardinality
constraint HpXj q ď log2 Nj “ nj , because ΠXj pQD q Ď RjD and the marginal entropy is bounded above by
the uniform marginal entropy. With some abuse we write HpRj q ď log2 Nj , blurring the distinction between
Rj and Xj . In addition, for any fd U Ñ V the entropy must satisfy the fd-constraint HpU q “ HpU V q.
We give here a very simple illustration of how the approach in [11] models the query output using entropy,
by illustrating on the query Qpx, y, zq “ Rpx, yq, Spy, zq, T pz, xq (without fd’s) and output with five outcomes:
x
a
a
b
d
a

y
3
2
2
3
3

z
r
q
q
r
q

1{5
1{5
1{5
1{5
1{5

x
a
a
b
d

y
3
2
2
3

2{5
1{5
1{5
1{5

y
3
2
3
4

z
r
q
q
q

2{5
2{5
1{5
0

x
a
a
b
d

z
r
q
q
r

1{5
2{5
1{5
1{5

Here Hpxyzq “ log 5, Hpxyq ď log |R| “ log 4, Hpyzq ď log |S| “ log 4, and Hpxzq ď log |T | “ log 4.
GLVV Bound. Gottlob et al. [11] observe that log |QD | ď maxH HpXq, where H ranges over all entropic
functions that satisfy the cardinality constraints and the fd-constraints, and this bound has recently been
shown to be tight [10]. However, computing this upper bound is extremely difficult, because of a long standing
open problem in information theory: the characterization of the cone of the closure of the set of entropic
functions. To circumvent this difficulty, in [11] the entropic function H is replaced with a polymatroid
function h. A polymatroid over a set of variables X is a function h : 2X Ñ R` that satisfies the following
inequalities, called Shannon inequalities:
hpXq ` hpY q ě hpX X Y q ` hpX Y Y q
hpX Y Y q ě hpXq
hpHq “ 0

Sub-modularity
Monotonicity
Zero

Every entropic function H is a polymatroid, and the converse fails when X has four or more variables [25].
def
The bound introduced in [11] is GLVVpQ, FD, pNj qj q “ maxh hpXq, where h ranges over all polymatroids
that satisfy all cardinality constraints hpXj q ď nj , and all fd-constraints hpU V q “ hpU q for U Ñ V P FD.
We abbreviate it GLVVpQq when FD and pNj qj are clear from the context. Clearly GLVVpQq is an upper
bound on |QD |, and it is open whether the bound is always tight.
2 Õ

means up to a logarithmic factor.

6

Closure. Fix a set FD. The closure of a set X Ď X is the smallest set X ` such that X Ď X ` , and that
U Ñ V P FD and U Ď X ` imply V Ď X ` . The intersection X ` X Y ` of closed sets is closed, hence the
family {X ` | X Ď X} is a closure.
Denote by Q` the query obtained by replacing each relation Rj pXj q with Rj pXj` q, then forgetting all
functional dependencies; it is easy to check that maxD |QD | ď AGMpQ` q. This bound is tight when all fd’s
are simple keys, because any product database over the schema of Q` can be converted into a database
over the schema for Q that satisfies all simple keys. Thus, for simple keys, AGMpQ` q is a tight upper
bound on |QD |. Theorem 4.4 in [11] uses query coloring to prove essentially the same result. For a simple
illustration, consider Q :- Rpx, yq, Spy, zq, T pz, uq, Kpu, xq, where AGMpQq “ minp|R| ¨ |T |, |S| ¨ |K|q. If we
define y to be a key in S, in other words FD “ {y Ñ z}, then Q` “ Rpx, y, zq, Spy, zq, T pz, uq, Kpu, xq and
AGM pQ` q “ min {|R| ¨ |T |, |S| ¨ |K|, |R| ¨ |K|}. However, for fd’s other than simple keys this technique fails,
as illustrated by Qpx, y, zq “ Rpxq, Spyq, T px, y, zq where xy is a key in T (in other words xy Ñ z): when
|R| “ |S| “ N , |T | “ M " N 2 then Q` “ Q and AGMpQ` q “ M , yet one can easily verify that |QD | ď N 2 .
The Expansion Procedure. All our algorithms use the following simple subroutine, called an expansion.
Fix a relation RpXq and a database instance D. R may be an input relation, or some intermediate relation
generated during query evaluation. An expansion of RD is some relation pR` qD over attributes X ` such
that ΠX ` pQD q Ď pR` qD and ΠX ppR` qD q Ď RD . If X ` “ X, then the expansion could be RD itself,
or any partial semi-join reduction that removes dangling tuples from RD (which do not join with tuples
in other relations). If X ‰ X ` , then the expansion fills in the extra attributes, by repeatedly applying
functional dependencies X Ñ y: if the fd is guarded in Rj , then it joins R with ΠXy pRj q; otherwise, if the
fd corresponds to a UDF y “ f pXq then it simply computes f for each tuple in R. The expansion of R can
be done in time ÕpN q using standard techniques.

3
3.1

A Lattice-based Approach
Lattice representation of queries with FDs

Fix a query with functional dependencies pQ, FDq, over variables X. It is well known [9, 14, 16] that the set
of closed sets forms a lattice:
Definition 3.1 (Lattice representation). The lattice associated to FD is LFD “ pL, q, where L consists
of all closed sets and the partial order  is Ď. The lattice representation of a query pQ, FDq is the pair
`
Ď L is the set of closures of the attributes of the input relations. We
pLFD , R` q, where R` “ R1` , . . . , Rm
drop the subscript FD when it is clear from the context and write simply L. With the expansion procedure
in place, w.l.o.g. we assume that all the input Rj are closed sets; thus, W
the lattice
W representation of the query
can be denoted simply by pL, Rq, where R “ {R1 , . . . , Rm } Ď L, and R “ Rj PR Rj “ 1̂.

Note that the size of the lattice may be exponential in that of the query, but this does not affect
our complexity results, because they are given in terms of data complexity only. If Q has no functional
dependencies, then L is the Boolean algebra 2X . We will use Fig.1 as a running example, which illustrates
the lattice for query (1): the lattice elements corresponding to input relations are framed.
We briefly review some notions of lattice theory needed later and refer the reader to [22] for an extensive
treatment. Let ^, _, 0̂, 1̂ denote the greatest lower bound (meet), least upper bound (join), minimum and
maximum elements of the lattice. The following hold in LFD : X ^ Y “ X X Y , X _ Y “ pX Y Y q` , 0̂ “ H,
and 1̂ “ X. We write X ­ž Y to mean X and Y are incomparable. An element U is said to cover an
element V of L if U ≻ V and U  W  V implies W “ U or W “ V ; an atom is an element X that
covers 0̂; a co-atom is an element covered by 1̂; X is called a join-irreducible if Y _ Z “ X implies Y “ X
or Z “ X; X is called meet-irreducible if Y ^ Z “ X implies Y “ X or Z “ X. For any X P L, let
def
ΛX “ {Z | Z  X, Z is a join-irreducible}. The mapping X ÞÑWΛX defines a 1-1 mapping from L to the
order ideals of the poset of join-irreducibles, with inverse ΛX ÞÑ ΛX “ X.
7

3
2

1̂ “ xyzu

3
2

S
xyu

1

´1
2

1

yz

´1
2

xu

0

xzu

1

R
1

1
2

´1
2

T
xy

y

1
2

0

0

1
2

x

1

1
2

0

u

0

1
2

zu

z

0

0

h is green
g is red

0̂

Figure 1: Q :- Rpx, yq, Spy, zq, T pz, uq, xz Ñ u, yu Ñ x
Lattice presentations and queries with functional dependencies are in 1-to-1 correspondence, up to the
addition/removal of variables functionally equivalent to some other set ofWvariables. To see this in one
direction, consider any pair pL, Rq where R “ {R1 , . . . , Rm } Ď L and R “ 1̂. Let X be the joinirreducibles of L, define a query pQ, FDq as follows. Let Rj be a relation with attributes ΛRj , and define FD
def 
such that the closed sets are {ΛU | U P L} (in other words FD “ X Ñ ΛW X | X Ď X ). One can check
that the lattice presentation of this query is isomorphic to pL, Rq. In the other direction, consider a query
with functional dependencies, pQ, FDq. Call a variable x redundant if Y Ø x for some set Y that does not
contain x. W.l.o.g. we can remove all redundant variables from Q (and decrease accordingly the arity of
the relations containing x), because the values of a redundant variable can be recovered through expansion
(Sec.2). We claim x ÞÑ x` is a 1-to-1 mapping between the variables of Q and the join-irreducibles of LFD .
We first check that x` is join-irreducible: if x` “ Y _ Z “ pY Y Zq` with x R Y, x R Z then x Ø Y Y Z
contradicting the fact that x is not redundant. For injectivity, if x ‰ y, then x` “ y ` implies
y ` ´ {x},
W x Ø`
again contradicting non-redundancy. Finally, surjectivity follows from the fact that Y “ xPY x for any
closed set Y P L: if Y is join-irreducible then Y “ x` for some x P Y , proving surjectivity.
Thus, in the rest of the paper we shall freely switch between queries and lattices, using the following
correspondence:
variable x P X
input Rj pXj q
set of variables X Ď X
its closure X `
FD“ H

join-irreducible X P L
input Rj P L with variables ΛRj
set of join-irreducibles X
W
def
X ` “ ΛZ , where Z “ X
Boolean Algebra

The following simple observation illustrates the power of the lattice formalism.
Proposition 3.2. If all functional dependencies are simple then L is a distributive lattice.
Proof. Construct a directed graph D “ pV, Eq where V is the set of all variables and there is an edge
pa, bq P D if a Ñ b is a functional dependency. Collapse each strongly connected component of this graph
into a single vertex. We are left with a directed acyclic graph (DAG), which defines a poset P where y ≺P x
iff there is a directed path from x to y in the DAG. Then, L is precisely the order ideal lattice of the direct
sum of these posets. The claim follows because any order ideal lattice is distributive.
8

It is easy to construct examples when non-simple FDs still produce a distributive lattice; for example,
the lattice for Q :- Rpxq, Spyq, xy Ñ z is isomorphic to the Boolean algebra lattice 2x,y which is distributive.
Hence, the class of distributive lattices strictly covers the simple FD case.
Consider the non-distributive lattice M3 (Fig. 3), then the procedure we discussed above associates it
with the following query: Rpxq, Spyq, T pzq, xy Ñ z, xz Ñ y, yz Ñ x.

3.2

Database Instances for a Lattice


Let X denote the set of join-irreducibles of a lattice L, and let FD “ X Ñ ΛW X | X Ď X be all fd’s
implicitly defined by L. A database instance D for L is a relation with attributes X that satisfies FD. We
denote hD : L Ñ R` its entropy function, as defined in Sec. 2. If pL, Rq is the lattice presentation of a query
def
pQ, FDq, then any database instance for L defines a standard database instance for Q by RjD “ ΠRj pDq.
For example, given the query
Q :- Rpxq, Spyq, T pzq, xy Ñ z, xz Ñ y, yz Ñ x,
An example of an instance for its lattice (which is M3 in Fig. 3) is:

D “ pi, j, kq P rN s3 | i ` j ` k mod N “ 0 .

It defines the following standard instance: RD “ S D “ T D “ rN s. Notice that all fd’s are unguarded and
hence lost in the standard instance. From Sec. 5.1 and up we will assume that during the query evaluation
we have access to the UDF’s that defined the unguarded fd’s.
Definition 3.3 (Materializability). A function h : L Ñ R` is called L-entropic if h “ hD for some instance
D for L and it is called materializable w.r.t. an input query pL, Rq if there exists an instance D such that
log |RjD | ď hpRj q forall j “ 1, m and log |QD | ě hp1̂q. Obviously, any entropic function is materializable
w.r.t. some input instance.

3.3

The Lattice Linear Program

This section shows that a very simple linear program defined on the FD lattice L is equivalent to GLVV
bound. Given a query pL, Rq and log cardinalities pnj qm
j“1 , we define the following Lattice Linear Program,
or LLP, over the non-negative variables phpXqqXPL :
max hp1̂q
hpX ^ Y q ` hpX _ Y q ´ hpXq ´ hpY q ď
hpRj q ď

0, @X, Y P L, X ­ž Y.
nj , @j P rms.

(5)

A feasible solution h to LLP is called a (non-negative) L-sub-modular function. If h is also L-monotone,
i.e. X  Y implies hpXq ď hpY q, then h is called an L-polymatroid. When L is clear from the context we
drop the L-prefix from L-monotone, L-submodular, and L-polymatroid, respectively. We did not require h
to be monotone because, at optimality, h˚ can always be taken to be a polymatroid thanks to Lovász’s monodef
def
tonization: if h is non-negative L-submodular, then the function h̄p0̂q “ 0 and h̄pXq “ minY :XY hpY q,
X ‰ 0̂, is an L-polymatroid (see e.g. [21], pp. 774, and Appendix B) and satisfies: h̄p1̂q “ hp1̂q and @X,
h̄pXq ď hpXq.
Proposition 3.4. Let h˚ be an optimal solution to the LLP of a query pL, Rq where Nj “ |Rj |, j P rms.
˚
Then, 2h p1̂q “ GLVVpQ, FD, pNj qj q.
Proof. From the discussion above, we can assume h˚ is an L-polymatroid. Define a function h : 2X Ñ R
by hpXq “ h˚ pX ` q; then, clearly h is non-negative and monotone (on the original variable set, not on the

9

lattice L), and satisfies the cardinality and fd constraints. We verify that it is also sub-modular: for any
(not necessarily closed) set X of variables, noting that pX X Y q`  X ` ^ Y ` , we have
hpX Y Y q ` hpX X Y q

“ h˚ ppX Y Y q` q ` h˚ ppX X Y q` q

pmonotonicityq

ď h˚ ppX Y Y q` q ` h˚ pX ` ^ Y ` q
“ h˚ pX ` _ Y ` q ` h˚ pX ` ^ Y ` q

pL-submodularityq

ď h˚ pX ` q ` h˚ pY ` q
“ hpXq ` hpY q.

Conversely, given any polymatroid h that satisfies the cardinality and fd-constraints, the restriction of h on
L is a feasible solution to LLP.
˚

The main goal in this paper is to design algorithms that compute a query Q in time Õp2h p1̂q q. When the
bound in the proposition is tight (which is currently an open problem) then such an algorithm is optimal,
hence our second goal is to study cases when the bound is tight, and this happens if and only if the LLP has
some optimal solution h˚ that is materializable. A secondary goal in this paper is to find sufficient conditions
for h to be materializable.
˚
When FD “ H, L is a Boolean algebra. In this case it is easy to see that AGMpQq “ 2h p1̂q . To see this,
in one direction start from an optimal weighted fractional vertex packing pvi˚ qki“1 of the query hypergraph
(Sec. 2), then the following is a feasible solution to LLP with the same objective value:
def

hpXq “

X

vi˚

(6)

i:xi PX
def

Conversely, given a polymatroid h˚ that is optimal to LLP, define vi “ h˚ p{x1 , . . . , xi }q´h˚ p{x1 , . . . , xi´1 }q,
then it can be verified (using sub-modularity of h˚ ) that pvi qki“1 is a feasible weighted fractional vertex packing
with the same objective value.

3.4

Embeddings

Embeddings allow us to construct an instance for one lattice L from an instance for a different lattice L1 .
W
Definition 3.5. An embedding between two lattices L and L1 is a function f : L Ñ L1 such that f p Xq “
W
f pXq forall X Ď L,3 and f p1̂L q “ 1̂L1 . An embedding between two queries f : pL, Rq Ñ pL1 , R1 q is an
embedding from L to L1 that is a bijection from R to R1 .
If f is an embedding from L to L1 and h1 is a non-negative, sub-modular function on L1 , then one can
def
check that h “ h1 ˝ f is also sub-modular. If f is an embedding between queries, then their relation symbols
1
respectively. Fix two queries pQ, FDq, pQ1 , FD1 q
are in 1-1 correspondence: R1 , . . . , Rm and R11 , . . . , Rm
1
1
X
with variables
X, X respectively. Call a function L : 2 Ñ 2X a variable renaming if LpXq “ LpX ` q,
S
LpXq “ p xPX Lpxqq` (L is uniquely defined by its values on single variables), and LpXq “ X1 (all variables
def

in Q1 are used). One can check that every embedding f defines the variable renaming LpXq “ f pX ` q forall
X Ď X, and vice versa.
def
Fix an embedding f : L Ñ L1 , and an instance D1 for L1 . Define the database instance D “ f ´1 pD1 q
def
as D “ {t ˝ L | t P D1 }. In other words, every tuple t1 P D1 has attributes X1 , hence it can be viewed as
a function t1 : X1 Ñ Dom: for each such t1 we include in D a tuple t1 ˝ L : X Ñ Dom, obtained from t1
by renaming its attributes. One can check that |D| “ |D1 | (because all variables in X1 are used), and the
def
same holds for all projections |ΠX pDq| “ |ΠLpXq pD1 q| forall X Ď X. For example, if Lpx1 q “ {y1 , y2 },
def

def

Lpx2 q “ {y2 , y3 } then Dpx1 , x2 q “ {ppabq, pbcqq | pa, b, cq P D1 py1 , y2 , y3 q}. This proves:
3 Equivalently:

f is the left adjoint of a Galois connection.

10

Proposition 3.6. If f : L Ñ L1 is a lattice embedding, then for any instance D1 for L1 , hD “ hD1 ˝ f , where
def
D “ f ´1 pD1 q. If f : pL, Rq Ñ pL1 , R1 q is a query embedding , and h1 : L1 Ñ R` is materializable, then
def
h “ h1 ˝ f is also materializable.
Definition 3.7. A quasi-product database instance for L is an instance of the form f ´1 pD1 q where f embeds
L into a Boolean algebra A, and D1 is a product database instance for A.
Example 3.8. Continuing our running example, consider the following two queries:
Q
Q1

“ Rpx, yq, Spy, zq, T pz, uq, xz Ñ u, yu Ñ x
“ R1 pa, bq, S 1 pb, cq, T 1 pc, aq

Q is the query in Fig. 1, while Q1 is the triangle query (without fd’s). Consider the following renaming
Lpxq “ Lpuq “ a, Lpyq “ b, Lpzq “ c, which defines an embedding4 from the lattice in Fig. 1 to the Boolean
algebra 2{a,b,c} . From the product instance
n
√ o
def
D1 “ pa, b, cq “ pi, j, kq | i, j, k P r N s

we construct, through renaming, the quasi-product instance
n
√ o
D “ px, y, z, uq “ pi, j, k, iq | i, j, k P r N s .
Notice that the FD’s xz Ñ u, yu Ñ x hold in D (as they should).

3.5

Inequalities

In informationP
theory, an information inequality is defined by a vector of real numbers pwX qXĎX such that
the inequality XĎX wX HpXq ě 0 holds for any entropic function H. We introduce here a related notion,
which we use to describe upper bounds on the query size.
Fix a query pL, Rq. An output-inequality is given by a vector of non-negative real numbers pwj qjPrms such
that the inequality
m
X

wj hpRj q ě hp1̂q

(7)

j“1

holds for all polymatroids
P h on the lattice L. For example, in a Boolean algebra output inequalities correspond
to Shearer’s lemma: j wj hpRj q ě hpXq iff pwj qm
j“1 is a fractional edge cover of the hypergraph with nodes
{x | x P X} and hyperedges {Rj | j P rms}. Any outputPinequality gives us immediately an upper bound on
the output size of a query, because (7) implies hp1̂q ď j wj nj for any feasible solution h of the LLP with
log-cardinalities pnj qm
j“1 .
An ouput size upperbound is best if it is minimized, which is precisely the objective of the dual-LLP,
which is defined over non-negative variables pwj qm
j“1 and psX,Y qX­žY , corresponding to the input Rj and
incomparable pairs of lattice elements (thus sX,Y is the same variable as sY,X ):
X
wj nj
min
j

wj `

X

X­žY :X_Y “Rj

sX,Y `

X

X­žY :X^Y “Rj

X

sX,Y

X­žY :X_Y
X“1̂

sX,Y ´

sX,Rj

ě 1,

(8)

ě 0, @j P rms

X­žRj

4 We need to check LpXq “ LpX ` q for all X: e.g. Lpxzq “ Lpxz ` q holds because Lpxzq “ ac, Lpxz ` q “ Lpxzuq “ ac, and
similarly Lpyuq “ Lpyu` q.

11

A simple way to prove an output inequality is to write it as a non-negative linear combination of submodularity inequalities. (See example below.) The following Lemma shows that every output inequality can
be proven this way, as follows from the theory of generalized inequalities [6, Ch.2].
Lemma 3.9. Let M denote the matrix of sub-modular inequalities (first inequality of the LLP (5)). Given
def
def
def
a non-negative vector pwj qjPrms , define the vector pcX qXPL by setting c1̂ “ 1, cRj “ ´wj and cX “ 0
otherwise. Then, the following statements are equivalent
(i) (7) holds for all polymatroids h
(ii) (7) holds for all non-negative sub-modular functions h
(iii) there exists s ě 0 such that cT ď sT M . Equivalently, w is part of a feasible solution ps, wq of the
dual-LLP (8).
P
˚
Furthermore, if ps˚ , w˚ q and h˚ are dual- and primal-optimal solutions, then h˚ p1̂q “ m
j“1 wj nj .

Proof. Using the Lovász monotonization map h Ñ h̄ described in Sec 3.3, it is straightforward to show that piq
def
and piiq are equivalent. To see the equivalence between piiq and piiiq, note that K “ {h | M h ď 0, h ě 0}

def
is the set of all non-negative, sub-modular functions, and the polar cone K ˚ “ c | cT h ď 0, @h P K is
˚
the set of all inequalities that hold for all non-negative sub-modular functions. Now,
 c TP K T iff the LP
T
maxh {c h | M h ď 0, h ě 0} has objective value 0, which holds iff the dual LP mins 0 | c ď s M, s ě 0
is feasible. The last statement is strong duality.

Example 3.10. The lattice presentation of the triangle query Q “ Rpx, yq, Spy, zq, T pz, xq (without FD’s)
is the Boolean algebra 2{x,y,z} . The following output inequality:
hpxyq ` hpyzq ` hpzxq ě

2hp1̂q

(9)

follows by adding two sub-modularity inequalities hpxyq ` hpyzq ě hp1̂q ` hpyq and hpyq ` hpzxq ě hp1̂q.
It corresponds to the dual solution sxy,yz “ sy,zx “ 1 with the rest 0. Some other output inequalities
are hpxyq ` hpxzq ě hp1̂q, hpxyq ` hpyzq ě hp1̂q, and hpxzq ` hpyzq ě hp1̂q. Together, these four output
inequalities prove Eq.(4).

4

Normal lattices

We show here that an L-polymatroid h can be materialized as a quasi-product database instance iff it
satisfies all output inequalities given by fractional edge covers of a certain hypergraph; in that case we call h
normal. The normal polymatroids are the largest class of polymatroids that preserve the elegant properties
of the AGM bound: upper bound given in terms of a fractional edge cover, and lower bound given a (quasi-)
product database. We then extend normality to a lattice, which we call normal if its optimal polymatroid
h˚ is normal.
Recall the Möbius inversion formula in a lattice L:
X
X
hpXq “
gpY q iff gpXq “
µpX, Y qhpY q
(10)
Y :XY

Y :XY

where µpX, Y q is the Möbius function on L [22]. In information theory, when h is an entropy and L a Boolean
algebra, the quantity ´gpXq is the (multivariate) conditional mutual information Ip1̂ ´ X | Xq, which we
abbreviate CMI. For example, in the Boolean Algebra 2{x,y,z} :
gpxyzq “ hpxyzq
gpxyq “ hpxyq ´ hpxyzq
gpxq “ hpxq ´ hpxyq ´ hpxzq ` hpxyzq
gp0̂q

“ hp0̂q ´ hpxq ´ hpyq ´ hpzq ` hpxyq ` hpxzq ` hpyzq ´ hpxyzq
12

We give below a simple sufficient condition on g which implies that h, defined by Eq.(10) is a polymatroid.
We need:
def

Lemma 4.1. For S Ď L, let cpZ, Sq “ | {U | U P S, U  Z} |. Then, for all X, Y, Z P L, cpZ, {X, Y }q ď
cpZ, {X ^ Y, X _ Y }q; moreover, if L is a distributive lattice and Z is a meet-irreducible, then equality holds.
Proof. If cpZ, {X, Y }q “ 1, then w.l.o.g. we assume X  Z, hence X^Y  Z, and cpZ, {X ^ Y, X _ Y }q ě 1.
If cpZ, {X, Y }q “ 2, then both X  Z, Y  Z hold, hence both X ^ Y  Z, X _ Y  Z hold, hence
cpZ, {X ^ Y, X _ Y }q “ 2. Next, suppose L is distributive and Z is a meet-irreducible. If cpZ, {X ^ Y, X _ Y }q “
2 then X _ Y  Z hence both X  Z, Y  Z hold. If cpZ, {X ^ Y, X _ Y }q “ 1, then X ^ Y  Z. By
distributivity Z  pX ^ Y q _ Z “ pX _ Zq ^ pY _ Zq. On the other hand both Z  X _ Z and Z  Y _ Z
hence Z “ pX _ Zq ^ pY _ Zq. Since Z is a meet-irreducible, it must be equal to one of the two terms.
Assume w.l.o.g. Z “ X _ Z then X  Z proving cpZ, {X, Y }q ě 1.
Lemma 4.1 immediately implies:
P
Lemma 4.2. Let g be any function s.t. gpZq ď 0 for Z ≺ 1̂, and gp1̂q “ ´ Z≺1̂ gpZq. Then the function h
defined by Eq.(10) is a polymatroid. Furthermore, if L is distributive, then h is a modular polymatroid, i.e.
hpXq ` hpY q “ hpX _ Y q ` hpX ^ Y q for all X, Y P L.
Proof. Non-negativity and monotonicity are easy to verify, submodularity follows from:
X
X
hpXq ` hpY q “
gpZq `
gpZq
Z:XZ

“

X
Z

ě

X
Z

“

Z:Y Z

cpZ, {X, Y }q ¨ gpZq
cpZ, {X _ Y, X ^ Y }q ¨ gpZq

hpX _ Y q ` hpX ^ Y q,

where the inequality holds due to Lemma 4.1 and the fact that gpZq ď 0 for Z ‰ 1̂. When L is distributive,
the inequality becomes an equality.
Any function h satisfying the property stated in Lemma 4.2 is called a normal submodular function. If,
furthermore, gpZq “ 0 for all Z ≺ 1̂ other than the co-atoms, then we say that h is strictly normal.
For a simple example, consider the function h in our running example Fig.1: it is strictly normal because
it is defined by the CMI g shown in the figure. A negative example is given by function h on the left of Fig. 3,
algebra, then the optimal
which is not normal, because its CMI satisfies gp0̂q ą 0. If the lattice L is a Boolean
P
polymatroid h˚ given given by Eq.(6) is strictly normal: its CMI is gpXq “ i vi˚ , gpX ´ {xi }q “ ´vi˚ , and
g “ 0 everywhere else.
Normal polymatroids are precisely non-negative linear combinations of “step functions”. For every Z P L,
the step function hZ at Z is defined by hZ pXq “ 1 if X ­ Z, and 0 otherwise. Every step function is normal,
because its Möbius inverse is gZ p1̂q “ 1, gZ pZq “ ´1, and gZ pXq “ 0 otherwise. Any non-negative linear
combination of step functions is normal. Conversely, if h is P
a normal polymatroid, then
P denoting aZ “ ´gpZq
for all Z ‰ 1̂ we have aZ ě 0 (since h is normal) and g “ Z aZ gZ , implying h “ Z aZ hZ .

4.1

Connection to Quasi-Product Instance

We have seen that the worst-case instance of the AGM-bound is a product database instance (Theorem 2.1),
and its entropy function given in Eq.(6) is strictly normal. We generalize this observation by proving that
normal polymatroids are precisely entropy functions of quasi-product instances (Definition 3.7). For one
direction we need:

13

Lemma 4.3. Let f : L Ñ L1 be an embedding between two lattices, and let h1 be a normal polymatroid on
def
L1 . Then h “ h1 ˝ f is a normal polymatroid on L.
Proof. Recall that an embedding is the left adjoint of a Galois connection. Let r : L1 Ñ L be its right adjoint5 ,
def P
1
in other words f pXq  Y iff X  rpY q. Let g 1 be the CMI for h1 . The function gpXq “
Y :rpY q“X g pY q
is the CMI of h, because, forall X P L:
X
X
X
X
X
g 1 pZ 1 q “
g 1 pZ 1 q “ h1 pf pXqq “ hpXq
g 1 pZ 1 q “
gpZq “
Z:XZ

Z:XZ Z 1 :rpZ 1 q“Z

Z 1 :XrpZ 1 q

Z 1 :f pXqZ 1

1
In any Galois connection, rp1̂q “ 1̂ (since f p1̂q
P 1̂ iff 1̂  1 rp1̂q). By normality of h we have Y ‰ 1̂ implies
1
g pY q ď 0. Therefore, X ‰ 1̂ implies gpXq “ Y :rpY q“X g pY q ď 0, proving that h is normal.

In the opposite direction, we need:

Definition 4.4. Let A “ 2X be a Boolean algebra. The canonical instance is the product database D “ r2sX ;
note that |ΠX pDq| “ 2|X| , and thus hD pXq “ |X|, forall X Ď X.
Let L be a lattice and h an integer-valued, normal polymatroid, and g its CMI. For all X P L, X ‰ 1̂, let
CpXq be a set of ´gpXq arbitrary elements, such that the sets pCpXqqX‰1̂ are disjoint. Define Cp1̂q “ H,
def S
and C “ X CpXq. The canonical Boolean Algebra is A “ p2C , Ěq, and the canonical embedding of L is
def S
f : L Ñ A, f pXq “ Z:XZ CpZq.

A is an “upside-down” Boolean algebra, where Y  Y 1 iff Y Ě Y 1 , and _ is set intersection; one can
check that f commutes with _. We can now prove our result. (As in the AGM bound, there is a bit of loss
when h are not integral, but this does affect asymptotics)
Lemma 4.5. Let h be an integral, non-negative, submodular function h on a lattice L. Then h is normal
iff it is the entropy function of a quasi-product instance.

Proof. In one direction, let D is a quasi-product instance and hD be its entropy function. By definition,
D “ f ´1 pD1 q, where f : L Ñ A is an embedding into a Boolean algebra and D1 is a product instance for
A. Since hD1 is normal (even strictly normal), hD is also normal by Lemma 4.3. In the opposite direction,
assume h is normal. Let f : L Ñ A be the canonical embedding, and D1 be the canonical instance for A.
def
Then D “ f ´1 pD1 q is the quasi-product instance, and one can check that h “ hD “ hD1 ˝ f .
Example 4.6. We illustrate the construction above on the lattice L in Fig. 1, showing that it leads to the
quasi-product instance in Example 3.8. The canonical embedding is into the Boolean algebra A “ 2{a,b,c}
because there are three co-atoms in L: if we call the atoms of this Boolean algebra a, b, c, then the embedding
f : L Ñ 2{a,b,c} is precisely the renaming in Example 3.8. The polymatroid h is equal to h1 ˝ f , where h1
is defined on A by h1 paq “ h1 pbq “ h1 pcq “ 1{2, h1 pabq “ h1 pacq “ h1 pbcq “ 1, h1 pabcq “ 3{2, whose
materialization is that in Example 3.8 for N “ 2.

4.2

Connection to Fractional Edge Covering

Definition 4.7. Let pL, Rq be a query given in lattice presentation. The co-atomic hypergraph Hco “
pVco , Eco q is defined as follows. The nodes Vco are the co-atoms of L, and Eco “ {e1 , . . . , em } with ej “
{Z | Z P Vco , Rj ­ Z, Rj P R}. In other words, each relation Rj defines a hyperedge ej consisting of those
nodes that do not contain the variables of Rj . A simple illustration of a co-atomic hypergraph is in Fig.2.
Lemma 4.8. Inequality (7) holds for all normal polymatroids h iff it holds for all strictly normal polymatroids
iff pwj qm
j“1 is a fractional edge cover of Hco .
5 The

standard notation is g, but we use g for the CMI.

14

Proof. Since each (stricly) normal polymatroid is a non-negative linear combination of (co-atomic) step
functions, it suffices to assume that h is a step function.
First consider a co-atomic step functions hZ , i.e.
P
Z is a co-atom: the left hand size of Eq. (7) is j:ZPej wj , and the right hand side is 1, meaning that the
inequality holds iff pwj qm
j“1 covers node Z P Vco . It remains to show that if (7) holds for all co-atomic step
functions then it holds for all step functions hX : let Z be any a co-atom s.t. Z  X, then hZ ď hX and
hZ p1̂q “ hX p1̂q “ 1 implying that (7) holds for hX .
The co-atomic hypergraph is the natural concept to capture Shearer’s lemma in a general lattice. In
fact, every vector pwj qm
j“1 for which the output inequality (7) holds is a fractional edge cover of the coatomic hypergraph. One may wonder whether the output inequalities could also be described by the atomic
hypergraph, defined in a similar way. In a Boolean algebra 2X the atomic and co-atomic hypergraphs are
isomorphic via x ÞÑ X ´ {x}, since x P Rj iff Rj Ę X ´ {x}, but in a general lattice the atomic hypegraph
does not seem to lead to any interesting properties.

4.3

Normal Lattices

A normal lattice is a lattice where, at optimality, the polymatroid is normal. This is captured by the
following, which is the main result of this section.
Theorem 4.9. Let pL, Rq be a query in lattice presentation. The following are equivalent:
1. For every non-negative, submodular function h there exists a normal polymatroid h1 s.t. h1 p1̂q “ hp1̂q
and h1 pRj q ď hpRj q for all Rj P R.
2. The previous property holds and h1 is strictly normal.
3. Inequality (7) holds for all non-negative, submodular functions h iff w1 , . . . , wm is a fractional edge
cover of the co-atomic hypergraph.
4. Every non-negative submodular function h on L has a materialization that is a quasi-product database
instance.
If L satisfies any of these conditions, then we call it a normal lattice w.r.t. R. If L is normal w.r.t. any
inputs R, then we call it shortly a normal lattice.
Proof. We first prove that items 1, 2, and 3 are equivalent, then show that item 2 is equivalent to 4.
Item 2ñ item 1 is obvious.
For Item 1ñ item 3, let h be any submodular function on L. Let h1 be aP
normal function
P as defined in
item 1. Since h1 is normal, it satisfies the inequality (7); it suffices to note that j wj hpRj q ě j wj h1 pRj q ě
h1 p1̂q ě hp1̂q.
For Item 3ñ item 2, let h be any submodular function on L, and let Z1 , . . . , Zk be all co-atoms in L. To
define a strictly normal function h1 , we need to find k numbers ai ě 0, i P rks and define:
X
ai
h1 p1̂q “
i

1

h pXq “

h1 p1̂q ´

X

{ai | i P rks : X  Zi } “

X

{ai | i P rks : X ­ Zi }

We need to find these numbers such that h1 p1̂q ě hp1̂q and h1 pRj q ď hpRj q for all Rj P R. To do that,
consider the following linear program:
maximize
a1 ` . . . ` ak
P
@j P rms :
{ai | i P rks, Rj ­ Zi } ď hpRj q
15

We claim that its optimal value is ě hp1̂q: this implies that h1 defined above is a strictly normal function
satisfying the requirement in the theorem. To prove the claim, consider the dual LP. Its variables are bj , for
j P rms:
P
minimize
j bj hpRj q
P
@i P rks :
{bj | j P rms, Rj ­ Zi } ě 1

Thus, the feasible solutions of the dual LP are precisely the fractional edge covers of the dual hypergraph.
Hence, by assumption in Item 3, the output inequality (7) holds:
X
bj hpRj q ě hp1̂q
j

which completes the proof.
Finally, we show that item 2 holds iff 4 holds. For the only if direction, consider a non-negative, submodular function h; by 1 there exists a normal polymatroid h1 s.t. h1 p1̂q “ hp1̂q and h1 pRj q ď hpRj q forall j. By
Lemma 4.5, h1 is the entropy of some quasi-product instance D. Then D is a materialization of h because
log |RjD | “ h1 pRj q ď hpRj q and log |D| “ h1 p1̂q “ hp1̂q. Conversely, assume item 4 holds: h has some materialization D that is a quasi-product. Then by Lemma 4.5, hD is normal, and hD pRj q “ log |RjD | ď hpRj q,
def

hD p1̂q “ log |D| “ hp1̂q, proving that item 1 holds, with h1 “ hD .
Normal lattices appear to be a new concept. It is decidable whether a lattice L is normal w.r.t. R, using
the following naive procedure. Enumerate all vertices pwj qj of the fractional edge packing polytope of the
co-atomic hypergraph, and check that the output inequality (7) holds, by using the criterion in Lemma 3.9.
We prove in Sec. 5.2 that every distributive lattice is normal; furthermore, Proposition 3.2 says that any
set of unary FDs generate a distributive lattice, which is therefore normal. The lattice on the left of Fig.3 is
a Boolean algebra, hence it is normal: note that h in the figure is not normal6 , but we can simply increase
hp1̂q to 3 and now it is normal.
The lattice L in Fig.1 is normal w.r.t. inputs xy, yz, zu, which follows by exhaustively proving all
inequalities defined by the fractional edge covers of the co-atomic hypergraph, shown in Fig. 2. For example,
the edge cover p1{2, 1{2, 1{2q corresponds to the inequality hpxyq ` hpyzq ` hpzuq ě 2hp1̂q, which can be
proven by hpxyq ` hpyzq ě hp1̂q ` hpyq and hpyq ` hpzuq ě hp1̂q ` hp0q. In fact, L is normal w.r.t. any
inputs. Notice that L is not distributive.
The lattice M3 on the right of Fig.3 is not normal. Its co-atomic hypergraph has edges ex “ {y, z},
ey “ {x, z}, ez “ {x, y} and the inequality corresponding to the fractional edge cover p1{2, 1{2, 1{2q,
hpxq ` hpyq ` hpzq ě 2hp1̂q, fails for the submodular function shown in the figure. In particular, this
polymatroid h is not materializable as a quasi-product database instance, but can be materialized as
{pi, j, kq | i, j, k P {0, 1} , i ` j ` k “ 0 mod 2}.
We give a necessary condition for normality (and we conjecture it is also sufficient):

Proposition 4.10. Let L be a lattice that contains a sublattice U, X, Y, Z, 1̂ isomorphic to M3 , and let
R “ {X, Y, Z}. Then L is not normal.
Proof. The co-atomic hypergraph has three hyper-edges, X, Y, Z. Then p1{2, 1{2, 1{2q is a fractional edge
cover of the co-atomic hypergraph, because every co-atom is above at most one of X, Y, Z, because X _ Y “
X _ Z “ Y _ Z “ 1̂, hence it belongs to at least two hyper-edges of the hypergraph. This defines the
inequality:
hpXq ` hpY q ` hpZq ě 2hp1̂q.
6 The function XOR on three variables, Rpx, y, zq “ {pa, b, cq | a, b, c P {0, 1} , a xor b xor c “ 0}, is the canonical example of
a distribution whose entropy has a negative mutual information.

16

R
y

T

T
x

u

z

S
Atomic Hypergraph HA

xyu

R
yz

xzu

S
Co-atomic Hypergraph HC

Figure 2: Atomic and Co-atomic hypergraphs for Fig.1
We construct a polymatroid h that violates this inequality:


0 when W  U
hpW q “ 1 when W  X or W  Y or W  z


2 when W is not below X or Y or Z

Then hpXq “ hpY q “ hpZq “ 1, hp1̂q “ 2 and therefore h violates the inequality above. We prove that h is
a polymatroid. Monotonicity is easy to check. We prove that it satsifies the submodularity laws:
hpAq ` hpBq ě hpA _ Bq ` hpA ^ Bq

Case 1: hpA _ Bq “ 0. Then all elements are below U , and all h are 0.
Case 2: hpA _ Bq “ 1. If hpAq “ 1 then the inequality follows from hpBq ě hpA ^ Bq, and similarly for
hpBq “ 1. If both hpAq “ hpBq “ 0 then both A, B are below U , hence A _ B is below U , contradicting
hpA _ Bq “ 1
Case 3: hpA _ Bq “ 2. We can rule out the cases when hpAq, hpBq are 0,0 or 0,1 because that implies
both A, B are below X (or Y or Z), implying hpA _ Bq “ 1. Also, the case when hpAq “ 2 or hpBq “ 2
follows immediately from monotonicity. Thus, assume hpAq “ hpBq “ hpA ^ Bq “ 1. Here we use the
structure of M3 . If A and B are below two distinct elements from X, Y, Z, e.g. A ď X and B ď Y , then
A ^ B ď U contradicting hpA ^ Bq “ 1. Hence both A, B are below X. But that implies A _ B is also below
X, contradicting hpA _ Bq “ 2.
1

Gottlob et al. [11] define a coloring of a query Q with variables X to be a function L : X Ñ 2X such that
def S
LpXq ‰ H, and for any FD X Ñ Y , LpY q Ď LpXq, where, for each set X, LpXq “ xPX LpXq. Then the
color number of L is defined as CpLq “ |LpXq|{ maxj |LpRj q| and the color number of Q is maxL CpLq. They
CpQq
prove two results: if the functional dependencies are restricted to simple keys then |QD | ď maxj |RjD |
,
and moreover this bound is essentially tight, even for general functional dependencies. S
Colorings correspond one-to-one to integral, normal polymatroids, via hpxq “ | xPX Lpxq|. To see
1
def S
this, in one direction let L : X Ñ 2X be a coloring and define hpXq “ | xPX Lpxq|. The function
1
def S
f pXq “ xPX Lpxq is an embedding f : L Ñ 2X into a Boolean algebra (we assume w.l.o.g. that f pXq “ X1 ,
def

otherwise we redefine X1 ), and we have h “ h1 ˝f where h1 pY q “ |Y |: since h1 is a strictly normal polymatroid
Lemma 4.3 says that h is also normal. In the other direction, if h is an integral, normal polymatroid, then
def S
its canonical embedding (Definition 4.4) defines a coloring L s.t. hpXq “ | xPX Lpxq|. Thus, colorings are
essentially normal polymatroids. This implies the two results in [11] as follows. If FD consists only of simple
keys, then the lattice L is distributive (Prop. 3.2), hence it is normal (Corollary 5.23), hence at optimality
h˚ can be assumed to be a normal polymatroid (Theorem 4.9 item 1), equivalently a coloring. The second
result, tightness, follows from our Lemma 4.5, since any normal polymatroid (coloring) is the entropy of a
quasi-product database instance.
To summarize, we have introduced a framework for studying the query upper bound under FDs that
uses the lattice of its closed sets of attributes, which extends and generalizes the framework introduced by
Gottlob et al. [11].
17

2

2

xy

0

2

1̂
xz

0

2

yz

x

´1

1

0

y
0̂

´1

1

z

1̂

1

y

´1

0

0̂

`1

0
1

1

2

x

´1

1

z

´1

´1

`1

Figure 3: A non-normal function h (left) and the non-normal lattice M3 (right)

5

Proof Sequence to Algorithm

We aim to design an algorithm that, given an input query Q and database instance D, computes QD in time
˚
˚
Õp2h p1̂q q, where
if ps˚ , w˚ q is dual-optimal
Pmh is˚ the optimal solution to the LLP (5). From Lemma 3.9,
˚
˚
then h p1̂q “ j“1 wj nj and the output inequality (7) holds with wj “ wj , for all polymatroids. Our
main algorithmic theme is to turn this process “inside-out”: find a “proof” of inequality (7) consisting of
a sequence of steps transforming the left-hand-side into the right-hand-side, then interpret these steps as
algorithmic steps whose runtime does not exceed what the symbolic step allows.
We show that three different proof techniques for (7) lead to three different bounds and algorithms. The
first two are known techniques for proving Shearer’s lemma (i.e. the Boolean algebra case) that we adapt
to lattices. The bounds are tight and corresponding algorithms are worst-case optimal for some classes
of lattices (such as distributive lattices, which include the Boolean algebra and the lattice of queries with
simpld fd’s, subsuming results
P from [11, 18, 23]). However, for a generic lattice the bounds these techniques
can prove are not hp1̂q ď j wj˚ hpRj q, and thus the corresponding algorithms’ runtimes in general can be
˚

worse than Õp2h p1̂q q. An advantage of these two algorithms is that there is only one log-factor hidden in
the Õ.
The last proof technique is our own, designed specifically to achieve the optimal LLP bound in an
˚
arbitrary lattice; this leads to an algorithm called CSMA runing in the stated time of Õp2h p1̂q q, where Õ
hides a polylogarithmic factor. This algorithms needs to regularize the data, somewhat similar in spirit to
the uniformization step in [17].

5.1

Chain Bound and Chain Algorithm (CA)

Our first proof sequence adapts Jaikumar Radhakrishnan’s proof of Shearer’s lemma [20] to lattices, which
is based on an arbitrary but fixed order of the random variables. We observe that a variable ordering
corresponds to a maximal chain in the Boolean algebra. This idea allows us to generalize Radhakrishnan’s
proof to general lattices. Fix a chain C : 0̂ “ C0 ≺ C1 ≺ ¨ ¨ ¨ ≺ Ck “ 1̂ in L. For X P L, we say that X
covers i if X ^ Ci ‰ X ^ Ci´1 . Intuitively, X covers i if it contains some variable in Ci that does not appear
in Ci´1 . Fix a query represented by pL, Rq, where R “ pR1 , . . . , Rm q.
Definition 5.1. The chain hypergraph associated with a chain C is HC “ prks, {ej | j P rms}q, where the
hyperedge ej contains all nodes i such that Rj covers i.
In a Boolean algebra all maximal chains have the same hypergraph, which is the same as the query
hypergraph, and the co-atomic hypergraph. But in a general lattice all these hypergraphs may be different,
and some output inequalities (7) can be derived only from non-maximal chains. For that reason, we relax
the maximality requirement on the chain, as follows. We say that the chain C is good for Rj if:
for all i P rks : i P ej ñ Ci´1 _ pRj ^ Ci q “ Ci .
The key property of “goodness” is that submodularity applies in the following way:
18

(11)

Proposition 5.2. If C is a maximal chain, then it is good for any Rj . Furthermore, if C is good for Rj ,
then
hpRj ^ Ci q ´ hpRj ^ Ci´1 q ě hpCi q ´ hpCi´1 q,

@i P ej

(12)

for every L-submodular function h.
def

Proof. Notice that Z “ Ci´1 _ pRj ^ Ci q is always in the interval rCi´1 , Ci s. In any chain, i R ej iff
Rj ^ Ci “ Rj ^ Ci´1 iff Z “ Ci´1 . Therefore, any maximal chain is good for Rj . To show (12), replace Ci
with pRj ^ Ci q _ Ci´1 and the inequality becomes the (lattice) submodularity constraint for the elements
pRj ^ Ci q and Ci´1 .
We say a chain C is good for R if it is good for all Rj P R. Radhakrishnan’s proof is adapted to a lattice
as follows.
Theorem 5.3 (The Chain Bound). Let C be any chain that is good for R. If pwj qm
j“1 is any fractional edge
cover of the chain hypergraph HC , then inequality (7) holds for any polymatroid h
Proof. By writing hpRj q as a telescoping sum, we obtain


m
m
X
X
X
wj hpRj q “
wj ¨  phpRj ^ Ci q ´ hpRj ^ Ci´1 qq
j“1

pfrom Eq.(12)q

j“1

ě

m
X
j“1

“

k
X
i“1

ě

k
X

iPej



wj ¨ 



X

X

iPej

j:iPej



phpCi q ´ hpCi´1 qq


wj  ¨ phpCi q ´ hpCi´1 qq

phpCi q ´ hpCi´1 qq

i“1

“ hp1̂q,
where the last inequality holds because pwj qm
j“1 is a fractional edge cover of HC and h is monotone.
Remark 5.4. Note that, if C is only good for a subset R1 of R, then we can apply the bound to R1 with
its corresponding chain hypergraph.
Example 5.5. Consider our running example from Figure 1; assume |R| “ |S| “ |T | “ N . Consider the
chain 0̂ ≺ y ≺ yz ≺ xyzu “ 1̂, whose hypergraph has three vertices and hyperedges eR “ {y, xyzu}, eS “
{y, yz}, eT “ {yz, xyzu} (isomorphic to the co-atomic hypergraph in√Fig.2). √
Thus, the chain bound on this
chain is N 3{2 , which is tight. (Consider the input R “ S “ T “ r N s ˆ r N s, where the fd xz Ñ u is
defined by the UDF f px, zq “ x and yu Ñ x by gpy, uq “ u.)
If there were no FD’s, then the chain bound is exactly Shearer’s lemma [8] (or, equivalently, AGM bound).
Corollary 5.6 (AGM bound and Shearer’s lemma). Consider a join query on n variables with no fd’s. The
chain bound on the chain C: C0 “ H ≺ C1 “ r1s ≺ C2 “ r2s ≺ ¨ ¨ ¨ ≺ Cn “ rns is exactly Shearer’s lemma.
The Chain Algorithm. In the proof above of the chain bound, the main idea is to take mixtures
of conditional entropies, climbing up the chain. This strategy corresponds combinatorially to conditional
search. From this proof, we derive Algorithm 1 that computes a query Q in time bounded by any fractional
edge cover of the chain hypergraph. The algorithm assumes a fixed, good chain C, where every node i is
19

Algorithm 1 The Chain Algorithm.
Input: A query pL, Rq, over R “ {R1 , . . . , Rm }
Input: A good chain C : 0̂ “ C0 ≺ C1 ≺ ¨ ¨ ¨ ≺ Ck “ 1̂
Input: Chain hypergraph HC “ prks, {e1, . . . , em }q
1: Expand Q to Q`
Ź Thus varspRj q “ Rj , j P rms
2: Q0 “ {pq}
3: For i “ 1 to k do
4:
Qi “ H
5:
For each t P Qi´1 do


T
Ź Takes time Õ min |t ✶ ΠRj ^Ci pRj q| . See text.
6:
T “ j:iPej pt ✶ ΠRj ^Ci pRj qq`
j:iPej

7:

8:

Qi “ Qi Y T
Return Qk

covered7. It preprocesses input relations by indexing them in an attribute order consistent with the chain.
Then, it starts by expanding the query, as explained at the end of Sec. 2. Thus far it takes ÕpN q-time.
Next, the algorithm computes inductively
def

Qi “



`
✶j:Rj ^Ci ‰0̂ ΠRj ^Ci pRj q ,

for i “ 0, 1, . . . , k, where Qi is an intermediate relation with attributes Ci . Initially Q0 consists of just the
empty tuple. Evidently, when i “ k, Qk is the output Q.
To compute Qi , let Rj be some relation such that i P ej , in other words Rj has some new variable that
occurs in Ci but not in Ci´1 . Note that there exists at least one such Rj , because i is covered. Define
Tij “ Qi´1 ✶ ΠCi ^Rj pRj q,
def

`
“ Ci´1 _ pCi ^ Rj q “ Ci .
whose attributes are Xij “ Ci´1 Y pCi ^ Rj q; and, by Eq.(11), its closure is Xij
`
`
Consider Tij ’s expansion Tij (see Sec. 2): it has the same size as Tij and has attributes Xij
“ Ci . Therefore,

Qi “

\

j:iPej

Tij` “

\

j:iPej

`
Qi´1 ✶ ΠCi ^Rj pRj q .

However, we do not want to compute all the Tij` and then compute the intersection to obtain Qi , because this
naı̈ve strategy will push the runtime over the budget. In order to stay within the time budget, the algorithm
computes this intersection differently: it iterates over all tuples t P Qi´1 , and for each tuple computes the
intersection T in line 6 in time Õpminj:iPej p|t ✶ ΠRj ^Ci pRj q|q. This can be accomplished by first computing
j˚ “ argminj:iPej p|t ✶ ΠRj ^Ci pRj q|q and tentatively setting T “ pt ✶ ΠRj˚ ^Ci pRj˚ qq` . Then, the algorithm
removes from T any tuple t1 that is not in the intersection defined in line 6. A tuple t1 P T is not removed
from T only if the following holds: for every j ‰ j˚ s.t. Rj covers i, we have ΠCi ^Rj pt1 q P ΠCi ^Rj pRj q and
pt ✶ ΠCi ^Rj pt1 qq` “ t1 . Note the crucial fact that the relation Rj˚ that is used to iterate over may depend
on the tuple t P Qi´1 . Due to the pre-processing step where every input relation is indexed with an attribute
order consistent with the chain, j˚ can easily be computed in logarithmic time in data complexity.
Theorem 5.7. Assume the chain C is good for R, and every node i is covered (i.e. no isolated vertices).
Then, for any fractional edge cover of the chain hypergraph, pwj qm
j“1 , the time taken by the Chain Algorithm
Qm
wj
to compute Q is ÕpN ` j“1 Nj q, where Õ hides a logarithmic factor needed for index lookup or binary
search, and a small polynomial factor in query complexity.
7 If

i is not covered, in other words HC has an isolated vertex, then ρ˚ pHC q “ 8, and the algorithm will not work.

20

Proof. We define some notation. For any tuple t and each relation Rj such that Rj ^ Ci ‰ 0̂, denote
nijt “ |t ✶ ΠRj ^Ci pRj q|. Note that if t “ pq is the empty tuple, then nijt “ nijpq “ |ΠRj ^Ci pRj q|.
Fix an iteration i. Denote by Timei the time taken by iteration i (to compute Qi ). We will show that,
for any i P rks,


Y
wj 
Timei “ Õ 
nijpq
.
(13)
j:Rj ^Ci ‰0̂

Qm
Since nijpq ď |Rj |, the sum over all Timei will be at most Õp j“1 |Rj |wj q, as desired. To bound Timei , note
that the number of steps taken to compute Qi is
X
X Y w
X
Y
w
min nijt ď
nijtj “
nijtj .
tPQi´1

j:iPej

tPQi´1 j:iPej

tPQi´1 j:Rj ^Ci ‰0̂

The equality follows from the fact that, if t P Qi´1 and Rj ^ Ci ‰ 0̂ but i R ej , then nijt “ 1. Hence, to
show (13), it is sufficient to show the following:
X
Y
Y
w
nijtj ď
(14)
|nijpq |wj .
tPQi´1 j:Rj ^Ci ‰0̂

j:Rj ^Ci ‰0̂

For 0 ď ℓ ď i ´ 1, define
Tℓ

def

gpℓq

def

“

“

ΠCℓ pQi´1 q,
X
Y

w

nijtj .

tPTℓ j:Rj ^Ci ‰0̂

By convention, T0 has a single empty tuple t “ pq. Then, (14) is equivalent to gpi ´ 1q ď gp0q. Thus, to
show (14) it is sufficient to show that gpℓq is non-increasing in ℓ:
X
Y
w
nijtj
gpℓq “
tPTℓ j:Rj ^Ci ‰0̂

“

X

uPTℓ´1

“

X

w

Y

j
niju

X

Y

j
niju

w

X

Y

j
niju

X

Y

j
niju

Y

j:Rj ^Ci ‰0̂
i´1Pej
w

uPTℓ´1 j:Rj ^Ci ‰0̂
i´1Rej

“

X

Y

w

j
nijpu,vq

v:
pu,vqPTℓ j:Rj ^Ci ‰0̂
i´1Pej

uPTℓ´1 j:Rj ^Ci ‰0̂
i´1Rej

ď

j
nijpu,vq

v:
pu,vqPTℓ j:Rj ^Ci ‰0̂

X

uPTℓ´1 j:Rj ^Ci ‰0̂
i´1Rej

ď

w

Y

Y

wj
X


nijpu,vq 



v:
pu,vqPTℓ

w

j
niju

j:Rj ^Ci ‰0̂
i´1Pej
w

uPTℓ´1 j:Rj ^Ci ‰0̂

“

gpℓ ´ 1q.

The first inequality is generalized Hölder inequality, which applies because pwj qm
j“1 fractionally cover vertex
i´1 of the chain hypergraph HC . The second inequality holds because, for every u P Tℓ´1 , u ✶ ΠRj XCi pRj q Ě
Tℓ .
21

1̂
R
abc
a

T
bdf

S
ade
b

c

d

U
cef
e

f

0̂
Figure 4: A query where the chain bound is not optimal
We present some examples.
Example 5.8. Continue with Example 5.5. The variable order corresponding to the chain 0̂ ≺ y ≺ yz ≺ 1̂
is y, z, pxuq, where x, u can be arranged in any order. The Chain Algorithm computes three intermediate
relations:
Q1 pyq “
Q2 pyzq “
Q3 pyzxuq “

Πy pRpxyqq X Πy pSpyzqq
Q1 pyq ✶ Spyzq
pQ2 pyzq ✶ Rpxyqq` X pQ2 pyzq ✶ T pzuqq`

The first two steps are straightforward. In the third, the join Q2 pyzq ✶ Rpxyq results in a relation with
attributes xyz, which needs to be expanded with u (e.g. by computing the user-defined function u “ f px, zq),
and similarly for the second join. However, the algorithm does not compute the joins first then intersect,
instead it iterates over tuples t P Q2 pyzq and computes an intersection on a per-tuple basis using the less
expensive option. In particular, for each t “ py, zq P Q2 , it compares |t ✶ Rpx, yq| and |t ✶ T pz, uq| (which
can be done in logarithmic time given that R was indexed with attribute order py, xq and T with order pz, uq).
Suppose |t ✶ Rpx, yq| ď |t ✶ T pz, uq|, then for each py, z, xq P t ✶ Rpx, yq the algorithm uses the xz Ñ u
FD to obtain the tuple py, z, x, uq. The next task is to verify that this tuple is indeed in the intersection as
defined in line 6. This is done with two verifications: we make sure that pz, uq P T , and that yu Ñ x is
indeed satisfied.8
On this chain the algorithm runs in optimal time OpN 3{2 q. We note that all previously proposed known
worst-case optimal join algorithms for queries without FD’s [18,19,23] require ΩpN 2 q to compute the previous
query on this instance: R “ S “ T “ {p1, iq | i P rN {2s} Y {pi, 1q | i P rN {2s}. For example, LFTJ
with variable order y, z, x, u computes queries Q1 pyq, Q2 pyzq, Q3 pxyzq, Q4 pxyzuq, where |Q3 | “ N 2 . Note,
however, that not every maximal chain gives an optimal bound: for example the chain 0̂ ≺ x ≺ xu ≺ xyu ≺
xyzu “ 1̂ has hyperedges: eR “ {x, xyu}, eS “ {xyu, xyzu}, eT “ {xu, xyzu} (isomorphic to the atomic
hypergraph in Fig.2), and the optimal fractional edge covering number ρ˚ “ 2, hence the chain bound is
|QD | ď N 2 , which is sub-optimal.
Choosing a good chain. When there are FDs, it is not clear if there even exists a chain with a finite
chain bound. We show in this section how to select a chain so that the chain hypergraph does not have
an isolated vertex. This means the fractional edge cover number of the chain hypergraph is finite. The
first method to select the chain corresponds to a generalization of Shearer’s lemma. The second method
interestingly corresponds to a dual version of Shearer’s lemma.
Corollary 5.9 (Shearer’s Lemma for FDs). Consider a query pL, Rq. Let J be the set of join-irreducibles
that are below the order ideal generated by elements in R. There exists a set {X1 , . . . , Xn } of members of J
8 This

is a subtle step in the algorithm that is easy to miss at the first read.

22

Wi
satisfying the following. Let C be the chain C0 “ 0̂ ≺ C1 ≺ ¨ ¨ ¨ ≺ Cn “ 1̂, where Ci “ j“1 Xj . Then the
chain C is good and the hypergraph HC has no isolated vertex.
W
W
Proof. Note that ZPJ Z “ 1̂ because m
j“1 Rj “ 1̂. We construct the sequence X1 , . . . , Xn inductively. For
Wi´1
i P rns, suppose we have constructed the sequence X1 , . . . , Xi´1 . Let Y “ j“1 Xj . (If i “ 1 then Y “ 0̂.)
Let Xi be an element in J ´ {X1 , . . . , Xi´1 } such that the Y ≺ Y _ Xi and Y _ Xi is minimal among all
such Xi . We stop at Xn when
Wi the join is 1̂.
For i P rns, let Ci “ j“1 Xj . We first show that the chain C “ pCi qni“1 is a good chain for R.
Note that all elements Ci are distinct. Consider any Rj P R, and suppose Rj ^ Ci´1 ‰ Rj ^ Ci but
pRj ^ Ci q _ Ci´1 ≺ Ci . Then, S “ pRj ^ Ci q _ Ci´1 is strictly in between Ci´1 and Ci . Because, if S “ Ci´1
W
then Rj ^ Ci´1 “ Rj ^ Ci . Let Y “ i´1
j“1 Xj . We show that there is an element X P J ´ {X1 , . . . , Xi´1 } such
that Ci´1 ≺ Y _ X ≺ Ci . This will violate the choice of Xi and the proof of the claim would be complete.
Note that S is the join of all join-irreducibles below Ci´1 and below Rj ^ Ci . The join-irreducibles below
Rj ^ Ci are below Rj , and thus they are in the set J. Pick X to be a join-irreducible below Rj ^ Ci but not
below Ci´1 and we are done.
To see that every vertex i P rns is covered in the chain-cover hypergraph, note that if Xi  Rj then
Rj ^ Ci ‰ Rj ^ Ci´1 .
xyz “ 1̂
yz

xz
x

z

y

0̂
Figure 5: Lattice for Q :- Rpxq, Spyq, xy Ñ z
Example 5.10. Recall an example query with UDFs: Q :- Rpxq, Spyq, z “ f px, yq where f is a UDF. The
lattice is shown in Fig. 5. If we selected any maximal (and thus good) chain, such as 0̂ ≺ z ≺ xz ≺ xyz, or
0̂ ≺ x ≺ xz ≺ xyz, then z or xz would be an isolated vertex in the chain hypergraph. Corollary 5.9 tells us
to construct a chain by joining the join irreducibles below R and S, which are x, y. Hence, we would select
a chain such as 0̂ ≺ x ≺ xyz which has no isolated vertices. The algorithm runs in time OpN 2 q, which is
worst-case optimal. This chain is not maximal.
We can flip the above proof, working from the meet-irreducibles instead of the join-irreducibles, to obtain
the dual version of Shearer’s lemma.
Corollary 5.11 (Dual Shearer’s Lemma for FDs). Let pL, Rq represent an input query. There exists a
sequence
X1 , . . . , Xn of meet-irreducibles of L satisfying the following. For i “ 0, 1, . . . n, define Ci “
Vn´i
n
X
.
j The chain C “ pCi qi“0 is good for R and the chain hypergraph HC has no isolated vertex.
j“1
A condition for the chain bound to be tight. Now that we know how to select a chain so that the
bound is finite, the next question is whether the chain bound is tight for some class of queries.
Example 5.12. The chain bound is optimal on some non-normal lattices. Consider the query
Rpxq, Spyq, T pzq, xy Ñ z, xz Ñ y, yz Ñ x,
23

whose lattice is M3 in Fig. 3 (a non-normal lattice), with |R| “ |S| “ |T | “ N . The chain 0̂ ≺ x ≺ xyz “ 1̂
gives a the tight upper bound N 2 , because its chain hypergraph is eR “ {x}, eS “ {1̂}, eT “ {1̂}, has optimal
edge covers pwx , wy , wz q “ p1, 1, 0q and “ p1, 0, 1q.
Before presenting a sufficient condition for when the chain bound is tight, we need a simple lemma.
Lemma 5.13. Let pL, Rq represent a query. Let C : 0̂ “ C0 ≺ C1 ≺ ¨ ¨ ¨ ≺ Ck “ 1̂ be a chain that is good
for every X P L. For every S P L, define epSq “ {i P rks | S ^ Ci ‰ S ^ Ci´1 }. Then, X  Y implies
epXq Ď epY q.
Proof. Consider any i R epY q; then, X ^ Ci  Y ^ Ci “ Y ^ Ci´1  Ci´1 . Thus, X ^ Ci “ X ^ Ci´1 which
means i R epXq.
Theorem 5.14. Let 0̂ “ C0 ≺ C1 ¨ ¨ ¨ ≺ Ck “ 1̂ be a chain that is good for every X P L. Also, suppose for
every X, Y P L, the following holds
epX _ Y q Ď epXq Y epY q.
(15)
Then the chain bound is tight on this lattice.
Proof. Let h˚ be an optimal (polymatroid) solution to LLP on L. We define a new L-function u as follows.
up0̂q “
upXq “

0
X

ph˚ pCi q ´ h˚ pCi´1 qq, X P L.

iPepXq

Claim 1. u is also an optimal solution to LLP on L.
We first show that u is a polymatroid. Non-negativity of u follows from monotonicity of h˚ . Monotonicity
of u follows from Lemma 5.13. Submodularity follows from the assumption that epX _ Y q Ď epXq Y epY q.
In fact, from Lemma 5.13 epXq Ď epX _ Y q and epY q Ď epX _ Y q, which means epX _ Y q “ epXq Y epY q.
And thus u is modular.
Next, we show that upXq ď h˚ pXq for all X P L. In particular, u is a feasible solution to LLP on L.
This is proved by induction on |epXq|. The base case when |epXq| “ 0 is trivial. For the inductive step, let
j be the maximum number in epXq. Then,
X
ph˚ pCi q ´ h˚ pCi´1 qq
upXq “
iPepXq

“

X

ph˚ pCi q ´ h˚ pCi´1 qq ` h˚ pCj q ´ h˚ pCj´1 q

iPepX^Cj´1 q

“
pinduction hypothesisq ď
psubmodularity of h˚ q ď

upX ^ Cj´1 q ` h˚ pCj q ´ h˚ pCj´1 q
h˚ pX ^ Cj´1 q ` h˚ pCj q ´ h˚ pCj´1 q
h˚ pXq

Since up1̂q “ h˚ p1̂q, u is an optimal solution to LLP on L as claimed.
Claim 2. u is materializable.
Let g be a polymatroid on the Boolean algebra Bk , where
gpiq “
gpXq “

h˚ pCi q ´ h˚ pCi´1 q
X
gpiq.
iPX

Qk
Then g is a modular polymatroid and it can be materialized with a product instance: D “ i“1 r2gpiq s.
We exhibit an embedding from u to f . The map f : L Ñ Bk defined by f pXq “ epXq is an embedding
because X _ Y Ñ epX _ Y q “ epXq Y epY q. One can verify that u “ g ˝ f . Hence, u is materializable from
Proposition 3.6.
24

{1, 2, 3} 1̂ “ xyzu
{1, 3} xyu
{1, 3} xy
{1} y

{1, 2} yz

xzu {2, 3}

{3} xu

zu {2, 3}

{3} x

{3} u

z {2}

0̂
Figure 6: Condition (15) holds for this lattice
Corollary 5.15. The chain bound is tight on distributive lattices.
Proof. Consider any maximal chain on the distributive lattice L. We only have to verify that
epX _ Y q Ď epXq Y epY q.
We prove this by showing that if i R epXq Y epY q then i R epX _ Y q. Suppose
X ^ Ci

“

X ^ Ci´1

Y ^ Ci

“

Y ^ Ci´1 .

Then,
pX _ Y q ^ Ci

“

pX ^ Ci q _ pY ^ Ci q

“
“

pX ^ Ci´1 q _ pY ^ Ci´1 q
pX _ Y q ^ Ci´1 .

Example 5.16 (Tightness on non-distributive lattice). The chain bound is tight on the lattice (and the
chain) shown in Figure 6. The red sets are the sets epXq, X P L. In particular, the characterization
condition (15) goes beyond distributive lattices.
From Proposition 3.2 we obtain the following which subsumes results from [11] in the simple FD case.
Corollary 5.17. If all FDs are simple, then the chain bound is tight and the chain algorithm is worst-case
optimal.
Example 5.18 (Chain bound is not always tight). For some queries, even with normal lattices, no chains
give a tight upper bound. This is illustrated by Q in Fig. 4. Consider the chain 0̂ ≺ a ≺ abc ≺ 1̂. Denoting
{1, 2, 3} the vertices of the chain hypergraph, its edges are eR “ {1, 2}, eS “ {1, 3}, eT “ eU “ {2, 3}. The
optimal fractional edge cover is pwR , wS , wT , wU q “ p1{2, 1{2, 1{2, 0q, ρ˚ “ 3{2, therefore the chain bound is
|QD | ď N 3{2 and the Chain Algorithm will run in this time. All other maximal chains give the same bound
(non-maximal chains are not good). However, we show in the next section that |QD | ď N 4{3 , which means
that no chain bound is tight.

25

Discussion We have shown that the chain bound implies Shearer’s lemma and AGM bound from the
Boolean algebra; more generally it is tight on all distributive lattices. The lattice corresponding to simple
FDs is distributive, thus the chain algorithm is worst-case optimal for simple FDs. We also presented
examples and proved results on how to choose a good chain so that the chain hypergraph does not have an
isolated vertex.
For brevity, we have described the Chain Algorithm using breadth-first search (or bottom-up). It can
also be adapted to a depth-first implementation (or top-down), as used for example in LogicBlox’ LFTJ [23],
which does not materialize intermediate relations.

5.2

Sub-Modularity Bound and Sub-Modularity Algorithm (SMA)

For some lattices, like Example 5.18, the Chain Algorithm is sub-optimal no matter what chain we choose.
We describe here a second proof technique for Shearer’s lemma and its adaptation to lattices, and derive
a new algorithm. We assume w.l.o.g. that all coefficients wj in (7) nare rational numbers,
o wj “ qj {d, and
rewrite the set {R1 , . . . , Rm } of lattice elements as a multiset B “
lattice element Rj is copied qj times. Then, inequality (7) becomes:
X
hpBi q ě d ¨ hp1̂q

B1 , B2 , . . . , BPj qj

Ď L where each

(16)

i

The Sub-modularity Proof Sequence. Balister and Bollobás [4] give a simple proof of (16) that uses
only the sub-modularity inequality, which we adapt here for arbitrary lattices. We refer to this proof
strategy a sub-modularity proof or SM-proof. An SM-proof starts with a mutiset B “ {B1 , B2 , . . .}, and
applies repeatedly sub-modularity steps (SM-steps)9 . An SM-step, pX, Y q Ñ pX ^ Y, X _ Y q, consists of
removing two incomparable elements X, Y from B, and replacing them with X ^ Y, X _ Y . A sub-modularity
proof sequence, or simply an SM-proof, repeatedly applies SM-steps to a multiset B until all elements in B
are comparable; at that point B is a chain 1̂  C1  C2  . . ., and we denote d, d1 , d2 , . . . the multiplicities
of the elements in B. The sub-modularity bound corresponding to this proof sequence is:
X
hpBi q ě d ¨ hp1̂q ` d1 ¨ hpC1 q ` . . . ě d ¨ hp1̂q
i

Example 5.19. The following is a valid instance of inequality (7) on the Boolean algebra lattice 2{a,b,c,d}:
1
1
1
hpabcq ` hpabdq ` hpacdq ` hpbcdq ě hp1̂q.
3
3
3
This corresponds to d “ 3, B “ {abc, abc, abc, abd, acd, bcd}, and the rewritten inequality
hpabcq ` hpabcq ` hpabcq ` hpabdq ` hpacdq ` hpbcdq ě 3 ¨ hp1̂q.
We can prove this inequality by applying the following SM-steps:
hpabcq ` hpabdq ě

hp1̂q ` hpabq

hpabcq ` hpacdq ě
hpabcq ` hpbcdq ě

hp1̂q ` hpacq
hp1̂q ` hpbcq

hpabq ` hpacq ě
hpaq ` hpbcq ě

hpabcq ` hpaq
hpabcq ` hp0̂q.

Altogether the SM-steps proved that
hpabcq ` hpabcq ` hpabcq ` hpabdq ` hpacdq ` hpbcdq ě 3 ¨ hp1̂q ` 2hpabcq ` hp0̂q,
9 Called

“elementary compression” in [4].

26

(17)

which implies (17). This example also shows that there is extra information we could not make use of:
the 2hpabcq term that is left “dangling”. As we shall see later, in some cases this is a manifestation of the
limitation of SM-proofs.
Example 5.20. Continuing Example 5.18 where the Chain bound is not tight, the SM-proof is very simple:
hpabcq ` hpadeq ě

hp1̂q ` hpaq

hpbdf q ` hpcef q ě
hpaq ` hpf q ě

hp1̂q ` hpf q
hp1̂q ` hp0̂q,

resulting in the SM-bound:
hp1̂q ď

1
1
1
1
hpabcq ` hpadeq ` hpbdf q ` hpcef q.
3
3
3
3

In particular, when all input relations have size N , the output size bound is N 4{3 . This coincides with the
co-atomic hypergraph cover, hence it is tight.
Obviously, any SM-bound is a correct inequality of the form (16), but the converse does not always hold,
as we shall see. The converse holds, however, in distributive lattices. We next show that given any fractional
edge cover pwj qm
j“1 of the co-atomic hypergraph of a distributive lattice, inequality (7) is provable through an
SM-proof sequence and, moreover, one can apply the SM-steps in any order. It follows that every distributive
lattice is normal!
For each element X P L, define eX “ {Z | Z P Vco , X ­ Z}; notice that, if X is an input, X “ Rj , then
eRj is a hyperedge of Hco . A d-cover of the co-atoms is a multiset B s.t. for each vertex Z P V there are at
least d elements X P B s.t. Z P eX . Then:
Lemma 5.21. Suppose L is a distributive lattice, and B is a d-cover of the co-atoms. If B 1 is obtained from
B by applying one SM-step pX, Y q Ñ pX ^ Y, X _ Y q, then B 1 is also a d-cover of the co-atoms.
Proof. We prove this using a similar argument as in [4]. By Lemma 4.1, for any co-atom Z, cpZ, {X, Y }q “
cpZ, {X ^ Y, X _ Y }q, hence the number of elements in B that cover Z is the same as the number of elements
in B 1 that cover Z.
Corollary 5.22. Given any fractional edge cover pwj qm
j“1 of the co-atomic hypergraph, inequality (7) is
provable through an SM-proof sequence and, moreover, one can apply the SM-steps in any order.
P
Proof. Progress is ensured by the fact that i |eBi |2 strictly increases after each sub-modularity step:
|eX |2 ` |eY |2 ă |eX X eY |2 ` |eX Y eY |2 “ |eX_Y |2 ` |eX^Y |2 .

Finally, when the process ends, the multiset B is a chain and hp1̂q must occur d times, because any co-atom
Z that is  C1 (the next largest element in the chain) is covered only by 1̂.
Corollary 5.23. Every distributive lattice is normal.
The Submodularity Algorithm. The SM-Algorithm (Algorithm 2) starts by using the cardinalities
˚
pNj qm
j“1 of the input relations to obtain an optimal solution h of the LLP (Eq.(5)), and an optimal dual
˚
˚
˚ m
solution s , w : the coefficients pwj qj“1 form a valid inequality (7) (see the discussion at the beginning of
Sec 5), which is tight for h˚ ; as before, write s˚X,Y , wj˚ as rational numbers, wj˚ “ qj {d, s˚X,Y “ pX,Y {d.10
The SM-algorithm requires as an input an SM-proof sequence of this inequality, then computes the query
QD as follows.
10 Extreme

points of the dual polytope are data-independent!

27

The algorithm performs the SM-steps in the proof sequence, maintaining the multiset B Ď L.11 It also
maintains a cache of temporary relations, in one-to-one correspondence with B: for each B P B, there is
one temporary relation T pBq, with set of attributes B; if B occurs multiple times in B, then there are
multiple temporary relations T pBq. Initially the temporary tables are the input relations, s.t. each relation
Rj is copied qj times. Next, the algorithm applies the SM-steps in the proof sequence, and for each step
pX, Y q Ñ pX ^ Y, X _ Y q performs a sub-modularity join:
Sub-modularity join. Q
Let Z “ X ^ Y be the set of common variables in T pXq, T pY q. The
degree of some value v P zPZ DomainpZq is the number of tuples in T pY q with Z “ v:
def

degreeT pY q pvq “ |σZ“v pT pY qq|

(18)

The SM-join partitions ΠZ pT pY qq into light hitters and heavy hitters, consisting of values with
˚
˚
˚
˚
degree ď 2h pY q´h pZq or ą 2h pY q´h pZq respectively; denote them Lite and Heavy. Define
T pX _ Y q the subset of the join T pXq ✶ T pY q restricted to light hitters, and define T pX ^ Y q
to be the set of heavy hitters. The SM-join removes T pXq, T pY q from the cache, and adds
T pX ^ Y q, T pX _ Y q to the cache of temporary tables.
After processing the entire proof sequence, the algorithm returns the union of all d temporary tables
T p1̂q, then semi-join reduces them with all input relations.
Algorithm 2 The Sub-modularity Algorithm
Input: A query Q, over relationsPR1 , . . . , Rm
Input: A SM-proof sequence of BPB h˚ pBq ě d ¨ h˚ p1̂q
1: Initialize |B| temporary tables T pBq, B P B:
2:
where each T pBq is initially some Rj
3: For each SM-step pX, Y q Ñ pX ^ Y, X _ Y q do
4:
Let Z “ X n^ Y
o
def
5:
LitepZq “ v | log degreeT pY q pvq ď h˚ pY q ´ h˚ pZq
n
o
def
6:
HeavypZq “ v | log degreeT pY q pvq ą h˚ pY q ´ h˚ pZq
7:
Add the following tables to the cache
8:
T pX ^ Y q “ ΠZ pT pXqq X ΠZ pT pY qq X HeavypZq
9:
T pX _ Y q “ pT pXq ✶ pT pY q ˙ LitepZqqq`
S
10: Return BPB,B“1̂ T pBq semi-join reduced with all inputs

Ź See text

The following invariant is maintained by the algorithm:

Lemma 5.24. At each step in the algorithm, for any relation T pBq in cache, log |T pBq| ď h˚ pBq.
Proof. We induct on the number of SM-steps. If T pBq was a copy of an input relation Rj that participates
in the proof, then log |T pBq| “ nj “ h˚ pBq, because due to complementary slackness wj˚ ą 0 implies
the primal constraint has to be tight. For every SM-step pX, Y q Ñ pX ^ Y, X _ Y q, it must hold that
h˚ pY q ´ h˚ pX ^ Y q “ h˚ pX _ Y q ´ h˚ pXq because inequality (7) is an equality for h˚ : we started from an
LLP-dual optimal solution. Hence,
|T pX _ Y q| ď

|T pXq| ¨ 2h

ď
ď

2h pXq ¨ 2h
˚
2h pX_Y q

|T pX ^ Y q| ď
11 I.e.

˚

|T pY q|{2h

every member of the multiset is a member of the set L

28

˚

˚

˚

pY q´h˚ pZq

pX_Y q´h˚ pXq

pY q´h˚ pZq

ď 2h

˚

pZq

Example 5.25. Consider the SM proof sequence from Example 5.20, we explain how the SM algorithm
works for this proof sequence. The optimal solution LLP solution is
h˚ p1̂q “

p4{3q ¨ log N,

˚

log N, for X P {abc, ade, bdf, cef },
p2{3q ¨ log N, for X P {a, b, c, d, e, f }.

h pXq “
h˚ pXq “
The SM algorithm works as follows.

• It first SM-joins Rpabcq with Spadeq, producing relations Q1 p1̂q and Heavy1 paq, where Heavy1 paq is the
set of values a whose S-degree is at least N 1´2{3 “ N 1{3 . Thus, |Heavy1 paq| ď N 2{3 . Since the light
part has degree at most N 1{3 , |Q1 p1̂q| ď N 4{3 .
• Similarly it SM-joins T pbdf q with U pcef q producing relations Q2 p1̂q and Heavy2 pf q, and finally it
computes the cross product Heavy1 paq ˆ Heavy2 pf q, then expands the result (since {a, f }` “ 1̂) to
obtain a relation Q3 p1̂q. Since both |Heavy1 paq| ď N 2{3 and |Heavy2 pf q| ď N 2{3 , their cross-product
has size at most N 4{3 and can be computed within that time budget.
• Finally, it returns Q1 Y Q2 Y Q3 semi-joined with input relations.
There are two reasons why the SM-algorithm may fail: some branches of heavy or light elements may
never join into a T p1̂q, and the algorithm may attempt to join some light with heavy values from the same
relation. We give a sufficient condition for the SMA algorithm to be correct. The criterion consists of
iterating over the SM-proof sequence, and assigning a set LabelspBq of labels to each copy B P B. (Copies
of the same lattice element receive their own label sets.) Initially, every B P B receives a single label
1, namely LabelspBq “ {1}, the same for all B P B. Consider an SM-step pX, Y q Ñ pX ^ Y, X _ Y q.
Let ApX, Y q “ LabelspXq X LabelspY q. Assign LabelspX _ Y q “ ApX, Y q and, if X ^ Y ‰ 0̂, assign to
LabelspX ^ Y q a fresh set of a labels: LabelspX ^ Y q “ {f pjq | j P ApX, Y q} for some label assignment f .
For each Z R {X, Y }, set LabelspZq “ LabelspZq Y {f pjq | | j P LabelspZq X ApX, Y q}. Note the crucial fact
that in this description we did not remove X, Y from B. We keep accumulating elements to B, unlike in the
proof sequence where each step replaces an old pair with a new pair. Note the important fact that that each
copy of lattice element in the multiset B gets its own label set.
Definition 5.26 (Good SM-proof sequence). Call the SM-proof sequence good
S if ApX, Y q ‰ H for all
SM-steps pX, Y q Ñ pX _ Y, X ^ Y q, and if in the end every label is present in 1̂PB Labelsp1̂q.

Example 5.27. Continue with Example 5.25, we check that the SM-proof is good. Initially all elements
in {abc, ade, bdf, cef } have Labels “ {1}. After the first SM-step: Labelsp1̂q “ {1} and Labelspaq “ {2},
where 2 is a fresh label; 2 is also added to Labels of abc,
Sade, bdf, cef , so they are all equal to {1, 2}.
After the second SM-step there are two copies of 1̂, where 1̂PB Labelsp1̂q “ {1, 2} and Labelspf q “ {3, 4},
two fresh labels, which are added to Labelspaq so that Labelspaq “ {2, 3, 4}. After the third SM-step,
S
1̂PB Labelsp1̂q “ {1, 2, 3, 4}; it follows that the proof sequence is good.

We next show that if there is a good proof sequence, then SMA runs in time that matches the bound.
P
Theorem 5.28. If the SM-proof sequence for j wj˚ hpRj q ě hp1̂q is good, then the SM algorithm correctly
Q
w˚
computes QD , and runs in time ÕpN ` j Nj j q, where Õ hides a log N factor, a polynomial in query size
and SM-proof length.
def

Proof. At any point in time, let Li “ {B P B | i P LabelspBq}. Let Qi “ ✶BPLi T pBq. We
S show by induction
on the number of SM-steps that the algorithm maintains the following invariant: Q Ď i Qi . The base case
holds because initially there is only one label, and Q “ Q1 . Consider an SM-step, pX, Y q Ñ pX ^ Y, X _ Y q.

29

Only the subqueries Qi for which i P ApX, Y q contain both X and Y . For each such query, consider two
new queries:
QHeavy
i
QLite
i

T pX ^ Y q ✶✶BPLi T pBq
T pX _ Y q ✶✶BPLi T pBq.

“
“

Then, obviously Qi Ď QHeavy
Y QLite
and thus the invariant is maintained after the SM-step. In the end, each
i
i
sub-query reaches 1̂ and the semi-join reduction filters the result. (We need this step because large input
relations Rj might have had coefficients wj˚ set to 0 in the optimal solution of dual-LLP.)
1̂
A
Z

D

X

Y

C

U

B

0̂
Figure 7: A lattice with an SM-proof that is not good
Example 5.29. Not every SM-proof sequence is good. Consider the following SM-proof sequence of hpXq `
hpY q ` hpZq ` hpU q ě 2hp1̂q ` 2hp0̂q on the lattice in Fig. 7:
hpXq ` hpY q ě
hpAq ` hpZq ě

hpAq ` hpBq
hp1̂q ` hpCq

hpBq ` hpU q ě
hpCq ` hpDq ě

hpDq ` hp0̂q
hp1̂q ` hp0̂q

From the first three SM-steps, LabelspBq “ {2} and LabelspCq “ {3}, and LabelspDq “ {2}. Thus, at the
last step ApC, Dq “ H which is not good. The inequality admits a different proof sequence, which is good:
pX, Zq Ñ pC, 1̂q, pY, U q Ñ p0̂, Dq, pC, Dq Ñ p0̂, 1̂q. It is unknown whether every SM-proof sequence can be
transformed into a good one.
Example 5.30. For the query in Fig. 8, an SM-proof is
hpXq ` hpY q ě hpCq ` hpAq
hpZq ` hpW q ě hpDq ` hpBq
hpAq ` hpDq
hpBq ` hpCq

ě hp1̂q ` hp0̂q
ě hp1̂q ` hp0̂q.

After the second SM-step, LabelspCq “ {1, 3}, LabelspDq “ {1, 2}, LabelspAq “ {2, 3}, LabelspBq “ {3}.
Hence, labels 2 and 3 are pushed to copies of Labelsp1̂q, but label 1 is not present in any set Labelsp1̂q. So
this proof sequence is no good, for a different reason from the previous example.
Here, we show that some lattices don’t have any SM-proofs:
30

1̂
D

C
X

Y

Z

W
B

A
0̂

Figure 8: Another example with a bad SM-proof
1̂
U

V

W

P

S

T

Z
M

N

O

G

I

J

D

E

F

0̂
Figure 9: A lattice with no SM-proof sequence
Example 5.31. Not every lattice admits an SM-proof. Consider the lattice in Fig. 9. It satisfies the
inequality hpM q ` hpN q ` hpOq ě 2hp1̂q ` hp0̂q, but there is no SM-proof sequence that derives it. This
is somewhat surprising, because Lemma 3.9 showed that every inequality can be proven by adding up submodularity inequalities, and indeed our inequality can be obtained by summing up:
hpM q ` hpZq ě
hpN q ` hpZq ě

hpU q ` hpGq
hpV q ` hpIq

(19)
(20)

hpOq ` hpZq ě
hpU q ` hpV q ě

hpW q ` hpJq
hp1̂q ` hpP q

(21)
(22)

hpW q ` hpP q ě
hpGq ` hpIq ě

hp1̂q ` hpZq
hpZq ` hpDq

(23)
(24)

hpJq ` hpDq ě

hpZq ` hp0̂q

(25)

(The last two inequalities each consists of 2 SM-steps, identical to the proof of hpxyq ` hpxzq ` hpyzq ě
31

2hpxyzq ` hp0̂q for the triangle query, see Example 3.10.) But this is not an SM-proof, because in the first
step we need hpZq, which is only produced later. More surprisingly, the lattice is normal.

5.3

Meeting LLP-Bound with Conditional SM Algorithm – CSMA

P
Recall that in the chain proof we decompose an input hpRj q into a telescoping sum hpRj q “ iPej phpRj ^
Ci q ´ hpRj ^ Ci´1 qq. If h is entropic, then hpY q ´ hpXq “ hpY |Xq is the conditional entropy. Hence, the
chain proof decomposes an input hpRi q into a sum of conditional terms. Taking cues from this conditional
decomposition, and the SM-steps of the SM-proof, we devise a new type of proof sequence that resolves the
dilemma of the query of Example 5.31, depicted in Fig. 9. In what follows, when X  Y we write hpY |Xq
as a short hand for hpY q ´ hpXq. We assume h is a polymatroid.
Example (5.31 Continued). The key issue is that, starting from hpM q ` hpN q ` hpOq there is no SM-step
that will help prove the desired inequality hpM q ` hpN q ` hpOq ě 2hp1̂q ` hp0̂q. For example, applying
hpM q ` hpN q ě hp1̂q ` hpDq and we are left to show that hpDq ` hpOq ě hp1̂q ` hp0̂q, but D _ O “ W ≺ 1̂
and so this is simply impossible. The trick is to apply an SM-step between G and I, which are below the
input relations, as suggested by (24). To obtain G and I, we decompose hpM q into hpM |Gq ` hpGq and hpN q
into hpN |Iq ` hpIq; these decomposition steps get the proof off the ground.
Formally, our proof strategy involves the following three basic rules, instead of just the SM-rule as before:
• CD-rule: for X ≺ Y , hpY q Ñ hpY |Xq ` hpXq.
• CC-rule: for X ≺ Y , hpY |Xq ` hpXq Ñ hpY q.
• SM-rule: for A ­ž B, hpAq ` hpB|A ^ Bq Ñ hpA _ Bq.
(CD stands for conditional decomposition, CC conditional composition, and SM sub-modularity.) Together,
they are called the CSM rules (for conditional submodularity). The vision behind CSMA is to show that
(A) every output inequality (7) can be proved using a series of CD, CC, and SM rules, and
(B) each rule can be interpreted combinatorially to become an algorithmic step, and together they consti˚
tute an algorithm (called CSMA) that runs in time Õp2h p1̂q q
Interestingly, we fell short of objective (A) yet were able to achieve a stronger result than objective (B)! In
particular, with respect to (A) we conjecture that the three rules above form a complete proof system. We
only managed to prove a weaker version of the conjecture (Theorem 5.34) which is sufficient for CSMA to
work, at the price of a poly-log factor. On the other hand, with respect to (B) we will work with output
inequalities that are more general than (7), and with constraints more general than the fd-constraints.
5.3.1

Conditional LLP (CLLP)

A key technical tool that helps realize the vision is a conditional version of LLP, called the conditional LLP
(CLLP). A nice by-product of CLLP is that we will be able to compute join queries with given degree bounds,
which is even more general than join queries with functional dependencies!
Let P be some set of pairs pX, Y q P L2 such that X ≺ Y . Assume for every pair pX, Y q P P, there is a
given non-negative number nY |X called a log-degree bound. The CLLP is defined as:
max
s.t.

hp1̂q
hpY q ´ hpXq ď nY |X

@pX, Y q P P

hpA _ Bq ` hpA ^ Bq ´ hpAq ´ hpBq ď 0 @A ­ž B P L
hpXq ´ hpY q ď 0
@X ≺ Y P L.

32

(By default, hp0̂q “ 0, and hpXq ě 0.) In other words, CLLP requires h to be a polymatroid, subject
to the log-degree constraints. The cardinality constraints are a special case of the log-degree constraints
hpY q ´ hp0̂q ď nY |0̂ “ nY . (Intuitively, cardinality constraints are degree bounds of the empty tuple;
fd-constraints X Ñ Y imposes the Y -degree bound of 0 for every X-tuple; and so the degree bounds
hpY |Xq ď nY |X strictly generalizes both cardinality constraints and fd constraints.) The following is obvious:

Proposition 5.32. LLP is exactly the same as CLLP for the special case when P “ p0̂, Rj q | Rj P R .
Furthermore, we can easily use the log-degree constraints to encode input relations with known maximum
degree bounds.
We will also need the dual CLLP. Let cY |X , sA,B and mX,Y denote the (non-negative) dual variables
corresponding to the log-degree, sub-modularity, and monotonicity constraints, respectively. For each Z P
L ´ {0̂}, define
def

netflowpZq “

X

X:X≺Z
pX,ZqPP

X

cZ|X ´

cY |Z `

Y :Z≺Y
pZ,Y qPP

X

sA,B `

X

sA,B ´

A­žB
A_B“Z

A­žB
A^B“Z

X

A:A­žZ

sA,Z ´

X

X:X≺Z

mX,Z `

X

mZ,Y .

Y :Z≺Y

Then, the dual CLLP is
min
s.t.

P

pX,Y qPP

nY |X cY |X

netflowp1̂q ě 1
netflowpZq ě 0

(26)
@Z P L ´ {1̂, 0̂}.

Example (5.31 Continued). Consider the lattice in Figure 9. Suppose the input relations are T pM q, T pN q, T pOq
(along with FDs imposing the lattice structure),12 and we are not given any other bounds on degrees/cardinalities,
then the CLLP has P “ {p0̂, M q, p0̂, N q, p0̂, Oq} where nM “ nM|0̂ “ log2 |T pM q|, nN “ nN |0̂ “ log2 |T pN q|,
and nO “ nO|0̂ “ log2 |T pOq|. In this case CLLP is just LLP. If in addition we also knew, for example, an
upper bound d on the degree of G in table T pM q, then we can extend the CLLP by adding pG, M q to P
where nM|G “ log2 d.
As mentioned earlier, this lattice satisfies the inequality 2hp1̂q ď hpM q ` hpN q ` hpOq, which does not
admit an SM-proof. In the CLLP, this inequality corresponds to the constraint hp1̂q ď nM `n2N `nO , which
results from the following dual solution.
cM “ cN “ cO “ 1{2,
sM,Z “ sN,Z “ sO,Z “ 1{2,

(27)

sU,V “ sP,W “ sG,I “ sD,J “ 1{2,
(where all dual variables that are not specified above are zeros). In this dual solution, netflowp1̂q “ 1 while
all other lattice nodes have a netflow value of 0. Hence, this solution is feasible.
5.3.2

CSM proof sequence

The analog of output inequality (7) in the conditional world is
X
cY |X hpY |Xq ě hp1̂q

(28)

pX,Y qPP

Identical to Lemma 3.9, we can show that (28) holds for all polymatroids if there are vectors s and m such
that pc, s, mq is feasible to the dual-CLLP.
12 We abuse notation here, when the same notation symbol is used for different input relations. This is to avoid notation
cluttering later in the description of the algorithm.

33

To answer question (A), we prove a “reachability” lemma that helps us construct a CSM proof sequence.
Let pc, s, mq be any feasible solution to the dual-CLLP (26). Let K Ď L be a set of lattice elements that
contains 0̂. The conditional closure of K (with respect to pc, s, mq) is computed from K by repeatedly
applying the following two steps: (1) CD-step (“Conditional Decomposition”): if Y P K and X ≺ Y then
add X to K, (2) CC-step (“Conditional Composition”): if X P K and cY |X ą 0 then add Y to K.
Lemma 5.33. For any dual-feasible solution pc, s, mq, let K Ď L be a set that contains 0̂, and K̄ be its
conditional closure. If 1̂ R K̄, then there are two lattice elements A, B P K̄ such that A _ B R K̄ and
sA,B ą 0.
def P
Proof. If 1̂ R K̄ then S “
ZRK̄ netflowpZq ě 1. If there is no such pair pA, Bq, then every dual variable
cY |X , mX,Y , sA,B contributes a non-positive amount to the sum S, which is a contradiction.

Example (5.31 Continued). Consider the dual solution in (27). Let’s take K “ {0̂} as an example.
Because cM , cN , cO ą 0 (where cM is just an alias for cM|0̂ and so on), the conditional closure K̄ contains
M, N, O due to the CC-steps. After applying CD-steps, K̄ includes all lattice elements below M, N, O as
well:
K̄ “ {0̂, D, E, F, G, I, J, M, N, O}.
(At this point K̄ is closed.) Applying Lemma 5.33, we can find G, I P K̄ with sG,I ą 0. If we add Z “ G _ I
to K (and K̄), we can apply Lemma 5.33 again and find M, Z P K̄ with sM,Z ą 0. After adding U “ M _ Z
to K, we can find N, Z P K̄ with sN,Zą0 . After adding V “ N _ Z, we will find U, V P K̄ and add 1̂ “ U _ V .
The above lemma allows us to constructively prove a weaker inequality than (28), which is our answer
to question (A) above.
Theorem 5.34. Let pc, s, mq be an arbitrary feasible solution to the dual-CLLP, where cY |X “ qY |X {d and
1
sA,B “ qA,B
{d are rational numbers. Let B be a multiset of variables hpY |Xq, pX, Y q P P, where each variable
hpY |Xq occurs 4|L| ¨qY |X times. Then, there is a sequence of CD-, CC-, and SM-rules that transforms B into
another multiset B̄ which contains the variable hp1̂q. Moreover, in this sequence all occurrences of identical
rules are consecutive in the sequence (hence, they can be combined into a single “rule with a multiplicity”).
Proof. We prove the theorem with an algorithm. We start from the set K “ {0̂}, and keep adding elements
to it using conditional closure (CC- and CD-) steps until K is conditionally closed; then we add a new
element A _ B with an SM-step using the pair pA, Bq found by Lemma 5.33. This process is repeated until
1̂ P K. With regard to B, initially we will pretend that for each variable hpY |Xq P B we have only qY |X
copies of it instead of 4|L|qY |X copies. While adding elements to K, we will also add variables to B so
eventually B contains ď 4|L|qY |X of each variable.
We maintain the following invariants throughout the execution of the algorithm:
• For every X P K, there is at least one copy of hpXq in B. To maintain this invariant, whenever we add
a new element X to K while B does not contain any copy of hpXq, we apply some conditional closure
rules on B to produce hpXq.
• For every copy of hpY |Xq currently in B, there will always remain at least one copy of hpY |Xq after
each step of the algorithm (i.e. in all subsequent multisets B). To maintain this invariant, before
applying any rule (where we will be losing one copy of each term on the left-hand side of that rule in
order to gain one copy of each term on the right-hand side), we duplicate the multiplicities of all terms
in the current B, all previous multisets B, and all rules that have been applied previously. (In effect,
we re-run the entire history of rule application once.)
The above invariants are initially satisfied. Now we take the conditional closure of K. Whenever X is added
to K due to some Y P K that satisfies X ≺ Y (signalling a CD-step), we first check whether B contains a
copy of hpXq. If it does, then no further action is needed. If not, we duplicate multiplicities in the current
34

and all previous B and all previous rules, and then we apply a CD-rule hpY q Ñ hpXq ` hpY |Xq. Whenever
Y is added to K due to cY |X ą 0 for some X P K, we first check whether hpY q is in B already. If not, we
duplicate all multiplicities as before, and then apply a CC-rule hpXq ` hpY |Xq Ñ hpY q.
Now, suppose K is already conditionally closed, we add A_B using an SM-step guaranteed by Lemma 5.33.
We check whether hpA_Bq is in B. If it is not, we check whether hpB|A^Bq is in B. If it is not, we duplicate
all multiplicities and apply a CD-rule hpBq Ñ hpA ^ Bq ` hpB|A ^ Bq. Now, duplicate all multiplicities
again, and apply an SM-rule hpAq ` hpB|A ^ Bq Ñ hpA _ Bq.
For each element that is added to K, we have to duplicate its multiplicity at most twice, and there are
at most |L| such elements.
Finally, we show that the same rule cannot be applied multiple times. In the above, before we applied
any CC-rule that produced hpY q, we checked whether hpY q was already in B. Only if it was not, we applied
the rule adding hpY q to B, and letting the second invariant preserve it in B. The same holds for SM-rules.
In the above arguments, we applied CD-rules of the form hpY q Ñ hpXq ` hpY |Xq in two different places: In
the first, we checked that hpXq was not in B before we added both hpXq and hpY |Xq to B. In the second,
we checked that hpB|A ^ Bq was not in B before we added both hpB|A ^ Bq and hpA ^ Bq to B.
The series of CC-, CD-, SM-rules with multiplicities is called a CSM proof sequence. Interpreted integrally,
we think of the proof sequence as having D ď 4|L| d copies of hp1̂q that it tries to reach, but at B̄ it reaches
at least one copy and we stop.
Example (5.31 Continued). Now, we simulate the proof of Theorem 5.34 on the dual solution in (27)
q`hpOq
). We will start off with four copies of the
(which corresponds to the inequality hp1̂q ď hpMq`hpN
2
right-hand side (i.e. 2hpM q ` 2hpN q ` 2hpOq), and generate a CSM proof sequence that will produce one
copy of hp1̂q (out of 4 copies).
2hpM q Ñ 2hpM |Gq ` 2hpGq

(adding G to K̄ based on M P K̄)

(29)

2hpN q Ñ 2hpN |Iq ` 2hpIq
2hpIq Ñ 2hpI|Dq ` 2hpDq

(adding I to K̄ based on N P K̄)
(extracting hpI|Dq for the next SM-rule)

(30)
(31)

2hpGq ` 2hpI|Dq Ñ 2hpZq
hpZq ` hpM |Gq Ñ hpU q

(SM-rule based on sG,I ą 0)
(SM-rule based on sM,Z ą 0)

(32)
(33)

hpZq ` hpN |Iq Ñ hpV q
hpV q Ñ hpV |P q ` hpP q

(SM-rule based on sN,Z ą 0)
(extracting hpV |P q for the next SM-rule)

(34)
(35)

hpU q ` hpV |P q Ñ hp1̂q

(SM-rule based on sU,V ą 0)

(36)

Note that rules (29). . . (32) above had multiplicities of 2, because we needed to produce two copies of hpZq:
one for (33) and another for (34).
5.3.3

The CSM algorithm (CSMA)

CSMA is our answer to question (B). The algorithm takes as input a join query with functional dependencies
and maximum degree bounds (if any) from input relations. This input is represented by the set P p0q ,
corresponding log-degree bounds, and the linear program CLLPp0q . For example, if we use CSMA for the
original join query with functional dependencies (with no other max-degree bounds), then we would be
starting with P p0q “ {p0̂, Rj q | Rj P R}; in this case CLLPp0q is equivalent to LLP.
Let hp0q and pcp0q , sp0q , mp0q q be a pair of primal and dual optimal solutions to CLLPp0q , and OPT be
its optimal objective value. CSMA takes the CSM-proof sequence for CLLPp0q as symbolic instructions.
For each instruction, CSMA does some computation, spawning a number of sub-problems, creating new
intermediate tables for the sub-problems if needed. The final output is contained in the union of outputs of
the sub-problems.
For each sub-problem, CSMA constructs a new pair-set P 1 , and a new linear program CLLP1 with dualfeasible solution pc1 , s1 , m1 q. Note that to construct CLLP1 , there has to be a corresponding log-degree bound
n1Y |X for each pair pX, Y q P P 1 . The following two invariants are maintained:
35

(Inv1) For any pX, Y q P P 1 , there is a table T pY q (an input relation of the sub-problem) that “guards” the
constraint hpY |Xq ď n1Y |X of CLLP1 in the sense that
max log2 degT pvq ď n1Y |X .

vPΠX pT q

(Note that if X “ 0̂ then the above says log2 |T | ď n1Y |0̂ “ n1Y , which is a cardinality constraint.)
def

(Inv2) pc1 , s1 , m1 q is feasible to dual-CLLP1 with objective value satisfying OBJ1 “

P

pX,Y qPP

n1Y |X c1Y |X ď OPT.

It can be verified that the two invariants are satisfied at CLLPp0q . Next we describe how CSMA deals with
each instruction from the CSM sequence.
(1) CD-rule hpY q Ñ hpY |Xq ` hpXq with multiplicity t.
Recall that hpY q is just a short hand for hpY |0̂q. By (Inv1) there is a table T pY q with log2 |T | ď nY .
Define
n1Y |X

def

n1X

def

“

“

max log2 degT pvq

vPΠX pT q

log2 |ΠX pT q|

Lemma 5.35 shows that T can be partitioned into at most ℓ “ 2 log N sub-tables T p1q , . . . , T pℓq such
pjq
pjq
that nY |X ` nX ď nY , for all j P rℓs, where
nY |X

def

pjq

def

pjq

nX

“

“

max

vPΠX pT pjq q

log2 degT pjq pvq,

log2 |ΠX pT pjq q|.

For each of these sub-tables T pjq of T , we create a sub-problem with T replaced by T pjq . For the jth
pjq
sub-problem, we add p0̂, Xq and pX, Y q to P with corresponding log-degree constraints hpXq ď nX
pjq
pjq
onto X so we have guards for
and hpY |Xq ď nY |X , respectively. We compute the projection of T
the two new constraints. Set
c1Y |X
c1X
c1Y

“ cY |X ` t{D,
“ cX ` t{D,
“ cY ´ t{D ě 0.

If c1Y “ 0, then we remove p0̂, Y q from P. By examining netflowpZq at each node, we can verify that
pc1 , s, mq is a feasible solution to the new CLLP1 with a reduction in objective value of pnY ´ n1Y |X ´
n1X qt{D.
(2) CC-rule hpY |Xq ` hpXq Ñ hpY q with multiplicity t.
Let R be the guard for hpY |Xq ď nY |X and S for hpXq ď nX . Let θ be a threshold to be determined.
def

If nY |X `nX ď OPT`θ, then we can compute the table T pY q “ SpXq ✶ RpY q by going over all tuples
in S and expanding them using matching tuples in R. The runtime is Õp2nX `nY |X q “ Õp2OPT`θ q. The
dual solution is modified by setting
c1Y |X

“

cY |X ´ t{D,

c1X
c1Y

“
“

cX ´ t{D,
cY ` t{D,

n1Y

“

nY |X ` nX .

36

If nY |X `nX ą OPT`θ, we will start afresh from an optimal solution to the current CLLP. Lemma 5.36
below shows that the current CLLP has an optimal objective value at most OPT ´ θ{pD ´ 1q.
(3) SM-rule hpAq ` hpB|A ^ Bq Ñ hpA _ Bq with multiplicity t.
This is similar to case (2), and becomes identical to case (2) when A “ A ^ B “ X and B “ Y . Let
R be the guard for hpAq ď nA and S for hpB|A ^ Bq ď nB|A^B . If nA ` nB|A^B ď OPT ` θ, then we
can compute T pA _ Bq “ R ✶ S in time Õp2OPT`ǫ q. If nA ` nA|A^B ą OPT ` θ, then we start afresh
from a new optimal solution to the current CLLP. The minor difference to case (2) is that we have to
modify the variable s1A,B “ sA,B ´ t{D. By selecting the correct threshold θ, we can prove that CSMA
runs in time Opplog N qe 2OPT q, where e is a data-independent constant (Theorem 5.37).
Example (5.31 Continued). Given a conjunctive query Q whose functional dependencies correspond to the
lattice in Figure 9 and whose input relations are T pM q, T pN q, T pOq, where |T pM q| “ |T pN q| “ |T pOq| “ N .
In the CLLP, we have P “ {p0̂, M q, p0̂, N q, p0̂, Oq} where nM “ nN “ nO “ log2 N “: n. The optimal
3
2
objective value is OPT “ 3n
2 (which implies that |Q| ď N ), and the feasible dual solution given by (27) is
optimal. Consider the CSM sequence (29). . . (36) that was constructed earlier for (27). We will explain how
3
to run CSMA on this sequence in order to answer Q in time within a polylogarithmic factor of 2OPT “ N 2 .
• The first rule (29) in the sequence is a CD-rule: hpM q Ñ hpM |Gq ` hpGq. The corresponding algorithmic step would be to project T pM q on G while making sure that the projection size times the
maximum degree of the projection in T pM q does not exceed |T pM q| (i.e. while making sure that the
def
def
sum of n1G “ log2 |ΠG pT pM qq| and n1M|G “ maxvPΠG pT pMqq log2 degT pMq pvq does not exceed nM ). If
all tuples v in the projection ΠG pT pM qq have the same degree degT pMq pvq (i.e., if T pM q is “uniform”
with respect to G), then the required condition is met. Otherwise, let’s assume for simplicity that
all degrees degT pMq pvq are powers of 2 (and |T pM q| is also a power of 2). If this is the case, then
based on degT pMq pvq we can partition T pM q into a logarithmic number (namely nM ` 1) of parts
T p0q pM q, T p1q pM q, . . . such that the required condition is met in each one of them. (In particular, let
piq
piq
T piq pM q satisfy nM|G ď i and nG ď nM ´ i.) Now, the execution of CSMA will split into a logarithmic
number of branches, each of which will continue on a different part of T pM q. For some arbitrarily-fixed
i, let’s track the execution of the i-th branch (i.e. the one on T piq pM q).
• The second rule (30) is another CD-rule: hpN q Ñ hpN |Iq ` hpIq. Similar to above, it will result in the
pjq
partitioning of T pN q into Oplog N q parts T p0q pN q, T p1q pN q, . . . (such that T pjq pN q satisfies nN |I ď j
pjq

and nI ď nN ´ j.) The current i-th branch on T piq pM q will now branch further into Oplog N q
branches corresponding to T p0q pN q, T p1q pN q, . . . Let’s keep track of the j-th branch (on T pjq pN q) for
some arbitrary j.
• The third rule (31) is yet another CD-rule: hpIq Ñ hpI|Dq ` hpDq. It will result in the partitioning
def
of T pIq “ ΠI pT pjq pN qq (where ΠI pT pjq pN qq resulted from the previous CD-step) into Oplog N q parts:
pkq
pkq
T p0q pIq, T p1q pIq, . . . (such that T pkq pIq satisfies nI|D ď k and nD ď nI ´k.) Let’s track the k-th branch
(on T pkq pIq).
• The fourth rule (32) is an SM-rule: hpGq ` hpI|Dq Ñ hpZq. The corresponding algorithmic step is to
join the table T pGq (or more precisely ΠG pT piq pM qq from Step 1) with the table T pIq (or more precisely
T pIq from Step 3) in order to get a relation T pZq. The time required to compute this join is bounded
by the size of T pGq times the maximum degree of D in T pIq. Depending on the current execution
branch pi, j, kq, this time might or might not exceed our budget of 2OPT “ N 3{2 . For example, in
the branch where both i and j are maximal, we will have |T pGq| ď 1 and |T pIq| ď 1, hence the join
takes Op1q time. On the other hand, in the branch where i “ j “ 0 and k is maximal, each one of
|T pGq|, |T pIq|, and the maximum degree of D in T pIq could be as large as N , hence the join could take
time OpN 2 q. Luckily, Lemma 5.36 below implies that “when one door closes, another one opens”: In
37

those particular branches where the join cannot be computed within our time budget, there are extra
constraints that if considered in the CLLP they would reduce the optimal objective value OPT. For
example, in the branch where i “ j “ 0 and k is maximal, the value of D is already fixed. This is
because the degree of D in table T pIq is maximal, hence it is equal to |T pIq|.
• The remaining rules (33). . . (36) are similar to the previous ones.
5.3.4

Analysis of CSMA

Lemma 5.35. Let X ≺ Y be in the lattice L. Let T pY q be a table with log2 |T | ď nY . Then, T can be
pjq
pjq
partitioned into at most ℓ “ 2 log N sub-tables T p1q , . . . , T pℓq such that nY |X ` nX ď nY , for all j P rℓs,
where
pjq

nY |X

def

pjq

def

nX

“

“

max

vPΠX pT pjq q

log2 degT pjq pvq

log2 |ΠX pT pjq q|.

Proof. To obtain the copies T pjq , observe that the number of elements v P ΠX pT q with log-degree in the
interval rj, j`1q is at most |T |{2j ď 2nY ´j . Hence, if we partition T based on which of the buckets rj, j`1q the
pjq
pjq
log-degree falls into, we would almost have the required inequality: nY |X ` nX ď pj ` 1q` pnY ´ jq “ nY ` 1.
To resolve the situation, we partition each T pjq into two equal-sized tables. Overall, we need ℓ “ 2 log N .
Lemma 5.36. Given a CLLP whose
optimal objective value is OPT, and a feasible dual solution pc, s, mq
P
whose objective value is OBJ “ pX̄,Ȳ qPP cȲ |X̄ nȲ |X̄ , let cY ą 0 for some p0̂, Y q P P.
• If nY ą OBJ, then OPT ă OBJ.

• Given θ ě 0, 0 ă ǫ ă 1, ǫ ď cY , if nY ą OBJ ` θ, then OPT ă OBJ ´

ǫθ
1´ǫ .

Proof. Let pc1 , s, m1 q be a dual solution obtained by setting c1Y “ cY ´ ǫ, m1Y,1̂ “ mY,1̂ ` ǫ and keeping other
c1 and m1 values identical to their c and m counterparts. pc1 , s, m1 q is not necessarily feasible. However, it
satisfies netflowp1̂q ě 1 ´ ǫ and netflowpZq ě 0 for all Z P L ´ {1̂, 0̂}. Let pc2 , s2 , m2 q be a dual solution
1
. Now pc2 , s2 , m2 q is indeed feasible. Let OBJ2 be its objective
obtained by multiplying pc1 , s, m1 q by 1´ǫ
2
value. Because it is dual feasible, OBJ ě OPT.
OBJ2

“

X

c2Ȳ |X̄ nȲ |X̄

pX̄,Ȳ qPP

“

X

c1Ȳ |X̄

pX̄,Ȳ qPP

“
ă
“

1
1´ǫ

1´ǫ
X

pX̄,Ȳ qPP

nȲ |X̄
cȲ |X̄ nȲ |X̄ ´

ǫ
nY
1´ǫ

ǫ
1
OBJ ´
pOBJ ` θq
1´ǫ
1´ǫ
ǫθ
OBJ ´
.
1´ǫ

38

All lattices
Normal lattices

Distributive
Lattices

Lattices
with tight
chain bound

Lattices
with tight
SM bound

Simple FDs
Boolean Algebra
i.e. no FD

Figure 10: A summary of the lattices discussed in this paper
Theorem 5.37. CSMA runs in time OpN ` plog N qe 2OPT q, where OPT is the optimal objective value for
CLLPp0q , N is the input size, and e is a data-independent constant.
Proof. Since the number of CSM rules is at most |L|2 (these are rules with multiplicities), so no rule is
repeated. The worst case is obtained when the algorithm branches as far as possible only to have to reduce
θ
the objective by ǫ “ D´1
at the very end and all leaf nodes of the execution tree have to be started afresh
with the new optimal value. Let x “ 2OPT and T pxq denote the runtime of the algorithm on the CLLPp0q
with objective value OPT. Then, the recurrence for the runtime is


2
2
θ
T pxq “ pℓq|L| T 2OPT´ D´1 ` ℓ|L| 2θ x


2
2
x
“ pℓq|L| T
` ℓ|L| 2θ x
θ{pD´1q
2
2

To get the exponential decay effect we set θ so that 2θ{pD´1q “ 2ℓ|L| , which means θ “ pD ´ 1qp|L|2 log2 ℓ `
1q.

6

Conclusions

We studied ways to prove worst-case output size bounds, and algorithms meeting the bounds for join queries
with functional dependencies. A main aim was to design an algorithm running within time bounded by the
entropy-based linear program proposed by Gottlob et al. [11]. For this purpose we developed new, lattice
theoretic techniques, of independent interest. We described several classes of lattices, and several ways to
prove upper or lower bounds on the worst-case query output, summarized in Fig. 10. On the algorithmic
side, we devised the novel idea of turning a proof of an inequality into an algorithm. Three proof techniques
lead to three different algorithms with increasing complexity. Our main algorithm does meet GLVV bound,
up to a poly-log factor. The algorithm manages to solve a stronger problem, where input relations have
prescribed maximum degree bounds, of which functional dependencies and cardinality bounds are special
cases.
39

References
[1] Aberger, C. R., Nötzli, A., Olukotun, K., and Ré, C. Emptyheaded: Boolean algebra based
graph processing. CoRR abs/1503.02368 (2015).
[2] Aref, M., ten Cate, B., Green, T. J., Kimelfeld, B., Olteanu, D., Pasalic, E., Veldhuizen,
T. L., and Washburn, G. Design and implementation of the logicblox system. In Proceedings of the
2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia,
May 31 - June 4, 2015 (2015), T. K. Sellis, S. B. Davidson, and Z. G. Ives, Eds., ACM, pp. 1371–1382.
[3] Atserias, A., Grohe, M., and Marx, D. Size bounds and query plans for relational joins. In
49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008,
Philadelphia, PA, USA (2008), pp. 739–748.
[4] Balister, P., and Bollobás, B. Projections, entropy and sumsets. Combinatorica 32, 2 (2012),
125–141.
[5] Benedikt, M., Leblay, J., and Tsamoura, E. Querying with access patterns and integrity constraints. PVLDB 8, 6 (2015), 690–701.
[6] Boyd, S., and Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004.
[7] Chu, S., Balazinska, M., and Suciu, D. From theory to practice: Efficient join query evaluation
in a parallel database system. In Proceedings of the 2015 ACM SIGMOD International Conference on
Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015 (2015), pp. 63–78.
[8] Chung, F. R. K., Graham, R. L., Frankl, P., and Shearer, J. B. Some intersection theorems
for ordered sets and graphs. J. Combin. Theory Ser. A 43, 1 (1986), 23–37.
[9] Demetrovics, J., Libkin, L., and Muchnik, I. B. Functional dependencies in relational databases:
A lattice point of view. Discrete Applied Mathematics 40, 2 (1992), 155–185.
[10] Gogacz, T., and Toruńczyk, S. Entropy bounds for conjunctive queries with functional dependencies. CoRR abs/1512.01808 (2015).
[11] Gottlob, G., Lee, S. T., Valiant, G., and Valiant, P. Size and treewidth bounds for conjunctive
queries. J. ACM 59, 3 (2012), 16.
[12] Grohe, M. Bounds and algorithms for joins via fractional edge covers. In In Search of Elegance in the
Theory and Practice of Computation. Springer Berlin Heidelberg, 2013, pp. 321–338.
[13] Grohe, M., and Marx, D. Constraint solving via fractional edge covers. In SODA (2006), ACM
Press, pp. 289–298.
[14] Harremoës, P. Functional dependences and Bayesian networks. In Proceedings WITMSE 2011
(Helsinki, 2011).
[15] Joglekar, M., and Ré, C. It’s all a matter of degree: Using degree information to optimize multiway
joins. CoRR abs/1508.01239 (2015).
[16] Levene, M. A lattice view of functional dependencies in incomplete relations. Acta Cybern. 12, 2
(1995), 181–207.
[17] Marx, D. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM
60, 6 (2013), Art. 42, 51.
[18] Ngo, H. Q., Porat, E., Ré, C., and Rudra, A. Worst-case optimal join algorithms: [extended
abstract]. In PODS (2012), pp. 37–48.
40

[19] Ngo, H. Q., Ré, C., and Rudra, A. Skew strikes back: new developments in the theory of join
algorithms. SIGMOD Record 42, 4 (2013), 5–16.
[20] Radhakrishnan, J. 6. entropy and counting. Computational Mathematics, Modelling and Algorithms
(2003), 146.
[21] Schrijver, A. Combinatorial optimization. Polyhedra and efficiency. Vol. B, vol. 24 of Algorithms and
Combinatorics. Springer-Verlag, Berlin, 2003. Matroids, trees, stable sets, Chapters 39–69.
[22] Stanley, R. P. Enumerative combinatorics. Volume 1, second ed., vol. 49 of Cambridge Studies in
Advanced Mathematics. Cambridge University Press, Cambridge, 2012.
[23] Veldhuizen, T. L. Triejoin: A simple, worst-case optimal join algorithm. In Proc. 17th International
Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014. (2014), N. Schweikardt,
V. Christophides, and V. Leroy, Eds., OpenProceedings.org, pp. 96–106.
[24] Yeung, R. W. Information Theory and Network Coding, 1 ed. Springer Publishing Company, Incorporated, 2008.
[25] Zhang, Z., and Yeung, R. W. On characterization of entropy function via information inequalities.
IEEE Transactions on Information Theory 44, 4 (1998), 1440–1452.

A

Additional Material for Sec 1

We show that the query shown in (2) has output size bounded by OpN 3{2 , N d1 , N d2 q. W.L.O.G we may
allow an outgoing edge to be colored with more than one color, i.e. the FD xy Ñ c1 is not required. This is
because the largest output is obtained when the number of pairs px, yq in R is maximized, while |R| ď N ,
and this happens when each edge has only one color. The bound follows easily because
hpzxq ` hpc1 q ě hppzxc1 q` q “ hpxyzc1 c2 q.

B

Additional Material for Sec 3

The following proposition can be found in [21], pp. 774; we reproduce it here for completeness.
Proposition B.1 (Lovasz’s monotonization). Let L “ pL, q be a lattice, and h be a non-negative submodular function on the lattice. Define h̄ : L Ñ R by
(
0
X “ 0̂
h̄pXq “
minY :XY hpY q X ‰ 0̂
Then, h̄ is a polymatroid where h̄p1̂q “ hp1̂q and @X, h̄pXq ď hpXq.
Proof. We verify the only non-trivial property, that h̄ is sub-modular. Fix X ­ž Y , and let X̄ “ argminZ:XZ hpZq
and Ȳ “ argminZ:Y Z hpZq. Noting that X _ Y  X̄ _ Ȳ and X ^ Y  X̄ ^ Ȳ , we have
h̄pXq ` h̄pY q

“ hpX̄q ` hpȲ q
ě hpX̄ ^ Ȳ q ` hpX̄ _ Ȳ q
ě h̄pX ^ Y q ` h̄pX _ Y q.

41

