Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
Summary: Natural tractability criterion: #UCQ(C) is FPT iff the combined CQ(s) of C and their contracts have bounded treewidth. Closure on C needed; even for a single UCQ, meta-decision NP-hard; exponential-time algorithm optimal; WL-dimension of a UCQ NP-hard. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Jacob Focke
- 2. Leslie Ann Goldberg
- 3. Marc Roth
- 4. Stanislav Živný
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 401 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS | 0.00024281448 |
| 770 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.0001686092 |
| 2,057 | Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability | 2014 | PODS | 9.665853e-05 |
| 3,005 | Counting Answers to Existential Positive Queries: A Complexity Classification | 2016 | PODS | 7.7315492e-05 |
| 3,386 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 7.151562e-05 |
| 4,978 | Constraint Satisfaction and Database Theory: a Tutorial | 2000 | PODS | 5.7833452e-05 |
| 8,994 | Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations | 2022 | PODS | 4.4094348e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,160 | Extremal Fitting Problems for Conjunctive Queries | 2023 | PODS | 4.1905499e-05 |
| 8,850 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4324268e-05 |
| 6,945 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8874695e-05 |
| 4,055 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4906839e-05 |
| 7,538 | A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries | 2021 | PODS | 4.7121279e-05 |
| 770 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.0001686092 |
| 11,975 | Does Query Evaluation Tractability Help Query Containment? | 2014 | PODS | 4.1905499e-05 |
| 12,039 | The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity | 2013 | PODS | 4.1905499e-05 |
| 2,057 | Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability | 2014 | PODS | 9.665853e-05 |
| 3,374 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1631303e-05 |