{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T13:25:24Z","timestamp":1791120324115,"version":"4.1.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>Most of the work on query evaluation in probabilistic databases has focused on the simple tuple-independent data model, where tuples are independent random events. Several efficient query evaluation techniques exists in this setting, such as safe plans, algorithms based on OBDDs, tree-decomposition and a variety of approximation algorithms. However, complex data analytics tasks often require complex correlations, and query evaluation then is significantly more expensive, or more restrictive.<\/jats:p>\n          <jats:p>In this paper, we propose MVDB as a framework both for representing complex correlations and for efficient query evaluation. An MVDB specifies correlations by views, called MarkoViews, on the probabilistic relations and declaring the weights of the view's outputs. An MVDB is a (very large) Markov Logic Network. We make two sets of contributions. First, we show that query evaluation on an MVDB is equivalent to evaluating a Union of Conjunctive Query(UCQ) over a tuple-independent database. The translation is exact (thus allowing the techniques developed for tuple independent databases to be carried over to MVDB), yet it is novel and quite non-obvious (some resulting probabilities may be negative!).<\/jats:p>\n          <jats:p>This translation in itself though may not lead to much gain since the translated query gets complicated as we try to capture more correlations. Our second contribution is to propose a new query evaluation strategy that exploits offline compilation to speed up online query evaluation. Here we utilize and extend our prior work on compilation of UCQ. We validate experimentally our techniques on a large probabilistic database with MarkoViews inferred from the DBLP data.<\/jats:p>","DOI":"10.14778\/2350229.2350236","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1160-1171","source":"Crossref","is-referenced-by-count":33,"title":["Probabilistic databases with MarkoViews"],"prefix":"10.14778","volume":"5","author":[{"given":"Abhay","family":"Jha","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}],"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":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497507"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100022398"},{"key":"e_1_2_1_3_1","volume-title":"The good old davis-putnam procedure helps counting models. J. Artif. Intell. Res. (JAIR), 10(1):457--477","author":"Birnbaum E.","year":"1999","unstructured":"E. Birnbaum and E. L. Lozinskii . The good old davis-putnam procedure helps counting models. J. Artif. Intell. Res. (JAIR), 10(1):457--477 , 1999 . E. Birnbaum and E. L. Lozinskii. The good old davis-putnam procedure helps counting models. J. Artif. Intell. Res. (JAIR), 10(1):457--477, 1999."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066277"},{"key":"e_1_2_1_5_1","first-page":"688","volume-title":"DAC","author":"Bryant R. E.","year":"1985","unstructured":"R. E. Bryant . Symbolic manipulation of boolean functions using a graphical representation . In DAC , pages 688 -- 694 , 1985 . R. E. Bryant. Symbolic manipulation of boolean functions using a graphical representation. In DAC, pages 688--694, 1985."},{"key":"e_1_2_1_6_1","volume-title":"Interpretations of negative probabilities. CoRR, arXiv:1008.1287v1","author":"Burgin M.","year":"2010","unstructured":"M. Burgin . Interpretations of negative probabilities. CoRR, arXiv:1008.1287v1 , 2010 . M. Burgin. Interpretations of negative probabilities. CoRR, arXiv:1008.1287v1, 2010."},{"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\/1807085.1807113"},{"key":"e_1_2_1_9_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. Morgan &amp","author":"Domingos P.","year":"2009","unstructured":"P. Domingos and D. Lowd . Markov Logic: An Interface Layer for Artificial Intelligence. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan &amp ; Claypool Publishers , 2009 . P. Domingos and D. Lowd. Markov Logic: An Interface Layer for Artificial Intelligence. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan &amp; Claypool Publishers, 2009."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90315-S"},{"key":"e_1_2_1_11_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 , pages 83 -- 97 , 2010 . W. Gatterbauer, A. K. Jha, and D. Suciu. Dissociation and propagation for efficient query evaluation over probabilistic databases. In MUD, pages 83--97, 2010."},{"key":"e_1_2_1_12_1","first-page":"256","volume-title":"UAI","author":"Gogate V.","year":"2011","unstructured":"V. Gogate and P. Domingos . Probabilistic theorem proving . In UAI , pages 256 -- 265 , 2011 . V. Gogate and P. Domingos. Probabilistic theorem proving. In UAI, pages 256--265, 2011."},{"key":"e_1_2_1_13_1","unstructured":"E. G. Haug. Why so negative to negative probabilities? Wilmott Magazine http:\/\/www.wilmott.com\/article.cfm?PageNum_rsQueryArticlesMain=3&NoCookies=Yes&forumid=1 2011.  E. G. Haug. Why so negative to negative probabilities? Wilmott Magazine http:\/\/www.wilmott.com\/article.cfm?PageNum_rsQueryArticlesMain=3&NoCookies=Yes&forumid=1 2011."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11527695_13"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938574"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807241"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453894"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102407"},{"key":"e_1_2_1_19_1","unstructured":"M. Ley. The dblp computer science bibliography. http:\/\/www.informatik.uni-trier.de\/~ley\/db\/.  M. Ley. The dblp computer science bibliography. http:\/\/www.informatik.uni-trier.de\/~ley\/db\/."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559887"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.123"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447826"},{"key":"e_1_2_1_25_1","first-page":"458","volume-title":"AAAI","author":"Poon H.","year":"2006","unstructured":"H. Poon and P. Domingos . Sound and efficient inference with probabilistic and deterministic dependencies . In AAAI , pages 458 -- 463 , 2006 . H. Poon and P. Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In AAAI, pages 458--463, 2006."},{"key":"e_1_2_1_26_1","first-page":"913","volume-title":"AAAI","author":"Poon H.","year":"2007","unstructured":"H. Poon and P. Domingos . Joint inference in information extraction . In AAAI , pages 913 -- 918 , 2007 . H. Poon and P. Domingos. Joint inference in information extraction. In AAAI, pages 913--918, 2007."},{"key":"e_1_2_1_27_1","first-page":"296","volume-title":"ACL","author":"Poon H.","year":"2010","unstructured":"H. Poon and P. Domingos . Unsupervised ontology induction from text . In ACL , pages 296 -- 305 , 2010 . H. Poon and P. Domingos. Unsupervised ontology induction from text. In ACL, pages 296--305, 2010."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_30_1","first-page":"868","volume-title":"AAAI","author":"Singla P.","year":"2005","unstructured":"P. Singla and P. Domingos . Discriminative training of markov logic networks . In AAAI , pages 868 -- 873 , 2005 . P. Singla and P. Domingos. Discriminative training of markov logic networks. In AAAI, pages 868--873, 2005."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.65"},{"key":"e_1_2_1_32_1","unstructured":"F. Somenzi. CUDD: CU Decision Diagram Package Release 2.4.2. http:\/\/vlsi.colorado.edu\/~fabio\/CUDD\/ 2011.  F. Somenzi. CUDD: CU Decision Diagram Package Release 2.4.2. http:\/\/vlsi.colorado.edu\/~fabio\/CUDD\/ 2011."},{"key":"e_1_2_1_33_1","volume-title":"Probabilistic Databases. Synthesis Lectures on Data Management. Morgan &amp","author":"Suciu D.","year":"2011","unstructured":"D. Suciu , D. Olteanu , C. R\u00e9 , and C. Koch . Probabilistic Databases. Synthesis Lectures on Data Management. Morgan &amp ; Claypool Publishers , 2011 . D. Suciu, D. Olteanu, C. R\u00e9, and C. Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan &amp; Claypool Publishers, 2011."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989378"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00297-X"},{"issue":"1","key":"e_1_2_1_36_1","first-page":"794","article-title":"Scalable probabilistic databases with factor graphs and mcmc","volume":"3","author":"Wick M. L.","year":"2010","unstructured":"M. L. Wick , A. McCallum , and G. Miklau . Scalable probabilistic databases with factor graphs and mcmc . PVLDB , 3 ( 1 ): 794 -- 804 , 2010 . M. L. Wick, A. McCallum, and G. Miklau. Scalable probabilistic databases with factor graphs and mcmc. PVLDB, 3(1):794--804, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_37_1","unstructured":"Alchemy - Open Source AI. http:\/\/alchemy.cs.washington.edu\/.  Alchemy - Open Source AI. http:\/\/alchemy.cs.washington.edu\/."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:25:51Z","timestamp":1672226751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":37,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350236"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350236","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}