Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Summary: Dichotomy (FPTRAS) for counting answers to conjunctive queries with disequalities/negations: under rETH, bounded-arity queries admit an FPTRAS iff treewidth is bounded; unbounded-arity (no negations) admit an FPTRAS iff adaptive width is bounded. No FPRAS exists unless NP=RP even for width 1, but if neither disequalities nor negations appear there is an FPRAS for queries of bounded fractional hypertreewidth, strictly generalizing STOC'21. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Jacob Focke (CISPA Helmholtz Center for Information Security)
- 2. Leslie Ann Goldberg (University of Oxford)
- 3. Marc Roth (University of Oxford)
- 4. Stanislav Živný (University of Oxford)
BibTeX Citation
@inproceedings{focke_pods22,
address = {New York, NY, USA},
series = {{PODS} '22},
title = {{Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations}},
url = {https://dl.acm.org/doi/10.1145/3517804.3526231},
doi = {10.1145/3517804.3526231},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Focke, Jacob and Goldberg, Leslie Ann and Roth, Marc and Živný, Stanislav},
year = {2022}
}
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,941 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS | 7.0074268e-05 |
| 11,140 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 414 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00018893507 |
| 4,266 | Counting Answers to Existential Positive Queries: A Complexity Classification | 2016 | PODS | 6.7936492e-05 |
| 5,773 | Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms | 2018 | PODS | 6.0926349e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,553 | On the Complexity of Approximate Query Optimization | 2002 | PODS |
| 2 | 11,140 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS |
| 3 | 11,523 | The Complexity of Conjunctive Queries with Degree 2 | 2022 | PODS |
| 4 | 636 | Answering Conjunctive Queries under Updates | 2017 | PODS |
| 5 | 644 | The Complexity of Query Reliability | 1998 | PODS |
| 6 | 9,921 | Combined Approximations for Uniform Operational Consistent Query Answering | 2024 | PODS |
| 7 | 8,241 | Counting Database Repairs Entailing a Query: The Case of Functional Dependencies | 2022 | PODS |
| 8 | 3,801 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS |
| 9 | 7,317 | Probabilistic Query Evaluation: The Combined FPRAS Landscape | 2023 | PODS |
| 10 | 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS |