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
he4be3b2c2a05e623
Venue
PODS
Year
2020
Pagerank
8.0487636e-05
Overall Rank
2,757 | 81.48%
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 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2548566e-05
3,994 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8652819e-05
4,700 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4609577e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
7,438 Efficient Computation of Quantiles over Joins 2023 PODS 5.5257365e-05
7,471 Reservoir Sampling over Joins 2024 SIGMOD 5.5172544e-05
8,219 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3745518e-05
8,285 Subset Sampling over Joins 2026 PODS 5.3612232e-05
8,837 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2661006e-05
9,420 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1802184e-05
9,477 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 5.1698497e-05
9,642 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.1445295e-05
10,383 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS 4.9769913e-05
10,853 I-Rex: An Interactive Debugger for SQL 2026 VLDB 4.9769913e-05
11,077 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9769913e-05
11,106 The Complexity of Maximal Common Subsequence Enumeration 2025 PODS 4.9769913e-05
11,494 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.9769913e-05
11,800 Approximate Queries over Concurrent Updates 2023 VLDB 4.9769913e-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