{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:16:48Z","timestamp":1778807808852,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2008,11]]},"abstract":"<jats:p>\n            Information describing the origin of data, generally referred to as\n            <jats:italic>provenance<\/jats:italic>\n            , is important in scientific and curated databases where it is the basis for the trust one puts in their contents. Since such databases are constructed using operations of both query and update languages, it is of paramount importance to describe the effect of these languages on provenance.\n          <\/jats:p>\n          <jats:p>\n            In this article we study provenance for query and update languages that are closely related to SQL, and compare two ways in which they can manipulate provenance so that elements of the input are rearranged to elements of the output:\n            <jats:italic>implicit provenance<\/jats:italic>\n            , where a query or update only provides the rearranged output, and provenance is provided implicitly by a default provenance semantics; and\n            <jats:italic>explicit provenance<\/jats:italic>\n            , where a query or update provides both the output and the description of the provenance of each component of the output. Although explicit provenance is in general more expressive, we show that the classes of implicit provenance operations expressible by query and update languages correspond to natural semantic subclasses of the explicit provenance queries.\n          <\/jats:p>\n          <jats:p>One of the consequences of this study is that provenance separates the expressive power of query and update languages. The model is also relevant to annotation propagation schemes in which annotations on the input to a query or update have to be transferred to the output or vice versa.<\/jats:p>","DOI":"10.1145\/1412331.1412340","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["On the expressiveness of implicit provenance in query and update languages"],"prefix":"10.1145","volume":"33","author":[{"given":"Peter","family":"Buneman","sequence":"first","affiliation":[{"name":"University of Edinburgh, Scotland, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Cheney","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Scotland, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley New York.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley New York."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237689"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 6th International Workshop on Database Programming Languages (DBPL). Springer-Verlag","author":"Beeri C.","unstructured":"Beeri , C. , Milo , T. , and Ta-Shma , P . 1998. Towards a language for the fully generic queries . In Proceedings of the 6th International Workshop on Database Programming Languages (DBPL). Springer-Verlag , Berlin, Germany, 239--259. Beeri, C., Milo, T., and Ta-Shma, P. 1998. Towards a language for the fully generic queries. In Proceedings of the 6th International Workshop on Database Programming Languages (DBPL). Springer-Verlag, Berlin, Germany, 239--259."},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Databases (VLDB). VLDB Endowment","author":"Benjelloun O.","unstructured":"Benjelloun , O. , Das Sarma , A. , Halevy , A. , and Widom , J . 2006. ULDBs: databases with uncertainty and lineage . In Proceedings of the 32nd International Conference on Very Large Databases (VLDB). VLDB Endowment , Seoul, Korea, 953--964. Benjelloun, O., Das Sarma, A., Halevy, A., and Widom, J. 2006. ULDBs: databases with uncertainty and lineage. In Proceedings of the 32nd International Conference on Very Large Databases (VLDB). VLDB Endowment, Seoul, Korea, 953--964."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0156-6"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057977.1057978"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142534"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_15"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 8th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science","volume":"1973","author":"Buneman P.","unstructured":"Buneman , P. , Khanna , S. , and Tan , W . 2001. Why and where: a characterization of data provenance . In Proceedings of the 8th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science , vol. 1973 . Springer, Berlin, Germany, 316--330. Buneman, P., Khanna, S., and Tan, W. 2001. Why and where: a characterization of data provenance. In Proceedings of the 8th International Conference on Database Theory (ICDT). Lecture Notes in Computer Science, vol. 1973. Springer, Berlin, Germany, 316--330."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00024-Q"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/567532.567537"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Cheney J. Ahmed A. and \n      Acar U. A\n  . \n  2007\n  . Provenance as dependency analysis. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL) Vienna Austria Lecture Notes in Computer Science Vol. \n  4797 Springer Berlin Germany 138--152.   Cheney J. Ahmed A. and Acar U. A. 2007. Provenance as dependency analysis. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL) Vienna Austria Lecture Notes in Computer Science Vol. 4797 Springer Berlin Germany 138--152.","DOI":"10.1007\/978-3-540-75987-4_10"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_2_14_1","volume-title":"Eds","author":"Foster I.","year":"2006","unstructured":"Foster , I. and Moreau , L. , Eds . 2006 . Proceedings of the International Provenance and Annotation Workshop (IPAW). Lecture Notes in Computer Science, Vol. 4145 , Springer-Verlag , Berlin, Germany. Foster, I. and Moreau, L., Eds. 2006. Proceedings of the International Provenance and Annotation Workshop (IPAW). Lecture Notes in Computer Science, Vol. 4145, Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkm1037"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1129754.1129942"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 11th International Symposium on Database Programming Languages (DBPL)","volume":"4797","author":"Geerts F.","unstructured":"Geerts , F. and Van den Bussche, J. 2007. Relational completeness of query languages for annotated databases . In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL) , Vienna, Austria, Lecture Notes in Computer Science , Vol. 4797 , Springer, Berlin, Germany, 127--137. Geerts, F. and Van den Bussche, J. 2007. Relational completeness of query languages for annotated databases. In Proceedings of the 11th International Symposium on Database Programming Languages (DBPL), Vienna, Austria, Lecture Notes in Computer Science, Vol. 4797, Springer, Berlin, Germany, 127--137."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1523"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1999.787620"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/128765.128768"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084805.1084812"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00293-9"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-40063-X"},{"key":"e_1_2_2_25_1","first-page":"45","article-title":"Research problems in data provenance","volume":"27","author":"Tan W.","year":"2004","unstructured":"Tan , W. 2004 . Research problems in data provenance . IEEE Data Eng. Bull. 27 , 4, 45 -- 52 . Tan, W. 2004. Research problems in data provenance. IEEE Data Eng. Bull. 27, 4, 45--52.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00301-1"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the 16th International Conference on Very Large Data Bases (VLDB). Brisbane","author":"Wang Y. R.","unstructured":"Wang , Y. R. and Madnick , S. E . 1990. A polygen model for heterogeneous database systems: the source tagging perspective . In Proceedings of the 16th International Conference on Very Large Data Bases (VLDB). Brisbane , Queensland, Australia. Morgan Kaufmann, San Francisco, CA, 519--538. Wang, Y. R. and Madnick, S. E. 1990. A polygen model for heterogeneous database systems: the source tagging perspective. In Proceedings of the 16th International Conference on Very Large Data Bases (VLDB). Brisbane, Queensland, Australia. Morgan Kaufmann, San Francisco, CA, 519--538."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0037"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003585"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the 13th International Conference on Data Engineering (ICDE), IEEE Computer Society Press","author":"Woodruff A.","unstructured":"Woodruff , A. and Stonebraker , M . 1997. Supporting fine-grained data lineage in a database visualization environment . In Proceedings of the 13th International Conference on Data Engineering (ICDE), IEEE Computer Society Press , Los Alamitos, CA, 91--102. Woodruff, A. and Stonebraker, M. 1997. Supporting fine-grained data lineage in a database visualization environment. In Proceedings of the 13th International Conference on Data Engineering (ICDE), IEEE Computer Society Press, Los Alamitos, CA, 91--102."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412340","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412331.1412340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1412331.1412340"],"URL":"https:\/\/doi.org\/10.1145\/1412331.1412340","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2007-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}