{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:16:27Z","timestamp":1778807787073,"version":"3.51.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T00:00:00Z","timestamp":1736467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council","award":["850979"],"award-info":[{"award-number":["850979"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-19-P3IA-0001, ANR-19-CE48-0019"],"award-info":[{"award-number":["ANR-19-P3IA-0001, ANR-19-CE48-0019"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomy showed for which queries and orders this task can be done in polylogarithmic access time after quasilinear preprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard. We determine the preprocessing time needed to achieve polylogarithmic access time for all join queries and all lexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access on join queries. We then explore its optimality by proving lower bounds for the preprocessing time based on the hardness of a certain online Set-Disjointness problem, which shows that our algorithm\u2019s bounds are tight for all lexicographic orders on join queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture, which is an established conjecture from fine-grained complexity theory. Interestingly, while proving our lower bound, we show that self-joins do not affect the complexity of direct access (up to logarithmic factors). Our algorithm can also be used to solve queries with projections and relaxed order requirements, though in these cases, its running time is not necessarily optimal. We also show that similar techniques to those used in our lower bounds can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing. This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of self-join-free cyclic joins with respect to linear preprocessing and constant delay.<\/jats:p>","DOI":"10.1145\/3707448","type":"journal-article","created":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T11:06:21Z","timestamp":1733483181000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Fine-Grained Bounds for Direct Access on Join Queries"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1356-5177","authenticated-orcid":false,"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[{"name":"Saarland University, Saarbrucken, Germany and Max Planck Institute for Informatics, Saarbrucken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"additional","affiliation":[{"name":"Inria, LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1386-8784","authenticated-orcid":false,"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[{"name":"Univ. Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), Lens, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,1,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/3188745.3188938","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201918)","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. 2018. More consequences of falsifying SETH and the orthogonal vectors conjecture. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201918), Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.). ACM, 253\u2013266. DOI:10.1145\/3188745.3188938"},{"key":"e_1_3_2_3_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-662-43948-7_4","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. 2014. Consequences of faster alignment of sequences. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)(Lecture Notes in Computer Science, Vol. 8572), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.). Springer, 39\u201351. DOI:10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_4_2","volume-title":"Foundations of Databases","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. Retrieved from http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2902251.2902280","volume-title":"Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201916)","author":"Khamis Mahmoud Abo","year":"2016","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. 2016. FAQ: Questions asked frequently. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201916). Association for Computing Machinery, New York, NY, USA, 13\u201328. DOI:10.1145\/2902251.2902280"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_2_8_2","series-title":"LIPIcs","first-page":"81:1\u201381:13","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Backurs Arturs","year":"2016","unstructured":"Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. 2016. Tight hardness results for maximum weight rectangles. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)(LIPIcs, Vol. 55), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 81:1\u201381:13. DOI:10.4230\/LIPIcs.ICALP.2016.81"},{"key":"e_1_3_2_9_2","series-title":"Proceedings of Machine Learning Research","first-page":"311","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)","author":"Backurs Arturs","year":"2017","unstructured":"Arturs Backurs and Christos Tzamos. 2017. Improving Viterbi is hard: Better runtimes imply faster clique algorithms. In Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)(Proceedings of Machine Learning Research, Vol. 70.), Doina Precup and Yee Whye Teh (Eds.). PMLR, 311\u2013321. Retrieved from http:\/\/proceedings.mlr.press\/v70\/backurs17a.html"},{"key":"e_1_3_2_10_2","volume-title":"Algorithmes et Complexit\u00e9 Des Probl\u00e8mes D\u2019\u00e9num\u00e9ration pour l\u2019\u00e9valuation de requ\u00eates Logiques. (Algorithms and Complexity of Enumeration Problems for the Evaluation of Logical Queries)","author":"Bagan Guillaume","year":"2009","unstructured":"Guillaume Bagan. 2009. Algorithmes et Complexit\u00e9 Des Probl\u00e8mes D\u2019\u00e9num\u00e9ration pour l\u2019\u00e9valuation de requ\u00eates Logiques. (Algorithms and Complexity of Enumeration Problems for the Evaluation of Logical Queries). Ph.D. Dissertation. University of Caen, Normandy, France. Retrieved from https:\/\/tel.archives-ouvertes.fr\/tel-00424232"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2007046"},{"issue":"1","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/3385634.3385636","article-title":"Constant delay enumeration for conjunctive queries: A tutorial","volume":"7","author":"Berkholz Christoph","year":"2020","unstructured":"Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. 2020. Constant delay enumeration for conjunctive queries: A tutorial. ACM SIGLOG News 7, 1 (2020), 4\u201333.","journal-title":"ACM SIGLOG News"},{"key":"e_1_3_2_13_2","series-title":"LIPIcs","first-page":"58:1\u201358:15","volume-title":"Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919)","author":"Berkholz Christoph","year":"2019","unstructured":"Christoph Berkholz and Nicole Schweikardt. 2019. Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919)(LIPIcs, Vol. 138), Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 58:1\u201358:15. DOI:10.4230\/LIPIcs.MFCS.2019.58"},{"key":"e_1_3_2_14_2","volume-title":"De la Pertinence de l\u2019\u00e9num\u00e9ration: Complexit\u00e9 en Logiques Propositionnelle et du Premier Ordre","author":"Brault-Baron Johann","year":"2013","unstructured":"Johann Brault-Baron. 2013. De la Pertinence de l\u2019\u00e9num\u00e9ration: Complexit\u00e9 en Logiques Propositionnelle et du Premier Ordre. Ph.D. Dissertation. Universit\u00e9 de Caen, Normandy, France."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1145\/3517804.3526234","volume-title":"Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201922)","author":"Bringmann Karl","year":"2022","unstructured":"Karl Bringmann, Nofar Carmeli, and Stefan Mengel. 2022. Tight fine-grained bounds for direct access on join queries. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201922). Association for Computing Machinery, New York, NY, USA, 427\u2013436. DOI:10.1145\/3517804.3526234"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381878"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/3584372.3588667","volume-title":"Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201923)","author":"Carmeli Nofar","year":"2023","unstructured":"Nofar Carmeli and Luc Segoufin. 2023. Conjunctive queries with self-joins, towards a fine-grained enumeration complexity analysis. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201923). Association for Computing Machinery, New York, NY, USA, 277\u2013289. DOI:10.1145\/3584372.3588667"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1145\/3452021.3458331","volume-title":"Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Carmeli Nofar","year":"2021","unstructured":"Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. 2021. Tractable orders for direct access to ranked answers of conjunctive queries. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 325\u2013341."},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1145\/3375395.3387662","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Carmeli Nofar","year":"2020","unstructured":"Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt. 2020. Answering (unions of) conjunctive queries using random access and random-order enumeration. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 393\u2013409."},{"key":"e_1_3_2_21_2","series-title":"LIPIcs","first-page":"110","volume-title":"Proceedings of the 18th International Conference on Database Theory (ICDT\u201915)","author":"Chen Hubie","year":"2015","unstructured":"Hubie Chen and Stefan Mengel. 2015. A trichotomy in the complexity of counting answers to conjunctive queries. In Proceedings of the 18th International Conference on Database Theory (ICDT\u201915)(LIPIcs, Vol. 31),Marcelo Arenas and Mart\u00edn Ugarte (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 110\u2013126. DOI:10.4230\/LIPIcs.ICDT.2015.110"},{"key":"e_1_3_2_22_2","volume-title":"Introduction to Algorithms, 3rd Edition","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press. Retrieved from http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.08.001"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3457374"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.18452\/21483"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/3034786.3056105","volume-title":"Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201917)","author":"Khamis Mahmoud Abo","year":"2017","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. 2017. What do Shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS\u201917), Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts (Eds.). ACM, 429\u2013444. DOI:10.1145\/3034786.3056105"},{"key":"e_1_3_2_30_2","first-page":"1272","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Kopelowitz Tsvi","year":"2016","unstructured":"Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 2016. Higher lower bounds from the 3SUM conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916), Robert Krauthgamer (Ed.). SIAM, 1272\u20131287. DOI:10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_2_31_2","first-page":"1236","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Lincoln Andrea","year":"2018","unstructured":"Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. 2018. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918), Artur Czumaj (Ed.). SIAM, 1236\u20131252. DOI:10.1137\/1.9781611975031.80"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_3_2_33_2","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press."},{"key":"e_1_3_2_34_2","first-page":"37","volume-title":"Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201912)","author":"Ngo Hung Q.","year":"2012","unstructured":"Hung Q. Ngo, Ely Porat, Christopher R\u00e9, and Atri Rudra. 2012. Worst-case optimal join algorithms: [Extended abstract]. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201912), Michael Benedikt, Markus Kr\u00f6tzsch, and Maurizio Lenzerini (Eds.). ACM, 37\u201348. DOI:10.1145\/2213556.2213565"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_3_2_36_2","series-title":"CEUR Workshop Proceedings","volume-title":"Proceedings of the 26th Italian Symposium on Advanced Database Systems","author":"Scarcello Francesco","year":"2018","unstructured":"Francesco Scarcello. 2018. From hypertree width to submodular width and data-dependent structural decompositions. In Proceedings of the 26th Italian Symposium on Advanced Database Systems(CEUR Workshop Proceedings, Vol. 2161), Sonia Bergamaschi, Tommaso Di Noia, and Andrea Maurino (Eds.). CEUR-WS.org. Retrieved from http:\/\/ceur-ws.org\/Vol-2161\/paper24.pdf"},{"key":"e_1_3_2_37_2","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer."},{"key":"e_1_3_2_38_2","first-page":"96","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT\u201914)","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT\u201914), Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceedings.org, 96\u2013106. DOI:10.5441\/002\/icdt.2014.13"},{"key":"e_1_3_2_39_2","first-page":"3447","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians. World Scientific, 3447\u20133487."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_42_2","first-page":"786","volume-title":"Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Williams Virginia Vassilevska","year":"2020","unstructured":"Virginia Vassilevska Williams and Yinzhan Xu. 2020. Monochromatic triangles, triangle listing and APSP. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920), Sandy Irani (Ed.). IEEE, 786\u2013797. DOI:10.1109\/FOCS46700.2020.00078"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707448","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3707448","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:38Z","timestamp":1750295858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707448"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,10]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3707448"],"URL":"https:\/\/doi.org\/10.1145\/3707448","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,10]]},"assertion":[{"value":"2023-01-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}