{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T18:07:34Z","timestamp":1776708454840,"version":"3.51.2"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,13]],"date-time":"2015-05-13T00:00:00Z","timestamp":1431475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EPSRC SOCIAM"},{"name":"ORCHID projects"},{"name":"FP7 SmartSociety project"},{"name":"ESRC ebook project"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2015,5,26]]},"abstract":"<jats:p>On the Web, where resources such as documents and data are published, shared, transformed, and republished, provenance is a crucial piece of metadata that would allow users to place their trust in the resources they access. The open provenance model (OPM) is a community data model for provenance that is designed to facilitate the meaningful interchange of provenance information between systems. Underpinning OPM is a notion of directed graph, where nodes represent data products and processes involved in past computations and edges represent dependencies between them; it is complemented by graphical inference rules allowing new dependencies to be derived. Until now, however, the OPM model was a purely syntactical endeavor. The present article extends OPM graphs with an explicit distinction between precise and imprecise edges. Then a formal semantics for the thus enriched OPM graphs is proposed, by viewing OPM graphs as temporal theories on the temporal events represented in the graph. The original OPM inference rules are scrutinized in view of the semantics and found to be sound but incomplete. An extended set of graphical rules is provided and proved to be complete for inference. The article concludes with applications of the formal semantics to inferencing in OPM graphs, operators on OPM graphs, and a formal notion of refinement among OPM graphs.<\/jats:p>","DOI":"10.1145\/2734116","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T16:05:34Z","timestamp":1431705934000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["A Formal Account of the Open Provenance Model"],"prefix":"10.1145","volume":"9","author":[{"given":"Natalia","family":"Kwasnikowska","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}]},{"given":"Luc","family":"Moreau","sequence":"additional","affiliation":[{"name":"University of Southampton, Southampton, United Kingdom"}]},{"given":"Jan Van Den","family":"Bussche","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeek, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2015,5,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376918"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.26.6"},{"key":"e_1_2_1_3_1","volume-title":"Semantics of the PROV Data Model. W3C Working Draft WD-prov-sem-20130312","author":"Cheney James","unstructured":"James Cheney . 2013. Semantics of the PROV Data Model. W3C Working Draft WD-prov-sem-20130312 . World Wide Web Consortium . James Cheney. 2013. Semantics of the PROV Data Model. W3C Working Draft WD-prov-sem-20130312. World Wide Web Consortium."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_5_1","unstructured":"James Cheney Paolo Missier Luc Moreau and Tom De Nies (Eds.). 2013. Constraints of the PROV Data Model. W3C Recommendation REC-prov-constraints-20130430. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/2013\/REC-prov-constraints-20130430\/.  James Cheney Paolo Missier Luc Moreau and Tom De Nies (Eds.). 2013. Constraints of the PROV Data Model. W3C Recommendation REC-prov-constraints-20130430. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/2013\/REC-prov-constraints-20130430\/."},{"key":"e_1_2_1_6_1","volume-title":"Poceedings of the 5th USENIX Workshop on the Theory and Practice of Provenance. https:\/\/www.usenix.org\/conference\/tapp13\/provenance-analyzer.","author":"Dey Saumen","year":"2013","unstructured":"Saumen Dey , Sean Riddle , and Bertram Lud\u00e4scher . 2013 . Provenance analyzer: Exploring provenance semantics with logic rules . In Poceedings of the 5th USENIX Workshop on the Theory and Practice of Provenance. https:\/\/www.usenix.org\/conference\/tapp13\/provenance-analyzer. Saumen Dey, Sean Riddle, and Bertram Lud\u00e4scher. 2013. Provenance analyzer: Exploring provenance semantics with logic rules. In Poceedings of the 5th USENIX Workshop on the Theory and Practice of Provenance. https:\/\/www.usenix.org\/conference\/tapp13\/provenance-analyzer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.10.011"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.10.010"},{"key":"e_1_2_1_9_1","volume-title":"Sam Coppens, Daniel Garijo, Jose Manuel Gomez, Paolo Missier, Satya Sahoo, and Jun Zhao (Eds.).","author":"Gil Yolanda","year":"2010","unstructured":"Yolanda Gil , James Cheney , Paul Groth , Olaf Hartig , Simon Miles , Luc Moreau , Paulo Pinheiro da Silva , Sam Coppens, Daniel Garijo, Jose Manuel Gomez, Paolo Missier, Satya Sahoo, and Jun Zhao (Eds.). 2010 . Provenance XG Final Report. W3C Incubator Group Report XGR-prov-20101214. World Wide Web Consortium . http:\/\/www.w3.org\/2005\/Incubator\/prov\/XGR-prov-20101214\/. Yolanda Gil, James Cheney, Paul Groth, Olaf Hartig, Simon Miles, Luc Moreau, Paulo Pinheiro da Silva, Sam Coppens, Daniel Garijo, Jose Manuel Gomez, Paolo Missier, Satya Sahoo, and Jun Zhao (Eds.). 2010. Provenance XG Final Report. W3C Incubator Group Report XGR-prov-20101214. World Wide Web Consortium. http:\/\/www.w3.org\/2005\/Incubator\/prov\/XGR-prov-20101214\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.10.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/axi147"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 16th International Conference on Very Large Data Bases. 455--468","author":"Hull Richard","year":"1990","unstructured":"Richard Hull and Masatoshi Yoshikawa . 1990 . ILOG: Declarative creation and manipulation of object identifiers . In Proceedings of the 16th International Conference on Very Large Data Bases. 455--468 . Richard Hull and Masatoshi Yoshikawa. 1990. ILOG: Declarative creation and manipulation of object identifiers. In Proceedings of the 16th International Conference on Very Large Data Bases. 455--468."},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Jacobs Ian","year":"2004","unstructured":"Ian Jacobs and Norman Walsh . 2004 . Architecture of the World Wide Web, Volume One. W3C Recommendation 15 December 2004 . Retrieved April 21, 2015, from http:\/\/www.w3.org\/TR\/webarch\/. Ian Jacobs and Norman Walsh. 2004. Architecture of the World Wide Web, Volume One. W3C Recommendation 15 December 2004. Retrieved April 21, 2015, from http:\/\/www.w3.org\/TR\/webarch\/."},{"key":"e_1_2_1_14_1","volume-title":"A Formal Account of the Open Provenance Model. eprint 271819","author":"Kwasnikowska Natalia","unstructured":"Natalia Kwasnikowska , Luc Moreau , and Jan Van den Bussche . 2010. A Formal Account of the Open Provenance Model. eprint 271819 . University of Southampton. Natalia Kwasnikowska, Luc Moreau, and Jan Van den Bussche. 2010. A Formal Account of the Open Provenance Model. eprint 271819. University of Southampton."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89965-5_3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.10.013"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Workshop on Parallel and Distributed Algorithms. 215--226","author":"Mattern Friedemann","year":"1989","unstructured":"Friedemann Mattern . 1989 . Virtual time and global states of distributed systems . In Proceedings of the International Workshop on Parallel and Distributed Algorithms. 215--226 . Friedemann Mattern. 1989. Virtual time and global states of distributed systems. In Proceedings of the International Workshop on Parallel and Distributed Algorithms. 215--226."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the AAAI Spring Symposium: AI Meets Business Rules and Process Management. 87--92","author":"Robert","unstructured":"Robert E. McGrath and Joe Futrelle. 2008. Reasoning about provenance with OWL and SWRL rules . In Proceedings of the AAAI Spring Symposium: AI Meets Business Rules and Process Management. 87--92 . Robert E. McGrath and Joe Futrelle. 2008. Reasoning about provenance with OWL and SWRL rules. In Proceedings of the AAAI Spring Symposium: AI Meets Business Rules and Process Management. 87--92."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.10.007"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10723-006-9055-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/WORKS.2010.5671861"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.10.012"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2011.03.001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/1800000010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2010.07.005"},{"key":"e_1_2_1_27_1","volume-title":"Retrieved","author":"Moreau Luc","year":"2010","unstructured":"Luc Moreau , Li Ding , Joe Futrelle , Daniel Garijo Verdejo , Paul Groth , Mike Jewell , Simon Miles , Paolo Missier , Jeff Pan , and Jun Zhao . 2010 . Open Provenance Model (OPM) OWL Specification . Retrieved April 21, 2015, from http:\/\/openprovenance.org\/model\/opmo. Luc Moreau, Li Ding, Joe Futrelle, Daniel Garijo Verdejo, Paul Groth, Mike Jewell, Simon Miles, Paolo Missier, Jeff Pan, and Jun Zhao. 2010. Open Provenance Model (OPM) OWL Specification. Retrieved April 21, 2015, from http:\/\/openprovenance.org\/model\/opmo."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54804-8_20"},{"key":"e_1_2_1_29_1","unstructured":"Luc Moreau Paolo Missier Khalid Belhajjame Reza B\u2019Far James Cheney Sam Coppens Stephen Cresswell Yolanda Gil Paul Groth Graham Klyne Timothy Lebo Jim McCusker Simon Miles James Myers Satya Sahoo and Curt Tilmes (Eds.). 2013. PROV-DM: The PROV Data Model. W3C Recommendation REC-prov-dm-20130430. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/2013\/REC-prov-dm-20130430\/.  Luc Moreau Paolo Missier Khalid Belhajjame Reza B\u2019Far James Cheney Sam Coppens Stephen Cresswell Yolanda Gil Paul Groth Graham Klyne Timothy Lebo Jim McCusker Simon Miles James Myers Satya Sahoo and Curt Tilmes (Eds.). 2013. PROV-DM: The PROV Data Model. W3C Recommendation REC-prov-dm-20130430. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/2013\/REC-prov-dm-20130430\/."},{"key":"e_1_2_1_30_1","series-title":"Lecture Notes in Computer Science","volume-title":"Provenance and Annotation of Data and Processes","author":"Myers James","unstructured":"James Myers . 2010. I think therefore I am someone else: Understanding the confusion of granularity with continuant\/occurrent and related perspective shifts . In Provenance and Annotation of Data and Processes . Lecture Notes in Computer Science , Vol. 6378 . Springer , 292--294. James Myers. 2010. I think therefore I am someone else: Understanding the confusion of granularity with continuant\/occurrent and related perspective shifts. In Provenance and Annotation of Data and Processes. Lecture Notes in Computer Science, Vol. 6378. Springer, 292--294."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084805.1084812"},{"key":"e_1_2_1_33_1","volume-title":"What are logical notions&quest","author":"Tarski Alfred","unstructured":"Alfred Tarski . 1986. What are logical notions&quest ; History and Philosophy of Logic 7, 2, 143--154. Alfred Tarski. 1986. What are logical notions&quest; History and Philosophy of Logic 7, 2, 143--154."},{"key":"e_1_2_1_34_1","volume-title":"Introduction to Distributed Algorithms","author":"Tel Gerard","unstructured":"Gerard Tel . 1994. Introduction to Distributed Algorithms . Cambridge University Press . Gerard Tel. 1994. Introduction to Distributed Algorithms. Cambridge University Press."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2013.2262179"},{"key":"e_1_2_1_36_1","volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman Jeffrey D.","unstructured":"Jeffrey D. Ullman . 1989. Principles of Database and Knowledge-Base Systems . Vol. II . Computer Science Press . Jeffrey D. Ullman. 1989. Principles of Database and Knowledge-Base Systems. Vol. II. Computer Science Press."},{"key":"e_1_2_1_37_1","volume-title":"Retrieved","author":"C","year":"2011","unstructured":"W3 C PROV. 2011 . W3C Provenance Working Group Activity . Retrieved April 21, 2015, from http:\/\/www.w3.org\/2011\/prov\/. W3C PROV. 2011. W3C Provenance Working Group Activity. Retrieved April 21, 2015, from http:\/\/www.w3.org\/2011\/prov\/."},{"key":"e_1_2_1_38_1","volume-title":"Retrieved","author":"Activity C Provenance Incubator","year":"2010","unstructured":"W3 C Provenance Incubator Activity . 2010 . Provenance Incubator Group Charter . Retrieved April 21, 2015, from http:\/\/www.w3.org\/2005\/Incubator\/prov\/charter. W3C Provenance Incubator Activity. 2010. Provenance Incubator Group Charter. Retrieved April 21, 2015, from http:\/\/www.w3.org\/2005\/Incubator\/prov\/charter."},{"key":"e_1_2_1_39_1","volume-title":"Using Z. Specification, Refinement, and Proof","author":"Woodcock Jim","unstructured":"Jim Woodcock and Jim Davies . 1996. Using Z. Specification, Refinement, and Proof . Prentice Hall . Jim Woodcock and Jim Davies. 1996. Using Z. Specification, Refinement, and Proof. Prentice Hall."}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2734116","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2734116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:02Z","timestamp":1750227422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2734116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,13]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,26]]}},"alternative-id":["10.1145\/2734116"],"URL":"https:\/\/doi.org\/10.1145\/2734116","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,13]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}