Back to papers
On the Enumeration Complexity of Unions of Conjunctive Queries
Summary: Generalizes free-connexity to UCQs and characterizes when UCQs admit linear preprocessing and constant‑delay enumeration, showing some unions—even of intractable CQs—can be tractable. For several query classes free‑connexity exactly captures tractability; full classification open.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1762
- Venue
- PODS
- Year
- 2019
- Pagerank
- 7.1696145e-05
- Overall Rank
- 3,371 | 76.55%
- DOI
-
10.1145/3294052.3319700
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 16 of 16 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 3,387 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.1573735e-05 |
| 3,715 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8220943e-05 |
| 5,718 |
Conjunctive Queries with Comparisons |
2022 |
SIGMOD |
5.3552123e-05 |
| 5,962 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2536266e-05 |
| 5,992 |
Evaluating Datalog over Semirings: A Grounding-based Approach |
2024 |
PODS |
5.2415551e-05 |
| 6,728 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9483326e-05 |
| 7,162 |
Computing the Difference of Conjunctive Queries Efficiently |
2023 |
SIGMOD |
4.8132423e-05 |
| 7,467 |
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees |
2025 |
SIGMOD |
4.7218691e-05 |
| 7,695 |
CORE: a Complex Event Recognition Engine |
2022 |
VLDB |
4.6757592e-05 |
| 8,589 |
Output-Optimal Algorithms for Join-Aggregate Queries |
2025 |
PODS |
4.4897014e-05 |
| 8,652 |
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration |
2020 |
PODS |
4.4753042e-05 |
| 8,995 |
Efficiently Enumerating Answers to Ontology-Mediated Queries |
2022 |
PODS |
4.412512e-05 |
| 10,324 |
Towards Efficient Random-Order Enumeration for Join Queries |
2026 |
VLDB |
4.1945683e-05 |
| 10,343 |
Circuit Bounds for Conjunctive Queries with Self-joins |
2025 |
PODS |
4.1945683e-05 |
| 10,898 |
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization |
2024 |
PODS |
4.1945683e-05 |
| 10,970 |
Relational Algorithms for Top-k Query Evaluation |
2024 |
SIGMOD |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,715 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8220943e-05 |
| 10,898 |
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization |
2024 |
PODS |
4.1945683e-05 |
| 12,031 |
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity |
2013 |
PODS |
4.1945683e-05 |
| 772 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.00016876498 |
| 8,851 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4363908e-05 |
| 2,243 |
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints |
2015 |
PODS |
9.2166927e-05 |
| 5,858 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2997454e-05 |
| 10,919 |
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity |
2024 |
PODS |
4.1945683e-05 |
| 3,387 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.1573735e-05 |
| 6,728 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9483326e-05 |