{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:03Z","timestamp":1755900603574,"version":"3.44.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"UK Research and Innovation","doi-asserted-by":"publisher","award":["EP\/X024431\/1"],"award-info":[{"award-number":["EP\/X024431\/1"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ (C) provides as input a UCQ \u03a8 \u2208 C and a database D and the problem is to compute the number of answers of \u03a8 in D.<\/jats:p>\n          <jats:p>Chen and Mengel [PODS'16] have shown that for any recursively enumerable class C, the problem #UCQ (C) is either fixed-parameter tractable or hard for one of the parameterised complexity classes W[1] or #W[1]. However, their tractability criterion is unwieldy in the sense that, given any concrete class C of UCQs, it is not easy to determine how hard it is to count answers to queries in C. Moreover, given a single specific UCQ \u03a8, it is not easy to determine how hard it is to count answers to \u03a8.<\/jats:p>\n          <jats:p>\n            In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ \u03a8=\u03c6\n            <jats:sub>1<\/jats:sub>\n            \u2228 ... \u2228 \u03c6\n            <jats:sub>l<\/jats:sub>\n            is the conjunctive query ^ \u03a8 = \u03c6_1 \u2227 ... \u2227 \u03c6\n            <jats:sub>l<\/jats:sub>\n            . We show that under natural closure properties of C, the problem #UCQ (C) is fixed-parameter tractable if and only if the combined conjunctive queries of UCQs in C, and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables --- if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of #UCQ (C) thus simplifies to the combined queries having bounded treewidth.\n          <\/jats:p>\n          <jats:p>\n            Finally, we give evidence that a closure property on C is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ \u03a8, the meta problem of deciding whether #UCQ (\u03a8) can be solved in time O(|D|\n            <jats:sup>d<\/jats:sup>\n            ) is NP-hard for any fixed d \u2265 1. Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is NP-hard.\n          <\/jats:p>","DOI":"10.1145\/3651614","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-17","source":"Crossref","is-referenced-by-count":0,"title":["Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6895-755X","authenticated-orcid":false,"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"CISPA, Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1879-6089","authenticated-orcid":false,"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3159-9418","authenticated-orcid":false,"given":"Marc","family":"Roth","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford &amp; School of Electronic Engineering and Computer Science, Queen Mary University of London, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"Zivn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_2_1","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451014"},{"key":"e_1_2_1_4_1","volume-title":"Bull. EATCS","volume":"120","author":"Arvind Vikraman","year":"2016","unstructured":"Vikraman Arvind. 2016. The Weisfeiler-Lehman Procedure. Bull. EATCS, Vol. 120 (2016). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/442"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104803"},{"key":"e_1_2_1_6_1","unstructured":"Guillaume Bagan. 2009. Algorithmes et complexit\u00e9 des probl\u00e8 mes d'\u00e9num\u00e9ration pour l'\u00e9 valuation de requ\u00eates logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries). Ph. D. Dissertation. University of Caen Normandy France. https:\/\/tel.archives-ouvertes.fr\/tel-00424232"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--74915--8_18"},{"key":"e_1_2_1_8_1","volume-title":"Weisfeiler and Leman Go Relational. In Learning on Graphs Conference, LoG 2022","volume":"46","author":"Barcel\u00f3 Pablo","year":"2022","unstructured":"Pablo Barcel\u00f3, Mikhail Galkin, Christopher Morris, and Miguel A. Romero Orth. 2022. Weisfeiler and Leman Go Relational. In Learning on Graphs Conference, LoG 2022, 9--12 December 2022, Virtual Event (Proceedings of Machine Learning Research, Vol. 198), Bastian Rieck and Razvan Pascanu (Eds.). PMLR, 46. https:\/\/proceedings.mlr.press\/v198\/barcelo22a.html"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034714"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3520240"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2018.8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2019.58"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_16_1","unstructured":"Johann Brault-Baron. 2013. De la pertinence de l'\u00e9 num\u00e9ration : complexit\u00e9 en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order). Ph. D. Dissertation. University of Caen Normandy France. https:\/\/tel.archives-ouvertes.fr\/tel-01081392"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--11269-0_6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531055"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2015.110"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902279"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--33293--7_4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.40"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.113"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448508"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526231"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2311.10634"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--57586--5_22"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139177801.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594559"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3333003"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1055"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2309.17053"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721845"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_47_1","volume-title":"A short note on the counting complexity of conjunctive queries. CoRR","author":"Mengel Stefan","year":"2021","unstructured":"Stefan Mengel. 2021. A short note on the counting complexity of conjunctive queries. CoRR, Vol. abs\/2112.01108 (2021). showeprint[arXiv]2112.01108 https:\/\/arxiv.org\/abs\/2112.01108"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000055"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.07011"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.012"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00676--9"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2012.07.003"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335209"},{"key":"e_1_2_1_55_1","volume-title":"7th International Conference, September 9--11","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9--11, 1981, Cannes, France, Proceedings. IEEE Computer Society, 82--94."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651614","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:06Z","timestamp":1755898806000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651614"],"URL":"https:\/\/doi.org\/10.1145\/3651614","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}