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.0221503e-05
Overall Rank
2,766 | 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,502 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2308675e-05
4,011 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.842581e-05
4,714 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4395938e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
7,459 Efficient Computation of Quantiles over Joins 2023 PODS 5.507465e-05
7,490 Reservoir Sampling over Joins 2024 SIGMOD 5.499011e-05
8,238 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3567801e-05
8,300 Subset Sampling over Joins 2026 PODS 5.3434957e-05
8,855 Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration 2020 PODS 5.2486885e-05
9,445 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1630894e-05
9,505 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 5.152755e-05
9,669 Poisson Sampling over Acyclic Joins 2026 SIGMOD 5.1275185e-05
10,449 Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum 2026 PODS 4.9605343e-05
10,914 I-Rex: An Interactive Debugger for SQL 2026 VLDB 4.9605343e-05
11,138 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9605343e-05
11,167 The Complexity of Maximal Common Subsequence Enumeration 2025 PODS 4.9605343e-05
11,546 Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity 2024 PODS 4.9605343e-05
11,844 Approximate Queries over Concurrent Updates 2023 VLDB 4.9605343e-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