DBScholar

Back to papers

Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration

Summary: Free-connex acyclic CQs admit linear preprocessing with polylog-delay enumeration, true random-order enumeration, and polylog random-access, while other CQs (no self-joins) are intractable under fine-grained assumptions. For UCQs the yardsticks separate: unions of free-connex acyclic CQs may be enumerable but lack random-access; paper gives an expected-log-delay random-order enumeration, a UCQ subclass with polylog random-access, and an implementation showing practical gains. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1825
Venue
PODS
Year
2020
Pagerank
8.1352657e-05
Overall Rank
2,777 | 80.95%
DOI
10.1145/3375395.3387662

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{carmeli_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387662},
        doi = {10.1145/3375395.3387662},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Carmeli, Nofar and Zeevi, Shai and Berkholz, Christoph and Kimelfeld, Benny and Schweikardt, Nicole},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
3,453 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.4004131e-05
3,941 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 7.0074268e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
7,286 Efficient Computation of Quantiles over Joins 2023 PODS 5.655242e-05
7,335 Reservoir Sampling over Joins 2024 SIGMOD 5.64193e-05
8,047 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.500514e-05
8,673 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.3872753e-05
9,235 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.3016261e-05
9,291 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 5.2910144e-05
9,512 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.2571354e-05
9,719 Subset Sampling over Joins 2026 PODS 5.2319816e-05
10,154 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS 5.093636e-05
10,622 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 5.093636e-05
10,654 The Complexity of Maximal Common Subsequence Enumeration 2025 PODS 5.093636e-05
11,140 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 5.093636e-05
11,484 Approximate Queries over Concurrent Updates 2023 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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