{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T11:26:11Z","timestamp":1764588371936,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:00:00Z","timestamp":1678665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google PhD Fellowships"},{"name":"German Research Foundation (DFG) Project","award":["412400621"],"award-info":[{"award-number":["412400621"]}]},{"name":"National Science Foundation","award":["IIS-1956096, CAREER IIS-1762268"],"award-info":[{"award-number":["IIS-1956096, CAREER IIS-1762268"]}]},{"name":"French government under management of Agence Nationale de la Recherche as part of the \u201cInvestissements d\u2019avenir\u201d program","award":["ANR-19-P3IA-0001"],"award-info":[{"award-number":["ANR-19-P3IA-0001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>\n            We study the question of when we can provide\n            <jats:italic>direct access to the k-th answer<\/jats:italic>\n            to a Conjunctive Query (CQ) according to a specified order over the answers in time logarithmic in the size of the database, following a preprocessing step that constructs a data structure in time quasilinear in database size. Specifically, we embark on the challenge of identifying\n            <jats:italic>the tractable answer orderings<\/jats:italic>\n            , that is, those orders that allow for such complexity guarantees. To better understand the computational challenge at hand, we also investigate the more modest task of providing access to only a single answer (i.e., finding the answer at a given position), a task that we refer to as\n            <jats:italic>the selection problem<\/jats:italic>\n            , and ask when it can be performed in quasilinear time. We also explore the question of when selection is indeed easier than ranked direct access.\n          <\/jats:p>\n          <jats:p\/>\n          <jats:p>\n            We begin with\n            <jats:italic>lexicographic orders<\/jats:italic>\n            . For each of the two problems, we give a decidable characterization (under conventional complexity assumptions) of the class of tractable lexicographic orders for every CQ without self-joins. We then continue to the more general\n            <jats:italic>orders by the sum of attribute weights<\/jats:italic>\n            and establish the corresponding decidable characterizations, for each of the two problems, of the tractable CQs without self-joins. Finally, we explore the question of when the satisfaction of Functional Dependencies (FDs) can be utilized for tractability and establish the corresponding generalizations of our characterizations for every set of unary FDs.\n          <\/jats:p>","DOI":"10.1145\/3578517","type":"journal-article","created":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T12:50:54Z","timestamp":1672663854000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries"],"prefix":"10.1145","volume":"48","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, CNRS, PSL University, Inria, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8342-2177","authenticated-orcid":false,"given":"Nikolaos","family":"Tziavelis","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9614-0504","authenticated-orcid":false,"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7156-1572","authenticated-orcid":false,"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6102-7472","authenticated-orcid":false,"given":"Mirek","family":"Riedewald","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,3,13]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059515"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2007046"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_36"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.20"},{"key":"e_1_3_4_12_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. U. de Caen. Retrieved from: https:\/\/hal.archives-ouvertes.fr\/tel-01081392."},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09937-9"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458331"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387662"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.5"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3389130"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313772"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1030"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213002"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850592"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735494"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0434-5"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/C2013-0-10739-8"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02127798"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/b104891"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207013"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.18452\/21483"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213584"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_3_4_35_2","article-title":"A short note on the counting complexity of conjunctive queries","volume":"2112","author":"Mengel Stefan","year":"2021","unstructured":"Stefan Mengel. 2021. A short note on the counting complexity of conjunctive queries. CoRR abs\/2112.01108 (2021).","journal-title":"CoRR"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90123-1"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.86"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3383132"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476306"},{"key":"e_1_3_4_44_2","article-title":"Any-k algorithms for enumerating ranked answers to conjunctive queries","volume":"2205","author":"Tziavelis Nikolaos","year":"2022","unstructured":"Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. 2022. Any-k algorithms for enumerating ranked answers to conjunctive queries. CoRR abs\/2205.05649 (2022).","journal-title":"CoRR"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2015.17"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3214708.3214711"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.5555\/1286831.1286840"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578517","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3578517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:37Z","timestamp":1750183717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3578517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,13]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3578517"],"URL":"https:\/\/doi.org\/10.1145\/3578517","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2023,3,13]]},"assertion":[{"value":"2021-12-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}