{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:12:03Z","timestamp":1779174723086,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["412400621; 414325841"],"award-info":[{"award-number":["412400621; 414325841"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-19-P3IA-0001"],"award-info":[{"award-number":["ANR-19-P3IA-0001"]}],"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":[[2022,9,30]]},"abstract":"<jats:p>As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tractability yardstick of answer enumeration with a polylogarithmic delay after a linear-time preprocessing phase. Such an evaluation is obtained by constructing, in the preprocessing phase, a data structure that supports polylogarithmic-delay enumeration. In this article, we seek a structure that supports the more demanding task of a \u201crandom permutation\u201d: polylogarithmic-delay enumeration in truly random order. Enumeration of this kind is required if downstream applications assume that the intermediate results are representative of the whole result set in a statistically meaningful manner. An even more demanding task is that of \u201crandom access\u201d: polylogarithmic-time retrieval of an answer whose position is given.<\/jats:p><jats:p>We establish that the free-connex acyclic CQs are tractable in all three senses: enumeration, random-order enumeration, and random access; and in the absence of self-joins, it follows from past results that every other CQ is intractable by each of the three (under some fine-grained complexity assumptions). However, the three yardsticks are separated in the case of a<jats:bold>union of CQs (UCQ<\/jats:bold>): while a union of free-connex acyclic CQs has a tractable enumeration, it may (provably) admit no random access. We identify a fragment of such UCQs where we can guarantee random access with polylogarithmic access time (and linear-time preprocessing) and a more general fragment where we can guarantee tractable random permutation. For general unions of free-connex acyclic CQs, we devise two algorithms with relaxed guarantees: one has logarithmic delay in expectation, and the other provides a permutation that is almost uniformly distributed. Finally, we present an implementation and an empirical study that show a considerable practical superiority of our random-order enumeration approach over state-of-the-art alternatives.<\/jats:p>","DOI":"10.1145\/3531055","type":"journal-article","created":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T09:36:36Z","timestamp":1656149796000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"first","affiliation":[{"name":"Technion, Israel and DI ENS, ENS, Universit\u00e9 PSL, CNRS, Inria, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8480-1731","authenticated-orcid":false,"given":"Shai","family":"Zeevi","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3554-517X","authenticated-orcid":false,"given":"Christoph","family":"Berkholz","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin-Adlershof, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0770-2235","authenticated-orcid":false,"given":"Alessio","family":"Conte","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7156-1572","authenticated-orcid":false,"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5705-1675","authenticated-orcid":false,"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin-Adlershof, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1145\/304182.304207","volume-title":"SIGMOD","author":"Acharya Swarup","year":"1999","unstructured":"Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, and Sridhar Ramaswamy. 1999. Join synopses for approximate query answering. In SIGMOD. ACM Press, 275\u2013286."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_3_7_2","first-page":"208","volume-title":"CSL","author":"Bagan Guillaume","year":"2007","unstructured":"Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In CSL. Springer, 208\u2013222."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_3_3_9_2","first-page":"1","volume-title":"ICDT","author":"Berkholz Christoph","year":"2018","unstructured":"Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under updates and in the presence of integrity constraints. In ICDT. 1\u201319."},{"key":"e_1_3_3_10_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."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.06.038"},{"key":"e_1_3_3_13_2","first-page":"1","article-title":"Enumeration complexity of conjunctive queries with functional dependencies","author":"Carmeli Nofar","year":"2019","unstructured":"Nofar Carmeli and Markus Kr\u00f6ll. 2019. Enumeration complexity of conjunctive queries with functional dependencies. Theory of Computing Systems (2019), 1\u201333.","journal-title":"Theory of Computing Systems"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319700"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458331"},{"key":"e_1_3_3_16_2","first-page":"393","volume-title":"PODS","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 PODS. ACM, 393\u2013409."},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/304182.304206","volume-title":"SIGMOD","author":"Chaudhuri Surajit","year":"1999","unstructured":"Surajit Chaudhuri, Rajeev Motwani, and Vivek R. Narasayya. 1999. On random sampling over joins. In SIGMOD. ACM Press, 263\u2013274."},{"key":"e_1_3_3_18_2","volume-title":"23rd International Conference on Database Theory (ICDT 2020)","author":"Chen Yu","year":"2020","unstructured":"Yu Chen and Ke Yi. 2020. Random sampling and size estimation over cyclic joins. In 23rd International Conference on Database Theory (ICDT 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.7"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_3_3_21_2","article-title":"Ranked enumeration of conjunctive query results","volume":"1902","author":"Deep Shaleen","year":"2019","unstructured":"Shaleen Deep and Paraschos Koutris. 2019. Ranked enumeration of conjunctive query results. CoRR abs\/1902.02698 (2019).","journal-title":"CoRR"},{"key":"e_1_3_3_22_2","first-page":"189","volume-title":"CSL (LIPIcs)","author":"Durand Arnaud","year":"2011","unstructured":"Arnaud Durand and Yann Strozecki. 2011. Enumeration complexity of logical query problems with second-order variables. In CSL (LIPIcs), Vol. 12. 189\u2013202."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/364520.364540"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/304182.304208","volume-title":"SIGMOD","author":"Haas Peter J.","year":"1999","unstructured":"Peter J. Haas and Joseph M. Hellerstein. 1999. Ripple joins for online aggregation. In SIGMOD. ACM Press, 287\u2013298."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375661"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3277006.3277009"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_3_3_33_2","first-page":"1236","volume-title":"Proc. SODA","author":"Lincoln Andrea","year":"2018","unstructured":"Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. 2018. Tight hardness for shortest cycles and paths in sparse graphs. In Proc. SODA. SIAM, 1236\u20131252."},{"key":"e_1_3_3_34_2","volume-title":"Algorithms from P to NP: Volume 1: Design & Efficiency","author":"Moret Bernard M. E.","year":"1991","unstructured":"Bernard M. E. Moret and Henry D. Shapiro. 1991. Algorithms from P to NP: Volume 1: Design & Efficiency. Benjamin-Cummings."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/502512.502568","volume-title":"KDD","author":"Street W. Nick","year":"2001","unstructured":"W. Nick Street and YongSeog Kim. 2001. A streaming ensemble algorithm (SEA) for large-scale classification. In KDD. ACM, 377\u2013382."},{"key":"e_1_3_3_38_2","article-title":"Optimal algorithms for ranked enumeration of answers to full conjunctive queries","volume":"1911","author":"Tziavelis Nikolaos","year":"2019","unstructured":"Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2019. Optimal algorithms for ranked enumeration of answers to full conjunctive queries. CoRR abs\/1911.05582 (2019).","journal-title":"CoRR"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_3_41_2","first-page":"82","volume-title":"VLDB (VLDB \u201981)","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB (VLDB \u201981). VLDB Endowment, 82\u201394. http:\/\/dl.acm.org\/citation.cfm?id=1286831.1286840."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077466"},{"key":"e_1_3_3_43_2","first-page":"1525","volume-title":"SIGMOD","author":"Zhao Zhuoyue","year":"2018","unstructured":"Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018. Random sampling over joins revisited. In SIGMOD. ACM, 1525\u20131539."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531055","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:27Z","timestamp":1750186827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3531055"],"URL":"https:\/\/doi.org\/10.1145\/3531055","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,18]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}