{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:45:51Z","timestamp":1776969951294,"version":"3.51.4"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2026,4,23]]},"abstract":"<jats:p>One of the most celebrated results for evaluating conjunctive queries (CQs) is the Yannakakis algorithm [24] proposed in 1981. It is known that free-connex CQs can be evaluated in O(N + OUT) time, where N is the input size of the database and OUT is the output size of the query result. This is already output-optimal. However, only an upper bound O(N \u00b7OUT) on the runtime is known for the remaining acyclic but non-freeconnex CQs. Alternatively, one can convert a non-freeconnex CQ into a free-connex one using tree decomposition techniques, and then run the Yannakakis algorithm. However, none of them is known to be output-optimal.<\/jats:p>","DOI":"10.1145\/3810900.3810906","type":"journal-article","created":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:16:38Z","timestamp":1776968198000},"page":"31-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Output-Optimal Evaluation of Conjunctive Queries"],"prefix":"10.1145","volume":"55","author":[{"given":"Xiao","family":"Hu","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaleen","family":"Deep","sequence":"additional","affiliation":[{"name":"Microsoft, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"UW-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Austen Z.","family":"Fan","sequence":"additional","affiliation":[{"name":"UW-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hangdong","family":"Zhao","sequence":"additional","affiliation":[{"name":"UW-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725235"},{"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.1137\/110859440"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_6_1","volume-title":"On the desirability of acyclic database schemes. Journal of the ACM (JACM), 30(3):479-513","author":"Beeri C.","year":"1983","unstructured":"C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. Journal of the ACM (JACM), 30(3):479-513, 1983."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3742728.3742737"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183748"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00040"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651599"},{"key":"e_1_2_1_12_1","volume-title":"arXiv preprint arXiv:2406.05536","author":"X. Hu.","year":"2024","unstructured":"X. Hu. Output-optimal algorithms for join-aggregate queries. arXiv preprint arXiv:2406.05536, 2024."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547326"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_16_1","volume-title":"Pandaexpress: a simpler and faster panda algorithm. arXiv preprint arXiv:2512.10217","author":"Khamis M. A.","year":"2025","unstructured":"M. A. Khamis, H. Q. Ngo, and D. Suciu. Pandaexpress: a simpler and faster panda algorithm. arXiv preprint arXiv:2512.10217, 2025."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_62"},{"key":"e_1_2_1_21_1","volume-title":"Proc. International Conference on Database Theory","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory, 2014."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725423"},{"key":"e_1_2_1_23_1","volume-title":"CIDR","author":"Yang Y.","year":"2024","unstructured":"Y. Yang, H. Zhao, X. Yu, and P. Koutris. Predicate transfer: Efficient pre-filtering on multi-join queries. CIDR, 2024."},{"key":"e_1_2_1_24_1","first-page":"82","volume-title":"VLDB","volume":"81","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, volume 81, pages 82-94, 1981."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725283"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3810900.3810906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:16:57Z","timestamp":1776968217000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3810900.3810906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,23]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,23]]}},"alternative-id":["10.1145\/3810900.3810906"],"URL":"https:\/\/doi.org\/10.1145\/3810900.3810906","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2026,4,23]]},"assertion":[{"value":"2026-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}