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
1794
Venue
PODS
Year
2019
Pagerank
8.5358494e-05
Overall Rank
2,468 | 83.07%
DOI
10.1145/3294052.3319700
Incoming Non-self Citations Over Time
BibTeX Citation
Copy BibTeX
@inproceedings{carmeli_pods19,
address = {New York, NY, USA},
series = {{PODS} '19},
title = {{On the Enumeration Complexity of Unions of Conjunctive Queries}},
url = {https://dl.acm.org/doi/10.1145/3294052.3319700},
doi = {10.1145/3294052.3319700},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Carmeli, Nofar and Kröll, Markus},
year = {2019}
}
Incoming Citations (Sorted by Pagerank)
Showing 19 of 19 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
2,745
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
2020
VLDB
8.1747954e-05
2,777
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
8.1352657e-05
4,575
Conjunctive Queries with Comparisons
2022
SIGMOD
6.6223692e-05
5,593
Beyond Equi-joins: Ranking, Enumeration and Factorization
2021
VLDB
6.1552328e-05
5,854
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS
6.064817e-05
6,301
Evaluating Datalog over Semirings: A Grounding-based Approach
2024
PODS
5.9213518e-05
6,434
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
2025
SIGMOD
5.8799421e-05
6,444
Output-Optimal Algorithms for Join-Aggregate Queries
2025
PODS
5.8774519e-05
7,161
Computing the Difference of Conjunctive Queries Efficiently
2023
SIGMOD
5.6852987e-05
7,574
CORE: a Complex Event Recognition Engine
2022
VLDB
5.5938402e-05
8,673
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration
2020
PODS
5.3872753e-05
9,291
Efficiently Enumerating Answers to Ontology-Mediated Queries
2022
PODS
5.2910144e-05
10,020
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
5.1757914e-05
10,154
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
5.093636e-05
10,159
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
2026
PODS
5.093636e-05
10,170
Towards Parameterized Hardness on Maintaining Conjunctive Queries
2026
PODS
5.093636e-05
10,622
Towards Efficient Random-Order Enumeration for Join Queries
2026
VLDB
5.093636e-05
10,639
Circuit Bounds for Conjunctive Queries with Self-joins
2025
PODS
5.093636e-05
11,183
Relational Algorithms for Top-k Query Evaluation
2024
SIGMOD
5.093636e-05
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 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
1
10,020
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
2
12,229
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
2013
PODS
3
636
Answering Conjunctive Queries under Updates
2017
PODS
4
9,009
Efficient Approximations of Conjunctive Queries
2012
PODS
5
1,707
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints
2015
PODS
6
4,781
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries
2021
PODS
7
10,154
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
8
11,140
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
2024
PODS
9
2,777
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
10
5,854
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS