{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:11:36Z","timestamp":1760033496492,"version":"build-2065373602"},"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>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 Praline, 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 \u03b4-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.<\/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":0,"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133904"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM on Programming Languages, 2, POPL","author":"Albarghouthi Aws","year":"2017","unstructured":"Aws Albarghouthi and Justin Hsu. 2017. Synthesizing coupling proofs of differential privacy. Proceedings of the ACM on Programming Languages, 2, POPL (2017), 1\u201330. https:\/\/doi.org\/doi\/10.1145\/3158146 \/10.1145\/3158146"},{"key":"e_1_2_1_3_1","unstructured":"V Aho Alfred S Lam Monica and D Ullman Jeffrey. 2007. Compilers principles techniques & tools. pearson Education."},{"key":"e_1_2_1_4_1","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_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132700"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775051.2677000"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523721"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Pyro: Deep universal probabilistic programming","volume":"20","author":"Bingham Eli","year":"2019","unstructured":"Eli Bingham, Jonathan P Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D Goodman. 2019. Pyro: Deep universal probabilistic programming. Journal of machine learning research, 20, 28 (2019), 1\u20136. https:\/\/doi.org\/doi\/abs\/10.5555\/3322706.3322734","journal-title":"Journal of machine learning research"},{"key":"e_1_2_1_10_1","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_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28869-2_9"},{"volume-title":"Modeling and reasoning with Bayesian networks","author":"Darwiche Adnan","key":"e_1_2_1_14_1","unstructured":"Adnan Darwiche. 2009. Modeling and reasoning with Bayesian networks. Cambridge university press."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 2633\u20132639","author":"Daxberger Erik","year":"2021","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."},{"key":"e_1_2_1_16_1","volume-title":"IJCAI 2007, Proceedings of the 20th international joint conference on artificial intelligence. 2462\u20132467","author":"Raedt Luc De","year":"2007","unstructured":"Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In IJCAI 2007, Proceedings of the 20th international joint conference on artificial intelligence. 2462\u20132467."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23461-8_37"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586051"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/215206.215372"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31365-3_23"},{"key":"e_1_2_1_23_1","volume-title":"International conference on artificial intelligence and statistics. 1682\u20131690","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. 1682\u20131690."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_4"},{"key":"e_1_2_1_25_1","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_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559102"},{"key":"e_1_2_1_27_1","volume-title":"Autoconj: recognizing and exploiting conjugacy without a domain-specific language. Advances in Neural Information Processing Systems, 31","author":"Hoffman Matthew D","year":"2018","unstructured":"Matthew D Hoffman, Matthew J Johnson, and Dustin Tran. 2018. Autoconj: recognizing and exploiting conjugacy without a domain-specific language. Advances in Neural Information Processing Systems, 31 (2018), https:\/\/doi.org\/doi\/10.5555\/3327546.3327731"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_2_1_29_1","volume-title":"Computer Aided Verification: 28th International Conference, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part II 28","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, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Proceedings, Part II 28. 422\u2013430."},{"key":"e_1_2_1_30_1","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_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649844"},{"key":"e_1_2_1_32_1","unstructured":"Lutz Klinkenberg Tobias Winkler Mingshuai Chen and Joost-Pieter Katoen. 2023. Exact probabilistic inference using generating functions. arXiv preprint arXiv:2302.00513."},{"volume-title":"Probabilistic graphical models: principles and techniques","author":"Koller Daphne","key":"e_1_2_1_33_1","unstructured":"Daphne Koller and Nir Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press. https:\/\/doi.org\/doi\/10.5555\/1795555"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950291"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106237.3106243"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656448"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591280"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908096"},{"key":"e_1_2_1_39_1","volume-title":"BLOG: Probabilistic models with unknown objects.","author":"Milch Brian","year":"2007","unstructured":"Brian Milch, Bhaskara Marthi, Stuart Russell, David Sontag, Daniel L Ong, and Andrey Kolobov. 2007. BLOG: Probabilistic models with unknown objects."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134018"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192417"},{"volume-title":"Applications of Logic Databases","author":"Reps Thomas W","key":"e_1_2_1_44_1","unstructured":"Thomas W Reps. 1995. Demand interprocedural program analysis using logic databases. In Applications of Logic Databases. Springer, 163\u2013196."},{"volume-title":"Advances in Probability Distributions with Given Marginals: beyond the copulas","author":"R\u00fcschendorf Ludger","key":"e_1_2_1_45_1","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_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462179"},{"key":"e_1_2_1_48_1","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_2_1_49_1","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_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594320"},{"key":"e_1_2_1_51_1","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_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068409003767"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27775-0_30"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2016.06.009"},{"key":"e_1_2_1_55_1","volume-title":"Workshops at the Thirtieth AAAI Conference on Artificial Intelligence.","author":"Wanders Brend","year":"2016","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_2_1_56_1","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_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE43902.2021.00079"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338913"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314619"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_8"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96142-2_12"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133881"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.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":[[2025,10,9]],"date-time":"2025-10-09T17:40:54Z","timestamp":1760031654000},"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":[{"type":"electronic","value":"2475-1421"}],"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"}}]}}