FAQ: Questions Asked Frequently
Mahmoud Abo Khamis

∗†

∗†

Hung Q. Ngo

†

Atri Rudra

arXiv:1504.04044v6 [cs.DB] 6 Feb 2017

∗

LogicBlox Inc.
{mahmoud.abokhamis,hung.ngo}@logicblox.com
†

Department of Computer Science and Engineering
University at Buffalo, SUNY
{mabokham,hungngo,atri}@buffalo.edu
Abstract

We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many
frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical
models and logic. This is our main conceptual contribution.
We then present a simple algorithm called InsideOut to solve this general problem. InsideOut is
a variation of the traditional dynamic programming approach for constraint programming based on
variable elimination. Our variation adds a couple of simple twists to basic variable elimination in order
to deal with the generality of FAQ, to take full advantage of Grohe and Marx’s fractional edge cover
framework, and of the analysis of recent worst-case optimal relational join algorithms.
As is the case with constraint programming and graphical model inference, to make InsideOut run
efficiently we need to solve an optimization problem to compute an appropriate variable ordering. The
main technical contribution of this work is a precise characterization of when a variable ordering is
‘semantically equivalent’ to the variable ordering given by the input FAQ expression. Then, we design an
approximation algorithm to find an equivalent variable ordering that has the best ‘fractional FAQ-width’.
Our results imply a host of known and a few new results in graphical model inference, matrix operations,
relational joins, and logic.
We also briefly explain how recent algorithms on beyond worst-case analysis for joins and those for
solving SAT and #SAT can be viewed as variable elimination to solve FAQ over compactly represented
input functions.

1

1
1.1

Introduction
Motivating examples

The following fundamental problems from three diverse domains share a common algebraic structure.
Example 1.1. (Matrix Chain Multiplication (MCM)) Given a series of matrices A1 , . . . , An over some field F,
where the dimension of Ai is pi × pi+1 , i ∈ [n], we wish to compute the product A = A1 · · · An . The problem
can be reformulated as follows. There are n + 1 variables X1 , . . . , Xn+1 with domains Dom(Xi ) = [pi ], for
i ∈ [n + 1]. For i ∈ [n], matrix Ai can be viewed as a function of two variables
ψi,i+1 : Dom(Xi ) × Dom(Xi+1 ) → F,
where ψi,i+1 (x, y) = (Ai )xy . The MCM problem is to compute the output function
ϕ(x1 , xn+1 ) =

X

x2 ∈Dom(X2 )

X

···

n
Y

ψi,i+1 (xi , xi+1 ).

xn ∈Dom(Xn ) i=1

Example 1.2. (Maximum A Posteriori (MAP) queries in probabilistic graphical models (PGM)) Consider
a discrete graphical model represented by a hypergraph H = (V, E). There are n discrete random variables
V = {X1 , . . . , Xn } on finite domains Dom(Xi ), i ∈ [n], and m = |E| factors
Y
ψS :
Dom(Xi ) → R+ , S ∈ E.
i∈S

A typical inference task is to compute the marginal MAP estimates, written in the form
Y
ϕ(x1 , . . . , xf ) =
max
···
max
ψS (xS ).
xf +1 ∈Dom(Xf +1 )

xn ∈Dom(Xn )

S∈E

Example 1.3. (# Quantified Conjunctive Query (#QCQ)) Let Φ be a first-order formula of the form


^
R ,
Φ(X1 , . . . , Xf ) = Qf +1 Xf +1 · · · Qn Xn 
R∈atoms(Φ)

where Qi ∈ {∃, ∀}, for i > f . The #QCQ problem is to count the number of tuples in relation Φ on the
free variables X1 , . . . , Xf . To reformulate #QCQ, construct a hypergraph H = (V, E) as follows: V is the
set of all variables X1 , . . . , Xn , and for each R ∈ atoms(Φ) there is a hyperedge S = vars(R) consisting of all
variables in R. The atom R can be viewed as a function indicating whether an assignment xS to its variables
is satisfied by the atom; namely ψS (xS ) = 1 if R(xS ) is true and 0 otherwise.
Now, for each i ∈ {f + 1, . . . , n} we define an aggregate operator
(
L(i)
max if Qi = ∃,
=
×
if Qi = ∀.

Then, the #QCQ problem above is to compute the constant function
X
X
L(f +1)
L(n) Y
···
ϕ=
···
ψS (xS ).
x1 ∈Dom(X1 )

xf ∈Dom(Xf ) xf +1 ∈{0,1}

xn ∈{0,1} S∈E

It turns out that these and dozens of other fundamental problems from constraint satisfaction (CSP),
databases, matrix operations, PGM inference, logic, coding theory, and complexity theory can be viewed
as special instances of a generic problem we call the Functional Aggregate Query, or the FAQ problem,
which we define next. The first two columns in Table 1 present eight of these problems. See [8, 30, 57] and
Appendix A for many more examples.
2

1.2

The FAQ problem

Throughout the paper, we use the following convention. Uppercase Xi denotes a variable, and lowercase xi
denotes a value in the domain Dom(Xi ) of the variable. Furthermore, for any subset S ⊆ [n], define
Y
XS = (Xi )i∈S ,
xS = (xi )i∈S ∈
Dom(Xi ).
i∈S

In particular, XS is a tuple of variables and xS is a tuple of specific values with support S. The input to FAQ
is a set of functions and the output is a function computed using a series of aggregates over the variables and
input functions. More specifically, for each i ∈ [n], let Xi be a variable on some discrete domain Dom(Xi ),
where |Dom(Xi )| ≥ 2. The FAQ problem is to compute the following function
ϕ(x[f ] ) =

L(f +1)

···

L(n)

N

ψS (xS ),

(1)

xn ∈Dom(Xn ) S∈E

xf +1 ∈Dom(Xf +1 )

where
• H = (V, E) is a multi-hypergraph. V = [n] is the index set of the variables Xi , i ∈ [n]. Overloading
notation, V is also referred to as the set of variables.
• The set F = [f ] is the set of free variables for some integer 0 ≤ f ≤ n. Variables in V − F are called
bound variables.
• D is a fixed domain, such as {true, false}, {0, 1} or R+ .
Q
• For every hyperedge S ∈ E, ψS : i∈S Dom(Xi ) → D is an input function (also called a factor). There
are m = |E| hyperedges.
• For every bound variable i > f , ⊕(i) is a binary (aggregate) operator on the domain D. Different
bound variables may have different aggregate operators.
• Finally, for each bound variable i > f either ⊕(i) = ⊗ or (D, ⊕(i) , ⊗) forms a commutative semiring
1
(with the same additive identity 0 and multiplicative identity 1). If ⊕(i) = ⊗, then ⊕(i) is called a
product aggregate; otherwise, it is a semiring aggregate.
To avoid triviality, we assume that there is at least one semiring aggregate. (The semiring requirement is not
as much of a restriction as one might think at first glance. In Appendix B, we describe several methods for
‘turning’ non-semiring aggregates into semiring aggregates.) Because for i > f every variable Xi has its own
L(i)
L
.
aggregate ⊕(i) over all values xi ∈ Dom(Xi ), in the rest of the paper we will write (i)
xi to mean
xi ∈Dom(Xi )

We will often refer to ϕ as an FAQ-query. We use FAQ-SS2 to denote the special case of FAQ when there
is only one variable aggregate, i.e. ⊕(i) = ⊕, ∀i > f , and (D, ⊕, ⊗) is a semiring. The special case of FAQ-SS
when there is no free variable is called the SumProd problem. As shall be further discussed in Section 3,
SumProd and FAQ-SS are well-studied problems.

1.3

Input and output representation

To make the problem definition complete, we will also have to specify how the input and output functions
of an FAQ instance are represented. As we shall see in Section 8, this is a subtle issue that vastly affects the
landscape of tractability of the problem.
1 A triple (D, ⊕, ⊗) is a commutative semiring if ⊕ and ⊗ are commutative binary operators over D satisfying the following:
(1) (D, ⊕) is a commutative monoid with an additive identity, denoted by 0. (2) (D, ⊗) is a commutative monoid with
a multiplicative identity, denoted by 1. (In the usual semiring definition, we do not need the multiplicative monoid to be
commutative.) (3) ⊗ distributes over ⊕. (4) For any element e ∈ D, we have e ⊗ 0 = 0 ⊗ e = 0.
2 FAQ with a Single Semiring.

3

To streamline the presentation, in the first part of this paper we will assume that both the input and
output factors are represented using the listing representation: each factor is a table of all tuples of the
form hxS , ψS (xS )i, such that ψS (xS ) 6= 0. (In particular, entries not in the table are 0-entries.) This
representation is commonly used in the CSP, databases, and sparse matrix computation domains.
Our algorithms are in fact more generic, they work for a general class of input and output representations,
as discussed in Section 8.

1.4

Paper organization

Section 2 summarizes the contributions of the paper and sketches the line of attack. Related works are
discussed in Section 3. Section 4 defines notations, terminologies, and establishes a few facts used throughout
the paper. Section 5 discusses the main ideas behind InsideOut and analyzes its runtime given a variable
ordering. Section 6 explains how to characterize variable orderings that are “semantically-equivalent” to
the original ordering in the given FAQ-query. Section 7 explains how to efficiently search through all those
equivalent variable orderings to find the “best” one (i.e. the one that allows InsideOut to run the fastest).
Finally, Section 8 presents the effect of input and output representations; in particular, it shows how InsideOut
is still useful for problems such as SAT and #SAT.

2

Summary of contributions

2.1

Conceptual contribution

The formulation of FAQ has its roots in the SumProd and more generally FAQ-SS problems, which have been
studied by by Dechter [30], Aji and McEliece [8] and Kohlas and Wilson [57]. The SumProd problem is
exactly the special case of FAQ when all variable aggregates are semiring aggregates over the same semiring,
and there is no free variable. We will discuss more of the history of this problem in Section 3.
FAQ substantially generalizes SumProd, as FAQ can now capture problems in logic such as QCQ (quantified
conjunctive query) or #QCQ (sharp quantified conjunctive query). We argue that FAQ is a very powerful
way of thinking about these problems and related issues. FAQ can be thought of as a declarative query
language over functions. For example, we show in Section 8 how different input representations can vastly
affect the landscape of tractability of the problem, and how the output representation is related to the notion
of factorized databases [73].

2.2

Algorithmic contribution

We present a single algorithm, called InsideOut, to solve FAQ. InsideOut is a variation of the variable
elimination algorithm [30, 93, 94]. In PGM, variable elimination was first proposed by Zhang and Poole [93].
Then Dechter [30] observed that this strategy can be applied to problems on other semirings such as constraint
satisfaction and SAT solving. In the database literature, Yannakakis’ algorithm [90] can also be cast as
variable elimination under the set semiring or Boolean semiring.3
InsideOut adds three minor twists to the basic variable elimination strategy. First, we use a backtrackingsearch strategy called OutsideIn to compute the intermediate results. This strategy allows us to use recent
worst-case optimal join algorithms [2, 67, 69, 89] to compute intermediate results within the fractional edge
cover bound [11, 46]. Second, we introduce the idea of an indicator projection of a function onto a given set
of variables to obtain the fractional hypertree width style of runtime guarantee [47]. Third, in addition to
making use of the distributive law to ‘fold’ common factors [8] when we face a semiring aggregate, we apply
a swap between an aggregate and the inside product when that aggregate is also a product.
We show that InsideOut runs in time Õ(N faqw(σ) + kϕk), where σ is a variable ordering that we choose
to run the algorithm on, N is the input size, and kϕk is the output size (under the ‘listing representation’
of input and output factors), and faqw(σ) is a parameter called the (fractional) FAQ-width of σ. FAQ-width
3 It

is well-known [8, 58] that variable elimination and message passing are equivalent in the special case of FAQ-SS.

4

is the FAQ-analog of the induced fractional hypertree width of a variable ordering. (See Definition 5.10.)
In this paper, we use Õ to hide a logarithmic factor in data complexity and a polynomial factor in query
complexity.
In fact, Section 8 shows that the variable elimination framework is still powerful in cases when the
fractional hypertree width bounds are no longer applicable. These are special cases of FAQ where the input
functions are compactly represented. In particular, we explain how – with a suitable modification – InsideOut
can be used to recover recently known beyond worst-case results in join algorithms (Minesweeper [65], and
Tetris [2]), and results on the tractability of SAT and #SAT for β-acyclic formulas [18, 74].

2.3
2.3.1

Main technical contributions
“Width” of an FAQ

In light of InsideOut running in time Õ(N faqw(σ) +kϕk) for a given variable order σ, the key technical problem
is choosing a σ that minimizes faqw(σ). This is where the generality of FAQ requires new techniques and
results. Traditional variable elimination for CSPs or PGM inference also requires computing a good variable
ordering to minimize the (induced) treewidth [58] or fractional hypertree width [47] of the variable ordering.
However, in those cases all variable orderings are valid; hence, all we have to do in this traditional setting is
to compute a tree decomposition whose maximum bag size (or maximum fractional edge cover number over
the bags) is minimized; then, the GYO-elimination procedure will produce a good variable ordering (see
Section 4). In the general setting of FAQ, just like in logic where there are alternating quantifiers, the set
of semantically equivalent variable orderings depends on both the scoping structure specified by the input
query expression and the connectivity structure of the query’s hypergraph.
To see how the query’s hypergraph affects the set of equivalent variable orderings, consider the following
simple example. A natural class of valid permutations to consider are those that only permute aggregates
in a maximal block of identical aggregates in the query expression. However, taking the query hypergraph
into account, one can do much better. Consider, for example, the FAQ-query
X
X
max · · ·
ψ{1,3,...,2k−1} ψ{2,4,...,2k}
ϕ = max
x1

x2

x3

x2k

P
where both factors have range R+ . In this case, even though max and
do not commute with one another,
we can rewrite ϕ using any of the (2k)! variable orderings and still obtain the same result. (The aggregates
have to be permuted along with the variables to which they are attached.)
Even for the special case of FAQ-SS, where there is only one type of semiring aggregates hence all
permutations are valid, computing the optimal variable ordering is already NP-hard in query complexity,
because computing the (fractional hyper) treewidth of the query hypergraph is NP-hard. (See Gottlob
et al [37, 42] for a recent survey and new results on this topic.) Hence, the extra complication of only
considering ‘valid’ orderings for FAQ seems to make our task much harder. Somewhat surprisingly, we are
able to show that the complexity of computing the optimal ordering for general FAQ is essentially the same
as the complexity of computing the optimal ordering for FAQ-SS instances. Figure 1 presents a schematic
summary of our main technical contributions, described in more details below.
• Given an FAQ-query ϕ, we define the set EVO(ϕ) of all variable orderings semantically equivalent to ϕ.
Roughly, for any σ ∈ EVO(ϕ), if we rewrite the expression for ϕ using the ordering σ (with all aggregates
permuted along), then we obtain a function identical to ϕ, no matter what the input factors are. The
FAQ-width of ϕ is faqw(ϕ) = minσ∈EVO(ϕ) faqw(σ). (If the FAQ instance was a SumProd instance, then
faqw(ϕ) is exactly the fractional hypertree width of the query.)
In Figure 1, suppose we are looking at the top/orange path: from the input expression ϕ with variable
order σ, if we somehow were able to compute the optimal variable ordering σ ∗ = arg minτ ∈EVO(ϕ) faqw(τ ),
then we would have an algorithm running in time Õ(N faqw(ϕ) + kϕk). Here, kϕk denotes the output
size. However, even if we were willing to spend an exponential time in query complexity, in order to
take the orange path and find σ ∗ we need to be able to characterize the set EVO(ϕ). In particular,
5

EVO(ϕ) = set of expressions
“semantically equivalent” to ϕ

Runtime = Õ(N faqw(σ

∗

)

+ kϕk)

= Õ(N opt + kϕk)
FAQ-expr. σ
for ϕ, hypergraph H

EVO(ϕ)

FAQ-expr. σ ∗
InsideOut
for ϕ
σ ∗ = arg minτ ∈EVO(ϕ) faqw(τ )

Runtime = Õ(N opt+g(opt) + kϕk)

LinEx(P ) ⊆ EVO(ϕ)

poly(|H|)

ϕ

EVO(ϕ) = CWE(LinEx(P ))
minτ ∈LinEx(P ) faqw(τ ) = minτ ∈EVO(ϕ) faqw(τ )
P

x1 ,x4

maxx3

Q

poly(|H|)

x2 ,x7

P

x5

Expression Tree
Precedence Poset P

poly(|H|)
maxx6

FAQ-expr. σ̄
for ϕ
faqw(σ̄) ≤ opt + g(opt)

Tree Decomposition of H

g = approx. factor
for fractional
hypertree width of H

Figure 1: Summary of our technical contributions
given a variable ordering τ , how do we know whether τ ∈ EVO(ϕ) or not? Our answer to this question
comes next.
• We describe how to (in poly-time, query complexity) construct an expression tree for the input FAQquery. The expression tree induces a partially ordered set on the variables called the precedence poset.
By defining a notion called component-wise equivalence (CWE), we completely characterize EVO(ϕ):
σ ∈ EVO(ϕ) if and only if it is component-wise equivalent to some linear extension of the precedence
poset. In fact, we also show that checking whether σ ∈ EVO(ϕ) can be done in polynomial time in
query complexity.
• While membership in EVO(ϕ) is verifiable in polynomial time, as aforementioned the optimization
problem σ ∗ = arg minτ ∈EVO(ϕ) faqw(τ ) is NP-hard. In some applications such as PGM-inference, we
cannot sweep query complexity under the rug as we do in database applications. It is thus natural
to design approximation algorithms for faqw(ϕ). To this end, we prove another technical result, that
going through all orderings in EVO(ϕ) is not necessary. The set of linear extensions of the precedence
poset is sufficient: every linear extension of the precedence poset is semantically equivalent to ϕ, and
every σ ∈ EVO(ϕ) has the same FAQ-width as some linear extension of this poset.4
• Finally, using an approximation algorithm for the fractional hypertree width (fhtw) with approximation
ratio g(fhtw) as a blackbox,5 and using the expression tree as a guide, we give an approximation
algorithm computing an ordering σ such that faqw(σ) ≤ opt + g(opt), where opt = faqw(ϕ). (In the
FAQ-SS case, our approximation guarantee is slightly better: faqw(σ) ≤ g(opt).)
4 If the instance is an FAQ-SS instance, then the poset imposes no order on the non-free variables, i.e. the set of linear
extensions is the set of all possible variable orderings of non-free variables.
5 The best known such algorithm due to Marx [60] has g(fhtw) = O(fhtw3 ).

6

2.3.2

The effect of input and output representation

The input to FAQ is a collection of functions. We observe that the representation of the input functions has
a huge effect on the computational complexity of the problem.
We begin with the representation of the input factors. One option is the truth table representation for
each factor involved in the FAQ instance ϕ (e.g. the conditional probability table in PGM [58] or the usual
2D-array representation of matrices). This representation is wasteful when the input factors have many
0-entries. Another option, which is commonly used in the CSP, databases, and sparse matrix computation
domains is to list pairs hxS , ψS (xS )i for a given factor ψS such that ψS (xS ) 6= 0. The results listed in Table 1
implicitly assumed the listing representation.
However, our results can handle even more succinct representations such as GDNFs and decision diagrams [25] in CSP literature and algebraic decision diagrams in the PGM literature [12]. We present a
common view of these representations: an input factor ψS (xS ) might itself be the output of some other
FAQ instance ϕ′S on the (free) variables xS . The succinctness in the representation comes from representing
factors of ϕ′S in the listing format (instead of listing ψS ). Technically, we analyze what happens when one
composes an FAQ instance with another. More interestingly, this framework is general enough to present a
class of structured matrices (including the DFT matrices) for which we can quantify how much better our
algorithm runs than the naı̈ve quadratic time algorithm.
Furthermore, we observe that when the input factors are too “compact”, then the class of tractable FAQqueries is much smaller, and the fractional hypertree width framework no longer applies. Nevertheless, the
variable elimination strategy is still a powerful approach. We will, however, have to change the algorithm
used to solve sub-problems: it can no longer be backtracking-search-style of algorithm. We give four examples
where we explain how recent beyond worst-case results in join algorithms (Minesweeper [65], and Tetris [2]),
and the tractability of SAT and #SAT for β-acyclic formulas [18, 74], all of which are special cases of FAQ,
can be explained using this idea.
Last but not least, we make several observations regarding the representations of the output function ϕ.
For the case when the FAQ instance ϕ has no free variables, the algorithm needs to output a single element
from D. However, when ϕ has free variables, then we have to also represent the output somehow. The
default option is to also use the listing representation for the output. However, InsideOut is general enough
to be able to output an FAQ instance as the output. This issue is slightly subtle as ϕ is already an FAQ
instance that represents the output but it is not an “interesting” representation. However, the generality of
our algorithm allows the input factors and output both to be represented as FAQ instances. Our observations
here are very close in spirit to the recent results on database factorization of Olteanu and Závodný [73].

2.4

Highlights of our corollaries

In light of the fact that many problems can be reduced to FAQ, Table 1 presents a selected subset of corollaries
that our results imply.6 We list the results assuming the optimal variable ordering is already given. (This
holds true for both known results and our results.) When the optimal variable ordering is not given, the
exponents of N in all cases have to be changed to the best known approximating factors for the corresponding
width. In the FAQ case, that would be O(faqw3 (ϕ)).
For each problem, the table lists the corresponding FAQ instance, the runtime of the previously best
known algorithm, and the runtime of InsideOut. These are the problems that we would like to highlight, as
they yield either new results or an alternative interpretation of known results in the FAQ framework.
The results in Table 1 roughly span three areas: (1) CSPs and Logic; (2) PGMs and (3) Matrix operations.
Except for joins, problems in area (1) need the full generality of our FAQ formulation, where InsideOut either
improves upon existing results or yields new results. Problems in area (2) can already be reduced to FAQ-SS.
Here, InsideOut improves upon known results since it takes advantage of Grohe and Marx’s more recent fractional hypertree width bounds. Finally, problems in area (3) of Table 1 are classic. InsideOut does not yield
anything new here, but it is intriguing to be able to explain the textbook dynamic programming algorithm
6 The

results listed in the table implicitly assumed the listing representation of input factors.

7

Problem
#QCQ

FAQ formulation
X L(f +1)
L(n) Y
ψS (xS )
xf +1 · · ·
xn

Previous Algo.

Our Algo.

No non-trivial algo

Õ(N faqw(ϕ) + kϕk)

Õ(N PW(H) + kϕk) [24]

Õ(N faqw(ϕ) + kϕk)

Õ(N DM(H) + kϕk) [34]

Õ(N faqw(ϕ) + kϕk)



Õ N fhtw(H) + kϕk [46]



Õ N fhtw(H) + kϕk

Õ(N htw(ϕ) + kϕk) [54]

Õ(N faqw(ϕ) + kϕk)

ψS (xS )

Õ(N htw(ϕ) + kϕk) [54]

Õ(N faqw(ϕ) + kϕk)

ψi,i+1 (xi , xi+1 )

DP bound [28]

DP bound

O(N log p N ) [27]

O(N logp N )

S∈E

(x1 ,...,xf )

QCQ

L
where (i) ∈ {max, ×}
L(f +1)
L(n) Y
ψS (xS )
xf +1 · · ·
xn
S∈E

where
#CQ

X

(x1 ,...,xf )

Joins
Marginal

S T
x

∈ {max, ×}
Y
ψS (xS )
max · · · max
xn

xf +1

S∈E

X

L(i)

S∈E

ψS (xS )
Y
ψS (xS )

(xf +1 ,...,xn ) S∈E

MAP
MCM

max

(xf +1 ,...,xn )

X

n
Y

Y

S∈E

x2 ,...,xn i=1

DFT

X

(y0 ,...,ym−1 )∈Zm
p

by ·

Y

x ·y

e

j k
i2π m−j−k
p

0≤j+k<m

Table 1: Runtimes of algorithms assuming optimal variable ordering is given. Problems shaded red are
in CSPs and logic (D = {0, 1} for CSP and D = N for #CSP), problems shaded green fall under PGMs
(D = R+ ), and problems shaded blue fall under matrix operations (D = C). N denotes the size of the
largest factor (assuming they are represented with the listing format). htw(ϕ) is the notion of integral
cover width defined in [54] for PGM. PW(H) is the optimal width of a prefix graph of H from [24] and
DM(H) = poly(F -ss(H), fhtw(H)), where F -ss(H) is the [f ]-quantified star size [34]. kϕk is the output size
in listing representation. Our width faqw(ϕ) is never worse than any of the three and there are classes of
queries where ours is unboundedly better than all three. In DFT, N = pm is the length of the input vector.
Õ hides a logarithmic factor in data complexity and polynomial factor in query complexity.
for Matrix-Chain Multiplication [28] as an algorithm to find a good variable ordering for the corresponding
FAQ-instance. The DFT result is a re-writing of Aji and McEliece’s observation [8].7
It should be noted that the prior results on #CQ [34] and QCQ [24] focused on dichotomy theorems for
bounded-arity classes of input hypergraphs, not just on the best possible runtime one can get. Our faqw
notion is a generalization of fractional hypertree width, which steps into the unbounded arity world. See
Marx [62] for a more detailed discussion of known results on CSP in the unbounded-arity case.

3

Related work

Since FAQ encompasses so many areas, our related work discussion is necessarily incomplete. Appendix G
discusses more related works on the factor/function representation issue.

3.1

Problems on one semiring

As was mentioned earlier, SumProd is the special case of FAQ when all variable aggregates are semiring
aggregate over the same semiring, and there is no free variable. This special case is powerful enough to capture
7 Note

that we have further results on matrix vector multiplication for structured matrices (see Appendix G.3).

8

a bunch of problems (e.g. it captures all CSPs). This problem was implicitly defined by by Dechter [30],
who solved it using variable elimination.
To the best of our knowledge, the FAQ-SS problem was explicitly defined by Aji and McEliece [8] who
called it the MPF problem (for Marginalize the product function).8 They presented a message passing algorithm for FAQ-SS and essentially showed that their algorithm meets the treewidth bound. Their paper also
lists a number of problems that are FAQ-SS instances, including Matrix Chain Multiplication (less specific than
our result, they just argue that essentially different variable orderings give rise to different ways of parenthesizing the matrix chain multiplication) and Matrix Vector Multiplication. They showed that their general
algorithm contains FFT as a special case. We re-phrase their interpretation of the FFT using InsideOut. They
also showed that many basic decoding problems in coding theory can be cast as FAQ-SS instances.
Kohlas and Wilson [57] presented even more applications of the FAQ-SS problem. The paper categorized
various existing message passing algorithms depending on what extra properties they need beyond (D, ⊕, ⊗)
being a commutative semiring. Their paper also explored algorithms for approximate computations (while in
this work we solely deal with exact computation). Approximate computations in PGMs have been explored
under the semiring framework [80].
Most of the results in the PGM literature present algorithms that are shown to obtain the treewidth bound.
To the best of our knowledge, the finest hypergraph width parameter used to bound the performance of PGM
inference algorithms is the integral hypertree width bound of [43], which appeared in [31,54]. See Sections 3.3
and 4.3 for a more detailed discussion on the various width parameters.
In the database literature, recently Koch [56] described an algebraic query language called AGCA over
‘rings of databases’ which is somewhat similar in spirit to FAQ. This framework makes use of additive
inverses to allow for efficient view maintenance.

3.2

Factorized databases

Bakibayev et al. [13] and Olteanu and Závodný [73] introduced the notion of factorized databases, and
showed how one can efficiently compute join and aggregates over factorized databases. In hindsight there
is much in common between their approach and InsideOut applied to the single semiring case of FAQ-SS.
Both approaches have the same runtime complexity, because both are dynamic programming algorithms,
InsideOut is bottom-up, and factorized database computation is top-down (memoized).
The FAQ framework is more general in that it can handle multiple aggregate types. Our contribution
also involves the characterization of EVO and an approximation algorithm for faqw. On the other hand,
aspects of factorized database that FAQ does not handle include the evaluation of SQL queries and output
size bounds on the factorized representations.

3.3

Width parameters

Various notions of hypergraph ‘widths’ have been developed over the years in PGM, CSP, and database
theory. In particular, two often-used properties of the input query are acyclicity and bounded width.
When the query is acyclic, the classic algorithm of Yannakakis [90] for relational joins (and CSPs) runs
in time linear in the input plus output size, modulo a log factor. Similarly, Pearl’s belief propagation
algorithm [77] works well for acyclic graphical models. As we briefly touch upon in Appendix F.1, Yannakakis’
algorithm is essentially belief propagation on the Boolean semiring or set semiring. The algorithm can also
be reinterpreted using InsideOut.
Subsequent works on databases and CSPs further expand the classes of queries that can be evaluated in
polynomial time. These works define progressively more general width parameters for a query, which intuitively measure how far a query is from being acyclic. Roughly, these results state that if the corresponding
width parameter is bounded by a constant, then the query is ‘tractable,’ i.e. there is a polynomial-time
algorithm to evaluate it. For example, Gyssens et al. [50, 51] showed that queries with bounded degree of
acyclicity are tractable. Then came query width (qw) from Chekuri and Rajaraman [22], hypertree width and
8 Though

related problems had been defined before: see e.g. [14].

9

generalized hypertree width (ghw) from Gottlob et al. [43, 82], and fractional hypertree width from Grohe and
Marx [47]. See [42] for a survey and [37] for the latest in this line of work. Marx developed stronger width
parameters called adaptive width and submodular width [61, 62], which were recently extended to functional
dependencies and degree bounds [3, 4].
In the PGM literature, the most common parameter is treewidth as the textbook variable elimination
and message passing algorithms are often stated to run in time O(N w+1 ) where w is the tree width of the
model [58]. Freuder [38] and Dechter and Pearl [32] showed in late 1980s that CSP instances with bounded
treewidth are tractable.
In the logic/finite model theory literature, several width parameters were also developed [6, 24, 34]. We
will describe them later in the relevant sections of the paper.

3.4

Finite model theory

In [79], Pichler and Skritek studied the #CQ problem in the special case where the query is acyclic. We
refer to this special case as #ACQ. In particular, they showed that #ACQ is tractable in data complexity
(i.e. when the number of variables that we are counting over is a constant) and in query complexity (i.e.
when all relations have constant sizes) but not in combined complexity where the problem turns out to be
#P-complete.
In [34], Durand and Mengel introduced a new parameter for #CQ called the quantified star size. It is
basically a measure of how free variables are connected in the query’s hypergraph. Along with bounded
generalized hypertree width (or fractional hypertree width), bounded quantified star size characterizes the
classes of #CQ instances that are tractable in the bounded arity (or bounded generalized hypertree width)
case.
The quantified star size idea has been expanded later by applying it to the core of the query instead of
the original query [45]. The core is a minimal subquery that is homomorphic to the original query. Because
homomorphism does not preserve counts (i.e. it is not a one-to-one mapping), free variables have to be
explicitly preserved by taking the core of the color query of the original query. Further development along
with new lower bounds appeared in [26].
QCQ (second row of Table 1) has its own long line of research. An early and interesting result was
the tractability of QCQ when the domain size, treewidth, and number of quantifier alternations are all
constants [23]. More recently, Chen and Dalmau introduced a width parameter for QCQ based on elimination
orderings [24]. In particular, they take the minimum width over some variable orderings that are equivalent
to the original query. They showed the tractability of QCQ when their width is bounded.
The runtime of InsideOut for CQ, #CQ, and QCQ are unboundedly better than the above results as shown
in Table 1. Our result on #QCQ is new: to the best of our knowledge no non-trivial efficient algorithms
for #QCQ were known prior to our work. Essentially, InsideOut is able to unify the above results under the
same umbrella.

4
4.1

Preliminaries
Factors, their representations, and sizes

In relational database systems [1, 59, 88], constraint satisfaction, and sparse matrix operations [92], the
following representation of input and output factors is the most common:
Definition 4.1 (Listing representation). In the listing representation, each factor is a table of all tuples of
the form hxS , ψS (xS )i, such that ψS (xS ) 6= 0. In particular, entries not in the table are 0-entries.
We will assume in most of this paper that all input and output factors are represented using the listing
representation. Section 8 discusses how our results still hold under other representations and the effect they
have on the computational landscape.

10

Recall that 0 is the additive identity of the semiring(s) which also annihilates any element of D under
multiplication.
Q
Let W ⊆ [n] be some subset of variables, and
Q yW ∈ i∈W Dom(Xi ) be some given value tuple. The
conditional factor ψS (· | yW ) is a function from i∈S Dom(Xi ) to D defined by
(
0
if S ∩ W 6= ∅ and xS∩W 6= yS∩W
ψS (xS | yW ) =
ψS (xS ) otherwise.
For each factor ψS , define its size to be the number of non-zero points under its domain:

kψS k := xS | ψS (xS ) 6= 0 .

(This is also the number of rows in the table representing ψS in the list representation.) Let T ⊆ S be
arbitrary, then obviously we can write a factor size as a sum of conditional factor sizes:
X
kψS (· | yT )k.
(2)
kψS k =
yT ∈

Q

i∈T

Dom(Xi )

Throughout this paper, we use N to denote the maximum over all input factor sizes.
Definition 4.2 (Indicator
Q projection). For any two sets T, S ⊆ [n] such that S ∩ T 6= ∅, and a given factor
ψS , the function ψS/T : i∈T Dom(Xi ) → D defined by
(
1 ∃xS−T s.t. ψS (xT , xS−T ) 6= 0
ψS/T (xT ) :=
0 otherwise
is called the indicator projection of ψS onto T .

4.2

AGM-bound and fractional cover numbers

Let H = (V, E) be a hypergraph. Let B ⊆ V be any subset of vertices. An integral edge cover of B using
edges in H is a feasible solution λ = (λS )S∈E to the following integer program:
X
min
λS
S∈E

s.t.

X

λS ≥ 1, ∀v ∈ B

S:v∈S

λS ∈ {0, 1}, ∀S ∈ E,
whose optimal objective value is denoted by ρH (B). The number ρH (B) is called the integral edge cover
number of B. Similarly, ρ∗H (B) is the optimal objective value of the relaxation
X
min
λS
S∈E

s.t.

X

λS ≥ 1, ∀v ∈ B

S:v∈S

λS ≥ 0, ∀S ∈ E.
Any feasible solution to the above linear program is called a fractional edge cover of B using edges in H.
Note that ρ and ρ∗ are functions from 2V → R+ .
Fix some input (ψS )S∈E for our FAQ problem. Let λ∗ = (λ∗S )S∈E denote an optimal solution to the linear
program
X
min
λS log2 |ψS |
S∈E

11

s.t.

X

λS ≥ 1, ∀v ∈ B

S:v∈S

λS ≥ 0, ∀S ∈ E.
Then, the quantity
AGMH (B) :=

Y

∗

|ψS |λS

(3)

S∈E

is called the AGM-bound for B using edges of H. It is obvious that
∗

AGMH (B) ≤ N ρH (B) .

(4)

We call the quantities ρH (V), ρ∗H (V), and AGMH (V) the integral cover number, fractional cover number,
and AGM-bound corresponding to H. When H is implicit from context, we shall drop the subscript H and
write ρ(B), ρ∗ (B), and AGM(B) for the sake of brevity. Note that the AGM-bound is “data-dependent”
in the sense that it is a function of the input factors, while the cover numbers are only dependent on the
hypergraph. Thus, our notation AGM(B) is under the implicit assumption that the input factors are fixed.

4.3

Tree decomposition, acyclicity, and width-parameters

Definition 4.3 (Tree decomposition). Let H = (V, E) be a hypergraph. A tree-decomposition of H is a pair
(T, χ) where T = (V (T ), E(T )) is a tree and χ : V (T ) → 2V assigns to each node of the tree T a subset
of vertices of H. The sets χ(t), t ∈ V (T ), are called the bags of the tree-decomposition. There are two
properties the bags must satisfy
(a) For any hyperedge F ∈ E, there is a bag χ(t), t ∈ V (T ), such that F ⊆ χ(t).
(b) For any vertex v ∈ V, the set {t | t ∈ V (T ), v ∈ χ(t)} is not empty and forms a connected subtree of
T.
Definition 4.4 (α-acyclic). A hypergraph H = (V, E) is α-acyclic iff there exists a tree decomposition (T, χ)
in which every bag χ(t) is a hyperedge of H.
When H represents a join query, the tree T in the above definition is also called the join tree of the query.
A query is acyclic if and only if its hypergraph is acyclic. While possessing many nice properties [36], the
notion of α-acyclicity is unsatisfying because we can turn any hypergraph into an α-acyclic hypergraph by
adding a hyperedge covering all its vertices. This observation motivates a second notion of acyclicity [36].
Definition 4.5 (β-acyclicity). A hypergraph H is β-acyclic iff the hypergraph formed by any subset of
edges of H is α-acyclic.
To define commonly used width parameters of hypergraphs, we follow the width function framework
introduced by Adler [5]. Let H = (V, E) be a hypergraph. Let g : 2V → R+ be a function that assigns a non-negative real number to each subset of V. Then, the g-width of a tree decomposition (T, χ) is
maxt∈V (T ) g(χ(t)). The g-width of H is the minimum g-width over all tree decompositions of H. Note that
the g-width of a hypergraph is a Minimax function.
Definition 4.6 (Common width parameters). Let s be the following function: s(B) = |B| − 1, ∀V ⊆ V.
Then the tree-width of a hypergraph H, denoted by tw(H), is exactly its s-width. The hypertree width of a
hypergraph H, denoted by htw(H), is the ρ-width of H, and the fractional hypertree width of a hypergraph
H, denoted by fhtw(H), is the ρ∗ -width of H.

12

4.4

Vertex/variable ordering and its equivalence to tree decomposition

Besides tree decompositions, there is another equivalent way to characterize and define (α/β-) acyclicity
and width parameters of hypergraphs using a listing of vertices of a hypergraph [15, 16]. The results in this
section are probably well-known to researchers in this area, but we were not able to track down a precise
reference for some of our propositions below. Their proofs are presented in Appendix C for completeness.
Definition 4.7 (Vertex/variable ordering). A vertex ordering of a hypergraph H = (V, E) is simply a listing
σ = v1 , . . . , vn of all vertices in V. Because we use vertices (of H) and variables more or less interchangeably
in this paper, the term variable ordering will also be used with the same semantic.
In the literature “elimination order,” “elimination ordering,” or “global attribute order” are also used in
place of “vertex ordering” [2, 15, 16, 65]. However, we chose not to use “elimination order” here because a
vertex ordering is meant to be the reverse of a (GYO) elimination ordering, as we explain below.
Elimination hypergraph sequence. Fix a vertex ordering σ = v1 , . . . , vn of H, for j = n, n − 1, . . . , 1 we
σ
recursively define a sequence of n hypergraphs Hnσ , Hn−1
, . . . , H1σ as follows. To avoid cumbersome superscripting, we will denote the sequence as Hn , Hn−1 , . . . , H1 when the vertex ordering σ is clear from context.
Define Hn = (Vn , En ) = (V, E) = H. Let ∂(vn ) be the set of hyperedges of Hn incident to vn , and Un be the
union of edges in ∂(vn ):

∂(vn ) =
S ∈ En | vn ∈ S ,
(5)
[
S..
(6)
Un =
S∈∂(vn )

For each j = n − 1, n − 2, . . . , 1, define the hypergraph Hj = (Vj , Ej ) as follows.
Vj
Ej

=
=

∂(vj ) =
Uj

=

{v1 , . . . , vj }

(Ej+1 − ∂(vj+1 )) ∪ Uj+1 − {vj+1 }

{S ∈ Ej | vj ∈ S}
[
S.
S∈∂(vj )

Again, strictly speaking the sets Vj , Ej , ∂(vj ), and Uj should have been denoted by Vjσ , Ejσ , ∂ σ (vj ), and Ujσ .
But we drop the superscript as σ is implicitly understood.
Definition 4.8. The above sequence of hypergraphs is called the elimination hypergraph sequence associated
with the vertex ordering σ. There is an intimate relationship between tree decompositions and vertex
orderings, which can be proved by making use of the above elimination hypergraph sequence.
Proposition 4.9 (α-Acyclicity). A hypergraph H is α-acyclic if and only if there is a vertex ordering
σ = (v1 , . . . , vn ) such that Ukσ ∈ ∂(vk ) for all k ∈ [n].
Proposition 4.10 (β-Acyclicity). A hypergraph H is β-acyclic if and only if there is a vertex ordering
σ = (v1 , . . . , vn ) such that the collection of hyperedges in ∂(vk ) form a nested inclusion chain, for all k ∈ [n].
Furthermore, β-acyclicity can be verified in polynomial-time.
Definition 4.11 (Induced g-width). Let H = (V, E) be a hypergraph. Let g : 2V → R+ be a function and
σ = (v1 , . . . , vn ) be a vertex ordering of H. Then, the induced g-width of σ is the quantity maxk∈[n] g(Ukσ ).
When g(B) = |B| − 1, this is called the induced width of σ. When g(B) = ρH (B), this is called the induced
integral edge cover width of σ. When g(B) = ρ∗H (B), this is called the induced fractional edge cover width of
σ.
We next characterize three width parameters of a hypergraph using vertex ordering. A function g : 2V →
R is said to be monotone if g(A) ≤ g(B) whenever A ⊆ B. We prove a generic lemma.
+

13

Lemma 4.12 (g-width). Let g : 2V → R+ be a monotone function. A hypergraph H = (V, E) has g-width
at most w if and only if there exists a vertex ordering σ of all vertices of H such that the induced g-width of
σ is at most w.
Because the functions s(Uk ) = |Uk | − 1, ρH (Uk ) and ρ∗H (Uk ) are all monotone, the following results follow
immediately.
Corollary 4.13. A hypergraph H = (V, E) has treewidth (respectively, generalized hypertree width, fractional
hypertree width) at most w if and only if there exists a vertex ordering σ = (v1 , . . . , vn ) of H such that for
every k ∈ [n] we have |Ukσ | ≤ w + 1 (respectively, ρH (Uk ) ≤ w, ρ∗H (Uk ) ≤ w).
Note that the above corollary is actually three corollaries. The one regarding tree-width alone is wellknown in the probabilistic graphical model literature [10, 32]. The other two are probably folklore, but we
were not able to find them explicitly stated anywhere.

5
5.1

The InsideOut Algorithm
Algorithmic Warm-ups

We first present a simple solution to the FAQ-SS problem. Recall FAQ-SS denotes the special case of FAQ
when all variable aggregates are the same: i.e. ⊕(i) = ⊕, ∀i > f , and (D, ⊕, ⊗) is a semiring. Our aim is
to gently introduce the reader to the duality of backtracking-search and dynamic programming, and to the
main idea of variable elimination.
5.1.1

Backtracking search

Consider the SumProd form of the FAQ expression (1) when there is no free variable and all aggregates are
the same semiring aggregate. In this case, we write the expression as


M O
MO
M

ϕ=
ψS (xS ) =
ψS (xS | x1 ) .
x S∈E

x1 ∈Dom(X1 )

x[n]−{1} S∈E

We can evaluate this expression by going through each value of x1 and computing the inner expression
‘conditioned’ on this x1 . The naı̈ve implementation of this strategy wastes time if there is any x1 for which
some conditional factor ψS (· | x1 ) is identically 0. Thus, the obvious idea is to first compute the set I1 of
values x1 for which ψS (· | x1 ) 6≡ 0 for all factors ψS . Then, recursively compute the expression


M
M O

ϕ=
ψS (xS | x1 ) .
x1 ∈I1

x[n]−{1} S∈E

Given that the input factors are represented using the listing format (i.e. only non-0 entries are listed),
computing the above expression recursively is a join algorithm in disguise, and any of the algorithms from
[2, 67, 69, 89] works. We call this the OutsideIn algorithm, as it evaluates the expression from the outer-most
aggregate to the inner-most. It will serve as the algorithmic building block of InsideOut. In fact, the OutsideIn
algorithm works even if there were free variables. The following is almost immediate (see Appendix D for
more details).
Theorem 5.1. Let ϕ be an FAQ-SS-query whose hypergraph H = (V, E) has m edges and n vertices. Algorithm OutsideIn computes ϕ in time O(mn · AGM(V) · log N ).

OutsideIn is backtracking search [29,41] which was known 50 years ago in the AI and constraint programming world. In the PGM literature, the method of conditioning search is similar, but the main theoretical
14

objective is so that the conditioning graph is acyclic [78]. The main advantage of backtracking search is that
it requires very little extra space. The main disadvantage is that it might have to resolve the same subproblem multiple times. The duality between backtracking search and dynamic programming is well-known
in the constraint programming literature [81]. The next section explores the other side of this duality: the
dynamic programming side.
5.1.2

Dynamic programming with variable elimination

To solve the FAQ-SS problem using variable elimination [30, 93, 94], the idea is to “fold” common factors,
exploiting the distributive law:
M
MO
ϕ(xF ) =
···
ψS (xS )
=

xf +1

xn S∈E

M

M

···

xf +1

O

xn−1 S∈E−∂(n)



M O
ψS (xS ) ⊗ 
ψS (xS ),
xn S∈∂(n)

|

{z

′
new factor ψU

n −{n}

}

where the equality follows from the fact that ⊗ distributes over ⊕, and recall from (5) and (6) that ∂(n)
denotes all edges incident to n in H and Un = ∪S∈∂(n) S. Note that the problem of computing the intermediate
′
factor ψU
is exactly an FAQ-SS instance, where there is only one bound variable Xn , and |Un | − 1 free
n −{n}
′
variables. Assume for the moment that we can somehow efficiently compute ψU
.
n −{n}
′
After computing ψU
,
the
resulting
problem
is
another
instance
of
FAQ-SS
on a modified multin −{n}
hypergraph Hn−1 , constructed from H by removing vertex n along with all edges in ∂(n), and adding
back a new hyperedge Un − {n}. Recursively, we continue this process until all variables Xn , . . . , Xf +1 are
eliminated. Textbook treewidth-based results for PGM inference are obtained this way [58]. In the database
′
context (i.e. given an FAQ-query over the Boolean semiring), the intermediate result ψU
is essentially
n −{n}
an intermediate materialized relation of a query plan.

5.2
5.2.1

The InsideOut Algorithm
Introducing the indicator projections

While correct, basic variable elimination as described in Section 5.1.2 is potentially not very efficient for
sparse input factors, i.e. factors whose sizes are smaller than the product of the domain sizes. The main
reason is that the product that was factored out (i.e. ⊗S∈E−∂(n) ψS (xS )) might annihilate many entries of
′
′
the intermediate result ψU
, while we have spent so much time computing ψU
. For example, for
n −{n}
n −{n}
an S ∈
/ ∂(n) and tuple yS such that S ⊆ Un and ψS (yS ) = 0, we do not need to compute the entries
′
ψU
(xUn −{n} ) for which yS = xS : those entries will be killed later anyhow. The idea is then to only
n −{n}
′
compute those ψU
(xUn −{n} ) values that will ‘survive’ the other factors. One simple way to achieve
n −{n}
this is to allow for the factors that were factored out of the scope of Xn to still participate in computing
′
ψU
(xUn −{n} ):
n −{n}

′
ψU
(xUn −{n} ) =
n −{n}









M O
 O

ψS (xS ) ⊗ 


xn

S∈∂(n)





ψS/Un (xS∩Un ) 
{z
} 
|

(7)

S ∈∂(n),
/
S∩Un 6=∅ indicator projection

′
For a set S ∈ En − ∂(n) with S ∩ Un 6= ∅, the participation of a factor ψS in computing ψU
is only
n −{n}
to “confirm” that entries computed are not wasteful; thus, only their indicator projections participate and
′
not the real factors ψS themselves. In database terms, one can also think of the definition of ψU
in (7)
n −{n}

15

Q
as a simultaneous semijoin reduction of the main product S∈∂(n) ψS with all of the “tables” ψS for which
S ∩ Un 6= ∅.
The problem defined in (7) is an FAQ-SS instance with |Un | − 1 free variables, which we can solve using
the OutsideIn algorithm as described in Section 5.1.1. Note the important point that, algorithmically we do
not perform the “semijoins” individually; rather, we compute the multiway-join using a worst-case optimal
join algorithm.
5.2.2

The general case

We finally describe how InsideOut deals with a general FAQ-query defined by the expression (1). Recall that
each operator ⊕(i) for f < i ≤ n either forms a semiring with ⊗ or is ⊗ itself. Let us see how the last
variable can be eliminated in this general scenario. The elimination depends on two cases.
Case 1: (D, ⊕(n) , ⊗) forms a semiring. In this case we apply the same strategy as before: we compute the
intermediate factor ψUn −{n} defined in (7) using OutsideIn.
Case 2: ⊕(n) = ⊗. In this case, we rewrite the expression as follows.

=
=
=
=
=

ϕ(x[f ] )
L(f +1)
xf +1

···

L(n) N

S∈E ψS (xS )
xn
L(n−1) L(n) N


ψ
(x
)
S
S∈E S
xn
xf +1
xn−1

L(f +1)
L(n−1) N N
S∈E ψS (xS )
xn
xf +1 · · ·
xn−1

N N
L(f +1)
L(n−1) N
[ψS (xS )]|Dom(Xn )|
S∈∂(n) ψS (xS )
xn
S ∈∂(n)
/
xf +1 · · ·
xn

L(f +1)
L(n−1) N
N
N
[ψS (xS )]|Dom(Xn )|
S ∈∂(n)
/
xf +1 · · ·
xn
S∈∂(n)
xn ψS (xS )
|
{z
}
{z
}
|
L(f +1)

···

′
ψS

(8)

′
ψS−{n}

def

|Dom(Xn )|

Thus, in Case 2, the new FAQ instance has as its input the factors ψS′ = ψS

for S 6∈ ∂(n), and the

def

′
factors ψS−{n}
(xS−{n} ) = ⊗xn ψS (xS ). We discuss how to compute these new factors in turn.
First, consider S ∈
/ ∂(n). When “passing through” a product aggregate, the factors ψS for S ∈
/ ∂(n)
are powered up, point-wise, by a power of |Dom(Xn )|. By repeated squaring, the number of multiplications
needed is within
X
2 · kψS k · ⌈log2 |Dom(Xn )|⌉.
S∈En −∂(n)

So these factors are generally changed to new factors with the same size.
There is one case in which we do not have to power them up: when ψS (xS ) is an idempotent element under
the product aggregate ⊗. In particular, if we knew that ψS (xS ) ∈ {0, 1} for all xS , then ψS (xS )|Dom(Xn )| =
ψS (xS ) and we can factor out ψS as in the semiring case. This is indeed the case for the instances of FAQ
that were reduced from QCQ and #QCQ as shown in Example A.20 and Example 1.3. Motivated by those
two examples, we define the following concept.
Definition 5.2 (Idempotent product aggregate). An aggregate ⊕(k) is called an idempotent product aggregate
with respect to the input variable ordering if it is a product aggregate in which for all S ∈ Ek \ ∂(k), the
(intermediate) factor ψS has as its range the idempotent elements of the operator ⊗. In particular, if
ψS (xS ) ∈ {0, 1} for all S ∈ Ek \ ∂(k), then ⊕(k) is an idempotent product aggregate whenever ⊕(k) = ⊗.
Note again that for the FAQ instances which are constructed from the reductions from QCQ and #QCQ,
all product aggregates are idempotent. In such a case, we can rewrite (8) as

N
N
L +1)
L(n−1) N
ψS (xS )
ϕ(x[f ] ) = (f
S∈∂(n)
xn ψS (xS ) .
S ∈∂(n)
/
xf +1 · · ·
xn
{z
}
|
′
ψS−{n}

16

′
Second, consider S ∈
/ ∂(n). The factor ψS−{n}
can be thought of as a “product marginalization” of ψS ,
where we “marginalize out” the Xn variable. Since we can compute these factors individually, we do not
′
have to solve the costly intermediate FAQ-SS instance ψU
as was done in Case 1.
n −{n}

5.2.3

Output representation

Every time InsideOut eliminates a variable, it obtains a new FAQ instance with one less variable. Let
Hn = H, Hn−1 , . . . denote the multi-hypergraphs of the resulting instances; i.e., Hk is the hypergraph of the
FAQ instance just before we eliminate the kth variable. We shall define the hypergraph sequence formally
below. Before then, we describe how the output is computed.
Let Hf = (Vf = [f ], Ef ) denote the hypergraph of the FAQ instance resulting from eliminating all bound
variables. With some abuse of notation, let ψS , S ∈ Ef denote the set of input factors to the Hf instance.
The output to FAQ is now the expression
N
(9)
ϕ(x[f ] ) = S∈Ef ψS (xS ),

which is an FAQ instance with all free variables. We can compute the output directly by running OutsideIn
on (9). However, inspired by Olteanu and Závodný [73] we can first compute the output in the factorized
representation, and then report it.
Intuitively, the idea is that we can first compute the set of tuples x[f ] for which ϕ(x[f ] ) 6= 0, and then
for each such tuple compute its value ϕ(x[f ] ) using (9) by simply multiplying together the corresponding
ψS -values. Computing the non-0 output tuples is a join problem, which in the FAQ setting is the (∪, ∩),
(∨, ∧), or ( 01 , ⊗) semiring under D = {0, 1} where 01 is the 01-OR operator defined below.
Definition 5.3 (01-OR). Define the 01-OR operator, denoted by 01 , as follows. Given a, b ∈ {0, 1},
(
0 if a = b = 0
a 01 b =
1 otherwise.
Clearly ( 01 , ⊗) is a semiring under the domain {0, 1}. We use this semiring to realize our intuition above
as follows. We continue running InsideOut to compute the following constant9 , whose value belongs to {0, 1}.
O
ψS/S (xS ).
ϕ() = 01
x[f ] S∈Ef

As before, when eliminating variables Xf , Xf −1 , . . . , X1 , we will obtain intermediate factors ψUk −{k} for
k = f, f − 1, . . . , 1. However, in this case we keep around a tiny bit more book-keeping information; for
k = f, f − 1, . . . , 1, we compute the following two intermediate factors
O
ψUk (xUk ) =
ψS/Uk (xS∩Uk )
(10)
S∈Ek
S∩Uk 6=∅

ψUk −{k} (xUk −{k} ) =

01 ψUk (xUk ).

(11)

xk

Computing ψUk (xUk ), defined in (10), is no extra work for the OutsideIn algorithm, which computes all points
xUk for which ψUk (xUk ) 6= 0 anyhow. We just need to keep it around more explicitly in this case. Note also
that U1 − {1} = ∅, and ψU1 −{1} = ϕ.
Finally, we run OutsideIn on the following expression instead of (9)


!
f
O
O
ϕ(x[f ] ) = 
ψS (xS ) ⊗
ψUk (xUk ) .
(12)
S∈Ef

9A

k=0

nullary function is a constant.

17

The fact that (9) defines exactly the same function as (12) follows from the following trivial observation: for
every fixed tuple x[f ] , ψS (xS ) 6= 0 for all S ∈ Ef implies ψS/S (xS ) = 1 for all S ∈ Ef , which in turns implies
ψUk (xUk ) = 1, for all k ∈ [f ].
Eliminating free variables and then recovering them back by (12) are equivalent to the two phases of
Yannakakis algorithm [90]. Our implementation of InsideOut in LogicBlox follows the elimination/recovery
method. The reason OutsideIn is faster on (12) than on (9) is that the factors ψUk help filter out potential
tuples x[f ] for which ϕ(x[f ] ) = 0. We will see in the analysis below the effect of this idea in the overall
runtime. One nice consequence of this strategy is that, in essence, “freeness” (of variables) is also a semiring
aggregate. The entire algorithm is sketched out in Algorithm 1.
Algorithm 1 InsideOut for FAQ
Require: Hypergraph H = (V, E), factors ψS , S ∈ E, set F = [f ] of free variables
Require: FAQ query ϕ in the form (1)
1:
2:
3:
4:
5:

En ← E
for (k ← n downto 1) do
∂(k) ← {S | S ∈ Ek and k ∈ S}
(k)
if k > f and
[(D, ⊕ , ⊗) is a semiring or k ≤ f then
S
Uk ←
S∈∂(k)

6:

if k > f then

ψUk −{k}(xUk −{k} ) =

7:

else
ψUk (xUk ) =

8:
9:

O

L(k)
xk




O

S∈∂(k)






ψS (xS ) ⊗ 


O

S∈Ek −∂(k),
S∩Uk 6=∅




ψS/Uk (xS∩Uk )


ψS/Uk (xS∩Uk )

S∈Ek ,
S∩Uk 6=∅

ψUk −{k} (xUk −{k} ) = 01 ψUk (xUk )

10:

xk

11:
12:
13:
14:
15:
16:
17:
18:
19:

Ek−1 ← (Ek \ ∂(k)) ∪ {Uk − {k}}
else
for each S ∈ ∂(k) do
N
Compute the product marginalization factors ψS−{k} (xS−{k} ) = xk ψS (xS )

for each S ∈ Ek − ∂(k) do
if Range of ψS is not idempotent wrt ⊗ then
ψS (xS ) = ψS (xS )|Dom(Xk )| , for all xS where ψS (xS ) is not ⊗-idempotent
Ek−1 ← (Ek \ ∂(k)) ∪ {S \ {k} | S ∈ ∂(k)}
Output ϕ by running OutsideIn on FAQ-expression (12)

5.3

Analysis

Definition 5.4 (Elimination hypergraph sequence). Algorithm 1 defines a sequence of hypergraphs Hk =
(Vk = [k], Ek ), for k = n, n − 1, . . . , 1 recursively. The algorithm also defines the sets Uk and ∂(k). Formally,
def
let Hn = ([n], En ) = H, ∂(n) and Un be defined as in (5) and (6). For k = n − 1, . . . , 1, construct Hk from
Hk+1 as follows:
[
S.
Vk = Vk+1 − {k + 1}
∂(k) = {S ∈ Ek | k ∈ S}
Uk =
S∈∂(k)

18

• If ⊕(k+1) = ⊗, then Ek is obtained from Ek+1 by removing k + 1 from all edges in Ek+1 .
• Otherwise, we construct Hk = (Vk = [k], Ek ) by defining

Ek = (Ek+1 − ∂(k + 1)) ∪ Uk+1 − {k + 1} .

From these notations, and recalling the AGM-bound definition (3), the following is the main theorem of
this section.
Theorem 5.5. Suppose ϕ is an FAQ query whose hypergraph H = (V, E) has m edges and n vertices. Define
n
o
K := [f ] ∪ k | k > f, ⊕(k) 6= ⊗ .
(13)

For each k ∈ [n] − K, S ∈ Ek \ ∂(k), define
(
0
Idemk (ψS ) =
2⌈log2 |Dom(Xk )|⌉

if the range of ψS is idempotent w.r.t. ⊗
otherwise.

Then, the InsideOut algorithm (Algorithm 1) computes ϕ in time
log N · O

X

|Uk | · |{S ∈ Ek : S ∩ Uk 6= ∅}| · AGMHk (Uk )

k∈K

+

X

X

|S| · kψS k +

k∈K
/
S∈Ek \∂(k)

k∈K
/
S∈∂(k)




|S| · kψS k · Idemk (ψS ) + f (f + m)kϕk
 . (14)

Proof. The runtime of InsideOut is the sum of the runtimes of n variable elimination steps plus the time
needed to report the output at the end. For k = n, ..., 1, the cost of the kth-elimination step depends on
whether the kth variable aggregate is a product aggregate or not:
L(k) N
• If k > f and
= , then the runtime is the total time it takes to compute the intermediate factors
shown in (8), each of which is either O(|S| · kψS k · log N ) or O(|S| · kψS k · Idem(ψS , k) · log N ).
• If either k ≤ f , or k > f and the aggregate ⊕(k) is a semiring aggregate, then the runtime is dominated
by the OutsideIn algorithm’s runtime to compute the intermediate factor ψUk −{k} . From Theorem 5.1,
this runtime is bounded by O (|Uk | · |{S ∈ Ek : S ∩ Uk 6= ∅}| · AGMHk (Uk ) · log N ) .
The final invocation of OutsideIn on (12) reports the output (in listing representation) in linear time (modulo
a log factor) in kϕk, just like the output phase of Yannakakis algorithm. This is because the participations
of the factors ψUk , k ∈ {0, . . . , f } in the formula ensures that every binding of the backtracking search
algorithm is part of an output tuple.
In the above discussion and analysis of InsideOut, we eliminated the variables Xn , Xn−1 , . . . , X1 in the
order given by the input FAQ-expression (1). However, as Example 5.6 shows, there is no reason to force
InsideOut to follow this particular order. In particular, there might be a different variable ordering for which
the overall runtime of InsideOut is a lot smaller and the algorithm still works correctly on that ordering.
Example 5.6 (Effect of variable ordering on runtime). We illustrate InsideOut and the effect of different
variable orderings on the runtime of InsideOut with an example. Consider the following FAQ query (without
free variables).
YX
max max ψ{1,5} ψ{2,5} ψ{1,3,4} ψ{2,3,6} .
ϕ = max max
x1

x2

x3

x4

x5

x6

19

Here, the support of each factor determines the variables so we do not write down the parameters of each
factor for the sake of brevity. Also, in this example we consider D = R+ and every input factor has range D.
Now, a straightforward run of the InsideOut algorithm (Algorithm 1) using the variable ordering (X1 , . . . , X6 )
evaluates the above expression as follows.
YX
ϕ = max max
max max ψ{1,5} ψ{2,5} ψ{1,3,4} ψ{2,3,6}
x1

(re-write) =
(spent O(N )-time)

=

(re-write) =
(spent O(N 2 )-time) =
(re-write) =
(spent O(N )-time)

=

(re-write) =

x2

max max
x1

x2

max max
x1

x2

max max
x1

x2

max max
x1

x2

max max
x1

x2

max max
x1

x2

x3

x3

x3

x3

x6

x5

max ψ{1,5} ψ{2,5} ψ{1,3,4} ψ{2,3}
x5

x4

YX

x6

max ψ{1,5} ψ{2,5} ψ{1,3,4} max ψ{2,3,6}

x4

YX

ψ{1,3,4} ψ{2,3} max ψ{1,5} ψ{2,5}
x5

x4

YX
x3

ψ{1,3,4} ψ{2,3} ψ{1,2}

x4

Y

ψ{2,3} ψ{1,2}

Y

x2

ψ{2,3} ψ{1,2} ψ{1,3}

Y

ψ{2,3}

x3

!

(re-write) =

max ψ{1} max ψ{2} ψ̄{1,2}

(spent O(N )-time)

=

Y
x3

max max ψ{2} ψ̄{1,2} ψ{1}

(spent O(N 2 )-time) =

ψ{1,3,4}

x3

(spent Õ(N 2 )-time) =

x1

X
x4

x3

max max
x1

x5

x4

YX

ψ{1,2}

!

Y

ψ{1,3}

x3

!

x2

x2

x1

max ψ{1} ψ̄{1}
x1

ψ∅

Note that ψ̄1,2 (x1 , x2 ) = ψ1,2 (x1 , x2 )|Dom(X3 )| , for every (x1 , x2 ). The overall runtime of the algorithm is
Õ(N 2 ).
Next, let us see how a slight change in the assumption of the input factors allows us to conclude that the
aggregate on X3 is an idempotent product aggregate, and that allows for a different variable ordering to be
equivalent to the original variable ordering, and that helps reduce the overall runtime of InsideOut. Suppose
we knew that all input factors have range {0, 1}. Then, we can evaluate the query as follows.
YX
ϕ = max max
max max ψ{1,5} ψ{2,5} ψ{1,3,4} ψ{2,3,6}
x1

x2

(re-write) = max max
x1

(spent O(N )-time)

x2

= max max
x1

x2

(re-write) = max max
x1

x2

(re-write) = max max
x1

(spent O(N )-time)

x2

= max max
x1

x2

x3

x4

YX
x3

x4

YX
x3

x4

YX
x3

Y

x6

max ψ{1,5} ψ{2,5} ψ{1,3,4} max ψ{2,3,6}
x6

x5

max ψ{1,5} ψ{2,5} ψ{1,3,4} ψ{2,3}
x5

ψ{1,3,4} ψ{2,3} (max ψ{1,5} ψ{2,5} )
x5

x4

ψ{2,3} (max ψ{1,5} ψ{2,5} )
x5

x3

Y

x5

X

ψ{1,3,4}

x4

ψ{2,3} (max ψ{1,5} ψ{2,5} )ψ{1,3}

x3

20

x5

(re-write) = max max
x2

x1

(× is acting idempotently)
(spent Õ(N )-time)

= max max
x2

x1

Y

ψ{2,3}

!

ψ{2,3}

!

x3

Y
x3

!
!
Y
Y
(max ψ{1,5} ψ{2,5} )
ψ{1,3}
x3

x5

max ψ{1,5} ψ{2,5}
x5

x3



= max max ψ{2} max ψ{1,5} ψ{2,5} ψ{1}
x1

x2

x3

 Y

ψ{1,3}

!

x5

(re-arrange) = max max max ψ{2} ψ{1,5} ψ{2,5} ψ{1}
x2

x1

(a crucial re-arrangement)

x5

= max max max ψ{2} ψ{1,5} ψ{2,5} ψ{1}
x1

x5

x2

(re-arrange) = max max ψ{1,5} ψ{1} max ψ{2} ψ{2,5}
x5

(spent O(N )-time)

x1

x2

= max max ψ{1,5} ψ{1} ψ{5}
x5

x1

(re-arrange) = max ψ{5} max ψ{1,5} ψ{1}
x1

x5

(spent O(N )-time)

= max ψ{5} ψ̄{5}

(spent O(N )-time)

= ψ∅

x5

So in this case the fact that all factors inside the scope of × have ranges which are {0, 1}, the idempotent
elements of ×, we are able to reduce the runtime down to O(N ). The key is, if we ran InsideOut with the
variable ordering (X5 , X1 , X2 , X3 , X4 , X6 ) then we would have achieved a runtime of O(N ).
The main technical contributions of this paper lie in answering the following two questions:
1. How do we know which variable orderings are equivalent to the original FAQ-query expression?
2. How do we find the “best” variable ordering among all equivalent variable orderings in an efficient way
(i.e. better than brute-force search)?
The next sections formalize the above two questions.

5.4

Equivalent variable orderings

We first formalize the concept of “equivalent variable ordering”:
Definition 5.7 (EVO(ϕ)). Let ϕ be an FAQ-query written in the form (1). A ϕ-equivalent variable ordering
is a vertex ordering σ = (v1 , . . . , vn ) of the hypergraph H satisfying the following conditions:
(a) The set {v1 , . . . , vf } is exactly F = [f ]. In other words, in the ϕ-equivalent variable ordering, the free
variables come first (in any order).
(b) The function ϕ′ defined by
ϕ′ (xF ) :=

L(vf +1 )
xvf +1

···

L(vn ) N
x vn

S∈E

ψS (xS )

is identical to the function ϕ no matter what the input factors are.10
Let EVO(ϕ) denote the set of all ϕ-equivalent variable orderings.
In many applications, we know a specific class of input factors that are allowed in the corresponding
FAQ problem. For example, in logic applications the input factors are often {0, 1}-valued functions. This
motivates a stronger definition of EVO.
10 Here, we assume that the variable domains, the range D, and the aggregates are fixed and known in advance, but the input
factors are not.

21

Definition 5.8 (EVO(ϕ, F )). Let F be a class of functions with range D. Let EVO(ϕ, F ) denote the set of
all ϕ-equivalent variable orderings under the promise that all input factors come from F . In other words,
the definition of EVO(ϕ, F ) is the same as that in Definition 5.7, except that we only require ϕ′ to be the
same as ϕ for all input factors belonging to F .

5.5

FAQ-width of a variable ordering

We now address the second question of what it means to be the “best” variable ordering. With respect to the
analysis of InsideOut in Theorem 5.5, naturally the “best” variable ordering is a variable ordering in EVO(ϕ)
which minimizes the runtime (14). The EVO constraint makes it trickier to find an optimal variable ordering
for the general FAQ problem, as opposed to the typical variable elimination in the graphical model, matrix
computation, and constraint satisfaction domains where all variable orderings are in EVO(ϕ). To illustrate
this point, Section E in the appendix presents two examples (namely MCM and DFT) where minimizing
(14) is easy. These examples explain two entries in the summary Table 1.
In general, however, without knowing a bit more about the structure of the problem it is hard(er) to
derive a general result on how to find a variable ordering to minimize (14). In particular, in these examples
we have been lucky that every permutation of the variable aggregates yields an expression that is equivalent
to the original FAQ expression (1). This is because in these examples there is only one variable aggregate
which is the + operator. The second thing that helps with these examples is that we know (a good estimate
of) the sizes of the indicator projections; so we can plug them in expression (14). In general, these sizes are
highly instance-dependent.
Minimizing (14) is a bit unwieldy, thus we slightly relax the runtime analysis of InsideOut to obtain a
better behaved expression than that in (14). A proof of the following is in Appendix D.
Proposition 5.9. Following notations defined in Theorem 5.5, the InsideOut algorithm (Algorithm 1) compute ϕ in time


!
X


∗
Idem(ψS , k) · N maxj∈K ρH (Uj ) + f (f + m)kϕk
(15)
log N · O 

n nm +
k∈K
/
S∈Ek −∂(k)

In addition to to the term kϕk required to report the output, the key parameter that controls the
complexity of the algorithm is the quantity maxj∈K {ρ∗H (Uj )} . This quantity is a function of the variable
ordering X1 , . . . , Xn we chose to write the input query ϕ on. As aforementioned, there might be multiple
ways of writing the same FAQ query, leading to wildly different runtimes for InsideOut. We have seen this
effect in Example 5.6, and have formalized what an “equivalent ordering” means in the previous section.
The following definition follows naturally:
Definition 5.10 (Fractional FAQ-width of a variable ordering). Let σ be a ϕ-equivalent variable ordering.
Define the sequence of hypergraphs Hkσ along with the sets Ukσ as in Definition 5.4 (but with respect to σ).
The fractional FAQ width of a variable ordering σ is the quantity

faqw(σ) := max ρ∗H (Ujσ ) .
(16)
j∈K

From the above definition, we can interpret Proposition 5.9 as basically saying that InsideOut runs in
time Õ(N faqw(σ) + kϕk), where Õ hides a factor that is polynomial in query size and logarithmic in data size.
In the next few sections, we study the main problem of how to select a ϕ-equivalent variable ordering σ
with the minimum faqw(σ).
Definition 5.11. The following quantity is called the FAQ-width of an FAQ-query ϕ:
def

faqw(ϕ) = min {faqw(σ) | σ ∈ EVO(ϕ)}
22

In some cases, EVO(ϕ) consists of all n! permutations, making it “easy” to solve the above optimization
problem. Appendix F.1 presents several immediate consequences of this easy case. In particular, faqw generalizes fractional hypertree widths (fhtw, see [47]), because the following follows directly from Corollary 4.13:
Proposition 5.12. Let ϕ be an FAQ query with hypergraph H. If EVO(ϕ) contains all n! variable orderings,
then faqw(ϕ) = fhtw(H).
In general, however, the question of determining whether a given variable ordering σ belongs to EVO(ϕ)
is a tricky question to answer formally. In particular, the answer depends on what exactly we meant by a
variable aggregate, a factor aggregate, the variable domain sizes, and the range D. This difficulty is analogous
to the situation in logic when one wants to decide whether two (first-order, e.g.) formulas of specific forms
are logically equivalent [17]11 .
Our approach to solving this problem was outlined in Figure 1, and is summarized again as follows.
• We define a class of variable orderings for a given input FAQ-query ϕ. This class will be precisely the
set of linear extensions LinEx(P ) of a partially ordered set (poset) on variables called the precedence
poset P . The precedence poset is defined on a tree called the expression tree of the input query ϕ. The
expression tree can be constructed in polynomial time in query complexity.
• We show that every variable ordering in LinEx(P ) is ϕ-equivalent. This is the “soundness” of LinEx(P ).
• We define a combinatorial notion called component-wise equivalence, which is a relation between pairs of
variable orderings. We show that component-wise equivalence preserves EVO-membership and preserves
faqw.
• We show that every variable ordering in EVO is component-wise equivalent to some ordering in
LinEx(P ). This is called “strong completeness” of LinEx(P ). In particular, by tracing component-wise
equivalent variable orderings starting from LinEx(P ), one can list all of EVO in exponential time and
find the ordering that minimizes faqw. (Moreover, by directly applying the definition of component-wise
equivalence, we can check whether a given variable ordering is in EVO in polynomial time.)
• However, we can do better. We prove that LinEx(P ) variable orderings is all we need to consider,
because every ϕ-equivalent variable ordering σ either belongs to LinEx(P ) or faqw(σ) = faqw(π) for
some π ∈ LinEx(P ). This shows the “completeness” of LinEx(P ) as far as the width is concerned.
The completeness result rests on the assumption that different variable aggregates do not commute.
(Even this simple statement needs clarification, which is done in Proposition 6.6.) Because the final result is
a bit technically involved, we present our results incrementally in several stages, by relaxing one assumption
at a time. Each time an assumption is relaxed, a couple of ideas are introduced to deal with the relaxation.
It should be noted, however, that in the end there is only one theorem and one algorithm.
In Appendix F.1 we describe the above steps when applied to FAQ-SS without free variables (i.e.
SumProd), which is the case when determining EVO(ϕ) is trivial. Appendix F.2 covers a simple but nontrivial case when ϕ has two blocks of semiring aggregates. The reader who would like to read at a slower
pace can start with those two sections in the appendix, where we also connect our results to known results
in PGM, joins, Yannakakis algorithm, and #CQ.
In Section 6.1, we present our solution for the case when there is an arbitrary number of semiring
aggregates but no product aggregates. This is when the idea of an expression tree is introduced. Finally, in
Sections 6.2 and 6.3 we cover the most general cases.
11 We

thank Balder ten Cate for pointing out to us the essence of the difficulty and the reference.

23

6

Characterizing equivalent variable orderings

6.1

FAQ with only semiring aggregates

This section presents the characterization of EVO results for FAQ where every variable aggregate forms a
semiring with the product aggregate. (Note that there can be an arbitrary number of different types of
semirings.) In particular, we consider the FAQ-query of the form
ϕ(x[f ] ) =

L(f +1)
xf +1

···

L(n) N
xn

S∈E

ψS (xS )

(17)

where (D, ⊕(i) , ⊗) is a semiring for every i > f (i.e. the set K as defined in (13) is [n]).
The main aim in this section is to illustrate the key technical idea of the expression tree. The expression
tree defines the precedence poset. One key component of our completeness results is the notion of componentwise equivalence between two variable orderings. Component-wise equivalence preserves FAQ-width and
ϕ-equivalence. We will show two important facts about the precedence poset:
• (Soundness) Every linear extension of the precedence poset is a ϕ-equivalent variable ordering.
• (Completeness) Every ϕ-equivalent variable ordering is component-wise equivalent to (hence has the
same FAQ-width as) some linear extension of the precedence poset. Therefore, EVO(ϕ) is completely characterized using component-wise equivalence and the precedence poset. Moreover, to compute/approximate faqw(ϕ), we only need to consider linear extensions of the precedence poset.
In Section 7, we will use the structure of the expression tree to compute a variable ordering to approximate
faqw(ϕ), using an approximation algorithm for fhtw as a blackbox. Thus, the expression tree is crucial in
guiding the construction of a good variable ordering.
6.1.1

Expression tree and and precedence poset

The expression tree is defined on a sequence of tagged variables along with a hypergraph. In such a sequence,
every vertex i (or equivalently variable Xi ) is tagged with its corresponding operator ⊕(i) ; or, if the variable
is a free variable then its tag is free. Given a sequence σ of tagged variables, a tag block is a maximal
subsequence of consecutive variables in σ with the same tag. The first tag block of a sequence σ of tagged
variables is the longest prefix of σ consisting of variables of the same tag.
Definition 6.1. (Expression tree) The expression tree for ϕ is a rooted tree P . Every node of the tree is a
set of variables. We construct the expression tree using two steps: the compartmentalization step and the
compression step. In the compartmentalization step, we construct the expression tree based on the connected
component structures of the FAQ-query relative to the hypergraph structure H. In the compression step we
collapse the tree to make it shorter whenever possible.
Compartmentalization. In this step, initially we start off with the sequence of variables with their
corresponding tags exactly as written in (17). In particular, the sequence starts with f free variables (whose
tags are ‘free’), and then the i’th variable with tag ⊕(i) for i = f + 1, . . . , n. For technical reasons, we add a
dummy variable X0 to the beginning of the sequence with a free tag too. So the sequence we start off with
is the following
D
E
σ = (X0 , ‘free’), . . . , (Xf , ‘free’), (Xf +1 , ⊕(f +1) ), . . . , (Xn , ⊕(n) ) .

The vertex X0 is an isolated vertex of the hypergraph H. Now given a tagged variable sequence σ and a
hypergraph H, we build the tree by constructing a node L containing all variables in the first tag block L of
σ. This node L will be the root of the expression tree. (The effect of the dummy variable X0 is that, even if
the original query has no free variable, the first block L still has X0 in it.) If L contains all variables already,
then naturally the tree has only one node. Otherwise, for each connected component C = (V(C), E(C)) of
H − L we construct a sequence σC of tagged variables by listing all variables in V(C) in exactly the same
relative order as they appeared in σ. From the sequence σC and the hypergraph C, we recursively construct
24

the expression tree PC . Finally, we connect all the roots of (sub)expression trees PC to the node L. This
completes the compartmentalization step. After everything is done, we also remove the dummy variable X0
from the expression tree P . If originally there was no free variable, the tree has an empty root node and the
subtrees correspond to the connected components of H. (See Example 6.2 and Figure 2.)
Compression. Now, in the expression tree P that resulted from the compartmentalization step, as long
as there is still a node L whose tag is the same as a child node L′ of the tree P , we merge the child into L;
namely, we set L := L ∪ L′ , remove L′ , and connect all subtrees under L′ to become subtrees of L. Repeat
this step until no further merging is possible. (See Figure 3.)
Note that the compression step can make some nodes L larger and the final tree T shorter than the
tree that resulted from the compartmentalization step alone. This step is crucial for getting the correct
expression tree. If ϕ is an instance of FAQ-SS, then P is a tree of depth ≤ 1 where the root node contains
all free variables (if any) and its children (if any) contain the rest of the variables.
Example 6.2 (Intuition
P behind expression tree). Consider the following FAQ query that has two different
semiring aggregates ( and max) and no free variables:
XX
XX
max max ψ12 ψ135 ψ14 ψ246 ψ27 ψ37 .
max
ϕ=
x1

x2

x3

x4

x5

x7

x6

(ψ12 above denotes a factor whose support is {X1 , X2 }, and so on.) The hypergraph of ϕ is depicted in
Figure 2a. The compartmentalization step of the construction of the expression tree is depicted in Figures 2b
through 2d. Figures 3a and 3b depict the compression step. The final expression tree appears on the right
of Figure 3b.
Definition 6.3. (Precedence poset) The expression tree defines a partial order on the variables. Abusing
notation we will also use P to denote the partial order ([n], ). In this poset, u ≺ v whenever u ∈ L, v ∈ L′ ,
and L′ is a (strict) descendant of L in the expression tree P . In particular, variables in the same node of the
expression tree are not comparable in this partial order. We call this partial order the precedence poset. Let
LinEx(P ) denote the set of all linear extensions of the poset.
6.1.2

What makes two aggregates different?

Before proving soundness and completeness, we need a small technical detour. Recall that aggregates are
simply binary operators under D.
¯ are different if there is a pair a, b ∈ D such
Definition 6.4. (Different aggregates) Two aggregates ⊕ and ⊕
that
¯
a ⊕ b 6= a⊕b.
Otherwise they are identical.
¯ are said to be commutative if for every
Definition 6.5. (Commutative aggregates) Two aggregates ⊕ and ⊕
¯ ⊕ d) = (a⊕c)
¯ ⊕ (b⊕d).
¯
a, b, c, d ∈ D, we have (a ⊕ b)⊕(c
Recall that in FAQ, all semirings share the same 0 (since one ‘0’ must annihilate the rest). Thus, if we
¯ = b ⊕ c, for every b, c ∈ D. This means
select a = d = 0 in the above equality, then we obtain b⊕c
Proposition 6.6. Commutative aggregates are identical aggregates. Conversely, non-commutative aggregates are different aggregates.
(Note that it is possible for semantically different aggregates to be identical under D by accident. For
example, in the {0, 1} domain min and × are identical.) In this paper, we assume that two different aggregates
in the input FAQ-expression are not functionally identical. Recall that we also assumed |Dom(Xi )| ≥ 2 for
every i ∈ [n] (otherwise the aggregate on that Xi is trivial and can be ignored).
25

5

1

4

2

6

3

7

(a) ϕ =

XX
x1

5

x2

1

max
x3

XX
x4

x5

max max ψ12 ψ135 ψ14 ψ246 ψ27 ψ37
x6

x7

1, 2

4

2

(b) ϕ =

XX

ψ12

x2

1

max
x3

X
x5

max ψ135 ψ27 ψ37
x7

!

X
x4

(c) ϕ =

XX

ψ12

x2

1

max
x3

5
X
x5

!

ψ135 max ψ27 ψ37
x7

P

x6

x4

5

6

x1

x2

ψ12

max
x3

!

1, 2
3

XX

max

max ψ14 ψ246

3

(d) ϕ =

4, 6
7

X

X
x5

ψ135 max ψ27 ψ37
x7

!

7

max

ψ14 max ψ246

x4

P

4

max

P

X

P

max

4

2

!

1, 2

6

x1

7

x6

3
2

5

max ψ14 ψ246

4

3

7

4, 6

6

x1

5

P

3, 5, 7

3

7

!

x6

6

P

max

!

Figure 2: The compartmentalization step of the expression
tree from
6.2, depicted using colors.
XX
X Example
X
(2a) depicts the hypergraph of the FAQ query: ϕ =
max
max max ψ12 ψ135 ψ14 ψ246 ψ27 ψ37 .
x1

x2

x3

x4

x5

x6

x7

For simplicity, the dummy free variable X0 is ignored in this example. (2b) shows the first part of the
compartmentalization step, where the first tag block is L = {1, 2}. After removing L, the query breaks
into two connected components: the red and the blue. The expression tree at this point appears on the
right. Each color is used to denote correspondence between parts of the query expression, hypergraph, and
expression tree having that color. (2c) shows how to apply compartmentalization recursively on the red
component, while (2d) shows the blue component compartmentalization.
26

5

1

1, 2

4

3, 7

3

7

2

(a) ϕ =

XX
x1

5

5

6

ψ12

x2

1

max max ψ27 ψ37
x3

x7

X

ψ135

x5

!

X

x6

2

5

6

XXX
x1

x2

x4

ψ12 ψ14

max max ψ27 ψ37
x3

x7

X
x5

ψ135

!

P

6

max

6

max

!

1, 2, 4
3, 7

(b) ϕ =

P

4

3

7

4

max

ψ14 max ψ246

x4

P

max

P

P

max ψ246
x6

!

Figure 3: The compression step of the expression tree from Example 6.2. Recall that Figure (2d) (right)
depicted the expression tree at the end of the compartmentalization step. (3a) shows a compression where
node {7} is merged into its parent {3} (since they both have the same tag “max”). (3b) shows another
compression where {4} is merged into {1, 2}. Since no further compression is possible, (3b) (right) depicts
the final expression tree.

27

¯ are different binary operators (under the domain D), then for every
Proposition 6.7. Suppose ⊕ and ⊕
i, j ∈ [n], there is a function φij : Dom(Xi ) × Dom(Xj ) → D for which
L̄
L̄
L
L
φij (xi , xj ) 6=
φij (xi , xj ).
(18)
xi ∈Dom(Xi ) xj ∈Dom(Xj )

xj ∈Dom(Xj ) xi ∈Dom(Xi )

Proof. From the analysis above, the two operators do not commute. Hence, there are four members a, b, c, d ∈
¯ ⊕ d) 6= (a⊕c)
¯ ⊕ (b⊕d).
¯
D so that (a ⊕ b)⊕(c
Fix arbitrary elements x1i 6= x2i ∈ Dom(Xi ) and x1j 6= x2j ∈
Dom(Xj ). Define

a if (xi , xj ) = (x1i , x1j )



2
1


b if (xi , xj ) = (xi , xj )
1
φij (xi , xj ) = c if (xi , xj ) = (xi , x2j )
(19)


2
2

d if (xi , xj ) = (xi , xj )



0 otherwise.
L̄ L
L L̄
¯ ⊕ (b⊕d)
¯ 6= (a ⊕ b)⊕(c
¯ ⊕ d) = x
Then, xi xj φij (xi , xj ) = (a⊕c)
xi φij (xi , xj ).
j
(I)

Given i, j ∈ [n], x1i 6= x2i ∈ Dom(Xi ), x1j 6= x2j ∈ Dom(Xj ), we define an ‘identity’ function φij :
Dom(Xi ) × Dom(Xj ) → D as follows.
(
1 if (xi , xj ) = (x1i , x1j ) or (xi , xj ) = (x2i , x2j )
(I)
φij (xi , xj ) =
(20)
0 otherwise.

We will use both φij and φIij in the proofs below.
6.1.3

Soundness and completeness

We are now fully equipped to show that LinEx(P ) is sound.
Theorem 6.8 (LinEx(P ) ⊆ EVO(ϕ)). Every linear extension of the precedence poset P is ϕ-equivalent.
Proof. Let P be the expression tree constructed using only the compartmentalization step. This expression
tree already defines a poset on variables. We will first show that every linear extension of this compartmentalization poset is ϕ-equivalent. We prove this claim by induction on the number of tag blocks of the input
sequence. Let σ denote the input sequence of tagged variables with input hypergraph H.
In the base case σ has only one tag block. All variables in the sequence belong to the same node of the
compartmentalization expression tree. This means every permutation of variables is a linear extension of
the poset, which is what we expect because every permutation is ϕ-equivalent.
In the inductive step, suppose σ has at least two tag blocks with the first block being the set L of variables.
Then, each sub-sequence 
σC for each connected component of H − L defines an FAQ-expression ϕC on the
set of conditional factors ψS (· | xL ) | S ∈ E ∧ S ∩ V(C) 6= ∅ . When we condition on the first L variables,
the expression ϕ(· | xL ) completely factorizes into a product of the FAQ-expressions ϕC . (Another way to
put this is that ϕ can be written as a series of aggregates on variables in L, with a product of ϕC inside.) By
induction, every linear extension of the compartmentalization poset for σC is ϕC -equivalent. Those linear
extensions can be put together in an arbitrary interleaving way to form ϕ(· | xL ). This observation completes
the proof of the claim, because every linear extension of the expression poset for ϕ consists of variables in
L, followed by arbitrary interleavings of linear extensions of the expression posets for the ϕC .
Next, we consider the expression tree after the compression step. We show that every linear extension
of the final precedence poset is ϕ-equivalent by induction on the number of merges of a child node L′ to
a parent node L (which both must have the same tag). To see this, we can take a linear extension σ of
the expression tree before the merge where all variables in L and in L′ are consecutive in σ. Then, because
all variables in L ∪ L′ have the same tag, we can permute them in any way and still obtain a ϕ-equivalent
variable ordering.
28

It would have been nice if every ϕ-equivalent variable ordering is a linear extension of P . Unfortunately
this is not true. Consider the following FAQ-query
X
XX
max max
ψ15 ψ25 ψ13 ψ24 ,
ϕ=
x3

x2

x1

x4

x5

where all factors have range R+ so that all variables are semiring variables. In this case the expression tree
has three nodes: one empty root, a node containing {1, 2, 5} and two children {3} and {4}. The linear
extensions will enforce that X1 , X2 , X5 come before X3 and X4 . However, it is easy to see that we can
rewrite ϕ as follows.
XX
X
ϕ =
max max
ψ15 ψ25 ψ13 ψ24
x1

=

x5

=

x2

x1

x1

x5

max max ψ15 ψ25 ψ13 ψ24
x3

x2

X X
x5

x4

x3

XXX

x4

max ψ15 ψ13
x3

!

·

X
x2

max ψ25 ψ24
x4

!

.

This means when conditioned on X5 , the expression factorizes and we can multiply them back allowing for
4 to come before 1, or for 3 to come before 2; namely,
X
XX
max
max ψ15 ψ25 ψ13 ψ24
ϕ =
x5

=

x2

XX
x5

x1

x4

max
x3

x1

X
x2

x3

max ψ15 ψ25 ψ13 ψ24 .
x4

However, it can be verified that
faqw(5, 1, 3, 2, 4) = faqw(5, 2, 4, 1, 3) = faqw(σ)
for any σ ∈ LinEx(P ) where 5 comes first in σ, and where P is the expression tree of the query. Note that
we can take the linear extensions of the factorized components {1, 3} and {2, 4} and interleave them in any
way, as long as we still respect their relative order within each component. However, these interleavings do
not add anything of value as far as the faqw is concerned.
Another way to think about the above example is that we could have arbitrarily selected one variable
in the first tag block of ϕ, construct a compartmentalization expression tree with that variable as the root.
(One variable at a time instead of one tag block at a time.) Then, by the same reasoning we used in the
proof of Theorem 6.8, every linear extension of this ‘variable-wise’ poset is ϕ-equivalent. However, this idea
alone also does not work because it will forbid the selection of X5 as the first variable in the above example.
Thus, it is crucial that we construct the compressed expression tree first, to determine which variable can
come first in a ϕ-equivalent variable ordering. Ultimately, the set LinEx(P ) gives us a canonical way of listing
the variable orderings that really matter in evaluating ϕ.
In what follows, we implement the above informal discussion and intuition by showing that every ϕequivalent variable ordering has the same width as some ordering in LinEx(ϕ). The following lemma says
that the expression tree indeed gives us a complete list of variables that can occur first (after the free
variables) in any ϕ-equivalent ordering.
Lemma 6.9. For every variable ordering π = (u1 , . . . , un ) ∈ EVO(ϕ), the variable uf +1 must belong to a
child node of the root of the expression tree.12
12 Recall that {u , . . . , u } are the free variables, which are located in the root of the expression tree. And, if f = 0 then the
1
f
root of the expression tree is empty.

29

Proof. Let ϕπ denote the function defined by the FAQ-query with π as the variable ordering (over the same
input factors as ϕ). Our aim is to show that if the conclusion of the lemma does not hold then there exist
input factors ψS for which ϕπ 6≡ ϕ.
Suppose for the sake of contradiction that uf +1 belongs to a node L whose parent is Lp , and Lp is not
the root of the expression tree P . Let La denote union of all the (strict) ancestors
of Lp in the expression

tree. From the construction of the expression tree, the vertices in the set uf +1 ∪ Lp belong to the same
connected component of the graph H − La . Let i0 := uf +1 , i1 , . . . , ik ∈ Lp be the shortest path in the
Gaifman graph of H − La from uf +1 to Lp . Then, the vertices i1 , . . . , ik−1 do not belong to Lp ∪ La ; and,
there are distinct hyperedges S1 , . . . , Sk of H such that {ij−1 , ij } ⊆ Sj for all j ∈ [k].
For each variable ℓ ∈ {i0 , . . . , ik }, we fix two arbitrary values x1ℓ 6= x2ℓ ∈ Dom(Xℓ ) and for each ℓ′ ∈
L L(i0 )
=
and
[n] \ {i0 , . . . , ik }, we fix one arbitrary value eℓ′ ∈ Dom(Xℓ′ ). For the sake of brevity, denote
L̄ L
= (ik ) .
Now, we construct an input set of factors ψS , S ∈ E, for which ϕπ 6≡ ϕ.
• Define the factor ψSk by

′

φik−1 ik (xik−1 , xik ) if xℓ′ = eℓ′ for all ℓ
ψSk (xSk ) :=
∈ Sk \ {i0 , . . . , ik }


0
otherwise,

where φik−1 ik is the function defined in (19).
• For every j ∈ [k − 1], define

(I)

 (I)
′

φij−1 ij (xij−1 , xij ) if xℓ′ = eℓ′ for all ℓ
ψSj (xSj ) :=
∈ Sj \ {i0 , . . . , ik }


0
otherwise,

where φij−1 ij is the ‘identity’ function defined in (20). (Think of these factors as little 2 × 2 identity
matrices.)
• Finally, for every S ′ ∈ E \ {S1 , . . . , Sk }, define
(
1 if xℓ′ = eℓ′ for all ℓ′ ∈ S ′ \ {i0 , . . . , ik }
ψS ′ (xS ′ ) :=
0 otherwise.
Because i0 is the first in π after the free variables, ϕπ (e1 , . . . , ef ) will evaluate to the left hand side of (18).
(Imagine running the InsideOut algorithm to evaluate ϕπ .) Next, to get a contradiction, we pick an ordering
σ ∈ LinEx(P ) such that i0 precedes all variables that are at the same or lower level in the expression tree.
By Theorem 6.8, we know that σ ∈ EVO(ϕ). In σ, ik precedes i0 which in turn precedes all of {i1 , . . . , ik−1 }.
Hence, when we compute ϕ(e1 , . . . , ef ) using the ordering σ (and the InsideOut algorithm) we get the right
hand side of (18). Thus, ϕπ 6≡ ϕ as desired.
The next definition realizes the intuition that if we construct the precedence tree using the one-variableat-a-time strategy (as opposed to the one-tag-block-at-a-time strategy), then we can interleave the linear
extensions of connected components arbitrarily and still get a variable ordering which is ϕ-equivalent with
the same FAQ-width. Since the interleaving can happen at any level, the definition is inductive.
Definition 6.10. (Component-wise equivalence) Let ϕ be an FAQ-query where all variable aggregates are
semiring aggregates. Let σ = (v1 , . . . , vn ) ∈ EVO(ϕ) be a variable ordering. Let π = (u1 , . . . , un ) be another
variable ordering with {u1 , . . . , uf } = F . Then, π is said to be component-wise equivalent (or CW-equivalent)
to σ if and only if:
30

• either n = 1,
• or H has ≥ 2 connected components, and for each connected component C = (V(C), E(C)) of H, πC
is CW-equivalent to σC , where σC (respectively, πC ) is the variable ordering of V(C) that is consistent
with σ (respectively, π),
• or u1 = v1 , and for each connected component C = (V(C), E(C)) of H − {v1 }, πC is CW-equivalent to
σC , where σC (respectively, πC ) is the ordering of V(C) that is consistent with σ (respectively, π).
Given a set of variable orderings Λ ⊆ EVO(ϕ), we use CWE(Λ) to denote the set of all variable orderings
that are CW-equivalent to some variable ordering in Λ.
Proposition 6.11. Let π be a variable ordering that is CW-equivalent to σ ∈ EVO(ϕ). Then, we have
π ∈ EVO(ϕ) and faqw(σ) = faqw(π).
Proof. Due to the fact that the different (conditional) connected components do not interact, when we run
InsideOut on σ and π for all k ∈ [n], we have Ukσ = Ukπ . This observation proves both claims.
The following theorem shows the completeness part.
Theorem 6.12 (EVO(ϕ) = CWE(LinEx(P ))). A variable ordering σ is ϕ-equivalent if and only if it is
CW-equivalent to some linear extension of the precedence poset P .
Proof. We only need to show that EVO(ϕ) ⊆ CWE(LinEx(P )) because the reverse containment follows from
Proposition 6.11 and Theorem 6.8. Also, without loss of generality we can assume that the root of the
expression tree F is empty, and it has one child node L. (If there were different connected components, they
can interleave arbitrarily and we prove each of them separately.)
Fix an arbitrary σ = (v1 , . . . , vn ) ∈ EVO(ϕ). Then v1 ∈ L by Lemma 6.9. For each connected
component C of H − {v1 }, define a sub-query ϕC with variable ordering σC on the conditional factors
{ψS (· | xv1 ) | S ∈ E ∧ S ∩ V(C) 6= ∅} , where σC is the subsequence of σ obtained by picking out vertices in
V(C). Let PC be the precedence poset of the expression tree for ϕC . By induction on the number of variables,
we know σC ∈ EVO(ϕC ) ⊆ CWE(LinEx(PC )). Hence, there exists πC ∈ LinEx(PC ) that is CW-equivalent to
σC .
The expression tree PC for ϕC consists of an empty root (with ‘free’ tag). This root has only one child
node LC . The subtree rooted at LC is called an LC -subtree. Now, if we attach all the roots of all the
LC -subtrees together, we will create a tree whose root R is the union of the LC . Then, we add v1 to the
root R and add an empty parent to R then we will obtain exactly the expression tree P .
From this observation, we can pick a variable ordering π that is consistent with all πC such that π starts
with v1 , followed by variables in L − {v1 }. It follows that π ∈ LinEx(P ) and π is CW-equivalent to σ.
Now, we give an example of component-wise equivalence (Definition 6.10) and the role it plays in completeness (Theorem 6.12).
Example 6.13 (Component-wise P
equivalence and completeness). Consider the following FAQ query with
two different semiring aggregates ( and max) and three variables, all are bound.
X
X
max
ϕ=
ψ12 ψ13 .
x1

x2

x3

(ψij above denotes an input factor whose support is {Xi , Xj }.) For this query,
EVO(ϕ) = {(1, 2, 3), (1, 3, 2), (3, 1, 2)}.
P
Ignoring the dummy free variable X0 , the expression tree of ϕ consists of a root with the tag ‘ ’ containing
the variables {X1 , X3 } and a single child node with tag ‘max’ containing {X2 }. Therefore, LinEx(P ) =
31

{(1, 3, 2), (3, 1, 2)} ⊆ EVO(ϕ), as suggested by Theorem 6.8. Note that the original ordering (1, 2, 3) ∈
/
LinEx(P ). However, (1, 2, 3) is component-wise equivalent to (1, 3, 2) (See Definition 6.10). Therefore,
CWE(LinEx(P )) = {(1, 3, 2), (1, 2, 3), (3, 1, 2)} = EVO(ϕ),
just as predicted by Theorem 6.12. Moreover, by Proposition 6.11, faqw((1, 2, 3)) = faqw((1, 3, 2)) = 1.
Therefore, when searching for the variable ordering with the best FAQ-width, the ordering (1, 2, 3) is redundant, hence it is sufficient to consider LinEx(P ), just as suggested by Corollary 6.14.
Proposition 6.11 and Theorem 6.12 imply the following result, which is precisely what we need to approximate faqw(ϕ) in Section 7.1.
Corollary 6.14. faqw(ϕ) = min {faqw(σ) | σ ∈ LinEx(P )} .

6.2

FAQ with an inner FAQ-formula closed under idempotent elements

Now, we generalize the results of Section 6.1 to FAQ-expressions that have “idempotent” product aggregates
(in addition to semiring aggregates). In particular, this section considers FAQ-expressions of the following
special form (that is still more general than that of Section 6.1).
6.2.1

Problem specification

Before defining the special case of FAQ that we solve in this section, we need to define and clarify a couple
of concepts. Let DI ⊆ D be a set of idempotent elements of ⊗ under the domain D. A variable aggregate
⊕ is said to be closed under DI if a ⊕ b ∈ DI whenever both a and b belong to DI . (Recall that ⊕ may or
may not be the same as ⊗). In the FAQ context, the two elements 0 and 1 are idempotent elements of ⊗.
Hence, the canonical example is DI = {0, 1}: max and × are closed under {0, 1}, ∨ and ∧ are closed under
{true, false}, ∪ and ∩ are closed under {2U , ∅}, etc. If D is a matrix domain then there might be more than
two idempotent elements under matrix multiplication.
Note that if a semiring aggregate ⊕ is closed under DI , then it is also closed under DI ∪ {0}; however,
it is not necessarily closed under DI ∪ {1}. On the other hand, a product aggregate is always closed under
DI ∪ {0, 1}.
Definition 6.15 (Identical aggregates under a subset D′ ⊆ D). Given a set D′ ⊆ D and two aggregates
¯ (that are not necessarily closed under D′ ), ⊕, ⊕
¯ are said to be identical under D′ if for all a, b ∈ D′ ,
⊕, ⊕
we have
¯
a ⊕ b = a⊕b.
Note that two aggregates might be identical under D′ but not under D (by accident).
In this section, we consider an FAQ-query ϕ of the following form:
ϕ(x[f ] ) =
where

L(f +1)
xf +1

···

L(f +ℓ) L(f +ℓ+1)
xf +ℓ

xf +ℓ+1

···

L(n) N
xn

S∈E

ψS (xS ),

(21)

• All input factors have range DI , such that DI is a set of idempotent elements of ⊗, {0, 1} ⊆ DI , and
⊗ is closed under DI .13
• 0 ≤ ℓ ≤ n − f is an integer,
L
• For f + 1 ≤ i ≤ f + ℓ, (i) is an arbitrary semiring aggregate,
L(i)
• For f + ℓ + 1 ≤ i ≤ n,
is closed under DI . (It could be either a product or semiring aggregate.)

13 If D is the set of all idempotent elements of ⊗, then ⊗ is closed under D , because for any two elements a, b ∈ D , we
I
I
I
have (a ⊗ b) ⊗ (a ⊗ b) = a ⊗ (b ⊗ b) ⊗ a = a ⊗ b ⊗ a = (a ⊗ a) ⊗ b = a ⊗ b.

32

L
L
L
L
• For every f + 1 ≤ i, j ≤ n such that (i) and (j) are semiring aggregates, if (i) and (j) are not
identical under D, then they are not identical under DI .
A compact way to write the above FAQ expression is
ϕ(xF ) =

L(f +1)
xf +1

···

L(f +ℓ)
xf +ℓ

ϕ′

where ϕ′ is a general FAQ expression whose aggregates are closed under DI . This special case of FAQ
captures the QCQ and #QCQ instances from Example A.20 and Example 1.3, both of which can be written
in the above form.
Example 6.16 (#QCQ-revisited). In #QCQ, ϕ′ is basically a QCQ formula. In particular, although the
input factors have range {0, 1}, the output is computed under the range D = N. Hence by choosing
DI = {0, 1}, we can compute the “QCQ-part” of #QCQ over DI exploiting the fact that all product
aggregates are idempotent (as in Definition 5.2), and the “#-part” of #QCQ over the full domain D while
enjoying the fact that there are no product aggregates.
More specifically, in #QCQ we have two aggregates (max, ×) that are closed under DI (those are equivalent to the logical ∨, ∧), and one aggregate + which is not (e.g. 1 + 1 ∈
/ {0, 1}). Notice that because of this, +
cannot be identical under DI to either max or × (even if we use any different arithmetic interpretation of the
logical ∨, ∧ other than max, ×). Hence, #QCQ satisfies the last condition above in the problem formulation.
In this special case of FAQ, as long as the variable ordering lists X[f +ℓ] first (in any order), then all
product aggregates are idempotent (see Definition 5.2). Our aim is to find a good variable ordering for ϕ in
the set EVO(ϕ, F (DI )), where F (DI ) is the set of factors whose range is DI (See Definition 5.8). Notice that
in this context, EVO(ϕ, F (DI )) is a stronger notion and harder to deal with than EVO(ϕ). In particular, a
variable ordering σ can still be in EVO(ϕ, F (DI )) even if the output evaluates differently under σ for some
input factors whose range is D, as long as those factors don’t have range DI ⊆ D.
6.2.2

Non-commutative aggregates vs. non-identical aggregates

From the discussion of Section 6.1.2, a necessary condition for two variable aggregates (possibly products)
to be commutative under DI is that for all a, b, c, d ∈ DI , we have
¯ ⊕ d) = (a⊕c)
¯ ⊕ (b⊕d).
¯
(a ⊕ b)⊕(c
¯ are not necessarily closed under DI , and that is why the above condition is not sufficient).
(Notice that ⊕, ⊕
We recognize two cases:
¯ are semiring aggregates, then by selecting a = d = 0 (since 0 ∈ DI ), we obtain
• If both ⊕ and ⊕
¯ = b ⊕ c for every b, c ∈ DI . Hence, no two semiring aggregates commute under DI unless they are
b⊕c
identical under DI . However, our problem formulation requires any two semiring aggregates that are
identical under DI to be identical under D as well.
¯ = ⊗, then by selecting a = d = 0 and b = c = 1,
• If exactly one of the two aggregates is a product, say ⊕
we get a contradiction (1 = 0). Hence, ⊕, ⊗ do not commute under DI .
We infer the following variant of Proposition 6.7: (Notice that the range of φij is now DI instead of D.)
¯ are either semiring aggregates that are not identical under D or
Proposition 6.17. Suppose that ⊕ and ⊕
one of them is a product aggregate (while the other is not). Then for every i, j ∈ [n], there is a function
φij : Dom(Xi ) × Dom(Xj ) → DI for which
L̄
L
L̄
L
(22)
xj ∈Dom(Xj )
xi ∈Dom(Xi ) φij (xi , xj ).
xj ∈Dom(Xj ) φij (xi , xj ) 6=
xi ∈Dom(Xi )

33

¯ are semiring aggregates, then φij is defined exactly the same as in the proof of
Proof. If both ⊕ and ⊕
¯ = ⊗, then φij is defined as follows. Fix
Proposition 6.7. If exactly one aggregate is a product, say ⊕
arbitrarily elements x1i 6= x2i ∈ Dom(Xi ), x1j ∈ Dom(Xj ) such that x1j is not the last in Dom(Xj ) (i.e. there
is x2j ∈ Dom(Xj ) such that x2j > x1j ). Define
φij (xi , xj ) =
Then,

L L̄
xi

6.2.3

(

1
0

if xi = x1i ∧ xj ≤ x1j
otherwise.

xj φij (xi , xj )

= 0 6= 1 =



L̄

xj

or xi = x2i ∧ xj > x1j

L

xi



(23)

φij (xi , xj ).

Expression tree and precedence poset

The approach in this section and the next mirrors that of Section 6.1. However, dealing with the product
aggregates (under the ϕ′ part of the query) requires extra care. In particular, the corresponding variables
do not play a role in determining the connected components when we construct the expression tree. (They
do not belong to the set K defined by (13).) And, they do not contribute directly to the width faqw(σ),
because faqw(σ) is defined only on Uk for k ∈ K. While our algorithm was designed for FAQ, it might be
helpful if the reader uses #QCQ as the running example for this section.
Definition 6.18 (Expression tree). The expression tree for ϕ is a rooted tree P . Every node of the tree
is a set of variables, and the tree is constructed via compartmentalization and the compression. While the
compression step remains identical to that in Section 6.1, the compartmentalization step is trickier.
Compartmentalization. In this step, initially we start off with the sequence of variables with their
corresponding tags exactly as written in (21). We also apply the same trick of adding a dummy free variable
X0 as was done in Section 6.1, i.e. we start off with the sequence
D
E
σ = (X0 , “free”), (X1 , “free”), . . . , (Xf , “free”), (Xf +1 , ⊕(f +1) ), . . . , (Xn , ⊕(n) )

and with the hypergraph H which has an extra isolated vertex X0 marked with a “free” tag.
Now given a tagged variable sequence σ and a hypergraph H, we build the tree by constructing a node
L containing the first tag block. Then, we do the following.
• Let W be the set of all product variables in σ that do not belong to L.

• For each connected component C = (V(C), E(C)) of H−L−W we construct a hypergraph (V ′ (C), E ′ (C))
called extended component of C as follows. We set
[
w ∈ W | ∃S ∈ E where S ∩ V(C) 6= ∅ and w ∈ S
V ′ (C) = V(C)

E ′ (C) =
S ∩ V ′ (C) | S ∈ E, S ∩ V(C) 6= ∅
• After all the extended components are constructed, we construct a special set D of variables called the
dangling product variable set, which is defined to be
[
D :=
(S ∩ W ).
S∈E
(S\L)⊆W

• Now, for each extended component (V ′ (C), E ′ (C)), we construct a sequence σC (of tagged variables) by
listing all variables in V ′ (C) in exactly the same relative order they appeared in σ. From the sequence
σC and the hypergraph (V ′ (C), E ′ (C)) we recursively construct the expression tree PC .
34

• Finally, we connect all subtrees PC to the node L. And, we create a node that contains D – all
dangling product variables – and connect it to L also.
• The dummy variable X0 is removed after everything is done. This completes the compartmentalization
step. Note that after compartmentalization all variables in the same node of P have the same tag.
Compression. Now, in the expression tree P that resulted from the compartmentalization step, as long
as there is still a node L whose tag is the same as a child node L′ of the tree P , we merge the child into L.
Repeat this step until no further merging is possible.
Before proceeding with the proof, we present an example to illustrate the computation of the expression
tree in the presence of product aggregates.
Example 6.19 (Intuition behind expression tree). Consider the following FAQ query, where all factors have
range {0, 1}.
Y
XXY
max
max ψ13 ψ24 ψ34 ψ15 ψ16 ψ26 ψ257 ψ167 ψ278 .
ϕ = max max
x1

x2

x3

x4

x5

x6

x8

x7

In this example, DI = {0, 1} while D = N. Both max and × are closed under {0, 1}, while + is not. Hence,
by comparison to the format in (21), f = 0 and ℓ should be taken as 4. Notice that because max is closed
under DI while + is not, max and + are not identical under DI . Hence, the last condition in the problem
specification is satisfied. Figure 4 illustrates the hypergraph H corresponding to this FAQ instance.
H

1

ϕ = maxx1 maxx2

2

P

x3

P

3

x4

Q

x5

4

maxx6

5

Q

x7

6

7

8

maxx8 ψ13 ψ24 ψ34 ψ15 ψ16 ψ26 ψ257 ψ167 ψ278

Figure 4: The hypergraph H corresponding to an FAQ instance ϕ with the factors having the range {0, 1}.

1

1
3

4

2

6

7

2

7

8

2
P

x3

P

x4 ψ13 ψ24 ψ34

maxx6

Q

x7

ψ16 ψ26 ψ167

Q

x7

maxx8 ψ278

Figure 5: The extended components for the FAQ instance ϕ from Figure 4. Ignoring the dummy free variable
X0 in this case, L = {1, 2} and the set of product nodes that are not contained in L is defined by W = {5, 7}.
The vertices in each of the three extended component are the ones with a solid circle. A (hyper)edge is drawn
with a solid line if it is completely contained inside the vertices of the extended component and is drawn
with a dotted line if it is only partially contained inside the vertices of the extended component. The
corresponding FAQ instances are shown below the components.

35

Compartmentalization

Compression

max

1, 2
D

5, 7

3, 4

Q

P

6, 7

7, 8

max

1, 2, 6

First level of recursion
Second level of recursion
max

5, 7

3, 4

7

1, 2

Q

P

Q

7

Q

8
5, 7

3, 4

Q

P

6

max

7

7

8

Q

max

Q

max

Figure 6: Construction of the expression tree for ϕ from Figure 4. The left panel is the compartmentalization
(top left being the tree after the first level of recursion and the bottom left being the tree after the second
and final level of recursion) while the right panel is the compression step. Each node is labeled with the
corresponding tag in blue (if all the nodes in the tree have the same tag). The dangling node D is marked
in orange on the top left. The dummy free variable X0 is ignored in this example.
Because in this example ϕ consists of a single extended component, we can ignore the dummy free variable
X0 in the construction of the expression tree. In the compartmentalization step, we try to symbolically
decompose the problem. In particular, due to the fact that all product aggregates are idempotent, we can
decompose the above problem gradually as follows. Note that, for brevity the scope of each aggregate is
the entire expression to its right; if we want to be more specific about the limit of the scope we put a
sub-expression inside a pair of parentheses.
ϕ
= max max
x1

x2

= max max
x1

x2

= max max
x1

x2

= max max
x1

x2

= max max
x1

x2

= max max
x1

x2

XXY
x3

x4

x5

XX
x3

ψ13 ψ24 ψ34

x7

Y

max ψ13 ψ24 ψ34 ψ15 ψ16 ψ26 ψ257 ψ167 ψ278
x8

Y

max
x6

x5

ψ13 ψ24 ψ34

Y

ψ13 ψ24 ψ34

max ψ278
x8

max ψ278
x8

Y

!

·
·

max ψ15 ψ16 ψ26 ψ257 ψ167 ψ278
x8

Y

x6

x6

x8

Y

ψ257

x7

ψ13 ψ24 ψ34

Y

ψ15 ·

Y

ψ167

x7

36

!

Y

·

!

·

ψ257

XX
x3

x4

Y

ψ167

x7

x7

x5

x4

max ψ16 ψ26

ψ257 ψ167 max ψ278

x7

ψ15 max ψ16 ψ26

XX
x3

x7

x6

x5

!

Y

ψ15 max ψ16 ψ26

x5

x4

Y
x7

x7

x4

XX
x3

x6

Y

x4

XX
x3

max

!

!

·

Y

max ψ278

x7

x8

· max ψ16 ψ26
x6

ψ13 ψ24 ψ34

Y

!

ψ167

!

ψ257

!

x7

Y
x5

ψ15 ·

Y
x7

Y

= max max
x2

x1

x7

max ψ278
x8

!

·

max
x6

Y

ψ16 ψ26 ψ167

x7

!

XX

·

ψ13 ψ24 ψ34

x4

x3

!

YY

·

ψ15 ψ257

x5 x7

!

.

The set D = {X5 , X7 } is the set of dangling product variables. When conditioned on (x1 , x2 ) the inner
instance factorizes into a product of four independent FAQ queries. The extended components along with
the corresponding FAQ factors are shown in Figure 5. The intermediate expression tree after this first level
of recursion is shown on top left in Figure 6. After recursively constructing the expression trees for each of
the sub-queries, we can connect them to the root node L = {x1 , x2 } of the expression tree (as in bottom left
of Figure 6). This is only the compartmentalization step. Everything is done at a symbolic level, no real
computation is involved.
Next, let us illustrate what the compression step does. We re-arrange the above expression for ϕ.
ϕ
Y

= max max
x1

x2

max ψ278

x7

= max max max
x1

x6

x2

x8

Y

= max max max ψ16 ψ26
x1

x2

x6

max
x6

ψ16 ψ26 ψ167

x6

x2

·

x7

= max max max ψ16 ψ26
x1

!

"
Y

ψ167

"

Y
x7

ψ167

#

ψ16 ψ26 ψ167

x7

!

x7

Y

·

Y

max ψ278
x8

x7

#!

·

Y
x7

Y
x7

!
!

·

x3

·

max ψ278
x8

max ψ278
x8

!

·

XX
XX
x3

!

·

ψ13 ψ24 ψ34

x4

XX
x3

XX
x3

ψ13 ψ24 ψ34

x4

x4

!
!

·

ψ13 ψ24 ψ34

!

·

ψ15 ψ257

!

ψ15 ψ257

!

x5 x7

·

ψ13 ψ24 ψ34

x4

YY
YY
x5 x7

!

·

YY

ψ15 ψ257

x5 x7

YY
x5 x7

ψ15 ψ257

!

!

.

Un-raveling an inner aggregate to become an outer aggregate corresponds to a merge of a child node to the
parent node in the compression step. The final expression tree is shown on right in Figure 6.
Unlike free and semiring variables, it is possible for the same product variable to appear multiple times
in the expression tree. In Example 6.19, X7 occurs three times in three different sub-expressions, and we can
think of them as three different variables X7 , X7′ , and X7′′ which all have domains Dom(X7 ) = Dom(X7′ ) =
Dom(X7′′ ) and rewrite ϕ as:


#
"
! 
Y
Y
XX
YY
ψ167  max ψ278  ·
ϕ = max max max ψ16 ψ26
ψ13 ψ24 ψ34 · 
ψ15 ψ257  .
x1

x2

x6

x7

x′7

x8

x3

x4

x5 x′′
7

Luckily, the distribution of product variables (with their multiple copies) in the expression tree exhibits some
nice properties, some of which do not even hold for semiring variables. Those nice properties enable us to
take care of multiple copies of product variables.
In particular, given integers i, j ∈ [n] − [f ], i < j, where ⊕(i) = ⊕(j) is a semiring aggregate, it is possible
for Xj to be a strict ancestor of Xi in the expression tree, due to the compression step. (Xj is a strict
ancestor of Xi if Xj ∈ L, Xi ∈ L′ , and L is a strict ancestor of L′ in the expression tree.) For example,
consider the following FAQ-query.
L L̄ L L
ϕ = x1 x2 x3 x4 ψ12 ψ23 ψ14 .
The expression tree roughly corresponds to the following re-writing of the query:

L
L L L̄
ϕ = x1 x4
x3 ψ12 ψ23 ψ14 .
x2

Although X3 comes before X4 in the original expression, X4 is now a strict ancestor of X3 in the expression
tree. However, the following lemma says that the above scenario is impossible if ⊕(i) = ⊕(j) is a product
aggregate. The lemma also allows us to show that the comparison relation formed by the expression tree is
indeed a partial order.
37

Lemma 6.20. The expression tree satisfies the following properties.
(a) For any i ∈ [n] − [f ] such that ⊕(i) = ⊗, no copy of Xi is a strict ancestor of another copy of Xi .
(b) For any i < j ∈ [n] − [f ] such that ⊕(i) = ⊕(j) = ⊗, no copy of Xj is a strict ancestor of any copy of
Xi .
Proof. The proof is by induction on the number of tag blocks. In the base case where there is only one tag
block, the expression tree has only one node and the lemma follows trivially.
In the inductive step, suppose σ has at least two tag blocks with L being the first tag block. Then, each
sub-sequence σC for each extended component (V ′ (C), E ′ (C)) defines an FAQ-expression ϕC . The expression
ϕC is on the conditional factors ψS (· | xL ) for each S ∈ E such that S∩V(C) 6= ∅. For the dangling component
D, the expression ϕD is defined similarly. The (compressed) expression tree for ϕ can be constructed by
taking all the (compressed) expression trees for all ϕC (and ϕD ), connecting all their roots to the new root
L, and then merging into L the children that have the same tag. Consider the following two cases.
Case 1. In the case where the tag of L is a semiring tag, consider two different expressions ϕC , ϕC ′ for
two extended components C, C ′ . Although C and C ′ could contain copies of the same product variable(s),
we can only merge the root of the expression tree for ϕC (or ϕC ′ ) into L when this root contains the same
semiring tag as that of L. Therefore even after merging, no (copy of a) product variable in C can be a strict
ancestor of any (copy of a) product variable in C ′ . Assuming the lemma holds for the expression trees of all
ϕC , it will hold for the expression tree of ϕ.
Case 2. If the tag of L is ⊗, we claim that there cannot be more than one extended component C.
Roughly, this is because in the construction of the expression tree, product variables are not taken into
account while determining connected components. Hence, removing them does not increase the number of
extended components. Assuming the lemma holds for ϕC , it will hold for ϕ.
Let us elaborate more on the above claim. Because we are adding a dummy free variable X0 , the first tag
block F always has the tag ”free”. After we condition on F , we recursively construct an expression tree for
each extended component. For each one of those components, we condition on the first block and recursively
construct an expression tree for each extended component... Hence, apart from the time when the first block
was F , we can always assume that the hypergraph H consists of only one extended component.
Now, suppose H is a single extended component; how did we get to H in the first place? In the previous
stage, we had a hypergraph H′ with L′ being the first tag block (not necessarily a product block) and W ′
being the product vertices in H′ −L′ . We obtained H by taking a single connected component of H′ −L′ −W ′
and extending it back with vertices from W ′ . Hence, H − W ′ is connected. Let L be the first tag block
of H and suppose it consists of product vertices. Let W be the product vertices in H − L. Note that that
L ∪ W ⊆ W ′ . We obtained the extended components of H − L by taking the connected components of
H − (L ∪ W ) and then adding back vertices from W . However, H − (L ∪ W ) is connected because H − W ′ is
connected. Hence, when we add back vertices from W , we get H − L as a single extended component; this
proves the claim.
Now we are ready to show that the expression tree defines a partial order on the variables. Let P be
the expression tree of ϕ as defined in Definition 6.18. Define a binary relation P ⊆ V × V on the variables
V as follows. For any pair u, v ∈ V, we write u P v if u = v or u belongs to a strict ancestor of v in the
expression poset P . (Note that the same variable u might occur several times in the expression tree, hence
it is not immediately obvious that P is indeed a partial order.)
Corollary 6.21. The binary relation P defines a partially ordered set.
Proof. Reflexivity and transitivity hold trivially. We check the antisymmetry property of P . Suppose
u P v, v P u, but u 6= v. It cannot be the case that both u and v are semiring variables, because each
semiring variable occurs only once in P . If u is a semiring variable and v is not, then v is both a strict
ancestor and a strict descendant of u. This means v is a strict ancestor of a copy of itself, violating part
(a) of Lemma 6.20. So we are left with the case when both u and v are product variables. But in this case,
one of them (say, u) comes before the other (say, v) in the original expression ϕ, and thus by part (b) of
Lemma 6.20 v cannot be an ancestor of u.
38

The above corollary justifies the correctness of the precedence poset definition.
Definition 6.22 (Precedence poset). The precedence poset is the partially ordered set P = (V, P ). (We
abuse notation and use P to denote the poset also.) Also, as in Definition 6.3 we let LinEx(P ) denote the
set of linear extensions of P .
We next prove the soundness of LinEx(P ).
Theorem 6.23 (LinEx(P ) ⊆ EVO(ϕ, F (DI ))). Every linear extension of the precedence poset is ϕ-equivalent.
Proof. Similar to the proof of Theorem 6.8, we only need to prove soundness for the compartmentalization
poset, i.e. the poset defined the expression tree constructed using only the compartmentalization step. A
slightly tricky issue in this case compared to that of Theorem 6.8 is the multiple occurrences of some product
variables. Let σ be the variable ordering used to write ϕ. We prove this claim by induction on the number
of tag blocks of the input sequence.
The base of one single tag block holds trivially. In the inductive step, suppose σ has at least two tag
blocks with L being the first tag block. For each extended component (V ′ (C), E ′ (C)) of H − L, we form
a sub-sequence σC , which defines an FAQ-expression ϕC . This expression ϕC is on the conditional factors
ψS (· | xL ) for each S ∈ E such that S ∩ V(C) 6= ∅. (Recall that V(C) is different from V ′ (C) because V ′ (C)
also contains some product variables.) We also construct the expression ϕD for the dangling component
D. This expression is on the conditional factors ψS (· | xL ) for each S ∈ E such that S \ L ⊆ W . When
we condition on the first L variables, the expression ϕ(· | xL ) factorizes completely into a product of the
FAQ-expressions ϕC and ϕD (if D is not empty). Note that the same product aggregate ⊕(i) = ⊗ might
occur in several ϕC and ϕD ; this corresponds to different copies of Xi in our construction.
Now, let π be an arbitrary linear extension of the compartmentalization poset for ϕ. For each extended
component (V ′ (C), E(C)), let πC denote the subsequence of π obtained by picking out variables in V ′ (C).
Then, πC is a linear extension of the (compartmentalization) poset for ϕC , and thus πC ∈ EVO(ϕC , F (DI ))
by induction. Note that the first |L| variables in π must be those in L. Hence, the FAQ-expression ϕπ defined
by π is identical to ϕ because ϕπ (· | xL ) factorizes into exactly the ϕC and ϕD .
We now follow the script of Section 6.1 to prove the completeness of LinEx(P ).
Lemma 6.24. For every variable ordering π = (u1 , . . . , un ) ∈ EVO(ϕ, F (DI )), the variable uf +1 must
belong to a child node of the root of the expression tree.
Proof Sketch. The proof is similar to that of Lemma 6.9. The main difference is that instead of considering a connected component, we will be considering an extended component. Hence in the path
(i0 := uf +1 , i1 , . . . , ik ∈ L), we can assume that non of the intermediate vertices i1 , . . . , ik−1 is a product variable. In addition, instead of using the φik−1 ik defined in Proposition 6.7, we will be using the one
defined in Proposition 6.17 (whose range is DI ). Also for all S ∈ E, instead of ψS (xS ) being 0 whenever
there is a variable ℓ′ ∈ S \ {i0 , . . . , ik } for which xℓ′ 6= eℓ′ , the value of ψS (xS ) could now be 0 or 1 depending
L ′
on whether (ℓ ) is a semiring or product aggregate. In particular, if there is ℓ′ ∈ S \ {i0 , . . . , ik } for which
L ′
xℓ′ 6= eℓ′ and (ℓ ) is a semiring aggregate, then ψS (xS ) = 0. Otherwise, if there is ℓ′ ∈ S \ {i0 , . . . , ik } for
L ′
which xℓ′ 6= eℓ′ and (ℓ ) is a product aggregate, then ψS (xS ) = 1. Otherwise, ψS (xS ) is defined as in the
proof of Lemma 6.9.
The definition of componentwise-equivalence remains the same as that of Section 6.1 except that instead
of taking connected components, we will be taking extended components (See Definition 6.18).
Definition 6.25 (Componentwise-equivalence). Let ϕ be an FAQ-query, σ = (v1 , . . . , vn ) ∈ EVO(ϕ, F (DI ))
be a variable ordering. Let π = (u1 , . . . , un ) be another variable ordering with {u1 , . . . , uf } = F . Then, π is
said to be componentwise-equivalent (or shortly CW-equivalent) to σ if and only if:
• either n = 1,
39

• or H has ≥ 2 extended components, and for each extended component C = (V ′ (C), E ′ (C)) of H, πC is
CW-equivalent to σC , where σC (respectively, πC ) is the variable ordering of V ′ (C) that is consistent
with σ (respectively, π),
• or {u1 } = {v1 } =: L is a semiring or free variable or (for some p ≥ 1) {u1 , . . . , up } = {v1 , . . . , vp } =: L
are product variables, and for each extended component C = (V ′ (C), E ′ (C)) of H − L, πC is CWequivalent to σC , where σC (respectively, πC ) is the ordering of V ′ (C) that is consistent with σ (respectively, π).
Given a set of variable orderings Λ ⊆ EVO(ϕ, F (DI )), we use CWE(Λ) to denote the set of all variable
orderings that are CW-equivalent to some variable ordering in Λ.
Notice that variables in the dangling product set can be placed anywhere later in the ordering, and hence
they are ignored in the above definition.
Proposition 6.26. Let π be a variable ordering that is CW-equivalent to σ ∈ EVO(ϕ, F (DI )), we have
π ∈ EVO(ϕ, F (DI )) and faqw(σ) = faqw(π).
Proof. Same as Proposition 6.11. The only difference is that for any product variable k ′ ∈ [n] − K, the
set Ukσ′ is not considered in the definition of faqw(σ) (Definition 5.10). Hence, an initial block of product
variables (such as {v1 , . . . , vp } in Definition 6.25) can be ordered arbitrarily.
Theorem 6.27 (EVO(ϕ, F (DI )) = CWE(LinEx(P ))). Let ϕ be an FAQ-expression of the form (21). A
variable ordering σ is ϕ-equivalent if and only if it is CW-equivalent to some ordering π which is a linear
extension of the precedence poset P .
Proof. Similar to the proof of Theorem 6.12. The containment CWE(LinEx(P )) ⊆ EVO(ϕ, F (DI )) follows
from Proposition 6.26 and Theorem 6.23. Hence, we only need to prove the other direction.
We prove the containment EVO(ϕ, F (DI )) ⊆ CWE(LinEx(P )) by induction with a slightly stronger induction hypothesis. We show that, if σ is ϕ-equivalent, then there is a linear extension π ∈ LinEx(P ) such
that all product variables in π have exactly the same relative order as that in σ.
Without loss of generality we can assume that the root of the expression tree F is empty. Fix an arbitrary
σ = (v1 , . . . , vn ) ∈ EVO(ϕ). By Lemma 6.24, v1 ∈ L. We recognize two case:
• If the tag of L is not ⊗, then for every extended component C of H − {v1 }, define a sub-query ϕC with
variable ordering σC on the conditional factors
{ψS (· | xv1 ) | S ∈ E ∧ S ∩ V(C) 6= ∅} ,
where σC is the subsequence of σ obtained by picking out vertices in V ′ (C). Let PC be the precedence
poset of the expression tree for ϕC . By induction on the number of variables, we know that
σC ∈ EVO(ϕC , F (DI )) ⊆ CWE(LinEx(PC )).
Hence, there is a variable ordering πC ∈ LinEx(PC ) that is CW-equivalent to σC . Moreover, product
variables (if any) in πC maintain their relative order in σC . Although the same product variable(s)
might appear in different components, we can pick a variable ordering π that is consistent with all πC
such that π starts with v1 , followed by variables in L − {v1 }. It follows that π ∈ LinEx(P ) and π is
CW-equivalent to σ. Moreover, product variables in π maintain their relative order in σ.
• If the tag of L is ⊗, then H − {v1 } cannot have more than one extended component (using the same
argument as in the proof of Lemma 6.20). Applying Lemma 6.24 and the “one-extended-component”
argument repeatedly, we infer that {v1 , . . . , v|L| } = L and that H − L has maximally one extended
component.

Corollary 6.28. We have
faqw(ϕ) = min {faqw(σ) | σ ∈ LinEx(P )} .
40

6.3

General FAQ query

The only case of FAQ that does not fall under the previous section is the case where we have non-idempotent
product aggregates. This general case is not very natural as it is really hard to find practical examples that
can only be represented using this form. For completeness, we describe how to handle it in this section.
Definition 5.2 defines idempotence from an algorithmic point of view: A product aggregate is called
idempotent at the time it is about to be eliminated in InsideOut if the ranges of all factors containing it at
that time are idempotent wrt to ⊗. This definition not only depends on the specific elimination ordering
being used, but also on the input factors (i.e. data-dependent). While this definition makes sense from an
algorithmic point of view, it does not capture idempotence at semantic level.
From a semantic point of view, we can only reason about whether the product is idempotent under the
entire domain D (or at least a closed subset of the domain DI , as we did in Section 6.2). More specifically
in this section, instead of thinking of idempotence as a property of each product aggregate, we will think of
it as a property of the product operator ⊗ under the domain D. A product operator ⊗ is idempotent under
D if and only if a ⊗ a = a for all a ∈ D. Here, we are interested in the case where ⊗ is not idempotent under
D.
We will explain the basic ideas using a simple example.
Example 6.29 (FAQ with non-idempotent ⊗ under D). Consider the following FAQ.
XYX
ϕ=
ψ13 (x1 , x3 )ψ2 (x2 ).
x1

x2

x3

Notice that ϕ consists of two connected components (or two extended components as defined in Section 6.2.3).
However, assuming the product is non-idempotent under D, ϕ is written as

!|Dom(X2 )|  "
#
X X
Y

ψ13 (x1 , x3 )
ψ2 (x2 ) .
ϕ=
x1

x3

x2

Although x2 is connected to neither x1 nor x3 , it imposes an order on them. However if we construct the
expression tree directly as described in Section 6.2.3, it is going to be equivalent to the following expression.
"
#"
#
X
Y
ϕ=
ψ13 (x1 , x3 )
ψ2 (x2 ) .
x1 ,x3

x2

The above expression fails to capture the fact that x1 must come before x3 . (Notice that this situation
does not necessarily happen between sibling nodes in the expression tree. It could have happened between
arbitrary nodes that are incomparable under the precedence poset of the expression tree.)
To solve this issue, we extend all factors by adding all product variables to them, and then we construct
the expression tree for the extended ϕ exactly as described in Section 6.2.3. In this example, we extend ψ13
′
into ψ123
which is defined for all (x1 , x2 , x3 ) ∈ Dom(X1 ) × Dom(X2 ) × Dom(X3 ) as follows.
′
ψ123
(x1 , x2 , x3 ) = ψ13 (x1 , x3 ).

The extended ϕ (let’s call it ϕ′ ) will be
ϕ′ =

XYX
x1

x2

′
ψ123
(x1 , x2 , x3 )ψ2 (x2 ).

x3

The expression tree of ϕ′ (under Definition 6.18) is going to be equivalent to the following expression.
#"
#
"
Y
XYX
′
′
ψ123 (x1 , x2 , x3 )
ψ2 (x2 ) .
ϕ =
x1

x2

x3

x2

41

Now, this new expression forces x1 to come before x3 in the order. Notice that the above extension takes
place only at semantic level (i.e. during the construction of the expression tree). At algorithmic level, we
will still be working P
over the original ϕ. For example after eliminating
x3 above in InsideOut, x2 is going to
P
′
(x1 , x2 , x3 ) by raising the original x3 ψ13 (x1 , x3 ) to the power of |Dom(X2 )|
be eliminated from x3 ψ123
(using repeated squaring).
Definition 6.30 (Expression tree and precedence poset). Given an FAQ query ϕ (as defined in Section 1.2)
with hypergraph H and domain D where ⊗ is not idempotent under D, let K be the set of semiring aggregates
and free variables (as define by (13)) and K̄ := [n] − K be the set of product aggregates. We define a new
FAQ query ϕ′ with domain D and hypergraph H′ = ([n], E ′ ) where

E ′ := S ∪ K̄ | S ∈ E ,
Q
and ϕ′ : i∈[f ] Dom(Xi ) → D is defined as
ϕ′ (x[f ] ) :=

′
where for each S ∪ K̄ ∈ E ′ , ψS∪
:
K̄

Q

L(f +1)

i∈S∪K̄

xf +1

···

L(n) N
xn

S ′ ∈E ′

ψS′ ′ (xS ′ ),

Dom(Xi ) → D is defined as

′
ψS∪
K̄ (xS∪K̄ ) := ψS (xS ).

The expression tree of ϕ is constructed by applying Definition 6.18 on ϕ′ . The precedence poset is constructed
by applying Definition 6.3 on the expression tree of ϕ.
Notice that because every factor in ϕ′ contains all product variables K̄, it doesn’t really matter anymore
whether product is idempotent or not. In particular, the situation of having to raise to a power of |Dom(Xi )|
won’t be happening anymore in ϕ′ (at semantic level). Hence, we can run the exact same analysis from
Section 6.2 on ϕ′ in order to prove that:
Theorem 6.31 (LinEx(P ) ⊆ EVO(ϕ)). Every linear extension of the precedence poset P is ϕ-equivalent.
Notice again that we are merely using ϕ′ to semantically determine which orderings σ are in EVO(ϕ).
The algorithm (e.g. InsideOut) will still be running on ϕ.
While the above definition of the expression tree captures completeness at an intuitive level (as we argued
for in Example 6.29), achieving completeness in a rigorous way requires long definitions and unnatural
assumptions. Because this class of FAQ is not well-motivated by any practical examples, we skip the rigorous
completeness definitions/proofs for this section.

7

Approximating the FAQ-width

Recently, it has been shown that computing the fractional hypertree width (fhtw) is NP-hard [37]. By
extension, the problem of computing a tree decomposition with the (optimal) fractional hypertree width
is also NP-hard (since having that tree decomposition enables computing fhtw in polynomial time). As
was shown in Proposition 5.12, our FAQ-width (faqw) is an exact generalization of the fractional hypertree
width: it coincides with fhtw for SumProd queries and for queries where all variables are free. By extension,
computing faqw and finding a tree decomposition with the optimal faqw are both NP-hard.
Marx [60] had suggested a polynomial-time approximation algorithm that, for any constant w, given a
hypergraph whose fhtw is at most w, outputs a tree decomposition whose fhtw is O(w3 ). In this section,
we aim to design a polynomial-time approximation algorithm for the FAQ-width. Our algorithm is going to
use any approximation algorithm for fhtw (such as Marx’s) as a blackbox, and our approximation guarantee
is going to be in terms of the approximation guarantee of the blackbox algorithm. Our approximation
algorithm is also going to rely on the expression tree constructed in Section 6.

42

7.1

FAQ with only semiring aggregates

Recall the definition of the FAQ-width (Definition 5.10):
faqw(σ) := max {ρ∗H (Uk )} .
k∈K

When there is no product aggregate, K (as defined in (13)) is exactly [n]. Let P be the expression tree
constructed from the query ϕ in the form (17). We define notation that will be used throughout this section.
Let C be a node of the expression tree P . (This means C is a set of variables of ϕ, and all variables in C
have the same tag.) Let L be the parent node of C (if any) in the expression tree P . We define the following
sets:

Ē(C) :=
S ∈ E | S ∩ C ′ 6= ∅
SL,C

U (C)

:=

:=

for some C ′ node in the subtree of P rooted at C.

[
L∩
S


(24)

(25)

S∈Ē(C)

[

L′ an ancestor of C



L ′ ∩

[

S∈Ē(C)



S .

(26)

If C has no parent then U (C) = ∅ by default. We think of the set SL,C as the contribution of all the nodes in
the C-branch to L, and the set U (C) as the contribution of all the nodes in the C-branch to all the (strict)
ancestors of C. Next, for every node L in the expression tree P , define the hypergraph HL as follows.
• If L is a leaf node of P , then HL = H[L], the subgraph of H induced by L.
• If L is not a leaf node of P , then HL = (L, EL ), where

EL :=
S ∩ L | (S ∈ E) ∧ (S ∩ L 6= ∅) ∧ (S ∩ C = ∅, ∀ descendant C of L)

∪ SL,C | C a child of L .

In other words, EL is the set of all projections of S down to L for all hyperedges S for which S intersects
L but not any descendant of L in the expression tree; and for each child C of L, EL also contains the
projection onto L of the union of all hyperedges S that intersect (some descendant of) C.

We next prove a simple lowerbound for faqw(ϕ) that leads to an approximation algorithm for computing
faqw(ϕ) using an approximation algorithm for fhtw as a blackbox.
Lemma 7.1. For any node L in the expression tree,
faqw(ϕ)
faqw(ϕ)

≥
≥

fhtw(HL )
ρ∗H (U (L)).

Proof. To show the first inequality, by Corollary 6.14, it is sufficient to prove that faqw(σ) ≥ fhtw(HL ) for
any variable ordering σ = (v1 , . . . , vn ) ∈ LinEx(P ) and for any node L in the expression tree.
If L is a leaf node of the expression tree, then faqw(σ) ≥ fhtw(H) ≥ fhtw(HL ) because HL is an induced
subgraph of H. Now, suppose L is not a leaf node. For any child C of L, let k be the smallest integer
such that vk belongs to some node in the subtree rooted at C. Then, due to the fact that σ ∈ LinEx(P ), if
vj ∈ L then j < k. The set Ukσ is precisely equal to U (C) ∪ {vk }. This is because each time we eliminate a
vertex belonging to any node in the subtree rooted at C, we insert back a hyperedge interconnecting all its
neighbors (to the next hypergraph in the hypergraph sequence). And so by the time we reach Ukσ all of the

43

nodes in U (C) belong to the same hyperedge of Hkσ . It follows that (Ukσ − {vk }) ∩ L = U (C) ∩ L = SL,C
(since L ∩ L′ = ∅ for any ancestor L′ of L). From this observation we obtain:
faqw(ϕ)

(ρ∗ is monotone)

= min (max {ρ∗H (Ukσ ) | k ∈ [n]})
σ


≥ min max ρ∗H (Ujσ ) | j ∈ L
σ


≥ min max ρ∗H (Ujσ ∩ L) | j ∈ L
σ


≥ min max ρ∗H (Ujτ ) | j ∈ L
τ

= fhtw(HL ).

In the above, τ is taken only over all variable orderings of L instead of the entire set [n].
We next prove the second inequality that, for any σ = (v1 , . . . , vn ) ∈ LinEx(ϕ), and any node C in the
expression tree, we have faqw(σ) ≥ ρ∗H (U (C)). As we have observed above, let k be the smallest integer such
that vk ∈ C, then Ukσ = U (C) ∪ {vk }. Hence, because ρ∗ is monotone,
faqw(σ) = max ρ∗H (Ujσ ) ≥ ρ∗H (Ukσ ) ≥ ρ∗H (U (C)).
j∈[n]

Theorem 7.2. Let ϕ be any FAQ query whose hypergraph is H and all variable aggregates are semiring
aggregates. Suppose there is an approximation algorithm that, given any hypergraph H′ , outputs a tree
decomposition of H′ with fractional hypertree width at most g(fhtw(H′ )) in time t(|H′ |, fhtw(H′ )) for some
non-decreasing functions g, t. Then, we can in time |H| · t(|H|, faqw(ϕ)) compute a ϕ-equivalent vertex
ordering σ such that
faqw(σ) ≤ faqw(ϕ) + g(faqw(ϕ)).
Proof. We use the blackbox approximation algorithm for fhtw to construct a tree decomposition (TL , χL ) for
every hypergraph HL where L is a node in the expression tree. Then, from each of those tree decompositions,
we construct a variable ordering σL for variables in the set L in the standard way. Finally, we construct
the variable ordering σ for [n] by concatenating all the σL together in any way that respects the precedence
partial order.
Suppose σ = (v1 , . . . , vn ) is the resulting variable ordering. Consider an arbitrary vertex vk . Let L be
the node of the precedence tree that contains vk . Let B be the bag in (TL , χL ) that vk belonged to when it
was eliminated to construct σL . Then, using the same argument as in the proof of Lemma 7.1, we can show
that
Ukσ ⊆ B ∪ U (L).
(27)
To see this, first consider the simpler case when L is a leaf node of the expression tree. Then, when we
eliminate vk the set Uk is the union of the sets S ∈ ∂(vk ). The part Uk ∩ L is covered by B because within L
the elimination algorithm works on HL . The part Uk \ L is covered by the maximum residue left over from
eliminating all vertices in L. The residue is precisely the set U (L), because every time we eliminate a vertex
we collect all its neighbors together into a hyperedge. By the time the last vertex from L is eliminated, the
entire set U (L) becomes a hyperedge. Now, if L is not a leaf node, the situation is exactly the same except
for the fact that we work on the graph HL which is not necessarily the same as H[L]. The hypergraph HL
contains the restrictions on L of all the residues of the subtrees under L.
Next, from Lemma 7.1 and from the fact that ρ∗ is subadditive, relation (27) implies
ρ∗H (Ukσ ) ≤
≤
≤
Finally,

ρ∗ (B) + ρ∗ (U (L))
g(fhtw(HL )) + faqw(ϕ)
g(faqw(ϕ)) + faqw(ϕ).

faqw(σ) = max ρ∗H (Ukσ ) ≤ g(faqw(ϕ)) + faqw(ϕ).
k∈[n]

44

7.2

FAQ with an inner FAQ-formula closed under idempotent elements

The key difference between this section and Section 7.1 is that K (define by (13)) is not necessarily equal to
[n]: instead it is now the union of F = [f ] and the set of semiring variables. We will still follow the same
strategy as that of Section 7.1, though the definition of the sets SL,C for each node L and a child C of L is
a bit more delicate.
Definition 7.3 (Semiring node and product node). A node in the expression tree P is called a semiring
node if its variables have a tag forming a semiring with ⊗. Otherwise, the node is called a product node.
Let C be a node of the expression tree P . Let L be the parent node of C (if any) in the expression tree
P . We define Ē(C) differently from the previous section as follows:

Ē(C) :=
S ∈ E | S ∩ C ′ 6= ∅ for some semiring node C ′
in the subtree of P rooted at C.

(28)

(Compare the above definition with (24).) We define SL,C and U (C) using (25) and (26) (where the Ē(C)
referred to in (25) and (26) is now the one defined by (28)). Note in particular that if a node does not
have any semiring descendant then U (C) is empty. We think of SL,C as the residue imposed on S from the
process of eliminating all semiring variables under the C-subtree.
We next define the hypergraphs HL , similar to what was defined in Section 7.1, with one small difference:
• If L is a leaf node of P , then HL = H[L], the subgraph of H induced by L.
• If L is not a leaf node of P , then HL = (L, EL ), where

EL :=
S ∩ L | (S ∈ E) ∧ (S ∩ L 6= ∅) ∧ (S ∩ C = ∅, ∀ semiring descendant C of L)

∪ SL,C | C a child of L .

Here is where EL is different from the corresponding definition of EL in Section 7.1. We only take the
projection of the hyperedges S for which S does not intersect any semiring descendant of L. The key
point to notice is that, if S intersects some semiring descendant, then its contribution to the node L is
summarized already in some SL,C .

We now can follow the script of Section 7.1. The proof of the following lowerbounds are identical to that
of Lemma 7.1, and thus is omitted. Note that the bound only holds for the semiring nodes.
Lemma 7.4. For any semiring node L in the expression tree, we have
faqw(ϕ)
faqw(ϕ)

≥
≥

fhtw(HL )
ρ∗H (U (L)).

We can now design the approximation algorithm.
Theorem 7.5. Let ϕ be any FAQ query of the form (21) whose hypergraph is H. Suppose there is an
approximation algorithm that, given any hypergraph H′ , outputs a tree decomposition of H′ with fractional
hypertree width at most g(fhtw(H′ )) in time t(|H′ |, fhtw(H′ )) for some non-decreasing functions g, t. Then,
we can in time |H| · t(|H|, faqw(ϕ)) compute a ϕ-equivalent vertex ordering σ such that
faqw(σ) ≤ faqw(ϕ) + g(faqw(ϕ)).
Proof. First, we construct a “super” tree P from the expression tree P by replacing every semiring node L
of P by a single “super-variable” L. After this is done, P contains super variables and product variables.
Since P defines a poset on the descendant relation, P also defines a poset on the descendant relation. We
call P the “super poset”.
45

Now, we take any linear extension σ of the super poset P . Then, for every super variable L (which is
a semiring node), we use the blackbox approximation algorithm to construct a tree decomposition (TL , χL )
for every hypergraph HL . Then, from each of those tree decompositions, we construct a variable ordering
σL for variables in the set L. Finally, we replace the occurrence of L in σ by the variable ordering σL . Call
the final variable ordering σ, then it is a linear extension of the precedence poset P .
Suppose σ = (v1 , . . . , vn ) is the resulting variable ordering. Consider an arbitrary vertex vk in a semiring
node L. Following the argument in the proof of Theorem 7.2, we can see that Ukσ ⊆ B ∪ U (L). From
Lemma 7.4 and from the fact that ρ∗ is subadditive, it follows that
ρ∗H (Ukσ ) ≤ ρ∗ (B) + ρ∗ (U (L)) ≤ g(fhtw(HL )) + faqw(ϕ) ≤ g(fhtw(ϕ)) + faqw(ϕ).
The rest of the proof is identical to that of Theorem 7.2.
Note that requiring different copies of the same variable to be consecutive is not necessary for InsideOut
to work. The algorithm works even if we consider them to be different variables on the same domain.
However, the collapsing of different copies back to the original copy is needed for the rigor of the definition
of EVO(ϕ, F (DI )).
Note also that Theorem 7.5 implies Theorem F.11 and Theorem 7.2. Applying the above theorem using
the approximation algorithm from Marx [60], we obtain the following
Corollary 7.6. Let ϕ be any FAQ query of the form defined in (21). Suppose faqw(ϕ) ≤ c for some constant
c. 14 Then, the query can be answered in time


3
Õ N O(faqw (ϕ)) + kϕk .
(Recall that Õ hides a factor that is polynomial in query complexity and logarithmic in data complexity.)
7.2.1

Corollaries in Logic

Using the reduction in Example A.20 from QCQ to FAQ, we obtain
Corollary 7.7. QCQ is tractable for the class of quantified conjunctive queries ϕ where faqw is bounded.
To determine which classes of QCQ formulas are tractable, Chen and Dalmau [24] defined the notion of
a prefixed graph and its width. The definition is in the beginning of Section III of their paper. The prefix
graph’s width corresponds exactly to to the quantity maxσ maxk∈K {|Uk |}. Since ρ∗H (Uk ) ≤ |Uk |, faqw(ϕ) is
a stronger notion and our result implies the main positive result in their paper (the first part of Theorem
3.1). Furthermore, we can construct families of QCQ instances for which faqw(ϕ) is bounded but the prefix
graph’s width is unbounded. For example, consider the following quantified conjunctive query


^
R(Xi , Xn+1 ) .
Φ = ∀X1 · · · ∀Xn ∃Xn+1 S(X1 , . . . , Xn ) ∧
i∈[n]

Chen-Dalmau’s prefix graph’s width is n+1 in this case, but faqw is 2. Consequently, our result is strictly
stronger. The next corollary resolves an open question posed at the end of Durant and Mengel’s paper [34].

Corollary 7.8. #QCQ is tractable for the class of quantified conjunctive queries ϕ whose faqw is bounded.
14 This

requirement is inherited from Marx approximation algorithm [60].

46

8

Input and Output Representation

Thus far we stated our results for the case when the input and output factors are in the listing representation
(Definition 4.1). Tracing back at the key steps of InsideOut (and OutsideIn) algorithm, it is easy to see that the
algorithm works for a more general setting than just the listing representation. Section 8.1 presents the two
conditions that we need from the input factor representation for all our previous arguments to go through.
In Sections 8.2 and 8.3, we consider more compressed forms of input factor representations than the listing
representation. In particular, Section 8.2 considers other representations that can be reduced to the listing
representation (at the cost of having to compute a modified FAQ), which means we can still use InsideOut as
is. In Section 8.3 we consider even more succinct representations where the reductions in Section 8.2 are too
costly. In particular, for the special case of SAT and #SAT, we show that we can replace OutsideIn with a
more specific algorithm, which allows us to recover known results on polynomial-time solvability of certain
classes of SAT and #SAT formulas. While these results only re-prove existing results, we consider these as
an illustration of the power of the FAQ (and variable elimination) framework. We then switch to considering
situations where one might be interested in output representations other than the listing representation in
Section 8.4. Finally in Section 8.5, we consider the case when the output and input representations match,
which naturally leads to the notion of composing FAQs. FAQ composition is also needed in Section 8.2. For
the sake of clarity, we will almost exclusively focus on FAQ-SS in this section.

8.1

The factor oracle

In many application areas of FAQ, there are many ways the input factors can be represented. Appendix G
lists some of the main representations collected from areas such as logic, PGM, and matrix computation.
It should be obvious that the computational complexity of FAQ is highly dependent on how the inputs are
specified. To generalize our results, we advocate for the following oracle model, which is sufficiently general
to capture existing models of input and output representations. We note that our assumptions here are met
by all of the representations discussed here and in Appendix G – the only difference is in the price the oracle
pays to answer the query.
Assumption 1 (Conditional query assumption). We assume that Dom(Xi ) are totally ordered.15 Each
factor oracle for ψS is capable of answering the following query called the conditional query. Let 0 ≤ k ≤ n−1
be any integer such that k + 1 ∈ S. Let x[k] = (x1 , . . . , xk ) be a vector such that ψS (· | x[k] ) 6≡ 0. Let
y ∈ Dom(Xk+1 ) be arbitrary. Then, the factor oracle for ψS can return a minimum value xk+1 > y for which
ψS (· | x[k+1] ) 6≡ 0, i.e.


S
yk+1
= min xk+1 | (xk+1 > y) ∧ ψS (· | xk+1 ) 6≡ 0 .

If no such xSk+1 exists, then +∞ (just a symbol) is returned.

A value query returns the value ψS (xS ) for some given xS . For simplicity we will also call those value
queries conditional queries.
The second assumption about the input oracles is the following.
Assumption 2 (Product-marginalization assumption). Let ψS be an input oracle and i ∈ S. The input
oracle for ψS can return another oracle on S − {i}, denoted by ψS−{i} , defined by
O
ψS (xS ).
ψS−{i} (xS−{i} ) =
xi ∈Dom(Xi )

The number of ⊗ operations performed to compute the factor ψS−{i} is bounded by kψS k.
This assumption is reasonable because as soon as ψS (xS ) = 0 we can infer that ψS−{i} (xS−{i} ) = 0.
Note also that if we use the listing representation for ψS−{i} , then we can compute entries of ψS−{i} using
at most kψS k conditional queries.
15 We order the domain arbitrarily if there is no natural total order; e.g. false < true for a Boolean problem, or blue < green
< red in a coloring problem.

47

Appendix G.1 explains why the listing representation satisfies both of the above assumptions. By reexamining the previous runtime analysis of InsideOut, one can check that in the more general factor oracle
model, one can prove the following generalization of Theorem 5.5:
Theorem 8.1. Suppose the Conditional query assumption and Product-marginalization assumption are satisfied. Using notations established in Theorem 5.5, the InsideOut algorithm applied to ϕ (Algorithm 1)
satisfies the following properties.
(i) The number of conditional queries to the factor oracles is at most
X

X

|Uk | · |{S ∈ E : S ∩ Uk 6= ∅}| · AGM(Uk ) +

k∈K

kψS k

k∈K
/
S∈∂(k)

X

+

kψS k · Idem(ψS , k) + f (f + m)kϕk. (29)

k∈K
/
S∈Ek −∂(k)

(ii) the total number of ⊕(k) operations performed is at most
(iii) the number of ⊗ operations performed is at most
X

k∈K

X

(|{S ∈ E : S ∩ Uk 6= ∅}| − 1) · AGM(Uk ) +

P

k∈K

|Uk | · AGM(Uk ).

kψS k

k∈K
/
S∈∂(k)

+

X

kψS k · Idem(ψS , k) + f (f + m)kϕk. (30)

k∈K
/
S∈Ek −∂(k)

8.2

Input representations parsimoniously reducible to FAQ

We briefly mention other representation choices for input factors. More details (including formal definitions)
can be found in Appendix G.
We begin with a representation that is more wasteful than the listing representation: the “truth table”
representation, which is the norm is dense matrix computation as well as inference in probabilistic graphical
models. The difference from listing representation is that tuples that result in a 0 are also explicitly listed.
It is trivial to convert this representation into the listing representations.
Beyond the truth tables, other known representations are more succinct than the listing representation.
In the CSP literature, these include generalized disjunctive normal form (GDNF) that was first considered by
Chen and Grohe [25] and decision diagram representation of Chen and Grohe [25], which is a generalization
of the well-studied ordered binary decision diagrams or OBDDs. In the database literature, Olteanu and
Závodný [73] considered factorized representations for conjunctive queries. Fast matrix vector multiplication
has many examples of more succinct representations than the listing representation (e.g. the DFT). In the
PGM world, Algebraic Decision Diagrams (or ADDs) were introduced in Bahar et al. [12].
A common property of all of the above succinct representations is that they can all be reduced to the
listing representation at the expense of having to solve a more complicated FAQ problem. In particular, this
leads to the problem of composing FAQ problems, which is discussed in Section 8.5.

8.3

Input representations not parsimoniously reducible to FAQ

Thus far we have analyzed the runtime of the InsideOut algorithm in terms of the sizes of the input factors,
which are the number of non-zero points of each input factor. If the input factors were represented using the
listing representation, then O(|S|·kψS k) is precisely the input size for the factor ψS (assuming each functional
48

value is of size O(1)). However, in some applications the input factors are much more compactly represented,
and the representation of ψS may be exponentially smaller than kψS k. The canonical example is the SAT
problem, where a CNF clause ψS has size kψS k = 2|S| − 1, yet represented using only |S| bits. Note that in
this case we could reduce the input to the listing representation but this would suffer an exponential blowup
in size, which is too expensive. In the rest of the section, we outline how we can modify our framework to
handle this succinct representation of SAT and #SAT problems.
The conditional-search OutsideIn algorithm is no longer a good choice for such compact input representation, because its runtime depends heavily on the number of non-zero elements in each input factor. Also,
we cannot expect the same sort of results from Section 5 to hold for SAT or #SAT, because even if the
input query was α-acyclic the problem is still NP-hard or #P-hard, respectively. (Recall that α-acyclic
hypergraphs have fhtw = 1.) Recently, however, there were a couple of interesting results showing that SAT
and #SAT are tractable for β-acyclic queries [18, 74].
In the relational join problem, there is also a phenomenon discovered recently where the computational
difficulty we face comes from precisely the same problem of compact input factor representations. In [65],
modulo a technical assumption, we showed that the minimum number of comparisons a comparison-based
join algorithm performs is in the same order as the minimum number of rectangular boxes of a certain format
needed to cover the entire output space. We designed an algorithm called Minesweeper whose core functionality is to determine whether or not a set of rectangular boxes covers the entire output space. In [2], the
Tetris algorithm relaxed the assumption about the input boxes, and formally defined this box cover problem
(or BCP). In both cases, BCP’s difficulty lies precisely in the fact that the boxes represent points not in the
output, and thus a conditional-search-style algorithm such as OutsideIn does not work well. In Minesweeper
and Tetris, the collection of supports of the rectangular boxes forms a hypergraph. Similar to the SAT
and #SAT case, if this hypergraph is only α-acyclic, then the box cover problem is NP-hard. But, if it is
β-acyclic then there is a linear time algorithm solving the box cover problem.
All of the four algorithms can be explained using the InsideOut/OutsideIn duality framework. The
InsideOut algorithm remains the same – it is just variable elimination – but we have to tailor the OutsideIn
algorithm to suit the compact encoding. In particular, BCP, SAT, and #SAT can all be reduced to FAQ
instances in which each of the input factors ψS is of a special form called the box factor.
Definition 8.2 (Box factor). A box with support S = {i1 , . . . , is } is a tuple B = hIQi1 , . . . , Iis i where
n
Iij ⊆ Dom(Xij ) is an interval in the domainQDom(Xij ). The box is a set of points x ∈ i=1 Dom(Xi ) for
which xij ∈ Iij for all j ∈ [s]. A factor ψS : ij ∈S Dom(Xij ) → D is called a box factor if there is a box B
and a c ∈ D for which
(
c if x ∈ B
ψS (x) =
1 if x ∈
/ B.
In SAT and #SAT, each CNF clause is a box factor. For example, in the clause (X1 ∨ X̄2 ∨ X3 ), the box
is h{false}, {true}, {false}i (with c = false). For SAT the domain D is {true, false}. For #SAT the domain is
R+ . Each rectangular box in BCP is clearly a box factor with Boolean domain, and looking for a point not
covered by all the boxes is the same as solving the corresponding FAQ instance.
The first key to the algorithm in [74] for SAT, the algorithm in [18] for #SAT, Minesweeper in [65], and
Tetris in [2] is that we can still run variable elimination, but each of the intermediate factors ψUk −{k} is
computed and represented as a product of box factors. The second key observation is that, for β-acyclic
hypergraphs, there is a variable ordering σ = (v1 , . . . , vn ) called the nested elimination order (NEO) such
that, for every k ∈ [n], the collection of sets in ∂(vk ) forms a chain (see Proposition 4.10 and its proof
in Appendix C). This nesting allows us to keep the box factor representation of the intermediate factors
compact, i.e. each intermediate factor ψUk −{vk } is a product of a “small” number of box factors.
Since Minesweeper and Tetris take a bit of work to set up properly, in the following section we explain
the algorithms in [74] and [18] using this idea.

49

8.3.1

InsideOut for SAT

Consider the SAT problem, where we want to know if there exists one satisfying assignment. What does
“eliminating a variable” mean in this case? We have a set of clauses that contain the variable Xn . In each
such clause, Xn occurs either as a positive literal Xn , or a negated variable X̄n . Let ∂P (Xn ) be the set of
clauses containing Xn , and ∂N (Xn ) be the set of clauses containing X̄n . Then, ∂(Xn ) = ∂P (Xn ) ∪ ∂N (Xn ).
We want to construct a new boolean factor ψUn −{Xn } where

 

^
^
C|xn =false 
C|xn =true  ∨ 
ψUn −{Xn } = 
C∈∂(Xn )

C∈∂(Xn )



= 
=

^

CN ∈∂N (Xn )

^





CN |xn =true  ∨ 

^

CP ∈∂P (Xn )



CP |xn =false 

(CN |xn =true ∨ CP |xn =false )

CN ∈∂N (Xn ),CP ∈∂P (Xn )

But CN |xn =true and CP |xn =false are simply the original clauses CN and CP with Xn eliminated completely.
Hence, the rule is: for every clause Ci containing Xn and every clause Cj containing X̄n , create a new clause
Cij = Ci ∨ Cj without Xn in it.16 And we have a new instance of the SAT problem. This procedure is known
as the Davis-Putnam procedure for SAT-solving. Under this procedure, we do not need to enumerate all
2|Un | truth assignments, so it might be faster depending on the input. On the other hand, we will run into a
combinatorial explosion problem in the number of clauses. For example, after one step we might have up to
Ω(m2 ) clauses. Dechter and Rish [33] showed that this algorithm runs in time at most O(n3 9w ), where w is
the appropriate notion of width for the SAT formula. Of course this is no better than the rough runtime of
O(mn2 2w ), but the advantage is that it creates a theory for the proof system. We will not delve any further
on this point.
What is important to note here is that the representation of the intermediate factor ψUn −{Xn } is a product
of box factors. One interesting class of input CNF formulas is the class of β-acyclic CNF formulas. Under
this class, if the vertex ordering is a nested elimination order, then we don’t have the clause (or box factor)
explosion problem. This is due to the fact that the set ∂(Xk ) forms a chain, so a variable set in ∂(Xk ) is a
subset of another variable set in ∂(Xk ). When the variables in Ci are a subset of variables in Cj , the new
clause Cij is either a tautology (which can be removed), or is equal to Cj . (When the resolvent is a subset of
one of the two resolvers, the resolution is called subsumption resolution.) Hence, every time we eliminate a
variable Xn , we do not increase the number of clauses. So we have a polynomial-time algorithm for solving
β-acyclic CNF formulas, a result that was only proved recently [74].
Theorem 8.3 (Ordyniak, Paulusma, and Szeider [74]). SAT is polynomial-time solvable for the class of
β-acyclic CNF formulas.
8.3.2

InsideOut for #SAT

For the #SAT problem, each clause corresponds to a function to {0, 1}. In particular, #SAT can be viewed
as an FAQ-SS over the semiring (R+ , +, ×) where each clause C (whose variables are vars(C)) corresponds
to a factor ψvars(C) defined as
(
1 if xvars(C) satisfies C,
ψvars(C) (xvars(C) ) :=
0 otherwise.
16 In

proof complexity, the clause Cij is called a resolvent of the two clauses Ci and Cj .

50

We will be working with a slightly more general version of #SAT, called #WSAT, where each clause C has
an associated weight (weight(C) ∈ R+ ) such that the corresponding factor ψvars(C) becomes
(
1
if xvars(C) satisfies C,
ψvars(C) (xvars(C) ) :=
weight(C) otherwise.
(Obviously, if each clause has weight 0, then #WSAT reduces back to #SAT. Further, note that this
is a re-statement of the box factor formulation from Definition 8.2 specialized to this problem.) We chose
to work with #WSAT because eliminating a variable from an n-variable #WSAT instance results in an
(n − 1)-variable #WSAT instance, as we will see shortly.
Eliminating a variable Xn in #WSAT means defining a set Cn′ of weighted clauses over the variables
Un − {Xn } such that for all x
X Y
Y
ψvars(C) (xvars(C) | xn ).
(31)
ψvars(C ′ ) (xvars(C ′ ) ) =
′
C ′ ∈Cn

|

xn C∈∂(Xn )

{z

ψUn −{Xn } (xUn −{Xn } )

}

A clause C ′ is called monochromatic with respect to a set of (weighted) clauses C if for every clause
C ∈ C, either (C =⇒ C ′ ) or (C ∨ C ′ ≡ true). The color of C ′ with respect to C, denoted by colorC (C ′ ), is
defined as:
Y
colorC (C ′ ) :=
weight(C).
C∈C | C =⇒ C ′

Given a clause C and a variable X ∈ vars(C), we will be using [C]−X to denote the clause that results
from C by dropping either the literal X or X̄ (whichever occurs in C). Let Cn be the set of clauses that
contained Xn but with Xn now removed from them, i.e.

Cn := [C]−Xn | C ∈ ∂(Xn ) .

Let πn = (Xi1 , Xi2 , . . . , Xiℓ ) be some arbitrarily-fixed order of Un − {Xn }. We can define Cn′ to be the set
of clauses that are “minimal” w.r.t πn and monochromatic w.r.t Cn . Formally,
)
(

vars(C ′ ) = Xi1 , Xi2 , . . . , Xiℓ′ for some ℓ′ ∈ [ℓ], and
′
′
.
(32)
Cn := C is a clause C ′ is monochromatic w.r.t C while [C ′ ]
n
−Xi is not.
ℓ′

Notice that for each C ′ ∈ Cn′ , both C ′ ∨ Xn and C ′ ∨ X̄n are monochromatic w.r.t ∂(Xn ). Let
weight(C ′ ) =
=

color∂(Xn ) (C ′ ∨ Xn ) + color∂(Xn ) (C ′ ∨ X̄n )
color∂P (Xn ) (C ′ ∨ Xn ) + color∂N (Xn ) (C ′ ∨ X̄n ).

It is not hard to verify that the above definition of Cn′ indeed satisfies (31). However, the size of Cn′ could be
larger than |∂(Xn )|, and |Ci′ | for i < n could be even much larger.
β-acyclic case: When the CNF formula is β-acyclic, it is convenient to work with a nested elimination
order. Let Xn be the last variable in such an order. Thanks to Proposition 4.10, we can choose πn =
(Xi1 , Xi2 , . . . , Xiℓ ) such that for each clause C ∈ ∂(Xn ),
vars(C) = {Xn } ∪ {Xi1 , Xi2 , . . . , Xik } for some k ∈ [ℓ].
While the above looks very convenient, if we define Cn′ as in (32), we might end up with a clause C ′ ∈ Cn′
for which vars(C ′ ) 6= vars(C) − {Xn } for every C ∈ ∂(Xn ). After eliminating Xn , the remaining hypergraph
′
might not be β-acyclic anymore because of the new
 hyperedge vars(C ).
To remedy the situation, let C1 , . . . , C|∂(Xn )| be the clauses of ∂(Xn ) sorted in ascending order by
|vars(Ci )|. In particular, for each i < j ∈ {1, . . . , |∂(Xn )|}, we have
|vars(Ci )| ≤ |vars(Cj )| ⇐⇒ vars(Ci ) ⊆ vars(Cj ).
51

(Ties can be broken arbitrarily. The above equivalence follows from Proposition 4.10 along with the fact
that Xn is the last in NEO.) Define

We will choose Cn′ :=

∂P≤i (Xn ) :=

∂P (Xn ) ∩ {Cj }j≤i ,

≤i
∂N
(Xn )
∂P<i (Xn )

:=

∂N (Xn ) ∩ {Cj }j≤i ,

:=

∂P (Xn ) ∩ {Cj }j<i ,

<i
(Xn )
∂N

:=

∂N (Xn ) ∩ {Cj }j<i .

o
n
′
, where C0′ is an empty clause whose weight is 2, and for each
C0′ , C1′ , . . . , C|∂(X
n )|

i ∈ {1, . . . , |∂(Xn )|}, Ci′ := [Ci ]−Xn has weight


0 if color∂P<i (Xn ) (Ci′ ∨ Xn ) + color∂N<i (Xn ) (Ci′ ∨ X̄n ) = 0,
′
(Ci′ ∨X̄n )
≤i
weight(Ci ) := color∂P≤i (Xn ) (Ci′ ∨Xn )+color∂N
(Xn )

otherwise.
 color <i
′
(Ci′ ∨X̄n )
(Ci ∨Xn )+color <i
(Xn )
∂
N

(Xn )
∂
P

While the above definition of Cn′ still satisfies (31), we now have for each Ci′ ∈ Cn′ , either vars(Ci′ ) = ∅ or
vars(Ci′ ) = vars(Ci ) − {Xn } for Ci ∈ ∂(Xn ). Hence after eliminating Xn , the remaining hypergraph is still
β-acyclic. Moreover, |Cn′ | = |∂(Xn )|, which guarantees that after eliminating Xn , the resulting #WSAT
instance has the same size as the original. We conclude that:
Theorem 8.4 (Brault-Baron, Capelli, and Mengel [18]). #SAT is polynomial-time solvable for the class of
β-acyclic CNF formulas.

8.4

Output representation

Our framework, in addition to being able to handle multiple input representations, is also able to handle
different output representations. In particular, we describe how one can modify InsideOut to obtain different
output representations.
Inspired by the factorized database ideas developed by Olteanu and Závodný [73], the extension to
aggregates in Bakibayev et al. [13], and inspired by the discussion in Section 8.2 regarding using an FAQinstance as an input factor, we observe that an FAQ-expression not only defines a new function, but also
stores the computation needed to compute that function. There is a spectrum of tradeoffs one can explore
in terms of the time it takes to query into a function stored in a “compressed” form and the time it takes to
decompress it.
In order to explain this idea more cleanly, and to simplify the presentation a bit, we will only consider
FAQ-SS instances, i.e.
M O
ϕ(xF ) =
ψS (xS ),
x[n]−F S∈E

where F = [f ] for some f ∈ [n]. Furthermore, we will assume that D = {0, 1}.
We now illustrate how we can modify InsideOut so that we can represent the output in three different
output representations (in addition to the default listing representation). We will compare these output
representations across the following three axes:
1. Output pre-processing time: This is the time needed to compute the output in the required form;
Qf
2. Value query time: This is the time needed to check if ϕ(y) = 1 given the query y ∈ i=1 Dom(Xi );
and
3. Enumeration delay: Given the output representation, how much time it takes between reporting two
consecutive output tuples, given that ultimately we want to list all output tuples.

52

Recall from Section 5.2.3 that InsideOut runs until it has eliminated the variables Xn , . . . , Xf +1 and then
runs OutsideIn on the resulting FAQ-SS instance ϕf corresponding to Hf . In two of the options below, we
will see how we can change this last step. Further, we will only talk about the runtime of the algorithm after
it has eliminated the variables Xn , . . . , Xf +1 .
Listing representation. This is the default behavior of InsideOut. After spending Õ(N faqw(σ) ) time in
eliminating variables Xn , . . . , Xf +1 , it runs OutsideIn on the resulting query (9) taking time Õ(AGM(F )) to
report the output ϕ (where kϕk ≤ AGM(F )). Here, the output pre-processing time is Õ(AGM(F )), the value
query time is Õ(1), and we have a constant enumeration delay.
Next, we consider two options where we have a smaller output pre-processing time while we can still
handle the value query and enumeration operations (at potentially a larger cost than above).
FAQ representation. Another option is to just not do any output pre-processing nor eliminate the free
variables. Note that the FAQ instance ϕf constructed when InsideOut eliminates Xf +1 is a valid representation of the output. Further, the value query time is still Õ(1) (by checking if for every T ∈ Ef , ψT (yT ) = 1).
However, there is no way to construct an enumeration algorithm with a constant delay from this representation. Finally, this representation has the advantage that if one considers the input as an FAQ instance
(see Section G.3), then there is a nice symmetry in that the output here is also an FAQ instance. Given
the discussion in Section G.3, this generalizes the framework of Olteanu and Závodný [73] from factorized
representation to FAQ representation.
Õ(1)-delay enumeration representation. Another option is to eliminate free variables but avoid running
the OutsideIn algorithm at the last step (i.e. drop line 19 of Algorithm 1). In this case, we already have the
output stored in a factorized representation like that from the factorized database framework. If the output
was only required to be in this form, then essentially our runtime is Õ(N faqw(σ) ) (without the +kϕk term).
In this output representation, the value query time is Õ(1) (since one can check if for every i ∈ [f ],
ψUi (yUi ) = 1). Perhaps more importantly, one can design a Õ(1)-delay enumeration function. Assume that
the ψUi are stored as a BTree/trie (with sort order X1 , X2 , . . . , Xf ). Start with the ‘first’ x1 such that
ψU1 (x1 ) = 1 and then figure out the ‘first’ x2 such that ψU2 (x1 , x2 ) = 1 and so on. It is easy to check that
there is Õ(1) delay in outputting every two consecutive output tuples.
FAQ composition and message passing Being able to efficiently enumerate entries of a function defined
by an FAQ expression might have applications, say in answering a conjunctive query in a database. Thus,
the Õ(1)-delay enumeration representation is a decent choice. However, as we mentioned in Section 8.2
there are cases where we want to use the output of one FAQ-query to feed into the input of another FAQquery. Thus, the output representation should allow us to efficiently answer conditional queries and product
marginalization queries (e.g. universal quantifiers in logic applications).
The problem is, we do not know in advance in which variable ordering the future conditional queries and
product marginalization queries will be posed. If they were posed in the same order as X1 , . . . , Xf , then
the Õ(1)-delay representation is sufficient. We can easily answer a conditional query using the intermediate
factors ψUi , i ∈ [f ], efficiently in Õ(1) time.
This is where we can use the playbook of the graphical model literature. The key reason that message
passing (or belief propagation) is advantageous over variable elimination is that it prepares the graphical
model for future (unknown) queries. The message passing algorithm is essentially variable elimination run
in all directions at once. We compute the tree decomposition of the graph Hf (after using InsideOut to
eliminate Xi , i > f .) Then, we run the message passing algorithm on the bags of the tree decomposition.
The overall complexity is still Õ(N fhtw(Hf ) ), but after convergence all the bags are in calibrated state, and
they allow for answering conditional queries along any GYO elimination order of the tree decomposition.
We leave the tradeoffs involved in realizing such an idea for a future work; but we would like to point out
that Olteanu and Závodný [73] has taken a step toward this direction in the database domain.

53

8.5

Composition of FAQ instances

We consider how the fractional hypertree width changes when we compose FAQ instances. More precisely
we consider the following problem:
Let H0 = (V, E 0 ) be a hypergraph. For every e ∈ E 0 , let He1 = (e, Ee1 ) be a hypergraph. Let H1
denote the collection of hypergraphs {He1 }e∈E 0 . Now consider the following composed hypergraph
H0 ◦ H1 with V as the set of nodes and the edge set E 01 = ∪e∈E 0 Ee1 . How does fhtw(H0 ◦ H1 )
behave with respect to fhtw(H0 ) and fhtw(He1 ) (or in terms of other widths of these hypergraphs)
for e ∈ E 0 ?
We begin with a simple observation:
Proposition 8.5. For every hypergraph H0 and a corresponding collection of hypergraphs H1 ,
fhtw(H0 ◦ H1 ) ≤ fhtw(H0 ) · max0 ρ∗ (He1 ).
e∈E

∗

0

Proof. Let (T, χ) be a tree decomposition for H with ρ -width of w = fhtw(H0 ). It is easy to check
that (T, χ) is also a valid tree decomposition for H0 ◦ H1 . Further, we claim that for every bag B in T ,
ρ∗H0 ◦H1 (B) ≤ w · maxe∈E 0 ρ∗ (He1 ), which would complete the proof.
0
Finally, we argue the
that e ∩ B 6= ∅ be the optimal
Pclaim. Fix any bag B and let xe for every e0 ∈ E such
e
x
≤
w).
For
every
edge
e
∈
E
,
let
y
for
every e′ ∈ Ee1 be an optimal
edge cover for B (i.e.
′
e
e∈E 0 :e∩B6=∅ e
fractional edge cover for He1 . Then it is easy to check that the following is a valid edge cover for B using
edges from H0 ◦ H1 : for every e′ ∈ E 01 such that e′ ∩ B 6= ∅, define
X
xe · yee′ .
ze′ =
e∈E 0 :e′ ∩e∩B6=∅,e′ Ee1

The claim follows by noting that
X

e′ ∈E 01 :e′ ∩B6=∅

which completes the proof.



ze′ ≤ 

X

e∈E 0 :e∩B6=∅

 

xe  · 

max

e∈E 0 :B∩e6=∅

X

e′ ∈Ee1 :e′ ∩e∩B6=∅



yee′  ,

Remark 8.6. We note that the proof above gives a better bound than that stated in Proposition 8.5 for
specific hypergraphs. However, we chose to present a uniform bound for all hypergraphs for its elegance.
It is natural to wonder if one can improve upon the bound of Proposition 8.5 in the worst-case. In
particular, it is natural to wonder if we can prove a bound of the form


fhtw(H0 ◦ H1 ) ≤ O fhtw(H0 ) · max0 fhtw(He1 ) .
e∈E

We argue next that such a bound is not achievable.
Lemma 8.7. There exists hypergraphs H0 and a family of corresponding hyerpgraphs H1 such that there is
an unbounded gap of Ω(|V|) between fhtw(H0 ◦ H1 ) and fhtw(H0 ) · maxe∈E 0 fhtw(He1 )
Proof. Let V = {a1 , . . . , an , b1 , . . . , bn }. The hypergraph H0 has the following n hyperedges: ei = {a1 , . . . , an , bi }.
Note that this is essentially a star graph with fhtw(H0 ) = 1. Further, for every i ∈ [n], the graph He11 is the
star graph with ai as the center and a1 , . . . , ai−1 , ai+1 , . . . , an , bi as the leaves. Note that for every i ∈ [n],
fhtw(He1i ) = 1.
However, note that H0 ◦ H1 has a Kn as a subgraph (in particular the subgraph on {a1 , . . . , an } forms
a clique). Further the only other edges are the n “spokes”– (ai , bi ) for i ∈ [n]. It can be verified that
fhtw(H0 ◦ H1 ) ≥ n, which completes the proof.
54

We now come back to the question of proving an upper bound on fhtw(H0 ◦ H1 ). We first note that
the argument in proof of Proposition 8.5 is wasteful since it does not make use of any tree decomposition
representation of the hypergraphs in H1 . Next we describe a simple algorithm that tries to take advantage
of this choice.
We begin with an optimal ρ∗ -width tree decomposition (T, χ) of H0 as in the proof of Proposition 8.5.
Consider an arbitrary bag B in this tree decomposition. For every edge e ∈ E 0 such that e ∩ B 6= ∅, let
(Te , χe ) be an optimal ρ∗ -width tree decomposition for He1 . Root this tree at an arbitrary bag re . Build
new tree T ′ as follows: for each bag B we create a new bag B ′ as follows. For every edge e ∈ E 0 such
that e ∩ B 6= ∅, add re to B ′ and hang the rest of tree Te from B ′ . Using the argument in the proof of
Proposition 8.5, one can argue that for every bag B ′ , ρ∗H0 ◦H1 (B ′ ) ≤ fhtw(H0 ) · maxe∈E 0 fhtw(He1 ). Define
χ′ as follows: for every t ∈ V (T ), if B = χ(t), then χ′ (t) = B ′ . For every other vertex t (that comes from
some Te ), χ′ (t) = χe (t). However, (T ′ , χ′ ) is not a valid tree decomposition because it might not satisfy the
running intersection property. We fix this with obvious greedy ‘patchup’ phase. The final tree T ′′ = T ′ but
we will modify the bags by defining a new map χ′′ . For every vertex v ∈ V, consider the sub-forest of T with
vertices whose bags contain v. Add in the set of vertices t′ to this forest such that the resulting sub-graph
is a tree and for each such t′ , χ′′ (t′ ) ← χ′′ (t) ∪ {t′ } (for every t, χ′′ (t) is initialized to χ′ (t)). Note that when
the patchup phase is done (T ′′ , χ′′ ) is indeed a valid tree decomposition for H0 ◦ H1 . It is not too hard to
verify that this tree decomposition gives the following bound:
Lemma 8.8. The following holds
fhtw(H0 ◦ H1 )

≤

max ρ∗H0 ◦H1 (χ′′ (t))

t∈V (T ′′ )

≤ fhtw(H0 ) · max0 fhtw(He1 ) + max′′ ρ∗H0 ◦H1 (χ′′ (t) − χ′ (t)).
e∈E

t∈V (T )

We finish with two remarks:
1. In the worst-case the algorithm will result in (T ′′ , χ′′ ) = (T, χ) (after reducing (T ′′ , χ′′ )), in which case
are back in the proof of Proposition 8.5.
2. Lemma 8.8 for the hard instance in proof of Lemma 8.7 translates into a bound of n + 1, which is
essentially tight.

9

Concluding Remarks

The algorithms and ideas developed in this paper are not just on paper. Implementations of join algorithms
based on fractional hypertree width for counting graph patterns have shown that the theory predicts what
happens in practice very well: as they are faster than existing commercial systems by at least an order
of magnitude [70] for selected queries. Far beyond graph patterns, we have implemented InsideOut within
the commerical LogicBlox database system [9] with great performance results. Moreover, learning from the
beautiful work of Olteanu and Schleich [72, 83], we realized [66] that InsideOut can be used to train a large
class of machine learning models inside the database. Our implementation showed orders of magnitude
speedup over the traditional data modeler route of exporting the data and running it through R or Python.
Real-world implementation of InsideOut faces two additional hurdles. The first problem is that we do
not just have materialized predicates as inputs, we also have predicates such as a < b, a + b = c, negations
and so on. These predicates do not have a “size”. To solve this problem, one solution is to set the “size” of
those predicates to be ∞ while computing the AGM-bound. For instance, if we have a sub-query of the form
Q ← R(a, b), S(b, c), a + b = c, where R and S are input materialized predicates of size N , then by setting
the size of a + b = c to be infinite, AGM(Q) = N 2 . This solution does not work for two reasons. (1) If we
knew a + b = c, then it is easy to infer that |Q| ≤ N and also to compute Q in time Õ(N ): scan over tuples
in R, use a + b = c to compute c, and see if (b, c) ∈ S. In other words, the AGM-bound is no longer tight.
(2) The solution may give an ∞-bound when the output size is clearly bounded. Consider, for example,
55

the query Q ← R(a), S(b), a + b = c; in this case, {a, b, c} is the only hyperedge covering vertex c in the
fractional edge cover. Our implementation at LogicBlox makes use of generalizations of AGM to queries with
functional dependencies and immaterialized predicates (such as a + b = c). These new bounds are based on
a linear program whose variables are marginal entropies [3, 4].
The second problem is to select a good variable ordering to run InsideOut on. In principle, one does
not have to use the AGM-bound or the bounds from [3, 4] to estimate the cost of an FAQ subquery. If one
were to implement InsideOut inside any RDBMS, one could poll that RDBMS’s optimizer to figure out the
cost of a given variable ordering. However, there are n! variable orderings, and optimizer’s cost estimation
is time-consuming. Furthermore, some subqueries have inputs which are intermediate results. Hence, it is
much faster to compute a variable ordering minimizing the faqw of the query, defined on the bounds in [3,4].
As the problem is NP-hard, either an approximation algorithm (from Section 7) or a greedy heuristic suffices
in our experience.

Acknowledgments
This work was partly supported by NSF grants CNF-1409551, CCF-1319402, and by DARPA under agreement #FA8750-15-2-0009. The U.S. Government is authorized to reproduce and distribute reprints for
Governmental purposes notwithstanding any copyright thereon.

References
[1] Abiteboul, S., Hull, R., and Vianu, V. Foundations of Databases. Addison-Wesley, 1995.
[2] Abo Khamis, M., Ngo, H. Q., Ré, C., and Rudra, A. Joins via geometric resolutions: Worst-case
and beyond. In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS
2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015 (2015), T. Milo and D. Calvanese, Eds.,
ACM, pp. 213–228.
[3] Abo Khamis, M., Ngo, H. Q., and Suciu, D. Computing join queries with functional dependencies.
In Milo and Tan [63], pp. 327–342.
[4] Abo Khamis, M., Ngo, H. Q., and Suciu, D. What do shannon-type inequalities, submodular
width, and disjunctive datalog have to do with one another? CoRR abs/1612.02503 (2016).
[5] Adler, I. Width functions for hypertree decompositions. 2006. Ph.D. Dissertation, Albert-LudwigsUniversität Freiburg. 2006.
[6] Adler, I., and Weyer, M. Tree-width for first order formulae. Logical Methods in Computer Science
8, 1 (2012).
[7] Aji, S. M. Graphical models and iterative decoding. PhD thesis, California Institute of Technology,
2000.
[8] Aji, S. M., and McEliece, R. J. The generalized distributive law. IEEE Transactions on Information
Theory 46, 2 (2000), 325–343.
[9] 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. Sellis, S. B. Davidson, and Z. G. Ives, Eds., ACM, pp. 1371–1382.
[10] Arnborg, S., and Proskurowski, A. Linear time algorithms for NP-hard problems restricted to
partial k-trees. Discrete Appl. Math. 23, 1 (1989), 11–24.

56

[11] Atserias, A., Grohe, M., and Marx, D. Size bounds and query plans for relational joins. In FOCS
(2008), IEEE Computer Society, pp. 739–748.
[12] Bahar, R. I., Frohm, E. A., Gaona, C. M., Hachtel, G. D., Macii, E., Pardo, A., and
Somenzi, F. Algebraic decision diagrams and their applications. Formal Methods in System Design
10, 2/3 (1997), 171–206.
[13] Bakibayev, N., Kociský, T., Olteanu, D., and Zavodny, J. Aggregation and ordering in factorised databases. PVLDB 6, 14 (2013), 1990–2001.
[14] Bistarelli, S., Montanari, U., and Rossi, F. Semiring-based constraint satisfaction and optimization. J. ACM 44, 2 (Mar. 1997), 201–236.
[15] Bodlaender, H. L. Treewidth: algorithmic techniques and results. In Mathematical foundations of
computer science 1997 (Bratislava), vol. 1295 of Lecture Notes in Comput. Sci. Springer, Berlin, 1997,
pp. 19–36.
[16] Bodlaender, H. L. Treewidth: characterizations, applications, and computations. In International
Workshop on Graph-Theoretic Concepts in Computer Science (2006), Springer, pp. 1–14.
[17] Börger, E., Grädel, E., and Gurevich, Y. The classical decision problem. Universitext. SpringerVerlag, Berlin, 2001. Reprint of the 1997 original.
[18] Brault-Baron, J., Capelli, F., and Mengel, S. Understanding model counting for β-acyclic
cnf-formulas. CoRR abs/1405.6043 (2014).
[19] Brouwer, A., and Kolen, A. A super-balanced hypergraph has a nest point. Tech. Report.
[20] Cai, J., Chen, X., and Lu, P. Graph homomorphisms with complex values: A dichotomy theorem.
SIAM J. Comput. 42, 3 (2013), 924–1029.
[21] Cai, J.-Y., Lu, P., and Xia, M. The complexity of complex weighted Boolean #CSP. J. Comput.
System Sci. 80, 1 (2014), 217–236.
[22] Chekuri, C., and Rajaraman, A. Conjunctive query containment revisited. Theor. Comput. Sci.
239, 2 (2000), 211–229.
[23] Chen, H. Quantified constraint satisfaction and bounded treewidth. In Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI’2004, including Prestigious Applicants of Intelligent
Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004 (2004), pp. 161–165.
[24] Chen, H., and Dalmau, V. Decomposing quantified conjunctive (or disjunctive) formulas. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik,
Croatia, June 25-28, 2012 (2012), IEEE Computer Society, pp. 205–214.
[25] Chen, H., and Grohe, M. Constraint satisfaction with succinctly specified relations. J. Comput.
Syst. Sci. 76, 8 (2010), 847–860.
[26] Chen, H., and Mengel, S. A trichotomy in the complexity of counting answers to conjunctive queries.
CoRR abs/1408.0890 (2014).
[27] Cooley, J. W., and Tukey, J. W. An algorithm for the machine calculation of complex Fourier
series. Mathematics of Computation 19 (1965), 297–301.
[28] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms,
second ed. MIT Press, Cambridge, MA, 2001.

57

[29] Davis, M., Logemann, G., and Loveland, D. W. A machine program for theorem-proving. Commun. ACM 5, 7 (1962), 394–397.
[30] Dechter, R. Bucket elimination: A unifying framework for reasoning. Artif. Intell. 113, 1-2 (1999),
41–85.
[31] Dechter, R., Otten, L., and Marinescu, R. On the practical significance of hypertree vs.
treewidth. In ECAI 2008 - 18th European Conference on Artificial Intelligence, Patras, Greece, July
21-25, 2008, Proceedings (2008), M. Ghallab, C. D. Spyropoulos, N. Fakotakis, and N. M. Avouris,
Eds., vol. 178 of Frontiers in Artificial Intelligence and Applications, IOS Press, pp. 913–914.
[32] Dechter, R., and Pearl, J. Tree clustering for constraint networks. Artificial Intelligence 38, 3
(1989), 353–366.
[33] Dechter, R., and Rish, I. Directional resolution: The davis-putnam procedure, revisited. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning
(KR’94). Bonn, Germany, May 24-27, 1994. (1994), J. Doyle, E. Sandewall, and P. Torasso, Eds.,
Morgan Kaufmann, pp. 134–145.
[34] Durand, A., and Mengel, S. Structural tractability of counting of solutions to conjunctive queries. In
Joint 2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22, 2013 (2013),
W. Tan, G. Guerrini, B. Catania, and A. Gounaris, Eds., ACM, pp. 81–92.
[35] Durand, A., and Mengel, S. The complexity of weighted counting for acyclic conjunctive queries.
J. Comput. Syst. Sci. 80, 1 (2014), 277–296.
[36] Fagin, R. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 3 (1983),
514–550.
[37] Fischl, W., Gottlob, G., and Pichler, R. General and fractional hypertree decompositions: Hard
and easy cases. CoRR abs/1611.01090 (2016).
[38] Freuder, E. C. Complexity of k-tree structured constraint satisfaction problems. In Proceedings of
the 8th National Conference on Artificial Intelligence. Boston, Massachusetts, July 29 - August 3, 1990,
2 Volumes. (1990), H. E. Shrobe, T. G. Dietterich, and W. R. Swartout, Eds., AAAI Press / The MIT
Press, pp. 4–9.
[39] Gogate, V., and Domingos, P. Structured message passing. In Proceedings of the Twenty-Ninth
Conference on Uncertainty in Artificial Intelligence, Bellevue, WA, USA, August 11-15, 2013 (2013),
AUAI Press, Corvallis, Oregon.
[40] Goldberg, L. A., Grohe, M., Jerrum, M., and Thurley, M. A complexity dichotomy for
partition functions with mixed signs. SIAM J. Comput. 39, 7 (Aug. 2010), 3336–3402.
[41] Golomb, S. W., and Baumert, L. D. Backtrack programming. pp. 516–524.
[42] Gottlob, G., Greco, G., Leone, N., and Scarcello, F. Hypertree decompositions: Questions
and answers. In Milo and Tan [63], pp. 57–74.
[43] Gottlob, G., Leone, N., and Scarcello, F. Robbers, marshals, and guards: game theoretic and
logical characterizations of hypertree width. J. Comput. Syst. Sci. 66, 4 (2003), 775–808.
[44] Graham, M. H. On the universal relation, 1980. Tech. Report.
[45] Greco, G., and Scarcello, F. Counting solutions to conjunctive queries: structural and hybrid
tractability. In Hull and Grohe [53], pp. 132–143.

58

[46] Grohe, M., and Marx, D. Constraint solving via fractional edge covers. In SODA (2006), ACM
Press, pp. 289–298.
[47] Grohe, M., and Marx, D. Constraint solving via fractional edge covers. ACM Transactions on
Algorithms 11, 1 (2014), 4.
[48] Guruswami, V. Algorithmic results in list decoding.
[49] Guruswami, V., Umans, C., and Vadhan, S. Unbalanced expanders and randomness extractors
from Parvaresh-Vardy codes. J. ACM 56, 4 (2009), Art. 20, 34.
[50] Gyssens, M., Jeavons, P., and Cohen, D. A. Decomposing constraint satisfaction problems using
database techniques. Artif. Intell. 66, 1 (1994), 57–89.
[51] Gyssens, M., and Paredaens, J. A decomposition methodology for cyclic databases. In Advances
in Data Base Theory (1982), pp. 85–122.
[52] Huang, C., and Darwiche, A. Inference in belief networks: A procedural guide. Int. J. Approx.
Reasoning 15, 3 (1996), 225–263.
[53] Hull, R., and Grohe, M., Eds. Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, UT, USA, June 22-27, 2014 (2014),
ACM.
[54] Kask, K., Dechter, R., Larrosa, J., and Dechter, A. Unifying tree decompositions for reasoning
in graphical models. Artif. Intell. 166, 1-2 (2005), 165–193.
[55] Khatri, C. G., and Rao, C. R. Solutions to some functional equations and their applications to
characterization of probability distributions. Sankhya: The Indian Journal of Statistics, Series A 30, 2
(1968).
[56] Koch, C. Incremental query evaluation in a ring of databases. In Proceedings of the Twenty-Ninth
ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June
6-11, 2010, Indianapolis, Indiana, USA (2010), J. Paredaens and D. V. Gucht, Eds., ACM, pp. 87–98.
[57] Kohlas, J., and Wilson, N. Semiring induced valuation algebras: Exact and approximate local
computation algorithms. Artif. Intell. 172, 11 (2008), 1360–1399.
[58] Koller, D., and Friedman, N. Probabilistic graphical models. Adaptive Computation and Machine
Learning. MIT Press, Cambridge, MA, 2009. Principles and techniques.
[59] Maier, D. The Theory of Relational Databases. Computer Science Press, 1983.
[60] Marx, D. Approximating fractional hypertree width. ACM Trans. Algorithms 6, 2 (Apr. 2010),
29:1–29:17.
[61] Marx, D. Tractable structures for constraint satisfaction with truth tables. Theory Comput. Syst. 48,
3 (2011), 444–464.
[62] Marx, D. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM
60, 6 (2013), 42.
[63] Milo, T., and Tan, W., 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
(2016), ACM.
[64] Newman, M. E. J. The structure and function of complex networks. SIAM Rev. 45, 2 (2003), 167–256
(electronic).
59

[65] Ngo, H. Q., Nguyen, D. T., Ré, C., and Rudra, A. Beyond worst-case analysis for joins with
minesweeper. In Hull and Grohe [53], pp. 234–245.
[66] Ngo, H. Q., Nguyen, X., Olteanu, D., and Schleich, M. In-database factorized learning, 2017.
Manuscript.
[67] Ngo, H. Q., Porat, E., Ré, C., and Rudra, A. Worst-case optimal join algorithms. In PODS
(2012), M. Lenzerini and M. Benedikt, Eds., ACM, pp. 37–48.
[68] Ngo, H. Q., Porat, E., and Rudra, A. Efficiently decodable error-correcting list disjunct matrices
and applications (extended abstract). In Automata, languages and programming. Part I, vol. 6755 of
Lecture Notes in Comput. Sci. Springer, Heidelberg, 2011, pp. 557–568.
[69] Ngo, H. Q., Ré, C., and Rudra, A. Skew strikes back: New developments in the theory of join
algorithms. In SIGMOD RECORD (2013), pp. 5–16.
[70] Nguyen, D. T., Aref, M., Bravenboer, M., Kollias, G., Ngo, H. Q., Ré, C., and Rudra, A.
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 (2015), pp. 2:1–2:8.
[71] Olshevsky, V., and Shokrollahi, M. A. Matrix-vector product for confluent cauchy-like matrices
with application to confluent rational interpolation. In Proceedings of the Thirty-Second Annual ACM
Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA (2000), F. F. Yao and
E. M. Luks, Eds., ACM, pp. 573–581.
[72] Olteanu, D., and Schleich, M. F: regression models over factorized views. PVLDB 9, 13 (2016),
1573–1576.
[73] Olteanu, D., and Závodný, J. Size bounds for factorised representations of query results. ACM
Trans. Datab. Syst. 40, 1 (2015).
[74] Ordyniak, S., Paulusma, D., and Szeider, S. Satisfiability of Acyclic and Almost Acyclic CNF
Formulas. In FSTTCS 2010 (2010), vol. 8.
[75] Pagh, R., and Tsourakakis, C. E. Colorful triangle counting and a mapreduce implementation.
Inf. Process. Lett. 112, 7 (Mar. 2012), 277–281.
[76] Pan, V. Y. Nearly optimal computations with structured matrices. In Proceedings of the Eleventh
Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA.
(2000), D. B. Shmoys, Ed., ACM/SIAM, pp. 953–962.
[77] Pearl, J. Reverend bayes on inference engines: A distributed hierarchical approach. In Proceedings
of the National Conference on Artificial Intelligence. Pittsburgh, PA, August 18-20, 1982. (1982), D. L.
Waltz, Ed., AAAI Press, pp. 133–136.
[78] Pearl, J. Fusion, propagation, and structuring in belief networks. Artif. Intell. 29, 3 (Sept. 1986),
241–288.
[79] Pichler, R., and Skritek, S. Tractable counting of the answers to conjunctive queries. J. Comput.
Syst. Sci. 79, 6 (Sept. 2013), 984–1001.
[80] Rollon, E., Larrosa, J., and Dechter, R. Semiring-based mini-bucket partitioning schemes. In
IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing,
China, August 3-9, 2013 (2013), F. Rossi, Ed., IJCAI/AAAI.
[81] Rossi, F., Beek, P. v., and Walsh, T. Handbook of Constraint Programming (Foundations of
Artificial Intelligence). Elsevier Science Inc., New York, NY, USA, 2006.
60

[82] Scarcello, F. Query answering exploiting structural properties. SIGMOD Record 34, 3 (2005), 91–99.
[83] Schleich, M., Olteanu, D., and Ciucanu, R. Learning linear regression models over factorized
joins. In SIGMOD (2016), pp. 3–18.
[84] Suri, S., and Vassilvitskii, S. Counting triangles and the curse of the last reducer. In WWW (2011),
pp. 607–614.
[85] Tarjan, R. E., and Yannakakis, M. Simple linear-time algorithms to test chordality of graphs, test
acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 3 (July
1984), 566–579.
[86] Tracy, D. S., and Singh, R. P. A new matrix product and its applications in partitioned matrix
differentiation. Statistica Neerlandica 26, 4 (1972), 143–157.
[87] Tsourakakis, C. E. Fast counting of triangles in large real networks without counting: Algorithms
and laws. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008),
December 15-19, 2008, Pisa, Italy (2008), IEEE Computer Society, pp. 608–617.
[88] Ullman, J. D. Principles of Database and Knowledge-Base Systems, Volume II. Computer Science
Press, 1989.
[89] Veldhuizen, T. L. Triejoin: A simple, worst-case optimal join algorithm. In ICDT (2014), pp. 96–106.
[90] Yannakakis, M. Algorithms for acyclic database schemes. In VLDB (1981), pp. 82–94.
[91] Yu, C., and Ozsoyoglu, M. On determining tree-query membership of a distributed query. Informatica 22, 3 (1984), 261–282.
[92] Yuster, R., and Zwick, U. Fast sparse matrix multiplication. ACM Trans. Algorithms 1, 1 (July
2005), 2–13.
[93] Zhang, N., and Poole, D. A simple approach to Bayesian network computations. In Proceedings of
the Tenth Canadian Conference on Artificial Intelligence (1994), pp. 171–178.
[94] Zhang, N. L., and Poole, D. Exploiting causal independence in Bayesian network inference. J.
Artificial Intelligence Res. 5 (1996), 301–328.

A

More examples of problems reducible to FAQ

This section presents many examples showing how FAQ captures a wide range of problems, such as graphical
model inference, matrix multiplication, constraint satisfaction, quantified conjunctive query evaluation, etc.
Some of the reductions to FAQ-SS are already discussed in the seminal work of Dechter [30], Aji and McEliece
[8], and Kohlas and Wilson [57]; other reductions to FAQ-SS are new; all reductions to the general FAQ
problem (over multiple semirings) are new. We first present the examples for FAQ-SS by considering the
following semirings.
• ({true, false}, ∨, ∧): the Boolean semiring
• (R, +, ×): the sum-product semiring
• (R+ , max, ×): the max-product semiring, which is essentially equivalent to the (R, min, +) semiring.17
• (2U , ∪, ∩): the set semiring, where U is some set called the universe. In this case, ∅ is the additive
identity, and U itself is the multiplicative identity.
17 If

the ranges of factors are non-negative, then we can take log of the factors to turn product into sum.

61

A.1

The Boolean semiring

Example A.1 (Satisfiability). Let ϕ be a CNF formula over n Boolean variables X1 , . . . , Xn . Let H = (V, E)
be the hypergraph of ϕ. Then, each clause of ϕ is a factor ψS , and the question of whether ϕ is satisfiable
is the same as evaluating the constant function
_^
ϕ=
ψS (xS ).
x S∈E

Note that in this case each factor is very compactly represented. The size of each factor ψS is O(|S|), i.e.
linear in the number of variables that the factor is on. We will have much more to say about such compact
representation in Sections 8 and G.
Example A.2 (k-colorability). Let G = (V, E) be a graph. Define the following instance of FAQ-SS. Let
V = {Xv | v ∈ V }, E = E, and Dom(Xv ) = [k]. Define a factor ψuv for every edge uv ∈ E to be the predicate
ψu,v (c1 , c2 ) = (c1 6= c2 ). The question of whether G is k-colorable is equivalent to evaluating the following
constant function:
_ ^
ϕ=
ψuv (xu , xv ).
x uv∈E

Even for non-constant k, each factor in this example is also very compactly represented, amounting to an
inequality.

Example A.3 (Boolean conjunctive query). The Boolean conjunctive query evaluation problem (BCQ) can
be written as follows. The query Φ has input relation set atoms(Φ). Each relation R ∈ atoms(Φ) is on
attribute set vars(R). We want to know if there exists a tuple satisfying all relations:
^
R(vars(R))
Φ = ∃X1 · · · ∃Xn
R∈atoms(Φ)

Define a hypergraph H = (V, E), where V is the set of all attributes, and E = {vars(R) | R ∈ atoms(Φ)}. For
each S ∈ E corresponding to relation R, there is a factor ψS where ψS (xS ) = (xS ∈ R). Then, the problem
is reduced to evaluating the constant function
_^
ϕ=
ψS (xS ).
x S∈E

Note that in this case, the typical input relation encoding is to list all tuples that belong to a given input
relation. Thus, the inputs are not as compact as the first two examples.
Example A.4 (Constraint satisfaction). The Constraint Satisfaction Problem (CSP) is reducible to FAQ-SS
in the obvious way. Note that SAT, 3-colorability, BCQ are all special cases of CSP.
To summarize, the subtle issue of input encodings already shows up in the above examples. In SAT each
input factor ψS is encoded using a clause of size O(|S|). In BCQ we use the listing encoding, where each
input factor is encoded with a table of entries whose functional values are true. The CSP problem as defined
above is underspecified.
Example A.5 (Conjunctive query). In the general conjunctive query evaluation (CQE) problem, the query
has existential quantifiers over a subset of variables in [n] − F . It should be obvious that conjunctive query
evaluation is reduced to the following form of FAQ-SS. The problem is to compute the output function
_ ^
ϕ(xF ) =
ψS (xS ).
x[n]−F S∈E

62

Example A.6 (Natural join query). The natural join query is the CQE problem when all variables are free.
Essentially, a natural join query is a quantifier-free conjunctive query, after some pre-processing steps. The
reason we need pre-processing is because, strictly speaking in a conjunctive query the same relation might
appear several times, and the same variable might appear more than once in the same atom. This point is
immaterial at this point of our discussion.
Example A.7 (Coding theory). Here’s a typical setting in coding theory. Let q be a prime power, and Fq
denote the field of order q. Let n ≥ k ≥ 1 be integers. Then, an (n, k)q -code C is a simply a subset of Fnq of
size Fkq . If every pair of codewords (i.e. members of C) have Hamming distance at least d, then we call the
code an (n, k, d)q -code. The List Recovery problem [48] in (modern) coding theory is the following problem.
We are given, for each position i ∈ [n] of the code, a subset Si ⊆ Fq of symbols. The objective is to “recover”
the set of all codewords c = (c1 , . . . , cn ) ∈ C for which ci ∈ Si for all i. (Technically, we also want to give
some lax where ci ∈ Si for only a fraction of the positions i; but that requirement is not important for our
discussion here.) List recoverable codes are codes for which, if the Si are “small” then the list of codewords
to be recovered (satisfying the above condition) is also “small.” Of course, we also would like the recovery
process to be as fast as possible.
The list recovery paradigm has found important applications. It should be noted that when |Si | = 1
for all i then we get back the list decoding problem. Powerful expander graphs are constructed using the
Parvaresh-Vardy family of codes, precisely because they are list recoverable [49]. In [68], we used list recovery
to construct very good group testing schemes.
In the list recovery problem, we have n + 1 factors: ψ[n] , and ψi for i ∈ [n], where
ψ[n] (c)
ψi (c)

= true iff c ∈ C
= true iff c ∈ Si .

The FAQ-SS instance is
ϕ(c1 , . . . , cn ) = ψ[n] (c1 , . . . , cn ) ∧

n
^

ψi (ci ).

i=1

A.2

The sum-product semiring

Example A.8 (Complex network analysis). In complex network analysis we often want to count the number
of occurrences of a given small (induced or non-induced) subgraph H inside of a massive graph G. This
problem is pervasive in social network and biological network analysis, where each occurrence of the subgraph
is a “pattern” that one wants to mine from the network. A canonical example is the triangle counting problem,
where we want to count the number of triangles in a given graph G = (V, E). The number of triangles is
used to compute the clustering coefficients [64, 84] and transitivity ratio [75, 87]. We reduce triangle counting
to FAQ-SS as follows. The FAQ-SS’s hypergraph is H = (V, E), where
V

= {1, 2, 3},

E

= {{1, 2}, {1, 3}, {2, 3}}

The domains are Dom(Xi ) = V , for i ∈ [3]. The factors are all the same: ψ12 = ψ13 = ψ23 = ψ, where
(
1 if {u, v} ∈ E, u < v
ψ(u, v) =
0 otherwise.
(In terms of input encoding, the factor ψ can be represented with a data structure of size O(|E|), for
example.) The problem is to compute the constant function
X X X
ϕ=
ψ(x1 , x2 ) · ψ(x1 , x3 ) · ψ(x2 , x3 ).
x1 ∈V x2 ∈V x3 ∈V

The same strategy can be used to count the number of occurrences of H in G, where H is a fixed graph.
For example, H can be a k-clique.
63

Remark A.9. If we’d like to list induced subgraphs, there should be other factors indicating the nonexistence of edges in the subgraph pattern. These factors correspond to inequalities, and they can be
compactly represented.
Example A.10 (#SAT). In SAT we want a Boolean answer: “is the formula satisfiable or not?” In #SAT
we want a more specific piece of information: “exactly how many satisfying assignments are there?” Let Φ
be a CNF formula over n Boolean variables X1 , . . . , Xn . Let H = (V, E) be the hypergraph of Φ. Then, for
each clause C of Φ there is a factor ψS defined by
(
1 if xS satisfies C
ψS (xS ) =
0 otherwise.
The problem of counting the number of satisfying assignments is the same as evaluating the constant function
XY
ϕ=
ψS (xS ).
x S∈E

Example A.11 (Permanent). #SAT is #P-complete. Another canonical #P-complete problem is Permanent, which is the problem of evaluating the permanent perm(A) of a given binary square matrix A. Let Sn
denote the symmetric group on [n], then the permanent of A = (aij )ni,j=1 is defined as follows.
perm(A) :=

n
X Y

aiπ(i) .

π∈Sn i=1

Note that perm(A) has exactly the same form as det(A) written using Leibniz formula except that the signs
are all 1.
The Permanent problem can be written in the sum-product form as follows. Say the input matrix
is

A = (aij ), there is a singleton factor ψi for each vertex i, where ψi (j) = aij . Then, there are n2 factors
ψjk for j 6= k ∈ [n], where ψjk (x, y) = 1 if x 6= y and 0 if x = y. The problem is to evaluate the constant
function
Y
X Y
ψjk (xj , xk ).
ψi (xi )
ϕ=
x i∈[n]

(j6=k)

Example A.12 (Probabilistic graphical models). We consider probabilistic graphical models (PGMs) on
discrete finite domains. Without loss of generality, we restrict ourselves to undirected graphical models (also
called Markov Random Field, factor graph, Gibbs distribution, etc.) If the input model is directed, we
moralize it to get an undirected model. The model can be represented by a hypergraph H = (V, E), where
there are n discrete random variables X1 , . . . , Xn on finite domains Dom(X1 ), . . . , Dom(Xn ) respectively,
and m factors (also called potential functions):
Y
ψS :
Dom(Xi ) → R+ .
i∈S

Typically, we want to learn the model and perform inference from the model.18 For example, we might want
to
• Compute the marginal distribution of some set of variables
• Compute the conditional distribution p(xA | xB ) of some set of variables A given specific values to
another set of variables xB .
18 From a Bayesian point of view, there is no difference between the two. “Learning” refers to the task of estimating the
parameters of a model given the observed data. For example, we often estimate the parameters using the Maximum A Posteriori
(MAP) estimate θ̂ = arg maxθ p(θ | xA ) = arg maxθ {log p(xA | θ) + log p(θ)}. Here, xA is the set of observed values. (MAP is
also called MPE which stands for most probable explanation, because it is the mode of the posterior distribution.) “Inference”
refers to the task of computing p(xB | xA , θ), where xB are the hidden variables and θ are known parameters.

64

• Compute arg maxxA p(xA | xB ) (for MAP queries, for example).
When we condition on some variables, we can restrict the factors to only those entries that match the
conditioned variables. It is obvious that the first two questions above are special cases of the FAQ-SS
problem on the sum-product semiring. (The third question is on the max-product semiring.) These are
well-known facts [58].
Since matrix-vector multiplication is a special case of matrix-matrix multiplication, Example 1.1 also
shows that the matrix vector multiplication problem is a special case of the FAQ-SS problem. Given the
above, it also follows that computing the Discrete Fourier Transform is a special case of FAQ-SS. Next, we
present another interpretation of the DFT from Aji’s thesis [7], which immediately shows that our algorithm
implies the Fast Fourier Transform (FFT).
Example A.13 (Discrete Fourier Transform). Recall that the discrete Fourier transform (DFT) is the
x·y
matrix vector multiplication where Axy = ei2π n . For this example, we will consider the case when n = pm
for some prime p and integer m ≥ 1. Recall that the DFT is defined as follows:
ϕ(x) =

n−1
X

by · ei2π

x·y
n

.

y=0

P
Pm−1
i
j
Write x = m−1
i=0 xi · p and y =
j=0 yj · p in their base-p form. Then we can re-write the transform
above as follows:
X

ϕ(x0 , x1 , . . . , xm−1 ) =

by · ei2π

P

j+k
0≤j+k≤2m−2 xj ·yk ·p
n

.

(y0 ,...,ym−1 )∈Fm
p

Recalling that n = pm , note that for any j + k ≥ m, we have ei2π
to
X
by ·
ϕ(x0 , x1 , . . . , xm−1 ) =
(y0 ,...,ym−1 )∈Fm
p

xj ·yk ·pj+k
n

Y

= 1. Thus, the above is equivalent
e

i2π

xj ·yk
pm−j−k

.

0≤j+k<m

The above immediately suggests the following reduction to FAQ-SS. Let H = (V, E) where V =
{X0 , X1 , . . . , Xm−1 , Y0 , Y1 , . . . , Ym−1 } and E has an edge (Xj , Yk ) for every j, k ∈ {0, 1, . . . , m − 1} such
that j + k < m. Further, there is another edge (Y0 , Y1 , . . . , Ym−1 ). The variable domains are Dom(Xi ) =
Dom(Yi ) = {0, 1, . . . , p − 1}. For every j, k ∈ Fp such that j + k < m, the corresponding factor
ψXj ,Yk : F2p → D
is defined as
ψXj ,Yk (x, y) = e

i2π

x·y
pm−j−k

.

Finally, the factor ψY : Fm
p → D is defined as
ψY (y0 , y1 , . . . , ym−1 ) = b(y0 ,y1 ,...,ym−1 ) .
Then the output is
ϕ(x0 , x1 , . . . , xm−1 ) =

X

ψY (y0 , y1 , . . . , ym−1 ) ·

Y

ψXj ,Yk (xj , yk ).

0≤j+k<m

(y0 ,...,ym−1 )∈Fm
p

Example A.14 (Graph homomorphism function). Given a (non-hyper) graph G and an m × m symmetric
matrix A = (aij ). The graph homomorphism function is defined by
X
Y
aζ(u),ζ(v) .
ZA (G) =
ζ:V →[m] uv∈E(G)

65

(The reader is referred to the masterpieces by Cai et al. [20], Goldberg et al. [40], references therein for a
long and fascinating history of this problem.) The corresponding FAQ instance is
X X Y
ψuv (xu , xv ),
···
ϕ=
x1

xn uv∈E(G)

where Dom(Xi ) = [m], and ψuv : [m] × [m] → D are identical factors, mapping ψuv (xu , xv ) = axu ,xv .
Example A.15 (Holant problem). The Holant problems can also be expressed using FAQ-SS. Essentially,
in a Holant instance there is a function fv for each vertex of a graph G, where the function is on the set
of incident edges. Each edge can be assigned a domain value. The problem is to compute the sum over all
edge assignments of the product of all vertex factors. See [21] for more details.

A.3

The max-product semiring

In addition to MAP queries in PGMs which are well-known to be reducible to FAQ-SS on the max-product
semiring, the following is another common instance of the max-product semiring.
Example A.16 (Maximum Likelihood Decoder for Linear Codes). We present the instantiation of Maximum
Likelihood Decoding (MLD) for linear codes as an instance of FAQ-SS from Aji and McEliece [8]. We consider
the decoding problem from a discrete memoryless channel. We assume that the alphabet is F2 and given
y, x ∈ F2 , ψp (y, x) denotes the probability of the receiver receiving y given that x was transmitted over the
channel. Let C be a binary linear code with dimension k and block length n. Then given a received word
y ∈ Fn2 and a codeword c ∈ C, the probability that the receiver receives y when c was transmitted is given
by
n
Y
ψp (yi , ci ).
Pr[y|c] =
i=1

The maximum likelihood decoder, given y ∈ Fn2 outputs the codeword c ∈ C that is most likely, i.e. it
outputs:
arg max Pr[y|c].
c∈C

For simplicity, we will concentrate on the related problem of computing the most likely probability, i.e.
max Pr[y|c].
c∈C

(33)

Define the hypergraph V = ([n], E) as follows. There is a singleton edge {i} for every i ∈ [n] (with the
corresponding factor ψi (Yi , Xi ) = ψp (Yi , Xi )). Further, the linear code C has an (n − k) × n parity check
matrix H such that c ∈ C if and only if H · cT = 0. Then for each row Hj , we have supp(Hj ) ∈ E. (The
factor ψHj (xsupp(Hj ) ) is defined to be 1 is the corresponding parity check is satisfied by x and 0 otherwise.)
It is easy to verify that the FAQ-SS instance below is equivalent to the problem in (33):
Y
Y
ψHj (xsupp(Hj ) ).
ψi (yi , xi ) ·
ϕ = maxn
x∈Fq

A.4

i∈[n]

j∈[n−k]

The set semiring

Example A.17 (Natural join query). Consider the natural join query
Φ = ✶R∈atoms(Φ) R.

66

Let H = (V, E) be the query’s hypergraph.
Qn We define a factor ψS for each S ∈ E as follows. The domain of
the set semiring is D = 2U , where U = i=1 Dom(Xi ). Let R be the relation corresponding to S. Then, ψS
(
t | πS (t) = xS
if xS ∈ R
ψS (xS ) =
∅
if xS ∈
/R
Computing the output of Φ becomes computing the constant set-valued function
[\
ϕ=
ψS (xS ).
x S∈E

A.5

Applications of the FAQ problem

The FAQ-SS problem is quite general, as we have seen above. However, there are at least two classes of
problems which are not captured by the basic FAQ-SS formulation above.
First, consider the problem of counting the number of answers to a conjunctive query. This is called the
#CQ problem [79]. If the input query is quantifier-free, then we can formulate the problem as FAQ-SS on the
sum-product semiring by mapping true to 1 and false to 0. However, when the query does have existential
quantifiers, the straightforward mapping does not work.
Second, consider the general Quantified Conjunctive Query (QCQ) problem, which has both existential
and universal quantifiers (and a conjunction of atoms inside). It is not possible to reduce this problem to
FAQ-SS. The related problem of counting the number of solutions to such formulas (#QCQ) is even harder.
Example A.18 (#CQ). Let Φ be a conjunctive formula of the form

^
Φ(X1 , . . . , Xf ) = ∃Xf +1 . . . Xn 

R∈atoms(Φ)



R ,

and the problem is to count the number of assignments (x1 , . . . , xf ) such that Φ(x1 , . . . , xf ) is satisfied.
Then, we can reduce this problem to FAQ with the constant function
X X
Y
···
max · · · max
ϕ=
ψS (xS ).
x1

xf

xf +1

xn

S∈E

Here, ψS (xS ) = δxS ∈R , where R ∈ atoms(Φ) is the atom corresponding to S. Note that
commutative.

P

and max are not

Example A.19 (QCQ – First Reduction). Let Φ be a first order formula of the form


^
R ,
Φ(X1 , . . . , Xf ) = Qf +1 Xf +1 · · · Qn Xn 
R∈atoms(Φ)

where Qi ∈ {∃, ∀}, for i > f . The problem is to compute the relation Φ on the free variables X1 , . . . , Xf .
Then, we can reduce this problem to FAQ with the function
ϕ(x1 , · · · , xf ) =

L(f +1)
xf +1

···

L(n) Q
xn

S∈E

ψS (xS ).

Similar to Example A.18, ψS (xS ) = δxS ∈R , where R ∈ atoms(Φ) is the atom corresponding to S. And,
L(i)
L(i)
= max if Qi = ∃ and
= min if Qi = ∀.
There is another way to reduce QCQ to FAQ. It is this reduction that we will use later in the paper.

67

Example A.20 (QCQ – Second Reduction). Let Φ be a first order formula of the form


^
R ,
Φ(X1 , . . . , Xf ) = Qf +1 Xf +1 · · · Qn Xn 
R∈atoms(Φ)

where Qi ∈ {∃, ∀}, for i > f . The problem is to compute the relation Φ on the free variables X1 , . . . , Xf .
Then, we can reduce this problem to FAQ with the function
L +1)
L(n) Q
ϕ(x1 , · · · , xf ) = (f
S∈E ψS (xS ).
xf +1 · · ·
xn

Similar to Example A.18, ψS (xS ) = δxS ∈R , where R ∈ atoms(Φ) is the atom corresponding to S. And,
(
L(i)
max if Qi = ∃,
=
×
if Qi = ∀.

What is interesting to note about the above reduction is that the product occurs as an aggregate operator
over (universally quantified) variables and also as an aggregate operator over the input factors.

Example A.21 (Example 1.3 revisited: #QCQ). This is similar to the above two examples. Let Φ be a
first order formula of the form


^
R ,
Φ(X1 , . . . , Xf ) = Qf +1 Xf +1 · · · Qn Xn 
R∈atoms(Φ)

where Qi ∈ {∃, ∀}, for i > f . The problem is to count the number of tuples in relation Φ on the free variables
X1 , . . . , Xf . Then, we can reduce this problem to FAQ with the constant function
X X L(f +1)
L(n) Q
···
ϕ=
S∈E ψS (xS ).
xf +1 · · ·
xn
x1

xf

Where ψS (xS ) = δxS ∈R , where R ∈ atoms(Φ) is the atom corresponding to S. And,
(
L(i)
max if Qi = ∃,
=
×
if Qi = ∀.

B

Reductions from non-semiring to semiring

In practice, we often encounter queries which have the same format as FAQ except that some of the aggregates
⊕(i) are neither product not semiring aggregates. Suppose that we want to compute the function
Y
Dom(Xi ) → D
ϕ:
i∈[f ]

defined by
ϕ(x[f ] ) =

L(f +1)
xf +1

···

L(n) N
xn

S∈E

ψS (xS ).

WLOG let ⊕ := ⊕(n) be neither a product nor a semiring aggregate (Otherwise, we could have eliminated xn
as described in Section 5.2). In many situations, it is possible to find a two-way mapping between (D, ⊕, ⊗)
¯ ⊗)
¯ where D̄ is some extended domain and ⊕,
¯ ⊗
¯ are extended versions
and some commutative semiring (D̄, ⊕,
of ⊕, ⊗ that fit the new domain D̄. If such a mapping exists, then we can transfer input factors into D̄, carry
¯ ⊗),
¯ and then transfer the results back to the original domain
out the calculations over the semiring (D̄, ⊕,
D, in order to bypass dealing with non-semirings.
Formally, suppose that there exists a function f¯ : D → D̄ and a function f : D̄ → D that satisfy the
following conditions:
68

1. For all x1 , . . . , xn ∈ D (where n ≥ 1),

L

i∈[n]

xi = f

¯ f¯(y).
2. For all x, y ∈ D, f¯(x ⊗ y) = f¯(x)⊗

L̄

¯


.

i∈[n] f (xi )

¯ = f (x̄) ⊗ f (ȳ).
3. For all x̄, ȳ ∈ D̄, f (x̄⊗ȳ)
If the above conditions are met (Examples B.2 and B.3 below), then variable elimination (Section 5.1.2) can
take place as if (D, ⊕, ⊗) were a commutative semiring.

=
=
=

ϕ(x[f ] )
L(f +1)

(34)
L(n−1)

hL̄(n) N̄

i

¯ (ψS (xS ))
i
 L̄(n) N̄
L(f +1)
L(n−1)
¯
¯
f
f¯ (ψS (xS )) ⊗
xn
xf +1 · · ·
xn
S∈∂(n) f (ψS (xS ))
S ∈∂(n)
/
L̄(n) N̄

L(f +1)
L(n−1) N
¯
ψS (xS ) ⊗ f
xf +1 · · ·
xn
S ∈∂(n)
/
xn
S∈∂(n) f (ψS (xS )) .
{z
}
|
xf +1

···

xn−1

f

xn

S∈E f

hN̄

(35)
(36)
(37)

new factor ψUn −{n} over D

If only conditions 1 and 2 (but not 3) are met (Example B.4), then we can still apply steps (35) and
(36) (but not (37)). In particular, factors ψS (xS ) will have to remain transformed f¯ (ψS (xS )) into the new
domain D̄, and the new factor will be over D̄ as well. We cannot transfer back to the original domain D
¯ have been computed.
until all products ⊗
¯ ⊗
¯
Let 0, 1 ∈ D denote the identities for ⊕, ⊗ respectively, and 0̄, 1̄ ∈ D̄ denote the identities for ⊕,
respectively. Many natural FAQ algorithms rely on zero entries in order to save computation (e.g., OutsideIn
and InsideOut in Sections 5.1.1 and 5.2 respectively). Therefore, it is desired that f and f¯ satisfy the
properties 0̄ = f¯(0) and 0 = f (0̄).
Remark B.1.
Notice
1 and 3 above

 that
 conditions

 imply that f (1̄) = 1. In particular, assuming f (1̄) 6= 1,
¯ 1̄ = f f¯(1) = 1, while f f¯(1) ⊗ f (1̄) = 1 ⊗ f (1̄) = f (1̄).
we have f f¯(1)⊗
Here are a few practical examples that can clarify the above abstract ideas (In all of those examples, we
have 0̄ = f¯(0), 0 = f (0̄), 1̄ = f¯(1), and 1 = f (1̄)).

Example B.2 (Average). Given n ≥ 1 numbers x1 , . . . , xn ∈ R, let avg(x1 , . . . , xn ) denote the average of
non-zero numbers among x1 , . . . , xn . (By convention, when all numbers are zeros, let the average be zero.)
(
0
if x1 = x2 = · · · = xn = 0,
avg(x1 , . . . , xn ) :=
x1 +···+xn
otherwise.
δx 6=0 +···+δx 6=0
1

n

(R, avg, ×) is not a semiring because avg is not associative (e.g., avg(avg(1, 2), 3) 6= avg(1, avg(2, 3))). How¯ ⊗)
¯ where ⊕
¯ and ⊗
¯ are defined as follows.
ever, we can extend it into the commutative semiring (R × N, ⊕,
For all (a1 , b1 ), (a2 , b2 ) ∈ R × N,
¯ 2 , b2 ) := (a1 + a2 , b1 + b2 ),
(a1 , b1 )⊕(a
¯ 2 , b2 ) := (a1 × a2 , b1 × b2 ).
(a1 , b1 )⊗(a
¯
Define f : R → R × N such that for all x ∈ R,
f¯(x) := (x, δx6=0 ).
Define f : R × N → R such that for all (a, b) ∈ (R, N),
(
0
f (a, b) := a
b

if b = 0,
otherwise.

It is not hard to verify that conditions 1, 2, and 3 are met in this example. Also, notice that 0 = 0, 1 = 1,
0̄ = (0, 0) and 1̄ = (1, 1).
69

Example B.3 (Uniqueness quantification (∃!)). Given n ≥ 1 Boolean variables b1 , . . . , bn , let unique(b1 , . . . , bn )
denote the truth value of whether there is a unique bi whose value is true.
unique(b1 , . . . , bn ) := (∃!i ∈ [n] | bi = true).
The problem with unique is that it is not cumulative over {true, false} (For example, unique(true, true, true) =
false while unique(unique(true, true), true) = true.) In fact, binary unique reduces to logical XOR, while nary unique does not correspond to XOR for n > 2. Therefore, we cannot use the commutative semiring
({true, false}, XOR, ∧) to solve this FAQ. However, we can extend the domain to become {0, 1, 2} and define
¯ ⊗)
¯ such that for all x, y ∈ {0, 1, 2},
a commutative semiring ({0, 1, 2}, ⊕,
¯ := min(x + y, 2),
x⊕y
¯ := min(x × y, 2).
x⊗y
Define f¯ : {true, false} → {0, 1, 2} such that
f¯(true) := 1,
f¯(false) := 0.
Define f : {0, 1, 2} → {true, false} such that for all x ∈ {0, 1, 2},
f (x) := (x = 1).
Notice that conditions 1, 2, and 3 are met in this example. Also, notice that 0 = false, 1 = true, 0̄ = 0, and
1̄ = 1.
Example B.4 ((R, max, ×)). (R, max, ×) is not a semiring because max does not have an identity over R.
However, we can fix this by extending the domain to become D := R ∪ {NaN} where NaN is a special symbol
having the following properties. For all x ∈ D,
max(x, NaN) = max(NaN, x) = x,
min(x, NaN) = min(NaN, x) = x,
x × NaN = NaN × x = NaN.
Now, we have the max identity 0 = NaN and the product identity identity 1 = 1. However, (D, max, ×)
is still not a semiring because × does not distribute over max in R (e.g., −1 × max(1, 2) 6= max(−1, −2)).
¯ ⊗)
¯ where
However, we can extend it into the commutative semiring (D̄, ⊕,


D̄ := (NaN, NaN) ∪ (a, b) ∈ R2 | a ≤ b ,
and for all (a1 , b1 ), (a2 , b2 ) ∈ D̄

¯ 2 , b2 ) := (min(a1 , a2 ), max(b1 , b2 )),
(a1 , b1 )⊕(a
¯ 2 , b2 ) := (min(a1 a2 , a1 b2 , b1 a2 , b1 b2 ), max(a1 a2 , a1 b2 , b1 a2 , b1 b2 )).
(a1 , b1 )⊗(a
Notice that 0̄ = (NaN, NaN) while 1̄ = (1, 1).
Define f¯ : D → D̄ such that for all x ∈ D,
f¯(x) := (x, x).
Define f : D̄ → D such that for all (a, b) ∈ D̄,
f (a, b) := b.
This example meets conditions 1 and 2 but not 3.
70

C

Tree decompositions and variable elimination

In this section, we prove Proposition 4.9, Proposition 4.10, and Lemma 4.12. To this end, we first describe
ways to convert back and forth between a tree decomposition and a vertex ordering of a given hypergraph.
We will also need the notion of a reduced (or non-redundant) tree decomposition.
Minimal tree decomposition The definition of tree decompositions doesn’t say anything about how
large a tree decomposition is, i.e. how many vertices T has. Fortunately, many tree decompositions are
“redundant” in the sense that one bag might be a subset of another. In that case, we can reduce the tree
decomposition as follows. Let (T, χ) be a tree decomposition of a hypergraph H. Suppose there is a bag
B that is a subset of another bag B ′ . Note that there is a unique path B = B0 , B1 , . . . , Bk = B ′ because
T is a tree. Then, B has to be a subset of every bag on this path. We can thus remove B, connect the
all neighbors of B, other than B1 , to B1 . It is easy to see that the new tree is a tree decomposition of the
same hypergraph still. When no such bag removal is possible, we have a reduced tree decomposition or a
non-redundant tree decomposition. The following shows that reduced tree decompositions do not have too
many nodes.
Proposition C.1. Let (T, χ) be a reduced tree decomposition of a connected hypergraph H on n vertices,
then T has at most n nodes.
Proof. Any leaf bag B of T necessarily has a private vertex v, i.e. a vertex that does not belong to any other
bag. Now, suppose we remove v from B. If B is a subset of its neighbor, then we also remove B. Either
way, what we end up with is a reduced tree decomposition of a hypergraph on n − 1 vertices. Induction
completes the proof.
Tree decomposition from vertex ordering. Given any vertex ordering σ = v1 , . . . , vn of a hypergraph
H = (V, E), we construct a tree decomposition recursively as follows. (Recall the hypergraph sequence
σ
defined in Definition 4.8. First, by induction, we construct a tree decomposition Tn−1 of the graph Hn−1
using the vertex ordering v1 , . . . , vn−1 . (The base case, i.e. the tree decomposition T1 is trivial as the
σ
hypergraph H1 has only one vertex.) Note that Unσ − {vn } is a hyperedge of Hn−1
. Let B be the bag of
Tn−1 that contains this hyperedge. Now, create a new bag Un and connect it to B. Note that all hyperedges
in ∂(vn ) are subsets of Unσ . One can verify by induction that this is indeed a tree decomposition of Hnσ = H.
The tree decomposition constructed this way has at most n bags, but it is not necessarily non-redundant.
We reduce the tree decomposition to make it a non-redundant, and refer to the final tree decomposition as a
tree decomposition induced by the vertex ordering. The following proposition is straightforward by induction.
Proposition C.2. In a tree decomposition (T, χ) induced by the vertex ordering σ = (v1 , . . . , vn ), every bag
of T is a set Ukσ , for some k ∈ [n]. Furthermore, (T, χ) is non-redundant.
GYO-elimination procedure. Next we explain why the vertex ordering is the reverse of what typically
is called an “elimination order”. The typical way to obtain a good vertex ordering from a tree decomposition
is the GYO-elimination procedure [44, 85, 91]. In this procedure, we repeatedly apply the following two
operations on a tree decomposition: (1) remove any bag that is a subset of another bag, (2) remove any
vertex that belongs to only one bag. Typically this procedure is done by fixing arbitrarily a root bag and
eliminating bags and vertices from the leaves up to the root bag.
The reversed sequence of vertices that were removed is a vertex ordering whose induced (fractional) width
is as good as the (fractional) width of the tree decomposition, as we show below. One key aspect of the
GYO-procedure is that we could have fixed any bag as the root bag, and thus the vertices inside this bag
can be eliminated last, which means they will occur first in the resulting vertex ordering.
Vertex ordering from tree decomposition. However, in this section for technical reasons we also
describe a specific realization of the basic GYO-elimination procedure. Given a tree decomposition (T, χ) of
71

H = (V, E) we construct an ordering of vertices v1 , . . . , vn as follows. First, we make (T, χ) a reduced tree
decomposition as described above. Second, we designate a node of T as the root node. For every vertex
v ∈ V, let tv denote the node highest in the tree such that v ∈ χ(tv ). We call the bag χ(tv ) the “owner” of
of v, and v a “private vertex” of χ(tv ). We construct a vertex ordering as follows:
1. If T is empty, return the empty sequence.
2. Otherwise, take any leaf node t of T , let Pt denote the set of private vertices of χ(t). (Because T is
reduced, Pt is not empty!)
3. Remove t from T , resulting in a tree T ′ . Let σ ′ denote the vertex ordering of V − Pt obtained from T ′
by induction. Let σ be obtained by appending vertices in Pt to the end of σ ′ . (Note that T ′ still has
the same root as T .)
The resulting vertex ordering is called a vertex ordering induced by the tree decomposition. The following
follows by induction.
Proposition C.3. Let σ = (v1 , . . . , vn ) be a vertex ordering induced by a tree decomposition (T, χ), then
Ukσ is a subset of some bag of T , for every k ∈ [n]. Furthermore, the vertex ordering can be constructed in
polynomial time.
Now we are ready to characterize acyclicity and widths using vertex orderings.
Proof of Proposition 4.9. For the forward direction, assume H is α-acyclic. Then, there is a tree decomposition (T, χ) of H in which every bag is a hyperedge. Let σ = (v1 , . . . , vn ) be an induced vertex ordering of
(T, χ). By Proposition C.3, Ukσ ⊆ χ(t) for some t ∈ V (T ). Since χ(t) is a hyperedge of H, χ(t) ∈ Ek and
hence Ukσ = χ(t) ∈ ∂ σ (vk ).
Conversely, suppose there is a vertex ordering σ for which Ukσ ∈ ∂ σ (vk ) for all k ∈ [n]. By induction,
σ
Hn−1 is α-acyclic. Thus, there is a tree decomposition Tn−1 in which every bag of Tn−1 is a hyperedge of
Hn−1 . There is a hyperedge B = Un − {vn } in Hn−1 which may not be a hyperedge of Hn . If B is indeed
not a hyperedge of Hn = H, then we replace B by Un , add a bag for each set in ∂(vn ) − {Un }, and connect
those bags to the Un -bag. If B is already a hyperedge of H, then we create a new bag B ′ = B ∪ {vn }, connect
it to B, and connect the remaining bags in ∂(vn ) to B ′ as before. Either way, we have just created a tree
decomposition of H in which every bag is a hyperedge and vice versa.
Proposition 4.10 was shown in [65]; we reproduce a stand-alone proof here for completeness. To prove
Proposition 4.10, we use a different characterization of β-acyclicity:
Proposition C.4 (See [36]). A hypergraph H = (V, E) is β-acyclic if and only if there is no sequence
(F1 , u1 , F2 , u2 , · · · , Fm , um , Fm+1 = F1 )
with the following properties
• m≥3
• u1 , . . . , um are distinct vertices of H
• F1 , . . . , Fm are distinct hyperedges of H
• for every i ∈ [m], ui ∈ Fi ∩ Fi+1 , and ui ∈
/ Fj for every j ∈ [m + 1] − {i, i + 1}.
.

72

Proof of Proposition 4.10. For the forward direction, suppose H is β-acyclic. A nest point of H is a vertex
v ∈ H such that the collection of hyperedges containing v forms a nested sequence of subsets, one contained
in the next. Any β-acyclic hypergraph H has at least two nest points [19]. Let vn be a nest point of
H = Hn . Then, ∂(vn ) is an inclusion chain and Un is the bottom element of ∂(vn ). Consequently, Hn−1 is
precisely H − {vn }, which is β-acyclic. By induction there exists an elimination order v1 , . . . , vn−1 such that
every collection ∂(vk ) forms a chain, k ∈ [n − 1], Thus, the elimination order v1 , . . . , vn satisfies the desired
property.
Conversely, suppose there exists an ordering σ = (v1 , . . . , vn ) of all vertices of H such that every collection
∂ σ (vk ) is a chain. Assume to the contrary that H is not β-acyclic. Then, there is a sequence
(F1 , u1 , F2 , u2 , . . . , Fm , um , Fm+1 = F1 )
satisfying the conditions stated in Proposition C.4. Without loss of generality, suppose um comes last in the
vertex ordering σ, and that um = vk for some k. Then, the poset ∂ σ (vk ) contains the set Fm ∩ {v1 , . . . , vk−1 }
and the set F1 ∩ {v1 , . . . , vk−1 }. Since both u2 and um−1 come before um in the ordering, we have
u2
um−1

∈ (F1 ∩ {v1 , . . . , vk−1 }) \ (Fm ∩ {v1 , . . . , vk−1 })
∈ (Fm ∩ {v1 , . . . , vk−1 }) \ (F1 ∩ {v1 , . . . , vk−1 }) .

Consequently, ∂ σ (vk ) is not a chain.
Proof of Lemma 4.12. For the forward direction, consider a tree decomposition (T, χ) with g-width w and
one of its induced vertex orderings σ = v1 , . . . , vn . By Proposition C.3, every set Ukσ is a subset of some bag
χ(t), t ∈ V (T ). Thus, due to g’s monotonicity, g(Uk ) ≤ g(χ(t)) ≤ w.
Conversely, suppose there is a vertex ordering σ = v1 , . . . , vn for which g(Ukσ ) ≤ w for all k ∈ [n]. Let T
be a tree decomposition induced by this ordering. Then, by Proposition C.2, every bag in T is some set Uk ,
which completes the proof.

D

Missing details from the analysis of InsideOut

Proof of Theorem 5.1. Consider an FAQ-SS query ϕ with free variables X[f ] . As discussed, OutsideIn is
basically LeapFrog Triejoin [89]: (1) it finds – by backtracking search – all
N tuples x[n] for which ψS (xS ) 6= 0
for all S ∈ E. For each found tuple, the algorithm adds the product
S∈E ψS (xS ) to the entry ϕ(x[f ] ).
Hence, the overall runtime is dominated by the backtracking search itself, which can be bounded by O(mn ·
AGM(V) · log N ) (see [69]).
Proof of Proposition 5.9. For the sake of brevity, define w = maxj∈K ρ∗H (Uj ). We use the same analysis
as that in the proof of Theorem 5.5. However, we further bound kψS k by N w and also replace all the
AGMHk (Uk ) terms by N w . Note that every factor ψS is either an input factor (S ∈ E) or an intermediate
factor (S = Uk − {k} for some k).
• If ψS was an input factor then kψS k ≤ N ≤ N w because w ≥ 1. If ψS is an intermediate factor
(S = Uk − {k}), then with exactly the same reasoning as in the proof of Theorem 5.1, kψS k can be
bounded by AGMH (Uk ) which is upperbounded by N w .
• Next, for k ∈ K, we show that the computation time of ψUk −{k} using OutsideIn can be bounded by
O(mnAGMH (Uk ) log N ) instead of O(mnAGMHk (Uk ) log N ).19 Since AGMH (Uk ) ≤ N w , we would be
done. This simple but subtle fact is best explained using the language of database join. For each
k ∈ [n] and S ∈ Ek , define a relation
def

R(ψS ) = {xS | ψS (xS ) 6= 0}.
19 Note that the bound AGM
Hk (Uk ) is computed from the best fractional edge cover of Uk using hyperedges Ek , which –
compared to E – has additional intermediate hyperedges/relations and also lack hyperedges/relations from E which belong to
∂(j) for j > k.

73

The runtime of OutsideIn computing ψUk −{k} is precisely the same runtime when we use a worst-case
optimal join algorithm to compute the natural join
Q=✶

S∈Ek
S∩Uk 6=∅

R(ψS/Uk ).

The runtime bound AGMHk (Uk ) is a bound on the maximum number of possible output tuples of Q.
Now, consider the query
Q′ = ✶ S∈E R(ψS/Uk ).
S∩Uk 6=∅

′

Then, it is easy to see that Q ⊆ Q , and thus the maximum number of output tuples of Q is bounded
by the maximum number of output tuples of Q′ , which is AGMH (Uk ).

E

Quick applications of InsideOut

We describe here some examples where expression (14) is “easy” to minimize. Note that to avoid cumbersome
notation, up to re-indexing of variables, we have stated (14) with the assumption that the variable ordering
of the input expression is from X1 to Xn . In the examples below, the variable indices might be arranged
differently from the natural 1 to n order.
Example E.1 (Matrix Chain Multiplication). Consider the matrix multiplication problem and its reduction
to FAQ-SS described in Example 1.1. In this problem, the set of free variables is F = {1, n + 1}. Let
v2 , . . . , vn be an arbitrary permutation of {2, . . . , n}, and let v1 = 1, vn+1 = n + 1. Then, the problem can
be re-stated as computing the function
ϕ(x1 , xn+1 ) =

XX
x v2 x v3

···

n
XY

ψvi ,vi+1 (xvi , xvi+1 ).

xvn i=1

And, expression (14) becomes
log N · O

n
X

!

|Uk | · |{S ∈ E : S ∩ Uk 6= ∅}| · AGMHk (Uk ) + np1 pn+1 .

k=2

(38)

Let us see how one can find a variable ordering v2 , . . . , vn to minimize this expression.
Let ℓ = vn ∈ {2, . . . , n}. Then, for this variable ordering Un = {ℓ − 1, ℓ, ℓ + 1}. In fact, it is easy to see
that every set Uk will have size 3 during the elimination process; and the number of hyperedges intersecting
Uk is at most 4. To fractionally cover Un , we can bound
|ψℓ,ℓ+1 | ≤ pℓ pℓ+1
|ψℓ−2,ℓ−1/Un | ≤ pℓ−1 .
Hence, we can bound the term |Un | · |{S ∈ E : S ∩ Un 6= ∅}| · AGMHn (Un ) in (38) to be 12 · pℓ−1 · pℓ · pℓ+1 . This
is exactly the usual rough estimate of the cost of multiplying a pℓ−1 × pℓ -matrix with a pℓ × pℓ+1 -matrix.
Inductively, finding the best variable ordering to minimize (38) is exactly the same as finding the best
sequence of matrix multiplications to minimize the overall multiplication cost as set up in the textbook
Matrix Chain Multiplication problem [28]. This problem can be solved by dynamic programming!
Example E.2 (Matrix Vector Multiplication for structured matrices). We begin with the DFT matrix.
Recall that we assume that n = pm for some constant prime p. Using the bound in (38), one can show that
InsideOut runs in time O(m4 pm ) = O(n log4 n), which is a log3 n factor off from the O(n log n) runtime of
FFT. Next, we will show that our framework as a special case contains the message passing interpretation
74

of the FFT algorithm of Aji and McEliece [7, 8]. In particular, we will need to do some pre-processing on
the input factors before running InsideOut. For every 0 ≤ k < m, define
Y
ψ·,Yk (x0 , . . . , xm−k−1 , yk ) =
ψXj ,Yk (xj , yk ).
0≤j+k<m

Noting that the entire truth table representation of ψ·,Yk can be computed in time O(mpm−k ) and hence
one can compute all the truth table of ψ·,Yk for k ∈ [m] in time O(mpm ) = O(n log n). Note that if we have
these factors pre-computed, then we want to compute the following FAQ-SS instance
X

ψY (y0 , . . . , Ym−1 ) ·

(y0 ,...,ym−1 )∈Zm
p

m−1
Y

ψ·,Yk (x0 , . . . , xm−k−1 , yk ).

k=0

Now consider the variable ordering Ym−1 , . . . , Y0 and note that Uk when eliminating Yk (note we changed
the notation from the default one), is given by Uk = {X0 , . . . , Xm−k , Y0 , . . . , Yk }. We further note that since
D = {0, 1} we do not need to use the indicator projections in InsideOut. In particular, this implies that
line 7 in Algorithm 1 is computing
X
ψ·,Yk · ψUk+1 ,
Yk ∈Zp

m

which can be done in O(p ) time. Since the above line is executed m times, the overall run time is
O(mpm ) = O(n log n), as desired.
For the circulant matrix, we note that if one picks the variable ordering
Wm−1 , . . . , W0 , Zm−1 , . . . , Z0 , Ym−1 , . . . , Y0
then Algorithm 1 with this variable ordering corresponds to computing C · b as computing F · b first, then
computing F · c next, then computing their component-wise product u = (F · c) · (F · b) and then finally
computing F−1 · u. Note that each of the DFT computations we just saw is done in O(n log n) leading to
an overall runtime of O(n log n) to compute C · b.
Next, we consider the case when A is the Kronecker product D ⊗ E. In this case for HD⊗E consider the
variable ordering Y1 , Y0 and the corresponding U1 = {X1 , Y0 , Y1 } and U0 = {X0 , X1 , Y0 }. To fractionally
(0)
(0)
(1)
(1)
cover U1 , set λ(X1 ,Y1 ) = λX0 ,Y0 = 1. Similarly to cover U0 , set λX0 ,Y0 = λX1 ,Y1 = 1. Finally to cover
F = {X0 , X1 }, set µX1 ,Y1 = µX0 ,Y0 = 1. Then (38) gives an overall runtime bound of O(n30 ) = O(n3/2 ).
We defer the discussion on the Khatri-Rao product case and now consider the case of A = D ◦ E.
Now consider the run of Algorithm 1 with variable ordering Y0 , Y2 , Y1 , Y3 . The corresponding sets are U0 =
{X0 , X2 , Y0 , Y1 , Y2 , Y3 }, U2 = {X0 , X2 , Y1 , Y2 , Y3 }, U1 = {X0 , X1 , X2 , X3 , Y1 , Y3 } and U3 = {X0 , X1 , X2 , X3 , Y3 }.
(0)
We note that it is enough to cover U0 and U1 since U2 ⊆ U0 and U3 ⊂ U1 . To cover U0 , set λX0 ,X2 ,Y0 ,Y2 =
(1)

(0)

(1)

λX1 ,X3 ,Y1 ,Y3 = 1 and to cover U1 set λX0 ,X2 ,Y0 ,Y2 = λX1 ,X3 ,Y1 ,Y3 = 1. Finally, to cover F = {X0 , X1 , X2 , X3 },
set µX0 ,X2 ,Y0 ,Y2 = µX1 ,X3 ,Y1 ,Y3 = 1. Then (38) givens an overall runtime bound of O(n60 ) = O(n3/2 ).
Finally, we consider the case when A is the Khatri-Rao product A = D ⋆ E. Now consider the run of
Algorithm 1 with variable ordering Y0 , Y1 , Y2 . The corresponding sets are U0 = {X0 , X2 , Y0 , Y1 , Y2 }, U1 =
{X0 , X1 , X2 , Y1 , Y2 } and U2 = {X0 , X1 , X2 , Y2 }. Since U2 ⊂ U1 , we only need to cover U0 and U1 . However, if
we just try and use an edge cover and then (38), then we will get the trivial quadratic runtime. However, like
in the case of the DFT, we can consider the InsideOut algorithm and argue an overall runtime of O(n5/3 ).
Since all the factors are represented using the truth table representation, Algorithm 1 would run in the
same time even if we added in the projection of the factor ψX0 ,Y0 ,X2 ,Y2 onto {X0 , Y0 } and the projection of
(0)
(0)
ψX1 ,Y1 ,X2 ,Y2 on to {X1 , Y1 }. With these extra factors, we can cover U0 with λX0 ,X2 ,Y0 ,Y2 = λX1 ,Y1 = 1, U1
(1)

with λX1 ,X2 ,Y1 ,Y2 = λX0 ,Y0 = 1 and F = {X0 , X1 , X2 } by µX0 ,Y0 = µX1 ,X2 ,Y1 ,Y2 = 1. Then (38) implies an
overall runtime of O(n50 ) = O(n5/3 ), as desired.

75

F

More on characterizing EVO(ϕ) and approximating faqw(ϕ)

F.1

Quick applications of FAQ-SS without free variables (i.e. SumProd)

FAQ-SS without free variables is the easiest special case of FAQ because all variable orderings are ϕ-equivalent.
In this case, every variable aggregate is a semiring aggregate.
Hence, K = [n]. Expression (15) becomes a

simple quantity log N · O mn2 N faqw(σ) + f (f + m)kϕk , where
faqw(σ) = max ρ∗H (Uk ).
k∈[n]

In this case, faqw(σ) is exactly the induced fractional edge cover width of σ (Definition 4.11). Thanks to
Lemma 4.12, it follows that
faqw(ϕ) = fhtw(H).
However, computing (a tree decomposition with) the optimal fhtw is NP-hard [37]. From the approximation algorithm of Marx [60] we obtain the following corollaries, which are essentially what was shown in
Grohe and Marx [60] applied to a wider context.
Corollary F.1 (Grohe-Marx [47, 60]). FAQ-SS without free variables on any semiring can be solved in time
Õ(N O(fhtw

3

(H))

+ kϕk),

where kϕk is the time needed to report the output (and under the assumption that fhtw(H) ≤ c for some
constant c 20 ).
In most of our applications, kϕk = Õ(1); however, as we have seen earlier in Example A.17 and shall visit
again below for the natural join problem, kϕk can be a lot larger than N fhtw(H) . We first describe several
applications where kϕk = Õ(1).
3

Corollary F.2 (Theorem 1 from [79]). Quantifier-free #CQ is solvable in time Õ(N O(fhtw (H)) ) (under the
assumption that fhtw(H) ≤ c for some constant c). In particular, #CQ is tractable for the class of conjunctive
queries with bounded fractional hypertree width.
The following result in the probabilistic graphical model context might have been known; but we could
not find a paper or textbook that proves it. (Note that N fhtw(H) ≤ Dtw(H)+1 if each input domain is of size
D. And, N fhtw(H) can be arbitrarily smaller than Dtw(H)+1 for sparse inputs.)
Corollary F.3 (Partition function in PGM). The partition function in probabilistic graphical models can be
3
computed in time Õ(N O(fhtw (H) ) (under the assumption that fhtw(H) ≤ c for some constant c).
For the natural join problem, there is the issue of output reporting. We next work out what InsideOut
does to the set semiring formulation of the natural join problem (Example A.17), and briefly analyze the time
it takes to report the output under this semiring. We prove here the Õ(N fhtw + kϕk)-runtime of InsideOut
for computing joins as shown in Table 1.
Example F.4 (InsideOut for joins under the set semiring). To detail how InsideOut works with the (2U , ∪, ∩)
semiring, we describe its behavior using the familiar relational algebra notations [1]. For this problem, the
input factors ψS are the input relations RS ; the intermediate factors are materialized intermediate relations;
the indicator projections are precisely the relational algebra projections. Following (7), the first intermediate
factor we want to compute is


πUn (RS )
RUn = ✶S∈∂(n) RS ✶ ✶S ∈∂(n),S∩U
/
n 6=∅
Then, we would like to “marginalize out” Xn under the ∪ operator of the set semiring. But we certainly
do not want to perform set-union brute-forcely because each tuple tUn is mapped to Dn−|Un | points in the
20 This

assumption is inherited from Marx approximation algorithm [60].

76

output space U. Luckily, all we have to do is to store RUn using a B-tree or trie data structure in an attribute
order such that Xn comes last. This way, if we only traverse the trie on the first |Un | − 1 attributes, we
will have access to exactly the tuples in RUn −{Xn } . Furthermore, if later we want to also visit the tuples in
RUn we can get down one more level in the trie. Thus, a trie-like index that respects the variable ordering
implicitly computes the marginalization operation for us!
The next issue is how much time it takes to report the output. Since our representation of the output set
is implicit, the set RU1 is an implicit representation of the output. Up until the point of computing RU1 we
have only spent Õ(N faqw(σ) ) time, but the total number of output tuples might be a lot larger than that.21
In order to actually report all output tuples, we will go through each x1 ∈ RU1 , then each x2 such that
(x1 , x2 ) aligns with RU2 , and so forth, until RUn . This is a series of semi-join reductions in disguise; and
it roughly corresponds to the second and the third phases of Yannakakis algorithm [90] performed at once.
The total amount of time to report all output tuples is O(nkϕk log N ), where kϕk is the number of output
tuples.
Corollary F.5 (Relational join). Given an optimal variable ordering, the InsideOut algorithm can solve the
natural join query in time
Õ(N fhtw(H) + kϕk)
where kϕk is the output size. Moreover, if an optimal ordering is not given and assuming that fhtw(H) ≤ c
for some constant c, the runtime becomes
Õ(N O(fhtw

3

(H))

+ kϕk).

The above discussion assumes that we are presenting the output in the listing representations. There are
other options which Section 8.4 discusses.

F.2

Variable ordering for FAQ with two blocks of semiring aggregates

This section highlights some of the subtle problems that arise when there are more than one variable aggregate. In particular, we consider the following instance of the FAQ problem where there are no free variables,
L L̄
N
ϕ = xL x[n]−L S∈E ψS (xS ).
(39)

The input FAQ query has two blocks of variable aggregates. In the first block, L̄
for variables Xi where i ∈ L,
L
is a semiring aggregate; and the second block, for variables Xi , i ∈
/ L, has
as a functionally different
A.18
showed
that
#CQ
can
be
reduced
to
an
FAQ-instance
of this form, where
semiring
aggregate.
Example
L P
L̄
L
L̄
=
and
= max. Note that
and
being functionally different means they are not commutative,
as we showed in Proposition 6.6.
F.2.1

The precedence poset

Define a poset called the precedence poset P = ([n], ) over the variables as follows. Let u ≺ v for every pair
(u, v) in the same connected component of H such that u ∈ L and v ∈
/ L. Let LinEx(P ) denote the set of
linear extensions of the precedence poset P . We first show that LinEx(P ) is “sound”.
L
L̄
Proposition F.6 (LinEx(P ) ⊆ EVO(ϕ)). Suppose
and
are not identical in the domain D. Given a
query ϕ with only two blocks of variable aggregates as written in (39), we have LinEx(P ) ⊆ EVO(ϕ).
the star join query φ = ✶n−1
i=1 Ri (X, Yi ). Since φ is acyclic, fhtw(φ) = 1 but it is easy to come up with instances
of the relations/factors such that the output size is as large as N n−1 (consider e.g. the case when each Ri = {1} × [N ]).
21 Consider

77

Proof. Suppose H has only one connected component. Then, every linear extension of the poset P has
variables in L listed before variables in [n] − L; the soundness of LinEx(P ) thus follows. If H has multiple
connected components, then expression (39) factorizes into a product over those connected components,
where each factor in this product is an FAQ-expression over the variables in that connected component. So
we are back to the case when there is only one connected component. This proves that LinEx(P ) is sound.
In Section 6.1, we prove a more general result stating that every ϕ-equivalent variable ordering σ has the
same faqw as some π ∈ LinEx(ϕ). In that sense, LinEx(P ) is also “complete” and we only need to look in
LinEx(P ) to find a σ minimizing faqw(σ). In particular, we will show that
faqw(ϕ) =

min

σ∈LinEx(P )

faqw(σ).

(40)

We next explain why the precedence poset and its linear extensions help find a good variable ordering.
In

this case, since there is no free variable, expression (15) becomes simply O log N · mn2 N faqw(σ) . However,
it is no longer clear how faqw(ϕ) is related to fhtw(H). Here are some simple properties that we can observe
straightaway:
• faqw(ϕ) ≥ fhtw(H), for any L ⊆ [n].
• If L = [n] or L = ∅, then faqw(ϕ) = fhtw(H).
• When ∅ ⊂ L ⊂ [n], the FAQ-width faqw(ϕ) can be arbitrarily far from fhtw(H). For example, consider
the star graph V = {1, . . . , n} with edges (1, n), (2, n), · · · , (n − 1, n). In this case, fhtw(H) = 1 because
the graph is acyclic. Now, let L = [n − 1], then every ϕ-equivalent variable ordering has n as the last
vertex, which means faqw(σ) = n − 1 for every ϕ-equivalent variable ordering.
F.2.2

Relation to L-star size

Before proving our main result for this section, we analyze how the FAQ-width faqw(ϕ) is related to the
notion of width that was defined in Durant and Mengel [34] for dealing with the #CQ problem. Durant and
Mengel [34] introduced the notion of L-star size of a hypergraph to characterize the complexity of counting
solutions to conjunctive queries.
Let F be any set of hyperedges and B be any set of vertices. Then, the independence
number αF (B) is
S
the maximum size of a set I ⊆ B satisfying the following conditions: (1) I ⊆ S∈F S, (2) no two vertices
from I belong to the same hyperedge in F .
Definition F.7 (L-star size). Let H = (V, E) be a hypergraph, and L be a subset of vertices. For any
connected component C of H − L with vertex set V(C) and edge set E(C), define
Ē(C)
U (C)

= {S ∈ E | S ∩ V(C) 6= ∅}


[
= L∩
S .

(41)
(42)

S∈Ē(C)

Then, the L-star size of H, denoted by L-ss(H), is the maximum independence number αĒ(C) (U (C)) over
all connected components C of H − L, i.e.

L-ss(H) = max αĒ(C) (U (C)) | C is a connected component of H − L
Note that in the above definition Ē(C) is not necessarily the same as E(C). The edges in E(C) do not
contain any member of L, in particular. And, the edges of Ē(C) are the original edges of H. To relate L-ss
to faqw, we need a simple technical lemma.

78

Lemma F.8. Let (T, χ) be a tree decomposition of a hypergraph H = (V, E), where the fractional hypertree
width of (T, χ) is w. Let L ⊆ V be an arbitrary set of vertices of H. Then, there exists a tree decomposition
(T ′ , χ′ ) of H with the same fractional hypertree width satisfying the following condition. Let V(C1 ) and
V(C2 ) be the vertex sets of two different connected components of H − L. Then, there is no bag in (T ′ , χ′ )
intersecting both V(C1 ) and V(C2 ).
Proof. We modify (T, χ) gradually to satisfy the required condition without increasing ρ∗H (B) for any bag B
of the tree decomposition. Fix an arbitrary root r of (T, χ). While there still are two connected components
C1 and C2 for which the desired condition is violated, we do the following.
Let B be the bag farthest from the root r such that B intersects both V(C1 ) and V(C2 ). In particular,
every child of B intersects at most one of the two sets V(C1 ) and V(C2 ). Now, we split B into two bags
B1 = B \ V(C2 ), and B2 = B \ V(C1 ). Remove B and connect both B1 and B2 to the parent of B. (If B is
already the root, then we connect B1 and B2 with an edge.) Children of B which intersect V(Ci ) are connected
to Bi , for i ∈ {1, 2}. Children which do not intersect neither V(Ci ) are connected arbitrarily to B1 or B2 . It
is straightforward to verify that we still have a tree decomposition for H and that ρ∗H (Bi ) ≤ ρ∗H (B).
Theorem F.9. Let ϕ be the FAQ-query defined in (39). For any hypergraph H = (V, E) and any subset L
of vertices of H, we have
(i) faqw(ϕ) ≤ (1 + L-ss(H)) · fhtw(H).
(ii) Furthermore, there is a class of hypergraphs H and sets L for which faqw(ϕ) is bounded but L-ss(H) is
unbounded.
Proof. To prove (i), we show that there exists a ϕ-equivalent vertex ordering σ such that faqw(σ) ≤ (1 +
L-ss(H)) · fhtw(H). We do so by constructing a tree decomposition (T, χ) of H for which the fractional
hypertree width of (T, χ) is at most (1 + L-ss(H)) · fhtw(H), and for which there exists a GYO-elimination
order where vertices in L are eliminated last.
The tree decomposition (T, χ) is constructed as follows. Let (TL , χL ) be a tree decomposition of H with
fractional hypertree width equal to fhtw(H). From Lemma F.8 we can assume that every bag of (TL , χL )
intersects at most one set V(C) for each connected component C of H − L. A bag that intersects V(C) is
called a C-bag. Then, adapting an argument in [34], for every C-bag χL (t) (t ∈ TL ), we amend χL (t) with
χL (t) = (χL (t) ∪ U (C)) \ V(C),
where U (C) is defined as in Definition F.7. After this step is done, (TL , χL ) is a tree decomposition of the
restriction of H on L. This is because the collection of all C-bags form a connected subtree of (TL , χL )
before the amendments.
Next, for each connected component C of H − L, we construct a tree decomposition (TC , χC ) with
fractional hypertree width at most fhtw(H). (This is possible because the fhtw of a subgraph is at most the
fhtw of the supergraph.) Then, for each bag χC (t) of (TC , χC ) we set
χC (t) = χC (t) ∪ U (C).
Finally, we construct the tree decomposition (T, χ) by connecting the tree decompositions (TC , χC ) to the
tree decomposition (TL , χL ). This is done by connecting an arbitrary bag of (TC , χC ) to a bag of (TL , χL )
that used to be a C-bag.
We claim the following:
Claim 1. (T, χ) is indeed a tree decomposition of H.
Claim 2. (T, χ) has fractional hypertree width at most fhtw(H) · (1 + L-ss(H)).
Assuming the claims hold, let us complete the proof of part (i) of the theorem. We construct the Lprefixed variable ordering by showing that we can eliminate vertices from V − L before any vertex in L using
the GYO-elimination procedure. Fix a connected component C of H − L; then vertices in V(C) all reside in
79

the subtree (TC , χC ). We now run the GYO-elimination procedure on this subtree up to its root r, which
was the node that was connected to the center tree (TL , χL ). In this process, all vertices in U (C) are not
eliminated since the neighbor of r contains U (C). We inductively eliminated other V(C ′ ) for other connected
components C ′ of H − L. Part (i) of the theorem is thus proved.
We next prove Claim 1. Every hyperedge S ∈ E is either completely contained in L, or S ∩ V(C) 6= ∅
for some C. If S ⊆ L, then S is a subset of some bag in (TL , χL ), which means it is contained in some
bag of the final tree decomposition (T, χ). If S ∩ V(C) 6= ∅, then S ∩ V(C) is contained in some bag of the
original tree decomposition (TC , χC ). And so S is contained in some bag of (TC , χC ) after we amend each
of those bags with the set U (C). To verify the running intersection property (RIP), fix a vertex v ∈ V. If
v ∈ V(C) for some connected component C of H − L, then RIP holds for v even after the amendments of
bags in (TC , χC ). If v ∈ L then its RIP property holds also because (TL , χL ) is a tree decomposition too.
Finally, we prove Claim 2. The crucial point to notice is that each bag is amended at most once with
U (C) for some C. This is because a C-bag is not a C ′ -bag for two different connected components C and
C ′ , thanks to Lemma F.8. From Lemma 19 of Durand and Mengel [35], each set U (C) can be covered by at
most L-ss(H) many C-bags. In particular, for each amended bag χC (t) = χC (t) ∪ U (C) we have
ρ∗H (χC (t))

≤ fhtw(H) + ρ∗H (U (C))
≤ fhtw(H) + L-ss(H) · fhtw(H)
= (1 + L-ss(H)) · fhtw(H).

Similarly, each amended bag χL (t) is also fractionally covered by at most the same quantity, which completes
the proof of the claim.
To prove part (ii) of the theorem, consider the hypergraph H = (V, E) where
V
E
L

= [n + 1]

=
[n], {1, n + 1}, {2, n + 1}, · · · , {n, n + 1}
= [n].

For this graph, faqw(ϕ) = 1 + (n − 1)/n = 2 − 1/n < 2, and L-ss(H) = n.
F.2.3

Approximating faqw(ϕ)

We now prove a lowerbound on faqw(ϕ) that leads to an approximation algorithm for computing faqw(ϕ)
using an approximation algorithm for fhtw(H) as a blackbox. Recall that we are still considering the FAQquery ϕ of the special form (39). Some of the ideas developed in this section will lead to the approximation
algorithm for faqw(ϕ) for the general FAQ-query case.
Let H = (V, E) be a hypergraph and L ⊆ V be a subset of vertices. For each connected component C of
H − L, let the sets Ē(C) and U (C) be as in Definition F.7. Define the hypergraph HL = (L, EL ) where
EL = {S | S ∈ E ∧ S ⊆ L} ∪ {U (C) | C is a connected component of H − L} .
Lemma F.10. For any connected component C of H − L we have
faqw(ϕ)
faqw(ϕ)

≥
≥

fhtw(C)
ρ∗H (U (C)).

(Note that C itself is a hypergraph.) Furthermore,
faqw(ϕ) ≥ fhtw(HL ).
Proof. For any connected component C of H − L, it is easy to see that
faqw(ϕ) ≥ fhtw(H) ≥ fhtw(C).
80

(43)

Let σ = (v1 , . . . , vn ) be an L-prefixed variable ordering of H with faqw(σ) = faqw(ϕ). (Such a variable
ordering exists due to (40).) For a connected component C of H − L, let k be the smallest integer such that
k > |L| and vk ∈ V(C). Then, the set Uk is precisely U (C) ∪ {vk }. (This is the reason why we chose the
notation U (C).) To see this, note that each time we eliminate a vertex from C, we insert back a hyperedge
interconnecting all its neighbors to the next hypergraph in the hypergraph sequence. And so by the time we
reach Uk all of the neighbors of C in L are connected, which is the set U (C). It follows that
faqw(ϕ) = faqw(σ) ≥ ρ∗H (Uk ) ≥ ρ∗H (U (C)).
It remains to prove faqw(ϕ) ≥ fhtw(HL ). From the above argument, for every connected component C
σ
of H − L, the set U (C) is a hyperedge of H|L|
, which is precisely the graph HL defined above. We thus have
faqw(ϕ)

=
≥
≥
=

min

σ∈LinEx(P )

(max {ρ∗H (Ukσ ) | 1 ≤ k ≤ n})

(max {ρ∗H (Ukσ ) | 1 ≤ k ≤ |L|})


min max ρ∗HL (Ukτ ) | 1 ≤ k ≤ |L|
min

σ∈LinEx(P )
τ

fhtw(HL ),

where τ is a variable ordering of the variables in L (as opposed to σ which was a variable ordering of [n]).
Theorem F.11. Let ϕ be any FAQ query of the form of (39) whose hypergraph is H. Suppose there is an
approximation algorithm that, given any hypergraph H′ , outputs a tree decomposition of H′ with fractional
hypertree width at most g(fhtw(H′ )) in time t(|H′ |, fhtw(H′ )) for some non-decreasing functions g, t. Then,
we can in time |H| · t(|H|, faqw(ϕ)) compute a ϕ-equivalent vertex ordering σ such that
faqw(σ) ≤ faqw(ϕ) + g(faqw(ϕ)).
Proof. We use the blackbox approximation algorithm to construct a tree decomposition (TC , χC ) for every
connected component C of H − L and also construct a tree decomposition (TL , χL ) for HL = (L, EL ).
(Recall that EL was defined in (43).) Then, we form a tree decomposition (T, χ) by connecting these tree
decompositions together in the following way. We add the set U (C) to each bag of of the tree decomposition
(TC , χC ), and arbitrarily connect any node of the tree (TC , χC ) to a bag B of the tree (TL , χL ) for which
U (C) ⊆ B.
From Lemma F.10 and the fact that g is non-decreasing, to cover any bag of the sub-tree (TL , χL ) we
need a fractional cover number of at most
g(fhtw(HL )) ≤ g(faqw(ϕ)).
To cover any bag of the sub-tree (TC , χC ) (after U (C) is added), we need a fractional cover number of at
most
ρ∗H (U (C)) + g(fhtw(C)) ≤ faqw(ϕ) + g(faqw(ϕ)).
Finally, we obtain σ by running the GYO-elimination procedure on the combined tree decomposition (T, χ),
making sure that variables in L are eliminated last.
By applying the above theorem using the fractional hypertree width approximation algorithm from
Marx [60], we obtain the following corollaries.
Corollary F.12. Let ϕ be any FAQ query of the form of (39). Suppose faqw(ϕ) ≤ c for some constant c 22 .
Then, in polynomial time we can compute a ϕ-equivalent vertex ordering σ such that faqw(σ) = O(faqw(ϕ)3 ).
In particular, we can solve the FAQ problem of the form (39) in time


O faqw3 (ϕ)
.
Õ N
22 This

assumption is inherited from Marx approximation algorithm [60].

81

Corollary F.13. Assuming faqw(ϕ) ≤ c for some constant c, the #CQ problem is solvable in time


O faqw3 (ϕ)
.
Õ N
In particular, #CQ is tractable for the class of conjunctive queries for which faqw(ϕ) is bounded.
Note that due to Theorem F.9, the above corollary implies the result by Durant and Mengel [34] that
#CQ is solvable in time Õ(N poly(L-ss(H),fhtw(H)) ). Furthermore, since as we have observed there are classes
of graphs for which faqw(ϕ) ≪ L-ss(H), our result is strictly stronger.

G
G.1

Factor representations
More on the factor oracle

We argue that the listing representation (Definition 4.1) satisfies both Conditional query assumption and
Product-marginalization assumption as long as we choose an appropriate data structure to support listing.
Furthermore, answering these queries from the data structure takes only at most Õ(1) time. We will assume
that the representation can depend on a given ordering σ among the variables (we will see shortly why this
latter requirement is needed).
Assume the non-0 elements of a factor ψS are stored in a B-Tree data structure that respects σ. In
particular, we will store the tuples z such that ψS (z) 6= 0 as follows. Except for the root node, all the
nodes in one level correspond to the same variable, and the ordering of the variables (when sorted from the
level closest to the root to the farthest) is consistent with σ. In other words, the children of the root node
correspond to all x1 such that ψS (· | x1 ) 6≡ 0 and are labeled with the corresponding value of x1 . (Here we
assume that 1 comes first in σ.) Further, these children are sorted in (say) increasing order of the x1 values.
Then for each child of such an x1 we build the tree recursively for ψS (· | x1 ). Finally, the leaves (which
correspond to a vector z formed by concatenating the labels on the unique path from the leaf to the root)
also store ψS (z): we will call this the value of the leaf. Note that it has to be the case that ψS (z) 6= 0.
We now argue why this listing representation satisfies the Conditional query assumption. Assume WLOG
that σ = (1, 2, . . . , n). Then given x[k] , we go down the path in the B-Tree labeled with x[k] . Say u is the
last node on this path. Then computing xk+1 basically corresponds to figuring out where y lies in the sorted
list of values of all children of u. Thus, with a binary search we can return the desired result. Note that if
the query did not respect the ordering σ, then this would not have been possible.
We now argue why the listing representation satisfies the Product-marginalization assumption. Assume
that under the ordering σ, i comes last in S. Then one can perform product marginalization given i and
the B-Tree representation of ψS as follows. Go through all leaves of ψS and multiply the values of all leaves
with the same parent, (pretend to) throw away the leaves and store the computed product as the value of
the new leaf just constructed. (We don’t really throw the leaves away because marginalizing just means we
pretend the depth of the trie/B-tree is one less.) Again note that we need the query to respect the ordering
σ.
In all our algorithms, we will have the case that all the queries respect the ordering σ of the B-Trees.
This is because the algorithm is given as an input a variable ordering σ and all its queries respect this
ordering. Then in essentially linear time one can construct the B-Tree representation of all factors with a
simple pre-processing step. (There is one caveat which is the indicator projections of the input factors; but
those can also be pre-processed in the same amount of time.)

G.2

Truth table representation

Q
In the truth-table representation, each input factor ψS is represented using a table of i∈S |Dom(Xi )| many
rows. Each row lists the parameters and the value of the function. The value can be implicit as in the set
semiring.
82

One example is the (dense) matrix multiplication problem where each input and output matrix is represented by listing out all of its entries. Another example is text-book description of PGM inference, where
conditional probability tables are often assumed to use the truth-table representation.
The truth-table representation makes problems easier because the input sizes are larger. However, it
should be obvious that this representation is wasteful when the input factors are sparse, in the sense that
they might have many 0-valued entries.
It is easy to see that truth table representation can be converted to the listing format in linear time.

G.3

Succinct Representation

This section considers four specific representations of factors where the goal is to (i) have a more succinct
representation of the factors than the listing representation and (ii) have an effective representation on
which one can run efficient algorithms without having to “unpack” the succinct representation (into the
listing representation). Our main aim will be to explain how these representations are essentially encodings
of each input factor as an output of another FAQ (or FAQ-SS) instance. In particular, we will use our notation
as opposed to those used in existing work.
GDNFs. We start with the generalized disjunctive normal form (GDNF) for CSPs that was first considered
by Chen and Grohe [25]. Recall that in the CSP problem (Example A.4) the corresponding FAQ-SS instance
is to compute
_^
ϕ=
ψS (xS ).
x S∈E

For the case when each of the ψS is presented in the listing representation, we get back the Boolean conjunctive query. In the GDNF format for each S ∈ E, we have
ψS (xS ) =

m
_S

^

(i,j)

ψS

(x{j} ).

i=1 j∈S
(i,j)

is presented in the listing representation.
We note two things: (i) the
For each (i, j) ∈ [mS ] × S, ψS
Q
|Dom(X
GDNF
representation
can
bring
down
the
representation
size
from
j )| (potentially) to O(mS ·
j∈S
P
|Dom(X
)|),
which
can
be
big
savings
and
(ii)
the
effective
FAQ
problem
that
we need to solve is
j
j∈S
ϕ=

_^ m
_S ^

(i,j)

ψS

(x{j} ).

x S∈E i=1 j∈S

Decision Diagram Representation. We now consider the decision diagram representation of Chen and
Grohe [25], which is a generalization of the well-studied ordered binary decision diagrams or OBDDs. Again
we consider the CSP problem:
_^
ϕ=
ψS (xS ).
x S∈E

In the decision diagram representation each ψS is represented as follows. For brevity we consider S =
{1, . . . , s}:
s
_
^
(i)
ψS (yi−1 , xi , yi ),
ψS (x1 , . . . , xs ) =
(y0 ,y1 ,...,ys ) i=1

(i)

where for each S and i, ψS is represented in the listing format. We make three remarks: (i) An equivalent
way to think about the above representation (which is how it is presented in [25] and makes the connection
to OBDDs more apparent) is the following. All the tuples x = (x1 , . . . , xs ) such that ψS (x) = 1 correspond to the sequence of labels on all paths of length s in the following layered graph (with s + 1 layers):

83

(i)

ψS (yi−1 , xi , yi ) = 1 if and only is there is an edge from vertex yi−1 (in layer i − 1) to vertex yi (in layer
i) that is labeled xi ; (ii) It is easy to see that a GDNF representation can be converted into a decision
diagram of essentially the same size and it is shown in [25] that the decision diagram representation can be
exponentially smaller than any equivalent GDNF representation; (iii) Note that the effective FAQ problem
that we need to solve is
|S|
^
_^
_
(i) S
ψS (yi−1
, xS[i] , yiS ),
ϕ=
x S∈E (y S ,y S ,...,y S ) i=1
0
1
|S|

where S[1], S[2], . . . , S[|S|] is some ordering of elements in S.
Factorized Databases. Olteanu and Závodný [73] considered factorized representations for conjunctive
queries (Example A.5). Recall that we consider the following instance of FAQ-SS:
_ ^
ϕ(xF ) =
ψS (xS ).
x[n]−F S∈E

In the factorized representation (called f-representation in [73]), each ψS is represented recursively as follows.
In the general case either
ℓ
_
ψS∪,i (x)
(44)
ψS (x) =
i=1

or

ψS (x) =

k
^

ψS×,i
(xSi ),
i

(45)

i=1

where S1 , . . . , Sk is a partition of S. In the base case we have factors of the form ψ{j} : Dom(Xj ) → {0, 1}.
We make five remarks: (i) An alternate formulation of f -representation is as follows. We can represent
all the x such that ψS (x) = 1 in the following tree format. The leaves of the trees have single value for
some attribute. Each of the internal nodes is either a ‘union’ node (corresponding to (44)) or an ‘Cartesian
product’ node (corresponding to (45)) with the natural semantics attached to these nodes; (ii) It is easy to
check that GDNFs are a special case of f-representations; (iii) A generalization of f-representation considered
in [73], called d-representations is where one takes an f-representation and removes repeated sub-expressions:
alternatively in the tree representation mentioned in (i), one ‘short-circuits’ sub-trees that are repeated
resulting in a DAG; (iv) The main contribution of [73] is to show that if the factors are presented in a
factorized representation, then the output of ϕ can also be represented in the same format (and they prove
tight bounds on the output size): we briefly touch on compressing the output in Section 8.4; (v) One can think
of ϕ with the factors in a factorized representation as a big FAQ instance (where each ψS is represented by an
FAQ instance itself over the Boolean semiring, where this instance is determined by the recursive definition
of ψS above).
Fast Matrix Vector Multiplication. We saw in Example A.13 that for the DFT matrix F we can represent the factor corresponding to the matrix more succinctly. We will now use the FAQ-SS formulation to
describe a generic way to talk about matrices A for which we can get a sub-quadratic matrix vector multiplication algorithm: further, our algorithm is the same. The only thing that changes is the representation
of the A and the elimination order. Next, we provide more details on this claim.
Recall that we are aiming to compute A · b. Assuming n = nm
0 for integers m, n0 ≥ 1, the most general
way to represent an n × n matrix A = (Ai,j ) is via the following factor
ψA (x0 , . . . , xm−1 , y0 , . . . , ym−1 ) = A(x0 ,...,xm−1 ),(y0 ,...,ym−1 ) ,

84

where we think of (x0 , . . . , xm−1 ), (y0 , . . . , ym−1 ) as integers in the range [0, n − 1]. Now assume that there
is a hypergraph HA = ({X0 , . . . , Xm−1 , Y0 , . . . , Ym−1 }, EA ) such that
Y
ψA (x0 , . . . , xm−1 , y0 , . . . , ym−1 ) =
ψe ((x, y)e ),
(46)
e∈EA

where we use (x, y)e as a short hand for the projection of {x0 , . . . , xm−1 , y0 , . . . , ym−1 } onto e (i.e. if Xj ∈ e
then we pick xj and if Yj ∈ e then we pick yj ). With this notation in place, recall we are trying to solve the
problem:
Y
X
ψb (y0 , . . . , ym−1 ) ·
φA·b (x0 , . . . , xm−1 ) =
ψe ((x, y)e ).
(47)
e∈EA

(y0 ,...,ym−1 )∈Zm
n0

Next we present some specific instantiations of the FAQ-SS instance from (46).
We begin with DFT and related matrices. In particular, recall the DFT matrix


x·y
F = fx,y = ei2π n
0≤x,y<n

and from Example A.13 that in this case we have the hypergraph HF = (VF , EF ) with
VF
EF

=
=

{X0 , . . . , Xm−1 , Y0 , . . . , Ym−1 },
{(Y0 , . . . , Ym−1 )} ∪ {(Xj , Yk )}0≤j+k<m .

Consider the n × n circulant matrix C where the first column is say the vector (c0 , . . . , cn−1 ) and the
rest of the columns are a cyclic shift of the previous column. It can be shown that C · b for a vector b is the
same as the convolution of c = (c0 , . . . , cn−1 ) and b. In other words,
C · b = F−1 · (F · c) · (F · b).
Note that the above is equivalent to the following FAQ-SS instance:
φC·b (x) =

X X X

m
m
y∈Fm
p z∈Fp w∈Fp

b w · cz ·

Y

ψYj ,Zk (yj , zk )

0≤j+k<m

·

Y

ψYj ,Wk (yj , wk ) ·

0≤j+k<m

Y

ψXj ,Yk (−xj , yk ).

0≤j+k<m

Next, we consider the case when the matrix A is itself a product of two or more matrices. For simplicity,
we will only consider the case when A is a product of two square matrices D and E (of the same order). Both
of these restrictions can be removed but we focus on these special cases since our goal is to show how our
framework gives a uniform way to measure the efficiency of our algorithm for matrix vector multiplication
with structured matrices A.
We begin with the Kronecker product. Given two n0 × n0 matrices D and E, their Kronecker product
A = D ⊗ E is defined as follows: for every (x0 , x1 ), (y0 , y1 ) ∈ Z2n0 , A[(x0 , x1 ), (y0 , y1 )] = E[x0 , y0 ] · F [x1 , y1 ].
In this case, we have the hypergraph HD⊗E = ({X0 , X1 , Y0 , Y1 }, ED⊗E ), where
ED⊗E = {(X1 , Y1 ), (Y0 , Y1 ), (X0 , Y0 )}.
Next, we consider the Khatri-Rao product [55]. We think of E and F as collection of n20 matrices Ex2 ,y2
and Fx2 ,y2 each of which are n0 × n0 matrices. The Khatri-Rao product A = E ⋆ F is defined as follows: for
every (x0 , x1 , x2 ), (y0 , y1 , y2 ) ∈ Z3n0 , A[(x0 , x1 , x2 ), (y0 , y1 , y2 )] = E x2 ,y2 [x0 , y0 ] · F x2 ,y2 [x1 , y1 ]. In this case,
we have the hypergraph HE⋆F = ({X0 , X1 , X2 , Y0 , Y1 , Y2 }, EE⋆F ), where
EE⋆F = {(X0 , X2 , Y0 , Y2 ), (X1 , X2 , Y1 , Y2 ), (Y0 , Y1 , Y2 )}.
85

Finally, we consider the Tracy-Singh product [86]. We think of E and F as collection of n20 matrices Ex2 ,y2
and Fx3 ,y3 each of which are n0 × n0 matrices. The Tracy-Singh product A = E ◦ F is defined as follows: for
every (x0 , x1 , x2 , x3 ), (y0 , y1 , y2 , y3 ) ∈ Z4n0 , A[(x0 , x1 , x2 , x3 ), (y0 , y1 , y2 , y3 )] = E x2 ,y2 [x0 , y0 ] · F x3 ,y3 [x1 , y1 ].
In this case, we have the hypergraph HE◦F = ({X0 , X1 , X2 , X3 , Y0 , Y1 , Y2 , Y2 }, EE◦F ), where
EE◦F = {(X0 , X2 , Y0 , Y2 ), (X1 , X3 , Y1 , Y3 ), (Y0 , Y1 , Y2 , Y3 )}.
We conclude by noting that if one is willing to go beyond semirings and look at fields (in particular,
all the matrices above are over complex numbers), then one can do faster matrix vector multiplication for
a wider family of matrices [71, 76]. Since we are interested primarily in semirings in this paper, we do not
further explore this connection.

G.4

Representations of sparse tables in PGMs

We now summarize the two main succinct representation of factors in PGMS (Example A.12): the first
one corresponds to the listing representation (Definition 4.1) and the second one is similar to the decision
diagram representation (Section G.3).
Sparse tables. This is the listing representation: only list inputs y in representation of ψS such that
ψS (y) 6= 0. This is called evidence shrinking in [52].
Algebraic Decision Diagrams. Algebraic Decision Diagrams (or ADDs) were introduced in Bahar et
al. [12]. This is a succinct representation that is very closely related to the decision diagrams from Section G.3,
as we shall see shortly. (Bahar et al. defined ADDs, considered some of their basic properties, and analyzed
(standard) algorithms for matrix multiplication, shortest path problems and linear algebra when the inputs
for the problems were represented as ADDs.)
We will present the definition of ADD for representing a single factor over bits (larger domain elements can
be represented as bits and the generalization to multiple factors is straightforward). In particular consider
the case when ψ : {0, 1}n → D. An ADD representation for ψ is a DAG G with the sinks (i.e. vertices in G
with no outgoing edges) being labeled with values from D. Further, each non-sink node is labeled with one
of the n variables such that it is consistent with an ordering σ of the n variables. (By consistent we mean
that if (u, v) is a directed edge and they are labeled ℓ(u) and ℓ(v), then σ(ℓ(u)) < σ(ℓ(v)).) Further, every
non-sink node has two outgoing edges: one labeled 0 and the other 1. Given an ADD for a factor ψ one can
compute ψ(x) for an input x = (x1 , . . . , xn ) in the natural way. Start with the root r and take the branch
corresponding to xℓ(r) and continue recursively and stop when you reach a sink s. The value of ψ(x) is the
label of s (recall that the sinks are labeled with elements from D).
The ADD representation is very similar to the decision diagram representation presented in Section G.3.
The main difference is that unlike the decision diagram case where the underlying DAG G is a layered graph,
in an ADD representation G might not be a layered graph. In particular, if we put all vertices in G with
the same label in a layer then there can be edges that connect layers that are not right next to each other.
However, if we are willing to tolerate a blowup of O(n) in the representation size, then we can indeed convert
a G for any ADD representation into a layered graph G′ as follows. For any edge (wi , wj ) between layer
i and j (for j > i + 1),23 we replace the edge with a dummy path (wi , wi+1 ), (wi+1 , wi+2 ), . . . , (wj−1 , wj ),
where wi+1 , . . . , wj−1 are new nodes in G′ . Further, (wi , wi+1 ) has the same label as (wi , wj ) while the rest
of the new edges have a label of both 0 and 1 (more precisely, there are two parallel edges one labeled 0 and
the other labeled 1). Finally, we add an (n + 1)th layer and connect all sinks to distinct vertices in this layer.
(Again if the sink is in layer i for i < n, then we’ll actually need a ‘dummy’ path of appropriate length). Let
L be the function that maps each vertex in the (n + 1)th layer to the corresponding sink label. Given the
ADD in the layered form G′ , one can represent ψ as before (with suitable modifications since ψ is no longer
23 WLOG

we assume that the ordering σ is 1, . . . , n.

86

binary as in Section G.3):
ψ(x1 , . . . , xn ) =

X

y0 ,...,ys+1

n
Y

!

ψ (i) (yi−1 , xi , yi )

i=1

· ψ (n+1) (yn , yn+1 ) · L(yn+1 ),

where ψ (i) encodes the edges between layer (i − 1) and layer i (for i ∈ [n + 1]). In the definition above these
ψ (i) are binary functions and we use the listing representation for each ψ (i) .
If the blowup by a factor of n when going from the original ADD representation to the layered representation is not acceptable, then there are potential ways to mitigate this blowup:
1. If there are s sinks in total, then one can convert G into a layered graph G′′ with an additive blowup
of O(sn + n3 ). To see this note that in the construction of G′ above, each sink leads to a dummy path
of length O(n), which justifies the O(sn) term. Next note that for every edge between layers i and j
(for j > i + 1), the dummy path is the same except for the label on the first edge. In other words, all
these dummy paths can have the same common suffix path of length j − i − 1. Note that there are
O(n3 ) distinct such suffixes, which justifies the O(n3 ) term. This additive factor is advantageous over
the multiplicative blowup of n when G has many more vertices when compared to n and s.
2. Alternatively, we can encode the ADD as an FAQ instance by essentially encoding the Boolean function
suggested by the ADD (modulo the labeling of the sink). More formally, let r be the root of G and let
c0 and c1 be its two outgoing neighbors. Then it is easy to see that
ψG (x1 , . . . , xn ) = ψℓ(r) (xℓ(r) ) · ψGc1 (xℓ(r)+1 , . . . , xn ) + ψ̄ℓ(r) (xℓ(r) ) · ψGc0 (xℓ(r)+1 , . . . , xn ),
where ψℓ(r) (xℓ(r) ) = xℓ(r) and ψ̄ℓ(r) (xℓ(r) ) = 1 − xℓ(r) and ψGc1 , ψGc0 are defined recursively. Finally,
for a sink u, ψGu (x) = L(u). The advantage of this representation is that there is only an O(1) blowup
in the representation size, but now the size of the resulting FAQ instance is the same as the size of
the original as opposed to our earlier representation where the size of the resulting FAQ instance only
depends on n and s (but not on the size of G).
Gogate and Domingos [39] present message passing algorithms that work with both the sparse table and
ADD representation. Unlike this work, which focuses on exact computation of ϕ, the work of [39] presents
algorithms that approximate ϕ.

87

