arXiv:1803.09930v1 [cs.DB] 27 Mar 2018

Worst-Case Optimal Join Algorithms:
Techniques, Results, and Open Problems
Hung Q. Ngo
RelationalAI, Inc.

Abstract. Worst-case optimal join algorithms are the class of join algorithms whose runtime match the
worst-case output size of a given join query. While the first provably worse-case optimal join algorithm was
discovered relatively recently, the techniques and results surrounding these algorithms grow out of decades
of research from a wide range of areas, intimately connecting graph theory, algorithms, information theory,
constraint satisfaction, database theory, and geometric inequalities. These ideas are not just paperware: in
addition to academic project implementations, two variations of such algorithms are the work-horse join
algorithms of commercial database and data analytics engines.
This paper aims to be a brief introduction to the design and analysis of worst-case optimal join algorithms. We discuss the key techniques for proving runtime and output size bounds. We particularly focus
on the fascinating connection between join algorithms and information theoretic inequalities, and the idea of
how one can turn a proof into an algorithm. Finally, we conclude with a representative list of fundamental
open problems in this area.

1. Introduction
1.1. Overview. Relational database query evaluation is one of the most well-studied problems in computer science. Theoretically, even special cases of the problem are already equivalent to fundamental problems
in other areas; for example, queries on one edge relation can already express various graph problems, conjunctive query evaluation is deeply rooted in finite model theory and constraint satisfaction [18, 23, 43, 57, 66],
and the aggregation version is inference in discrete graphical models [5]. Practically, relational database
management systems (RDBMS) are ubiquitous and commercially very successful, with almost 50 years of
finely-tuned query evaluation algorithms and heuristics [13, 31, 62].
In the last decade or so there have emerged fundamentally new ideas on the three key problems of a
relational database engine: (1) constructing query plans, (2) bounding intermediate or output size, and (3)
evaluating (intermediate) queries. The new query plans are based on variable elimination and equivalently
tree decompositions [5, 6, 29]. The new (tight) size bounds are information-theoretic, taking into account in
a principled way input statistics and functional dependencies [7, 8, 12, 30, 32]. The new algorithms evaluate
the multiway join operator in a worst-case optimal manner [7,8,51,52,67], which is provably asymptotically
better than the one-pair-at-a-time join paradigm.
These fresh developments are exciting both from the theory and from the practical stand point. On
the theory side, these results demonstrate beautiful synergy and interplay of ideas from many different research areas: algorithms, extremal combinatorics, parameterized complexity, information theory, databases,
machine learning, and constraint satisfaction. We will briefly mention some of these connections in Sec. 1.2
below. On the practice side, these results offer their assistance “just in time” for the ever demanding modern
data analytics workloads. The generality and asymptotic complexity advantage of these algorithms open
wider the pandora box of true “in-database” graph processing, machine learning, large-scale inference, and
constraint solving [2, 3, 11, 22, 25, 34, 36, 45, 50, 54, 55, 60].
The reader is referred to [5, 6] for descriptions of the generality of the types of queries the new style
of query plans can help answer. In particular, one should keep in mind that the bounds and algorithms
1

described in this paper apply to aggregate queries in a very general setting, of which conjunctive queries
form a special case. The focus of this paper is on the other two developments: output size bounds and
worst-case optimal join (WCOJ) algorithms.
Roughly speaking, a WCOJ algorithm is a join algorithm evaluating a full conjunctive query in time
that is proportional to the worst-case output size of the query. More precisely, we are given a query Q along
with a set DC of “constraints” the input database D is promised to satisfy. The simplest form of constraints
contain the sizes of input relations; these are called cardinality constraints. The second form of constraints
is prevalent in RDBMSs, that of functional dependencies (FD). We shall refer to them as FD constraints.
These constraints say that, if we fix the bindings of a set X of variables, then there is at most one binding for
every variable in another set Y . More generally, there are degree constraints, which guarantee that for any
fixed binding of variables in X, there are at most some given number of bindings of variables in Y . Degree
constraints generalize both cardinality and FD constraints, because cardinality constraints correspond to
degree constraints when X = ∅.
We write D |= DC to denote the fact that the database D satisfies the degree constraints DC. The
worst-case output size problem is to determine the quantity
(1)

sup |Q(D)|

(worst-case output size)

D|=DC

and a WCOJ algorithm runs in time Õ(|D| + supD|=DC |Q(D)|), where Õ hides a log factor in the data size
and some query-size dependent factor. In what follows we present a brief overview of the history of results
on determining (1) and on associated WCOJ algorithms.
Independent of WCOJ algorithms, the role of bounding and estimating the output size in query optimizer
is of great importance, as estimation errors propagate and sometimes are as good as random guesses, leading
to bad query plans [39]. Hence, as we enrich the class of constraints allowable in the DC set (say from upper
degree bounds to histogram information or more generally various statistical properties of the input), one
should expect the problem of determining (1) or its expectation to gain more prominence in any RDBMS.
The role of determining and computing (1) in the design of WCOJ algorithms, on the other hand, has
a fascinating and different bent: we can turn a mathematical proof of a bound for (1) into an algorithm;
different proof strategies yield different classes of algorithms with their own pros and cons. Deriving the
bound is not only important for analyzing the runtime of the algorithm, but also instrumental in how one
thinks about designing the algorithm in the first place. Another significant role that the problem (1) plays
is in its deep connection with information theory and (abstract algebraic) group theory. This paper aims to
be a guided tour of these connections.
The notion of worst-case optimality has influenced a couple of other lines of inquiries, in parallel query
processing [42,44], and join processing in the IO model [37]. Furthermore, more than just paperware, WCOJ
algorithms have found their way to academic data management and analytic systems [1, 10, 19, 41, 56], and
are part of two commercial data analytic engines at LogicBlox [11] and RelationalAI.
The author is deeply indebted to Mahmoud Abo Khamis and Dan Suciu, whose insights, enthusiasm,
and collaborative effort (both on [7, 8] and off official publication records) in the past few years have helped
form the skeleton of the story that this article is attempting to tell. The technical landscape has evolved
drastically from an early exposition on the topic [52].
1.2. A brief history of bounds and algorithms. We start our history tour with the bound (1) in
the simple setting when all constraints in DC are cardinality constraints. Consider, for example, the following
“triangle query”:
(2)

Q△ (A, B, C) ← R(A, B), S(B, C), T (A, C),

While simple, this is not a toy query. In social network analysis, counting and enumerating the number of
triangles in a large graph G = (V, E) is an important problem, which corresponds to (2) with R = S = T = E.
There is a large literature on trying to speed up this one query; see, e.g. [15, 64, 65] and references thereof.
One way to think about the output size bound is to think of Q△ as containing points (a, b, c) in a
three-dimensional space, whose projection onto the (A, B)-plane is contained in R, onto the (B, C) plane
is contained in S, and onto the (A, C)-plane is contained in T . There is a known geometric inequality
shown by Loomis and Whitney in 1949 [46] which addresses a more general problem: bound the volume
2

of a convex body in space whose shadows on the coordinate hyperplanes have bounded areas. The triangle
query above corresponds to the discrete measure
p case, where “volume” becomes “count”. Specializing to the
triangle, Loomis-Whitney states that |Q△ | ≤ |R| · |S| · |T |. Thus, while studied in a completely different
context, Loomis-Whitney’s inequality is our earliest known answer to determining (1) for a special class of
join queries. In [51, 52], we referred to these as the Loomis-Whitney queries: those are queries where every
input atom contains all but one variable.
In a different context, in 1981 Noga Alon [9] studied the problem (1) in the case where we want to
determine the maximum number of occurrences of a given subgraph H in a large graph G. (H is the query’s
body, and G is the database.) Alon’s interest was to determine the asymptotic behavior of this count, but
his formula was also asymptotically tight. In the triangle case, for example, Alon’s bound is Θ(N 3/2 ), the
∗
same as that of Loomis-Whitney. Here, N is the number of edges in G. Alon’s general bound is Θ(N ρ (H) ),
∗
where ρ denote the “fractional edge cover number” of H (see Section 3). However, his results were not
formulated in this more modern language.
A paper by Chung et al. [20] on extremal set theory was especially influential in our story. The paper
proved the “Product Theorem” which uses the entropy argument connecting a count estimation problem to
an entropic inequality. We will see this argument in action in Section 4. The Product theorem is proved
using what is now known as Shearer’s lemma; a clean formulation and a nice proof of this lemma was given
by Radhakrishnan [58].
In 1995, Bollobás and Thomason [16] proved a vast generalization of Loomis-Whitney’s result. Their
bound, when specialized down to the discrete measure and our problem, implies what is now known as the
AGM-bound (see below and Corollary 4.2). The equivalence was shown in Ngo et al. [51]. The key influence
of Bollobás-Thomason’s result to our story was not the bound, which can be obtained through Shearer’s
lemma already, but the inductive proof based on Hölder’s inequality. Their inductive proof suggests a natural
recursive algorithm and its analysis, which lead to the algorithms in [51, 52].
Independently, in 1996 Friedgut and Kahn [27] generalized Alon’s earlier result from graphs to hypergraphs, showing that the maximum number of copies of a hypergraph H inside another hypergraph G is
∗
Θ(N ρ (H) ). Their argument uses the product theorem from Chung et al. [20]. The entropic argument was
used in Friedgut’s 2004 paper [26] to prove a beautiful inequality, which we shall call Friedgut’s inequality.
In Theorem 4.1 we present an essentially equivalent version of Friedgut’s inequality formulated in a more
database-friendly way, and prove it using the inductive argument from Bollobás-Thomason. Friedgut’s inequality not only implies the AGM-bound as a special case, but also can be used in analyzing the backtracking
search algorithm presented in Section 5. Theorem 4.1 was stated and used in Beame et al. [14] to analyze
parallel query processing; Friedgut’s inequality is starting to take roots in database theory.
Grohe and Marx ( [32,33], 2006) were pushing boundaries on the parameterized complexity of constraint
satisfaction problems. One question they considered was to determine the maximum possible number of
solutions of a sub-problem defined within a bag of a tree decomposition, given that the input constraints
were presented in the listing representation. This is exactly our problem (1) above, and they proved the
∗
bound of O(N ρ (Q) ) using Shearer’s lemma, where ρ∗ (Q) denote the fractional edge cover number of the
∗
hypergraph of the query. They also presented a join-project query plan running in time O(N ρ (Q)+1 ), which
is almost worst-case optimal.
Atserias et al. ( [12], 2008) applied the same argument to conjunctive queries showing what is now known
as the AGM-bound. More importantly, they proved that the bound is asymptotically tight and studied the
average-case output size. The other interesting result from [12] was from the algorithmic side. They showed
that there is class of queries Q for which a join-project plan evaluates them in time O(N 3 ) while any join-only
plan requires Ω(N Ω(log k) ), where k is the query size. In particular, join-project plans are strictly better than
join-only plans.
Continuing with this line of investigation, Ngo et al. (2012, [51]) presented the NPRR algorithm running
∗
in time Õ(N ρ (Q) ), and presented a class of queries for which any join-project plan is worse by a factor of
1−1/k
Ω(N
) where k is the query size. The class of queries contains the Loomis-Whitney queries. The NPRR
algorithm and its analysis were overly complicated. Upon learning about this result, Todd Veldhuizen of
LogicBlox realized that his Leapfrog-Triejoin algorithm (LFTJ) can also achieve the same runtime, with a
simpler proof. LFTJ is the work-horse join algorithm for the LogicBlox’s datalog engine, and was already
implemented since about 2009. Veldhuizen published his findings in 2014 [67]. Inspired by LFTJ and its
3

simplicity, Ngo et al. [52] presented a simple recursive algorithm called Generic-Join which also has a compact
analysis.
The next set of results extend DC to more than just cardinality constraints. Gottlob et al. [30] extended
the AGM bound to handle FD constraints, using the entropy argument. They also proved that the bound
is tight if all FD’s are simple FDs. Abo Khamis et al. [7] observed that the same argument generalizes the
bound to general degree constraints, and addressed the corresponding algorithmic question. The bound was
studied under the FD-closure lattice formalism, where they showed that the bound is tight if the lattice is
a distributive lattice. This result is a generalization of Gottlob et al.’s result on the tightness of the bound
under simple FDs. The connection to information theoretic inequalities and the idea of turning an inequality
proof into an algorithm was also developed with the CSMA algorithm in [7]. However, the algorithm was
also too complicated, whose analysis was a little twisted at places.
Finally, in [8] we developed a new collection of bounds and proved their tightness and looseness for
disjunctive datalog rules, a generalization of conjunctive queries. It turns out that under general degree
constraints there are two natural classes of bounds for the quantity (1): the entropic bounds are tight but we
do not know how to compute them, and the relaxed versions called polymatroid bounds are computable via
a linear program. When there is only cardinality constraints, these two bounds collapse into one (the AGM
bound). We discuss some of these results in Section 4. The idea of reasoning about algorithms’ runtimes
using Shannon-type inequalities was also developed to a much more mature and more elegant degree, with
an accompanying algorithm called PANDA. We discuss what PANDA achieves in more details in Section 5.
1.3. Organization. The rest of the paper is organized as follows. Section 2 gently introduces two ways
of bounding the output size and two corresponding algorithms using the triangle query. Section 3 presents
notations, terminology, and a brief background materials on information theory and properties of the entropy
functions. Section 4 describes two bounds and two methods for proving output size bounds on a query given
degree constraints. This section contains some proofs and observations that have not appeared elsewhere.
Section 5 presents two algorithms evolving naturally from the two bound-proving strategies presented earlier.
Finally, Section 6 lists selected open problems arising from the topics discussed in the paper.
2. The triangle query
The simplest non-trivial example illustrating the power of WCOJ algorithms is the triangle query (2).
We use this example to illustrate several ideas: the entropy argument, two ways of proving an output size
bound, and how to derive algorithms from them. The main objective of this section is to gently illustrate
some of the main reasoning techniques involved in deriving the bound and the algorithm; we purposefully
do not present the most compact proofs. At the end of the section, we raise natural questions regarding the
assumptions made on the bound and algorithm to motivate the more general problem formulation discussed
in the rest of the paper.
The bound. Let Dom(X) denote the domain of attribute X ∈ {A, B, C}. Construct a distribution on
Dom(A) × Dom(B) × Dom(C) where a triple (a, b, c) is selected from the output Q△ uniformly. Let H denote
the entropy function of this distribution, namely for any X ⊆ {A, B, C}, H[X] denotes the entropy of the
marginal distribution on the variables X. Then, the following hold:
H[A, B, C] = log2 |Q△ |,

(due to uniformity)

H[A, B] ≤ log2 |R|,
H[B, C] ≤ log2 |S|,
H[A, C] ≤ log2 |T |.
The first inequality holds because the support of the marginal distribution on Dom(A)×Dom(B) is a subset of
R(A, B), and the entropy is bounded by the log2 of the support (see Section 3.2). The other two inequalities
hold for the same reason. Hence, whenever there are coefficients α, β, γ ≥ 0 for which
(3)

H[A, B, C] ≤ αH[A, B] + βH[B, C] + γH[A, C]

holds for all entropy functions H, we can derive an output size bound for the triangle query:
(4)

|Q△ | ≤ |R|α · |S|β · |T |γ .
4

In Section 4 we will show that (3) holds for all entropy function H if and only if α + β ≥ 1, β + γ ≥ 1,
and α + γ ≥ 1, for non-negative α, β, γ. This fact is known as Shearer’s inequality, though Shearer’s original
statement is weaker than what was just stated.
One consequence of Shearer’s inequality is that, to obtain the best possible bound, we will want to
minimize the right-hand-side (RHS) of (4) subject to the above constraints:
(5)

log2 |Q△ | ≤ min α log2 |R| + β log2 |S| + γ log2 |T |

(6)

s.t. α + β ≥ 1,

(7)

α + γ ≥ 1,

(8)

β + γ ≥ 1,

(9)

α, β, γ ≥ 0.

This bound is known as the AGM-bound for Q△ . It is a direct consequence of Friedgut’s inequality (Theorem 4.1).
Algorithms. Let N = max{|R|, |S|, |T |}, and (α∗ , β ∗ , γ ∗ ) denote an optimal solution to the LP (5) above.
∗
∗
∗
A WCOJ algorithm needs to be able to answer Q△ in time Õ(N + |R|α |S|β |T |γ ), where Õ hides a single
log N factor. The feasible region of (5) is a 3-dimensional simplex. Without loss of generality, we can
assume that (α∗ , β ∗ , γ ∗ ) is one of the 4 vertices of the simplex, which are (1, 1, 0), (1, 0, 1), (0, 1, 1), and
(.5, .5, .5). If (α∗ , β ∗ , γ ∗ ) = (1, 1, 0), then the traditional join plan (R ✶ S) ✶ T has the desired runtime of
∗
∗
∗
Õ(|R| · |S|) = Õ(|R|α |S|β |T |γ ), modulo Õ(N ) preprocessing time.
Consequently, the only interesting case is when (α∗ , β ∗ , γ ∗ ) = (.5, .5, .5). It is easy to see that this is
from R, S, and T is greater than the size
optimal to LP (5) when the product of sizes of any two relations p
of the third relation. To design an algorithm running in Õ(N + |R| · |S| · |T |)-time, we draw inspiration
from two different proofs of the bound (5).
First Algorithm. Write 1E to denote the indicator variable for the Boolean event E; for example 1R(a,b)
is 1 if (a, b) ∈ R and 0 otherwise. Let σ denote the relational selection operator. The Bollobás-Thomason’s
argument for proving (5) goes as follows.
XXX
|Q△ | =
(10)
1R(a,b) 1S(b,c) 1T (a,c)
a

(11)

=

≤

c

1R(a,b)

XX

1R(a,b)

a

(12)

b

XX
a

1S(b,c) 1T (a,c)

c

b

sX
c

b

XX

X

1S(b,c) ·

sX

1T (a,c)

c

p
p
|σB=b S| · |σA=a T |

(13)

=

(14)

X
Xp
p
|σA=a T |
1R(a,b) · |σB=b S|
=

a

1R(a,b)

b

a

(15)

b

sX
sX
Xp
≤
|σA=a T |
1R(a,b) ·
|σB=b S|
a

(16)

b

b

Xp
p
p
|σA=a T | |σA=a R| |S|
=
a

(17)

Xp
p
p
= |S| ·
|σA=a T | |σA=a R|
a

(18)

p
≤ |R| · |S| · |T |.

All three inequalities follow from Cauchy-Schwarz. Tracing the inequalities back to |Q△ |, Algorithm 1
emerges. The analysis is based on only a single assumption, that we can loop through the intersection of
two sets X and Y in time bounded by Õ(min{|X|, |Y |}). This property can be satisfied with sort-merge or
simple hash join when we iterate through the smaller of the two sets and look up in the hash table of the
5

Algorithm 1: based on Hölder’s inequality proof
for a ∈ πA R ∩ πA T do
for b ∈ πB σA=a R ∩ πB S do
for c ∈ πC σB=b S ∩ πC σA=a T do
Report (a, b, c);
end
end
end
Algorithm 2: based on entropy inequality proof
q
θ ← |R|·|S|
|T | ;

Rheavy ← {(a, b) ∈ R : |σA=a R| > θ};
Rlight ← {(a, b) ∈ R : |σA=a R| ≤ θ};
return [(Rheavy ✶ S) ⋉ T ] ∪ [(Rlight ✶ T ) ⋉ S];

other. For a fixed binding (a, b), the inner-most loop runs in time
p
min {|πC σB=b S|, |πC σA=a T |} ≤ |σB=b S| · |σA=a T |.

A binding (a, b) gets in the inner loop only if (a, b) ∈ R, and so the total amount of work is
!
XX
p
(19)
Õ
1R(a,b) |σB=b S| · |σA=a T | .
a

b

Compare this with (13), and the runtime analysis is completed.
Second Algorithm. This algorithm is inspired by a proof of inequality (3), which implies (5). In this
particular case (3) can be written as

(20)

2H[A, B, C] ≤ H[A, B] + H[B, C] + H[A, C].

Using the chain rule (eq. (29)) and the submodularity rule (eq. (33)) for entropic functions, the inequality
can be proved as follows.
(21)

H[A, B] + H[B, C] + H[A, C] = H[A] + H[B | A] + H[B, C] + H[A, C]

(22)

= (H[A] + H[B, C]) + (H[B | A] + H[A, C])

(23)

≥ (H[A | B, C] + H[B, C]) + (H[B | A, C] + H[A, C])

(24)

= 2H[A, B, C].

The first replacement H[A, B] → H[A] + H[B | A] is interpreted as a decomposition of the relation R(A, B)
into two parts “heavy” and “light”. After applying submodularity, two compositions are performed to obtain
two copies of H[A, B, C]: H[A | B, C] + H[B, C] → H[A, B, C] and H[B | A, C] + H[A, C] → H[A, B, C].
These correspond to join operators. Algorithm 2 has the pseudo-code. It is remarkable how closely the
algorithm mimics the entropy proof.
The analysis is also compact. Note that |Rheavy | ≤ |R|/θ and thus
|R| · |S| p
|Rheavy ✶ S| ≤
= |R| · |S| · |T |.
θ
p
In the other case, |Rlight ✶ T | ≤ |T | · θ = |R| · |S| · |T |. This completes the analysis.
Follow-up questions. In a more realistic setting, we know more about the input than just the cardinalities.
In a database there may (and will) be FDs. In a graph we may know the maximum degree of a vertex. How
do the bounds and algorithms change when we take such information into account? Which of the above two
bounds and algorithms generalize better in the vastly more general setting? We explore these questions in
the remainder of this paper.
6

3. Preliminaries
Throughout the paper, we use the following convention. The non-negative reals, rationals, and integers
are denoted by R+ , Q+ , and N respectively. For a positive integer n, [n] denotes the set {1, . . . , n}.
Functions log without a base specified are base-2, i.e. log = log2 . Uppercase Ai denotes a variable/attribute, and lowercase ai denotes a value in Q
the discrete domain Dom(Ai ) of the variable. For any
subset S ⊆ [n], define AS = (Ai )i∈S , aS = (ai )i∈S ∈ i∈S Dom(Ai ). In particular, AS is a tuple of variables
and aS is a tuple of specific values with support S. We also use XS to denote variables and xS , tS to denote
value tuples in the same way.
3.1. Queries and degree constraints. A multi-hypergraph is a hypergraph where edges may occur
more than once. We associate a full conjunctive query Q to a multi-hypergraph H := ([n], E), E ⊆ 2[n] ; the
query is written as
^
(25)
Q(A[n] ) ←
RF (AF ),
F ∈E

with variables Ai , i ∈ [n], and atoms RF , F ∈ E.
Definition 1 (Degree constraint). A degree constraint is a triple (X, Y, NY |X ), where X ( Y ⊆ [n] and
NY |X ∈ N. The relation RF is said to guard the degree constraint (X, Y, NY |X ) if Y ⊆ F and
(26)

degF (AY |AX ) := max |ΠAY (σAX =t (RF ))| ≤ NY |X .
t

Note that a given relation may guard multiple degree constraints. Let DC denote a set of degree constraints.
The input database D is said to satisfy DC if every constraint in DC has a guard, in which case we write
D |= DC.
A cardinality constraint is an assertion of the form |RF | ≤ NF , for some F ∈ E; it is exactly the degree
constraint (∅, F, NF |∅ ) guarded by RF . A functional dependency AX → AY is a degree constraint with
NX∪Y |X = 1. In particular, degree constraints strictly generalize both cardinality constraints and FDs.
Our problem setting is general, where we are given a query of the form (25) and a set DC of degree
constraints satisfied by the input database D. The first task is to find a good upper bound, or determine
exactly the quantity supD|=DC |Q(D)|, the worst-case output size of the query given that the input satisfies
the degree constraints. The second task is to design an algorithm running in time as close to the bound as
possible.
Given a multi-hypergraph H = ([n], E), define its corresponding “fractional edge cover polytope”:
(
)
X
FECP(H) := δ = (δF )F ∈E | δ ≥ 0 ∧
δF ≥ 1, ∀v ∈ [n] .
F :v∈F

Every point δ ∈ FECP(H) is called a fractional edge cover of H. The quantity
(
)
X
ρ∗ (H) := min
δF | δ ∈ FECP(H)
F ∈E

is called the fractional edge cover number of H.

3.2. Information theory. The books [21, 68] are good references on information theory. We extract
only simple facts needed for this paper. Consider a joint probability distribution D on n discrete variables
A = (Ai )i∈[n] and a probability mass function P. The entropy function associated with D is a function
H : 2A → R+ , where
X
1
P[AF = aF ] log
(27)
H[AF ] :=
P[A
Q
F = aF ]
aF ∈

i∈F

Dom(Ai )

is the entropy of the marginal distribution on AF . To simplify notations, we will also write H[F ] for H[AF ],
turning H into a set function H : 2[n] → R+ . For any F ⊆ [n], define the “support” of the marginal
7

distribution on AF to be
(28)

suppF (D) :=

(

xF ∈

Y

)

Dom(Ai ) | P[AF = xF ] > 0 .

i∈F

Given X ⊆ Y ⊆ [n], define the conditional entropy to be
H[Y | X] := H[Y ] − H[X].

(29)

This is also known as the chain rule of entropy. The following facts are basic and fundamental in information
theory:
(30)

H[∅] = 0

(31)

H[X] ≤ log |suppX (D)|

∀X ⊆ [n]

(32)

H[X] ≤ H[Y ]

∀X ⊆ Y ⊆ [n]

(33)

H[X ∪ Y | Y ] ≤ H[X | X ∩ Y ]

∀X, Y ⊆ [n]

Inequality (31) follows from Jensen’s inequality and the concavity of the entropy function. Equality holds if
and only if the marginal distribution on X is uniform. Entropy measures the “amount of uncertainty” we
have: the more uniform the distribution, the less certain we are about where a random point is in the space.
Inequality (32) is the monotonicity property: adding more variables increases uncertainty. Inequality (33)
is the submodularity property: conditioning on more variables reduces uncertainty.1
V
A function
P f : 2 → R+ is called a (non-negative) set function on V. A set function f on V is modular
if f (S) =
v∈S f ({v}) for all S ⊆ V, is monotone if f (X) ≤ f (Y ) whenever X ⊆ Y , is subadditive if
f (X ∪ Y ) ≤ f (X) + f (Y ) for all X, Y ⊆ V, and is submodular if f (X ∪ Y ) + f (X ∩ Y ) ≤ f (X) + f (Y ) for
all X, Y ⊆ V. Let n be a positive integer. A function h : 2[n] → R+ is said to be entropic if there is a joint
distribution on A[n] with entropy function H such that h(S) = H[S] for all S ⊆ [n]. We will write h(S) and
h(AS ) interchangeably, depending on context.
Unless specified otherwise, we will only consider non-negative and monotone set functions f for which
f (∅) = 0; this assumption will be implicit in the entire paper.
Definition 2. Let Mn , SAn , and Γn denote the set of all (non-negative and monotone) modular,
subadditive, and submodular set functions on V, respectively. Let Γ∗n denote the set of all entropic functions
∗
on n variables, and Γn denote its topological closure. The set Γn is called the set of polymatroidal functions,
or simply polymatroids.
∗

The notations Γn , Γ∗n , Γn are standard in information theory. It is known [68] that Γ∗n is a cone which
∗
is not topologically closed. And hence, when optimizing over this cone we take its topological closure Γn ,
which is convex. The sets Mn and Γn are clearly polyhedral cones.
As mentioned above, entropic functions satisfy non-negativity, monotonicity, and submodularity. Linear
inequalities regarding entropic functions derived from these three properties are called Shannon-type inequalities. For a very long time, it was widely believed that Shannon-type inequalities form a complete set of
∗
linear inequalities satisfied by entropic functions, namely Γn = Γn . This indeed holds for n ≤ 3, for example.
However, in 1998, in a breakthrough paper in information theory, Zhang and Yeung [69] presented a new
∗
inequality which cannot be implied by Shannon-type inequalities. Their result proved that, Γn ( Γn for any
n ≥ 4. Lastly the following chain of inclusion is known [68]
(34)

∗

Mn ⊆ Γ∗n ⊆ Γn ⊆ Γn ⊆ SAn .

When n ≥ 4, all of the containments are strict.
4. Output size bounds
This section addresses the following question: given a query Q and a set of degree constraints DC,
determine supD|=DC |Q(D)| or at least a good upper bound of it.
1H[X | X ∩ Y ] ≥ H[X | (X ∩ Y ) ∪ (Y \ X)] = H[X | Y ] = H[X ∪ Y | Y ].
8

4.1. Cardinality constraints only. Friedgut’s inequality is essentially equivalent to Hölder’s inequality. Following Beame et al. [14], who used the inequality to analyze parallel query processing algorithms,
we present here a version that is more database-friendly. We also present a proof of Friedgut’s inequality
using Hölder’s inequality, applying the same induction strategy used in the proof of Bollobás-Thomason’s
inequality [16] and the “query decomposition lemma” in [52].
Theorem 4.1 (Friedgut [26]). Let Q denote a full conjunctive query with hypergraph H = ([n], E) and
inputQrelations RF , F ∈ E. Let δ = (δF )F ∈E denote a fractional edge cover of H. For each F ∈ E, let
wF : i∈F Dom(Xi ) → R+ denote an arbitrary non-negative weight function. Then, the following holds
X Y

(35)

[wF (aF )]

δF

Y

≤

a∈Q F ∈E

X

F ∈E

!δF

wF (t)

t∈RF

Proof. We induct on n. When n = 1, the inequality is exactly generalized Hölder inequality [35].
Suppose n > 1; define En := {F ∈ E | n ∈ F } and Qn−1 := πX[n−1] Q. We write a ∈ Q as a pair of tuples
a = (a[n−1] , an ) where a[n−1] ∈ Qn−1 and break the sum over a ∈ Q into a double sum:
X Y

a∈Q F ∈E

a[n−1] ∈Qn−1

X

Y

[wF (aF )]δF

Y

X

Y

[wF (aF )]δF

X

Y

δF

≤

F ∈E−En

=

Y

F ∈E

X

[wF (aF )]

X

t∈RF

Y 



Y

F ∈En

!δF

wF (t)

t∈RF



F ∈En

a[n−1] ∈Qn−1 F ∈E−En

Y

[wF (aF )]δF

an :
F ∈En
(a[n−1] ,an )∈Q

a[n−1] ∈Qn−1 F ∈E−En

≤

Y

X

[wF (aF )]δF

a[n−1] ∈Qn−1 F ∈E−En

≤

[wF (aF )]δF

an :
F ∈E
(a[n−1] ,an )∈Q

X

=

Y

(a[n−1] ,an )∈Q F ∈E

X

=

X

[wF (aF )]δF =

Y

·

F ∈En

!δF

X

δF

X

an :
(a[n−1] ,an )∈Q

X


wF (aF )


!δF

wF (t)

t∈RF

!δF

wF (t)

t∈RF

wF (t)

The
P first inequality follows from Hölder’s inequality and the fact that δ is a fractional edge cover; in particular,
F :n∈F δF ≥ 1. The second inequality is due to the fact that πXF Q ⊆ RF , and the third inequality is the
induction hypothesis.

By setting all weight functions to be identically 1, we obtain
Corollary 4.2 (AGM-bound [12]). Given the same setting as that of Theorem 4.1, we have
Y
(36)
|Q| ≤
|RF |δF .
F ∈E

∗

In particular, let N = maxF ∈E |RF | then |Q| ≤ N ρ

(H)
9

.

4.2. General degree constraints. To obtain a bound in the general case, we employ the entropy
argument, which by now is widely used in extremal combinatorics [20, 40, 59]. In fact, Friedgut [26] proved
Theorem 4.1 using an entropy argument too. The particular argument below can be found in the first paper
mentioning Shearer’s inequality [20], and a line of follow-up work [7, 8, 27, 30, 59].
QLet D |= DC be any database instance satisfying the input degree constraints. Construct a distribution D
on i∈[n] Dom(Ai ) by picking uniformly a tuple a[n] from the output Q(D). Let H denote the corresponding
entropy function. Then, due to uniformity we have log2 |Q(D)| = H([n]). Now, consider any degree
constraint (X, Y, NY |X ) ∈ DC guarded by an input relation RF . From (31) it follows that H[Y | X] ≤
log NY |X . Define the collection HDC of set functions satisfying the degree constraints DC:
HDC := {h | h(Y ) − h(X) ≤ log NY |X , ∀(X, Y, NY |X ) ∈ DC}.
Then, the entropy argument immediately gives the following result, first explicitly formulated in [8]:
Theorem 4.3 (From [7, 8]). Let Q be a conjunctive query and DC be a given set of degree constraints,
then for any database D satisfying DC, we have
(37)

log |Q(D)| ≤

max
∗

h([n])

(entropic bound)

max

h([n])

(polymatroid bound)

h∈Γn ∩HDC

≤

(38)

h∈Γn ∩HDC

Furthermore, the entropic bound is asymptotically tight and the polymatroid bound is not.
The polymatroid relaxation follows from the chain of inclusion (34); the relaxation is necessary because
we do not know how to compute the entropic bound. Also from the chain of inclusion, we remark that while
the set SAn is not relevant to our story, we can further move from Γn to SAn and end up with the integral
edge cover number [8].
Table 1, extracted from [8], summarizes our current state of knowledge on the tightness and looseness
of these two bounds. The entropic bound is asymptotically tight, i.e. there are arbitrarily large databases
Bound

Entropic Bound
sup log |Q(D)| ≤

Definition
DC contains only
cardinality constraints
DC contains only
cardinality and FD constraints
DC is a general
set of degree constraints

max
∗

Polymatroid Bound
h([n])

h∈Γn ∩HDC

D|=DC

(See [7, 30])
AGM bound [12, 33]
(Tight [12])
Entropic Bound for FD [30]
(Tight [28])
Entropic Bound for DC [7]
(Tight [8])

sup log |Q(D)| ≤
D|=DC

max

h∈Γn ∩HDC

h([n])

(See [7, 30])
AGM bound [12, 33]
(Tight [12])
Polymatroid Bound for FD [30]
(Not tight [8])
Polymatroid Bound for DC [7]
(Not tight [8])

Table 1. Summary of entropic and polymatroid size bounds for full conjunctive queries
along with their tightness properties.

D |= DC for which log |Q(D)| approaches the entropic bound. The polymatroid bound is not tight, i.e. there
exist a query and degree constraints for which its distance from the entropic bound is arbitrarily large.
The tightness of the entropic bound is proved using a very interesting connection between information
theory and group theory first observed in Chan and Yeung [17]. Basically, given any entropic function
∗
h ∈ Γn ∈ HDC, one can construct a database instance D which satisfies all degree constrains DC and
log |Q(D)| ≥ h([n]). The database instance is constructed from a system of (algebraic) groups derived from
the entropic function.
The looseness of the polymatroid bound follows from Zhang and Yeung result [69] mentioned in Section 3.2. In [8], we exploited Zhang-Yeung non-Shannon-type inequality and constructed a query for which
∗
the optimal polymatroid solution h∗ to problem (38) strictly belongs to Γn − Γn . This particular h∗ proves
the gap between the two bounds, which we can then magnify to an arbitrary degree by scaling up the degree
constraints.
10

In addition to being not tight for general degree constraints, the polymatroid bound has another disadvantage: the linear program (38) has an exponential size in query complexity. While this is “acceptable”
in theory, it is simply not acceptable in practice. Typical OLAP queries we have seen at LogicBlox or
RelationalAI have on average 20 variables; and 220 certainly cannot be considered a “constant” factor, let
alone analytic and machine learning workloads which have hundreds if not thousands of variables. We next
present a sufficient condition allowing for the polymatroid bound to not only be tight, but also computable
in polynomial time in query complexity.
Definition 3 (Acyclic degree constraints). Associate a directed graph GDC = ([n], E) to the degree
constraints DC by adding to E all directed edges (x, y) ∈ X × (Y − X) for every (X, Y, NY |X ) ∈ DC. If GDC
is acyclic, then DC is said to be acyclic degree constraints, in which case any topological ordering (or linear
ordering) of [n] is said to be compatible with DC. The graph GDC is called the constraint dependency graph
associated with DC.
Note that if there are only cardinality constraints, then GDC is empty and thus DC is acyclic. In
particular, acyclicity of the constraints does not imply acyclicity of the query, and the cardinality constraints
do not affect the acyclicity of the degree constraints. In a typical OLAP query, if in addition to cardinality
constraints we have FD constraints including non-circular key-foreign key lookups, then DC is acyclic. Also,
verifying if DC is acyclic can be done efficiently in poly(n, |DC|)-time.
Proposition 4.4. Let Q be a query with acyclic degree constraints DC; then the following hold:
(39)

max

h∈Mn ∩HDC

h([n]) =

max
∗

h∈Γn ∩HDC

h([n]) =

max

h∈Γn ∩HDC

h([n]).

In particular, the polymatroid bound is tight and computable in poly(n, |DC|)-time.
Proof. Let h∗ denote an optimal solution to the linear program max{h([n]) | h ∈ Γn ∩ HDC}. Because
∗
Mn ⊆ Γn ⊆ Γn , to prove (39) it is sufficient to exhibit a modular function f ∈ Mn ∩ HDC for which
f ([n]) = h∗ ([n]).
Without loss of generality, assume the identity permutation is compatible with DC, i.e. for every
(X, Y, NY |X ) ∈ DC, we have x < y for all x ∈ X and y ∈ Y − X. Define a set function f : 2[n] → R+
as follows:


if S = ∅
0
∗
∗
(40)
f (S) := h ([i]) − h ([i − 1]) if S = {i}, i ∈ [n]

P
if S ⊆ [n], |S| > 1.
i∈S f (i)
The function f is clearly modular because h∗ is monotone. The fact that f ([n]) = h∗ ([n]) follows from
the telescoping sum. It remains to show that f ∈ HDC. We will show by induction on |Y − X| that
f (Y |X) ≤ h∗ (Y |X) for any degree constraint (X, Y, NY |X ) ∈ DC. The base case when Y = X holds
trivially. Let (X, Y, NY |X ) be any degree constraint in DC where |Y − X| > 0. Let j be the largest integer
in Y − X. We have
(41)

f (Y | X) = h∗ ([j] | [j − 1]) + f (Y − {j} | X)

(42)

≤ h∗ ([j] | [j − 1]) + h∗ (Y − {j} | X)

(43)

= h∗ ([j − 1] ∪ Y | [j − 1]) + h∗ (Y − {j} | X)

(44)

≤ h∗ (Y | Y ∩ [j − 1]) + h∗ (Y − {j} | X)

(45)

= h∗ (Y | Y − {j}) + h∗ (Y − {j} | X)

(46)

= h∗ (Y | X)

(47)

≤ log NY |X .

Inequality (42) follows from the induction hypothesis, (44) from submodularity of h∗ , and (47) from the fact
that h∗ ∈ HDC.
Lastly, the polymatroid bound is computable in poly(n, |DC|)-time because the linear program max{h([n]) | h ∈
Mn ∩ HDC} has polynomial size in n and |DC|. To see this, define a variable vi = h(i) for every i ∈ [n], then
11

the modular LP is
(48)

max

n
X

vi

i=1

(49)

s.t.

X

vi ≤ log2 NY |X

(X, Y, NY |X ) ∈ DC

i∈Y −X

vi ≥ 0

(50)

∀i ∈ [n].


Associate a dual variable δY |X for every (X, Y, NY |X ) ∈ DC. In what follows for brevity we sometimes
write (X, Y ) ∈ DC instead of the lengthier (X, Y, NY |X ) ∈ DC. The dual LP of (48) is the following
X
(51)
δY |X log2 NY |X
min
(X,Y,NY |X )∈DC

(52)

s.t.

X

δY |X ≥ 1

∀i ∈ [n]

(X,Y )∈DC
i∈Y −X

(53)

δY |X ≥ 0

∀(X, Y ) ∈ DC.

This is exactly AGM-bound if DC contains only cardinality constraints, and hence our proposition is a
generalization of AGM-bound and its tightness.
5. Algorithms
An algorithm evaluating Q(D) under degree constraints DC is a WCOJ algorithm if it runs in time


max
∗
h([n])
Õ |D| + 2 h∈Γn ∩HDC
.

In general, we do not know how to even compute the entropic bound, in part because there is no finite set
for designing
of linear inequalities characterizing the entropic cone [47]. Hence, thus far we have settled

maxh∈Γn ∩HDC h([n])
algorithms meeting the polymatroid bound, running in time Õ |D| + 2
. This question is
difficult enough, and in some cases (e.g. Proposition 4.4), the two bounds collapse. We we present two
such algorithms in this section, the first algorithm is inspired by the proof of Friedgut’s inequality, and the
second is guided by a proof of a particular type of information theoretic inequalities called Shannon-flow
inequalities.
5.1. An algorithm for acyclic degree constraints. For simplicity, we first assume that there is
a variable order compatible with DC, and w.l.o.g. we assume the order is (1, . . . , n). Algorithm 3 is a
backtracking search algorithm inspired by the inductive proof of Theorem 4.1. Our analysis is summarized
in the following theorem. Note that the runtime expression does not hide any factor behind Õ.
Theorem 5.1. Let Q be a query with acyclic degree constraints DC. Suppose (1, . . . , n) is compatible
with DC. Let D |= DC be a database instance. Then, Algorithm 3 runs in worst-case optimal time:

h
i
max
h([n])
∗
(54)
O n · |DC| · log |D| |D| + 2 h∈Γn ∩HDC

Proof. Let δ denote an optimal solution to the LP (51). Then, by Proposition 4.4 and strong duality
of linear programming, it is sufficient to show that Algorithm 3 runs in time



Y
δY |X
(55)
O n · |DC| · log |D| |D| +
NY |X  .
(X,Y,NY |X )∈DC

The O(n · |DC| · |D| log |D|) term in (55) comes from a preprocessing step where we precompute and index
the projections πY R in the algorithm. We show the remaining runtime by induction on n. When n = 1, the
12

Algorithm 3: Backtracking Search for Acyclic DC
Input: Query Q, acyclic degree constraints DC
(1, . . . , n) compatible with DC ;
return search(());
// empty-tuple argument;
SubRoutine search(aS )
i ← |S| + 1;
if i > n then
return aS ;
end
else
P ← ∅;
\
πAi σAS∩Y =aS∩Y πY R do
for ai ∈
(X,Y )∈DC s.t. i∈Y −X
R guards (X,Y )

P ←P
end
return P ;
end

S

search((aS , ai ));

only thing the algorithm does is compute the intersection
\
(56)
I :=

πA1 R.

(∅,Y,NY |∅ )∈DC s.t. 1∈Y
R guards (∅,Y,NY |∅ )

The intersection can be computed in time proportional to the smallest set, up to a log |D| factor. And thus,
up to a log |D| factor, the runtime is
Y
|πA1 R|δY |∅
min
|πA1 R| ≤
(∅,Y,NY |∅ )∈DC s.t. 1∈Y
R guards (∅,Y,NY |∅ )

(∅,Y,NY |∅ )∈DC s.t. 1∈Y
R guards (∅,Y,NY |∅ )
δ

Y

≤

|X
.
NYY|X

(X,Y,NY |X )∈DC

The first inequality follows because the minimum of a set of non-negative reals is bounded above by their
geometric mean, and from the fact that δ satisfies (52).
When n > 1, the algorithm implicitly or explicitly computes I in (56), which can be done within the
budget time as shown in the base case. Then, for each binding a1 ∈ I, Algorithm 3 performs backtracking
search on the remaining variables (A2 , . . . , An ). By induction, up to a log |D| factor, this can be done in
time
Y
X
Y
δ |X
NYY|X
|σA1 =a1 πY R|δY |∅ ·
a1 ∈I

≤

Y

(∅,Y,NY |∅ )∈DC
1∈Y
R guards (∅,Y,NY |∅ )

≤

(X,Y,NY |X )∈DC
1∈Y
/ −X

(∅,Y,NY |∅ )∈DC
1∈Y
R guards (∅,Y,NY |∅ )

Y

X

|σA1 =a1 πY R|

a1 ∈I

!δY |∅

·

Y

δ

|X
NYY|X

(X,Y,NY |X )∈DC
1∈Y
/ −X

δ

|X
.
NYY|X

(X,Y,NY |X )∈DC

The first inequality follows from Theorem 4.1 and the fact that δ satisfies (52). The second inequality follows
from the fact that R guards (∅, Y, NY |∅ ).

13

Algorithm 3 has several key advantages: (1) It is worst-case optimal when DC is acyclic; (2) It is very
simple and does not require any extra memory (after pre-processing): we can iterate through the output
tuples without computing intermediate results; (3) It is friendly to both hash or sort-merge strategies, as the
only required assumption is that we can compute set intersection in time proportional to the smallest set.
What if DC is not acyclic? There are two solutions. The first solution is to find an acyclic collection DC′
of degree constraints giving the smallest worst-case output size bound and run Algorithm 3 on DC′ . (The final
output is semijoin-reduced against the guards of the original degree constraints DC.) The second solution is
to run the more general and more sophisticated algorithm called PANDA we will present in Section 5.2.
We discuss in this section more details regarding the first strategy of constructing an acyclic DC′ . How
do we know that such an acyclic DC′ exists and is satisfied by the input database? And, how do we know
that the corresponding worst-case output size bound is finite? For example, the first thought that comes
to mind may be to try to remove one or more constraints from DC to make it acyclic. However, this naı̈ve
strategy may result in an infinite output size bound. Consider the following query
(57)

Q(A, B, C, D) ← R(A), S(A, B), T (B, C), W (C, A, D).

The degree constraints given to us are NA|∅ guarded by R, NB|A guarded by S, NC|B guarded by T , and
NAD|C guarded by W . In particular we do not know the sizes of S, T , and W . (They can be user-defined
functions/relations, which need not be materialized.) It is easy to see that removing any of the input
constraints will yield an infinite output size bound. (An infinite output size bound corresponds precisely to
situations where some output variable is unbound and cannot be inferred from bound variables by chasing
FDs.)
Proposition 5.2. Let Q be a full conjunctive query with degree constraints DC such that supD|=DC Q(D)
is finite. Then, there exists an acyclic set of degree constraints DC′ for which
(i) For any database instance D, if D |= DC then D |= DC′ .
(ii) supD|=DC′ Q(D) is finite.
Proof. First, we claim that there exists a degree constraint of the form (∅, Z, NZ|∅ ) ∈ DC with Z 6= ∅.
∗
Assume to the contrary that whenever (X, Y, NY |X ) ∈ DC the set X is not empty. Let h ∈ Γn ∩ HDC denote
an arbitrary entropic function. Let c > 0 be an arbitrary constant. Define a new set function f : 2[n] → R+
∗
by setting f (∅) = 0 and f (S) := h(S) + c for all S 6= ∅. Then, we can verify that f ∈ Γn ∩ HDC as
∗
well: f ∈ Γn because it is a non-negative linear combination of entropic functions,2 and f ∈ HDC because
f (Y |X) = h(Y ) + c − (h(X) + c) = h(Y |X) for every constraints (X, Y, NY |X ) ∈ DC. Since c was arbitrary,
supD|=DC Q(D) = maxh∈Γ∗ ∩HDC h([n]) is unbounded.
n
Second, fix a variable z ∈ Z. Construct a new set DC′ of degree constraints as follows. For every degree
constraints (X, Y, NY |X ) ∈ DC, if X = ∅ or z ∈
/ Y − X, then we we add (X, Y, NY |X ) to DC′ . On the other
hand, if X 6= ∅ and z ∈ Y − X, then we add (X, Y − {z}, NY −{z}|X := NY |X ) to DC′ . It is easy to see that
every guard of (X, Y, NY |X ) in DC remains a guard for the corresponding constraint in DC′ . Hence, D |= DC
implies D |= DC′ .
Third, we show that supD|=DC′ Q(D) is finite. Let HDC′ denote the collection of set functions satisfying
∗
′
DC . Let h′ ∈ Γn ∩ HDC′ be arbitrary. Then h′ (z) ≤ h′ (Z) ≤ log2 NZ|∅ . Define a set function h :
∗
2[n] → R+ by setting h(S) := h′ (S \ {z}). Then, one can mechanically verify that h ∈ Γn ∩ HDC. By
definition h([n]) = h′ ([n] \ {z}) ≥ h′ ([n]) − h′ ({z}) ≥ h′ ([n]) − log NZ|∅ . Consequently, supD|=DC Q(D) ≥
supD|=DC′ Q(D) − log NZ|∅ , implying that supD|=DC′ Q(D) is finite.
To complete the proof, note that the constraint dependency graph GDC′ has a few less edges than those
in GDC ; the edges removed are those pointing to z. Hence, we can repeat this process until DC′ reaches
acyclicity.

The proof of the above proposition also suggests a simple brute-force algorithm for finding the best
acyclic constraint set DC′ . The algorithm runs in exponential time in query complexity. It also raises a
natural question: when is the worst-case output size on the best acyclic DC′ the same as that of DC? We
2Recall that Γ∗ is a convex cone.
n
14

do not know the general answer to this question; however, there is one case when the answer is easy. Recall
that a simple FD is an FD of the form Ai → Aj for two single variables Ai and Aj . The following implies a
result from Gottlob et al. [30].
Corollary 5.3. If DC contains only cardinality constraints and simple FDs, then in polynomial time
in query complexity, we can determine a subset DC′ ⊆ DC so that DC′ is acyclic and, more importantly,
supD|=DC Q(D) = supD|=DC′ Q(D). In particular, Algorithm 3 is a WCOJ algorithm for Q.
Proof. The constraints in the set HDC are either cardinality constraints of the form h(Y ) ≤ NY |∅ or
FD-constraints of the form h({i, j}) = h({i}). Since equalities are transitive, if there was a cycle in GDC
we can remove one edge from the cycle without changing the feasible region defining HDC. Keep breaking
directed cycles this way, we end up with the acyclic DC′ as desired.

5.2. PANDA. Finally we informally present the main ideas behind the PANDA algorithm [8], which can
achieve the polymatroid-bound runtime, modulo huge polylog and query-dependent factors. The algorithm
actually solves a particular form of disjunctive datalog rules, of which conjunctive queries are a special case.
Most importantly, it leads to algorithms meeting highly refined notions of “width parameters” over tree
decompositions of the query. In summary, PANDA has far reaching theoretical implications in terms of the
class of problems it helps solve and the insights it provides in designing and reasoning about join algorithms;
at the same time, the hidden query-dependent and polylog in the data factors leave much room for desire.
Materials in this section are exclusively from [8], with some simplification.
5.2.1. Understanding the polymatroid bound. The starting point of designing any algorithm meeting
the polymatroid bound is to understand in detail what the bound entails. To this end, we establish some
notations. For any I, J ⊆ [n], we write I ⊥ J to mean I 6⊆ J and J 6⊆ I. In order to avoid rewriting
log2 NY |X and (X, Y, NY |X ) ∈ DC over and over, we define
P := {(X, Y ) | ∅ ⊆ X ( Y ⊆ [n]}
(
log2 NY |X (X, Y, NY |X ) ∈ DC
nY |X :=
+∞
otherwise.

(58)
(59)


Pn
Note that |P| = i=0 ni (2i − 1) = 3n − 2n , and the vector n := (nY |X ) lies in RP
+ . The polymatroid bound
maxh∈Γn ∩HDC h([n]) is the optimal objective value of the following optimization problem:
(60)

max
s.t.

h([n])
h(Y ) − h(X) ≤ nY |X ,

(X, Y ) ∈ P

h(I ∪ J) + h(I ∩ J) − h(I) − h(J) ≤ 0,

I ⊥J

h(Y ) − h(X) ≥ 0,

(X, Y ) ∈ P

In addition to the degree constraints h(Y )−h(X) ≤ nY |X , signifying h ∈ HDC, the remaining constraints spell
out the definition of a polymatroid: submodularity, monotonicity, and non-negativity, where monotonicity
and non-negativity collapsed into one constraint h(Y |X) ≥ 0. It is thus more notationally convenient to
[n]
→ R+ .
work on the space h = (h(Y |X)) ∈ RP
+ instead of the original space of functions h : 2
Definition 4 (Conditional polymatroids). We refer to the vectors h = (h(Y |X)) ∈ RP
+ that are feasible
to the last two constraints of (60) and to (63) below as the conditional polymatroids. Also, we will write
h(Y ) instead of h(Y |∅) for brevity.
The equivalent linear program in the space of conditional polymatroids is
(61)

max
s.t.

h([n]|∅)
h(Y |X) ≤ nY |X ,

(X, Y ) ∈ P

(62)

h(I ∪ J|J) − h(I|I ∩ J) ≤ 0,

I⊥J

(63)

h(Y |X) + h(X|∅) − h(Y |∅) = 0,

(X, Y ) ∈ P

h(Y |X) ≥ 0,

(X, Y ) ∈ P

15

In the above, when performing the space transformation from polymatroids to conditional polymatroids, we
impose the obvious extra “conservation” constraints h(Y |∅) = h(Y |X) + h(X|∅). Note that this implies (and
thus is equivalent to) the more general conservation constraints h(Y |Z) = h(Y |X) + h(X|Z).
The (primal) linear program is very clean, but it does not give us a clear sense of the bound relative to
the input statistics nY |X . To obtain this relationship, we look at the dual linear program. Associate dual
variables δ = (δY |X ) to the degree constraints, ξ = (ξI,J ) to the submodularity constraints, α = (αX,Y ) to
the extra conservation constraints, then the dual LP can be written as follows.
(64)

hδ, ni

min
s.t.

inflow(∅, [n]) ≥ 1,
inflow(X, Y ) ≥ 0,

(X, Y ) ∈ P ∧ (X, Y ) 6= (∅, [n]),

(δ, ξ) ≥ 0.
where for any (X, Y ) ∈ P, inflow(X, Y ) is defined by
X
X
αX,Y +
inflow(∅, Y ) := δY |∅ −

W :(Y,W )∈P

X:(X,Y )∈P

inflow(X, Y ) := δY |X +

X

I:I⊥X
I∪X=Y

αY,W −

ξI,X −

X

X

ξY,J

J:Y ⊥J
Y ∩J=∅

ξY,J + αX,Y

X 6= ∅

J:Y ⊥J
Y ∩J=X

Note that there is no non-negativity requirement on α. The dual LP (64) is important in two ways. First,
let h∗ and (δ ∗ , ξ ∗ , α∗ ) denote a pair of primal- and dual-optimal solutions, then from strong duality of linear
programming [61] we have
X
δY∗ |X nY |X .
(65)
h∗ ([n]) = hδ ∗ , ni =
(X,Y )∈P

We are now able to “see” the input statistics contributions to the objective function. (The reader is welcome
to compare this expression with that of (51).) Second, the dual formulation allows us to formulate a (vast)
generalization of Shearer’s inequality, to deal with general degree constraints. We refer to this generalization
as “Shannon-flow inequalities”, which is discussed next.
5.2.2. Shannon-flow inequalities.
Definition 5 (Shannon-flow inequality). Let δ ∈ RP
+ denote a non-negative coefficient vector. If the
inequality
(66)

h([n]) ≤ hδ, hi

holds for all conditional polymatroids h, then it is called a Shannon-flow inequality.
It is important not to lose sight of the fact that conditional polymatroids are simply a syntactical shortcut
to the underlying polymatroids, designed to simplify notations; they P
are not a new function class. We can
rewrite (66) in a wordier form involving only polymatroids: h([n]) ≤ (X,Y )∈P δY |X (h(Y ) − h(X)).
Shannon-flow inequalities occur naturally in characterizing feasible solutions to the dual LP (64) using
Farkas’ lemma [61]:
Proposition 5.4 (From [8]). Let δ ∈ RP
+ denote a non-negative coefficient vector. The inequality
h([n]) ≤ hδ, hi is a Shannon-flow inequality if and only if there exist ξ, α such that (δ, ξ, α) is a feasible
solution to the dual LP (64).
It is not hard to show that Shearer’s inequality is a consequence.
Corollary 5.5 (Shearer’s inequality). Let H = ([n], P
E) be a hypergraph, and δ = (δF )F ∈E be a vector
of non-negative coefficients. Then, the inequality h([n]) ≤ F ∈E δF h(F ) holds for all polymatroids iff δ is a
fractional edge cover of H.
16

5.2.3. Proof sequences and PANDA. We next explain how studying Shannon-flow inequalities leads to
an algorithm called the Proof Assisted eNtropic Degree Aware (PANDA) algorithm whose runtime meets
the polymatroid bound. At a high level, the algorithm consists of the following steps.
(1) Obtain an optimal solution (δ ∗ , ξ ∗ , α∗ ) to the dual LP (64).
(2) Use the dual solution to derive a particular mathematical proof of the Shannon-flow inequality
h([n]) ≤ hδ ∗ , hi. This inequality is a Shannon-flow inequality thanks to Proposition 5.4. This
mathematical proof has to be of a particular form, called the “proof sequence,” which we define
below.
(3) Finally, every step in the proof sequence is interpreted as a symbolic instruction to perform a
relational operator (partition some relation, or join two relations). These symbolic instructions are
sufficient to compute the final result.
The full version of PANDA is more complex than the three steps above, due to several technical hurdles we
have to overcome. The reader is referred to [8] for the details. This section can only present a simplified
high-level structure of the algorithm.
We next explain the proof sequence notion in some details.
P If we were to expand out a Shannon-flow
inequality h([n]) ≤ hδ ∗ , hi, it would be of the form h([n]) ≤ (X,Y )∈P δY∗ |X h(Y |X), where δY∗ |X are all nonnegative. Hence, we interpret the RHS of the above inequality as a set of “weighted” conditional polymatroid
terms: the term h(Y |X) is weighted by δY∗ |X . To prove the inequality, one may attempt to apply either the
submodularity inequality (62) or the equality (63) to some of the terms to start converting the RHS to the
LHS. These applications lead to three types of rules:
• Suppose δ · h(I|I ∩ J) occurs on the RHS, then we may apply (62) with a weight of w ∈ [0, δ] to
obtain a (new or not) weighted term w · h(I ∪ J|J) while retain (δ − w) · h(I|I ∩ J) of the old term.
In this scenario, we say that we have applied the submodularity rule h(I|I ∩ J) → h(I ∪ J|J) with
a weight of w.
• The equality (63) can be used in two ways: either we replace h(Y |∅) by h(Y |X) + h(X|∅), resulting
in a decomposition rule h(Y |∅) → h(Y |X) + h(X|∅), or the other way around where we’d get a
composition rule h(Y |X) + h(X|∅) → h(Y ). These rules can be applied with a weight, as before.
A (weighted) proof sequence of a Shannon-flow inequality is a series of weighted rules such that at no point
in time any weight is negative, and that in the end h([n]) occurs with a weight of at least 1. We were able
to prove the following result:
Theorem 5.6 (From [8]). There exists a proof sequence for every Shannon-flow inequality h([n]) ≤ hδ, hi
The dual feasible solution (δ, ξ, α) gives us an intuition already on which rule to apply. For example,
ξI,J > 0 indicates that we should apply the submodularity rule, αX,Y > 0 indicates a decomposition rule,
and αX,Y < 0 hints at a composition rule. The technical issue we have to solve is to make sure that these
steps serialize to a legitimate proof sequence.
Finally, after obtaining the proof sequence for the inequality h([n]) ≤ hδ ∗ , hi, PANDA interprets the
proof sequence as follows. Note that δY∗ |X > 0 implies nY |X < ∞, which means there is a guard for the
corresponding constraint. We associate the guarding relation with the term h(Y |X). Now, we look at each
rule in turn: a decomposition rule corresponds to partitioning the relation associated with the conditional
polymatroid term being decomposed; a composition rule corresponds to joining the two associated relations;
and a submodularity rule is used to move the association map. These concepts are best illustrated with an
example, which is a minor modification of an example from [7].
Example 1. Consider the following query
Q(A, B, C, D) ← R(A, B), S(B, C), T (C, D), W (A, C, D), V (A, B, D),
with the
•
•
•
•
•

following degree constraints:
(∅, AB, NAB ) guarded by R,
(∅, BC, NBC ) guarded by S,
(∅, CD, NCD ) guarded by T ,
(AC, ACD, NACD|AC ) guarded by W ,
(BD, ABD, NABD|BD ) guarded by V .
17

Name

proof step

operation

action

decomposition

h(BC) → h(B) + h(BC|B)

partition

submodularity
composition
submodularity
composition
submodularity
composition
submodularity
composition

h(CD) → h(BCD|B)
h(B) + h(BCD|B) → h(BCD)
h(ABD|BD) → h(ABCD|BCD)
h(ABCD|BCD) + h(BCD) → h(ABCD)
h(BC|B) → h(ABC|AB)
h(AB) + h(ABC|AB) → h(ABC)
h(ACD|AC) → h(ABCD|ABC)
h(ABC) + h(ABCD|ABC) → h(ABCD)

NOOP
join
NOOP
join
NOOP
join
NOOP
join

S → S heavy ∪ S light
S heavy ← {(b, c) ∈ S : |σB=b R| > θ}
S light ← {(b, c) ∈ S : |σB=b R| ≤ θ}
T (C, D) now “affiliated” with h(BCD|B)
I1 (B, C, D) ← S heavy (B, C), T (C, D).
V (A, B, D) now “affiliated” with h(ABCD|BCD)
output1 (A, B, C, D) ← V (A, B, D), I1 (B, C, D).
S light now “affiliated” with h(ABC|AB)
I2 (A, B, C) ← R(A, B), S light (B, C).
W (A, C, D) now “affiliated” with h(ABCD|ABC)
output2 (A, B, C, D) ← I2 (A, B, C), W (A, C, D).

Table 2. Proof sequence to algorithmic steps. θ :=

q

NBC NCD NABD|BD
NAB NACD|AC

We claim that the following is a Shannon-flow inequality:
1
h(ABCD) ≤ [h(AB) + h(BC) + h(CD) + h(ACD|AC) + h(ABD|BD)],
2
and PANDA can evaluate the query in time
q

(67)
Õ
NBC NCD NABD|BD NAB NACD|AC .
Inequality (1) holds for every polymatroid h ∈ Γ4 , because

h(AB) + h(BC) + h(CD) + h(ACD|AC) + h(ABD|BD)
= h(AB) + h(B) + h(BC|B) + h(CD) + h(ACD|AC) + h(ABD|BD)
≥ h(AB) + h(B) + h(BC|B) + h(BCD|B) + h(ACD|AC) + h(ABD|BD)
= h(AB) + h(BC|B) + h(BCD) + h(ACD|AC) + h(ABD|BD)
≥ h(AB) + h(BC|B) + h(BCD) + h(ACD|AC) + h(ABCD|BCD)
= h(AB) + h(BC|B) + h(ACD|AC) + h(ABCD)
≥ h(AB) + h(ABC|AB) + h(ACD|AC) + h(ABCD)
= h(ABC) + h(ACD|AC) + h(ABCD)
≥ h(ABC) + h(ABCD|ABC) + h(ABCD)
= h(ABCD) + h(ABCD).
The proof above applied the proof sequence shown in Table 2, which also contains the step-by-step description
of how to translate the proof sequence into an algorithm. The total runtime is within (67):



q
NBC
NCD NABD|BD + θNAB NACD|AC = Õ
(68)
Õ
NBC NCD NABD|BD NAB NACD|AC .
θ
6. Open problems
There are many interesting and challenging open questions arising from this line of inquiries: questions
regarding the bounds, the algorithms, the desire to make them practical and extend their reach to more
difficult or realistic settings. In terms of bounds, the most obvious question is the following:
Open Problem 1. Is the entropic bound computable?
We know that the entropic bound is tight, but we do not know if it is decidable whether the bound is
below a given threshold. This question is closely related to the question of determining whether a linear
inequality is satisfied by all entropic functions or not.
Next, assuming we have to settle for the polymatroid bound, then the challenge is to find efficient
algorithms for computing the polymatroid bound, which is a linear program with an exponential number of
18

variables. As we have seen, there are classes of queries and degree constraints for which we can compute the
polymatroid bound in polynomial time in query copmlexity. Even if computing the polymatroid bound is
difficult in general, say it is NP-hard or harder, it would be nice to be able to characterize larger classes of
queries and constraints allowing for tractability.
Open Problem 2. What is the computational (query) complexity of computing the polymatroid bound?
Design an efficient algorithm computing it.
Another important line of research is to enlarge the class of degree constraints for which the polymatroid
bound is tight, making PANDA a WCOJ algorithm (up to a large polylog factor). In these special cases,
perhaps there are simpler algorithms than PANDA, such as Algorithm 3. The following two questions are
along this direction.
Open Problem 3. Characterize the class of queries and degree constraints for which the best constraint
modification as dictated by Proposition 5.2 has the same worst-case output size bound as the original
constraint set.
Open Problem 4. Characterize the class of degree constraints DC for which the polymatroid bound is
tight.
PANDA is a neat algorithm, which is capaable of answering the more general problem of evaluating
a disjunctive datalog rule. Hence, perhaps there are faster algorithms without the large polylog factor,
designed specifically for answering conjunctive queries:
Open Problem 5. Find an algorithm running within the polymatroid bound that does not impose the
poly-log (data) factor as in PANDA.
Reasoning about entropic inequalities has allowed us to gain deeper insights on both the algorithm design
and bounding the worst-case output size. Entropy is, by definition, an expectation. And thus it should serve
as a bridge to reasoning about average output size. A result from Atserias et al. [12] which has not been
exploited further by the database community is their concentration result, a good starting point for the
following question.
Open Problem 6. Develop a theory and algorithms for average-case output size bound.
Average case bounds and complexity is only one way to go beyond worst-case. Another line of research
is on the notion of instance-optimality for computing joins. Instance optimality is a difficult notion to define
formally, let alone having an optimal algorithm under such stringent requirement. There are only a few
known work on instance-optimality in database theory [4, 24, 49, 53]. After information theory perhaps
geometric ideas will play a bigger role in answering this question:
Open Problem 7. Develop a theory and practical algorithms for instance-optimal query evaluation.
Last but not least, traditional database optimizers have been designed on the “one join at a time”
paradigm, influenced by relational algebra operators. It is this author’s strong belief that the time is ripe for
the theory and practice of multiway join optimizers, based on information theoretic analysis and sampling
strategies, taking into account systems requirements such as streaming, transactional constraints, incremental
view maintenance, etc.
Open Problem 8. Develop a theory and practical algorithms for an optimizer for the multiway join
operator.
References
[1] C. R. Aberger, A. Lamb, S. Tu, A. Nötzli, K. Olukotun, and C. Ré, Emptyheaded: A relational engine for graph
processing, ACM Trans. Database Syst., 42 (2017), pp. 20:1–20:44.
[2] M. Abo Khamis, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich, In-database learning with sparse tensors,
in Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2018,
Houston, TX, USA.
, AC/DC: In-database learning thunderstruck, CoRR, (2018).
[3]
[4] M. Abo Khamis, H. Q. Ngo, C. Ré, and A. Rudra, Joins via geometric resolutions: Worst case and beyond, ACM
Trans. Database Syst., 41 (2016), pp. 22:1–22:45.
19

[5] M. Abo Khamis, H. Q. Ngo, and A. Rudra, FAQ: questions asked frequently, in Milo and Tan [48], pp. 13–28.
[6]
, Juggling functions inside a database, SIGMOD Record, 46 (2017), pp. 6–13.
[7] M. Abo Khamis, H. Q. Ngo, and D. Suciu, Computing join queries with functional dependencies, in Milo and Tan [48],
pp. 327–342.
[8]
, What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?, in
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017,
Chicago, IL, USA, May 14-19, 2017, E. Sallinger, J. V. den Bussche, and F. Geerts, eds., ACM, 2017, pp. 429–444.
[9] N. Alon, On the number of subgraphs of prescribed type of graphs with a given number of edges, Israel J. Math., 38 (1981),
pp. 116–130.
[10] K. Ammar, F. McSherry, S. Salihoglu, and M. Joglekar, Distributed evaluation of subgraph queries using worst-case
optimal and low-memory dataflows, PVLDB, 11 (2018), pp. 691–704.
[11] M. Aref, B. ten Cate, T. J. Green, B. Kimelfeld, D. Olteanu, E. Pasalic, T. L. Veldhuizen, and G. Washburn,
Design and implementation of the logicblox system, in Sellis et al. [63], pp. 1371–1382.
[12] A. Atserias, M. Grohe, and D. Marx, Size bounds and query plans for relational joins, in FOCS, IEEE Computer
Society, 2008, pp. 739–748.
[13] P. Bailis, J. M. Hellerstein, and M. Stonebraker, eds., Readings in Database Systems, 5th Edition, 2015.
[14] P. Beame, P. Koutris, and D. Suciu, Skew in parallel query processing, in Hull and Grohe [38], pp. 212–223.
[15] L. Becchetti, P. Boldi, C. Castillo, and A. Gionis, Efficient algorithms for large-scale local triangle counting, ACM
Trans. Knowl. Discov. Data, 4 (2010), pp. 13:1–13:28.
[16] B. Bollobás and A. Thomason, Projections of bodies and hereditary properties of hypergraphs, Bull. London Math. Soc.,
27 (1995), pp. 417–424.
[17] T. H. Chan and R. W. Yeung, On a relation between information inequalities and group theory, IEEE Transactions on
Information Theory, 48 (2002), pp. 1992–1995.
[18] A. K. Chandra and P. M. Merlin, Optimal implementation of conjunctive queries in relational data bases, in STOC,
1977, pp. 77–90.
[19] S. Chu, M. Balazinska, and D. Suciu, From theory to practice: Efficient join query evaluation in a parallel database
system, in Sellis et al. [63], pp. 63–78.
[20] F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer, Some intersection theorems for ordered sets and graphs,
J. Combin. Theory Ser. A, 43 (1986), pp. 23–37.
[21] T. M. Cover and J. A. Thomas, Elements of information theory, Wiley-Interscience [John Wiley & Sons], Hoboken, NJ,
second ed., 2006.
[22] T. Elgamal, S. Luo, M. Boehm, A. V. Evfimievski, S. Tatikonda, B. Reinwald, and P. Sen, SPOOF: sum-product
optimization and operator fusion for large-scale machine learning, in CIDR 2017, 8th Biennial Conference on Innovative
Data Systems Research, Chaminade, CA, USA, January 8-11, 2017, Online Proceedings, www.cidrdb.org, 2017.
[23] R. Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30 (1983), pp. 514–550.
[24] R. Fagin, A. Lotem, and M. Naor, Optimal aggregation algorithms for middleware, in Proceedings of the Twentieth ACM
SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 21-23, 2001, Santa Barbara, California,
USA, P. Buneman, ed., ACM, 2001.
[25] X. Feng, A. Kumar, B. Recht, and C. Ré, Towards a unified architecture for in-rdbms analytics, in Proceedings of the
ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012,
K. S. Candan, Y. Chen, R. T. Snodgrass, L. Gravano, and A. Fuxman, eds., ACM, 2012, pp. 325–336.
[26] E. Friedgut, Hypergraphs, entropy, and inequalities, Amer. Math. Monthly, 111 (2004), pp. 749–760.
[27] E. Friedgut and J. Kahn, On the number of copies of one hypergraph in another, Israel J. Math., 105 (1998), pp. 251–256.
[28] T. Gogacz and S. Toruńczyk, Entropy bounds for conjunctive queries with functional dependencies, in Proc. 20th
International Conference on Database Theory (ICDT), 2017. To appear.
[29] G. Gottlob, G. Greco, N. Leone, and F. Scarcello, Hypertree decompositions: Questions and answers, in Milo and
Tan [48], pp. 57–74.
[30] G. Gottlob, S. T. Lee, G. Valiant, and P. Valiant, Size and treewidth bounds for conjunctive queries, J. ACM, 59
(2012), p. 16.
[31] G. Graefe, Query evaluation techniques for large databases, ACM Computing Surveys, 25 (1993), pp. 73–170.
[32] M. Grohe and D. Marx, Constraint solving via fractional edge covers, in SODA, ACM Press, 2006, pp. 289–298.
[33] M. Grohe and D. Marx, Constraint solving via fractional edge covers, ACM Transactions on Algorithms, 11 (2014), p. 4.
[34] D. Halperin, V. T. de Almeida, L. L. Choo, S. Chu, P. Koutris, D. Moritz, J. Ortiz, V. Ruamviboonsuk, J. Wang,
A. Whitaker, S. Xu, M. Balazinska, B. Howe, and D. Suciu, Demonstration of the myria big data management
service, in International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, C. E.
Dyreson, F. Li, and M. T. Özsu, eds., ACM, 2014, pp. 881–884.
[35] G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1988. Reprint of
the 1952 edition.
[36] J. M. Hellerstein, C. Ré, F. Schoppmann, D. Z. Wang, E. Fratkin, A. Gorajek, K. S. Ng, C. Welton, X. Feng,
K. Li, and A. Kumar, The madlib analytics library or MAD skills, the SQL, PVLDB, 5 (2012), pp. 1700–1711.
[37] X. Hu and K. Yi, Towards a worst-case i/o-optimal algorithm for acyclic joins, in Proceedings of the 35th ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’16, New York, NY, USA, 2016, ACM, pp. 135–150.

20

[38] R. Hull and M. Grohe, eds., Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of
Database Systems, PODS’14, Snowbird, UT, USA, June 22-27, 2014, ACM, 2014.
[39] Y. E. Ioannidis and S. Christodoulakis, On the propagation of errors in the size of join results, in Proceedings of the
1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991., J. Clifford
and R. King, eds., ACM Press, 1991, pp. 268–277.
[40] S. Jukna, Extremal combinatorics, Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg,
second ed., 2011. With applications in computer science.
[41] C. Kankanamge, S. Sahu, A. Mhedbhi, J. Chen, and S. Salihoglu, Graphflow: An active graph database, in Proceedings
of the 2017 ACM International Conference on Management of Data, SIGMOD ’17, New York, NY, USA, 2017, ACM,
pp. 1695–1698.
[42] B. Ketsman and D. Suciu, A worst-case optimal multi-round algorithm for parallel computation of conjunctive queries,
in Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’17,
New York, NY, USA, 2017, ACM, pp. 417–428.
[43] P. G. Kolaitis and M. Y. Vardi, Conjunctive-query containment and constraint satisfaction, J. Comput. Syst. Sci., 61
(2000), pp. 302–332.
[44] P. Koutris, P. Beame, and D. Suciu, Worst-case optimal algorithms for parallel query processing, in 19th International
Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016, W. Martens and T. Zeume, eds.,
vol. 48 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, pp. 8:1–8:18.
[45] A. Kumar, J. F. Naughton, and J. M. Patel, Learning generalized linear models over normalized data, in Sellis et al. [63],
pp. 1969–1984.
[46] L. H. Loomis and H. Whitney, An inequality related to the isoperimetric inequality, Bull. Amer. Math. Soc, 55 (1949),
pp. 961–962.
[47] F. Matus, Infinitely many information inequalities, in 2007 IEEE International Symposium on Information Theory, IEEE,
2007, pp. 41–44.
[48] T. Milo and W. Tan, eds., Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database
Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, ACM, 2016.
[49] H. Q. Ngo, D. T. Nguyen, C. Ré, and A. Rudra, Beyond worst-case analysis for joins with minesweeper, in Hull and
Grohe [38], pp. 234–245.
[50] H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich, In-database factorized learning, in Proceedings of the 11th
Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, Montevideo, Uruguay,
June 7-9, 2017., J. L. Reutter and D. Srivastava, eds., vol. 1912 of CEUR Workshop Proceedings, CEUR-WS.org, 2017.
[51] H. Q. Ngo, E. Porat, C. Ré, and A. Rudra, Worst-case optimal join algorithms: [extended abstract], in PODS, 2012,
pp. 37–48.
[52] H. Q. Ngo, C. Ré, and A. Rudra, Skew strikes back: new developments in the theory of join algorithms, SIGMOD
Record, 42 (2013), pp. 5–16.
[53] D. T. Nguyen, M. Aref, M. Bravenboer, G. Kollias, H. Q. Ngo, C. Ré, and A. Rudra, Join processing for graph
patterns: An old dog with new tricks, in Proceedings of the Third International Workshop on Graph Data Management
Experiences and Systems, GRADES 2015, Melbourne, VIC, Australia, May 31 - June 4, 2015, J. Larriba-Pey and T. L.
Willke, eds., ACM, 2015, pp. 2:1–2:8.
[54] D. Olteanu and F. Rusu, Special issue on in-database analytics, Distributed and Parallel Databases, 35 (2017), pp. 333–
334.
[55] D. Olteanu and M. Schleich, F: regression models over factorized views, PVLDB, 9 (2016), pp. 1573–1576.
[56] D. Olteanu and J. Závodný, Size bounds for factorised representations of query results, ACM Trans. Database Syst., 40
(2015), pp. 2:1–2:44.
[57] C. H. Papadimitriou and M. Yannakakis, On the complexity of database queries, in PODS, 1997, pp. 12–19.
[58] J. Radhakrishnan, Entropy and counting, Computational Mathematics, Modelling and Algorithms, (2003), p. 146.
[59] J. Radhakrishnan, Entropy and counting, (2003).
[60] M. Schleich, D. Olteanu, and R. Ciucanu, Learning linear regression models over factorized joins, in Proceedings of
the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26
- July 01, 2016, F. Özcan, G. Koutrika, and S. Madden, eds., ACM, 2016, pp. 3–18.
[61] A. Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley
& Sons Ltd., Chichester, 1986. A Wiley-Interscience Publication.
[62] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price, Access path selection in a relational
database management system, in Proceedings of the 1979 ACM SIGMOD international conference on Management of data,
SIGMOD ’79, New York, NY, USA, 1979, ACM, pp. 23–34.
[63] T. K. Sellis, S. B. Davidson, and Z. G. Ives, eds., Proceedings of the 2015 ACM SIGMOD International Conference
on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, ACM, 2015.
[64] S. Suri and S. Vassilvitskii, Counting triangles and the curse of the last reducer, in WWW, 2011, pp. 607–614.
[65] C. E. Tsourakakis, U. Kang, G. L. Miller, and C. Faloutsos, Doulion: counting triangles in massive graphs with a
coin, in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD
’09, New York, NY, USA, 2009, ACM, pp. 837–846.
[66] M. Y. Vardi, The complexity of relational query languages (extended abstract), in STOC, 1982, pp. 137–146.

21

[67] T. L. Veldhuizen, Triejoin: A simple, worst-case optimal join algorithm, in Proc. 17th International Conference on
Database Theory (ICDT), Athens, Greece, March 24-28, 2014., N. Schweikardt, V. Christophides, and V. Leroy, eds.,
OpenProceedings.org, 2014, pp. 96–106.
[68] R. W. Yeung, Information Theory and Network Coding, Springer Publishing Company, Incorporated, 1 ed., 2008.
[69] Z. Zhang and R. W. Yeung, On characterization of entropy function via information inequalities, IEEE Transactions on
Information Theory, 44 (1998), pp. 1440–1452.

22

