{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:41:36Z","timestamp":1787017296274,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":39,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"DOI":"10.1145\/3375395.3387642","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T11:10:29Z","timestamp":1590750629000},"page":"149-163","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases"],"prefix":"10.1145","author":[{"given":"Mika\u00ebl","family":"Monet","sequence":"first","affiliation":[{"name":"DCC, University of Chile & IMFD Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675141"},{"key":"e_1_3_2_1_2_1","unstructured":"Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2017. https:\/\/arxiv.org\/pdf\/1702.05589 A circuit-based approach to efficient enumeration. In ICALP .  Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2017. https:\/\/arxiv.org\/pdf\/1702.05589 A circuit-based approach to efficient enumeration. In ICALP ."},{"key":"e_1_3_2_1_3_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Amarilli Antoine","unstructured":"Antoine Amarilli , Pierre Bourhis , and Pierre Senellart . 2015. https:\/\/arxiv.org\/pdf\/1511.08723.pdf Provenance circuits for trees and treelike instances . In International Colloquium on Automata, Languages, and Programming . Springer , 56--68. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. 2015. https:\/\/arxiv.org\/pdf\/1511.08723.pdf Provenance circuits for trees and treelike instances. In International Colloquium on Automata, Languages, and Programming. Springer, 56--68."},{"key":"e_1_3_2_1_4_1","volume-title":"https:\/\/arxiv.org\/pdf\/1811.02944.pdf Connecting knowledge compilation classes and width parameters. Theory of Computing Systems (Jun","author":"Amarilli Antoine","year":"2019","unstructured":"Antoine Amarilli , Florent Capelli , Mika\u00ebl Monet , and Pierre Senellart . 2019. https:\/\/arxiv.org\/pdf\/1811.02944.pdf Connecting knowledge compilation classes and width parameters. Theory of Computing Systems (Jun 2019 ). Antoine Amarilli, Florent Capelli, Mika\u00ebl Monet, and Pierre Senellart. 2019. https:\/\/arxiv.org\/pdf\/1811.02944.pdf Connecting knowledge compilation classes and width parameters. Theory of Computing Systems (Jun 2019)."},{"key":"e_1_3_2_1_5_1","unstructured":"Gilles Audemard and Laurent Simon. 2009. http:\/\/ijcai.org\/Proceedings\/09\/Papers\/074.pdf Predicting learnt clauses quality in modern SAT solvers. In IJCAI.  Gilles Audemard and Laurent Simon. 2009. http:\/\/ijcai.org\/Proceedings\/09\/Papers\/074.pdf Predicting learnt clauses quality in modern SAT solvers. In IJCAI."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984632"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392300"},{"key":"e_1_3_2_1_8_1","first-page":"1008","article-title":"https:\/\/www.ijcai.org\/Proceedings\/16\/Papers\/147.pdf Knowledge compilation meets communication complexity","volume":"16","author":"Bova Simone","year":"2016","unstructured":"Simone Bova , Florent Capelli , Stefan Mengel , and Friedrich Slivovsky . 2016 . https:\/\/www.ijcai.org\/Proceedings\/16\/Papers\/147.pdf Knowledge compilation meets communication complexity . In IJCAI , Vol. 16. 1008 -- 1014 . Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. 2016. https:\/\/www.ijcai.org\/Proceedings\/16\/Papers\/147.pdf Knowledge compilation meets communication complexity. In IJCAI, Vol. 16. 1008--1014.","journal-title":"IJCAI"},{"key":"e_1_3_2_1_9_1","unstructured":"Simone Bova and Stefan Szeider. 2017. https:\/\/arxiv.org\/abs\/1701.04626 Circuit treewidth sentential decision and query compilation. In PODS. ACM 233--246.  Simone Bova and Stefan Szeider. 2017. https:\/\/arxiv.org\/abs\/1701.04626 Circuit treewidth sentential decision and query compilation. In PODS. ACM 233--246."},{"key":"e_1_3_2_1_10_1","volume-title":"https:\/\/www.cs.cmu.edu\/bryant\/pubdir\/ieeetc86.pdf Graph-based algorithms for Boolean function manipulation","year":"1986","unstructured":"Bryant. 1986. https:\/\/www.cs.cmu.edu\/bryant\/pubdir\/ieeetc86.pdf Graph-based algorithms for Boolean function manipulation . IEEE Trans. Comput ., Vol. C-35 , 8 ( 1986 ), 677--691. Bryant. 1986. https:\/\/www.cs.cmu.edu\/bryant\/pubdir\/ieeetc86.pdf Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput., Vol. C-35, 8 (1986), 677--691."},{"key":"e_1_3_2_1_11_1","volume-title":"https:\/\/web.cs.ucdavis.edu\/green\/courses\/ecs289f-w10\/iidb06.pdf Why and where: a characterization of data provenance","author":"Buneman Peter","unstructured":"Peter Buneman , Sanjeev Khanna , and Tan Wang-Chiew . 2001. https:\/\/web.cs.ucdavis.edu\/green\/courses\/ecs289f-w10\/iidb06.pdf Why and where: a characterization of data provenance . In ICDT. Springer , 316--330. Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. 2001. https:\/\/web.cs.ucdavis.edu\/green\/courses\/ecs289f-w10\/iidb06.pdf Why and where: a characterization of data provenance. In ICDT. Springer, 316--330."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.11.11-34"},{"key":"e_1_3_2_1_14_1","volume-title":"https:\/\/www.cambridge.org\/core\/books\/modeling-and-reasoning-with-bayesian-networks\/8A3769B81540EA93B525C4C2700C9DE6 Modeling and reasoning with Bayesian networks","author":"Darwiche Adnan","unstructured":"Adnan Darwiche . 2009. https:\/\/www.cambridge.org\/core\/books\/modeling-and-reasoning-with-bayesian-networks\/8A3769B81540EA93B525C4C2700C9DE6 Modeling and reasoning with Bayesian networks . Cambridge University Press . Adnan Darwiche. 2009. https:\/\/www.cambridge.org\/core\/books\/modeling-and-reasoning-with-bayesian-networks\/8A3769B81540EA93B525C4C2700C9DE6 Modeling and reasoning with Bayesian networks. Cambridge University Press."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.989"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877203"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_3_2_1_18_1","volume-title":"International Conference on Extending Database Technology. Springer, 278--296","author":"Green Todd J","year":"2006","unstructured":"Todd J Green and Val Tannen . 2006 . https:\/\/web.cs.ucdavis.edu\/ green\/courses\/ecs289f-w10\/iidb06.pdf Models for incomplete and probabilistic information . In International Conference on Extending Database Technology. Springer, 278--296 . Todd J Green and Val Tannen. 2006. https:\/\/web.cs.ucdavis.edu\/ green\/courses\/ecs289f-w10\/iidb06.pdf Models for incomplete and probabilistic information. In International Conference on Extending Database Technology. Springer, 278--296."},{"key":"e_1_3_2_1_19_1","first-page":"6","article-title":"http:\/\/web.cs.ucla.edu\/guyvdb\/publications\/browse.php?bib=guyvdb.bib&key=GribkoffDEBUL14 Lifted probabilistic inference: a guide for the database researcher","volume":"37","author":"Gribkoff Eric","year":"2014","unstructured":"Eric Gribkoff , Dan Suciu , and Guy Van den Broeck . 2014 . http:\/\/web.cs.ucla.edu\/guyvdb\/publications\/browse.php?bib=guyvdb.bib&key=GribkoffDEBUL14 Lifted probabilistic inference: a guide for the database researcher . IEEE Data Eng. Bull. , Vol. 37 , 3 (2014), 6 -- 17 . Eric Gribkoff, Dan Suciu, and Guy Van den Broeck. 2014. http:\/\/web.cs.ucla.edu\/guyvdb\/publications\/browse.php?bib=guyvdb.bib&key=GribkoffDEBUL14 Lifted probabilistic inference: a guide for the database researcher. IEEE Data Eng. Bull., Vol. 37, 3 (2014), 6--17.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_1_20_1","first-page":"183","article-title":"http:\/\/www.mathnet.ru\/links\/5e9c2c452b73e3545c38707329c00429\/rm3055.pdf Repetition-free Boolean functions","volume":"32","author":"Gurvich Vladimir Alexander","year":"1977","unstructured":"Vladimir Alexander Gurvich . 1977 . http:\/\/www.mathnet.ru\/links\/5e9c2c452b73e3545c38707329c00429\/rm3055.pdf Repetition-free Boolean functions . Uspekhi Matematicheskikh Nauk , Vol. 32 , 1 (1977), 183 -- 184 . Vladimir Alexander Gurvich. 1977. http:\/\/www.mathnet.ru\/links\/5e9c2c452b73e3545c38707329c00429\/rm3055.pdf Repetition-free Boolean functions. Uspekhi Matematicheskikh Nauk, Vol. 32, 1 (1977), 183--184.","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"e_1_3_2_1_21_1","first-page":"156","article-title":"https:\/\/www.ijcai.org\/Proceedings\/05\/Papers\/0876.pdf DPLL with a trace: From SAT to knowledge compilation","volume":"5","author":"Huang Jinbo","year":"2005","unstructured":"Jinbo Huang and Adnan Darwiche . 2005 . https:\/\/www.ijcai.org\/Proceedings\/05\/Papers\/0876.pdf DPLL with a trace: From SAT to knowledge compilation . In IJCAI , Vol. 5. 156 -- 162 . Jinbo Huang and Adnan Darwiche. 2005. https:\/\/www.ijcai.org\/Proceedings\/05\/Papers\/0876.pdf DPLL with a trace: From SAT to knowledge compilation. In IJCAI, Vol. 5. 156--162.","journal-title":"IJCAI"},{"key":"e_1_3_2_1_22_1","article-title":"http:\/\/dl.acm.org\/citation.cfm?id=1622606.1622613 The language of search","volume":"29","author":"Huang Jinbo","year":"2007","unstructured":"Jinbo Huang and Adnan Darwiche . 2007 . http:\/\/dl.acm.org\/citation.cfm?id=1622606.1622613 The language of search . J. Artif. Int. Res. , Vol. 29 , 1 (2007). Jinbo Huang and Adnan Darwiche. 2007. http:\/\/dl.acm.org\/citation.cfm?id=1622606.1622613 The language of search. J. Artif. Int. Res., Vol. 29, 1 (2007).","journal-title":"J. Artif. Int. Res."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Abhay Jha and Dan Suciu. 2012. https:\/\/homes.cs.washington.edu\/ suciu\/file37_paper.pdf On the tractability of query compilation and bounded treewidth. In ICDT. ACM 249--261.  Abhay Jha and Dan Suciu. 2012. https:\/\/homes.cs.washington.edu\/ suciu\/file37_paper.pdf On the tractability of query compilation and bounded treewidth. In ICDT. ACM 249--261.","DOI":"10.1145\/2274576.2274603"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9392-5"},{"key":"e_1_3_2_1_25_1","unstructured":"Mika\u00ebl Monet. 2019. https:\/\/cstheory.stackexchange.com\/q\/42626\/38111 Perfect matching of monotone Boolean function with null Euler characteristic. https:\/\/cstheory.stackexchange.com\/q\/42626\/38111  Mika\u00ebl Monet. 2019. https:\/\/cstheory.stackexchange.com\/q\/42626\/38111 Perfect matching of monotone Boolean function with null Euler characteristic. https:\/\/cstheory.stackexchange.com\/q\/42626\/38111"},{"key":"e_1_3_2_1_26_1","unstructured":"Mika\u00eb l Monet and Dan Olteanu. 2018. http:\/\/mikael-monet.net\/publications\/monet2018towards.pdf Towards deterministic decomposable circuits for safe queries. In AMW .  Mika\u00eb l Monet and Dan Olteanu. 2018. http:\/\/mikael-monet.net\/publications\/monet2018towards.pdf Towards deterministic decomposable circuits for safe queries. In AMW ."},{"key":"e_1_3_2_1_27_1","volume-title":"https:\/\/link.springer.com\/article\/10.1007\/BF01263419 On the degree of Boolean functions as real polynomials. Computational complexity","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan and Mario Szegedy . 1994. https:\/\/link.springer.com\/article\/10.1007\/BF01263419 On the degree of Boolean functions as real polynomials. Computational complexity , Vol. 4 , 4 ( 1994 ), 301--313. Noam Nisan and Mario Szegedy. 1994. https:\/\/link.springer.com\/article\/10.1007\/BF01263419 On the degree of Boolean functions as real polynomials. Computational complexity, Vol. 4, 4 (1994), 301--313."},{"key":"e_1_3_2_1_28_1","volume-title":"https:\/\/www.cs.ox.ac.uk\/people\/dan.olteanu\/papers\/oh-sum08.pdf Using OBDDs for efficient query evaluation on probabilistic databases","author":"Olteanu Dan","unstructured":"Dan Olteanu and Jiewen Huang . 2008. https:\/\/www.cs.ox.ac.uk\/people\/dan.olteanu\/papers\/oh-sum08.pdf Using OBDDs for efficient query evaluation on probabilistic databases . In SUM. Springer , 326--340. Dan Olteanu and Jiewen Huang. 2008. https:\/\/www.cs.ox.ac.uk\/people\/dan.olteanu\/papers\/oh-sum08.pdf Using OBDDs for efficient query evaluation on probabilistic databases. In SUM. Springer, 326--340."},{"key":"e_1_3_2_1_29_1","volume-title":"https:\/\/www.aaai.org\/Papers\/AAAI\/2008\/AAAI08-082.pdf New compilation languages based on structured decomposability","author":"Pipatsrisawat Knot","unstructured":"Knot Pipatsrisawat and Adnan Darwiche . 2008. https:\/\/www.aaai.org\/Papers\/AAAI\/2008\/AAAI08-082.pdf New compilation languages based on structured decomposability . In AAAI. AAAI Press , 517--522. Knot Pipatsrisawat and Adnan Darwiche. 2008. https:\/\/www.aaai.org\/Papers\/AAAI\/2008\/AAAI08-082.pdf New compilation languages based on structured decomposability. In AAAI. AAAI Press, 517--522."},{"key":"e_1_3_2_1_30_1","first-page":"985","article-title":"https:\/\/www.ijcai.org\/Proceedings\/03\/Papers\/142.pdf First-order probabilistic inference","volume":"3","author":"Poole David","year":"2003","unstructured":"David Poole . 2003 . https:\/\/www.ijcai.org\/Proceedings\/03\/Papers\/142.pdf First-order probabilistic inference . In IJCAI , Vol. 3. 985 -- 991 . David Poole. 2003. https:\/\/www.ijcai.org\/Proceedings\/03\/Papers\/142.pdf First-order probabilistic inference. In IJCAI, Vol. 3. 985--991.","journal-title":"IJCAI"},{"key":"e_1_3_2_1_31_1","unstructured":"RDBury. 2018. https:\/\/math.stackexchange.com\/a\/3039814\/378365 Uniqueness of minimal positive CNFs. https:\/\/math.stackexchange.com\/a\/3039814\/378365  RDBury. 2018. https:\/\/math.stackexchange.com\/a\/3039814\/378365 Uniqueness of minimal positive CNFs. https:\/\/math.stackexchange.com\/a\/3039814\/378365"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2012.07.003"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236253"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.29007\/h4p9"},{"key":"e_1_3_2_1_35_1","volume-title":"http:\/\/www-math.mit.edu\/rstan\/ec\/ec1.pdf Enumerative Combinatorics","author":"Stanley Richard P.","unstructured":"Richard P. Stanley . 2011. http:\/\/www-math.mit.edu\/rstan\/ec\/ec1.pdf Enumerative Combinatorics : Volume 1 2 nd ed.). Richard P. Stanley. 2011. http:\/\/www-math.mit.edu\/rstan\/ec\/ec1.pdf Enumerative Combinatorics: Volume 1 2nd ed.).","edition":"2"},{"key":"e_1_3_2_1_36_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_37_1","volume-title":"Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 137--146","author":"Vardi Moshe Y","year":"1982","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 Proceedings of the fourteenth annual ACM symposium on Theory of computing. 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 Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 137--146."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00297-X"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00129-6"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"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.3387642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375395.3387642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:32:48Z","timestamp":1750185168000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":39,"alternative-id":["10.1145\/3375395.3387642","10.1145\/3375395"],"URL":"https:\/\/doi.org\/10.1145\/3375395.3387642","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"}}]}}