Bibliography
Aryak Sen, Silviu Maniu, and Pierre Senellart. ProvSQL: a general system for keeping track of the provenance and probability of data. In Proc. IEEE 42nd International Conference on Data Engineering (ICDE), Montréal, Canada, May 2026. 2026. Also arXiv abs/2504.12058.
Pierre Senellart, Louis Jachiet, Silviu Maniu, and Yann Ramusat. ProvSQL: provenance and probability management in PostgreSQL. Proc. VLDB Endow., 11(12):2034–2037, 2018. Demonstration. doi:10.14778/3229863.3236253.
Pierre Senellart. Provenance in databases: principles and applications. In Reasoning Web. Explainable Artificial Intelligence - 15th International Summer School 2019, Bolzano, Italy, September 20-24, 2019, Tutorial Lectures, Lecture Notes in Computer Science, 104–109. Springer, 2019. doi:10.1007/978-3-030-31423-1_3.
Pierre Senellart. Provenance and probabilities in relational databases. SIGMOD Rec., 46(4):5–15, 2017. doi:10.1145/3186549.3186551.
Todd J. Green, Gregory Karvounarakis, and Val Tannen. Provenance semirings. In Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China, 31–40. ACM, 2007. doi:10.1145/1265530.1265535.
Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. Circuits for datalog provenance. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, 201–212. OpenProceedings.org, 2014. doi:10.5441/002/ICDT.2014.22.
Yael Amsterdamer, Daniel Deutch, and Val Tannen. Provenance for aggregate queries. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, 153–164. ACM, 2011. doi:10.1145/1989284.1989302.
Floris Geerts and Antonella Poggi. On database query languages for K-relations. J. Appl. Log., 8(2):173–185, 2010. doi:10.1016/J.JAL.2009.09.001.
Todd J. Green and Val Tannen. Models for incomplete and probabilistic information. In Current Trends in Database Technology - EDBT 2006, EDBT 2006 Workshops, Munich, Germany, March 26-31, 2006, Revised Selected Papers, Lecture Notes in Computer Science, 278–296. Springer, 2006. doi:10.1007/11896548_24.
Nilesh N. Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. VLDB J., 16(4):523–544, 2007. doi:10.1007/s00778-006-0004-3.
Nilesh N. Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. J. ACM, 59(6):30:1–30:87, 2012. doi:10.1145/2395116.2395119.
Abhay Kumar Jha and Dan Suciu. Knowledge compilation meets database theory: compiling queries to decision diagrams. In Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, 162–173. ACM, 2011. doi:10.1145/1938551.1938574.
Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory Comput. Syst., 64(5):861–914, 2020. doi:10.1007/S00224-019-09930-2.
Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, Lecture Notes in Computer Science, 56–68. Springer, 2015. doi:10.1007/978-3-662-47666-6_5.
Antoine Amarilli. Leveraging the Structure of Uncertain Data. PhD thesis, Télécom ParisTech, 2016. tel-01345836. URL: https://theses.hal.science/tel-01345836.
Richard M. Karp, Michael Luby, and Neal Madras. Monte-carlo approximation algorithms for enumeration problems. J. Algorithms, 10(3):429–448, 1989. doi:10.1016/0196-6774(89)90038-2.
Dan Olteanu, Jiewen Huang, and Christoph Koch. Approximate confidence computation in probabilistic databases. In Proceedings of the 26th International Conference on Data Engineering, ICDE 2010, March 1-6, 2010, Long Beach, California, USA, 145–156. IEEE Computer Society, 2010. doi:10.1109/ICDE.2010.5447826.
Yong Lai, Kuldeep S. Meel, and Roland H. C. Yap. Panini: an efficient and flexible knowledge compiler. In Ruzica Piskac and Zvonimir Rakamaric, editors, Computer Aided Verification - 37th International Conference, CAV 2025, Zagreb, Croatia, July 23-25, 2025, Proceedings, Part III, Lecture Notes in Computer Science, 92–105. Springer, 2025. doi:10.1007/978-3-031-98682-6_6.
Yong Lai, Dayou Liu, and Minghao Yin. New canonical representations by augmenting OBDDs with conjunctive decomposition. J. Artif. Intell. Res., 58:453–521, 2017. doi:10.1613/JAIR.5271.
Shubham Sharma, Subhajit Roy, Mate Soos, and Kuldeep S. Meel. GANAK: A scalable probabilistic exact model counter. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, 1169–1176. ijcai.org, 2019. doi:10.24963/IJCAI.2019/163.
Tuukka Korhonen and Matti Järvisalo. Integrating tree decompositions into decision heuristics of propositional model counters (short paper). In 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, LIPIcs, 8:1–8:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.CP.2021.8.
Jeffrey M. Dudek, Vu H. N. Phan, and Moshe Y. Vardi. DPMC: weighted model counting by dynamic programming on project-join trees. In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Lecture Notes in Computer Science, 211–230. Springer, 2020. doi:10.1007/978-3-030-58475-7_13.
Jean-Marie Lagniez and Pierre Marquis. An improved decision-DNNF compiler. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 667–673. ijcai.org, 2017. doi:10.24963/ijcai.2017/93.
Jean-Marie Lagniez and Pierre Marquis. About caching in D4 2.0. In Workshop on Counting and Sampling 2021. Barcelona, Spain, July 2021. URL: https://hal.science/hal-04252723.
Adnan Darwiche. New advances in compiling CNF into decomposable negation normal form. In Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI'2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004, 328–332. IOS Press, 2004.
Umut Oztok and Adnan Darwiche. A top-down compiler for sentential decision diagrams. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, 3141–3148. AAAI Press, 2015.
Christian J. Muise, Sheila A. McIlraith, J. Christopher Beck, and Eric I. Hsu. Dsharp: fast d-DNNF compilation with sharpSAT. In Advances in Artificial Intelligence - 25th Canadian Conference on Artificial Intelligence, Canadian AI 2012, Toronto, ON, Canada, May 28-30, 2012. Proceedings, volume 7310 of Lecture Notes in Computer Science, 356–361. Springer, 2012. doi:10.1007/978-3-642-30353-1_36.
Abhay Kumar Jha and Dan Suciu. Probabilistic databases with markoviews. Proc. VLDB Endow., 5(11):1160–1171, 2012. doi:10.14778/2350229.2350236.
Pratik Karmakar, Mikaël Monet, Pierre Senellart, and Stéphane Bressan. Expected shapley-like scores of boolean functions: complexity and applications to probabilistic databases. Proc. ACM Manag. Data, 2(2):92, 2024. Presented at the PODS 2024 conference in Santiago, Chile. Also arXiv abs/2401.06493. doi:10.1145/3651593.
Peter Buneman, Sanjeev Khanna, and Wang Chiew Tan. Why and where: A characterization of data provenance. In Database Theory - ICDT 2001, 8th International Conference, London, UK, January 4-6, 2001, Proceedings, Lecture Notes in Computer Science, 316–330. Springer, 2001. doi:10.1007/3-540-44503-X_20.
Pierre Bourhis, Daniel Deutch, and Yuval Moskovitch. Equivalence-invariant algebraic provenance for hyperplane update queries. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, 415–429. ACM, 2020. doi:10.1145/3318464.3380578.
Albert Ariel Widiaatmaja, Belkis Djeffal, Ashish Dandekar, and Pierre Senellart. Demonstration of ProvSQL update provenance through temporal databases. In Proceedings of the Provenance Week 2025, PW'25, Berlin, Germany, June 22-27, 2025, 71–76. ACM, 2025. Demonstration. doi:10.1145/3736229.3736253.
Fajrian Yunus, Pratik Karmakar, Pierre Senellart, Talel Abdessalem, and Stéphane Bressan. Using A probabilistic database in an image retrieval application. In Proceedings 28th International Conference on Extending Database Technology, EDBT 2025, Barcelona, Spain, March 25-28, 2025, 1106–1109. OpenProceedings.org, 2025. doi:10.48786/EDBT.2025.100.
Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. ISBN 978-3-031-00751-4. doi:10.2200/S00362ED1V01Y201105DTM016.
Wolfgang Gatterbauer and Dan Suciu. Approximate lifted inference with probabilistic databases. Proc. VLDB Endow., 8(5):629–640, 2015. doi:10.14778/2735479.2735494.
Silviu Maniu, Pierre Senellart, and Suraj Jog. An experimental study of the treewidth of real-world graph data. In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, volume 127 of LIPIcs, 12:1–12:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICDT.2019.12.
Christopher Ré and Dan Suciu. The trichotomy of HAVING queries on a probabilistic database. VLDB J., 18(5):1091–1116, 2009. doi:10.1007/s00778-009-0151-4.