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.3589894e-05
Overall Rank
2,517 | 83.08%
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,591
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries
2020
VLDB
8.2468757e-05
2,757
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
8.0525756e-05
4,509
Conjunctive Queries with Comparisons
2022
SIGMOD
6.570408e-05
5,482
Beyond Equi-joins: Ranking, Enumeration and Factorization
2021
VLDB
6.111411e-05
5,902
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
2025
SIGMOD
5.9536872e-05
5,978
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS
5.9287388e-05
6,429
Evaluating Datalog over Semirings: A Grounding-based Approach
2024
PODS
5.7884926e-05
6,573
Output-Optimal Algorithms for Join-Aggregate Queries
2025
PODS
5.7455776e-05
7,292
Computing the Difference of Conjunctive Queries Efficiently
2023
SIGMOD
5.5642569e-05
7,717
CORE: a Complex Event Recognition Engine
2022
VLDB
5.4683294e-05
8,828
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration
2020
PODS
5.2685945e-05
9,466
Efficiently Enumerating Answers to Ontology-Mediated Queries
2022
PODS
5.1722982e-05
10,209
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
5.0596605e-05
10,371
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
4.9793485e-05
10,376
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
2026
PODS
4.9793485e-05
10,387
Towards Parameterized Hardness on Maintaining Conjunctive Queries
2026
PODS
4.9793485e-05
11,068
Towards Efficient Random-Order Enumeration for Join Queries
2026
VLDB
4.9793485e-05
11,082
Circuit Bounds for Conjunctive Queries with Self-joins
2025
PODS
4.9793485e-05
11,526
Relational Algorithms for Top-k Query Evaluation
2024
SIGMOD
4.9793485e-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,209
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
2024
PODS
2
12,520
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
2013
PODS
3
637
Answering Conjunctive Queries under Updates
2017
PODS
4
9,169
Efficient Approximations of Conjunctive Queries
2012
PODS
5
1,735
The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints
2015
PODS
6
4,698
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries
2021
PODS
7
10,371
Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
2026
PODS
8
11,488
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
2024
PODS
9
2,757
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
2020
PODS
10
5,978
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
2023
PODS