{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:24Z","timestamp":1750220484093,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T00:00:00Z","timestamp":1631059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID - Millennium Science Initiative Program","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}]},{"name":"Fondecyt","award":["1191337 and 1200967"],"award-info":[{"award-number":["1191337 and 1200967"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query\u00a0\n            <jats:italic>q<\/jats:italic>\n            , we consider the following two problems: Given as input an incomplete database\u00a0\n            <jats:italic>D<\/jats:italic>\n            , (a) return the number of completions of\u00a0\n            <jats:italic>D<\/jats:italic>\n            that satisfy\u00a0\n            <jats:italic>q<\/jats:italic>\n            ; or (b) return the number of valuations of the nulls of\u00a0\n            <jats:italic>D<\/jats:italic>\n            yielding a completion that satisfies\u00a0\n            <jats:italic>q<\/jats:italic>\n            . We obtain dichotomies between\u00a0#P-hardness and polynomial-time computability for these problems when\u00a0\n            <jats:italic>q<\/jats:italic>\n            is a self-join\u2013free conjunctive query and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in\u00a0\n            <jats:italic>D<\/jats:italic>\n            (what is called\n            <jats:italic>Codd tables<\/jats:italic>\n            ); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations: For instance, while the latter is always in\u00a0#P, we prove that the former is not in\u00a0#P under some widely believed theoretical complexity assumption. Moreover, we find that both (1) and (2) can reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial-time randomized approximation scheme (FPRAS), in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes.\n          <\/jats:p>","DOI":"10.1145\/3461642","type":"journal-article","created":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T19:02:44Z","timestamp":1631127764000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Counting Problems Over Incomplete Databases"],"prefix":"10.1145","volume":"22","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"Universidad Cat\u00f3lica &amp; IMFD Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"Barcel\u00f3","sequence":"additional","affiliation":[{"name":"Universidad Cat\u00f3lica &amp; IMFD Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,8]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Vol. 8 . Addison-Wesley Reading . Retrieved from http:\/\/webdam.inria.fr\/Alice\/. Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Vol. 8. Addison-Wesley Reading. Retrieved from http:\/\/webdam.inria.fr\/Alice\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/106886.106891"},{"key":"e_1_2_1_3_1","unstructured":"Adam. 2013. Number of surjective functions. Retrieved from https:\/\/math.stackexchange.com\/a\/615136\/378365.  Adam. 2013. Number of surjective functions. Retrieved from https:\/\/math.stackexchange.com\/a\/615136\/378365."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920976"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.35"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0149-y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387656"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319704"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0080-z"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371212"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3322190"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0044-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319703"},{"key":"e_1_2_1_16_1","first-page":"23","article-title":"Understanding relations (installment# 7)","volume":"7","author":"Codd T.","year":"1975","unstructured":"T. Codd . 1975 . Understanding relations (installment# 7) . FDT Bull. ACM SIGMOD 7 (1975), 23 \u2013 28 . T. Codd. 1975. Understanding relations (installment# 7). FDT Bull. ACM SIGMOD 7 (1975), 23\u201328.","journal-title":"FDT Bull. ACM SIGMOD"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3032027.3032069"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.006"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.05.003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80024-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367243.3367275"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007327"},{"key":"e_1_2_1_27_1","volume-title":"On decomposing graphs into forests and pseudoforests. arXiv preprint arXiv:1904.12435","author":"Grout Logan","year":"2019","unstructured":"Logan Grout and Benjamin Moore . 2019. On decomposing graphs into forests and pseudoforests. arXiv preprint arXiv:1904.12435 ( 2019 ). Logan Grout and Benjamin Moore. 2019. On decomposing graphs into forests and pseudoforests. arXiv preprint arXiv:1904.12435 (2019)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1991.160242"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1032"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/ijhc.2001.0506"},{"key":"e_1_2_1_31_1","unstructured":"Neil Immerman. 2012. Descriptive Complexity. Springer Science & Business Media. Retrieved from https:\/\/people.cs.umass.edu\/ immerman\/book\/ch0_1_2.pdf.  Neil Immerman. 2012. Descriptive Complexity. Springer Science & Business Media. Retrieved from https:\/\/people.cs.umass.edu\/ immerman\/book\/ch0_1_2.pdf."},{"key":"e_1_2_1_32_1","volume-title":"Welsh","author":"Jaeger Fran\u00e7ois","year":"1990","unstructured":"Fran\u00e7ois Jaeger , Dirk L. Vertigan , and Dominic J. A . Welsh . 1990 . On the computational complexity of the Jones and Tutte polynomials. In Math. Proc. Cambridge Phil. Soc., Vol. 108 . Cambridge University Press , 35\u201353. Retrieved from https:\/\/www.cambridge.org\/core\/journals\/mathematical-proceedings-of-the-cambridge-philosophical-society\/article\/on-the-computational-complexity-of-the-jones-and-tutte-polynomials\/0EA052341269A2816C36B15380B8AA02. Fran\u00e7ois Jaeger, Dirk L. Vertigan, and Dominic J. A. Welsh. 1990. On the computational complexity of the Jones and Tutte polynomials. In Math. Proc. Cambridge Phil. Soc., Vol. 108. Cambridge University Press, 35\u201353. Retrieved from https:\/\/www.cambridge.org\/core\/journals\/mathematical-proceedings-of-the-cambridge-philosophical-society\/article\/on-the-computational-complexity-of-the-jones-and-tutte-polynomials\/0EA052341269A2816C36B15380B8AA02."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3383313.3411537"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90139-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/69304.69309"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_56"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594561"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196983"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00068-9"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.011"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the International Conference on Database Theory. 155\u2013164","author":"Maslowski Dany","year":"2014","unstructured":"Dany Maslowski and Jef Wijsen . 2014 . Counting database repairs that satisfy conjunctive queries with self-joins . In Proceedings of the International Conference on Database Theory. 155\u2013164 . Retrieved from http:\/\/www.openproceedings.org\/ICDT\/ 2014\/paper_17.pdf. Dany Maslowski and Jef Wijsen. 2014. Counting database repairs that satisfy conjunctive queries with self-joins. In Proceedings of the International Conference on Database Theory. 155\u2013164. Retrieved from http:\/\/www.openproceedings.org\/ICDT\/2014\/paper_17.pdf."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90006-I"},{"key":"e_1_2_1_43_1","first-page":"179","article-title":"What is a matroid","volume":"5","author":"Oxley James","year":"2003","unstructured":"James Oxley . 2003 . What is a matroid . Cubo Matem. Educac. 5 , 3 (2003), 179 \u2013 218 . Retrieved from https:\/\/www.math.lsu.edu\/ oxley\/survey4.pdf. James Oxley. 2003. What is a matroid. Cubo Matem. Educac. 5, 3 (2003), 179\u2013218. Retrieved from https:\/\/www.math.lsu.edu\/ oxley\/survey4.pdf.","journal-title":"Cubo Matem. Educac."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/902066"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0147-0"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90369-Q"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/294135.294145"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/339266.339267"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.023"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/33.4.493"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3461642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:49:04Z","timestamp":1750193344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,8]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3461642"],"URL":"https:\/\/doi.org\/10.1145\/3461642","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2021,9,8]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}