{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T19:04:34Z","timestamp":1784574274333,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,2,3]],"date-time":"2018-02-03T00:00:00Z","timestamp":1517616000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1217099, CCF-1524246, IIS-1115188, IIS- 0911036, IIS-0915054"],"award-info":[{"award-number":["CCF-1217099, CCF-1524246, IIS-1115188, IIS- 0911036, IIS-0915054"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"<jats:p>\n                    We prove exponential lower bounds on the running time of the state-of-the-art exact model counting algorithms\u2014algorithms for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas. These algorithms can be seen, either directly or indirectly, as building\n                    <jats:italic toggle=\"yes\">Decision-Decomposable Negation Normal Form (decision-DNNF)<\/jats:italic>\n                    representations of the input Boolean formulas. Decision-DNNFs are a special case of\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    -DNNFs where\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    stands for\n                    <jats:italic toggle=\"yes\">deterministic<\/jats:italic>\n                    . We show that any knowledge compilation representations from a class (called DLDDs in this article) that contain decision-DNNFs can be converted into equivalent\n                    <jats:italic toggle=\"yes\">Free Binary Decision Diagrams (FBDDs)<\/jats:italic>\n                    , also known as\n                    <jats:italic toggle=\"yes\">Read-Once Branching Programs<\/jats:italic>\n                    , with only a quasi-polynomial increase in representation size. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs, which imply exponential lower bounds for model-counting algorithms. We also separate the power of decision-DNNFs from\n                    <jats:italic toggle=\"yes\">d<\/jats:italic>\n                    -DNNFs and a generalization of decision-DNNFs known as AND-FBDDs.\n                  <\/jats:p>\n                  <jats:p>\n                    We then prove new lower bounds for FBDDs that yield exponential lower bounds on the running time of these exact model counters when applied to the problem of query evaluation in tuple-independent probabilistic databases\u2014computing the probability of an answer to a query given independent probabilities of the individual tuples in a database instance. This approach to the query evaluation problem, in which one first obtains the lineage for the query and database instance as a Boolean formula and then performs weighted model counting on the lineage, is known as\n                    <jats:italic toggle=\"yes\">grounded inference<\/jats:italic>\n                    . A second approach, known as\n                    <jats:italic toggle=\"yes\">lifted inference<\/jats:italic>\n                    or\n                    <jats:italic toggle=\"yes\">extensional query evaluation<\/jats:italic>\n                    , exploits the high-level structure of the query as a first-order formula. Although it has been widely believed that lifted inference is strictly more powerful than grounded inference on the lineage alone, no formal separation has previously been shown for query evaluation. In this article, we show such a formal separation for the first time. In particular, we exhibit a family of database queries for which polynomial-time extensional query evaluation techniques were previously known but for which query evaluation via grounded inference using the state-of-the-art exact model counters requires exponential time.\n                  <\/jats:p>","DOI":"10.1145\/2984632","type":"journal-article","created":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T08:28:54Z","timestamp":1486715334000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Exact Model Counting of Query Expressions"],"prefix":"10.1145","volume":"42","author":[{"given":"Paul","family":"Beame","sequence":"first","affiliation":[{"name":"University of Washington, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"MIT, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,2,3]]},"reference":[{"issue":"1","key":"e_1_2_1_1_1","first-page":"1","volume":"1","year":"2014","unstructured":"2014. The SDD Package: Version 1.1.1. Retrieved January 31, 2014, from http:\/\/reasoning.cs.ucla.edu\/sdd\/.","journal-title":"The SDD Package: Version"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675141"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Fahiem Bacchus Shannon Dalmao and Toniann Pitassi. 2003. Algorithms and complexity results for #SAT and Bayesian inference. In FOCS. 340--351.","DOI":"10.5555\/946243.946291"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Roberto J. Bayardo Jr. and J. D. Pehoushek. 2000. Counting models using connected components. In AAAI. 157--162.","DOI":"10.5555\/647288.721114"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1714450.1714452"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622487.1622497"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Paul Beame Jerry Li Sudeepa Roy and Dan Suciu. 2013. Lower bounds for exact model counting and applications in probabilistic databases. In UAI.","DOI":"10.5555\/3023638.3023644"},{"key":"e_1_2_1_8_1","unstructured":"Paul Beame Jerry Li Sudeepa Roy and Dan Suciu. 2014. Counting of query expressions: Limitations of propositional methods. In ICDT. 177--188."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Paul Beame and Vincent Liew. 2015. New limits for knowledge compilation and applications to exact model counting. In UAI. 131--140.","DOI":"10.5555\/3020847.3020862"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745760"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00042-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502091"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.11.11-34"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283536"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622810.1622817"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855041"},{"key":"e_1_2_1_22_1","volume-title":"Handbook of Satisfiability","author":"Gomes Carla P.","unstructured":"Carla P. Gomes, Ashish Sabharwal, and Bart Selman. 2009. Model counting. In Handbook of Satisfiability. IOS Press, 633--654."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904487"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Jinbo Huang and Adnan Darwiche. 2005. DPLL with a trace: From SAT to knowledge compilation. In IJCAI. 156--162.","DOI":"10.5555\/1642293.1642318"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622606.1622613"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2nd International Workshop on Statistical Relational AI.","author":"Jaeger Manfred","year":"2012","unstructured":"Manfred Jaeger and Guy Van den Broeck. 2012. Liftability of probabilistic inference: Upper and lower bounds. In Proceedings of the 2nd International Workshop on Statistical Relational AI."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Abhay Kumar Jha and Dan Suciu. 2011. Knowledge compilation meets database theory: Compiling queries to decision diagrams. In ICDT. 162--173. 10.1145\/1938551.1938574","DOI":"10.1145\/1938551.1938574"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9392-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/295240.295933"},{"key":"e_1_2_1_30_1","unstructured":"William Joseph Masek. 1976. A Fast Algorithm for the String Editing Problem and Decision Graph Complexity. Master\u2019s thesis MIT."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30353-1_36"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0059-x"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-008-9060-1"},{"key":"e_1_2_1_34_1","unstructured":"Tian Sang Fahiem Bacchus Paul Beame Henry A. Kautz and Toniann Pitassi. 2004. Combining component caching and clause learning for effective model counting. In SAT."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Richard P. Stanley. 1997. Enumerative Combinatorics. Cambridge University Press.","DOI":"10.1017\/CBO9780511805967"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. 2011. Probabilistic Databases. Morgan 8 Claypool.","DOI":"10.5555\/2031527"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Marc Thurley. 2006. sharpSAT: Counting models with advanced component caching and implicit BCP. In SAT. 424--429. 10.1007\/11814948_38","DOI":"10.1007\/11814948_38"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986614"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Guy Van den Broeck Wannes Meert and Adnan Darwiche. 2014. Skolemization for weighted first-order model counting. In KR.","DOI":"10.5555\/3031929.3031944"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/355481"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2984632","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2984632","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2984632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:23:32Z","timestamp":1763457812000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2984632"}},"subtitle":["Limitations of Propositional Methods"],"short-title":[],"issued":{"date-parts":[[2017,2,3]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/2984632"],"URL":"https:\/\/doi.org\/10.1145\/2984632","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,3]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}