{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:19:24Z","timestamp":1778807964334,"version":"3.51.4"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Science Fund","award":["P30930-N35, W1255-N23"],"award-info":[{"award-number":["P30930-N35, W1255-N23"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            We study the enumeration complexity of\n            <jats:bold>Unions of Conjunctive Queries (UCQs)<\/jats:bold>\n            . We aim to identify the UCQs that are tractable in the sense that the answer tuples can be enumerated with a linear preprocessing phase and a constant delay between every successive tuples. It has been established that, in the absence of self-joins and under conventional complexity assumptions, the CQs that admit such an evaluation are precisely the free-connex ones. A union of tractable CQs is always tractable. We generalize the notion of free-connexity from CQs to UCQs, thus showing that some unions containing intractable CQs are, in fact, tractable. Interestingly, some unions consisting of only intractable CQs are tractable too. We show how to use the techniques presented in this article also in settings where the database contains cardinality dependencies (including functional dependencies and key constraints) or when the UCQs contain disequalities. The question of finding a full characterization of the tractability of UCQs remains open. Nevertheless, we prove that, for several classes of queries, free-connexity fully captures the tractable UCQs.\n          <\/jats:p>","DOI":"10.1145\/3450263","type":"journal-article","created":{"date-parts":[[2021,5,30]],"date-time":"2021-05-30T01:20:56Z","timestamp":1622337656000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["On the Enumeration Complexity of Unions of Conjunctive Queries"],"prefix":"10.1145","volume":"46","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"first","affiliation":[{"name":"Technion - Israel Institute of Technology, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Kr\u00f6ll","sequence":"additional","affiliation":[{"name":"TU Wien, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 580\u2013591","author":"Alman J."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 21st International Conference on Database Theory (ICDT 2018","author":"Berkholz Christoph","year":"2018"},{"key":"e_1_2_1_10_1","volume-title":"Incremental delay enumeration: Space and time. Discrete Applied Mathematics","author":"Capelli Florent","year":"2018"},{"key":"e_1_2_1_11_1","volume-title":"Enumeration complexity of conjunctive queries with functional dependencies. Theory of Computing Systems","author":"Carmeli Nofar","year":"2019"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319700"},{"key":"e_1_2_1_13_1","first-page":"77","volume-title":"Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC\u201977)","author":"Ashok"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276923"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02127798"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_20_1","unstructured":"Wojciech Kazana. 2013. Query evaluation with constant delay. Theses. \u00c9cole normale sup\u00e9rieure de Cachan - ENS Cachan. https:\/\/tel.archives-ouvertes.fr\/tel-00919786  Wojciech Kazana. 2013. Query evaluation with constant delay. Theses. \u00c9cole normale sup\u00e9rieure de Cachan - ENS Cachan. https:\/\/tel.archives-ouvertes.fr\/tel-00919786"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Lincoln Andrea","year":"2018"},{"key":"e_1_2_1_23_1","volume-title":"Shapiro","author":"Moret Bernard M. E.","year":"1991"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196961"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196971"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_27_1","volume-title":"ICDT 2017 (Leibniz International Proceedings in Informatics (LIPIcs)), Michael Benedikt and Giorgio Orsi (Eds.)","volume":"68","author":"Segoufin Luc","year":"2017"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases -","volume":"7","author":"Yannakakis Mihalis","year":"1981"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450263","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:46:58Z","timestamp":1750193218000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,29]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3450263"],"URL":"https:\/\/doi.org\/10.1145\/3450263","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,29]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}