Project-connex Decompositions and Tractability of Aggregate Group-by Conjunctive Queries Diego Figueira, Cibele Freire Abstract We introduce ‘project-connex’ tree-width as a measure of tractability for counting and aggregate conjunctive queries over semirings with ‘group-by’ projection (also known as ‘AJAR’ or ‘FAQ’ queries). This elementary measure allows to obtain comparable complexity bounds to the ones obtained by previous structural conditions tailored for efficient evaluation of semiring aggregate queries, enumeration algorithms of conjunctive queries, and tractability of counting answers to conjunctive queries. Project-connex tree decompositions are defined as the natural extension of the known notion of ‘free-connex’ decompositions. They allow for a unified, simple and intuitive algorithmic manipulation for evaluation of aggregate queries and explain some existing tractability results on conjunctive query enumeration, counting conjunctive query evaluation, and evaluation of semiring aggregate queries. Using this measure we also recover results relating tractable classes of counting conjunctive queries and bounded free-connex tree-width, or the constant-time delay enumeration of semiring aggregate queries over bounded project-connex classes. We further show that project-connex tree decompositions can be obtained via algorithms for computing classical tree decompositions. Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, France diego.figueira@cnrs.fr https://orcid.org/0000-0003-0114-2257 Computer Science Department, Bowdoin College, USA cfreire@bowdoin.edu https://orcid.org/0009-0000-4242-1311 \declaretheorem [name=Theorem,numberwithin=section]thm keywords tree decomposition, query evaluation, counting complexity, aggregate queries, semirings † † runningtitle: Project-connex Decompositions and Tractability of Aggregate CQs † † runningauthor: D. Figueira and C. Freire † † copyright: Diego Figueira and Cibele Freire † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: XX † † articleno: XX 🖙 This pdf contains internal links: clicking on a notion leads to its definition . 1 Introduction The aim of this work is to offer an alternative structural measure for the study of evaluation and enumeratimacon of aggregate conjunctive queries. We introduce project-connex width as a natural and intuitive extension of the notion of ‘free-connex’ width having an intuitive definition. Our approach views aggregation as a generalized form of projection over suitable semirings in conjunctive queries, in line with the seminal work on the AJAR [ JoglekarPR16 ] and FAQ frameworks [ KhamisNR16 , DBLP:journals/tods/KhamisCMNNOS20 , khamis2023faqquestionsaskedfrequently ] . We adopt the widely used annotated database setting [ GreenKT07 ] , where each tuple in a database is associated with an annotation drawn from a given commutative semiring. Annotations can be combined, depending on the context, using the semiring’s multiplicative ( \otimes ) and additive ( \oplus ) operations. In this setting, the relational algebra join ( \Join ) between two relations results in a new relation where annotations are combined by \otimes -multiplying the corresponding tuples. On the other hand, the projection ( \pi ) collapses all tuples that agree on a set of attributes, and their annotations are aggregated using the semiring’s \oplus -additive operation. This semiring-based semantics supports efficient evaluation of conjunctive queries via Yannakakis-style algorithms on tree decompositions, even in the generalized setting. We further consider the framework of [ JoglekarPR16 , KhamisNR16 ] , in which projections over different sorts of ‘sums’ can be nested, giving the possibility of nesting ‘group-by’ operations on conjunctive queries. We give below some examples to build intuition on this kind of queries. An introductive example Consider the query asking to return each salesperson in Boston together with their maximum sales produced in any given day, over a database with schema Branch(city,person) , Sale(person,date,product,qty) , Price(product,amount) , where each row in a database is annotated with a number : the last number of the row in the case of Sale and Price tables, and ‘1’ in the case of Branch , as depicted in Figure 1 -(a). Figure 1 : (a) A database D of sales, where row annotations are in green. (b), (c) project-connex tree decompositions. The evaluation Q(D) of Q on D outputs salesperson ‘p1’ with value 18 and ‘p2’ with value 20 ; while Q^{\prime}(D) outputs ‘Boston’ with value 38 . To compute the query’s output, we need a natural join where the annotations are multiplied when joined. We then use a join parameterized by the multiplication operation on numbers, i.e. , \textsf{Branch}(\textup{`Boston'},\textit{pers})\Join^{\textup{mult}}\textsf{Sale}(\textit{pers},d,\textit{prd},qty)\Join^{\textup{mult}}\textsf{Price}(\textit{prd},amt) , that we just write as \Join^{\textup{mult}}\{\textsf{Branch}(\textup{`Boston'},\textit{pers}), \textsf{Sale}(\textit{pers},d,\textit{prd},qty), \textsf{Price}(\textit{prd},amt)\} . Now we need to aggregate: first by summing all sales of each day/person, and then findinig the maximum for each person. This is done using projection operators, which specify an aggregation operation to perform for rows having the same projection. Then the aggregate query in the language we study is the following: Q\mathrel{\hat{=}}\pi^{\max{}}_{\{\textit{pers}\}}\pi^{\textup{sum}}_{\{\textit{pers},d\}}\Join^{\textup{mult}}\{\textsf{Branch}(\textup{`Boston'},\textit{pers}),\textsf{Sale}(\textit{pers},d,\textit{prd},qty),\textsf{Price}(\textit{prd},amt)\}. When can this kind of queries be evaluated efficiently? Observe that both (\mathbb{N},\textup{sum},\text{mult}) and (\mathbb{N},\max{},\text{mult}) are commutative semirings , and it is in this context that we work: queries in which the join-operation and the project-operation form a semiring . When working over a commutative semirings , efficient evaluation methods based on tree decompositions can often be adapted exploiting the versatility offered by the semiring distributivity. To understand whether the evaluation can be done efficiently, one may consider ‘tree decompositions’, such as the decomposition of Q of Figure 1 -(b). Observe how each bag ( i.e. , each gray potato of variables) is covered 1 1 1 ‘Covered’ in the sense that the variables of the atom contain all variables of the bag. Generally, it would be covered by k atoms if there were k atoms whose variables contain all the bag’s variables. by one atom of the query and hence its ‘width’ is said to be one (this is known as the ‘generalized hypertree width’, or ‘coverwidth’). Further, there are two subtrees (highlighted in red and in blue) which: (i) contain precisely the variables of the projections ( i.e. , \{\textit{pers}\} and \{\textit{pers},d\} resp.), and (ii) the first one is contained in the second one. We shall say that such decomposition is then ‘ project-connex ’, since each projection set has an associated connected subtree. As we show, the existence of this decomposition witnesses an efficient evaluation. In this example, since the width is one, the query admits a constant delay enumeration after a linear pre-processing ( ). If the query was numeric, for instance by outputting the maximum sales by a person in any given day (which would be formally denoted by \pi^{\max{}}_{\varnothing}Q ), then the output can be computed in linear time ( ). And more generally, the output can be computed in \mathcal{O}(|Q|\cdot n^{k}) time for project-connex width k queries, where n is the size of the database ( ). This is true also for aggregate queries with an arbitrary nesting of aggregate operations. If instead of ‘Boston’ we would prefer outputting, for each location, the sum of maximum sales of any salesperson in a day ( e.g. , as a bound to the maximum future turnover in a day per location), we could have written Q^{\prime}\mathrel{\hat{=}}\pi^{\textup{sum}}_{\{\textit{loc}\}}\pi^{\max{}}_{\{\textit{pers},\textit{loc}\}}\pi^{\textup{sum}}_{\{\textit{pers},d,\textit{loc}\}}\Join^{\textup{mult}}\{\textsf{Branch}(\textit{loc},p),\textsf{Sale}(\textit{pers},d,\textit{prd},qty),\textsf{Price}(\textit{prd},amt)\} and there would still be the project-connex decomposition Figure 1 -(c) witnessing tractability. Depending on the number of nested projections and choice of semirings on these aggregate queries, we may find different previously studied query languages. For example: • If there is only one projection which covers all variables and we work on the (\mathbb{N},\text{sum},\text{mult}) semiring, the queries express counting homomorphisms from conjunctive queries (or, equivalently, counting the number of answers to full conjunctive queries), and its tractability has been characterized as having bounded tree-width [ DalmauJ04 ] . • If there is only one projection but which may not cover all variables, we may be rather interested in the efficient enumeration of answers; in this vein we find the setting of enumerating answers to conjunctive queries, for which bounded ‘free-connex’ tree-width has been identified as a fundamental measure in the pioneering work [ BaganDG07 ] . • On the other hand, a particular case of two nested projections is counting the number of answers to conjunctive queries, for which other measures characterizing tractability have been developed [ DurandMengel15 ] . Works on constant-delay enumeration, counting, and provenance have initially evolved rather independently, proposing a series of tractability measures on queries with two different sorts of problems in mind: constant-delay enumeration and direct access on the one hand, and evaluation on the other. Some structural query measures found in the literature are: • ‘free-connex’ tree decompositions [ BaganDG07 ] in the context of Conjunctive Query enumeration; • ‘quantified star-size’ [ DurandMengel15 ] , tree-width of ‘contracted’ queries [ DBLP:conf/icdt/ChenM15 ] , or ‘ \# -hypertree decompositions’ [ GrecoS14 ] in the context of counting solutions to Conjunctive Queries; • ‘decomposable’ and ‘valid’ tree decompositions [ JoglekarPR16 ] and ‘FAQ-width’ [ KhamisNR16 , khamis2023faqquestionsaskedfrequently ] in the context of evaluation of aggregate Conjunctive Queries over arbitrary semirings. Contributions We show how a simple measure like project-connex width can explain most tractability results in the areas above, allowing an elementary and uniform algorithmic treatment for both evaluation and enumeration. Hence, this work is guided by the question of whether there is a query measure which is simultaneously simple to define , easy to compute , and admitting simple algorithmic manipulation that can be used to give an account of the basic tractability results on aggregate conjunctive queries, including enumeration . This quest leads to the proposal of the project-connex measure, that we believe can improve the understanding and teaching of some of the rich and deep results developed in the literature. It is important to remark that influential previous work [ KhamisNR16 , khamis2023faqquestionsaskedfrequently ] already unifies known results for CQs and \# CQs (and more), but our approaches differ on methodology and scope (more on this in Section 2 ). We adopt the general approach for aggregation, provenance and counting, in such a way that they can be expressed and intermixed in a rather intuitive way, in queries which also admit free variables and are hence amenable to enumeration algorithms. Our aggregate queries are in line with the FAQ/AJAR approach 2 2 2 There are some syntactical differences on how the language is defined, but the underlying concept is similar. stemming from the seminal works [ KhamisNR16 , khamis2023faqquestionsaskedfrequently , JoglekarPR16 ] , which in particular includes a form of group-by queries. This allows to capture queries such as taking the maximum of aggregate queries, or enumerating the tuples satisfying a query together with some aggregate value, or more complex nested queries. For example, it is often the case that efficiently-enumerable queries are also efficient for counting the number of answers [ berkholz2020constant ] . Here we see ‘enumeration’ and ‘counting’ as two sorts of queries from a same “ aggregate query language ”, with a unified evaluation algorithm . We give next some more detail on our contributions. Introducing structural conditions for tractability. We generalize the notion of “free-connex” tree decompositions to “project-connex”, where we allow an arbitrary nesting of projections ( Section 5 ). This allows to obtain complexity upper bounds for nested group-by queries. Computing project-connex width. We show that the project-connex width of an aggregate query \gamma can be simply computed as the tree-width of a conjunctive query q which can be obtained from \gamma in polynomial time. Further, we show that project-connex decompositions of width 1 ( i.e. , acyclic) can be produced in linear time ( Sections 5 and ). Providing combined complexity bounds. In we provide complexity bounds via an elementary algorithm which yields a modest improvement —to the best of our knowledge— in the state-of-the-art bounds for evaluation in combined complexity of counting and enumeration of CQs with bounded free-connex width. Further, the same algorithm also yields the constant delay enumeration of aggregate queries , whenever there are free variables. Simplifying the tractability measure for counting CQs. For the case of counting answers to conjunctive queries, we show that project-connex boundedness (which in the setting of CQs is just free-connex) is equivalent to the known characterization for tractability [ DurandMengel15 ] . Arguably, this simplifies the tractability characterization theorem 3 3 3 It simplifies the statement, but not the proof, which crucially relies on prior characterization results by Chen, Durand, and Mengel for counting CQs [ DurandMengel15 , DBLP:conf/icdt/ChenM15 ] . for counting CQs ( ). Hence, an added value of using a generalization of free-connex decompositions is to make explicit known connections between counting and enumeration. Organization We start on Section 2 with a discussion of related work. After some preliminaries in Section 3 , we introduce the aggregate queries we will study in Section 4 . In Section 5 , we introduce the notion of project-connex decompositions and prove that computing such decompositions of any width is polynomial time, and linear time in the case of acyclic decompositions. illustrates how decompositions are useful to algorithmic manipulation, by giving a simple procedure for evaluating and enumerating aggregate queries . shows that project-connex decompositions can be used for characterizing tractability on counting CQs. Finally, in we give some concluding remarks. Due to space constraints, missing proof details and extended discussions are relegated to the appendix. 2 Related Work FAQ/AJAR framework. Previous, seminal works [ KhamisNR16 , JoglekarPR16 , khamis2023faqquestionsaskedfrequently ] study essentially the same aggregate query language as we do here. The emphasis of these works is put on ‘semantic equivalence’, that is, characterizing when two queries, which only differ in the order in which the projections are applied, are equivalent depending on the semirings at hand. In constrast, our measures are purely structural and completely blind to the specific semiring being used. For these reasons, our results do not necessarily imply any of the previous bounds of [ JoglekarPR16 , KhamisNR16 , khamis2023faqquestionsaskedfrequently ] . Rather, we emphasize that bounded project-connex width can already explain tractability of some aggregate queries and leads to the elementary algorithm of for evaluation and enumeration. On the other hand, the cited works focus their analysis of query evaluation on data complexity. In comparison, our algorithmic analysis yields also combined complexity bounds. FAQ queries with additive inequalities (FAQ-AI) [ DBLP:journals/tods/KhamisCMNNOS20 ] were studied later, and their work shows better bounds for query evaluation than earlier results from [ KhamisNR16 , khamis2023faqquestionsaskedfrequently ] . Similar to our work and [ khamis2023faqquestionsaskedfrequently ] , they obtain constant delay enumeration, when carefully considering how to represent the query output. On a syntactic level, the aggregate queries we introduce are slightly different to the ones of FAQ/AJAR since our projection operator projects onto a set of variables while their projection operator projects away one variable at a time. Concretely, a CQ q(\{x_{1},\dotsc,x_{n}\}) , where {\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(q)=\{x_{1},\dotsc,x_{n},\dotsc,x_{m}\} is expressed to something closer to \pi^{\oplus}_{x_{n+1}}\pi^{\oplus}_{x_{n+2}}\dotsb\pi^{\oplus}_{x_{m}}{\Join^{\otimes}}q in their work instead of as \pi^{\oplus}_{\{x_{1},\dotsc,x_{n}\}}{\Join^{\otimes}}q in our formalism. Among the reasons for our proposed syntax are to make the link to free-connex decompositions evident, since we project onto a set of variables, and to be able to give some complexity results in terms of the number of projections ( ), which implies a linear time algorithm for classes of bounded number of projections, independently of how many variables we may be projecting away. In addition, [ JoglekarPR16 ] also investigates structural conditions for efficient evaluation, based on a restriction of tree decompositions called “decomposable”. While decomposable and project-connex are distinct decomposition restrictions, they share some common aspects. Our objective in using project-connex decompositions lies in their intuitive connection to enumeration measures, allowing us to directly leverage known results. We also remark that [ JoglekarPR16 , Definition 3] proposes a width measure which may also bear some resemblances to project-width, as well as a way to compute it by means of reducing it to the computation of the tree-width of conjunctive queries (as we do here). 4 4 4 Unfortunately the characterization provided in the paper has an error ( cf. ), but we believe that our characterization for project-width can be used instead, implying that the results of [ JoglekarPR16 ] relying on the characterization still hold. Counting. [ DalmauJ04 ] offers the characterization of tractability for counting answers to full conjunctive queries – or, equivalently, counting homomorphisms – based on the boundedness of tree-width. For arbitrary conjunctive queries , the work [ DurandMengel15 ] initially established a characterization of tractability based on a measure of “quantified star-size”. This was later expanded in [ DBLP:conf/icdt/ChenM15 ] and [ ChenGrecoMengelScarcello23 ] , where the proposed tractability characterization is based on the tree-width of two related queries: its core and the so-called ‘contraction’ of the query. 5 5 5 The need to use the tree-width measure on two separate queries is useful and probably necessary for deriving the trichotomy result of [ DBLP:conf/icdt/ChenM15 ] in parameterized complexity . As we show, if the focus is on obtaining a tractability characterization, one can just use the notion of width on tree decompositions which are “free-connex”. Our bounds for the evaluation of counting queries are, to the best of our knowledge, in line or improving the algorithms in the literature. In particular, seems to improve on the bound of [ PichlerS13 , Theorem 5 with k=0 ] in combined complexity, which claims \mathcal{O}({\color[rgb]{0.0195,0.2109,0.2539}|}q{\color[rgb]{0.0195,0.2109,0.2539}|}\cdot{\color[rgb]{0.0195,0.2109,0.2539}\|}D{\color[rgb]{0.0195,0.2109,0.2539}\|}^{2}) for acyclic full CQs . Enumeration. The recent work [ EldarCarmeliKimelfeld23 ] studies the complexity of enumeration and direct-access to results of conjunctive queries with grouping and aggregation over annotated databases. The paper focuses on acyclic queries in relation to the direct-access problem ( i.e. , the problem of accessing efficiently the i -th solution in the lex-ordering). For self-join free queries the aggregate query language of [ EldarCarmeliKimelfeld23 ] can be translated into ours, with a different syntax ( cf. ). For self-join queries the translation is not so simple, if at all possible. Output-Sensitive Evaluation. The classic Yannakakis algorithm provides an output-sensitive query evaluation bound of \mathcal{O}({\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}+{\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}\cdot|OUT|) for acyclic CQs [ Yannakakis81 ] , where OUT is the size of the output. This was the best known bound until very recently, when a series of papers made significant improvements. In [ Hu24 ] , the author uses fast matrix multiplication to devise an algorithm that improves the bound for acyclic CQs, obtaining a running time of \mathcal{O}({\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}+|OUT|+{\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}\cdot|OUT|^{5/6}) . Soon after, [ DeepZFK24 ] presents a generalization of Yannakakis algorithm to evaluate any acyclic CQ with running time \mathcal{O}({\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}+|OUT|+{\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}\cdot|OUT|^{1-\varepsilon}) , where 0<\varepsilon\leqslant 1 is a constant that depends on the query.They also show this bound is tight for star queries, and their algorithm is general enough to provide bounds for some aggregate queries (FAQ). The most recent work improves on previous results via a semiring algorithm [ Hu25 ] . Hu proves an output-optimal bound of \Theta({\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}\cdot OUT^{1-1/\textit{fn-fhtw}}+OUT) for acyclic queries, where fn-fhtw is the free-connex fractional hypertree width of the query. 3 Preliminaries We use the usual “bar notation” \bar{x} for a tuple of elements, where “ \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}()} ” denotes the empty tuple , \immediate{\color[rgb]{0.3438,0.0195,0.0273}\dim}(\bar{x}) denotes the dimension of \bar{x} , and \bar{x}[i] denotes its i -th element, for i\in\{1,\dotsc,{\color[rgb]{0.0195,0.2109,0.2539}\dim}(\bar{x})\} . In particular {\color[rgb]{0.0195,0.2109,0.2539}\dim}({\color[rgb]{0.0195,0.2109,0.2539}()})=0 . We fix disjoint infinite sets Const , Var of constants and variables , respectively. For any syntactic object O ( e.g. database, query, tuple), we will use \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{vars}}(O) and \immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{const}}(O) to denote the sets of variables and constants contained in O , and let \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{term}}(O)\mathrel{\hat{=}}{\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(O)\cup{\color[rgb]{0.0195,0.2109,0.2539}\textit{const}}(O) denote its set of terms . A (relational) schema is a finite set of relation symbols, each associated with an arity ( \geqslant 0 ). A (relational) atom over a schema \Sigma takes the form R(\bar{t}) where R is a relation name from \Sigma of some arity k , and \bar{t}\in({\color[rgb]{0.0195,0.2109,0.2539}\textup{Const}}\cup{\color[rgb]{0.0195,0.2109,0.2539}\textup{Var}})^{k} . A fact is an atom which contains only constants . A database D over a schema \Sigma is a finite set of facts over \Sigma . We denote by \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\textup{DB}_{\Sigma}} the set of all databases over \Sigma , or DB if the schema is not relevant. Let {\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|} be the size of the encoding of D and {\color[rgb]{0.0195,0.2109,0.2539}\|}D{\color[rgb]{0.0195,0.2109,0.2539}\|} be the maximum size of a relation of D , that is, \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}|}D{\color[rgb]{0.3438,0.0195,0.0273}|}\mathrel{\hat{=}}\sum_{R\in\Sigma}\sum_{R(\bar{c})\in D}\immediate{\color[rgb]{0.3438,0.0195,0.0273}\textup{arity}}(R) and \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\|}D{\color[rgb]{0.3438,0.0195,0.0273}\|}\mathrel{\hat{=}}\max_{R\in\Sigma}\sum_{R(\bar{c})\in D}{\color[rgb]{0.0195,0.2109,0.2539}\textup{arity}}(R) . A query is a computable function \gamma:{\color[rgb]{0.0195,0.2109,0.2539}\textup{DB}}\to\mathcal{O} for some output domain \mathcal{O} . To improve readability we denote by \gamma\immediate{\color[rgb]{0.3438,0.0195,0.0273}\langle}D{\color[rgb]{0.3438,0.0195,0.0273}\rangle} (instead of \gamma(D) ) its evaluation on a database D . For any class \mathcal{C} of queries , the evaluation task \immediate{\color[rgb]{0.3438,0.0195,0.0273}\textup{{Eval-}}}\mathcal{C} is the task of, given a database D and a query \gamma\in\mathcal{C} , computing \gamma{\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle} . 6 6 6 We understand this as a “ promise problem ”, that is, the input to the evaluation problem is a query from \mathcal{C} , as opposed to some arbitrary string. Unless otherwise stated, all the bounds we give for evaluation are in terms of combined complexity , that is, where both the query and the database are taken as input (we assume any reasonable encoding under the RAM model). We say \mathcal{C} admits constant delay enumeration after a polynomial pre-processing if there is an algorithm which upon a query \gamma and database D first performs a pre-processing in \mathcal{O}({\color[rgb]{0.0195,0.2109,0.2539}|}D{\color[rgb]{0.0195,0.2109,0.2539}|}^{k}) for some k in data complexity ( i.e. , where the query \gamma is fixed) in which some data structure is created, and then it enumerates, one by one and without repetitions, all answers from \gamma{\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle} such that the time between two consecutive answers does not depend on the size of the database . If k=1 , we say that \mathcal{C} admits constant delay enumeration after a linear pre-processing . We work under a standard computational model of Random Access Machines ( RAM ) (more details in ). For sets of atoms S_{1},S_{2} , a homomorphism from S_{1} to S_{2} is a function h:{\color[rgb]{0.0195,0.2109,0.2539}\textit{term}}(S_{1})\rightarrow{\color[rgb]{0.0195,0.2109,0.2539}\textit{term}}(S_{2}) such that R(h(t_{1}),\dotsc,h(t_{k}))\in S_{2} for every R(t_{1},\dotsc,t_{k})\in S_{1} . We write S_{1}\mathrel{\immediate{\color[rgb]{0.3438,0.0195,0.0273}\xrightarrow{\smash{\textit{hom}}}}}S_{2} to indicate the existence of such h . If further we have that h(c)=c for every c\in C\subseteq{\color[rgb]{0.0195,0.2109,0.2539}\textup{Const}}\cup{\color[rgb]{0.0195,0.2109,0.2539}\textup{Var}} , we call h a C -homomorphism and write S_{1}\mathrel{\immediate{\color[rgb]{0.3438,0.0195,0.0273}\xrightarrow{\smash{{C}\textit{-hom}}}}}S_{2} . If further h is bijective and h^{-1} is a C -homomorphism , we call h a C -isomorphism . A conjunctive query (henceforth just CQ ) over \Sigma is an expression of the form \pi_{X}q , where q is a finite set of atoms over \Sigma , and X is a subset of variables from {\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(q) . We will sometimes write q(X) instead of \pi_{X}q . We call X the free variables of q(X) ; the remaining ones are bound . If there are no free variables ( i.e. , X=\varnothing ), then the query is Boolean , and we often write it as q() . If all its variables are free , then we call the query full . The size of an atom \alpha , noted \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}|}\alpha{\color[rgb]{0.3438,0.0195,0.0273}|} , is the arity of the relation name it contains, and the size of a CQ q(X) , noted {\color[rgb]{0.3438,0.0195,0.0273}|}q{\color[rgb]{0.3438,0.0195,0.0273}|} , is the sum of sizes of its atoms . We use \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{atoms}}(q) to denote the set of atoms of a CQ q(X) . A CQ is self-join free if it has no two atoms with the same relation name . The arity of a class \mathcal{C} of CQs , noted {\color[rgb]{0.0195,0.2109,0.2539}\textup{arity}}(\mathcal{C}) , is the maximum arity of the relations used in the queries of \mathcal{C} , or \infty otherwise. The {\color[rgb]{0.0195,0.2109,0.2539}\textup{arity}}(\Sigma) of a schema is the maximum arity of a relation name therein. The evaluation of a CQ q(X) on a database D is the set q(X)\immediate{\color[rgb]{0.3438,0.0195,0.0273}\langle}D{\color[rgb]{0.3438,0.0195,0.0273}\rangle}\mathrel{\hat{=}}\{h|_{X}\mid h:q\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\xrightarrow{\smash{{C}\textit{-hom}}}}}D\} for C={\color[rgb]{0.0195,0.2109,0.2539}\textit{const}}(q) , where h|_{X} is the restriction of h on X . The evaluation problem for a class \mathcal{C} of CQs is the task of, given q(X)\in\mathcal{C} and D , computing q(X){\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle} . For a Boolean query q() , we often write D\models q to denote q(){\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle}\neq\varnothing . Two CQs q(X),q^{\prime}(X) are equivalent if q(X){\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle}=q^{\prime}(X){\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle} for every database D or, equivalently, if q\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\xrightarrow{\smash{{C}\textit{-hom}}}}}q^{\prime} and q^{\prime}\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\xrightarrow{\smash{{C}\textit{-hom}}}}}q for C=X\cup{\color[rgb]{0.0195,0.2109,0.2539}\textit{const}}(q)\cup{\color[rgb]{0.0195,0.2109,0.2539}\textit{const}}(q^{\prime}) . The core of a CQ q(X) is its minimal equivalent query, noted \immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{core}}(q(X)) , which is unique up to ( {\color[rgb]{0.0195,0.2109,0.2539}\textit{const}}(q)\cup X )-isomorphisms . The core of a class \mathcal{C} of CQs is {\color[rgb]{0.3438,0.0195,0.0273}\textit{core}}(\mathcal{C})\mathrel{\hat{=}}\{{\color[rgb]{0.0195,0.2109,0.2539}\textit{core}}(q(X)):q(X)\in\mathcal{C}\} . A (partial) assignment is a (partial) function f:{\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(q)\to{\color[rgb]{0.0195,0.2109,0.2539}\textup{Const}} . For \bar{x} and \bar{c} a tuple of variables from q and of constants, respectively, of the same dimension, \bar{x}\mathrel{\immediate{\color[rgb]{0.3438,0.0195,0.0273}\mapsto}}\bar{c} denotes the assignment mapping \bar{x}[i] to \bar{c}[i] for every i . 7 7 7 Assuming that there are no “clashes”, i.e. , that \bar{c}[i]=\bar{c}[j] for every i,j such that \bar{x}[i]=\bar{x}[j] . To obtain efficient evaluation algorithms, we focus on aggregate queries having a semiring embedded in its operators.A semiring \mathbb{K}=(K,\oplus,\otimes) verifies: (i) (K,\oplus) is a commutative monoid with identity 0_{\oplus} ; (ii) (K,\otimes) is a monoid ; (iii) \otimes distributes over \oplus ( i.e. , (a_{1}\oplus\dotsb\oplus a_{n})\otimes(b_{1}\oplus\dotsb\oplus b_{m})=\bigoplus_{i,j}a_{i}\otimes b_{j} ); and (iv) a\otimes 0_{\oplus}=0_{\oplus}\otimes a=0_{\oplus} for every a\in K . It is a commutative semiring if \otimes is further commutative . Tree Decompositions We use the standard notation for hypergraphs G , where \immediate{\color[rgb]{0.3438,0.0195,0.0273}V}(G) is the set of vertices and \immediate{\color[rgb]{0.3438,0.0195,0.0273}E}(G) the set of hyperedges. Given a hypergraph G and a set of vertices C thereof, let G\immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}[}{C}{\color[rgb]{0.3438,0.0195,0.0273}]} be the subgraph of G induced by C , obtained by replacing each edge e\in{\color[rgb]{0.0195,0.2109,0.2539}E}(G) with e\cap C when the intersection is nonempty. The underlying hypergraph \immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\mathbf{G}_{q}} of a CQ q(X) is the hypergraph where V({\color[rgb]{0.0195,0.2109,0.2539}\mathbf{G}_{q}})={\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(q) and E({\color[rgb]{0.0195,0.2109,0.2539}\mathbf{G}_{q}})=\{{\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(\alpha)~|~\alpha\in{\color[rgb]{0.0195,0.2109,0.2539}\textit{atoms}}(q)\} . A generalized hypertree decomposition (henceforth just tree decomposition ) of a hypergraph G is a tuple (T,\immediate{\color[rgb]{0.3438,0.0195,0.0273}\mathbf{b}},\immediate{\color[rgb]{0.3438,0.0195,0.0273}\mathbf{a}}) where T is a tree, {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}:{\color[rgb]{0.0195,0.2109,0.2539}V}(T)\to\mathcal{P}({\color[rgb]{0.0195,0.2109,0.2539}V}(G)) , and {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}}:{\color[rgb]{0.0195,0.2109,0.2539}V}(T)\to\mathcal{P}({\color[rgb]{0.0195,0.2109,0.2539}E}(G)) such that (a) for each hyperedge e\in{\color[rgb]{0.0195,0.2109,0.2539}E}(G) , there is a vertex v\in{\color[rgb]{0.0195,0.2109,0.2539}V}(T) such that e\subseteq{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(v) —this is the completeness condition ; (b) for each v\in{\color[rgb]{0.0195,0.2109,0.2539}V}(G) , the set of vertices \{t\in{\color[rgb]{0.0195,0.2109,0.2539}V}(T):v\in{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(t)\} is connected in T —this is often known as the connectivity condition ; 8 8 8 If v is isolated it may not appear in the decomposition. However, the hypergraphs we consider do not contain isolated vertices. (c) for each v\in{\color[rgb]{0.0195,0.2109,0.2539}V}(T) , {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(v)\subseteq\bigcup{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}}(v) —this is the covering condition . We often refer to vertices of T as bags , and say that a bag v contains some variable x to denote x\in{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(v) . The generalized hyperwidth (henceforth just ‘ width ’ for brevity) of such tree decomposition is the maximum cardinality of {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}}(v) , for v ranging over all vertices. The generalized hyperwidth of a hypergraph G , or \immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{ghw}}(G) , is the minimum (generalized hyper-) width among all its tree decompositions . The tree decomposition and generalized hyperwidth of a CQ or any K -aggregate query is defined analogously by applying the definitions above to its underlying hypergraph . An acyclic CQ or aggregate query is one having generalized hyperwidth 1 . In this context, a join tree of a set q of atoms is a tree decomposition of width 1 of q together with a witnessing bijection \varphi:{\color[rgb]{0.0195,0.2109,0.2539}V}(T)\to q such that {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}}(v)=\{{\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(\varphi(v))\} and {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(v)={\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(\varphi(v)) for every v . The tree-width of a tree decomposition is the maximum cardinality of {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(v) minus one, and the tree-width of q , or \immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{tw}}(q) , is the minimum tree-width among all its tree decompositions . Notice that when working with tree-width we can disregard the {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}} -component from the definition of tree decomposition and simply describe a tree decomposition as a pair (T,{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}) . Free-Connex Decompositions Given a tree decomposition (T,{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}},{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}}) of a hypergraph G and a set X\subseteq{\color[rgb]{0.0195,0.2109,0.2539}V}(G) , we say that T^{\prime} is a witness subtree for X (or simply a witness subtree if X is clear from the context) if T^{\prime} is a connected subtree of T such that \bigcup_{v\in{\color[rgb]{0.0195,0.2109,0.2539}V}(T^{\prime})}{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}}(v)=X . We say that a tree decomposition for a CQ q(X) is free-connex if it contains a witness subtree for X . The free generalized hyperwidth of a CQ q(X) , or \immediate{\color[rgb]{0.3438,0.0195,0.0273}\textit{fghw}}(q(X)) , is the minimum width among all its free-connex tree decompositions . Free connex decompositions have been introduced and studied in the realm of enumeration algorithms for CQs . In particular, sjf CQs of free generalized hyperwidth 1 ( a.k.a. free-connex acyclic sjf CQs ) characterize (under complexity theoretic assumptions) the sjf CQs admitting a constant delay enumeration after a linear pre-processing [ BaganDG07 , Theorem 34] . 4 Aggregate Queries For a set K , a K -annotated database is a pair (D,\immediate{\color[rgb]{0.3438,0.0195,0.0273}\nu}) where D is a database and {\color[rgb]{0.0195,0.2109,0.2539}\nu}:D\to K is a function giving a K -valued annotation to each fact . In our examples we will fix K=\mathbb{N} , and hence by annotated database we shall mean a \mathbb{N} -annotated database . We now define the language of aggregate queries based on CQs over K -annotated databases , which we call K -aggregate queries . 9 9 9 This language is heavily inspired by previous works as stated in Section 2 . A K -aggregate query on a set X of free variables yields, when evaluated on a K -annotated database , a set of pairs (f,n) such that f is an assignment f:X\to{\color[rgb]{0.0195,0.2109,0.2539}\textup{Const}} and n\in K . The syntax and semantics are given below: {\Join^{\otimes}}q Given a finite set q of atoms and a commutative monoid \otimes:K\times K\to K , the expression “ {\Join^{\otimes}}q ” is a K -aggregate query on X , for X={\color[rgb]{0.0195,0.2109,0.2539}\textit{vars}}(q) . Given a K -annotated database (D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}) the evaluation of {\Join^{\otimes}}q for q=\{\alpha_{1},\dotsc,\alpha_{\ell}\} on (D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}) is the set {\Join^{\otimes}}q\immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}{\color[rgb]{0.3438,0.0195,0.0273}\rangle}\mathrel{\hat{=}}\{(h,{\color[rgb]{0.0195,0.2109,0.2539}\nu}(h(\alpha_{1}))\otimes\dotsb\otimes{\color[rgb]{0.0195,0.2109,0.2539}\nu}(h(\alpha_{\ell})))\mid h:q\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\xrightarrow{\smash{{C}\textit{-hom}}}}}D\} for C={\color[rgb]{0.0195,0.2109,0.2539}\textit{const}}(q) . That is, it outputs all satisfying homomorphisms together with the \otimes -multiplication of the facts involved. For example, in the annotated database (D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}) of Figure 1 , {\Join^{\!\times}}\{\textsf{Sale}(\textit{pers},d,\textit{prd},qty),\textsf{Price}(\textit{prd},amt)\}{\color[rgb]{0.0195,0.2109,0.2539}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}{\color[rgb]{0.0195,0.2109,0.2539}\rangle} contains in particular (f,8) , where f=(\textit{pers},d,\textit{prd},qty,amt)\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\mapsto}}(\text{p1},\text{2-sept},X,4,2) . \pi_{Y}^{\oplus}~\gamma Given a commutative monoid \oplus:K\times K\to K , a K -aggregate query \gamma on X , and a set Y\subsetneq X , the expression “ \pi_{Y}^{\oplus}~\gamma ” is a K -aggregate query on Y . Given a K -annotated database (D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}) the evaluation of \pi_{Y}^{\oplus}\gamma on (D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}) is the set consisting of all pairs (f,n) such that S_{f}=\{(f^{\prime},n^{\prime})\in\gamma{\color[rgb]{0.0195,0.2109,0.2539}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}{\color[rgb]{0.0195,0.2109,0.2539}\rangle}:f^{\prime}(Y)=f(Y)\} is non-empty and n=\bigoplus\{n^{\prime}:(f^{\prime},n^{\prime})\in S_{f}\} . 10 10 10 By f^{\prime}(Y)=f(Y) we mean f(y)=f^{\prime}(y) for all y\in Y ; and by \bigoplus\{n^{\prime}:(f^{\prime},n^{\prime})\in S_{f}\} we mean the \oplus -sum with multiplicities : each n^{\prime}\in\{n^{\prime}:(f^{\prime},n^{\prime})\in S_{f}\} is \oplus -summed |\{f^{\prime}:(f^{\prime},n^{\prime})\in S_{f}\}| -times. That is, it outputs the restriction onto Y of all homomorphisms given by \gamma while \oplus -summing the annotations of the collisions. Again in Figure 1 , we have that \pi_{\varnothing}^{\max}\Join^{\!\times}\{\textsf{Sale}(\textit{pers},d,\textit{prd},qty)\}{\color[rgb]{0.0195,0.2109,0.2539}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}{\color[rgb]{0.0195,0.2109,0.2539}\rangle} is \{(\varnothing,5)\} where \varnothing is the empty assignment , while \pi_{\{\textit{pers}\}}^{\!+}\Join^{\!\times}\{\textsf{Sale}(\textit{pers},d,\textit{prd},qty)\}{\color[rgb]{0.0195,0.2109,0.2539}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}{\color[rgb]{0.0195,0.2109,0.2539}\rangle} is \{(\textit{pers}\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\mapsto}}\text{p1},10),(\textit{pers}\mathrel{{\color[rgb]{0.0195,0.2109,0.2539}\mapsto}}\text{p2},2)\} (on atomic queries the choice for the \times -product is irrelevant). We will simply write aggregate query to denote a K -aggregate query on any K . The underlying hypergraph {\color[rgb]{0.3438,0.0195,0.0273}\mathbf{G}_{\gamma}} of an aggregate query \gamma=\pi_{X_{n}}^{\oplus_{n}}\dotsb\pi_{X_{1}}^{\oplus_{1}}{\Join^{\otimes}}q is defined as {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{G}_{q}} , and its size is \immediate{\color[rgb]{0.3438,0.0195,0.0273}|}\gamma{\color[rgb]{0.3438,0.0195,0.0273}|}\mathrel{\hat{=}}{\color[rgb]{0.0195,0.2109,0.2539}|}q{\color[rgb]{0.0195,0.2109,0.2539}|}+\sum_{i\in[n]}|X_{i}| . Further, we say that a K -aggregate query \gamma is a semiring K -aggregate query if (K,\oplus_{i},\otimes) is a commutative semiring for every i . The evaluation task {\color[rgb]{0.3438,0.0195,0.0273}\textup{{Eval-}}}\mathcal{C} for a class \mathcal{C} of K -aggregate queries is the task of, given \gamma\in\mathcal{C} and a K -annotated database (D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}) , computing \gamma{\color[rgb]{0.0195,0.2109,0.2539}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\nu}{\color[rgb]{0.0195,0.2109,0.2539}\rangle} . The concepts of constant delay enumeration after a linear (or polynomial) pre-processing for \mathcal{C} are defined analogously. Basic Examples of Aggregate Queries We show here some examples of what kind of queries can be expressed via aggregate queries . Other examples can be found in . Note that all the examples are of semiring aggregate queries and hence the complexity results of this manuscript will apply to such kind of queries. In what follows we consider + , \max and \times as the operations of sum, maximum, and product of natural numbers, respectively. We will refer to (D,\immediate\immediate\immediate{\color[rgb]{0.3438,0.0195,0.0273}\mathbf{1}}) as a 1 -initialized \mathbb{N} -annotated database where {\color[rgb]{0.0195,0.2109,0.2539}\mathbf{1}} is the function that annotates each fact in the database with 1. Example 4.1 (CQ) . Any CQ q(X) can be expressed as a K -aggregate query \pi^{\max}_{X}{\Join^{\max}}q where K=\{1\} is a singleton set of annotations . Indeed, for any database D , we have that q(X){\color[rgb]{0.0195,0.2109,0.2539}\langle}D{\color[rgb]{0.0195,0.2109,0.2539}\rangle} coincides with the projection onto the first component of (\pi^{\max}_{X}{\Join^{\max}}q){\color[rgb]{0.0195,0.2109,0.2539}\langle}D,{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{1}}{\color[rgb]{0.0195,0.2109,0.2539}\rangle} . 11 11 11 Since there is only one semiring on one element, the query could be more intuitively written as \pi_{X}{\Join}q . ∎ Example 4.2 (Counting answers to CQs ) . A query of the form \pi_{\varnothing}^{+}\pi_{X}^{\max}{\Join^{\times}}q evaluated on (D,{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{1}}) outputs a pair (\varnothing,n) , where n is the number of answers to the (classical) CQ q(X) . In the literature this is often written \#q(X) . We will study this particular case in . ∎ Example 4.3 (Max group-by count) . On (D,{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{1}}) , suppose we want to compute the maximum number of inhabitants satisfying some criteria in a district, then the query \pi_{\varnothing}^{\max}\pi_{\{y\}}^{+}\pi_{\{x,y\}}^{\max}{\Join^{\!\times}}q with q of the form \{\textsf{Person}(x,\bar{w}),\textsf{PersonDistrict}(x,y),\textsf{District}(y,\bar{z}),q_{\textup{criteria}}(\bar{z},\bar{w})\} would yield the expected result. More generally, an aggregate query of the form \pi_{\varnothing}^{\max}\pi_{Y}^{+}\pi_{X}^{\max}{\Join^{\!\times}}q outputs a pair (\varnothing,n) , where n is the maximum number of answers to the (classical) CQ q(X) for every possible assignment of the variables Y\subsetneq X . ∎ 5 Project-Connex Decompositions for Aggregate Queries We generalize the definition of free-connex to aggregate queries . A tree decomposition (T,{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{b}},{\color[rgb]{0.0195,0.2109,0.2539}\mathbf{a}}) for an aggregate query \gamma=\pi_{X_{n}}^{\oplus_{n}}\dotsb\pi_{X_{1}}^{\oplus_{1}}{\Join^{\otimes}}q is project-connex if for every i\in[n] there are subtrees T_{i} such that (i) each T_{i} is a witness subtree for X_{i} and (ii) for every i