{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:57:29Z","timestamp":1791460649059,"version":"4.3.4"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T00:00:00Z","timestamp":1759968000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1762299, CCF-1918889, CNS-1908304, CCF-1901376, CNS-2120696, CCF-2210831, CCF-2319471, CCF-2422130, CCF-2403211"],"award-info":[{"award-number":["CCF-1762299, CCF-1918889, CNS-1908304, CCF-1901376, CNS-2120696, CCF-2210831, CCF-2319471, CCF-2422130, CCF-2403211"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>\n                    Probabilistic extensions of logic programming languages, such as ProbLog, integrate logical reasoning with probabilistic inference to evaluate probabilities of output relations; however, prior work does not account for potential statistical correlations among input facts. This paper introduces\n                    <jats:sc>Praline,<\/jats:sc>\n                    a new extension to Datalog designed for precise probabilistic inference in the presence of (partially known) input correlations. We formulate the inference task as a constrained optimization problem, where the solution yields sound and precise probability bounds for output facts. However, due to the complexity of the resulting optimization problem, this approach alone often does not scale to large programs. To address scalability, we propose a more efficient \ud835\udeff-exact inference algorithm that leverages constraint solving, static analysis, and iterative refinement. Our empirical evaluation on challenging real-world benchmarks, including side-channel analysis, demonstrates that our method not only scales effectively but also delivers tight probability bounds.\n                  <\/jats:p>","DOI":"10.1145\/3763058","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"220-247","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Probabilistic Inference for Datalog with Correlated Inputs"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5877-2677","authenticated-orcid":false,"given":"Jingbo","family":"Wang","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1268-4345","authenticated-orcid":false,"given":"Shashin","family":"Halalingaiah","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6276-3525","authenticated-orcid":false,"given":"Weiyi","family":"Chen","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4684-3943","authenticated-orcid":false,"given":"Chao","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8006-1230","authenticated-orcid":false,"given":"I\u015f\u0131l","family":"Dillig","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133904"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158146"},{"key":"e_1_3_1_4_2","volume-title":"Compilers principles, techniques & tools,","author":"Alfred V Aho","year":"2007","unstructured":"V Aho Alfred, S Lam Monica, and D Ullman Jeffrey. 2007. Compilers principles, techniques & tools,. pearson Education."},{"issue":"109","key":"e_1_3_1_5_2","first-page":"1","article-title":"Hinge-loss markov random fields and probabilistic soft logic","volume":"18","author":"Bach Stephen H","year":"2017","unstructured":"Stephen H Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. 2017. Hinge-loss markov random fields and probabilistic soft logic. Journal of Machine Learning Research. 18, 109 (2017), 1\u201367.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132700"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677000"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","unstructured":"Raven Beutner C-H Luke Ong and Fabian Zaiser. 2022. Guaranteed bounds for posterior inference in universal probabilistic programming. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 536\u2013551. https:\/\/doi.org\/doi\/10.1145\/3519939.3523721 10.1145\/3519939.3523721","DOI":"10.1145\/3519939.3523721"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/3322706.3322734"},{"issue":"2","key":"e_1_3_1_11_2","first-page":"159","article-title":"The gurobi optimizer","volume":"41","author":"Bixby Bob","year":"2007","unstructured":"Bob Bixby. 2007. The gurobi optimizer. Transp. Re-search Part B. 41, 2 (2007), 159\u2013178.","journal-title":"Transp. Re-search Part B"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","unstructured":"Martin Bravenboer and Yannis Smaragdakis. 2009. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications 243\u2013262. https:\/\/doi.org\/10.1145\/1640089.1640108 10.1145\/1640089.1640108","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28869-2_9"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/1534901"},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","unstructured":"Erik Daxberger Anastasia Makarova Matteo Turchetta and Andreas Krause. 2021. Mixed-variable Bayesian optimization. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 2633\u20132639.","DOI":"10.24963\/ijcai.2020\/365"},{"key":"e_1_3_1_17_2","unstructured":"Luc De Raedt Angelika Kimmig and Hannu Toivonen. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In IJCAI2007 Proceedings of the 20th international joint conference on artificial intelligence.IJCAI-INT JOINT CONF ARTIF INTELL 2462\u20132467."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23461-8_37"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_8"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","unstructured":"Shenghua Feng Mingshuai Chen Han Su Benjamin Lucien Kaminski Joost-Pieter Katoen and Naijun Zhan. 2023. Lower bounds for possibly divergent probabilistic programs. Proceedings of the ACM on Programming Languages. 7 OOPSLA1 (2023) 696\u2013726. https:\/\/doi.org\/10.1145\/3586051 10.1145\/3586051","DOI":"10.1145\/3586051"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","unstructured":"Norbert Fuhr. 1995. Probabilistic datalog\u2014a logic for powerful retrieval methods. In Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval. 282\u2013290. https:\/\/doi.org\/doi\/10.1145\/215206.215372 10.1145\/215206.215372","DOI":"10.1145\/215206.215372"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31365-3_23"},{"key":"e_1_3_1_24_2","first-page":"1682","volume-title":"International conference on artificial intelligence and statistics","author":"Ge Hong","year":"2018","unstructured":"Hong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: a language for flexible probabilistic inference. In International conference on artificial intelligence and statistics. PMLR, 1682\u20131690."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_4"},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","unstructured":"Lise Getoor Nir Friedman Daphne Koller Avi Pfeffer and Ben Taskar. 2007. Probabilistic relational models.","DOI":"10.7551\/mitpress\/7432.003.0007"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3559102"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/3327546.3327731"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_3_1_30_2","first-page":"422","volume-title":"Computer Aided Verification: 28th International Conference, CAV2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part II","author":"Jordan Herbert","year":"2016","unstructured":"Herbert Jordan, Bernhard Scholz, and Pavle Suboti\u0107. 2016. Souffl\u00e9: On synthesis of program analyzers. In Computer Aided Verification: 28th International Conference, CAV2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part II. Springer, 422\u2013430."},{"key":"e_1_3_1_31_2","doi-asserted-by":"crossref","unstructured":"Kristian Kersting and Luc De Raedt. 2007. Bayesian logic programming: Theory and tool.","DOI":"10.7551\/mitpress\/7432.003.0012"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649844"},{"key":"e_1_3_1_33_2","article-title":"Exact probabilistic inference using generating functions","author":"Klinkenberg Lutz","year":"2023","unstructured":"Lutz Klinkenberg, Tobias Winkler, Mingshuai Chen, and Joost-Pieter Katoen. 2023. Exact probabilistic inference using generating functions. arXiv preprint arXiv:2302.00513 (2023).","journal-title":"arXiv preprint arXiv:2302.00513"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","unstructured":"Daphne Koller and Nir Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press. https:\/\/doi.org\/doi\/10.5555\/1795555 10.5555\/1795555","DOI":"10.5555\/1795555"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","unstructured":"Markus Kusano and Chao Wang. 2016. Flow-sensitive composition of thread-modular abstract interpretation. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 799\u2013809. https:\/\/doi.org\/doi\/10.1145\/2950290.2950291 10.1145\/2950290.2950291","DOI":"10.1145\/2950290.2950291"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","unstructured":"Markus KusanoChaoWang. 2017. Thread-modular static analysis for relaxed memory models. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering 337\u2013348. https:\/\/doi.org\/10.1145\/3106237.3106243 10.1145\/3106237.3106243","DOI":"10.1145\/3106237.3106243"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","unstructured":"Jianlin Li Eric Wang and Yizhou Zhang. 2024. Compiling Probabilistic Programs for Variable Elimination with Information Flow. Proceedings of the ACM on Programming Languages. 8 PLDI (2024) 1755\u20131780. https:\/\/doi.org\/10.1145\/3656448 10.1145\/3656448","DOI":"10.1145\/3656448"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591280"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908096"},{"key":"e_1_3_1_40_2","doi-asserted-by":"crossref","unstructured":"Brian Milch Bhaskara Marthi Stuart Russell David Sontag Daniel L Ong and Andrey Kolobov. 2007. BLOG: Probabilistic models with unknown objects. (2007).","DOI":"10.7551\/mitpress\/7432.003.0015"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","unstructured":"Mayur Naik Alex Aiken and John Whaley. 2006. Effective static race detection for Java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation. 308\u2013319. https:\/\/doi.org\/doi\/10.1145\/1133981.1134018 10.1145\/1133981.1134018","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","unstructured":"Mukund Raghothaman Sulekha Kulkarni Kihong Heo and Mayur Naik. 2018. User-guided program reasoning using Bayesian inference. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation 722\u2013735. https:\/\/doi.org\/10.1145\/3296979.3192417 10.1145\/3296979.3192417","DOI":"10.1145\/3296979.3192417"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-2207-2_8"},{"key":"e_1_3_1_46_2","first-page":"151","volume-title":"Advances in Probability Distributions with Given Marginals: beyond the copulas","author":"R\u00fcschendorf Ludger","unstructured":"Ludger R\u00fcschendorf. [n. d.]. Fr\u00e9chet-bounds and their applications. In Advances in Probability Distributions with Given Marginals: beyond the copulas. Springer, 151\u2013187."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","unstructured":"Feras A Saad Martin C Rinard and Vikash K Mansinghka. 2021. SPPL: probabilistic programming with fast exact symbolic inference. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation 804\u2013819. https:\/\/doi.org\/10.1145\/3453483.3454078 10.1145\/3453483.3454078","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_3_1_48_2","doi-asserted-by":"crossref","unstructured":"Sriram Sankaranarayanan Aleksandar Chakarov and Sumit Gulwani. 2013. Static analysis for probabilistic programs: inferring whole program properties from finitely many paths. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation 447\u2013458.","DOI":"10.1145\/2491956.2462179"},{"key":"e_1_3_1_49_2","doi-asserted-by":"crossref","unstructured":"Taisuke Sato. 1995. A statistical learning method for logic programs with distribution semantics.","DOI":"10.7551\/mitpress\/4298.003.0069"},{"key":"e_1_3_1_50_2","doi-asserted-by":"crossref","unstructured":"Marco Scutari. 2009. Learning Bayesian networks with the bnlearn R package. arXiv preprint arXiv:0908.3817.","DOI":"10.18637\/jss.v035.i03"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","unstructured":"Yannis Smaragdakis George Kastrinis and George Balatsouras. 2014. Introspective analysis: context-sensitivity across the board. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation 485\u2013495. https:\/\/doi.org\/10.1145\/2499370.2462179 10.1145\/2499370.2462179","DOI":"10.1145\/2499370.2462179"},{"key":"e_1_3_1_52_2","unstructured":"Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2018. An introduction to probabilistic programming. arXiv preprint arXiv:1809.10756."},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068409003767"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27775-0_30"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","unstructured":"Jonas Vlasselaer Guy Van den Broeck Angelika Kimmig Wannes Meert and Luc De Raedt. 2016. Tp-compilation for inference in probabilistic logic programs. International Journal of Approximate Reasoning 78 (2016) 15\u201332. https:\/\/doi.org\/10.1016\/j.ijar.2016.06.009 10.1016\/j.ijar.2016.06.009","DOI":"10.1016\/j.ijar.2016.06.009"},{"key":"e_1_3_1_56_2","unstructured":"Brend Wanders Maurice van Keulen and Jan Flokstra. 2016. Judged: a probabilistic datalog with dependencies. In Workshops at the Thirtieth AAAI Conference on Artificial Intelligence."},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","unstructured":"Jingbo Wang Shashin Halalingaiah Weiyi Chen Chao Wang and Isil Dillig. 2025. Reproduction Package for Article \u2018Probabilistic Inference for Datalog with Correlated Inputs\u2019. ACM. https:\/\/doi.org\/10.5281\/zenodo.15760564 10.5281\/zenodo.15760564","DOI":"10.5281\/zenodo.15760564"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","unstructured":"Jingbo Wang Chungha Sung Mukund Raghothaman and Chao Wang. 2021. Data-driven synthesis of provably sound side channel analyses. In 2021 IEEE\/ACM 43rd International Conference on Software Engineering (ICSE). https:\/\/doi.org\/10.1109\/ICSE43902.2021.00079 10.1109\/ICSE43902.2021.00079","DOI":"10.1109\/ICSE43902.2021.00079"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","unstructured":"Jingbo Wang Chungha Sung and Chao Wang. 2019. Mitigating power side channels during compilation. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering 590\u2013601. https:\/\/doi.org\/10.1145\/3338906.3338913 10.1145\/3338906.3338913","DOI":"10.1145\/3338906.3338913"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","unstructured":"Yuxin Wang Zeyu Ding Guanhong Wang Daniel Kifer and Danfeng Zhang. 2019. Proving differential privacy with shadow execution. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation 655\u2013669. https:\/\/doi.org\/10.1145\/3314221.3314619 10.1145\/3314221.3314619","DOI":"10.1145\/3314221.3314619"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/11575467-8"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96142-2_12"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133881"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","unstructured":"Xin Zhang Ravi Mangal Radu Grigore Mayur Naik and Hongseok Yang. 2014. On abstraction refinement for program analyses in Datalog. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation 239\u2013248. https:\/\/doi.org\/10.1145\/2666356.2594327 10.1145\/2666356.2594327","DOI":"10.1145\/2666356.2594327"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763058","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:00:26Z","timestamp":1784196026000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":63,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763058"],"URL":"https:\/\/doi.org\/10.1145\/3763058","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}