Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Open Access
- 30 November 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (1) , 1-29
Abstract
We study the complexity of approximating the number of answers to a small query \(\varphi\) in a large database \(\mathcal{D}\) . We establish an exhaustive classification into tractable and intractable cases if \(\varphi\) is a conjunctive query possibly including disequalities and negations: — If there is a constant bound on the arity of \(\varphi\) , and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of \(\varphi\) is bounded. — If the arity is unbounded and \(\varphi\) does not have negations, then the problem has an FPTRAS if and only if the adaptive width of \(\varphi\) (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well. Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless \(\mathrm{NP}=\mathrm{RP}\) , there is no FPRAS even if the treewidth (and the adaptive width) is \(1\) . However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).
Keywords
All Related Versions
Funding Information
- European Research Council (714532, 725978)
This publication has 31 references indexed in Scilit:
- Parameterized Counting of Partially Injective HomomorphismsAlgorithmica, 2021
- Answering Conjunctive Queries with InequalitiesTheory of Computing Systems, 2016
- Structural Tractability of Counting of Solutions to Conjunctive QueriesTheory of Computing Systems, 2014
- Fundamentals of Parameterized Complexity2013
- Query Languages for Data Exchange: Beyond Unions of Conjunctive QueriesTheory of Computing Systems, 2010
- Tractable Structures for Constraint Satisfaction with Truth TablesTheory of Computing Systems, 2009
- The Relative Complexity of Approximate Counting ProblemsAlgorithmica, 2003
- Hypertree Decompositions and Tractable QueriesJournal of Computer and System Sciences, 2002
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- On the Complexity of Database QueriesJournal of Computer and System Sciences, 1999