{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:57:31Z","timestamp":1791460651423,"version":"4.3.4"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["1492\/16-1 and GRK 2236"],"award-info":[{"award-number":["1492\/16-1 and GRK 2236"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["787914"],"award-info":[{"award-number":["787914"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Arguing for the need to combine declarative and probabilistic programming, B\u00e1r\u00e1ny et\u00a0al. (TODS 2017) recently introduced a probabilistic extension of Datalog as a \u201cpurely declarative probabilistic programming language.\u201d We revisit this language and propose a more principled approach towards defining its semantics based on stochastic kernels and Markov processes\u2014standard notions from probability theory. This allows us to extend the semantics to continuous probability distributions, thereby settling an open problem posed by B\u00e1r\u00e1ny et\u00a0al.<\/jats:p>\n          <jats:p>We show that our semantics is fairly robust, allowing both parallel execution and arbitrary chase orders when evaluating a program. We cast our semantics in the framework of infinite probabilistic databases (Grohe and Lindner, LMCS 2022) and show that the semantics remains meaningful even when the input of a probabilistic Datalog program is an arbitrary probabilistic database.<\/jats:p>","DOI":"10.1145\/3559102","type":"journal-article","created":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T07:09:21Z","timestamp":1661843361000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Generative Datalog with Continuous Distributions"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5185-2324","authenticated-orcid":false,"given":"Benjamin Lucien","family":"Kaminski","sequence":"additional","affiliation":[{"name":"Saarland University, Saarland Informatics Campus, Germany and University College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6143-1926","authenticated-orcid":false,"given":"Joost-pieter","family":"Katoen","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2041-7201","authenticated-orcid":false,"given":"Peter","family":"Lindner","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Foundations of Databases (1st ed.)","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Richard Vianu. 1995. Foundations of Databases (1st ed.). Addison-Wesley Publishing Company, Inc., Reading, MA."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.190"},{"key":"e_1_3_3_4_2","first-page":"17","volume-title":"Proceedings of the 3rd VLDB Workshop on Management of Uncertain Data (MUD\u201909)","author":"Agrawal Parag","year":"2009","unstructured":"Parag Agrawal and Jennifer Widom. 2009. Continuous uncertainty in trio. In Proceedings of the 3rd VLDB Workshop on Management of Uncertain Data (MUD\u201909). Centre for Telematics and Information Technology (CTIT), 17\u201332."},{"key":"e_1_3_3_5_2","volume-title":"Proceedings of the International Conference on Logic Programming Workshops co-located with the 37th International Conference on Logic Programming (ICLP\u201921)","author":"Alviano Mario","year":"2021","unstructured":"Mario Alviano and Arnel Zamayla. 2021. A speech about generative datalog and non-measurable sets. In Proceedings of the International Conference on Logic Programming Workshops co-located with the 37th International Conference on Logic Programming (ICLP\u201921). 8. Retrieved from http:\/\/ceur-ws.org\/Vol-2970\/aspocpinvited2.pdf."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132700"},{"key":"e_1_3_3_7_2","first-page":"28:1\u201328:6","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 A. Szerlip, Paul Horsfall, and Noah D. Goodman. 2019. Pyro: Deep universal probabilistic programming. J. Mach. Learn. Res. 20 (2019), 28:1\u201328:6.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1973.223746"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(3:11)2013"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32033-3_24"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2734"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465283"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3873"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108770750.008"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959068"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3949"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49835-5"},{"key":"e_1_3_3_20_2","first-page":"2468","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI\u201907)","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 Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI\u201907). Morgan Kaufmann Publishers Inc., San Francisco, CA, 2468\u20132473."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00692ED1V01Y201601AIM032"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469-8.50053-X"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807114"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"e_1_3_3_26_2","volume-title":"Measure Theory. Vol. IV: Topological Measure Spaces, Part I (2nd ed.)","author":"Fremlin David H.","year":"2013","unstructured":"David H. Fremlin. 2013. Measure Theory. Vol. IV: Topological Measure Spaces, Part I (2nd ed.). Torres Fremlin."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/215206.215372"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(2000)51:2<95::AID-ASI2>3.0.CO;2-H"},{"issue":"2","key":"e_1_3_3_29_2","first-page":"169","article-title":"Sigma-algebras on spaces of probability measures","volume":"16","author":"Gaudard Marie","year":"1989","unstructured":"Marie Gaudard and Donald Hadwin. 1989. Sigma-algebras on spaces of probability measures. Scandin. J. Statist. 16, 2 (1989), 169\u2013175.","journal-title":"Scandin. J. Statist."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387644"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429117"},{"key":"e_1_3_3_32_2","first-page":"220","volume-title":"Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI\u201908)","author":"Goodman Noah D.","year":"2008","unstructured":"Noah D. Goodman, Vikash K. Mansinghka, Daniel Roy, Keith Bonawitz, and Joshua B. Tenenbaum. 2008. Church: A language for generative models. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI\u201908). AUAI Press, Arlington, VA, 220\u2013229."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2593882.2593900"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-013-9342-1"},{"key":"e_1_3_3_35_2","volume-title":"Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201914)","author":"Gottlob Georg","year":"2014","unstructured":"Georg Gottlob, Thomas Lukasiewicz, and Andreas Pieris. 2014. Datalog+\/\u2013: Questions and answers. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201914). AAAI Press. Retrieved from https:\/\/www.aaai.org\/ocs\/index.php\/KR\/KR14\/paper\/view\/7965."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387659"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319681"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(1:34)2022"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21295-6_12"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmp.2019.102308"},{"key":"e_1_3_3_41_2","first-page":"26","volume-title":"Proceedings of the 48th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL\u201921)","volume":"5","author":"Jacobs Jules","year":"2021","unstructured":"Jules Jacobs. 2021. Paradoxes of probabilistic programming. In Proceedings of the 48th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL\u201921), Vol. 5. ACM, 26."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000828"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4015-8"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_24"},{"key":"e_1_3_3_45_2","first-page":"1","volume-title":"Proceedings of the NIPS Workshop on Probabilistic Programming: Foundations and Applications","author":"Kimmig Angelika","year":"2012","unstructured":"Angelika Kimmig, Stephen Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. 2012. A short introduction to probabilistic soft logic. In Proceedings of the NIPS Workshop on Probabilistic Programming: Foundations and Applications. 1\u20134."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_3_47_2","volume-title":"Foundations of the Theory of Probability (2nd English ed.)","author":"Kolmogorov Andrei Nikolajewitsch","year":"1956","unstructured":"Andrei Nikolajewitsch Kolmogorov. 1956. Foundations of the Theory of Probability (2nd English ed.). Chelsea Publishing Company, New York, NY."},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90036-2"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808758"},{"key":"e_1_3_3_50_2","first-page":"397","article-title":"A general theorem on selectors","volume":"13","author":"Kuratowski C.","year":"1965","unstructured":"C. Kuratowski and C. Ryll-Nardzewski. 1965. A general theorem on selectors. Bull. Polish Acad. Sci. 13 (1965), 397\u2013403.","journal-title":"Bull. Polish Acad. Sci."},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1641\/0006-3568(2001)051[0341:LNDATS]2.0.CO;2"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.18154\/RWTH-2021-10669"},{"key":"e_1_3_3_54_2","volume-title":"Probabilistic Models with Unknown Objects","author":"Milch Brian","year":"2006","unstructured":"Brian Milch. 2006. Probabilistic Models with Unknown Objects. Ph.D. Dissertation. University of California at Berkeley."},{"key":"e_1_3_3_55_2","first-page":"1352","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI\u201905)","author":"Milch Brian","year":"2005","unstructured":"Brian Milch, Bhaskara Marthi, Stuart Russell, David Sontag, David L. Ong, and Andrey Kolobov. 2005. Blog: Probabilistic models with unknown objects. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI\u201905). Morgan Kaufmann, San Francisco, CA, 1352\u20131359."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.9060"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/C2009-0-27609-4"},{"key":"e_1_3_3_58_2","volume-title":"Figaro: An Object-Oriented Probabilistic Programming Language","author":"Pfeffer Avi","year":"2009","unstructured":"Avi Pfeffer. 2009. Figaro: An Object-Oriented Probabilistic Programming Language. Technical Report. Charles River Analytics."},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08921-7_92"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376744"},{"key":"e_1_3_3_62_2","first-page":"368","volume-title":"Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI\u201907)","author":"Singla Parag","year":"2007","unstructured":"Parag Singla and Pedro Domingos. 2007. Markov logic in infinite domains. In Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI\u201907). AUAI Press, Arlington, VA, 368\u2013375."},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-85473-6"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00362ED1V01Y201105DTM016"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23461-8_36"},{"key":"e_1_3_3_66_2","article-title":"An introduction to probabilistic programming","author":"Meent Jan-Willem van de","year":"2018","unstructured":"Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, and Wood Frank. 2018. An introduction to probabilistic programming. arXiv e-prints (2018). Retrieved from https:\/\/arxiv.org\/abs\/1809.10756.","journal-title":"arXiv e-prints"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1561\/1900000052"},{"key":"e_1_3_3_68_2","volume-title":"The Workshops of the Thirtieth AAAI Conference on Artificial Intelligence: Technical Reports WS-16-01 \u2013 WS-16-15","author":"Wanders Brend","year":"2016","unstructured":"Brend Wanders, Maurice van Keulen, and Jan Flokstra. 2016. JudgeD: A probabilistic datalog with dependencies. In The Workshops of the Thirtieth AAAI Conference on Artificial Intelligence: Technical Reports WS-16-01 \u2013 WS-16-15. AAAI Press, Palo Alto, CA."},{"key":"e_1_3_3_69_2","first-page":"1106","article-title":"Hybrid Markov logic networks","author":"Wang Jue","year":"2008","unstructured":"Jue Wang and Pedro Domingos. 2008. Hybrid Markov logic networks. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI\u201908). 1106\u20131111. Retrieved from https:\/\/www.aaai.org\/Papers\/AAAI\/2008\/AAAI08-175.pdf.","journal-title":"Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI\u201908)"},{"key":"e_1_3_3_70_2","first-page":"5343","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918) (Proceedings of Machine Learning Research)","volume":"80","author":"Wu Yi","year":"2018","unstructured":"Yi Wu, Siddharth Srivastava, Nicholas Hay, Simon Du, and Stuart Russell. 2018. Discrete-continuous mixtures in probabilistic programming: Generalized semantics and inference algorithms. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918) (Proceedings of Machine Learning Research), Vol. 80. PMLR, 5343\u20135352."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:45Z","timestamp":1750186845000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":69,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3559102"],"URL":"https:\/\/doi.org\/10.1145\/3559102","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"2021-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}