Tight Fine-Grained Bounds for Direct Access on Join Queries
Summary: Decomposition-based algorithm that achieves the minimal preprocessing needed to support polylogarithmic lexicographic direct access for every self-join-free query and lexicographic order. Matching lower bounds via online Set-Disjointness reductions from the Zero-Clique conjecture, with consequences ruling out subtrivial preprocessing for Loomis–Whitney and supporting enumeration hardness for cyclic self-join-free joins. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Karl Bringmann (Max Planck Institute; Saarland University)
- 2. Nofar Carmeli (CNRS; INRIA; PSL University (Paris Sciences et Lettres); École Normale Supérieure)
- 3. Stefan Mengel (CNRS; Centre de Recherche en Informatique de Lens (CRIL); University of Artois)
BibTeX Citation
@inproceedings{bringmann_pods22,
address = {New York, NY, USA},
series = {{PODS} '22},
title = {{Tight Fine-Grained Bounds for Direct Access on Join Queries}},
url = {https://dl.acm.org/doi/10.1145/3517804.3526234},
doi = {10.1145/3517804.3526234},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Bringmann, Karl and Carmeli, Nofar and Mengel, Stefan},
year = {2022}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,904 | Tight Bounds of Circuits for Sum-Product Queries | 2024 | PODS | 5.5181056e-05 |
| 9,183 | Extending SQL to Return a Subdatabase | 2025 | SIGMOD | 5.3058708e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS | 0.00021283186 |
| 411 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00018902089 |
| 2,777 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 8.1352657e-05 |
| 4,781 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS | 6.5116536e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,593 | Beyond Equi-joins: Ranking, Enumeration and Factorization | 2021 | VLDB |
| 2 | 636 | Answering Conjunctive Queries under Updates | 2017 | PODS |
| 3 | 411 | Worst-case Optimal Join Algorithms | 2012 | PODS |
| 4 | 7,286 | Efficient Computation of Quantiles over Joins | 2023 | PODS |
| 5 | 9,845 | Towards Update-Dependent Analysis of Query Maintenance | 2025 | PODS |
| 6 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 7 | 4,781 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS |
| 8 | 10,170 | Towards Parameterized Hardness on Maintaining Conjunctive Queries | 2026 | PODS |
| 9 | 5,854 | Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis | 2023 | PODS |
| 10 | 10,154 | Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum | 2026 | PODS |