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 |
|---|---|---|---|---|
| 407 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS | 0.00024004562 |
| 772 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.00016876498 |
| 2,063 | Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability | 2014 | PODS | 9.6447857e-05 |
| 3,003 | Counting Answers to Existential Positive Queries: A Complexity Classification | 2016 | PODS | 7.7388586e-05 |
| 3,387 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 7.1573735e-05 |
| 4,977 | Constraint Satisfaction and Database Theory: a Tutorial | 2000 | PODS | 5.7881576e-05 |
| 8,992 | Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations | 2022 | PODS | 4.413099e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,157 | Extremal Fitting Problems for Conjunctive Queries | 2023 | PODS | 4.1945683e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 4,048 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS | 6.4968603e-05 |
| 7,539 | A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries | 2021 | PODS | 4.7166538e-05 |
| 772 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.00016876498 |
| 11,967 | Does Query Evaluation Tractability Help Query Containment? | 2014 | PODS | 4.1945683e-05 |
| 12,031 | The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity | 2013 | PODS | 4.1945683e-05 |
| 2,063 | Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability | 2014 | PODS | 9.6447857e-05 |
| 3,371 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1696145e-05 |