{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T15:10:47Z","timestamp":1766848247234,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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-0915054 and IIS-1115188"],"award-info":[{"award-number":["IIS-0915054 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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            This article develops upper and lower bounds for the probability of Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach\n            <jats:italic>dissociation<\/jats:italic>\n            and give an exact characterization of\n            <jats:italic>optimal oblivious bounds<\/jats:italic>\n            , that is, when the new probabilities are chosen independently of the probabilities of all other variables. Our motivation comes from the\n            <jats:italic>weighted model counting<\/jats:italic>\n            problem (or, equivalently, the problem of computing the probability of a Boolean function), which is #P-hard in general. By performing several dissociations, one can transform a Boolean formula whose probability is difficult to compute into one whose probability is easy to compute, and which is guaranteed to provide an upper or lower bound on the probability of the original formula by choosing appropriate probabilities for the dissociated variables. Our new bounds shed light on the connection between previous relaxation-based and model-based approximations and unify them as concrete choices in a larger design space. We also show how our theory allows a standard relational database management system (DBMS) to both upper and lower bound hard probabilistic queries in guaranteed polynomial time.\n          <\/jats:p>","DOI":"10.1145\/2532641","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Oblivious bounds on the probability of boolean functions"],"prefix":"10.1145","volume":"39","author":[{"given":"Wolfgang","family":"Gatterbauer","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle"}]}],"member":"320","published-online":{"date-parts":[[2014,1,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1771668.1771682"},{"key":"e_1_2_1_2_1","volume-title":"Willem-Jan Van Hoeve, and John N. Hooker","author":"Bergman David","year":"2013","unstructured":"David Bergman , Andre. A. Cire , Willem-Jan Van Hoeve, and John N. Hooker . 2013 . Optimization bounds from binary decision diagrams. INFORMS J. Comput. To appear. David Bergman, Andre. A. Cire, Willem-Jan Van Hoeve, and John N. Hooker. 2013. Optimization bounds from binary decision diagrams. INFORMS J. Comput. To appear."},{"volume-title":"Proceedings of the 8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'11)","author":"Bergman David","key":"e_1_2_1_3_1","unstructured":"David Bergman , Willem Jan van Hoeve , and John N. Hooker . 2011. Manipulating MDD relaxations for combinatorial optimization . In Proceedings of the 8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'11) . 20--35. David Bergman, Willem Jan van Hoeve, and John N. Hooker. 2011. Manipulating MDD relaxations for combinatorial optimization. In Proceedings of the 8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'11). 20--35."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.11.002"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 23rd Conference in Uncertainty in Artificial Intelligence (UAI'07)","author":"Choi Arthur","year":"2007","unstructured":"Arthur Choi , Mark Chavira , and Adnan Darwiche . 2007 . Node Splitting: A scheme for generating upper bounds in bayesian networks . In Proceedings of the 23rd Conference in Uncertainty in Artificial Intelligence (UAI'07) . 57--66. Arthur Choi, Mark Chavira, and Adnan Darwiche. 2007. Node Splitting: A scheme for generating upper bounds in bayesian networks. In Proceedings of the 23rd Conference in Uncertainty in Artificial Intelligence (UAI'07). 57--66."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS'09)","author":"Choi Arthur","year":"2009","unstructured":"Arthur Choi and Adnan Darwiche . 2009 . Relax then compensate: On max-product belief propagation and more . In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS'09) . 351--359. Arthur Choi and Adnan Darwiche. 2009. Relax then compensate: On max-product belief propagation and more. In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS'09). 351--359."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25655-4_16"},{"key":"e_1_2_1_8_1","unstructured":"Arthur Choi and Adnan Darwiche. 2011. Personal communication.  Arthur Choi and Adnan Darwiche. 2011. Personal communication."},{"key":"e_1_2_1_9_1","volume-title":"Hammer","author":"Crama Yves","year":"2011","unstructured":"Yves Crama and Peter L . Hammer . 2011 . Boolean Functions : Theory, Algorithms, and Applications. Cambridge University Press . Yves Crama and Peter L. Hammer. 2011. Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807113"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622810.1622817"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636866"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.209"},{"key":"e_1_2_1_15_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller William","unstructured":"William Feller . 1968. An Introduction to Probability Theory and Its Applications 3 rd Ed. Wiley , New York . William Feller. 1968. An Introduction to Probability Theory and Its Applications 3rd Ed. Wiley, New York.","edition":"3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938575"},{"volume-title":"Proceedings of the Conference on Advances in Neural Information Systems (NIPS97)","author":"Brendan","key":"e_1_2_1_17_1","unstructured":"Brendan J. Frey and David J. C. MacKay. 1997. A revolution: Belief propagation in graphs with cycles . In Proceedings of the Conference on Advances in Neural Information Systems (NIPS97) . Brendan J. Frey and David J. C. MacKay. 1997. A revolution: Belief propagation in graphs with cycles. In Proceedings of the Conference on Advances in Neural Information Systems (NIPS97)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 4th International VLDB workshop on Management of Uncertain Data (MUD'10)","author":"Gatterbauer Wolfgang","year":"2010","unstructured":"Wolfgang Gatterbauer , Abhay K. Jha , and Dan Suciu . 2010 . Dissociation and propagation for efficient query evaluation over probabilistic databases . In Proceedings of the 4th International VLDB workshop on Management of Uncertain Data (MUD'10) . 83--97. Wolfgang Gatterbauer, Abhay K. Jha, and Dan Suciu. 2010. Dissociation and propagation for efficient query evaluation over probabilistic databases. In Proceedings of the 4th International VLDB workshop on Management of Uncertain Data (MUD'10). 83--97."},{"key":"e_1_2_1_20_1","unstructured":"Wolfgang Gatterbauer and Dan Suciu. 2011. Optimal upper and lower bounds for boolean expressions by dissociation. http:\/\/arxiv.org\/abs\/1105.2813arXiv:1105.2813 {cs.AI}.  Wolfgang Gatterbauer and Dan Suciu. 2011. Optimal upper and lower bounds for boolean expressions by dissociation. http:\/\/arxiv.org\/abs\/1105.2813arXiv:1105.2813 {cs.AI}."},{"key":"e_1_2_1_21_1","unstructured":"Wolfgang Gatterbauer and Dan Suciu. 2013. Dissociation and propagation for efficient query evaluation over probabilistic databases. http:\/\/arxiv.org\/abs\/1310.6257arXiv:1310.6257 {cs.DB}.  Wolfgang Gatterbauer and Dan Suciu. 2013. Dissociation and propagation for efficient query evaluation over probabilistic databases. http:\/\/arxiv.org\/abs\/1310.6257arXiv:1310.6257 {cs.DB}."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.10.009"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 26th Conference in Uncertainty in Artificial Intelligence (UAI'10)","author":"Gogate Vibhav","year":"2010","unstructured":"Vibhav Gogate and Pedro Domingos . 2010 . Formula-Based Probabilistic Inference . In Proceedings of the 26th Conference in Uncertainty in Artificial Intelligence (UAI'10) . 210--219. Vibhav Gogate and Pedro Domingos. 2010. Formula-Based Probabilistic Inference. In Proceedings of the 26th Conference in Uncertainty in Artificial Intelligence (UAI'10). 210--219."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 27th Conference in Uncertainty in Artificial Intelligence (UAI'11)","author":"Gogate Vibhav","year":"2011","unstructured":"Vibhav Gogate and Pedro Domingos . 2011 . Approximation by quantization . In Proceedings of the 27th Conference in Uncertainty in Artificial Intelligence (UAI'11) . 247--255. Vibhav Gogate and Pedro Domingos. 2011. Approximation by quantization. In Proceedings of the 27th Conference in Uncertainty in Artificial Intelligence (UAI'11). 247--255."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 29th Conference in Uncertainty in Artificial Intelligence (UAI'13)","author":"Gogate Vibhav","year":"2013","unstructured":"Vibhav Gogate and Pedro Domingos . 2013 . Structured message passing . In Proceedings of the 29th Conference in Uncertainty in Artificial Intelligence (UAI'13) . 252--261. Vibhav Gogate and Pedro Domingos. 2013. Structured message passing. In Proceedings of the 29th Conference in Uncertainty in Artificial Intelligence (UAI'13). 252--261."},{"key":"e_1_2_1_26_1","first-page":"183","article-title":"Repetition-free Boolean functions","volume":"32","author":"Gurvich Vladimiar A.","year":"1977","unstructured":"Vladimiar A. Gurvich . 1977 . Repetition-free Boolean functions . Uspekhi Mat. Nauk 32 , 183 -- 184 . Vladimiar A. Gurvich. 1977. Repetition-free Boolean functions. Uspekhi Mat. Nauk 32, 183--184.","journal-title":"Uspekhi Mat. Nauk"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376686"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739082"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447879"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.123"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447826"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781238.1781268"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90061-F"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1771668.1771714"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920975"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems 13 (NIPS'00)","author":"St-Aubin Robert","year":"2000","unstructured":"Robert St-Aubin , Jesse Hoey , and Craig Boutilier . 2000 . APRICODD: Approximate policy construction using decision diagrams . In Proceedings of the Conference on Advances in Neural Information Processing Systems 13 (NIPS'00) . 1089--1095. Robert St-Aubin, Jesse Hoey, and Craig Boutilier. 2000. APRICODD: Approximate policy construction using decision diagrams. In Proceedings of the Conference on Advances in Neural Information Processing Systems 13 (NIPS'00). 1089--1095."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283696.2283762"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2532641","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2532641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:05Z","timestamp":1750278125000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2532641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2532641"],"URL":"https:\/\/doi.org\/10.1145\/2532641","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}