{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:55:44Z","timestamp":1766138144544,"version":"3.40.5"},"reference-count":79,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T00:00:00Z","timestamp":1667952000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide a framework for probabilistic reasoning in Vadalog-based Knowledge Graphs (KGs), satisfying the requirements of ontological reasoning: full recursion, powerful existential quantification, expression of inductive definitions. Vadalog is a Knowledge Representation and Reasoning (KRR) language based on Warded Datalog+\/\u2013, a logical core language of existential rules, with a good balance between computational complexity and expressive power. Handling uncertainty is essential for reasoning with KGs. Yet Vadalog and Warded Datalog+\/\u2013 are not covered by the existing probabilistic logic programming and statistical relational learning approaches for several reasons, including insufficient support for recursion with existential quantification and the impossibility to express inductive definitions. In this work, we introduce Soft Vadalog, a probabilistic extension to Vadalog, satisfying these desiderata. A Soft Vadalog program induces what we call a Probabilistic Knowledge Graph (PKG), which consists of a probability distribution on a network of chase instances, structures obtained by grounding the rules over a database using the chase procedure. We exploit PKGs for probabilistic marginal inference. We discuss the theory and present MCMC-chase, a Monte Carlo method to use Soft Vadalog in practice. We apply our framework to solve data management and industrial problems and experimentally evaluate it in the Vadalog system.<\/jats:p>","DOI":"10.1017\/s1471068422000412","type":"journal-article","created":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T09:22:34Z","timestamp":1667985754000},"page":"507-534","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Swift Markov Logic for Probabilistic Reasoning on Knowledge Graphs"],"prefix":"10.1017","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6863-0162","authenticated-orcid":false,"given":"LUIGI","family":"BELLOMARINI","sequence":"first","affiliation":[]},{"given":"ELEONORA","family":"LAURENZA","sequence":"additional","affiliation":[]},{"given":"EMANUEL","family":"SALLINGER","sequence":"additional","affiliation":[]},{"given":"EVGENY","family":"SHERKHONOV","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2022,11,9]]},"reference":[{"key":"S1471068422000412_ref70","first-page":"1330","article-title":"PRISM: A language for symbolic-statistical modeling","author":"Sato","year":"1997","journal-title":"In IJCAI"},{"key":"S1471068422000412_ref39","first-page":"552","article-title":"Slimshot: In-database probabilistic inference for knowledge bases","volume":"7","author":"Gribkoff","year":"2016","journal-title":"PVLDB 9"},{"key":"S1471068422000412_ref44","doi-asserted-by":"crossref","unstructured":"Jaeger, M. 2018. Probabilistic logic and relational models. In Encyclopedia of Social Network Analysis and Mining. 2nd Ed. Springer.","DOI":"10.1007\/978-1-4939-7131-2_157"},{"key":"S1471068422000412_ref50","first-page":"399","article-title":"Solving conflicts in database fusion with bayesian networks","author":"Laurenza","year":"2015","journal-title":"In FUSION"},{"key":"S1471068422000412_ref33","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"S1471068422000412_ref60","unstructured":"Olteanu, D. 2016. Factorized databases: A knowledge compilation perspective. In AAAI Workshop: Beyond NP. AAAI Workshops, vol. WS-16-05. AAAI Press."},{"key":"S1471068422000412_ref8","first-page":"2","article-title":"Swift logic for big data and knowledge graphs","author":"Bellomarini","year":"2017","journal-title":"In IJCAI"},{"key":"S1471068422000412_ref11","unstructured":"Berti-\u00c9quille, L. , Sarma, A. D. , Dong, X. , Marian, A. and Srivastava, D. 2009. Sailing the information ocean with awareness of currents: Discovery and application of source dependence. CoRR abs\/0909.1776."},{"key":"S1471068422000412_ref49","doi-asserted-by":"crossref","unstructured":"Latour, A. L. D. , Babaki, B. , Dries, A. , Kimmig, A. , den Broeck, G. V. and Nijssen, S. 2017. Combining stochastic constraint optimization and probabilistic programming - from knowledge compilation to constraint solving. In CP. LNCS, vol. 10416. Springer, 495\u2013511.","DOI":"10.1007\/978-3-319-66158-2_32"},{"key":"S1471068422000412_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/3241978"},{"key":"S1471068422000412_ref31","doi-asserted-by":"crossref","unstructured":"Fayzrakhmanov, R. R. , Sallinger, E. , Spencer, B. , Furche, T. and Gottlob, G. 2018. Browserless web data extraction: Challenges and opportunities. In WWW. ACM, 1095\u20131104.","DOI":"10.1145\/3178876.3186008"},{"key":"S1471068422000412_ref35","unstructured":"Goodman, N. D. , Mansinghka, V. K. , Roy, D. M. , Bonawitz, K. and Tenenbaum, J. B. 2008. Church: a language for generative models. In UAI."},{"key":"S1471068422000412_ref55","doi-asserted-by":"crossref","unstructured":"Michels, C. , Fayzrakhmanov, R. R. , Ley, M. , Sallinger, E. and Schenkel, R. 2017. Oxpath-based data acquisition for dblp. In JCDL. IEEE Computer Society, 319\u2013320.","DOI":"10.1109\/JCDL.2017.7991609"},{"key":"S1471068422000412_ref66","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/0212053","article-title":"The complexity of counting cuts and of computing the probability that a graph is connected","volume":"4","author":"Provan","year":"1983","journal-title":"SIAM Journal on Computing 12"},{"key":"S1471068422000412_ref69","unstructured":"Sato, T. 1995. A statistical learning method for logic programs with distribution semantics. In ICLP, 715\u2013729."},{"key":"S1471068422000412_ref72","doi-asserted-by":"crossref","unstructured":"Singla, P. and Domingos, P. M. 2006. Entity resolution with markov logic. In ICDM. IEEE Computer Society, 572\u2013582.","DOI":"10.1109\/ICDM.2006.65"},{"key":"S1471068422000412_ref51","unstructured":"Lee, J. and Wang, Y. 2016. Weighted rules under the stable model semantics. In KR, 145\u2013154."},{"key":"S1471068422000412_ref9","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Laurenza, E. , Sallinger, E. and Sherkhonov, E. 2020. Reasoning under uncertainty in knowledge graphs. In RuleML+RR. Vol. 12173. Springer, 131\u2013139.","DOI":"10.1007\/978-3-030-57977-7_9"},{"key":"S1471068422000412_ref62","unstructured":"Pfeffer, A. and River Analytics, C. 2009. Figaro: An object-oriented probabilistic programming language."},{"key":"S1471068422000412_ref75","first-page":"1701","article-title":"Markov chains for exploring posterior distributions","author":"Tierney","year":"1994","journal-title":"Annals of Statistics 22"},{"volume-title":"Probabilistic Graphical Models: Principles and Techniques","year":"2009","author":"Koller","key":"S1471068422000412_ref47"},{"key":"S1471068422000412_ref37","first-page":"2999","article-title":"Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue","author":"Gottlob","year":"2015","journal-title":"In IJCAI."},{"key":"S1471068422000412_ref54","unstructured":"McCallum, A. and Wellner, B. 2004. Conditional models of identity uncertainty with application to noun coreference. In NIPS. 905\u2013912."},{"key":"S1471068422000412_ref76","doi-asserted-by":"crossref","unstructured":"Ullman, J. D. 1997. Information integration using logical views. In ICDT, 19\u201340.","DOI":"10.1007\/3-540-62222-5_34"},{"key":"S1471068422000412_ref19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-31164-2","volume-title":"Data Matching - Concepts and Techniques for Record Linkage, Entity Resolution, and Duplicate Detection","author":"Christen","year":"2012"},{"key":"S1471068422000412_ref59","doi-asserted-by":"publisher","DOI":"10.1007\/b98874"},{"key":"S1471068422000412_ref73","unstructured":"Stuart, A. and Ord, K. 1991. Kendall\u2019s advanced theory of statistics, Fifth ed. Vol. 2, Classical Inference and Relationship."},{"key":"S1471068422000412_ref24","doi-asserted-by":"crossref","unstructured":"Dantsin, E. 1991. Probabilistic logic programs and their semantics. In RCLP. Lecture Notes in Computer Science, vol. 592. Springer, 152\u2013164.","DOI":"10.1007\/3-540-55460-2_11"},{"key":"S1471068422000412_ref7","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Fayzrakhmanov, R. R. , Gottlob, G. , Kravchenko, A. , Laurenza, E. , Nenov, Y. , Reissfelder, S. , Sallinger, E. , Sherkhonov, E. and Wu, L. 2018. Data science with Vadalog: Bridging machine learning and reasoning. In MEDI. Vol. 11163. Springer, 3\u201321.","DOI":"10.1007\/978-3-030-00856-7_1"},{"key":"S1471068422000412_ref43","doi-asserted-by":"crossref","unstructured":"Huang, J. , Antova, L. , Koch, C. and Olteanu, D. 2009. Maybms: a probabilistic database management system. In SIGMOD Conference, 1071\u20131074.","DOI":"10.1145\/1559845.1559984"},{"key":"S1471068422000412_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"S1471068422000412_ref42","first-page":"1716","article-title":"Scale-free networks","volume":"1","author":"Hidalgo","year":"2008","journal-title":"Scholarpedia 3"},{"key":"S1471068422000412_ref52","first-page":"1188","article-title":"Logic on MARS: ontologies for generalised property graphs","author":"Marx","year":"2017","journal-title":"In IJCAI."},{"key":"S1471068422000412_ref71","doi-asserted-by":"crossref","unstructured":"Singla, P. and Domingos, P. M. 2005. Object identification with attribute-mediated dependences. In PKDD. Lecture Notes in Computer Science, vol. 3721. Springer, 297\u2013308.","DOI":"10.1007\/11564126_31"},{"key":"S1471068422000412_ref61","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"S1471068422000412_ref65","doi-asserted-by":"crossref","unstructured":"Poole, D. 2008. The independent choice logic and beyond. In Probabilistic Inductive Logic Progr. LNCS, vol. 4911. Springer, 222\u2013243.","DOI":"10.1007\/978-3-540-78652-8_8"},{"key":"S1471068422000412_ref10","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Sallinger, E. and Gottlob, G. 2018. The Vadalog system: Datalog-based reasoning for knowledge graphs. In VLDB.","DOI":"10.14778\/3213880.3213888"},{"key":"S1471068422000412_ref14","doi-asserted-by":"crossref","unstructured":"Borgwardt, S. , Ceylan, I. I. and Lukasiewicz, T. 2017. Ontology-mediated queries for probabilistic databases. In AAAI. AAAI Press, 1063\u20131069.","DOI":"10.1609\/aaai.v31i1.10680"},{"key":"S1471068422000412_ref17","first-page":"146","article-title":"What you always wanted to know about datalog (and never dared to ask)","volume":"1","author":"Ceri","year":"1989","journal-title":"KDE 1"},{"key":"S1471068422000412_ref77","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068409003767"},{"volume-title":"Synthesis Lectures on Data Management","year":"2011","author":"Suciu","key":"S1471068422000412_ref74"},{"key":"S1471068422000412_ref58","first-page":"373","article-title":"Tuffy: Scaling up statistical inference in markov logic networks using an RDBMS","volume":"6","author":"Niu","year":"2011","journal-title":"PVLDB 4"},{"key":"S1471068422000412_ref46","doi-asserted-by":"crossref","unstructured":"Kersting, K. and Raedt, L. D. 2008. Basic principles of learning bayesian logic programs. In Probabilistic Inductive Logic Programming.","DOI":"10.1007\/978-3-540-78652-8"},{"key":"S1471068422000412_ref68","doi-asserted-by":"crossref","unstructured":"Riguzzi, F. 2007. A top down interpreter for LPAD and cp-logic. In AI*IA. Vol. 4733. Springer, 109\u2013120.","DOI":"10.1007\/978-3-540-74782-6_11"},{"key":"S1471068422000412_ref15","first-page":"5420","article-title":"Recent advances in querying probabilistic knowledge bases","author":"Borgwardt","year":"2018","journal-title":"In IJCAI,"},{"key":"S1471068422000412_ref26","first-page":"5","article-title":"Probabilistic (logic) programming concepts","volume":"1","author":"De Raedt","year":"2015","journal-title":"ML 100"},{"key":"S1471068422000412_ref2","doi-asserted-by":"publisher","DOI":"10.3233\/IA-170106"},{"key":"S1471068422000412_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04898-2_161"},{"key":"S1471068422000412_ref79","first-page":"796","article-title":"Truth discovery with multiple conflicting information providers on the web","volume":"6","author":"Yin","year":"2008","journal-title":"IEEE Transactions on Knowledge and Data Engineering. 20"},{"key":"S1471068422000412_ref56","unstructured":"Milch, B. , Marthi, B. , Russell, S. J. , Sontag, D. , Ong, D. L. and Kolobov, A. 2005. BLOG: probabilistic models with unknown objects. In IJCAI."},{"key":"S1471068422000412_ref64","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037184"},{"key":"S1471068422000412_ref29","unstructured":"Dong, X. L. , Berti-\u00c9quille, L. and Srivastava, D. 2015. Data fusion: Resolving conflicts from multiple sources. CoRR abs\/1503.00310."},{"key":"S1471068422000412_ref23","doi-asserted-by":"crossref","unstructured":"d\u2019Amato, C. , Fanizzi, N. and Lukasiewicz, T. 2008. Tractable reasoning with bayesian description logics. In SUM. Lecture Notes in Computer Science, vol. 5291. Springer, 146\u2013159.","DOI":"10.1007\/978-3-540-87993-0_13"},{"key":"S1471068422000412_ref13","unstructured":"Bollob\u00e1s, B. , Borgs, C. , Chayes, J. and Riordan, O. 2003. Directed scale-free graphs. In SODA, 132\u2013139."},{"key":"S1471068422000412_ref18","doi-asserted-by":"crossref","unstructured":"Ceylan, I. I. and Pe\u00f1aloza, R. 2015. Probabilistic query answering in the bayesian description logic BEl. In SUM. Lecture Notes in Computer Science, vol. 9310. Springer, 21\u201335.","DOI":"10.1007\/978-3-319-23540-0_2"},{"key":"S1471068422000412_ref38","first-page":"17","article-title":"Models for incomplete and probabilistic information","volume":"1","author":"Green","year":"2006","journal-title":"IEEE Database Engineering Bulletin 29"},{"key":"S1471068422000412_ref20","doi-asserted-by":"crossref","unstructured":"Culotta, A. and McCallum, A. 2005. Joint deduplication of multiple record types in relational data. In CIKM. ACM, 257\u2013258.","DOI":"10.1145\/1099554.1099615"},{"key":"S1471068422000412_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-013-9342-1"},{"key":"S1471068422000412_ref40","first-page":"1375","article-title":"An analysis of first-order logics of probability","author":"Halpern","year":"1989","journal-title":"In IJCAI"},{"key":"S1471068422000412_ref12","first-page":"1:1","article-title":"Data fusion","volume":"1","author":"Bleiholder","year":"2008","journal-title":"ACM Computing Surveys 41"},{"key":"S1471068422000412_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"S1471068422000412_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"S1471068422000412_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"S1471068422000412_ref22","first-page":"30:1","article-title":"The dichotomy of probabilistic inference for unions of conjunctive queries","volume":"6","author":"Dalvi","year":"2012","journal-title":"J. ACM 59"},{"key":"S1471068422000412_ref32","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10501049"},{"key":"S1471068422000412_ref57","unstructured":"Mumick, I. S. , Pirahesh, H. and Ramakrishnan, R. 1990. The magic of duplicates and aggregates. In VLDB (2002-01-03), D. McLeod, R. Sacks-Davis, and H.-J. Schek, Eds. Kaufmann, Morgan , 264\u2013277."},{"volume-title":"Representing and Reasoning with Probabilistic Knowledge - A Logical Approach to Probabilities","year":"1990","author":"Bacchus","key":"S1471068422000412_ref4"},{"volume-title":"Chapman and Hall\/CRC Interdisciplinary Statistics","year":"1995","author":"Gilks","key":"S1471068422000412_ref34"},{"key":"S1471068422000412_ref41","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"S1471068422000412_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745760"},{"key":"S1471068422000412_ref48","doi-asserted-by":"crossref","unstructured":"Krompa\u00df, D. , Nickel, M. and Tresp, V. 2014. Querying factorized probabilistic triple databases. In ISWC (2). Lecture Notes in Computer Science, vol. 8797. Springer, 114\u2013129.","DOI":"10.1007\/978-3-319-11915-1_8"},{"key":"S1471068422000412_ref27","doi-asserted-by":"publisher","DOI":"10.1561\/1900000052"},{"key":"S1471068422000412_ref63","first-page":"133","article-title":"Linking data to ontologies","author":"Poggi","year":"2008","journal-title":"J. Data Semant. 10"},{"key":"S1471068422000412_ref78","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27775-0_30"},{"key":"S1471068422000412_ref45","first-page":"182","volume-title":"Computer Science","volume":"7649","author":"Jung","year":"2012"},{"key":"S1471068422000412_ref67","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"S1471068422000412_ref53","unstructured":"McCallum, A. , Tejada, S. and Quass, D. , Eds. 2003. Proceedings of the KDD-2003 Workshop on Data Cleaning, Record Linkage, and Object Consolidation. ACM Press."},{"key":"S1471068422000412_ref6","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Fakhoury, D. , Gottlob, G. and Sallinger, E. 2019. Knowledge graphs and enterprise AI: the promise of an enabling technology. In ICDE. IEEE, 26\u201337.","DOI":"10.1109\/ICDE.2019.00011"},{"key":"S1471068422000412_ref3","unstructured":"Angles, R. 2018. The property graph database model. In AMW. Vol. 2100."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068422000412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T03:08:03Z","timestamp":1684465683000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068422000412\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,9]]},"references-count":79,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["S1471068422000412"],"URL":"https:\/\/doi.org\/10.1017\/s1471068422000412","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2022,11,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}