Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
Open Access
- 27 March 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 51 (3) , 1-42
Abstract
In this article, we study the complexity of evaluating Conjunctive Queries with negation ( \(\mathsf {CQ}^{\lnot }\) ). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation ( \(\mathsf {FAQ}^{\lnot }\) ). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.
Keywords
This publication has 12 references indexed in Scilit:
- Computing the Difference of Conjunctive Queries EfficientlyProceedings of the ACM on Management of Data, 2023
- On the Enumeration Complexity of Unions of Conjunctive QueriesACM Transactions on Database Systems, 2021
- Functional Aggregate Queries with Additive InequalitiesACM Transactions on Database Systems, 2020
- Constant delay enumeration for conjunctive queriesACM SIGLOG News, 2020
- What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?2017
- Hypergraph Acyclicity RevisitedACM Computing Surveys, 2016
- FAQ2016
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINEInternational Journal of Computational Geometry & Applications, 1991
- Computing partial sums in multidimensional arrays1989
- A unifying look at data structuresCommunications of the ACM, 1980