{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:26:27Z","timestamp":1760171187939,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,14]],"date-time":"2020-06-14T00:00:00Z","timestamp":1592092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Millennium Institute for Foundational Research on Data (IMFD)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"DOI":"10.1145\/3375395.3387656","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T15:10:29Z","timestamp":1590765029000},"page":"165-177","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Counting Problems over Incomplete Databases"],"prefix":"10.1145","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[{"name":"PUC & IMFD Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"Barcel\u00f3","sequence":"additional","affiliation":[{"name":"PUC & IMFD Chile, Sanrtiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"IMFD Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"volume-title":"http:\/\/webdam.inria.fr\/Alice\/ Foundations of databases","author":"Abiteboul Serge","key":"e_1_3_2_1_1_1","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. http:\/\/webdam.inria.fr\/Alice\/ Foundations of databases . Vol. 8 . Addison-Wesley Reading . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. http:\/\/webdam.inria.fr\/Alice\/ Foundations of databases. Vol. 8. Addison-Wesley Reading."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(51)90007-2"},{"key":"e_1_3_2_1_3_1","unstructured":"Adam. 2013. https:\/\/math.stackexchange.com\/a\/615136\/378365 Number of surjective functions. https:\/\/math.stackexchange.com\/a\/615136\/378365  Adam. 2013. https:\/\/math.stackexchange.com\/a\/615136\/378365 Number of surjective functions. https:\/\/math.stackexchange.com\/a\/615136\/378365"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920976"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"volume-title":"ftp:\/\/ftp.cs.toronto.edu\/csrg-technical-reports\/513\/tr513.pdf Clean answers over dirty databases: A probabilistic approach","author":"Andritsos Periklis","key":"e_1_3_2_1_6_1","unstructured":"Periklis Andritsos , Ariel Fuxman , and Renee J Miller . 2006. ftp:\/\/ftp.cs.toronto.edu\/csrg-technical-reports\/513\/tr513.pdf Clean answers over dirty databases: A probabilistic approach . In ICDE. IEEE , 30--30. Periklis Andritsos, Ariel Fuxman, and Renee J Miller. 2006. ftp:\/\/ftp.cs.toronto.edu\/csrg-technical-reports\/513\/tr513.pdf Clean answers over dirty databases: A probabilistic approach. In ICDE. IEEE, 30--30."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0149-y"},{"key":"e_1_3_2_1_8_1","volume-title":"2019 a. Counting Problems over Incomplete Databases. arXiv preprint arXiv:1912.11064","author":"Arenas Marcelo","year":"2019","unstructured":"Marcelo Arenas , Pablo Barcel\u00f3 , and Mika\u00ebl Monet . 2019 a. Counting Problems over Incomplete Databases. arXiv preprint arXiv:1912.11064 ( 2019 ). https:\/\/arxiv.org\/abs\/1912.11064 Extended version of the current article. Marcelo Arenas, Pablo Barcel\u00f3, and Mika\u00ebl Monet. 2019 a. Counting Problems over Incomplete Databases. arXiv preprint arXiv:1912.11064 (2019). https:\/\/arxiv.org\/abs\/1912.11064 Extended version of the current article."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Marcelo Arenas Leopoldo E. Bertossi and Jan Chomicki. 1999. http:\/\/marenas.sitios.ing.uc.cl\/publications\/pods99.pdf Consistent query answers in inconsistent databases. In PODS. 68--79.  Marcelo Arenas Leopoldo E. Bertossi and Jan Chomicki. 1999. http:\/\/marenas.sitios.ing.uc.cl\/publications\/pods99.pdf Consistent query answers in inconsistent databases. In PODS. 68--79.","DOI":"10.1145\/303976.303983"},{"key":"e_1_3_2_1_10_1","unstructured":"Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram and Cristian Riveros. 2019 b. https:\/\/arxiv.org\/abs\/1906.09226 Efficient logspace classes for enumeration counting and uniform generation. In PODS. 59--73.  Marcelo Arenas Luis Alberto Croquevielle Rajesh Jayaram and Cristian Riveros. 2019 b. https:\/\/arxiv.org\/abs\/1906.09226 Efficient logspace classes for enumeration counting and uniform generation. In PODS. 59--73."},{"key":"e_1_3_2_1_11_1","volume-title":"Alon Y. Halevy, and Jennifer Widom.","author":"Benjelloun Omar","year":"2006","unstructured":"Omar Benjelloun , Anish Das Sarma , Alon Y. Halevy, and Jennifer Widom. 2006 . http:\/\/www.vldb.org\/conf\/2006\/p953-benjelloun.pdf ULDBs: Databases with uncertainty and lineage. In VLDB. 953--964. Omar Benjelloun, Anish Das Sarma, Alon Y. Halevy, and Jennifer Widom. 2006. http:\/\/www.vldb.org\/conf\/2006\/p953-benjelloun.pdf ULDBs: Databases with uncertainty and lineage. In VLDB. 953--964."},{"volume-title":"https:\/\/www.cs.ubc.ca\/laks\/cpsc504\/dc-leo.pdf Database repairing and consistent query answering","author":"Bertossi Leopoldo E.","key":"e_1_3_2_1_12_1","unstructured":"Leopoldo E. Bertossi . 2011. https:\/\/www.cs.ubc.ca\/laks\/cpsc504\/dc-leo.pdf Database repairing and consistent query answering . Morgan & Claypool Publishers . Leopoldo E. Bertossi. 2011. https:\/\/www.cs.ubc.ca\/laks\/cpsc504\/dc-leo.pdf Database repairing and consistent query answering. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Leopoldo E. Bertossi. 2019. https:\/\/dl.acm.org\/citation.cfm?id=3322190 Database repairs and consistent query answering: Origins and further developments. In PODS. 48--58.  Leopoldo E. Bertossi. 2019. https:\/\/dl.acm.org\/citation.cfm?id=3322190 Database repairs and consistent query answering: Origins and further developments. In PODS. 48--58.","DOI":"10.1145\/3294052.3322190"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0044-6"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Marco Calautti Marco Console and Andreas Pieris. 2019. https:\/\/dl.acm.org\/citation.cfm?id=3319703 Counting database repairs under primary Keys revisited. In PODS. 104--118.  Marco Calautti Marco Console and Andreas Pieris. 2019. https:\/\/dl.acm.org\/citation.cfm?id=3319703 Counting database repairs under primary Keys revisited. In PODS. 104--118.","DOI":"10.1145\/3294052.3319703"},{"key":"e_1_3_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. of ACM Sigmod , Vol. 7 (1975), 23 -- 28 . T Codd. 1975. Understanding relations (installment# 7). FDT Bull. of ACM Sigmod, Vol. 7 (1975), 23--28.","journal-title":"FDT Bull. of ACM Sigmod"},{"key":"e_1_3_2_1_17_1","unstructured":"Marco Console Paolo Guagliardo and Leonid Libkin. 2016. https:\/\/dl.acm.org\/citation.cfm?id=3032069 Approximations and refinements of certain answers via many-valued logics. In KR. 349--358.  Marco Console Paolo Guagliardo and Leonid Libkin. 2016. https:\/\/dl.acm.org\/citation.cfm?id=3032069 Approximations and refinements of certain answers via many-valued logics. In KR. 349--358."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.006"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383844"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80024-8"},{"key":"e_1_3_2_1_23_1","unstructured":"Am\u00e9 lie Gheerbrant and Cristina Sirangelo. 2019. https:\/\/www.ijcai.org\/proceedings\/2019\/236 Best answers over incomplete data: Complexity and first-order rewritings. In IJCAI. 1704--1710.  Am\u00e9 lie Gheerbrant and Cristina Sirangelo. 2019. https:\/\/www.ijcai.org\/proceedings\/2019\/236 Best answers over incomplete data: Complexity and first-order rewritings. In IJCAI. 1704--1710."},{"volume-title":"https:\/\/ieeexplore.ieee.org\/abstract\/document\/160242 The power of witness reduction. In [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference","author":"Gupta Sanjay","key":"e_1_3_2_1_24_1","unstructured":"Sanjay Gupta . 1991. https:\/\/ieeexplore.ieee.org\/abstract\/document\/160242 The power of witness reduction. In [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference . IEEE , 43--59. Sanjay Gupta. 1991. https:\/\/ieeexplore.ieee.org\/abstract\/document\/160242 The power of witness reduction. In [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference. IEEE, 43--59."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"volume-title":"Mathematical Proc. of the Cambridge Phil. Soc.","author":"Jaeger Francc","key":"e_1_3_2_1_26_1","unstructured":"Francc ois Jaeger , Dirk L Vertigan , and Dominic JA Welsh . 1990. 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 On the computational complexity of the Jones and Tutte polynomials . In Mathematical Proc. of the Cambridge Phil. Soc. , Vol. 108 . Cambridge University Press , 35--53. Francc ois Jaeger, Dirk L Vertigan, and Dominic JA Welsh. 1990. 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 On the computational complexity of the Jones and Tutte polynomials. In Mathematical Proc. of the Cambridge Phil. Soc., Vol. 108. Cambridge University Press, 35--53."},{"key":"e_1_3_2_1_27_1","volume-title":"TCS","volume":"43","author":"Jerrum Mark R","year":"1986","unstructured":"Mark R Jerrum , Leslie G Valiant , and Vijay V Vazirani . 1986 . http:\/\/www2.stat.duke.edu\/ scs\/Courses\/Stat376\/Papers\/ConvergeRates\/RandomizedAlgs\/JerrumValiantVaziraniTCS1986.pdf Random generation of combinatorial structures from a uniform distribution . TCS , Vol. 43 (1986), 169--188. Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. 1986. http:\/\/www2.stat.duke.edu\/ scs\/Courses\/Stat376\/Papers\/ConvergeRates\/RandomizedAlgs\/JerrumValiantVaziraniTCS1986.pdf Random generation of combinatorial structures from a uniform distribution. TCS, Vol. 43 (1986), 169--188."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90139-9"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/69304.69309"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Leonid Libkin. 2014. https:\/\/homepages.inf.ed.ac.uk\/libkin\/papers\/pods14.pdf Incomplete data: what went wrong and how to fix it. In PODS. 1--13.  Leonid Libkin. 2014. https:\/\/homepages.inf.ed.ac.uk\/libkin\/papers\/pods14.pdf Incomplete data: what went wrong and how to fix it. In PODS. 1--13.","DOI":"10.1145\/2594538.2594561"},{"key":"e_1_3_2_1_31_1","unstructured":"Leonid Libkin. 2018. https:\/\/homepages.inf.ed.ac.uk\/libkin\/papers\/pods18.pdf Certain answers meet zero-one laws. In PODS. 195--207.  Leonid Libkin. 2018. https:\/\/homepages.inf.ed.ac.uk\/libkin\/papers\/pods18.pdf Certain answers meet zero-one laws. In PODS. 195--207."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.011"},{"key":"e_1_3_2_1_33_1","unstructured":"Dany Maslowski and Jef Wijsen. 2014. http:\/\/www.openproceedings.org\/ICDT\/2014\/paper_17.pdf Counting database repairs that satisfy conjunctive queries with self-joins.. In ICDT. 155--164.  Dany Maslowski and Jef Wijsen. 2014. http:\/\/www.openproceedings.org\/ICDT\/2014\/paper_17.pdf Counting database repairs that satisfy conjunctive queries with self-joins.. In ICDT. 155--164."},{"key":"e_1_3_2_1_34_1","unstructured":"Mika\u00ebl Monet. 2019. https:\/\/cstheory.stackexchange.com\/questions\/43888\/a-variant-of-positive-2-dnf A variant of #POSITIVE-2-DNF. https:\/\/cstheory.stackexchange.com\/q\/43888\/38111  Mika\u00ebl Monet. 2019. https:\/\/cstheory.stackexchange.com\/questions\/43888\/a-variant-of-positive-2-dnf A variant of #POSITIVE-2-DNF. https:\/\/cstheory.stackexchange.com\/q\/43888\/38111"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90006-I"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"volume-title":"https:\/\/pdfs.semanticscholar.org\/d82a\/786f460a5d5c2c6d97aa60f0ead0e70dc67e.pdf On closed world data bases","author":"Reiter Raymond","key":"e_1_3_2_1_37_1","unstructured":"Raymond Reiter . 1978. https:\/\/pdfs.semanticscholar.org\/d82a\/786f460a5d5c2c6d97aa60f0ead0e70dc67e.pdf On closed world data bases . Springer US , 55--76. Raymond Reiter. 1978. https:\/\/pdfs.semanticscholar.org\/d82a\/786f460a5d5c2c6d97aa60f0ead0e70dc67e.pdf On closed world data bases. Springer US, 55--76."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0147-0"},{"key":"e_1_3_2_1_39_1","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. https:\/\/www.morganclaypool.com\/doi\/abs\/10.2200\/S00362ED1V01Y201105DTM016 Probabilistic databases. Morgan & Claypool.  Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. https:\/\/www.morganclaypool.com\/doi\/abs\/10.2200\/S00362ED1V01Y201105DTM016 Probabilistic databases. Morgan & Claypool."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90369-Q"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"volume-title":"Logics for databases and information systems","author":"van der Meyden Ron","key":"e_1_3_2_1_44_1","unstructured":"Ron van der Meyden . 1998. https:\/\/link.springer.com\/chapter\/10.1007\/978--1--4615--5643--5_10 Logical approaches to incomplete information: A survey . In Logics for databases and information systems . Springer , 307--356. Ron van der Meyden. 1998. https:\/\/link.springer.com\/chapter\/10.1007\/978--1--4615--5643--5_10 Logical approaches to incomplete information: A survey. In Logics for databases and information systems. Springer, 307--356."},{"key":"e_1_3_2_1_45_1","unstructured":"Moshe Y Vardi. 1982. http:\/\/www.dis.uniroma1.it\/degiacom\/didattica\/semingsoft\/SIS05-06\/materiale\/1-query-congiuntive\/riferimenti\/vardi-1982.pdf The complexity of relational query languages. In STOC. ACM 137--146.  Moshe Y Vardi. 1982. http:\/\/www.dis.uniroma1.it\/degiacom\/didattica\/semingsoft\/SIS05-06\/materiale\/1-query-congiuntive\/riferimenti\/vardi-1982.pdf The complexity of relational query languages. In STOC. ACM 137--146."}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Portland OR USA","acronym":"SIGMOD\/PODS '20"},"container-title":["Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375395.3387656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:48Z","timestamp":1750199568000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":45,"alternative-id":["10.1145\/3375395.3387656","10.1145\/3375395"],"URL":"https:\/\/doi.org\/10.1145\/3375395.3387656","relation":{},"subject":[],"published":{"date-parts":[[2020,6,14]]},"assertion":[{"value":"2020-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}