{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T14:09:39Z","timestamp":1774706979373,"version":"3.50.1"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["GR 1492\/16-1 and KI 2348\/1-1"],"award-info":[{"award-number":["GR 1492\/16-1 and KI 2348\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"\u201cQuantitative Reasoning About Database Queries\u201d","award":["GRK 2236"],"award-info":[{"award-number":["GRK 2236"]}]},{"name":"Google PhD Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Infinite probabilistic databases (PDBs) are a framework of probability distributions over infinitely many different database instances. We systematically study the representability problem for such PDBs by means of tuple-independence and first-order views. Although first-order views over tuple-independent PDBs are not a complete representation system for infinite PDBs, they form a fairly robust class: Adding first-order constraints does not give them additional expressive power, and they cover many relevant special cases such as block-independent disjoint PDBs, and PDBs of bounded instance size. We identify criteria for representability (or non-representability) in this class and explore their limits. In addition, we study the expressive power of fragments of first-order logic over tuple-independent PDBs. In general, for infinite PDBs, the landscape of relative expressive power for various classes of views over PDBs with independence assumptions is much more complex than in the finite setting.<\/jats:p>","DOI":"10.1145\/3771733","type":"journal-article","created":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T11:28:46Z","timestamp":1762428526000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Tuple-Independent Representations of Infinite Probabilistic Databases"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0673-5510","authenticated-orcid":false,"given":"Nofar","family":"Carmeli","sequence":"first","affiliation":[{"name":"Inria, LIRMM, University of Montpellier, CNRS","place":["Montpellier, France"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[{"name":"RWTH Aachen University","place":["Aachen, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2041-7201","authenticated-orcid":false,"given":"Peter","family":"Lindner","sequence":"additional","affiliation":[{"name":"RWTH Aachen University","place":["Aachen, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3034-730X","authenticated-orcid":false,"given":"Christoph","family":"Standke","sequence":"additional","affiliation":[{"name":"RWTH Aachen University","place":["Aachen, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,28]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043658"},{"key":"e_1_3_3_3_2","volume-title":"Foundations of Databases (1st ed.)","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases (1st ed.). Addison-Wesley, Boston, MA, USA."},{"issue":"1","key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0304-3975(51)90007-2","article-title":"On the representation and querying of sets of possible worlds","volume":"78","author":"Abiteboul Serge","year":"1991","unstructured":"Serge Abiteboul, Paris Kanellakis, and G\u00f6sta Grahne. 1991. On the representation and querying of sets of possible worlds. Theoretical Computer Science 78, 1 (1991), 159\u2013187. DOI:10.10.1016\/0304-3975(51)90007-2","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_3_5_2","series-title":"CTIT Workshop Proceedings Series","first-page":"17","volume-title":"Proceedings of the 3rd VLDB workshop on Management of Uncertain Data (MUD2009) in conjunction with VLDB 2009, Lyon, France, August 28th, 2009","volume":"09","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 (MUD2009) in conjunction with VLDB 2009, Lyon, France, August 28th, 2009(CTIT Workshop Proceedings Series, Vol. WP09-14). Centre for Telematics and Information Technology (CTIT), University of Twente, The Netherlands, 17\u201332."},{"key":"e_1_3_3_6_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/978-3-662-47666-6_5","volume-title":"Proceedings of the Automata, Languages, and Programming.","volume":"9135","author":"Amarilli Antoine","year":"2015","unstructured":"Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. 2015. Provenance circuits for trees and treelike instances. In Proceedings of the Automata, Languages, and Programming.. Lecture Notes in Computer Science, Vol. 9135, Springer, Berlin, 56\u201368. DOI:10.10.1007\/978-3-662-47666-6_5"},{"key":"e_1_3_3_7_2","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"5:1\u20135:20","volume-title":"23rd International Conference on Database Theory (ICDT 2020)","volume":"155","author":"Amarilli Antoine","year":"2020","unstructured":"Antoine Amarilli and \u0130smail \u0130lkan Ceylan. 2020. A dichotomy for homomorphism-closed queries on probabilistic graphs. In 23rd International Conference on Database Theory (ICDT 2020)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 155). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 5:1\u20135:20. DOI:10.10.4230\/LIPIcs.ICDT.2020.5"},{"key":"e_1_3_3_8_2","first-page":"30","volume-title":"Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA","author":"Andritsos Periklis","year":"2006","unstructured":"Periklis Andritsos, Ariel Fuxman, and Ren\u00e9e J. Miller. 2006. Clean answers over dirty databases: A probabilistic approach. In Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA. IEEE Computer Society, 30. DOI:10.10.1109\/ICDE.2006.35"},{"issue":"5","key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1007\/s00778-009-0149-y","article-title":"\\(\\smash{10^{(10^{6})}}\\)  Worlds and beyond: Efficient representation and processing of incomplete information","volume":"18","author":"Antova Lyublena","year":"2009","unstructured":"Lyublena Antova, Christoph Koch, and Dan Olteanu. 2009. \\(\\smash{10^{(10^{6})}}\\) Worlds and beyond: Efficient representation and processing of incomplete information. The VLDB Journal 18, 5 (2009), 1021. DOI:10.10.1007\/s00778-009-0149-y","journal-title":"The VLDB Journal"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132700"},{"key":"e_1_3_3_11_2","first-page":"3701","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence","author":"Belle Vaishak","year":"2017","unstructured":"Vaishak Belle. 2017. Open-Universe Weighted Model Counting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. AAAI, 3701\u20133708."},{"issue":"1","key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"770","DOI":"10.14778\/1920841.1920939","article-title":"Probabilistic XML via Markov chains","volume":"3","author":"Benedikt Michael","year":"2010","unstructured":"Michael Benedikt, Evgeny Kharlamov, Dan Olteanu, and Pierre Senellart. 2010. Probabilistic XML via Markov chains. Proceedings of the VLDB Endowment 3, 1\u20132 (2010), 770\u2013781. DOI:10.10.14778\/1920841.1920939","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_3_13_2","first-page":"953","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases","author":"Benjelloun Omar","year":"2006","unstructured":"Omar Benjelloun, Anish Das Sarma, Alon Halevy, and Jennifer Widom. 2006. ULDBs: Databases with uncertainty and lineage. In Proceedings of the 32nd International Conference on Very Large Data Bases. VLDB Endowment, 953\u2013964."},{"issue":"3","key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1080\/00031305.1984.10483195","article-title":"A biographical glimpse of William sealy gosset","volume":"38","author":"Boland Philip J.","year":"1984","unstructured":"Philip J. Boland. 1984. A biographical glimpse of William sealy gosset. The American Statistician 38, 3 (1984), 179\u2013183. Retrieved from http:\/\/www.jstor.org\/stable\/2683648","journal-title":"The American Statistician"},{"key":"e_1_3_3_15_2","first-page":"1063","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence","author":"Borgwardt Stefan","year":"2017","unstructured":"Stefan Borgwardt, \u0130smail \u0130lkan Ceylan, and Thomas Lukasiewicz. 2017. Ontology-mediated queries for probabilistic databases. In Proceedings of the 31st AAAI Conference on Artificial Intelligence. AAAI, 1063\u20131069."},{"key":"e_1_3_3_16_2","volume-title":"An Introduction to the Theory of Infinite Series (2nd, revised ed.)","author":"Bromwich T. J. I\u2019A.","year":"1926","unstructured":"T. J. I\u2019A. Bromwich. 1926. An Introduction to the Theory of Infinite Series (2nd, revised ed.). Macmillan and Company Ltd., London, United Kingdom."},{"key":"e_1_3_3_17_2","first-page":"637","volume-title":"Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data","author":"Cai Zhuhua","year":"2013","unstructured":"Zhuhua Cai, Zografoula Vagena, Luis Perez, Subramanian Arumugam, Peter J. Haas, and Christopher Jermaine. 2013. Simulation of database-valued Markov chains using SimSQL. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 637\u2013648. DOI:10.1145\/2463676.2465283"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1145\/3452021.3458315","volume-title":"Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021","author":"Carmeli Nofar","year":"2021","unstructured":"Nofar Carmeli, Martin Grohe, Peter Lindner, and Christoph Standke. 2021. Tuple-independent representations of infinite probabilistic databases. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021. ACM, 388\u2013401. DOI:10.1145\/3452021.3458315"},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"103474","DOI":"10.1016\/j.artint.2021.103474","article-title":"Open-world probabilistic databases: Semantics, algorithms, complexity","volume":"295","author":"Ceylan \u0130smail \u0130lkan","year":"2021","unstructured":"\u0130smail \u0130lkan Ceylan, Adnan Darwiche, and Guy Van den Broeck. 2021. Open-world probabilistic databases: Semantics, algorithms, complexity. Artificial Intelligence 295, Awards Track (2021), 103474. DOI:10.10.1016\/j.artint.2021.103474","journal-title":"Artificial Intelligence"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/3375395.3387666","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Console Marco","year":"2020","unstructured":"Marco Console, Matthias Hofer, and Leonid Libkin. 2020. Queries with arithmetic on incomplete databases. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, New York, NY, USA, 179\u2013189. DOI:10.1145\/3375395.3387666"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"issue":"3","key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/j.jcss.2010.04.006","article-title":"Queries and materialized views on probabilistic databases","volume":"77","author":"Dalvi Nilesh","year":"2011","unstructured":"Nilesh Dalvi, Christopher Re, and Dan Suciu. 2011. Queries and materialized views on probabilistic databases. Journal of Computer and System Sciences 77, 3 (2011), 473\u2013490. DOI:10.10.1016\/j.jcss.2010.04.006","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_3_23_2","first-page":"1","volume-title":"Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Dalvi Nilesh","year":"2007","unstructured":"Nilesh Dalvi and Dan Suciu. 2007. Management of probabilistic data: Foundations and challenges. In Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Association for Computing Machinery, New York, NY, USA, 1\u201312. DOI:10.1145\/1265530.1265531"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_3_3_25_2","volume-title":"Proceedings of the 22nd International Conference on Data Engineering","author":"Sarma Anish Das","year":"2006","unstructured":"Anish Das Sarma, Omar Benjelloun, Alon Halevy, and Jennifer Widom. 2006. Working models for uncertain data. In Proceedings of the 22nd International Conference on Data Engineering. IEEE Computer Society, Los Alamitos, CA, USA, Article 7, 12 pages. DOI:10.10.1109\/ICDE.2006.174"},{"key":"e_1_3_3_26_2","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"6:1\u20136:18","volume-title":"Proceedings of the 22nd International Conference on Database Theory. (ICDT 2019)","volume":"127","author":"Sa Christopher De","year":"2019","unstructured":"Christopher De Sa, Ihab F. Ilyas, Benny Kimelfeld, Christopher R\u00e9, and Theodoros Rekatsinas. 2019. A formal framework for probabilistic unclean databases. In Proceedings of the 22nd International Conference on Database Theory. (ICDT 2019)Leibniz International Proceedings in Informatics (LIPIcs), Vol. 127,Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 6:1\u20136:18. DOI:10.10.4230\/LIPIcs.ICDT.2019.6"},{"key":"e_1_3_3_27_2","first-page":"588","volume-title":"Proceedings of the 30th VLDB Conference","author":"Deshpande Amol","year":"2004","unstructured":"Amol Deshpande, Carlos Guestrin, Samuel R. Madden, Joseph M. Hellerstein, and Wei Hong. 2004. Model-driven data acquisition in sensor networks. In Proceedings of the 30th VLDB Conference. Morgan Kaufmann, 588\u2013599. DOI:10.10.1016\/B978-012088469-8.50053-X"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1109\/ICDE.2002.994710","volume-title":"Proceedings of the 18th International Conference on Data Engineering","author":"Faradjian Anton","year":"2002","unstructured":"Anton Faradjian, Johannes Gehrke, and Philippe Bonnet. 2002. GADT: A probability space ADT for representing and querying the physical world. In Proceedings of the 18th International Conference on Data Engineering. IEEE Computer Society, 201\u2013211. DOI:10.10.1109\/ICDE.2002.994710"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2877203"},{"key":"e_1_3_3_30_2","first-page":"5722","volume-title":"Proceedings of the 38th International Joint Conference on Artificial Intelligence","author":"Friedman Tal","year":"2019","unstructured":"Tal Friedman and Guy Van den Broeck. 2019. On constrained open-world probabilistic databases. In Proceedings of the 38th International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 5722\u20135729. DOI:10.10.24963\/ijcai.2019\/793"},{"key":"e_1_3_3_31_2","volume-title":"Introduction to Random Graphs","author":"Frieze Alan","year":"2016","unstructured":"Alan Frieze and Michal Karonski. 2016. Introduction to Random Graphs. Cambridge University Press, Cambridge, UK. DOI:10.10.1017\/CBO9781316339831"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_3_3_33_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/11896548_24","volume-title":"Proceedings of the Current Trends in Database Technology.","author":"Green Todd J.","year":"2006","unstructured":"Todd J. Green and Val Tannen. 2006. Models for incomplete and probabilistic information. In Proceedings of the Current Trends in Database Technology.Lecture Notes in Computer Science,Springer, 278\u2013296. DOI:10.10.1007\/11896548_24"},{"issue":"3","key":"e_1_3_3_34_2","first-page":"6","article-title":"Lifted probabilistic inference: A guide for the database researcher","volume":"37","author":"Gribkoff Eric","year":"2014","unstructured":"Eric Gribkoff, Dan Suciu, and Guy Van den Broeck. 2014. Lifted probabilistic inference: A guide for the database researcher. Bulletin of the Technical Committee on Data Engineering 37, 3 (2014), 6\u201317.","journal-title":"Bulletin of the Technical Committee on Data Engineering"},{"key":"e_1_3_3_35_2","first-page":"1","volume-title":"Proceedings of the 1st international workshop on Big Uncertain Data","author":"Gribkoff Eric","year":"2014","unstructured":"Eric Gribkoff, Guy Van den Broeck, and Dan Suciu. 2014. The most probable database problem. In Proceedings of the 1st international workshop on Big Uncertain Data. 1\u20137."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3559102"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3549525"},{"key":"e_1_3_3_38_2","doi-asserted-by":"crossref","unstructured":"Martin Grohe and Peter Lindner. 2022. Infinite probabilistic databases. Logical Methods in Computer Science 18 1 (2022) 34:1\u201334:42. DOI:10.10.46298\/lmcs-18(1:34)2022","DOI":"10.46298\/lmcs-18(1:34)2022"},{"key":"e_1_3_3_39_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-642-21295-6_12","volume-title":"Proceedings of the Inductive Logic Programming.","author":"Gutmann Bernd","year":"2011","unstructured":"Bernd Gutmann, Manfred Jaeger, and Luc De Raedt. 2011. Extending problog with continuous distributions. In Proceedings of the Inductive Logic Programming.Lecture Notes in Computer Science,Springer, Berlin, Germany, 76\u201391. DOI:10.10.1007\/978-3-642-21295-6_12"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000828"},{"issue":"11","key":"e_1_3_3_42_2","doi-asserted-by":"crossref","first-page":"1160","DOI":"10.14778\/2350229.2350236","article-title":"Probabilistic databases with markoviews","volume":"5","author":"Jha Abhay","year":"2012","unstructured":"Abhay Jha and Dan Suciu. 2012. Probabilistic databases with markoviews. Proceedings of the VLDB Endowment 5, 11 (2012), 1160\u20131171. DOI:10.10.14778\/2350229.2350236","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_3_43_2","first-page":"157","volume-title":"Proceedings of the 2010 IEEE 26th International Conference on Data Engineering","author":"Kennedy Oliver","year":"2010","unstructured":"Oliver Kennedy and Christoph Koch. 2010. PIP: A database system for great and small expectations. In Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. IEEE, 157\u2013168. DOI:10.10.1109\/ICDE.2010.5447879"},{"key":"e_1_3_3_44_2","series-title":"Studies in Fuzziness and Soft Computing","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-642-37509-5_3","volume-title":"Proceedings of the Advances in Probabilistic Databases for Uncertain Information Management","author":"Kimelfeld Benny","year":"2013","unstructured":"Benny Kimelfeld and Pierre Senellart. 2013. Probabilistic XML: Models and complexity. In Proceedings of the Advances in Probabilistic Databases for Uncertain Information Management. Studies in Fuzziness and Soft Computing. Springer, 39\u201366. DOI:10.10.1007\/978-3-642-37509-5_3"},{"issue":"1","key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"313","DOI":"10.14778\/1453856.1453894","article-title":"Conditioning probabilistic databases","volume":"1","author":"Koch Christoph","year":"2008","unstructured":"Christoph Koch and Dan Olteanu. 2008. Conditioning probabilistic databases. Proceedings of the VLDB Endowment 1, 1 (2008), 313\u2013325. DOI:10.10.14778\/1453856.1453894","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_3_46_2","volume-title":"Probabilistic Graphical Models\u2014Principles and Techniques","author":"Koller Daphne","year":"2009","unstructured":"Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models\u2014Principles and Techniques. MIT Press."},{"key":"e_1_3_3_47_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","year":"2004","unstructured":"Leonid Libkin. 2004. Elements of Finite Model Theory. Springer-Verlag, Berlin, Germany. DOI:10.10.1007\/978-3-662-07003-1"},{"key":"e_1_3_3_48_2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/3196959.3196983","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Libkin Leonid","year":"2018","unstructured":"Leonid Libkin. 2018. Certain answers meet zero-one laws. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, New York, NY, USA, 195\u2013207. DOI:10.1145\/3196959.3196983"},{"key":"e_1_3_3_49_2","first-page":"573","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017","author":"Meneghetti Niccol\u00f2","year":"2017","unstructured":"Niccol\u00f2 Meneghetti, Oliver Kennedy, and Wolfgang Gatterbauer. 2017. Beta probabilistic databases: A scalable approach to belief updating and parameter learning. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017. ACM, 573\u2013586. DOI:10.1145\/3035918.3064026"},{"key":"e_1_3_3_50_2","first-page":"1352","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence","author":"Milch Brian","year":"2005","unstructured":"Brian Milch, Bhaskara Marthi, Stuart Russell, David Sontag, Daniel L. Ong, and Andrey Kolobov. 2005. BLOG: Probabilistic models with unknown objects. In Proceedings of the 19th International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1352\u20131359."},{"key":"e_1_3_3_51_2","volume-title":"Proceedings of the Managing and Mining Uncertain Data","author":"Sarkar Sumit","year":"2009","unstructured":"Sumit Sarkar and Debabrata Dey. 2009. Relational models and algebra for uncertain data. In Proceedings of the Managing and Mining Uncertain Data. Springer, Boston, MA, USA, Chapter 3. DOI:10.10.1007\/978-0-387-09690-2_3"},{"issue":"5","key":"e_1_3_3_52_2","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1007\/s00778-009-0153-2","article-title":"PrDB: Managing and exploiting rich correlations in probabilistic databases","volume":"18","author":"Sen Prithviraj","year":"2009","unstructured":"Prithviraj Sen, Amol Deshpande, and Lise Getoor. 2009. PrDB: Managing and exploiting rich correlations in probabilistic databases. VLDB Journal 18, 5 (2009), 1065\u20131090. DOI:10.10.1007\/s00778-009-0153-2","journal-title":"VLDB Journal"},{"key":"e_1_3_3_53_2","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1145\/1376616.1376744","volume-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data","author":"Singh Sarvjeet","year":"2008","unstructured":"Sarvjeet Singh, Chris Mayfield, Sagar Mittal, Sunil Prabhakar, Susanne Hambrusch, and Rahul Shah. 2008. Orion 2.0: Native support for uncertain data. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 1239\u20131242. DOI:10.1145\/1376616.1376744"},{"key":"e_1_3_3_54_2","first-page":"1053","volume-title":"Proceedings of the 24th International Conference on Data Engineering","author":"Singh Sarvjeet","year":"2008","unstructured":"Sarvjeet Singh, Chris Mayfield, Rahul Shah, Sunil Prabhakar, Susanne E. Hambrusch, Jennifer Neville, and Reynold Cheng. 2008. Database support for probabilistic attributes and tuples. In Proceedings of the 24th International Conference on Data Engineering. 1053\u20131061. DOI:10.10.1109\/ICDE.2008.4497514"},{"key":"e_1_3_3_55_2","first-page":"368","volume-title":"Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence","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. AUAI Press, Arlington, Virginia, USA, 368\u2013375."},{"key":"e_1_3_3_56_2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/3375395.3389129","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Suciu Dan","year":"2020","unstructured":"Dan Suciu. 2020. Probabilistic databases for all. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. Association for Computing Machinery, New York, NY, USA, 19\u201331. DOI:10.1145\/3375395.3389129"},{"key":"e_1_3_3_57_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01879-4","volume-title":"Probabilistic Databases (1st ed.)","author":"Suciu Dan","year":"2011","unstructured":"Dan Suciu, Dan Olteanu, Christopher R\u00e9, and Christoph Koch. 2011. Probabilistic Databases (1st ed.). Morgan & Claypool, San Rafael, CA, USA. DOI:10.10.2200\/S00362ED1V01Y201105DTM016"},{"issue":"3","key":"e_1_3_3_58_2","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1561\/1900000052","article-title":"Query processing on probabilistic data: A survey","volume":"7","author":"Broeck Guy Van den","year":"2017","unstructured":"Guy Van den Broeck and Dan Suciu. 2017. Query processing on probabilistic data: A survey. Foundations and Trends\u00ae in Databases 7, 3\u20134 (2017), 197\u2013341. DOI:10.10.1561\/1900000052","journal-title":"Foundations and Trends\u00ae in Databases"},{"key":"e_1_3_3_59_2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-1-4615-5643-5_10","volume-title":"Proceedings of the Logics for Databases and Information Systems","author":"Meyden Ron van der","year":"1998","unstructured":"Ron van der Meyden. 1998. Logical approaches to incomplete information: A survey. In Proceedings of the Logics for Databases and Information Systems. Springer US, Boston, MA, USA, 307\u2013356. DOI:10.10.1007\/978-1-4615-5643-5_10"},{"key":"e_1_3_3_60_2","first-page":"405","volume-title":"Proceedings of the 9th International Conference on Web-Age Information Management","author":"Zhang Wenjie","year":"2008","unstructured":"Wenjie Zhang, Xuemin Lin, Jian Pei, and Ying Zhang. 2008. Managing uncertain data: Probabilistic approaches. In Proceedings of the 9th International Conference on Web-Age Information Management. IEEE Computer Society, 405\u2013412. DOI:10.10.1109\/WAIM.2008.42"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T13:18:17Z","timestamp":1774703897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771733"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,28]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1145\/3771733"],"URL":"https:\/\/doi.org\/10.1145\/3771733","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,28]]},"assertion":[{"value":"2021-12-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-04","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}