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.1631303e-05
- Overall Rank
- 3,374 | 76.56%
- 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,386 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.151562e-05 |
| 3,702 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8251643e-05 |
| 5,728 |
Conjunctive Queries with Comparisons |
2022 |
SIGMOD |
5.350072e-05 |
| 5,963 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2485815e-05 |
| 5,996 |
Evaluating Datalog over Semirings: A Grounding-based Approach |
2024 |
PODS |
5.2365238e-05 |
| 6,732 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9435849e-05 |
| 7,161 |
Computing the Difference of Conjunctive Queries Efficiently |
2023 |
SIGMOD |
4.8086254e-05 |
| 7,465 |
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees |
2025 |
SIGMOD |
4.7186055e-05 |
| 7,679 |
CORE: a Complex Event Recognition Engine |
2022 |
VLDB |
4.676558e-05 |
| 8,587 |
Output-Optimal Algorithms for Join-Aggregate Queries |
2025 |
PODS |
4.4853975e-05 |
| 8,650 |
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration |
2020 |
PODS |
4.4710131e-05 |
| 9,001 |
Efficiently Enumerating Answers to Ontology-Mediated Queries |
2022 |
PODS |
4.4082817e-05 |
| 10,336 |
Towards Efficient Random-Order Enumeration for Join Queries |
2026 |
VLDB |
4.1905499e-05 |
| 10,355 |
Circuit Bounds for Conjunctive Queries with Self-joins |
2025 |
PODS |
4.1905499e-05 |
| 10,902 |
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization |
2024 |
PODS |
4.1905499e-05 |
| 10,973 |
Relational Algorithms for Top-k Query Evaluation |
2024 |
SIGMOD |
4.1905499e-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,702 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8251643e-05 |
| 10,902 |
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization |
2024 |
PODS |
4.1905499e-05 |
| 12,039 |
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity |
2013 |
PODS |
4.1905499e-05 |
| 770 |
Answering Conjunctive Queries under Updates |
2017 |
PODS |
0.0001686092 |
| 8,850 |
Efficient Approximations of Conjunctive Queries |
2012 |
PODS |
4.4324268e-05 |
| 2,246 |
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints |
2015 |
PODS |
9.2039096e-05 |
| 5,859 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2963939e-05 |
| 10,923 |
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity |
2024 |
PODS |
4.1905499e-05 |
| 3,386 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.151562e-05 |
| 6,732 |
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis |
2023 |
PODS |
4.9435849e-05 |