Conjunctive queries (CQs) are one of the most fundamental forms of database queries. In general, the evaluation of CQs is NPcomplete. 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.
other tractable fragments of CQs [
In this paper, we concentrate on the counting problem related to CQ
evaluation, 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
intractable. Indeed, it is #P-complete for CQs with free variables only (i.e., no
existential quanti ers) and even slightly harder (namely # NP-complete) in the
general case [
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 speci c 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 quanti ers.
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 signi cant 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 immediately carry over to CQs of bounded hypertree-width. In Section 5, we discuss further extensions and applications of our results. For instance, the #Pcompleteness of the combined complexity of the counting problem of ACQs allows us an easy #P-completeness proof for the counting problem of unions of ACQs even if these ACQs have no existentially quanti ed variables at all. 2
Schemas and instances. A relational schema R = fR1; : : : ; Rng is a set of
relation symbols Ri each of a xed arity k and with an assigned sequence of k
attributes (A1; : : : ; Ak). An instance I over a schema R consists of a relation RI
i
for each relation symbol Ri 2 R, s.t. both have the same arity. We only consider
nite instances here, and denote with dom(I) the active domain of I. We write
x for a tuple (x1; : : : ; xn). By slight abuse of notation, we also refer to the set
X, etc. For
CQs. A conjunctive query (CQ) Q on a database schema R is of the form
Q : ans(x) 9y (x; y), where (x; y) = Vin=1 ri is a conjunction of atoms ri =
Rj (z), s.t. Rj 2 R with arity k, and z x [ y with jzj = 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 [
In this paper, we study the counting problem #CQ, which is de ned as
follows: Given a conjunctive query Q over some relational schema R and an
instance I for R, how many tuples are contained in ansQ(I)?
ACQs. There exist several notions of acyclic CQs (ACQs). We restrict ourselves
here to the so-called -acyclicity [
Hypertree decompositions. A hypertree decomposition [
We rst consider CQs of the form ans(x) (x), i.e. only queries that contain
no existentially quanti ed variables. Without further restrictions, #CQ is well
known to be #P-complete for CQs of this form [
Before describing the algorithm, we have to x 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 2 T , Qt denotes the query atom identi ed 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 (fQtg). For Qt = Ri(x1; : : : ; xk), if clear from the context, it is convenient to also write Qt to refer to (x1; : : : ; xk) only. For a subtree T 0 of T , XT 0 = St2T 0 Xt and QT 0 = St2T 0 Qt. Given QT 0 , the subquery de ned by QT 0 is the query ans(XT 0 ) V the following, we always assume an acyclic CQ Q : ans(x) (x) witth2Tj o0iQntt.rIene 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 2 T , in a bottom-up traversal of the tree the number of possible extensions of to XTt that are valid solutions to the subquery de ned by QTt . Formally, for a mapping : XTt ! dom(I) and some t 2 T , we de ne the footprint of on t as fpr ( ; t) = , where is a variable assignment on Xt s.t. (xi) = (xi) for all xi 2 Xt. For a subtree T 0 T with root t and : Xt ! dom(I), we de ne the set N (T 0; t; ) = f : XT 0 ! dom(I) j fpr ( ; t) = and (QT 0 ) Ig 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 2 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 a ord to compute this set explicitly (which would be the naive algorithm), we just compute and store its cardinality, i.e. jN (Tt; t; )j. Hence, at each node t 2 T we maintain a table R^t, having jXtj + 1 columns. Thereby the rst jXtj columns (denoted as R^t; (Xt)) store , while the last column stores jN (Tt; t; )j. To better distinguish between jN (Tt; t; )j, 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) 2= Rt, we need no entry in R^t, and therefore R^t contains exactly one row for every 2 Rt s.t. jN (Tt; t; )j > 0. Thereby denotes the variable assignment de ned 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 2Rr N (Tr; r; ) gives all possible variable assignments on XTr = x s.t.
(QTr ) = (Q) I. By the disjointness of N (Tr; r; ) for di erent values of nu, mjSber2Rofr dNi (Terre;nrt; so)jlu=tioPns.2IRtrrjeNm(aTirn;srt;o )sjh, oawndhothwerteofocroemPput2eRtrhce vgailvueess tfhoer 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 2 T , R^t is computed as follows: For every distinct tuple 2 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 2 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 2 f1; : : : ; kg. The idea is now to compute R^t by starting from a relation considering t only and then, step by step, for every j 2 f1; : : : ; kg, to include the subtree Tj (where we use Tj to abbreviate Ttj ) by computing the semijoin between the output of the previous step and R^tj . Formally, let R^t0 contain a tuple ( ; 1) for every distinct tuple 2 Rt, i.e. R^t0 is de ned analogously to R^t0 for a leaf node t0 2 T . Then, for every child j 2 f1; : : : ; kg, compute Rt; (Xt) = R^tj; 1(Xt) n R^tj; (Xtj ). To compute cj for every row in R^tj, we rst ^j de ne for every 2 R^tj; (Xt) the set B R^tj; (Xtj ) containing exactly those 2 R^tj; (Xt) that can be joined with , i.e. B (xi) for every xi 2 Xt \ Xtj g. Then cj for every row = f 2 R^tj; (Xtj ) j (xi) =
^j 2 Rt; (Xt) is set to cj = cj 1 P 2B c where cj 1 is the value of c in R^tj 1. Finally, R^t = R^tk.
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 = fR1(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)g over the schema R = fR1=3; R2=2; R3=1; R4=3g. A possible join tree for Q is shown in Fig. 1, where each of the nodes t 2 ft1; : : : ; t5g 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 nal result jQ(I)j = 9 can be read o at the root node.
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(jQj (maxt2T jRtj)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 2 T , R^t; (Xt) Rt. Hence, at each node t 2 T , the space required to store R^t is obviously in O(jRtj). On the other hand, by de nition, 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 2 T is trivially O(jQj maxt2T jRtj). 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(jQj (maxt2T jRtj)2). tu
For deciding whether a CQ has some solution, it makes no di erence whether it
contains only free variables, or additional nondistinguished ones. As the goal is
just to nd 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
problem, this is no longer true, as only variable assignments that di er on the free
variables also give di erent solutions. On the other hand, variable assignments
that only di er on the existentially quanti ed variables must not be counted
twice. As already noted in the introduction, under reasonable complexity
theoretical assumptions, in the general case, counting becomes harder for queries
with nondistinguished variables [
Given an ACQ Q : ans(x) 9y (x; y), the naive approach for counting
the number of solutions over some instance I is to check for each possible
variable assignment : x ! dom(I), whether the (Boolean) ACQ Q0 : ans()
9y ( (x); y) is satis ed over I. As Q0 is acyclic, the check can be done in time
O(jQj jIj) [
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 2 T , to de ne 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 de ned 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 di erent y, have di erent footprints. Hence, if we de ne 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 f( x; y1); : : : ; ( x; yn)g. For convenience, we may also write ( x; I) with I = f y1; : : : ; yng to denote the combined footprint.
For a subtree Tt at node t 2 T and a combined footprint ( x; I) at node t, we de ne N (Tt; t; x; I) as the set of mappings x : XTt ! dom(I) such that (1) for every i 2 f1; : : : ; jIjg, 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 2 f1; : : : ; jIjg s.t. fpr ( x; y; t) = ( x; yj) As mentioned above, we cannot a ord to store the set N (Tt; t; x; I) at node t 2 T . Hence, we only store ( x; I) together with jN (Tt; t; x; I)j, since we are only interested in the number of such assignments. Note that ( x; I) ts into a table with jXtj + jYtj columns (i.e. with schema (Xt; Yt)), containing one row i for every yi 2 I, storing x in the rst jXtj columns, and yi in the last jYtj columns. Hence at every node t 2 T , we maintain a set R^ Tt = fS^1; : : : ; S^ng (for some n 2 N; an upper bound on n will be given below) of relations of the above form. In addition, we maintain for each relation S^j 2 RTt a counter ctj storing ^ jN (Tt; t; x; I)j. 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 S^j 2 R^ t encodes a set of mappings x : XTt ! dom(I), while each row in S^j encodes a di erent 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 2 T ) is again computed in two phases. In an initialisation phase, rst for every leaf node t 2 T , R^ t contains exactly one relation for every di erent value x for Xt in Rt, containing one row ( x; y) for every value y for Yt s.t. ( x; y) 2 Rt. The counter for each such relation is set to one. Then, in a bottom-up traversal of the tree, for every t 2 T with children t1; : : : ; tk s.t. R^ ti has already been computed, we again start with some R^ t0 that is de ned like R^ t0 for leaf nodes t0 2 T , and then include one child after the other as follows: For i 2 f1; : : : ; kg, let R^ it contain all nonempty results S^1 n S^2 for all pairs (S^1 2 Rt ^
^ i 1; S^2 2 Rti ). If S^1 n S^2 is nonempty, the value of the counter for the resulting table is the product of the counters for S^1 and S^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 S^j 2 Rr 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) 9yR3(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 2 ft1; : : : ; t5g 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^ t0 ) R^ t1 ) R^ t". Thereby, the rst row in each table shows the schema, followed by the relations S^j 2 R^ it separated by double horizontal lines. In the rst row for each relation S^j , the last column shows the counter for S^j . For instance, at node t3, we have two relations S^1 = f(s1; c1; b1); (s1; c1; b2)g and S^2 = f(s1; c1; b2)g in R^ t. Note that S^1 and S^2 refer to two di erent extensions of x(x1; x2) = (s1; c1) to x(x1; x2; x4). Indeed, S^1 corresponds to x(x4) = a1 while S^2 corresponds to x(x4) = a2. Again, the nal result jQ0(I)j = 6 can be read o at the root node.
t1 : R2(x2; y) x2 y c x2 y c c1 b2 1 c1 b2 3 ) c1 b1 ) c1 b1 c4 b6 1 c4 b6 3
Theorem 3. Suppose that we only consider ACQs Q : ans(x) 9y (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(jQj m2 4m) (assuming unit cost for arithmetic operations), where m = maxt2T jRtj.
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 2 T , the values for Xt need not be di erent between two di erent relations S^i; S^j 2 R^ t. Hence for every t 2 T , there might be up to 2m di erent elements in R^ t, each of size O(m) (obviously, S^i Rt for every S^i 2 R^ t), where m = maxt2T jRtj. 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(jQj m2 (2m)2). tu
Theorem 2 and Theorem 3 immediately imply that #CQ can be solved efciently for data- and query complexity. The natural next question is, whether there exists also an algorithm that solves the problem e ciently 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) 9y (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 [
Obviously, this reduction is feasible in polynomial time. Its correctness as well as the membership will be proved in the full version. 5
Queries with bounded hypertree-width. In [
j=1ftj (x) j x 2 B n fbj gg.
Intuitively, we expand the query by instantiating the existentially quanti ed variable in Q2, and create one disjunct for every instantiation. Hence, for the correctness, analogous arguments as in the proof of Theorem 4 apply. tu tu 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 nondistinguished 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 [
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 2 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 2 Rt. It can be easily checked that the remaining algorithm can be left unchanged. tu 6
In [
Another interesting extension of [