DBScholar

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

Authors

BibTeX Citation

@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
Previous Page 1 / 1 Next

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.

Previous Page 1 / 1 Next

Semantically Similar Papers