{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T22:39:11Z","timestamp":1783204751825,"version":"3.54.6"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0713576 and IIS-1115188"],"award-info":[{"award-number":["IIS-0713576 and IIS-1115188"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>We study the complexity of computing a query on a probabilistic database. We consider unions of conjunctive queries, UCQ, which are equivalent to positive, existential First Order Logic sentences, and also to nonrecursive datalog programs. The tuples in the database are independent random events. We prove the following dichotomy theorem. For every UCQ query, either its probability can be computed in polynomial time in the size of the database, or is #P-hard. Our result also has applications to the problem of computing the probability of positive, Boolean expressions, and establishes a dichotomy for such classes based on their structure. For the tractable case, we give a very simple algorithm that alternates between two steps: applying the inclusion\/exclusion formula, and removing one existential variable. A key and novel feature of this algorithm is that it avoids computing terms that cancel out in the inclusion\/exclusion formula, in other words it only computes those terms whose Mobius function in an appropriate lattice is nonzero. We show that this simple feature is a key ingredient needed to ensure completeness. For the hardness proof, we give a reduction from the counting problem for positive, partitioned 2CNF, which is known to be #P-complete. The hardness proof is nontrivial, and combines techniques from logic, classical algebra, and analysis.<\/jats:p>","DOI":"10.1145\/2395116.2395119","type":"journal-article","created":{"date-parts":[[2013,1,8]],"date-time":"2013-01-08T15:34:16Z","timestamp":1357659256000},"page":"1-87","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":76,"title":["The dichotomy of probabilistic inference for unions of conjunctive queries"],"prefix":"10.1145","volume":"59","author":[{"given":"Nilesh","family":"Dalvi","sequence":"first","affiliation":[{"name":"Facebook, Menlo Park, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison Wesley Publishing Co. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison Wesley Publishing Co."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Conference very Large Databases. 71--81","author":"Cavallo R.","unstructured":"Cavallo , R. and Pittarelli , M . 1987. The theory of probabilistic databases . In Proceedings of the Conference very Large Databases. 71--81 . Cavallo, R. and Pittarelli, M. 1987. The theory of probabilistic databases. In Proceedings of the Conference very Large Databases. 71--81."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807113"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Dalvi N.","unstructured":"Dalvi , N. and Suciu , D . 2004. Efficient query evaluation on probabilistic databases . In Proceedings of the International Conference on Very Large Databases (VLDB). Dalvi, N. and Suciu, D. 2004. Efficient query evaluation on probabilistic databases. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Dalvi N. N. and Suciu D. 2006. The dichotomy of conjunctive queries on probabilistic structures. CoRR abs\/cs\/0612102. Dalvi N. N. and Suciu D. 2006. The dichotomy of conjunctive queries on probabilistic structures. CoRR abs\/cs\/0612102.","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_2_1_10_1","unstructured":"Darwiche A. 2000. On the tractable counting of theory models and its application to belief revision and truth maintenance. CoRR cs.AI\/0003044. Darwiche A. 2000. On the tractable counting of theory models and its application to belief revision and truth maintenance. CoRR cs.AI\/0003044."},{"key":"e_1_2_1_11_1","volume-title":"Modeling and Reasoning with Bayesian Networks","author":"Darwiche A.","unstructured":"Darwiche , A. 2009. Modeling and Reasoning with Bayesian Networks . Cambridge University Press . Darwiche, A. 2009. Modeling and Reasoning with Bayesian Networks. Cambridge University Press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622810.1622817"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the of the International Joint Conference on Artificial Intelligence (IJCAI). 1319--1125","author":"de Salvo Braz R.","unstructured":"de Salvo Braz , R. , Amir , E. , and Roth , D . 2005. Lifted first-order probabilistic inference . In Proceedings of the of the International Joint Conference on Artificial Intelligence (IJCAI). 1319--1125 . de Salvo Braz, R., Amir, E., and Roth, D. 2005. Lifted first-order probabilistic inference. In Proceedings of the of the International Joint Conference on Artificial Intelligence (IJCAI). 1319--1125."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01549-6","volume-title":"Markov Logic: An Interface Layer for Artificial Intelligence. Synthesis Lectures on Artificial Intelligence and Machine Learning","author":"Domingos P.","year":"2009","unstructured":"Domingos , P. and Lowd , D . 2009 . Markov Logic: An Interface Layer for Artificial Intelligence. Synthesis Lectures on Artificial Intelligence and Machine Learning , Morgan & Claypool Publishers . Domingos, P. and Lowd, D. 2009. Markov Logic: An Interface Layer for Artificial Intelligence. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.09.016"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Gomes C. P. Sabharwal A. and Selman B. 2009. Model counting. In Handbook of Satisfiability 633--654. Gomes C. P. Sabharwal A. and Selman B. 2009. Model counting. In Handbook of Satisfiability 633--654.","DOI":"10.3233\/978-1-58603-929-5-633"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.295124"},{"key":"e_1_2_1_18_1","first-page":"183","article-title":"Repetition-free Boolean functions","volume":"32","author":"Gurvich V.","year":"1977","unstructured":"Gurvich , V. 1977 . Repetition-free Boolean functions . Uspekhi Mat. Nauk 32 , 183 -- 184 . Gurvich, V. 1977. Repetition-free Boolean functions. Uspekhi Mat. Nauk 32, 183--184.","journal-title":"Uspekhi Mat. Nauk"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938574"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2004.11.039"},{"key":"e_1_2_1_21_1","unstructured":"Krattenthaler C. 1999. Advanced determinant calculus. Seminaire Lotharingien Combin 42 (The Andrews Festschrift) 1--66. Article B42q. Krattenthaler C. 1999. Advanced determinant calculus. Seminaire Lotharingien Combin 42 (The Andrews Festschrift) 1--66. Article B42q."},{"key":"e_1_2_1_22_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"Libkin , L. 2004. Elements of Finite Model Theory . Springer . Libkin, L. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559887"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.123"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Artificial Intelligence (AAAI). 913--918","author":"Poon H.","unstructured":"Poon , H. and Domingos , P . 2007. Joint inference in information extraction . In Proceedings of the International Conference on Artificial Intelligence (AAAI). 913--918 . Poon, H. and Domingos, P. 2007. Joint inference in information extraction. In Proceedings of the International Conference on Artificial Intelligence (AAAI). 913--918."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Annual Meaning of the Assocation Per Computational Linguistics (ACL). 296--305","author":"Poon H.","unstructured":"Poon , H. and Domingos , P . 2010. Unsupervised ontology induction from text . In Proceedings of the Annual Meaning of the Assocation Per Computational Linguistics (ACL). 296--305 . Poon, H. and Domingos, P. 2010. Unsupervised ontology induction from text. In Proceedings of the Annual Meaning of the Assocation Per Computational Linguistics (ACL). 296--305."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497511"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Sen P.","unstructured":"Sen , P. and Deshpande , A . 2007. Representing and querying correlated tuples in probabilistic databases . In Proceedings of the International Conference on Data Engineering (ICDE). Sen, P. and Deshpande, A. 2007. Representing and querying correlated tuples in probabilistic databases. In Proceedings of the International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.65"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Stanley R. P. 1997. Enumerative Combinatorics. Cambridge University Press. Stanley R. P. 1997. Enumerative Combinatorics. Cambridge University Press.","DOI":"10.1017\/CBO9780511805967"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Suciu D. Olteanu D. R\u00e9 C. and Koch C. 2011. Probabilistic Databases. Synthesis Lectures on Data Management Morgan & Claypool Publishers. Suciu D. Olteanu D. R\u00e9 C. and Koch C. 2011. Probabilistic Databases. Synthesis Lectures on Data Management Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-01879-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Wegener I. 2000. Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM. Wegener I. 2000. Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM.","DOI":"10.1137\/1.9780898719789"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00297-X"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2395116.2395119","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2395116.2395119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:56Z","timestamp":1750239296000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2395116.2395119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2395116.2395119"],"URL":"https:\/\/doi.org\/10.1145\/2395116.2395119","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}