Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
Preprint
Abstract
In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). 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 (\faqneg). 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 Ackermmann function is probably unavoidable for general semirings, but can be removed when the semiring has specific structure. Finally, we show an application of our results to computing the difference of CQs.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Functional Aggregate Queries with Additive InequalitiesACM Transactions on Database Systems, 2020
- More consequences of falsifying SETH and the orthogonal vectors conjecture2018
- What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?2017
- Hypergraph Acyclicity RevisitedACM Computing Surveys, 2016
- FAQ2016
- Powers of tensors and fast matrix multiplication2014
- On the complexity of RAM with various operation sets1992
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINEInternational Journal of Computational Geometry & Applications, 1991
- On the Desirability of Acyclic Database SchemesJournal of the ACM, 1983
- On the power of multiplication in random access machines1974