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