{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:13:34Z","timestamp":1784099614691,"version":"3.55.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,2,22]],"date-time":"2018-02-22T00:00:00Z","timestamp":1519257600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2018,2,22]]},"abstract":"<jats:p>We review the basics of data provenance in relational databases. We describe different provenance formalisms, from Boolean provenance to provenance semirings and beyond, that can be used for a wide variety of purposes, to obtain additional information on the output of a query. We discuss representation systems for data provenance, circuits in particular, with a focus on practical implementation. Finally, we explain how provenance is practically used for probabilistic query evaluation in probabilistic databases.<\/jats:p>","DOI":"10.1145\/3186549.3186551","type":"journal-article","created":{"date-parts":[[2018,2,23]],"date-time":"2018-02-23T16:40:01Z","timestamp":1519404001000},"page":"5-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Provenance and Probabilities in Relational Databases"],"prefix":"10.1145","volume":"46","author":[{"given":"Pierre","family":"Senellart","sequence":"first","affiliation":[{"name":"DI ENS, ENS, CNRS, PSL Research University &amp; Inria Paris&amp;LTCI, T\u00e9l\u00e9com ParisTech, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,2,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","year":"1995","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . Foundations of Databases . Addison-Wesley , 1995 . Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"key":"e_1_2_1_2_1","volume-title":"ICDT","author":"Amarilli Antoine","year":"2017","unstructured":"Antoine Amarilli , Pierre Bourhis , Mika\u00ebl Monet , and Pierre Senellart . Combined tractability of query evaluation via tree automata and cycluits . In ICDT , 2017 . Antoine Amarilli, Pierre Bourhis, Mika\u00ebl Monet, and Pierre Senellart. Combined tractability of query evaluation via tree automata and cycluits. In ICDT, 2017."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902301"},{"key":"e_1_2_1_5_1","unstructured":"Antoine Amarilli and Mika\u00ebl Monet. Example of a naturally ordered semiring which is not an m-semiring. http:\/\/math.stackexchange. com\/questions\/1966858 2016.  Antoine Amarilli and Mika\u00ebl Monet. Example of a naturally ordered semiring which is not an m-semiring. http:\/\/math.stackexchange. com\/questions\/1966858 2016."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"K. Amer. Algebra Universalis 18(1) 1984.  K. Amer. Algebra Universalis 18(1) 1984.","DOI":"10.1007\/BF01182246"},{"key":"e_1_2_1_7_1","volume-title":"TaPP","author":"Amsterdamer Yael","year":"2011","unstructured":"Yael Amsterdamer , Daniel Deutch , and Val Tannen . On the limitations of provenance for queries with difference . In TaPP , 2011 . Yael Amsterdamer, Daniel Deutch, and Val Tannen. On the limitations of provenance for queries with difference. In TaPP, 2011."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_9_1","volume-title":"VLDB","author":"Benjelloun Omar","year":"2006","unstructured":"Omar Benjelloun , Anish Das Sarma , Alon Halevy , and Jennifer Widom . ULDBs : Databases with uncertainty and lineage . In VLDB , 2006 . Omar Benjelloun, Anish Das Sarma, Alon Halevy, and Jennifer Widom. ULDBs: Databases with uncertainty and lineage. In VLDB, 2006."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656274"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2000.839437"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_16_1","author":"Darwiche Adnan","year":"2001","unstructured":"Adnan Darwiche . On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Applied Non-Classical Logics, 11(1--2) , 2001 . Adnan Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Applied Non-Classical Logics, 11(1--2), 2001.","journal-title":"J. Applied Non-Classical Logics, 11(1--2)"},{"key":"e_1_2_1_17_1","volume-title":"ECAI","author":"Darwiche Adnan","year":"2004","unstructured":"Adnan Darwiche . New advances in compiling CNF to decomposable negation normal form . In ECAI , 2004 . Adnan Darwiche. New advances in compiling CNF to decomposable negation normal form. In ECAI, 2004."},{"issue":"1","key":"e_1_2_1_18_1","volume":"17","author":"Darwiche Adnan","year":"2002","unstructured":"Adnan Darwiche and Pierre Marquis . A knowledge compilation map. J. Artificial Intelligence Research , 17 ( 1 ), 2002 . Adnan Darwiche and Pierre Marquis. A knowledge compilation map. J. Artificial Intelligence Research, 17(1), 2002.","journal-title":"J. Artificial Intelligence Research"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376772"},{"key":"e_1_2_1_20_1","volume-title":"ICDT","author":"Deutch Daniel","year":"2014","unstructured":"Daniel Deutch , Tova Milo , Sudeepa Roy , and Val Tannen . Circuits for Datalog provenance . In ICDT , 2014 . Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. Circuits for Datalog provenance. In ICDT, 2014."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1667106"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140445"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"issue":"2","key":"e_1_2_1_24_1","volume":"8","author":"Geerts Floris","year":"2010","unstructured":"Floris Geerts and Antonella Poggi . On database query languages for K-relations. J. Applied Logic , 8 ( 2 ), 2010 . Floris Geerts and Antonella Poggi. On database query languages for K-relations. J. Applied Logic, 8(2), 2010.","journal-title":"K-relations. J. Applied Logic"},{"key":"e_1_2_1_25_1","volume-title":"Provenance in ORCHESTRA","author":"Green Grigoris","year":"2010","unstructured":"Grigoris Green , Todd J. and Karvounarakis , Zach Ives , and Val Tannen . Provenance in ORCHESTRA . IEEE Data Eng. Bull , 33(3), 2010 . Grigoris Green, Todd J. and Karvounarakis, Zach Ives, and Val Tannen. Provenance in ORCHESTRA. IEEE Data Eng. Bull, 33(3), 2010."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_28_1","volume-title":"Green and Val Tannen. Models for incomplete and probabilistic information","author":"Todd","year":"2006","unstructured":"Todd J. Green and Val Tannen. Models for incomplete and probabilistic information . IEEE Data Eng. Bull ., 29(1), 2006 . Todd J. Green and Val Tannen. Models for incomplete and probabilistic information. IEEE Data Eng. Bull., 29(1), 2006."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0042"},{"key":"e_1_2_1_30_1","volume-title":"LDOW","author":"Hartig Olaf","year":"2009","unstructured":"Olaf Hartig . Provenance information in the web of data . In LDOW , 2009 . Olaf Hartig. Provenance information in the web of data. In LDOW, 2009."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739082"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9392-5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380776.2380778"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171738"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1523"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3044713"},{"key":"e_1_2_1_39_1","volume-title":"Semiring frameworks and algorithms for shortest-distance problems. J. Automata, Languages and Combinatorics, 7(3)","author":"Mohri Mehryar","year":"2002","unstructured":"Mehryar Mohri . Semiring frameworks and algorithms for shortest-distance problems. J. Automata, Languages and Combinatorics, 7(3) , 2002 . Mehryar Mohri. Semiring frameworks and algorithms for shortest-distance problems. J. Automata, Languages and Combinatorics, 7(3), 2002."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2926693.2929905"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30353-1_36"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447826"},{"key":"e_1_2_1_43_1","volume-title":"https: \/\/github.com\/PierreSenellart\/provsql","author":"Senellart Pierre","year":"2017","unstructured":"Pierre Senellart . Prov SQL. https: \/\/github.com\/PierreSenellart\/provsql , 2017 . Pierre Senellart. ProvSQL. https: \/\/github.com\/PierreSenellart\/provsql, 2017."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544869"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. Probabilistic Databases. Morgan&Claypool 2011.   Dan Suciu Dan Olteanu Christopher R\u00e9 and Christoph Koch. Probabilistic Databases. Morgan&Claypool 2011.","DOI":"10.1007\/978-3-031-01879-4"},{"key":"e_1_2_1_46_1","volume-title":"Studies in Constrained Mathematics and Mathematical Logic","author":"Tseitin G","year":"1968","unstructured":"G Tseitin . On the complexity of derivation in propositional calculus . Studies in Constrained Mathematics and Mathematical Logic , 1968 . G Tseitin. On the complexity of derivation in propositional calculus. Studies in Constrained Mathematics and Mathematical Logic, 1968."},{"key":"e_1_2_1_47_1","volume-title":"The complexity of Boolean functions","author":"Wegener Ingo","year":"1987","unstructured":"Ingo Wegener . The complexity of Boolean functions . Wiley , 1987 . Ingo Wegener. The complexity of Boolean functions. Wiley, 1987."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/893658"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186549.3186551","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186549.3186551","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:27Z","timestamp":1750212687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186549.3186551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,22]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,2,22]]}},"alternative-id":["10.1145\/3186549.3186551"],"URL":"https:\/\/doi.org\/10.1145\/3186549.3186551","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2018,2,22]]},"assertion":[{"value":"2018-02-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}