{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:14:08Z","timestamp":1789434848044,"version":"build-2803163510"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>\n            Join evaluation is one of the most fundamental operations performed by database systems and arguably the most well-studied problem in the Database community. A staggering number of join algorithms have been developed, and commercial database engines use finely tuned join heuristics that take into account many factors including the selectivity of predicates, memory, IO, etc. However, most of the results have catered to either full join queries or non-full join queries but with degree constraints (such as PK-FK relationships) that makes join evaluation easier. Further, most of the algorithms are also not output-sensitive. In this paper, we present a novel, output-sensitive algorithm for the evaluation of acyclic Conjunctive Queries (CQs) that contain arbitrary free variables. Our result is based on a novel generalization of the Yannakakis algorithm and shows that it is possible to improve the running time guarantee of Yannakakis algorithm by a polynomial factor. Importantly, our algorithmic improvement does not depend on the use of fast matrix multiplication, as a recently proposed algorithm does. The application of our algorithm recovers known prior results and improves on known state-of-the-art results for common queries such as paths and stars. The upper bound is complemented with a matching lower bound for star queries, a restricted subclass of acyclic CQs, and a family of cyclic CQs conditioned on two variants of the\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -clique conjecture.\n          <\/jats:p>","DOI":"10.1145\/3695838","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-24","source":"Crossref","is-referenced-by-count":6,"title":["Output-sensitive Conjunctive Query Evaluation"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2342-4060","authenticated-orcid":false,"given":"Shaleen","family":"Deep","sequence":"first","affiliation":[{"name":"Microsoft Jim Gray Systems Lab, Madison, WI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7636-0831","authenticated-orcid":false,"given":"Hangdong","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7714-2195","authenticated-orcid":false,"given":"Austen Z.","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6309-1702","authenticated-orcid":false,"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"arXiv preprint arXiv:2211.10022","author":"Abboud Amir","year":"2022","unstructured":"Amir Abboud, Seri Khoury, Oree Leibowitz, and Ron Safier. 2022. Listing 4-cycles. arXiv preprint arXiv:2211.10022 (2022)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695835"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492488"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_2_1_8_1","volume-title":"Constant delay enumeration with fpt-preprocessing for conjunctive queries of bounded submodular width. arXiv preprint arXiv:2003.01075","author":"Berkholz Christoph","year":"2020","unstructured":"Christoph Berkholz and Nicole Schweikardt. 2020. Constant delay enumeration with fpt-preprocessing for conjunctive queries of bounded submodular width. arXiv preprint arXiv:2003.01075 (2020)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210059"},{"key":"e_1_2_1_10_1","volume-title":"Virginia Vassilevska Williams, and Uri Zwick","author":"Bj\u00f6rklund Andreas","year":"2014","unstructured":"Andreas Bj\u00f6rklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. 2014. Listing triangles. In International Colloquium on Automata, Languages, and Programming. Springer, 223--234."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9632-8"},{"key":"e_1_2_1_12_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP","volume":"148","author":"Conte Alessio","year":"2016","unstructured":"Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. 2016. Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Vol. 148. 1--148."},{"key":"e_1_2_1_13_1","volume-title":"A Guide to the SQL Standard","author":"Date Chris J","unstructured":"Chris J Date. 1989. A Guide to the SQL Standard. Addison-Wesley Longman Publishing Co., Inc."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183748"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588666"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems. In ICALP (LIPIcs, Vol. 261)","volume":"127","author":"Fan Austen Z.","year":"2023","unstructured":"Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. 2023. The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems. In ICALP (LIPIcs, Vol. 261). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 127:1--127:20.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '07)","author":"Green Todd J.","unstructured":"Todd J. Green, Grigoris Karvounarakis, and Val Tannen. [n.,d.]. Provenance semirings. In Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '07). Association for Computing Machinery, New York, NY, USA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651599"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings. Springer, 766--778","author":"Jacob Riko","year":"2015","unstructured":"Riko Jacob and Morten St\u00f6ckel. 2015. Fast output-sensitive matrix multiplication. In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14--16, 2015, Proceedings. Springer, 766--778."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585157"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","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 PODS. ACM 429--444.","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings 9. Springer, 260--272","author":"Makino Kazuhisa","year":"2004","unstructured":"Kazuhisa Makino and Takeaki Uno. 2004. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humleb\u00e6k, Denmark, July 8--10, 2004. Proceedings 9. Springer, 260--272."},{"key":"e_1_2_1_26_1","unstructured":"HG Marc. 1979. On the universal relation. Technical Report. Technical report University of Toronto."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_2_1_30_1","first-page":"82","article-title":"Algorithms for acyclic database schemes","volume":"81","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82--94.","journal-title":"VLDB"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings. Computer Software and The IEEE Computer Society's Third International Applications Conference","author":"Yu Clement Tak","year":"1979","unstructured":"Clement Tak Yu and Meral Z Ozsoyoglu. 1979. An algorithm for tree-query membership of a distributed query. In COMPSAC 79. Proceedings. Computer Software and The IEEE Computer Society's Third International Applications Conference, 1979. IEEE, 306--312."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651591"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695838","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:33:03Z","timestamp":1755916383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695838"],"URL":"https:\/\/doi.org\/10.1145\/3695838","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}