=Paper=
{{Paper
|id=None
|storemode=property
|title=Tractable Counting of the Answers to Conjunctive Queries
|pdfUrl=https://ceur-ws.org/Vol-749/paper4.pdf
|volume=Vol-749
|dblpUrl=https://dblp.org/rec/conf/amw/PichlerS11
}}
==Tractable Counting of the Answers to Conjunctive Queries==
https://ceur-ws.org/Vol-749/paper4.pdf
Tractable Counting of the Answers to
Conjunctive Queries?
Reinhard Pichler and Sebastian Skritek
Technische Universität Wien, {pichler, skritek}@dbai.tuwien.ac.at
Abstract. Conjunctive queries (CQs) are one of the most fundamen-
tal forms of database queries. In general, the evaluation of CQs is NP-
complete. Consequently, there has been an intensive search for tractable
fragments. In this paper, we want to initiate a systematic search for
tractable fragments of the counting problem of CQs, i.e., the problem
of counting the answers to a CQ. We prove several new tractability and
intractability results by starting with acyclic conjunctive queries and
generalising these results to CQs of bounded hypertree-width.
1 Introduction
Conjunctive queries (CQs) are one of the most fundamental forms of database
queries. They correspond to select-project-join queries in relational algebra and
to select-from-where queries in SQL. As such, they are the primary target of
most current query optimisation techniques. Moreover, CQs are closely related
to Constraint Satisfaction Problems (CSPs) [14], which play an important role
in artificial intelligence and reasoning. By slight abuse of notation, we consider
CQ evaluation as a decision problem. Strictly speaking, there are several (inter-
reducible) decision problems related to CQ evaluation, like query containment
or asking if a given CQ has at least one solution over some database or asking
if a given tuple is part of the answer of the CQ over some database, etc.
Without any restrictions, the evaluation of CQs (and, likewise, solving CSPs)
is NP-complete (query complexity) [3]. Consequently, there has been an intensive
search for tractable fragments. Acyclic conjunctive queries (ACQs) [19] have
thus played an important role. The most common characterisation of ACQs
is in terms of join trees (for details, see Section 2). ACQs can be evaluated
efficiently by performing solely semi-joins in a bottom-up traversal of the join
tree. Meanwhile, many further tractable classes of CQs have been identified. In
particular, many structural decomposition methods have been developed which
are based on some notion of decomposition of the graph or hypergraph structure
underlying a conjunctive query and which are used to define some notion of
width. Hypertree decompositions, which are used to define the hypertree-width of
a CQ, are a very powerful decomposition method (for details, see Section 2) [11].
In particular, CQs can be efficiently evaluated if their hypertree-width is bounded
by some constant. The class of CQs of bounded hypertree-width generalises many
?
This work was supported by the Vienna Science and Technology Fund (WWTF),
project ICT08-032.
other tractable fragments of CQs [9] like CQs of bounded tree-width [17], CQs of
bounded query-width [4], and also ACQs. Indeed, ACQs are precisely the CQs
whose hypertree-width is equal to 1.
In this paper, we concentrate on the counting problem related to CQ eval-
uation, i.e., the problem of counting the number of answers to a CQ. We shall
refer to this problem as the #CQ problem. Of course, the #CQ problem is in-
tractable. Indeed, it is #P-complete for CQs with free variables only (i.e., no
existential quantifiers) and even slightly harder (namely # · NP-complete) in the
general case [1]. Interestingly, the search for tractable fragments of #CQ has
received very little attention so far even though the count operator is an integral
part of the SQL language and is supported by virtually any relational database
management system. Very recently, we have shown by an ad hoc algorithm that
the query complexity of #CQ becomes tractable for CQs of bounded tree-width
[16]. However, a systematic search for tractable fragments of #CQ is completely
missing to date. In this paper, we want to close this gap. Our goal is to arrive at a
situation comparable to the well-studied decision problem of CQ evaluation, i.e.,
(i) we want to establish tractability for ACQs, (ii) the corresponding algorithms
should be based on semi-joins, and (iii) it should be possible to generalise the
tractability results to CQs of bounded hypertree-width.
Organisation of the paper and summary of results. In Section 2, we
recall some basic notions and results. A conclusion is given in Section 6. The
main results of the paper are detailed in Sections 3 – 5, namely:
• ACQs with free variables only. In Section 3, we restrict ourselves to ACQs
with free variables only. We present our basic algorithm for counting the answers
to ACQs of this specific form. Our algorithm only requires semi-joins and simple
arithmetic. We thus establish the tractability of the combined complexity of
#CQ for ACQs without existential quantifiers.
• Arbitrary ACQs. In Section 4, we consider #CQ for arbitrary ACQs. The
tractability of the data complexity is easily shown. For the query complexity,
a significant extension of the basic algorithm from Section 3 is required. In
contrast, for the combined complexity of the #CQ problem for arbitrary ACQs
we establish the intractability by proving its #P-completeness.
• Extensions. All tractability and intractability results discussed above imme-
diately carry over to CQs of bounded hypertree-width. In Section 5, we dis-
cuss further extensions and applications of our results. For instance, the #P-
completeness of the combined complexity of the counting problem of ACQs al-
lows us an easy #P-completeness proof for the counting problem of unions of
ACQs even if these ACQs have no existentially quantified variables at all.
2 Preliminaries
Schemas and instances. A relational schema R = {R1 , . . . , Rn } is a set of
relation symbols Ri each of a fixed arity k and with an assigned sequence of k
attributes (A1 , . . . , Ak ). An instance I over a schema R consists of a relation RiI
for each relation symbol Ri ∈ R, s.t. both have the same arity. We only consider
finite instances here, and denote with dom(I) the active domain of I. We write
2
x for a tuple (x1 , . . . , xn ). By slight abuse of notation, we also refer to the set
{x1 , . . . , xn } as x. Hence, we may use expressions like xi ∈ x or x ⊆ X, etc. For
a tuple s ∈ RiI , we also say Ri (s) ∈ I.
CQs. A conjunctive query (CQ) Q on aVdatabase schema R is of the form
n
Q : ans(x) ← ∃yφ(x, y), where φ(x, y) = i=1 ri is a conjunction of atoms ri =
Rj (z), s.t. Rj ∈ R with arity k, and z ⊆ x ∪ y with |z| = k. We do not consider
constants in the query, because a simple preprocessing step allows us to get rid of
them. For the same reason, w.l.o.g. we assume no variable to occur twice in any
atom [10]. The free variables x are also referred to as distinguished variables,
while the existentially quantified variables y are often called nondistinguished
variables. We denote with atoms(Q) the set {r1 , . . . , rn } of atoms appearing
in Q, and for a set A of atoms, var (A) denotes the set of variables occurring
in A. By slight abuse of notation, for a tuple x = (x1 , . . . , xn ) of variables
and a mapping µ : x → dom(I), we write µ(x) for (µ(x1 ), . . . , µ(xn )). A tuple
s is called an answer or solution to a CQ Q on an instance I if s = µ(x),
where µ : x ∪ y → dom(I) is a variable assignment on x, y, s.t. for every atom
Ri (z) ∈ atoms(Q), Ri (µ(z)) ∈ I. For such a mapping µ, we also write µ(Q) ⊆ I
to emphasise that every atom Ri (z) ∈ atoms(Q) is sent to an atom in I. The
set Q(I) of answers to Q on I is a relation ans Q(I) containing all answers.
In this paper, we study the counting problem #CQ, which is defined as
follows: Given a conjunctive query Q over some relational schema R and an
instance I for R, how many tuples are contained in ans Q(I) ?
ACQs. There exist several notions of acyclic CQs (ACQs). We restrict ourselves
here to the so-called α-acyclicity [7]. One way to characterise ACQs is via join
trees, i.e., a CQ is acyclic, if it has a join tree [7]. A join tree T for a query Q
is a tree T = (V, E), where V is identified with the set of atoms in Q, and E is
such that for every two atoms ri , rj ∈ V having variables in common, all atoms
on the unique path from ri to rj contain all variables shared by ri and rj . Given
a CQ it can be efficiently checked if it is acyclic, and if so, also a join tree can
be computed efficiently [12, 20]. We often identify a tree T with its vertex set
V , and write t ∈ T for T = (V, E), t ∈ V . If we want to stress the difference
between the graph structure and the query atoms, for some t ∈ T for a join tree
T , we write Qt to denote the query atom identified with node t. Further, given
an instance I to evaluate Q on, for every t ∈ T we denote with Rt the relation
RiI assigned to the relation symbol of Qt .
Hypertree decompositions. A hypertree decomposition [11] of a CQ Q is
a triple hT, χ, λi, where T = (V, E) is a tree and χ, λ are mappings χ : V →
P(var (atoms(Q))) and λ : V → P(atoms(Q)) s.t. (1) for each atom ri ∈ atoms(Q),
there exists a v ∈ V s.t. var ({ri }) ⊆ χ(v); (2) for each z ∈ var (atoms(Q)), the
set T 0 = {v ∈ V | z ∈ χ(v)} of T induces a connected subtree of T ; (3) for
each v ∈ V , χ(v) ⊆ var (λ(v)); (4) for each v ∈ V , var (λ(v)) ∩ χ(Tv ) ⊆ χ(v),
where Tv ⊆ T is the complete subtree of T rooted at v. The width of a hypertree
decomposition is maxv∈V |λ(v)|, and the hypertree-width of Q is the minimum
width over all hypertree decompositions of Q. For a given width ω, the exis-
tence of a hypertree decomposition of width ω can be efficiently decided, and a
decomposition can be efficiently computed, if one exists [11].
3
Counting complexity. While decision problems ask if for a given problem in-
stance, at least one solution exists, counting problems ask how many different
solutions exist, see e.g. [15], Chap. 18. The most intensively studied counting
complexity class is #P, which contains those function problems which consist
in counting the number of accepting computation paths of a non-deterministic
polynomial-time Turing machine. In other words, #P captures the counting
problems corresponding to decision problems in NP. However, there exist also
#P-complete problems for which the corresponding decision problem is easy.
Classical examples of this “easy to decide, hard to count” phenomenon are
#PERFECT MATCHINGS and 2-SAT [18]: checking if a bipartite graph has a
perfect matching or if a 2-CNF formula has a model is easy. But counting the
number of perfect matchings or the number of models of a 2-CNF-formula is
hard. Note that by #P-completeness we mean completeness w.r.t. Cook reduc-
tions, i.e., polynomial-time Turing reductions [15].
3 ACQs without Nondistinguished Variables
We first consider CQs of the form ans(x) ← φ(x), i.e. only queries that contain
no existentially quantified variables. Without further restrictions, #CQ is well
known to be #P-complete for CQs of this form [5]. However, just as for the
decision problem, for ACQs, we can make use of the existence of a join tree to
guide the computation. We provide an algorithm, mainly working with semi-
joins along the join tree, that shows that the problem is indeed tractable for
ACQs. Note that we consider counting w.r.t. set semantics here.
Before describing the algorithm, we have to fix some notation. Given an
acyclic CQ Q : ans(x) ← φ(x) over database schema R and instance I, let T be
a join tree of Q. Recall that for t ∈ T , Qt denotes the query atom identified with
t, and Rt the relation RiI assigned to the relational symbol of Qt . Further let
Tt be the complete subtree of T rooted at t, and let Xt = var ({Qt }). For Qt =
Ri (x1 , . . . , xk ), if clear from the context, it is convenient to also write QSt to refer
to (x1 , . . . , xk ) only. For a subtree T 0 of T , XT 0 = t∈T 0 Xt and QT 0 V
S
= t∈T 0 Qt .
Given QT 0 , the subquery defined by QT 0 is the query ans(XT 0 ) ← t∈T 0 Qt . In
the following, we always assume an acyclic CQ Q : ans(x) ← φ(x) with join tree
T to be evaluated over some database instance I.
Obviously, every row in Rt encodes a variable assignment α on Xt , hence
a partial assignment on x. The idea of the algorithm is to compute, for every
t ∈ T , in a bottom-up traversal of the tree the number of possible extensions µ of
α to XTt that are valid solutions to the subquery defined by QTt . Formally, for a
mapping µ : XTt → dom(I) and some t ∈ T , we define the footprint of µ on t as
fpr (µ, t) = α, where α is a variable assignment on Xt s.t. α(xi ) = µ(xi ) for all
xi ∈ Xt . For a subtree T 0 ⊆ T with root t and α : Xt → dom(I), we define the set
N (T 0 , t, α) = {µ : XT 0 → dom(I) | fpr (µ, t) = α and µ(QT 0 ) ⊆ I} of all possible
extensions of the variable assignment α to an assignment µ on the variables XT 0
that are solutions to the subquery QT 0 . The intuition behind this set is that for
every row ρ ∈ Rt (which can be considered as a variable assignment α on Xt ),
N (Tt , t, α) contains all possible extensions of α to XTt that are solutions to QTt .
As we cannot afford to compute this set explicitly (which would be the naive
algorithm), we just compute and store its cardinality, i.e. |N (Tt , t, α)|. Hence,
4
at each node t ∈ T we maintain a table R̂t , having |Xt | + 1 columns. Thereby
the first |Xt | columns (denoted as R̂t,π(Xt ) ) store α, while the last column stores
|N (Tt , t, α)|. To better distinguish between |N (Tt , t, α)|, i.e. the value intended
to be stored in this column, and the actual value present there, we refer to this
column (or value) as cα . Note that we are only interested in such assignments α
s.t. N (Tt , t, α) 6= ∅, because otherwise α can never be extended to an answer to
Q. Hence, for every assignment α s.t. α(Qt ) ∈ / Rt , we need no entry in R̂t , and
therefore R̂t contains exactly one row for every ρ ∈ Rt s.t. |N (Tt , t, αρ )| > 0.
Thereby αρ denotes the variable assignment defined by ρ. If clear from the
context, we drop the ρ from αρ and use α and ρ interchangeably.
It is easy to see that N (Tt , t, α) ∩ N (Tt , t, α0 ) = ∅ for α 6= α0 . Hence, the
number of answers to the ACQ Q can be retrieved from the root node r of
T , by just summing up the counter of all entries in R̂r . Indeed, the union
S
α∈Rr N (Tr , r, α) gives all possible variable assignments µ on XTr = x s.t.
µ(QS Tr ) = µ(Q) ⊆ I. ByP the disjointness of N (Tr , r, α) forPdifferent values of
α, | α∈Rr N (Tr , r, α)| = α∈Rr |N (Tr , r, α)|, and therefore α∈Rr cα gives the
number of different solutions. It remains to show how to compute the values for
each R̂t . The algorithm for this consists of two phases: The initialisation phase,
and a bottom-up traversal of the tree.
Initialisation Phase: For every leaf node t ∈ T , R̂t is computed as follows: For
every distinct tuple ρ ∈ Rt , add a tuple (ρ, 1) to R̂t . Note that for leaf nodes
we have Xt = XTt . Hence, the only extension µ for each α is α itself, and R̂t
therefore contains the correct values.
Bottom-Up Traversal: Let t ∈ T be a node with children t1 , . . . , tk (k ≥ 1),
such that R̂tj has already been computed during the bottom-up traversal for
every j ∈ {1, . . . , k}. The idea is now to compute R̂t by starting from a relation
considering t only and then, step by step, for every j ∈ {1, . . . , k}, to include
the subtree Tj (where we use Tj to abbreviate Ttj ) by computing the semi-
join between the output of the previous step and R̂tj . Formally, let R̂t0 contain
a tuple (ρ, 1) for every distinct tuple ρ ∈ Rt , i.e. R̂t0 is defined analogously
to R̂t0 for a leaf node t0 ∈ T . Then, for every child j ∈ {1, . . . , k}, compute
j j−1
R̂t,π(X t)
= R̂t,π(X t)
n R̂tj ,π(Xtj ) . To compute cjα for every row in R̂tj , we first
j
define for every α ∈ R̂t,π(Xt)
the set Bα ⊆ R̂tj ,π(Xtj ) containing exactly those
β ∈ R̂tj ,π(Xt ) that can be joined with α, i.e. Bα = {β ∈ R̂tj ,π(Xtj ) | β(xi ) =
j
α(xi ) for every xi ∈ Xt ∩ Xtj }. Then cjα for every row α ∈ R̂t,π(Xt)
is set to
j−1
cα = cα · β∈Bα cβ where cα is the value of cα in R̂t . Finally, R̂t = R̂tk .
j j−1 j−1
P
The following example will help to illustrate this algorithm.
Example 1. Consider an ACQ Q : ans(x1 , x2 , x3 , x4 , x5 , x6 ) ← R3 (x3 ) ∧ R4 (x2 ,
x4 , x3 ) ∧ R1 (x1 , x2 , x3 ) ∧ R2 (x2 , x3 ) ∧ R2 (x5 , x6 ) and an instance I = {R1 (s1 , c1 ,
b1 ), R1 (s1 , c1 , b2 ), R1 (s3 , c3 , b1 ), R1 (s3 , c1 , b4 ), R1 (s2 , c2 , b3 ), R2 (c1 , b2 ),
R2 (c1 , b1 ), R2 (c4 , b6 ), R3 (b1 ), R3 (b2 ), R4 (c1 , a1 , b1 ), R4 (c1 , a1 , b2 ), R4 (c1 , a2 , b2 )}
over the schema R = {R1 /3, R2 /2, R3 /1, R4 /3}. A possible join tree for Q is
5
shown in Fig. 1, where each of the nodes t ∈ {t1 , . . . , t5 } is annotated with Qt .
In addition, the pattern of the relations shown at the leaf nodes is “Rt ⇒ R̂t ”. At
the two non-leaf nodes, the pattern is “Rt ⇒ R̂t0 ⇒ R̂t1 ⇒ R̂t ”. The last column
in each table contains the counter. The content of the relations is computed in
a bottom-up manner as described above. The final result |Q(I)| = 9 can be read
off at the root node.
t1 : R2 (x2 , x3 )
A1 A2 x2 x3 c x2 x3 c
x2 x3 c
c1 b2 c1 b2 1 c1 b2 3
⇒ ⇒ ⇒ c1 b2 6
c1 b1 c1 b1 1 c1 b1 3
c1 b1 3
c4 b6 c4 b6 1 c4 b6 3
t2 : R2 (x5 , x6 ) t3 : R1 (x1 , x2 , x3 )
A1 A2 x5 x6 c A1 A2 A3 x1 x2 x3 c
c 1 b2 c 1 b2 1 s1 c1 b1 s1 c1 b1 1 x1 x2 x3 c
⇒ x1 x2 y c
c 1 b1 c 1 b1 1 s1 c1 b2 s1 c1 b2 1 s1 c1 b1 1
⇒ ⇒ ⇒ s1 c1 b1 1
c 4 b6 c 4 b6 1 s3 c3 b1 s3 c3 b1 1 s1 c1 b2 1
s1 c1 b2 2
s3 c1 b4 s3 c1 b4 1 s3 c3 b1 1
s2 c2 b3 s2 c2 b3 1
t4 : R3 (x3 ) t5 : R4 (x2 , x4 , x3 )
A1 x3 c A1 A2 A3 x2 x4 x3 c
b1 ⇒ b1 1 c1 a1 b1 c1 a1 b1 1
⇒
b2 b2 1 c1 a1 b2 c1 a1 b2 1
c1 a2 b2 c1 a2 b2 1
Fig. 1. Annotated join tree for the query Q (Example 1) over I.
Theorem 1. Suppose that we only consider ACQs Q : ans(x) ← φ(x) without
nondistinguished variables. Then for query Q with join tree T over schema R
and instance I, #CQ can be solved in time O(|Q| · (maxt∈T |Rt |)2 ), assuming
unit cost for arithmetic operations.
Proof (sketch). First of all, it must be shown that the algorithm is indeed correct.
This will be done implicitly in Section 4, where we present an algorithm for
counting the number of solutions to an ACQ with nondistinguished variables
and prove its correctness. As the algorithm presented above will turn out to be
a special case of the one in Section 4, for the correctness we refer to the proof
of Theorem 3.
It therefore remains to show the upper bound on the runtime of the algorithm:
First of all, note that at each t ∈ T , R̂t,π(Xt ) ⊆ Rt . Hence, at each node t ∈ T ,
the space required to store R̂t is obviously in O(|Rt |). On the other hand, by
definition, the size of a join tree of Q is linear in the size of Q. Hence the space
required to store R̂t for all t ∈ T is trivially O(|Q| · maxt∈T |Rt |). Therefore, as
even the naive implementation (with nested loops) of the semi-join needs only
quadratic time, by assuming unit cost for the arithmetic operations, the runtime
for the algorithm is in O(|Q| · (maxt∈T |Rt |)2 ). t
u
6
4 ACQs with Nondistinguished Variables
For deciding whether a CQ has some solution, it makes no difference whether it
contains only free variables, or additional nondistinguished ones. As the goal is
just to find one assignment on all variables that maps the query into the instance,
all variables can be treated in the same way. In contrast, for the counting prob-
lem, this is no longer true, as only variable assignments that differ on the free
variables also give different solutions. On the other hand, variable assignments
that only differ on the existentially quantified variables must not be counted
twice. As already noted in the introduction, under reasonable complexity the-
oretical assumptions, in the general case, counting becomes harder for queries
with nondistinguished variables [1]. In this section, we show that a similar be-
haviour can be observed for ACQs: First we will show that the problem remains
tractable for data- and query complexity, and then we show #P-completeness
for the combined complexity.
Given an ACQ Q : ans(x) ← ∃yφ(x, y), the naive approach for counting
the number of solutions over some instance I is to check for each possible vari-
able assignment µ : x → dom(I), whether the (Boolean) ACQ Q0 : ans() ←
∃yφ(µ(x), y) is satisfied over I. As Q0 is acyclic, the check can be done in time
O(|Q| · |I|) [19, 8] which immediately leads to tractable data complexity.
Theorem 2. Suppose that we only consider ACQs Q : ans(x) ← ∃yφ(x, y) with
nondistinguished variables y. Then for query Q over schema R and instance I,
#CQ can be solved in time O(|dom(I)||x| · |Q| · |I|).
When considering query complexity, tractability can be reached by some major
extensions of the algorithm from the previous section. In the following, we will
sketch the necessary changes. Recall that in the last section, given a CQ Q
with join tree T on some schema R with instance I, the idea was, at each
t ∈ T , to define a footprint (small enough to be stored) for every assignment
µ : XTt → dom(I), and to keep track of the number of partial solutions that
have this footprint. Now we have to deal with assignments µ = µx ∪ µy with
µ : XTt ∪YTt → dom(I), where µx and µy are the restrictions of µ to XTt and YTt
resp., and Yt and YTt are defined on the nondistinguished variables analogously to
Xt and XTt . Therefore we have fpr (µx , µy , t) = (αx , αy ) again as the restriction
of µx (resp. µy ) to Xt (resp. Yt ). However, this time the problem is that the
same partial solution µx may, with different µy , have different footprints. Hence,
if we define the sets N (Tt , t, αx , αy ) of partial assignments (on the distinguished
variables x) analogously as before, these sets are not necessarily disjoint. We
therefore have to group footprints by αx , and identify sets of partial solutions
by a combined footprint, which is a set of footprints {(αx , αy1 ), . . . , (αx , αyn )}. For
convenience, we may also write (αx , I) with I = {αy1 , . . . , αyn } to denote the
combined footprint.
For a subtree Tt at node t ∈ T and a combined footprint (αx , I) at node t,
we define N (Tt , t, αx , I) as the set of mappings µx : XTt → dom(I) such that
(1) for every i ∈ {1, . . . , |I|}, there exists a µy : YTt → dom(I) s.t.
(a) fpr (µx , µy , t) = (αx , αyi ), and (b) µ(QTt ) ⊆ I (where µ = µx ∪ µy )
(2) for all µ̄y : YTt → dom(I) s.t. µ(QTt ) ⊆ I (where µ = µx ∪ µ̄y ) holds, there
exists a j ∈ {1, . . . , |I|} s.t. fpr (µx , µ̄y , t) = (αx , αyj )
7
As mentioned above, we cannot afford to store the set N (Tt , t, αx , I) at node
t ∈ T . Hence, we only store (αx , I) together with |N (Tt , t, αx , I)|, since we are
only interested in the number of such assignments. Note that (αx , I) fits into a
table with |Xt | + |Yt | columns (i.e. with schema (Xt , Yt )), containing one row ρi
for every αyi ∈ I, storing αx in the first |Xt | columns, and αyi in the last |Yt |
columns. Hence at every node t ∈ T , we maintain a set R̂Tt = {Ŝ1 , . . . , Ŝn } (for
some n ∈ N; an upper bound on n will be given below) of relations of the above
form. In addition, we maintain for each relation Ŝj ∈ R̂Tt a counter cjt storing
|N (Tt , t, αx , I)|. Actually, it is convenient to write R̂t short for R̂Tt . Only for
the correctness proof (in the full version) it will be advantageous to explicitly
index R̂ by a subtree Tt rather than just by a node t. Intuitively, every relation
Ŝj ∈ R̂t encodes a set of mappings µx : XTt → dom(I), while each row in Ŝj
encodes a different set of mappings µy : YTt → dom(I) for this µx , s.t. for each
µ = µx ∪ µy , µ(QTt ) ⊆ I holds. Note that within each relation, each row has the
same value for Xt , and several relations may contain the same αx .
The content of R̂t (for t ∈ T ) is again computed in two phases. In an initial-
isation phase, first for every leaf node t ∈ T , R̂t contains exactly one relation
for every different value αx for Xt in Rt , containing one row (αx , αy ) for every
value αy for Yt s.t. (αx , αy ) ∈ Rt . The counter for each such relation is set to
one. Then, in a bottom-up traversal of the tree, for every t ∈ T with children
t1 , . . . , tk s.t. R̂ti has already been computed, we again start with some R̂0t that
is defined like R̂t0 for leaf nodes t0 ∈ T , and then include one child after the other
as follows: For i ∈ {1, . . . , k}, let R̂it contain all nonempty results Ŝ1 n Ŝ2 for all
pairs (Ŝ1 ∈ R̂i−1 t , Ŝ2 ∈ R̂ti ). If Ŝ1 n Ŝ2 is nonempty, the value of the counter
for the resulting table is the product of the counters for Ŝ1 and Ŝ2 . Whenever
several such pairs give the same result, only one copy of the relations is stored,
and their counters are summed up. The number of solutions to Q is retrieved by
summing up the counters for all Ŝj ∈ R̂r at the root node r of T .
Example 2. Recall the instance I and query Q from Example 1. We will use the
same instance I, and change Q to Q0 only by removing x3 from the free variables.
(For convenience, we rename it to y.) I.e., Q0 : ans(x1 , x2 , x4 , x5 , x6 ) ← ∃yR3 (y)∧
R4 (x2 , x4 , y) ∧ R1 (x1 , x2 , y) ∧ R2 (x2 , y) ∧ R2 (x5 , x6 ). We use the same join tree as
before. It is shown in Fig. 2, where again each node t ∈ {t1 , . . . , t5 } is annotated
with Qt . Recall that to deal with nondistinguished variables, we have to maintain
sets R̂t of relations. At each node t, R̂t is depicted together with its derivation
sequence: The pattern shown at the leaf nodes is “Rt ⇒ R̂t ”, and for the inner
nodes it is “Rt ⇒ R̂0t ⇒ R̂1t ⇒ R̂t ”. Thereby, the first row in each table shows the
schema, followed by the relations Ŝj ∈ R̂it separated by double horizontal lines.
In the first row for each relation Ŝj , the last column shows the counter for Ŝj .
For instance, at node t3 , we have two relations Ŝ1 = {(s1 , c1 , b1 ), (s1 , c1 , b2 )} and
Ŝ2 = {(s1 , c1 , b2 )} in R̂t . Note that Ŝ1 and Ŝ2 refer to two different extensions
of αx (x1 , x2 ) = (s1 , c1 ) to µx (x1 , x2 , x4 ). Indeed, Ŝ1 corresponds to µx (x4 ) = a1
while Ŝ2 corresponds to µx (x4 ) = a2 . Again, the final result |Q0 (I)| = 6 can be
read off at the root node.
8
t1 : R2 (x2 , y)
A1 A2 x2 y c x2 y c x2 y c
c1 b2 c1 b2 1 c1 b2 3 c1 b1 3
⇒ ⇒ ⇒
c1 b1 c1 b1 c1 b1 c1 b2
c4 b6 c4 b6 1 c4 b6 3 c1 b2 3
t2 : R2 (x5 , x6 ) t3 : R1 (x1 , x2 , y)
x5 x6 c x1 x2 y c
A1 A2 A1 A2 A3
c1 b2 c1 b2 1 s 1 c 1 b1 s1 c1 b1 1 x1 x2 y c x1 x2 y c
⇒ s1 c1 b2
c1 b1 c1 b1 1 s 1 c 1 b2 s1 c1 b1 1 s1 c1 b1 1
⇒ ⇒ ⇒
c4 b6 s 3 c 3 b1 s3 c3 b1 1 s1 c1 b2 s1 c1 b2
c4 b6 1
s 3 c 1 b4 s3 c1 b4 s3 c3 b1 1 s1 c1 b2 1
s 2 c 2 b3
s2 c2 b3 1
t4 : R3 (y) t5 : R4 (x2 , x4 , y)
A1 y c A1 A2 A3 x2 x4 y c
b1 ⇒ b1 1 c1 a1 b1 c1 a1 b1 1
b2 ⇒
b2 c1 a1 b2 c1 a1 b2
c1 a2 b2 c1 a2 b2 1
Fig. 2. Annotated join tree for the query Q0 (Example 2) over I.
Theorem 3. Suppose that we only consider ACQs Q : ans(x) ← ∃yφ(x, y) with
nondistinguished variables y. Then for query Q with join tree T over schema R
and instance I, #CQ can be solved in time O(|Q| · m2 · 4m ) (assuming unit cost
for arithmetic operations), where m = maxt∈T |Rt |.
Proof (sketch). The details of the algorithm and the correctness proof will be
given in the full version. We only discuss the runtime here. Note that at some
node t ∈ T , the values for Xt need not be different between two different relations
Ŝi , Ŝj ∈ R̂t . Hence for every t ∈ T , there might be up to 2m different elements
in R̂t , each of size O(m) (obviously, Ŝi ⊆ Rt for every Ŝi ∈ R̂t ), where m =
maxt∈T |Rt |. Hence there are at most O((2m )2 ) semi-joins between two nodes,
each requiring time at most O(m2 ) even for a naive implementation, which gives
an overall runtime estimation of O(|Q| · m2 · (2m )2 ). t
u
Theorem 2 and Theorem 3 immediately imply that #CQ can be solved ef-
ficiently for data- and query complexity. The natural next question is, whether
there exists also an algorithm that solves the problem efficiently when considering
combined complexity. However, the next theorem shows that such an algorithm
is very unlikely to exist.
Theorem 4. Suppose that we only consider ACQs Q : ans(x) ← ∃yφ(x, y)
with nondistinguished variables y. Then the combined complexity of #CQ is
#P-complete. The problem remains #P-complete, even if Q contains a single
nondistinguished variable only.
Proof (sketch). Membership is easy to show. The hardness is shown by reduction
from the #P-complete problem #PERFECT MATCHINGS [18], i.e. from the
problem of counting the number of perfect matchings in a bipartite graph. A
9
perfect matching for a bipartite graph G = (V, E) is a subset M ⊆ E s.t.
every v ∈ V is contained in exactly one e ∈ M . Let an arbitrary instance of
#PERFECT MATCHINGS be given by a bipartite graph G = (V, E), where
V = A ∪ B with A = {a1 , . . . , an }, B = {b1 , . . . , bn }, and E ⊆ A × B. From this,
we create a database instance I over the Snschema S = {e/2, t/2} as follows:
I = {e(ai , bj ) | for each (ai , bj ) ∈ E} ∪ i=1 {t(i, x) | x ∈ B \ {bi }},
where, by slight abuse of notation, we use ai and bi to denote both, vertices in
V and constants in I. We Vnfurther define two conjunctive queries Q1 , Q2 as
Q1 : ans(x1 , . . . , xn ) ← i=1
Vne(ai , xi ) Vn
Q2 : ans(x1 , . . . , xn ) ← ∃y i=1 e(ai , xi ) ∧ i=1 t(y, xi )
Note that a perfect matching is equivalent to a bijective mapping from A to B
along the edges in E. The idea of the reduction is that Q1 (over I) selects all
possible mappings of nodes from A to nodes from B, while Q2 selects all those
mappings where at least one element from B is not assigned to an element from
A. Hence, Q1 (I)\Q2 (I) gives exactly the set of perfect matchings, and because of
Q2 (I) ⊆ Q1 (I), |Q1 (I)| − |Q2 (I)| returns the number of perfect matchings. Note
that this is a special case of a Turing reduction, called subtractive reduction [6].
Obviously, this reduction is feasible in polynomial time. Its correctness as
well as the membership will be proved in the full version. t
u
5 Extensions
In this section we discuss some extensions and applications of our main results.
Unions of conjunctive queries. For unions of conjunctive queries (UCQs), it
is well known that the decision problem is not harder to solve than for CQs. In
contrast, for the counting problem, even if we consider UCQs with distinguished
variables only, we encounter a similar problem as for CQs with nondistinguished
variables: the same answer could be produced in different ways. For UCQs this
means that the same answer could appear in several disjuncts. In fact, a slight
modification of the proof of Theorem 4 yields the following intractability result.
Theorem 5. WnSuppose that we only consider unions of acyclic conjunctive queries
ans(x) ← i=1 φi (x) without nondistinguished variables. Then the combined
complexity of the counting problem of such UCQs is #P-complete.
Proof (idea). For the hardness, recall the hardness part of the proof of Theo-
rem 4. We use the same reduction as described there, only that instead of a single
relation
Wn Vt/2,
n
we use n relations
Vn and we define Q2 as Q2 : ans(x1 , . . . , xn ) ←
ti /1,
j=1 i=1 e(ai , xi ) ∧ i=1 t j (x i ) . We define instance I also as before, but in-
Sn
stead of the content of t, we have j=1 {tj (x) | x ∈ B \ {bj }}.
Intuitively, we expand the query by instantiating the existentially quantified
variable in Q2 , and create one disjunct for every instantiation. Hence, for the
correctness, analogous arguments as in the proof of Theorem 4 apply. t
u
Queries with bounded hypertree-width. In [11] it was shown that testing
if the result of a CQ is nonempty (or whether the result contains a certain tuple)
is tractable for queries with bounded hypertree-width. Below we also generalise
the tractability of #CQ on ACQs to queries with bounded hypertree-width.
10
Theorem 6. Suppose that we only consider CQs Q whose hypertree-width is
bounded by some constant. Then the following holds: If Q contains no nondistin-
guished variables, then #CQ is polynomial time solvable (combined complexity).
On the other hand, if Q contains nondistinguished variables, then solving
#CQ is feasible in polynomial time (data complexity and query complexity),
while the problem is #P-complete (combined complexity).
Proof (idea). In [11] it was shown that, given a Boolean CQ Q with hypertree-
width ω (for some constant ω) over some instance I, an equivalent ACQ Q0 over
an instance I 0 can be efficiently constructed, such that the combined size of Q0
and I 0 is in O(|Q| · mω ), where m = maxSi ∈I |Si |, and s.t. Q(I) returns true
iff Q0 (I 0 ) returns true. It is easy to verify that this construction preserves the
number of solutions. Actually, even Q(I) = Q0 (I 0 ) holds. Hence applying the
results from the previous sections to Q0 and I 0 proves the case. t
u
Counting under bag semantics. So far, we have only considered counting
under set semantics. However, by a slight change of the initialisation step, the
algorithm presented in Section 3 works for counting under bag semantics as
well. Further, note that the proof of Theorem 4 heavily depends on assuming
set semantics for the query. In fact, we can show the following result.
Theorem 7. Suppose that we only consider ACQs. Then, for query Q with join
tree T over schema R and instance I, #CQ w.r.t. bag semantics can be solved
in time O(|Q| · maxt∈T |Rt |2 ) (assuming unit cost for arithmetic operations), no
matter whether Q contains nondistinguished variables or not.
Proof (sketch). First, note that under bag semantics, there is no need to make a
distinction between distinguished- and nondistinguished variables: In Section 4,
the problem was to avoid multiple counting of the same solution if it can be
derived in several ways. However, under bag semantics, this is exactly what we
want to do. Hence, we can just consider all variables in Q as free.
It therefore remains to show that the algorithm from Section 3 can be adapted
to bag semantics. In fact, the only thing that needs to be changed is in the
initialisation phase: Recall that for every distinct tuple ρ ∈ Rt , we add a tuple
(ρ, 1) to R̂t . All that needs to be changed is to replace 1 by the number of
occurrences of ρ ∈ Rt . It can be easily checked that the remaining algorithm can
be left unchanged. t
u
6 Conclusion
In [16], we started to look for a tractable fragment of the #CQ problem via
the tree-width of the query. In the current paper, we initiated a systematic
study of tractable fragments of #CQ, considering ACQs and CQs with bounded
hypertree-width (which is a more general measure than tree-width). We have
presented new algorithms based on semi-joins which allowed us to prove several
new tractability results. We also identified limits to this search for tractable
fragments by proving the #P-completeness of the #CQ problem for arbitrary
acyclic conjunctive queries. Our results apply to the count operator, which is an
11
integral part of the SQL language. In the future, we want to extend the search
for tractable fragments to other aggregate functions (like minimum, maximum,
sum, average) and to the group by construct in SQL.
Another interesting extension of [16] would be the search for a dichotomy
result in the style of [13]. Further, extending the results from [2] concerning
the expressiveness of counting the answers of CQs to ACQs, and addressing the
complexity related questions raised there is another direction for future work.
References
1. M. Bauland, P. Chapdelaine, N. Creignou, M. Hermann, and H. Vollmer. An
algebraic approach to the complexity of generalized conjunctive queries. In SAT
2004 - Revised Selected Papers, volume 3542 of LNCS, pages 30–45. Springer, 2005.
2. M. Bielecki and J. V. den Bussche. Database interrogation using conjunctive
queries. In Proc. ICDT 2003, pages 259–269. Springer, 2003.
3. A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries
in relational data bases. In Proc. STOC 1977, pages 77–90. ACM, 1977.
4. C. Chekuri and A. Rajaraman. Conjunctive query containment revisited. Theor.
Comput. Sci., 239(2):211–229, 2000.
5. N. Creignou and M. Hermann. Complexity of generalized satisfiability counting
problems. Inf. Comput., 125(1):1–12, 1996.
6. A. Durand, M. Hermann, and P. G. Kolaitis. Subtractive reductions and complete
problems for counting complexity classes. Theor. Comput. Sci., 340(3):496–513,
2005.
7. R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes.
J. ACM, 30(3):514–550, 1983.
8. J. Flum, M. Frick, and M. Grohe. Query evaluation via tree-decompositions. J.
ACM, 49(6):716–752, 2002.
9. G. Gottlob, N. Leone, and F. Scarcello. A comparison of structural CSP decom-
position methods. Artif. Intell., 124(2):243–282, 2000.
10. G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive
queries. J. ACM, 48(3):431–498, 2001.
11. G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable
queries. J. Comput. Syst. Sci., 64(3):579–627, 2002.
12. M. Graham. On the universal relation. University of Toronto technical report,
1979.
13. M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive
queries tractable? In Proc. STOC 2001, pages 657–666, 2001.
14. P. G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint
satisfaction. J. Comput. Syst. Sci., 61(2):302–332, 2000.
15. C. H. Papadimitriou. Computational complexity. Addison-Wesley, 1994.
16. R. Pichler and S. Skritek. The complexity of evaluating tuple generating depen-
dencies. In Proc. ICDT 2011, pages 244–255. ACM, 2011.
17. N. Robertson and P. D. Seymour. Graph minors. ii. algorithmic aspects of tree-
width. J. Algorithms, 7(3):309–322, 1986.
18. L. G. Valiant. The complexity of enumeration and reliability problems. SIAM J.
Comput., 8(3):410–421, 1979.
19. M. Yannakakis. Algorithms for acyclic database schemes. In Proc. VLDB 1981,
pages 82–94. IEEE Computer Society, 1981.
20. C. Yu and M. Ozsoyoglu. An algorithm for tree-query membership of a distributed
query. In Proc. COMPSAC 1979w, pages 306–312. IEEE, 1979.
12