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.0525756e-05
Overall Rank
2,757 | 81.47%
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.2582926e-05
3,992 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8685334e-05
4,698 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4640177e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
7,435 Efficient Computation of Quantiles over Joins 2023 PODS 5.5283535e-05
7,467 Reservoir Sampling over Joins 2024 SIGMOD 5.5198675e-05
8,212 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3770972e-05
8,279 Subset Sampling over Joins 2026 PODS 5.3637624e-05
8,828 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2685945e-05
9,410 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1826718e-05
9,466 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 5.1722982e-05
9,634 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.146966e-05
10,371 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS 4.9793485e-05
10,843 I-Rex: An Interactive Debugger for SQL 2026 VLDB 4.9793485e-05
11,068 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9793485e-05
11,097 The Complexity of Maximal Common Subsequence Enumeration 2025 PODS 4.9793485e-05
11,488 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.9793485e-05
11,794 Approximate Queries over Concurrent Updates 2023 VLDB 4.9793485e-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