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
h536fb820ffe66459
Venue
PODS
Year
2019
Pagerank
8.3274934e-05
Overall Rank
2,526 | 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,602
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
2020
VLDB
8.2157154e-05
2,766
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
8.0221503e-05
4,527
Conjunctive Queries with Comparisons
2022
SIGMOD
6.5466033e-05
5,506
Beyond Equi-joins: Ranking, Enumeration and Factorization
2021
VLDB
6.0883761e-05
5,911
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
2025
SIGMOD
5.9338021e-05
5,989
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS
5.9063374e-05
6,443
Evaluating Datalog over Semirings: A Grounding-based Approach
2024
PODS
5.7666211e-05
6,585
Output-Optimal Algorithms for Join-Aggregate Queries
2025
PODS
5.7238683e-05
7,311
Computing the Difference of Conjunctive Queries Efficiently
2023
SIGMOD
5.5432326e-05
7,738
CORE: a Complex Event Recognition Engine
2022
VLDB
5.4476676e-05
8,855
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration
2020
PODS
5.2486885e-05
9,505
Efficiently Enumerating Answers to Ontology-Mediated Queries
2022
PODS
5.152755e-05
10,252
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
5.0405429e-05
10,449
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
4.9605343e-05
10,454
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
2026
PODS
4.9605343e-05
10,465
Towards Parameterized Hardness on Maintaining Conjunctive Queries
2026
PODS
4.9605343e-05
11,138
Towards Efficient Random-Order Enumeration for Join Queries
2026
VLDB
4.9605343e-05
11,152
Circuit Bounds for Conjunctive Queries with Self-joins
2025
PODS
4.9605343e-05
11,581
Relational Algorithms for Top-k Query Evaluation
2024
SIGMOD
4.9605343e-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,252
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
2
12,569
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
2013
PODS
3
639
Answering Conjunctive Queries under Updates
2017
PODS
4
9,205
Efficient Approximations of Conjunctive Queries
2012
PODS
5
1,747
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints
2015
PODS
6
4,714
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries
2021
PODS
7
10,449
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
8
11,546
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
2024
PODS
9
2,766
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
10
5,989
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS