{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:38:19Z","timestamp":1703187499802},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>This paper proposes a new approach for approximate evaluation of #P-hard queries with probabilistic databases. In our approach, every query is evaluated entirely in the database engine by evaluating a fixed number of query plans, each providing an upper bound on the true probability, then taking their minimum. We provide an algorithm that takes into account important schema information to enumerate only the minimal necessary plans among all possible plans. Importantly, this algorithm is a strict generalization of all known results of PTIME self-join-free conjunctive queries: A query is safe if and only if our algorithm returns one single plan. We also apply three relational query optimization techniques to evaluate all minimal safe plans very fast. We give a detailed experimental evaluation of our approach and, in the process, provide a new way of thinking about the value of probabilistic methods over non-probabilistic methods for ranking query answers.<\/jats:p>","DOI":"10.14778\/2735479.2735494","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"629-640","source":"Crossref","is-referenced-by-count":11,"title":["Approximate lifted inference with probabilistic databases"],"prefix":"10.14778","volume":"8","author":[{"given":"Wolfgang","family":"Gatterbauer","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"320","published-online":{"date-parts":[[2015,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43984-5_27"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497507"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.369042"},{"key":"e_1_2_1_4_1","first-page":"177","volume-title":"ICDT","author":"Beame P.","year":"2014","unstructured":"P. Beame , J. Li , S. Roy , and D. Suciu . Model counting of query expressions: Limitations of propositional methods . In ICDT , pp. 177 -- 188 , 2014 . P. Beame, J. Li, S. Roy, and D. Suciu. Model counting of query expressions: Limitations of propositional methods. In ICDT, pp. 177--188, 2014."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2898607.2898816"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610516"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_9_1","unstructured":"DeepDive: http:\/\/deepdive.stanford.edu\/.  DeepDive: http:\/\/deepdive.stanford.edu\/."},{"key":"e_1_2_1_10_1","first-page":"131","article-title":"Lifted relax, compensate and then recover: From approximate to exact lifted probabilistic inference","author":"den Broeck G. V.","year":"2012","unstructured":"G. V. den Broeck , A. Choi , and A. Darwiche . Lifted relax, compensate and then recover: From approximate to exact lifted probabilistic inference . In UAI , pp. 131 -- 141 , 2012 . G. V. den Broeck, A. Choi, and A. Darwiche. Lifted relax, compensate and then recover: From approximate to exact lifted probabilistic inference. In UAI, pp. 131--141, 2012.","journal-title":"UAI"},{"key":"e_1_2_1_11_1","volume-title":"UAI tutorials","author":"den Broeck G. V.","year":"2014","unstructured":"G. V. den Broeck and D. Suciu . Lifted probabilistic inference in relational models . In UAI tutorials , 2014 . G. V. den Broeck and D. Suciu. Lifted probabilistic inference in relational models. In UAI tutorials, 2014."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283696.2283762"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855041"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623623"},{"key":"e_1_2_1_15_1","volume-title":"UAI","author":"Ermis B.","year":"2014","unstructured":"B. Ermis and G. Bouchard . Scalable binary tensor factorization . In UAI , 2014 . B. Ermis and G. Bouchard. Scalable binary tensor factorization. In UAI, 2014."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938575"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594549"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"issue":"5","key":"e_1_2_1_19_1","first-page":"1406","article-title":"Linearized and single-pass belief propagation","volume":"8","author":"Gatterbauer W.","year":"2015","unstructured":"W. Gatterbauer , S. G\u00fcnnemann , D. Koutra , and C. Faloutsos . Linearized and single-pass belief propagation . PVLDB , 8 ( 5 ), 2015 . (CoRR abs\/ 1406 .7288). W. Gatterbauer, S. G\u00fcnnemann, D. Koutra, and C. Faloutsos. Linearized and single-pass belief propagation. PVLDB, 8(5), 2015. (CoRR abs\/1406.7288).","journal-title":"PVLDB"},{"key":"e_1_2_1_20_1","first-page":"83","volume-title":"MUD","author":"Gatterbauer W.","year":"2010","unstructured":"W. Gatterbauer , A. K. Jha , and D. Suciu . Dissociation and propagation for efficient query evaluation over probabilistic databases . In MUD , pp. 83 -- 97 , 2010 . W. Gatterbauer, A. K. Jha, and D. Suciu. Dissociation and propagation for efficient query evaluation over probabilistic databases. In MUD, pp. 83--97, 2010."},{"key":"e_1_2_1_21_1","volume-title":"Dissociation and propagation for efficient query evaluation over probabilistic databases. CoRR abs\/1310.6257","author":"Gatterbauer W.","year":"2013","unstructured":"W. Gatterbauer and D. Suciu . Dissociation and propagation for efficient query evaluation over probabilistic databases. CoRR abs\/1310.6257 , 2013 . W. Gatterbauer and D. Suciu. Dissociation and propagation for efficient query evaluation over probabilistic databases. CoRR abs\/1310.6257, 2013."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2532641"},{"key":"e_1_2_1_23_1","first-page":"210","article-title":"Formula-based probabilistic inference","author":"Gogate V.","year":"2010","unstructured":"V. Gogate and P. Domingos . Formula-based probabilistic inference . In UAI , pp. 210 -- 219 , 2010 . V. Gogate and P. Domingos. Formula-based probabilistic inference. In UAI, pp. 210--219, 2010.","journal-title":"UAI"},{"key":"e_1_2_1_24_1","first-page":"256","article-title":"Probabilistic theorem proving","author":"Gogate V.","year":"2011","unstructured":"V. Gogate and P. Domingos . Probabilistic theorem proving . In UAI , pp. 256 -- 265 , 2011 . V. Gogate and P. Domingos. Probabilistic theorem proving. In UAI, pp. 256--265, 2011.","journal-title":"UAI"},{"key":"e_1_2_1_25_1","first-page":"633","volume-title":"Handbook of Satisfiability","author":"Gomes C. P.","year":"2009","unstructured":"C. P. Gomes , A. Sabharwal , and B. Selman . Model counting . In Handbook of Satisfiability , pp. 633 -- 654 . 2009 . C. P. Gomes, A. Sabharwal, and B. Selman. Model counting. In Handbook of Satisfiability, pp. 633--654. 2009."},{"key":"e_1_2_1_26_1","volume-title":"KR","author":"Guy Van den Broeck A. D.","year":"2014","unstructured":"A. D. Guy Van den Broeck , Wannes Meert . Skolemization for weighted first-order model counting . In KR , 2014 . A. D. Guy Van den Broeck, Wannes Meert. Skolemization for weighted first-order model counting. In KR, 2014."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.06.001"},{"key":"e_1_2_1_28_1","volume-title":"StaRAI","author":"Jaeger M.","year":"2012","unstructured":"M. Jaeger and G. V. den Broeck . Liftability of probabilistic inference: Upper and lower bounds . In StaRAI , 2012 . M. Jaeger and G. V. den Broeck. Liftability of probabilistic inference: Upper and lower bounds. In StaRAI, 2012."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376686"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739082"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350236"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0095-0"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447879"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1394399"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1793274.1793325"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_2_1_37_1","unstructured":"OEIS\n  : The on-line encyclopedia of integer sequences: http:\/\/oeis.org\/.  OEIS: The on-line encyclopedia of integer sequences: http:\/\/oeis.org\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.123"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447826"},{"key":"e_1_2_1_41_1","volume-title":"networks of plausible inference","author":"Pearl J.","year":"1988","unstructured":"J. Pearl . Probabilistic reasoning in intelligent systems : networks of plausible inference . Morgan Kaufmann Publishers , 1988 . J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann Publishers, 1988."},{"key":"e_1_2_1_42_1","first-page":"985","volume-title":"IJCAI","author":"Poole D.","year":"2003","unstructured":"D. Poole . First-order probabilistic inference . In IJCAI , pp. 985 -- 991 , 2003 . D. Poole. First-order probabilistic inference. In IJCAI, pp. 985--991, 2003."},{"key":"e_1_2_1_43_1","unstructured":"PostgreSQL 9.2: http:\/\/www.postgresql.org\/download\/.  PostgreSQL 9.2: http:\/\/www.postgresql.org\/download\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453943"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938582"},{"key":"e_1_2_1_47_1","unstructured":"SampleSearch: http:\/\/www.hlt.utdallas.edu\/~vgogate\/SampleSearch.html.  SampleSearch: http:\/\/www.hlt.utdallas.edu\/~vgogate\/SampleSearch.html."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367905"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920975"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401969"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767854"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_2_1_54_1","unstructured":"TPC-H benchmark: http:\/\/www.tpc.org\/tpch\/.  TPC-H benchmark: http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463702"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735479.2735494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:20:50Z","timestamp":1672226450000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735479.2735494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":56,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.14778\/2735479.2735494"],"URL":"https:\/\/doi.org\/10.14778\/2735479.2735494","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}