--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/model/diff-c.html Tue Aug 07 12:32:13 2012 +0100
@@ -0,0 +1,3507 @@
+
+<!DOCTYPE html PUBLIC '-//W3C//DTD HTML 4.01 Transitional//EN' 'http://www.w3.org/TR/html4/loose.dtd'>
+<html lang="en" dir="ltr">
+<head><style type="text/css"><!--
+
+.insert { background-color: #aaffaa }
+.delete { background-color: #ff8888; text-decoration: line-through }
+.tagInsert { background-color: #007700; color: #ffffff }
+.tagDelete { background-color: #770000; color: #ffffff }
+
+--></style>
+ <title>Constraints of the Provenance Data Model</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
+
+
+ <style type="text/css">
+ .note { font-size:small; margin-left:50px }
+ </style>
+
+
+
+
+
+
+
+
+ <style type="text/css">
+/*****************************************************************
+ * ReSpec CSS
+ * Robin Berjon (robin at berjon dot com)
+ * v0.05 - 2009-07-31
+ *****************************************************************/
+
+
+/* --- INLINES --- */
+em.rfc2119 {
+ text-transform: lowercase;
+ font-variant: small-caps;
+ font-style: normal;
+ color: #900;
+}
+
+h1 acronym, h2 acronym, h3 acronym, h4 acronym, h5 acronym, h6 acronym, a acronym,
+h1 abbr, h2 abbr, h3 abbr, h4 abbr, h5 abbr, h6 abbr, a abbr {
+ border: none;
+}
+
+dfn {
+ font-weight: bold;
+}
+
+a.internalDFN {
+ color: inherit;
+ border-bottom: 1px solid #99c;
+ text-decoration: none;
+}
+
+a.externalDFN {
+ color: inherit;
+ border-bottom: 1px dotted #ccc;
+ text-decoration: none;
+}
+
+a.bibref {
+ text-decoration: none;
+}
+
+code {
+ color: #ff4500;
+}
+
+
+/* --- WEB IDL --- */
+pre.idl {
+ border-top: 1px solid #90b8de;
+ border-bottom: 1px solid #90b8de;
+ padding: 1em;
+ line-height: 120%;
+}
+
+pre.idl::before {
+ content: "WebIDL";
+ display: block;
+ width: 150px;
+ background: #90b8de;
+ color: #fff;
+ font-family: initial;
+ padding: 3px;
+ font-weight: bold;
+ margin: -1em 0 1em -1em;
+}
+
+.idlType {
+ color: #ff4500;
+ font-weight: bold;
+ text-decoration: none;
+}
+
+/*.idlModule*/
+/*.idlModuleID*/
+/*.idlInterface*/
+.idlInterfaceID, .idlDictionaryID {
+ font-weight: bold;
+ color: #005a9c;
+}
+
+.idlSuperclass {
+ font-style: italic;
+ color: #005a9c;
+}
+
+/*.idlAttribute*/
+.idlAttrType, .idlFieldType, .idlMemberType {
+ color: #005a9c;
+}
+.idlAttrName, .idlFieldName, .idlMemberName {
+ color: #ff4500;
+}
+.idlAttrName a, .idlFieldName a, .idlMemberName a {
+ color: #ff4500;
+ border-bottom: 1px dotted #ff4500;
+ text-decoration: none;
+}
+
+/*.idlMethod*/
+.idlMethType {
+ color: #005a9c;
+}
+.idlMethName {
+ color: #ff4500;
+}
+.idlMethName a {
+ color: #ff4500;
+ border-bottom: 1px dotted #ff4500;
+ text-decoration: none;
+}
+
+/*.idlParam*/
+.idlParamType {
+ color: #005a9c;
+}
+.idlParamName {
+ font-style: italic;
+}
+
+.extAttr {
+ color: #666;
+}
+
+/*.idlConst*/
+.idlConstType {
+ color: #005a9c;
+}
+.idlConstName {
+ color: #ff4500;
+}
+.idlConstName a {
+ color: #ff4500;
+ border-bottom: 1px dotted #ff4500;
+ text-decoration: none;
+}
+
+/*.idlException*/
+.idlExceptionID {
+ font-weight: bold;
+ color: #c00;
+}
+
+.idlTypedefID, .idlTypedefType {
+ color: #005a9c;
+}
+
+.idlRaises, .idlRaises a.idlType, .idlRaises a.idlType code, .excName a, .excName a code {
+ color: #c00;
+ font-weight: normal;
+}
+
+.excName a {
+ font-family: monospace;
+}
+
+.idlRaises a.idlType, .excName a.idlType {
+ border-bottom: 1px dotted #c00;
+}
+
+.excGetSetTrue, .excGetSetFalse, .prmNullTrue, .prmNullFalse, .prmOptTrue, .prmOptFalse {
+ width: 45px;
+ text-align: center;
+}
+.excGetSetTrue, .prmNullTrue, .prmOptTrue { color: #0c0; }
+.excGetSetFalse, .prmNullFalse, .prmOptFalse { color: #c00; }
+
+.idlImplements a {
+ font-weight: bold;
+}
+
+dl.attributes, dl.methods, dl.constants, dl.fields, dl.dictionary-members {
+ margin-left: 2em;
+}
+
+.attributes dt, .methods dt, .constants dt, .fields dt, .dictionary-members dt {
+ font-weight: normal;
+}
+
+.attributes dt code, .methods dt code, .constants dt code, .fields dt code, .dictionary-members dt code {
+ font-weight: bold;
+ color: #000;
+ font-family: monospace;
+}
+
+.attributes dt code, .fields dt code, .dictionary-members dt code {
+ background: #ffffd2;
+}
+
+.attributes dt .idlAttrType code, .fields dt .idlFieldType code, .dictionary-members dt .idlMemberType code {
+ color: #005a9c;
+ background: transparent;
+ font-family: inherit;
+ font-weight: normal;
+ font-style: italic;
+}
+
+.methods dt code {
+ background: #d9e6f8;
+}
+
+.constants dt code {
+ background: #ddffd2;
+}
+
+.attributes dd, .methods dd, .constants dd, .fields dd, .dictionary-members dd {
+ margin-bottom: 1em;
+}
+
+table.parameters, table.exceptions {
+ border-spacing: 0;
+ border-collapse: collapse;
+ margin: 0.5em 0;
+ width: 100%;
+}
+table.parameters { border-bottom: 1px solid #90b8de; }
+table.exceptions { border-bottom: 1px solid #deb890; }
+
+.parameters th, .exceptions th {
+ color: #fff;
+ padding: 3px 5px;
+ text-align: left;
+ font-family: initial;
+ font-weight: normal;
+ text-shadow: #666 1px 1px 0;
+}
+.parameters th { background: #90b8de; }
+.exceptions th { background: #deb890; }
+
+.parameters td, .exceptions td {
+ padding: 3px 10px;
+ border-top: 1px solid #ddd;
+ vertical-align: top;
+}
+
+.parameters tr:first-child td, .exceptions tr:first-child td {
+ border-top: none;
+}
+
+.parameters td.prmName, .exceptions td.excName, .exceptions td.excCodeName {
+ width: 100px;
+}
+
+.parameters td.prmType {
+ width: 120px;
+}
+
+table.exceptions table {
+ border-spacing: 0;
+ border-collapse: collapse;
+ width: 100%;
+}
+
+/* --- TOC --- */
+.toc a {
+ text-decoration: none;
+}
+
+a .secno {
+ color: #000;
+}
+
+/* --- TABLE --- */
+table.simple {
+ border-spacing: 0;
+ border-collapse: collapse;
+ border-bottom: 3px solid #005a9c;
+}
+
+.simple th {
+ background: #005a9c;
+ color: #fff;
+ padding: 3px 5px;
+ text-align: left;
+}
+
+.simple th[scope="row"] {
+ background: inherit;
+ color: inherit;
+ border-top: 1px solid #ddd;
+}
+
+.simple td {
+ padding: 3px 10px;
+ border-top: 1px solid #ddd;
+}
+
+.simple tr:nth-child(even) {
+ background: #f0f6ff;
+}
+
+/* --- DL --- */
+.section dd > p:first-child {
+ margin-top: 0;
+}
+
+.section dd > p:last-child {
+ margin-bottom: 0;
+}
+
+.section dd {
+ margin-bottom: 1em;
+}
+
+.section dl.attrs dd, .section dl.eldef dd {
+ margin-bottom: 0;
+}
+
+/* --- EXAMPLES --- */
+pre.example {
+ border-top: 1px solid #ff4500;
+ border-bottom: 1px solid #ff4500;
+ padding: 1em;
+ margin-top: 1em;
+}
+
+pre.example::before {
+ content: "Example";
+ display: block;
+ width: 150px;
+ background: #ff4500;
+ color: #fff;
+ font-family: initial;
+ padding: 3px;
+ font-weight: bold;
+ margin: -1em 0 1em -1em;
+}
+
+/* --- EDITORIAL NOTES --- */
+.issue {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #ffc;
+}
+
+.issue::before {
+ content: "Issue";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #f00;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+.note {
+ margin: 1em 0em 0em;
+ padding: 1em;
+ border: 2px solid #cff6d9;
+ background: #e2fff0;
+}
+
+.note::before {
+ content: "Note";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #cff6d9;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+/* --- Best Practices --- */
+div.practice {
+ border: solid #bebebe 1px;
+ margin: 2em 1em 1em 2em;
+}
+
+span.practicelab {
+ margin: 1.5em 0.5em 1em 1em;
+ font-weight: bold;
+ font-style: italic;
+}
+
+span.practicelab { background: #dfffff; }
+
+span.practicelab {
+ position: relative;
+ padding: 0 0.5em;
+ top: -1.5em;
+}
+
+p.practicedesc {
+ margin: 1.5em 0.5em 1em 1em;
+}
+
+@media screen {
+ p.practicedesc {
+ position: relative;
+ top: -2em;
+ padding: 0;
+ margin: 1.5em 0.5em -1em 1em;
+ }
+}
+
+/* --- SYNTAX HIGHLIGHTING --- */
+pre.sh_sourceCode {
+ background-color: white;
+ color: black;
+ font-style: normal;
+ font-weight: normal;
+}
+
+pre.sh_sourceCode .sh_keyword { color: #005a9c; font-weight: bold; } /* language keywords */
+pre.sh_sourceCode .sh_type { color: #666; } /* basic types */
+pre.sh_sourceCode .sh_usertype { color: teal; } /* user defined types */
+pre.sh_sourceCode .sh_string { color: red; font-family: monospace; } /* strings and chars */
+pre.sh_sourceCode .sh_regexp { color: orange; font-family: monospace; } /* regular expressions */
+pre.sh_sourceCode .sh_specialchar { color: #ffc0cb; font-family: monospace; } /* e.g., \n, \t, \\ */
+pre.sh_sourceCode .sh_comment { color: #A52A2A; font-style: italic; } /* comments */
+pre.sh_sourceCode .sh_number { color: purple; } /* literal numbers */
+pre.sh_sourceCode .sh_preproc { color: #00008B; font-weight: bold; } /* e.g., #include, import */
+pre.sh_sourceCode .sh_symbol { color: blue; } /* e.g., *, + */
+pre.sh_sourceCode .sh_function { color: black; font-weight: bold; } /* function calls and declarations */
+pre.sh_sourceCode .sh_cbracket { color: red; } /* block brackets (e.g., {, }) */
+pre.sh_sourceCode .sh_todo { font-weight: bold; background-color: #00FFFF; } /* TODO and FIXME */
+
+/* Predefined variables and functions (for instance glsl) */
+pre.sh_sourceCode .sh_predef_var { color: #00008B; }
+pre.sh_sourceCode .sh_predef_func { color: #00008B; font-weight: bold; }
+
+/* for OOP */
+pre.sh_sourceCode .sh_classname { color: teal; }
+
+/* line numbers (not yet implemented) */
+pre.sh_sourceCode .sh_linenum { display: none; }
+
+/* Internet related */
+pre.sh_sourceCode .sh_url { color: blue; text-decoration: underline; font-family: monospace; }
+
+/* for ChangeLog and Log files */
+pre.sh_sourceCode .sh_date { color: blue; font-weight: bold; }
+pre.sh_sourceCode .sh_time, pre.sh_sourceCode .sh_file { color: #00008B; font-weight: bold; }
+pre.sh_sourceCode .sh_ip, pre.sh_sourceCode .sh_name { color: #006400; }
+
+/* for Prolog, Perl... */
+pre.sh_sourceCode .sh_variable { color: #006400; }
+
+/* for LaTeX */
+pre.sh_sourceCode .sh_italics { color: #006400; font-style: italic; }
+pre.sh_sourceCode .sh_bold { color: #006400; font-weight: bold; }
+pre.sh_sourceCode .sh_underline { color: #006400; text-decoration: underline; }
+pre.sh_sourceCode .sh_fixed { color: green; font-family: monospace; }
+pre.sh_sourceCode .sh_argument { color: #006400; }
+pre.sh_sourceCode .sh_optionalargument { color: purple; }
+pre.sh_sourceCode .sh_math { color: orange; }
+pre.sh_sourceCode .sh_bibtex { color: blue; }
+
+/* for diffs */
+pre.sh_sourceCode .sh_oldfile { color: orange; }
+pre.sh_sourceCode .sh_newfile { color: #006400; }
+pre.sh_sourceCode .sh_difflines { color: blue; }
+
+/* for css */
+pre.sh_sourceCode .sh_selector { color: purple; }
+pre.sh_sourceCode .sh_property { color: blue; }
+pre.sh_sourceCode .sh_value { color: #006400; font-style: italic; }
+
+/* other */
+pre.sh_sourceCode .sh_section { color: black; font-weight: bold; }
+pre.sh_sourceCode .sh_paren { color: red; }
+pre.sh_sourceCode .sh_attribute { color: #006400; }
+
+</style><link href="./extra.css" rel="stylesheet" type="text/css" charset="utf-8"><link href="http://www.w3.org/StyleSheets/TR/W3C-ED" rel="stylesheet" type="text/css" charset="utf-8"></head>
+ <body style="display: inherit; "><div class="head"><p><a href="http://www.w3.org/"><img width="72" height="48" src="http://www.w3.org/Icons/w3c_home" alt="W3C"></a></p><h1 class="title" id="title">Constraints of the Provenance Data Model</h1><h2 id="subtitle"><span class="delete">Version for</span><a href="diff-c.html"><span class="insert">Changes</span></a><span class="insert"> since</span> internal <span class="delete">review</span><span class="insert">release (pre-LC)</span></h2><h2 id="w3c-editor-s-draft-07-august-2012"><acronym title="World Wide Web Consortium">W3C</acronym> Editor's Draft <span class="delete">23 July</span><span class="insert">07 August</span> 2012</h2><dl><dt>This version:</dt><dd><a href="http://dvcs.w3.org/hg/prov/raw-file/default/model/prov-constraints.html">http://dvcs.w3.org/hg/prov/raw-file/default/model/prov-constraints.html</a></dd><dt>Latest published version:</dt><dd><a href="http://www.w3.org/TR/prov-constraints/">http://www.w3.org/TR/prov-constraints/</a></dd><dt>Latest editor's draft:</dt><dd><a href="http://dvcs.w3.org/hg/prov/raw-file/default/model/prov-constraints.html">http://dvcs.w3.org/hg/prov/raw-file/default/model/prov-constraints.html</a></dd><dt>Previous version:</dt><dd><a href="http://www.w3.org/TR/2012/WD-prov-constraints-20120503/">http://www.w3.org/TR/2012/WD-prov-constraints-20120503/</a></dd><dt>Editors:</dt><dd><a href="http://homepages.inf.ed.ac.uk/jcheney">James Cheney</a>, University of Edinburgh</dd>
+<dd><a href="http://www.cs.ncl.ac.uk/people/Paolo.Missier">Paolo Missier</a>, Newcastle University</dd>
+<dd><a href="http://www.ecs.soton.ac.uk/~lavm/">Luc Moreau</a>, University of Southampton</dd>
+<dt>Author:</dt><dd><a href="http://users.ugent.be/~tdenies/">Tom De Nies</a>, IBBT - Ghent University</dd>
+</dl><p class="copyright"><a href="http://www.w3.org/Consortium/Legal/ipr-notice#Copyright">Copyright</a> © 2012-2012 <a href="http://www.w3.org/"><acronym title="World Wide Web Consortium">W3C</acronym></a><sup>®</sup> (<a href="http://www.csail.mit.edu/"><acronym title="Massachusetts Institute of Technology">MIT</acronym></a>, <a href="http://www.ercim.eu/"><acronym title="European Research Consortium for Informatics and Mathematics">ERCIM</acronym></a>, <a href="http://www.keio.ac.jp/">Keio</a>), All Rights Reserved. <acronym title="World Wide Web Consortium">W3C</acronym> <a href="http://www.w3.org/Consortium/Legal/ipr-notice#Legal_Disclaimer">liability</a>, <a href="http://www.w3.org/Consortium/Legal/ipr-notice#W3C_Trademarks">trademark</a> and <a href="http://www.w3.org/Consortium/Legal/copyright-documents">document use</a> rules apply.</p><hr></div>
+
+ <div id="abstract" class="introductory section"><h2>Abstract</h2>
+<p>
+Provenance is information about entities, activities, and people
+involved in producing a piece of data or thing, which can be used to
+form assessments about its quality, reliability or
+trustworthiness. PROV-DM is the conceptual data model that forms a
+basis for the <acronym title="World Wide Web Consortium">W3C</acronym> provenance (PROV) family of specifications.<span class="delete"> PROV-DM distinguishes core structures, forming the essence of provenance information, from extended structures catering for more specific uses of provenance. PROV-DM is organized in six components, respectively dealing with: (1) entities and activities, and the time at which they were created, used, or ended; (2) derivations of entities from entities; (3) agents bearing responsibility for entities that were generated and activities that happened; (4) a notion of bundle, a mechanism to support provenance of provenance; (5) properties to link entities that refer to the same thing; and, (6) collections forming a logical structure for its members.
+</span>
+
+</p>
+
+
+<p> This document introduces <a><span class="insert">definitions</span></a><span class="insert"> and </span><a>inferences<span class="delete"> and </span><span class="delete">definitions</span></a>
+ that are allowed on provenance statements and <a>constraints</a>
+ that PROV instances <em class="rfc2119" title="must">must</em> satisfy in order to be considered
+ <a href="#dfn-valid" class="internalDFN">valid</a>. These <span class="delete">inferences</span><span class="insert">definitions, inferences,</span> and constraints are useful for
+ readers who develop applications that generate provenance or reason
+ over provenance. They can also be used to <a title="normal form" href="#dfn-normal-form" class="internalDFN">normalize</a> PROV
+ instances to forms that can easily be compared in order to determine
+ whether two PROV instances are <a href="#dfn-equivalent" class="internalDFN">equivalent</a>.</p>
+
+</div><div id="sotd" class="introductory section"><h2>Status of This Document</h2><p><em>This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current <acronym title="World Wide Web Consortium">W3C</acronym> publications and the latest revision of this technical report can be found in the <a href="http://www.w3.org/TR/"><acronym title="World Wide Web Consortium">W3C</acronym> technical reports index</a> at http://www.w3.org/TR/.</em></p>
+<h4 id="last-call">Last Call</h4>
+<p>This is the second public release of the PROV-CONSTRAINTS document.
+This is a Last Call Working Draft. The design is not expected to change significantly, going forward, and now is the key time for external review.</p>
+
+<p>This specification identifies <a href="http://www.w3.org/2005/10/Process-20051014/tr#cfi">features at
+risk</a> related to the at-risk Mention feature of [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-DM">PROV-DM</a></cite>]:
+<a class="rule-text" href="#mention-specialization-inference_text"><span>Inference 24 <span class="delete">(mention-specialization)</span><span class="delete"> and
+</span><span class="insert">(mention-specialization-inference)</span></span></a><span class="insert"> and
+</span><a class="rule-text" href="#unique-mention_text"><span>Constraint 33 <span class="delete">(mention-unique)</span><span class="insert">(unique-mention)</span></span></a>.
+These might be removed from PROV-CONSTRAINTS.</p>
+
+<h4 id="prov-family-of-specifications">PROV Family of Specifications</h4>
+This document is part of the PROV family of specifications, a set of specifications defining various aspects that are necessary to achieve the vision of inter-operable
+interchange of provenance information in heterogeneous environments such as the Web. The specifications are:
+<ul>
+<li> <a href="http://www.w3.org/TR/prov-dm/">PROV-DM</a>, the PROV data model for provenance;</li>
+<li> <a href="http://www.w3.org/TR/prov-constraints/">PROV-CONSTRAINTS</a>, a set of constraints applying to the PROV data model (this document);</li>
+<li> <a href="http://www.w3.org/TR/prov-n/">PROV-N</a>, a notation for provenance aimed at human consumption;</li>
+<li> <a href="http://www.w3.org/TR/prov-o/">PROV-O</a>, the PROV ontology, an OWL2 ontology allowing the mapping of PROV to RDF;</li>
+<li> <a href="http://www.w3.org/TR/prov-aq/">PROV-AQ</a>, the mechanisms for accessing and querying provenance; </li>
+<li> <a href="http://www.w3.org/TR/prov-primer/">PROV-PRIMER</a>, a primer for the PROV data model.</li>
+</ul>
+<h4 id="how-to-read-the-prov-family-of-specifications">How to read the PROV Family of Specifications</h4>
+<ul>
+<li>The primer is the entry point to PROV offering an introduction to the provenance model.</li>
+<li>The Linked Data and Semantic Web community should focus on PROV-O
+defining PROV classes and properties specified in an OWL2
+ontology. For further details, PROV-DM and PROV-CONSTRAINTS specify
+the constraints applicable to the data model, and its interpretation.<span class="delete"> PROV-SEM provides a mathematical semantics.</span>
+
+</li>
+<li>Developers seeking to retrieve or publish provenance should focus on PROV-AQ.</li>
+<li>Readers seeking to implement other PROV serializations
+should focus on PROV-DM and PROV-CONSTRAINTS. PROV-O and PROV-N offer examples of mapping to RDF and text, respectively.</li>
+</ul>
+
+<p>This document was published by the <a href="http://www.w3.org/2011/prov/">Provenance Working Group</a> as an Editor's Draft. If you wish to make comments regarding this document, please send them to <a href="mailto:public-prov-comments@w3.org">public-prov-comments@w3.org</a> (<a href="mailto:public-prov-comments-request@w3.org?subject=subscribe">subscribe</a>, <a href="http://lists.w3.org/Archives/Public/public-prov-comments/">archives</a>). All feedback is welcome.</p><p>Publication as an Editor's Draft does not imply endorsement by the <acronym title="World Wide Web Consortium">W3C</acronym> Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.</p><p>This document was produced by a group operating under the <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/">5 February 2004 <acronym title="World Wide Web Consortium">W3C</acronym> Patent Policy</a>. <acronym title="World Wide Web Consortium">W3C</acronym> maintains a <a href="http://www.w3.org/2004/01/pp-impl/46974/status" rel="disclosure">public list of any patent disclosures</a> made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/#def-essential">Essential Claim(s)</a> must disclose the information in accordance with <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/#sec-Disclosure">section 6 of the <acronym title="World Wide Web Consortium">W3C</acronym> Patent Policy</a>.</p></div><div id="toc" class="section"><h2 class="introductory">Table of Contents</h2><ul class="toc"><li class="tocline"><a href="#introduction" class="tocxref"><span class="secno">1. </span>Introduction<br>
+</a><ul class="toc"><li class="tocline"><a href="#conventions" class="tocxref"><span class="secno">1.1 </span>Conventions</a></li><li class="tocline"><a href="#purpose" class="tocxref"><span class="secno">1.2 </span>Purpose of this document</a></li><li class="tocline"><a href="#structure-of-this-document" class="tocxref"><span class="secno">1.3 </span>Structure of this document</a></li><li class="tocline"><a href="#audience" class="tocxref"><span class="secno">1.4 </span> Audience </a></li></ul></li><li class="tocline"><a href="#rationale" class="tocxref"><span class="secno">2. </span>Rationale</a><ul class="toc"><li class="tocline"><a href="#entities--activities-and-agents" class="tocxref"><span class="secno">2.1 </span>Entities, Activities and Agents</a></li><li class="tocline"><a href="#events" class="tocxref"><span class="secno">2.2 </span>Events</a></li><li class="tocline"><a href="#summary-of-constraints-and-inferences" class="tocxref"><span class="secno">2.3 </span>Summary of constraints and inferences</a></li></ul></li><li class="tocline"><a href="#compliance" class="tocxref"><span class="secno">3. </span>Compliance with this document</a></li><li class="tocline"><a href="#inferences" class="tocxref"><span class="secno">4. </span>Inferences and Definitions</a><ul class="toc"><li class="tocline"><a href="#optional-identifiers-and-attributes" class="tocxref"><span class="secno">4.1 </span>Optional Identifiers and Attributes</a></li><li class="tocline"><a href="#entities-and-activities" class="tocxref"><span class="secno">4.2 </span>Entities and Activities</a></li><li class="tocline"><a href="#derivations" class="tocxref"><span class="secno">4.3 </span>Derivations</a></li><li class="tocline"><a href="#agents" class="tocxref"><span class="secno">4.4 </span>Agents</a></li><li class="tocline"><a href="#alternate-and-specialized-entities" class="tocxref"><span class="secno">4.5 </span>Alternate and Specialized Entities</a></li></ul></li><li class="tocline"><a href="#constraints" class="tocxref"><span class="secno">5. </span>Constraints</a><ul class="toc"><li class="tocline"><a href="#uniqueness-constraints" class="tocxref"><span class="secno">5.1 </span>Uniqueness Constraints</a></li><li class="tocline"><a href="#event-ordering-constraints" class="tocxref"><span class="secno">5.2 </span>Event Ordering Constraints</a><ul class="toc"><li class="tocline"><a href="#activity-constraints" class="tocxref"><span class="secno">5.2.1 </span>Activity constraints</a></li><li class="tocline"><a href="#entity-constraints" class="tocxref"><span class="secno">5.2.2 </span> Entity constraints</a></li><li class="tocline"><a href="#agent-constraints" class="tocxref"><span class="secno">5.2.3 </span> Agent constraints</a></li></ul></li><li class="tocline"><a href="#impossibility-constraints" class="tocxref"><span class="secno">5.3 </span>Impossibility constraints</a></li><li class="tocline"><a href="#type-constraints" class="tocxref"><span class="secno">5.4 </span>Type Constraints</a></li></ul></li><li class="tocline"><a href="#normalization-validity-equivalence" class="tocxref"><span class="secno">6. </span>Normalization, Validity, and Equivalence</a><ul class="toc"><li class="tocline"><a href="#bundle-constraints" class="tocxref"><span class="secno">6.1 </span>Bundles</a></li></ul></li><li class="tocline"><a href="#acknowledgements" class="tocxref"><span class="secno">A. </span>Acknowledgements</a></li><li class="tocline"><a href="#glossary" class="tocxref"><span class="secno">B. </span>Glossary</a></li><li class="tocline"><a href="#termination" class="tocxref"><span class="secno">C. </span>Termination of normalization</a></li><li class="tocline"><a href="#references" class="tocxref"><span class="secno">D. </span>References</a><ul class="toc"><li class="tocline"><a href="#normative-references" class="tocxref"><span class="secno">D.1 </span>Normative references</a></li><li class="tocline"><a href="#informative-references" class="tocxref"><span class="secno">D.2 </span>Informative references</a></li></ul></li></ul></div>
+
+
+
+
+
+
+ <div id="introduction" class="section">
+ <h2><span class="secno">1. </span>Introduction<br>
+</h2>
+
+<p>
+Provenance is a record that describes the people, institutions,
+ entities, and <span class="delete">activities,</span><span class="insert">activities</span> involved in producing, influencing, or
+ delivering a piece of data or a thing.
+This document complements
+ the PROV-DM specification [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-DM">PROV-DM</a></cite>] that defines a data model for
+ provenance on the Web. </p>
+
+
+
+ <div id="conventions" class="section">
+<h3><span class="secno">1.1 </span>Conventions</h3>
+
+
+
+<p>The key words "<em class="rfc2119" title="must">must</em>", "<em class="rfc2119" title="must not">must not</em>", "<em class="rfc2119" title="required">required</em>", "<em class="rfc2119" title="shall">shall</em>", "<em class="rfc2119" title="shall
+ not">shall
+ not</em>", "<em class="rfc2119" title="should">should</em>", "<em class="rfc2119" title="should not">should not</em>", "<em class="rfc2119" title="recommended">recommended</em>", "<em class="rfc2119" title="may">may</em>", and
+ "<em class="rfc2119" title="optional">optional</em>" in this document are to be interpreted as described in
+ [<cite><a class="bibref" rel="biblioentry" href="#bib-RFC2119">RFC2119</a></cite>].</p>
+
+<p>In this document, logical formulas contain variables written as
+ lower-case identifiers. Some of these <span class="delete">ariables</span><span class="insert">variables</span> are written
+ beginning with the underscore character <span class="name">_</span>, by convention, to indicate that they
+ (intentionally) appear only once in the formula; thus, the textual
+ variable name is mnemonic only. </p>
+
+</div>
+
+
+<div id="purpose" class="section">
+
+<h3><span class="secno">1.2 </span>Purpose of this document</h3>
+
+<p>The PROV Data Model, PROV-DM, is a conceptual data model for provenance, which is
+realizable using different serializations such as PROV-N and PROV-O.
+A PROV <dfn id="dfn-instance">instance</dfn> is a set of PROV statements,
+possibly including <a>bundles</a>, or named sets of statements. For
+example, such a PROV instance could be a .provn document, the result
+of a query, a triple store containing PROV statements in RDF, etc. The
+PROV-DM specification [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-DM">PROV-DM</a></cite>] imposes minimal requirements upon
+PROV instances. A <a href="#dfn-valid" class="internalDFN">valid</a> PROV instance corresponds to a
+consistent history of objects and interactions to which logical
+reasoning can be safely applied. By default, PROV instances need not
+be <span class="delete">valid.</span><a href="#dfn-valid" class="internalDFN"><span class="insert">valid</span></a><span class="insert">.</span> </p>
+
+<p> This document specifies <em>inferences</em> over PROV instances
+that applications <em class="rfc2119" title="may">may</em> employ, including <em>definitions</em> of some
+provenance statements in terms of others, and also defines a class of
+<a href="#dfn-valid" class="internalDFN">valid</a> PROV instances by specifying <em>constraints</em> that
+<a href="#dfn-valid" class="internalDFN">valid</a> PROV instances must satisfy. <span class="insert">There are four kinds of
+constraints: </span><em><span class="insert">uniqueness constraints</span></em><span class="insert">, </span><em><span class="insert">event ordering
+constraints</span></em><span class="insert">, </span><em><span class="insert">impossibility constraints</span></em><span class="insert">, and </span><em><span class="insert">type constraints</span></em><span class="insert">.
+</span>Applications <em class="rfc2119" title="should">should</em> produce valid
+provenance and <em class="rfc2119" title="may">may</em> reject provenance that is not <span class="delete">valid.</span><a href="#dfn-valid" class="internalDFN"><span class="insert">valid</span></a><span class="insert">.</span> Applications
+<em class="rfc2119" title="should">should</em> also use definitions, inferences and constraints to normalize
+PROV instances in order to determine whether two such instances convey
+the same information.
+
+
+</p><p>To summarize: compliant applications use definitions,
+inferences, and uniqueness constraints to normalize PROV instances,
+and then <span class="delete">apply</span><span class="insert">check</span> event <span class="delete">ordering constraints to determine whether the
+instance has a consistent event ordering.</span><span class="insert">ordering, impossibility, and type constraints.</span> If <span class="delete">so,</span><span class="insert">these
+checks succeed,</span> the instance is
+<a href="#dfn-valid" class="internalDFN">valid</a>, and the normal form is considered <a href="#dfn-equivalent" class="internalDFN">equivalent</a> to
+the original instance. Also, any two PROV instances that yield the
+same normal form are considered <a href="#dfn-equivalent" class="internalDFN">equivalent</a>. Further discussion
+of the semantics of PROV statements, which justifies the inferences
+and constraints, can be found in the formal semantics [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-SEM">PROV-SEM</a></cite>].
+</p>
+</div>
+<div id="structure-of-this-document" class="section">
+<h3><span class="secno">1.3 </span>Structure of this document</h3>
+
+<p><a href="#rationale">Section 2</a> gives a brief rationale
+for the definitions, inferences and constraints.
+</p>
+<p>
+<a href="#compliance">Section 3</a> summarizes the
+requirements for compliance with this document, which are specified in
+detail in the rest of the document. </p>
+
+<p> <a href="#inferences">Section 4</a> presents <span class="delete">inferences and
+definitions.</span><span class="insert">definitions and inferences.</span> Definitions allow replacing shorthand notation in [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-N">PROV-N</a></cite>]
+with more explicit and complete statements; inferences allow adding
+new facts representing implicit knowledge about the structure of
+provenance. </p>
+
+<p><a href="#constraints">Section 5</a> presents <span class="delete">three</span><span class="insert">four</span> kinds of constraints,
+<em>uniqueness</em> constraints that prescribe that certain <span class="delete">statments</span><span class="insert">statements</span>
+must be unique within PROV <a>instances</a>,
+<em>event ordering</em> constraints that require that the records in a
+PROV <a href="#dfn-instance" class="internalDFN">instance</a> are consistent with a sensible ordering of events
+relating the activities, entities and agents involved,<span class="delete"> and
+</span>
+<em>impossibility</em> constraints that forbid certain patterns of
+statements<span class="insert"> in valid PROV instances, and </span><em><span class="insert">type</span></em><span class="insert"> constraints that
+classify the types of identifiers</span> in valid PROV instances.
+</p>
+
+<p><a href="#normalization-validity-equivalence">Section 6</a> defines the notions
+of <a>validity</a>, <a>equivalence</a> and <a>normalization</a>.
+</p>
+
+
+
+</div>
+<div id="audience" class="section">
+<h3><span class="secno">1.4 </span> Audience </h3>
+
+<p> The audience for this document is the same as for [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-DM">PROV-DM</a></cite>]: developers
+and users who wish to create, process, share or integrate provenance
+records on the (Semantic) Web. Not all PROV-compliant applications
+need to perform inferences or check validity when processing provenance.
+However, applications that create or transform provenance <em class="rfc2119" title="should">should</em>
+attempt to produce valid provenance, to make it more useful to other
+applications by ruling out nonsensical or inconsistent information.
+</p>
+
+<p>This document assumes familiarity with [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-DM">PROV-DM</a></cite>] and employs the
+[<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-N">PROV-N</a></cite>] notation.
+</p>
+
+</div>
+</div>
+
+<div id="rationale" class="informative section">
+<h2><span class="secno">2. </span>Rationale</h2><p><em>This section is non-normative.</em></p>
+<p> In this section we give a high-level rationale that provides some
+ further background for the constraints. </p>
+
+<div id="entities--activities-and-agents" class="section">
+<h3><span class="secno">2.1 </span>Entities, Activities and Agents</h3>
+<p>
+One of the central challenges in representing provenance information
+is how to deal with change. Real-world objects, information objects
+and Web resources change over time, and the characteristics that make
+them identifiable in a given situation are sometimes subject to change
+as well. <span class="delete">To avoid over-reliance on assumptions that identifying
+characteristics do not change, </span>PROV allows for things to be described
+in different ways, with different descriptions of their<span class="delete"> partial
+</span>
+state.
+</p>
+
+<p>
+An entity is a thing one wants to provide provenance for
+and whose situation in the world is described by some fixed
+attributes. An entity has a <dfn id="lifetime">lifetime</dfn>,
+defined as the period
+between its <a title="entity generation event" href="#dfn-generation-event" class="internalDFN">generation event</a>
+and its <a title="entity invalidation event" href="#dfn-invalidation-event" class="internalDFN">invalidation event</a>.
+An entity's attributes are established when the entity is
+created and describe the entity's situation and (partial) state
+during <span class="delete">an</span><span class="insert">the</span> entity's lifetime.</p>
+
+<p>
+A different entity (perhaps representing a different user or
+system perspective) may fix other aspects of the same thing, and its provenance
+may be different. Different entities that <span class="delete">are</span><span class="insert">fix</span> aspects of the same
+thing are called <em>alternate</em>, and the PROV relations of
+specialization and alternate can be used to link such entities.</p>
+
+<p>Besides entities, a variety of other PROV objects have
+attributes, including activity, generation, usage, invalidation, start, end,
+communication, attribution, association, delegation, and
+derivation. Each object has an associated duration interval (which may
+be a single time point), and attribute-value pairs for a given object
+are expected to be descriptions that hold for the object's duration.
+</p>
+<p>
+However, the attributes of entities have special meaning because they
+are considered to be fixed aspects
+of underlying, changing things. This motivates constraints on
+<span class="name">alternateOf</span> and <span class="name">specializationOf</span> relating the attribute values of
+different entities.
+</p>
+
+<p>
+In order to describe the provenance of something during an interval
+ over which relevant attributes of the thing are not fixed, a PROV
+ instance would describe multiple entities, each with its own
+ identifier, <a href="#lifetime" class="internalDFN">lifetime</a>, and fixed attributes, and express dependencies between
+ the various entities using events. For example, if we want to
+ describe the provenance of several versions of a document, involving
+ attributes such as authorship that change over time, we need
+ different entities for the versions linked by appropriate
+ generation, usage, revision, and invalidation events.
+</p>
+
+<p>There is no assumption that the set of attributes listed in an
+<span class="name">entity</span> statement is complete, nor
+that the attributes are independent or orthogonal of each
+other. Similarly, there is no assumption that the attributes of an
+entity uniquely identify it. Two different entities that present the
+same aspects of possibly different things can have the same
+attributes; this leads to potential ambiguity, which is mitigated through the
+use of identifiers.</p>
+
+<p>An <a>activity</a> is delimited by its <a title="activity start event" href="#dfn-start-event" class="internalDFN">start</a> and its <a title="activity end event" href="#dfn-end-event" class="internalDFN">end</a> events; hence, it occurs over
+an interval delimited by two <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous
+events</a>. However, an activity statement need not mention start or end time information, because they may not be known.
+An activity's attribute-value pairs are expected to describe the activity's situation during its interval, i.e. an interval between two instantaneous events, namely its <a title="activity start event" href="#dfn-start-event" class="internalDFN">start</a> event and its <a title="activity end event" href="#dfn-end-event" class="internalDFN">end</a> event.
+</p>
+
+
+
+<p>An activity is not an entity. Indeed, an entity exists in full at
+any point in its lifetime, persists during this interval, and
+preserves the characteristics <span class="delete">that make it identifiable.</span><span class="insert">provided.</span> In
+contrast, an activity is something that occurs, happens, unfolds, or
+develops through time, but is typically not identifiable by the
+characteristics it exhibits at any point during its duration. This
+distinction is similar to the distinction between 'continuant' and
+'occurrent' in logic [<cite><a class="bibref" rel="biblioentry" href="#bib-Logic">Logic</a></cite>].</p>
+
+
+</div>
+<div id="events" class="section">
+<h3><span class="secno">2.2 </span>Events</h3>
+
+<p> Although time is important for provenance, provenance can be used
+in many different contexts within individual systems and across the
+Web. Different systems may use different clocks which may not be
+precisely synchronized, so when provenance statements are combined by
+different systems, we may not be able to align the times involved to a
+single global timeline. Hence, PROV is designed to minimize
+assumptions about time. Instead, PROV talks about (identified)
+events. </p>
+
+<p>The PROV data model is implicitly based on a notion of <dfn id="dfn-event">instantaneous event</dfn>s (or just <a title="instantaneous event" href="#dfn-event" class="internalDFN">event</a>s), that mark
+transitions in the world. Events include generation, usage, or
+invalidation of entities, as well as start or end of activities. This
+notion of event is not first-class in the data model, but it is useful
+for explaining its other concepts and its semantics [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-SEM">PROV-SEM</a></cite>].
+Thus, events help justify <i>inferences</i> on provenance as well as
+<i>validity</i> constraints indicating when provenance is
+ self-consistent.
+
+
+
+</p><p>Five kinds of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous
+events</a> are used in PROV. The <strong>activity start</strong>
+and <strong>activity end</strong> events delimit the beginning and the
+end of activities, respectively. The
+<strong>entity <span class="delete">usage</span><span class="insert">generation</span></strong>,
+ <strong>entity <span class="delete">generation</span><span class="insert">usage</span></strong>, and <strong>entity
+invalidation</strong> events apply to entities, and the generation and
+invalidation events delimit the <a href="#lifetime" class="internalDFN">lifetime</a> of an entity. More
+precisely:
+</p>
+
+<p>An <dfn id="dfn-start-event">activity start event</dfn> is the <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> that marks the instant an activity starts.</p>
+
+<p>An <dfn id="dfn-end-event">activity end event</dfn> is the <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> that marks the instant an activity ends.</p>
+
+<p>An <dfn id="dfn-generation-event"><span class="insert">entity generation event</span></dfn><span class="insert"> is the </span><a title="instantaneous event" href="#dfn-event" class="internalDFN"><span class="insert">instantaneous event</span></a><span class="insert"> that marks the final instant of an entity's creation timespan, after which
+it is available for use. The entity did not exist before this event.</span></p>
+
+
+<p><span class="insert">An </span><dfn id="dfn-usage-event">entity usage event</dfn> is the <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> that marks the first instant of
+an entity's consumption timespan by an activity. Before this instant
+the entity had not begun to be used by the activity.</p>
+
+<span class="delete">An </span><span class="delete">entity generation event</span><span class="delete"> is the </span><span class="delete">instantaneous event</span><span class="delete"> that marks the final instant of an entity's creation timespan, after which
+it is available for use. The entity did not exist before this event.</span>
+
+
+
+
+<p>An <dfn id="dfn-invalidation-event">entity invalidation event</dfn>
+is the <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> that
+marks the initial instant of the destruction, invalidation, or
+cessation of an entity, after which the entity is no longer available
+for use. The entity no longer exists after this event.</p>
+
+</div>
+
+<div id="summary-of-constraints-and-inferences" class="section">
+<h3><span class="secno">2.3 </span>Summary of constraints and inferences</h3>
+
+<p><a href="">Table <span class="delete">5</span><span class="insert">1</span></a> summarizes the definitions, inferences, and
+constraints of this document.
+</p>
+
+<div class="note">Table: work in progress; these entries might change when the document is updated.</div>
+
+<div id="prov-constraints-fig" style="text-align: left;">
+<table class="thinborder" style="margin-left: auto; margin-right: auto; border-color: #0;">
+<caption id="prov-constraints">Table <span class="delete">5:</span><span class="insert">1:</span> Summary of definitions, constraints, and inferences for PROV Types and Relations</caption>
+<tbody><tr><td><a><b>Type or Relation Name</b></a></td><td><b><span class="delete">Definitions, Constraints, </span>
+ Inferences<span class="insert"> and Constraints</span></b></td><td><b>Component</b></td></tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr class="component1-color">
+ <td class="essential"><a>Entity</a></td>
+ <td><a class="rule-text" href="#entity-generation-invalidation-inference_text"><span>Inference 7 (entity-generation-invalidation-inference)</span></a><br>
+ <a class="rule-text" href="#specialization-attributes-inference_text"><span>Inference 23 <span class="delete">(specialization-attributes)</span><span class="insert">(specialization-attributes-inference)</span></span></a><br>
+ <a class="rule-text" href="#key-object_text"><span>Constraint 25 (key-object)</span></a><br>
+ <a class="rule-text" href="#impossible-object-property-overlap_text"><span>Constraint <span class="delete">53</span><span class="insert">52</span> (impossible-object-property-overlap)</span></a><br>
+ <a class="rule-text" href="#entity-activity-disjoint_text"><span>Constraint <span class="delete">55</span><span class="insert">54</span> (entity-activity-disjoint)</span></a><br>
+ </td>
+ <td rowspan="8"><a href="http://www.w3.org/TR/prov-dm/#component1">Component 1: Entities/Activities</a></td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>Activity</a></td>
+ <td><a class="rule-text" href="#activity-start-end-inference_text"><span>Inference 8 (activity-start-end-inference)</span></a><br>
+ <a class="rule-text" href="#key-object_text"><span>Constraint 25 (key-object)</span></a><br>
+ <a class="rule-text" href="#unique-startTime_text"><span>Constraint 31 (unique-startTime)</span></a><br>
+ <a class="rule-text" href="#unique-endTime_text"><span>Constraint 32 (unique-endTime)</span></a><br>
+ <a class="rule-text" href="#impossible-object-property-overlap_text"><span>Constraint <span class="delete">53</span><span class="insert">52</span> (impossible-object-property-overlap)</span></a><br>
+ <a class="rule-text" href="#entity-activity-disjoint_text"><span>Constraint <span class="delete">55</span><span class="insert">54</span> (entity-activity-disjoint)</span></a><br>
+ </td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>Generation</a></td>
+ <td><a class="rule-text" href="#generation-use-communication-inference_text"><span>Inference 6 (generation-use-communication-inference)</span></a><br>
+ <a class="rule-text" href="#derivation-use-inference_text"><span>Inference 12 <span class="delete">(derivation-use)</span><span class="insert">(derivation-use-inference)</span></span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#unique-generation_text"><span>Constraint 27 (unique-generation)</span></a><br>
+ <a class="rule-text" href="#generation-within-activity_text"><span>Constraint 36 (generation-within-activity)</span></a><br>
+ <a class="rule-text" href="#generation-precedes-invalidation_text"><span>Constraint 38 (generation-precedes-invalidation)</span></a><br>
+ <a class="rule-text" href="#generation-precedes-usage_text"><span>Constraint 39 (generation-precedes-usage)</span></a><br>
+ <a class="rule-text" href="#derivation-usage-generation-ordering_text"><span>Constraint 41 (derivation-usage-generation-ordering)</span></a><br>
+ <a class="rule-text" href="#derivation-generation-generation-ordering_text"><span>Constraint 42 (derivation-generation-generation-ordering)</span></a><br>
+ <a class="rule-text" href="#wasStartedBy-ordering_text"><span>Constraint 43 (wasStartedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#wasEndedBy-ordering_text"><span>Constraint 44 (wasEndedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#specialization-generation-ordering_text"><span>Constraint 45 <span class="delete">(specialization-generation)</span><span class="insert">(specialization-generation-ordering)</span></span></a><br>
+ <a class="rule-text" href="#wasAssociatedWith-ordering_text"><span>Constraint 47 (wasAssociatedWith-ordering)</span></a><br>
+ <a class="rule-text" href="#wasAttributedTo-ordering_text"><span>Constraint 48 (wasAttributedTo-ordering)</span></a><br>
+ <a class="rule-text" href="#actedOnBehalfOf-ordering_text"><span>Constraint 49 (actedOnBehalfOf-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>Usage</a></td>
+ <td><a class="rule-text" href="#generation-use-communication-inference_text"><span>Inference 6 (generation-use-communication-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#usage-within-activity_text"><span>Constraint 35 (usage-within-activity)</span></a><br>
+ <a class="rule-text" href="#generation-precedes-usage_text"><span>Constraint 39 (generation-precedes-usage)</span></a><br>
+ <a class="rule-text" href="#usage-precedes-invalidation_text"><span>Constraint 40 (usage-precedes-invalidation)</span></a><br>
+ <a class="rule-text" href="#derivation-usage-generation-ordering_text"><span>Constraint 41 (derivation-usage-generation-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>Communication</a></td>
+ <td><a class="rule-text" href="#communication-generation-use-inference_text"><span>Inference 5 (communication-generation-use-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#wasInformedBy-ordering_text"><span>Constraint 37 (wasInformedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>Start</a></td>
+ <td><a class="rule-text" href="#wasStartedBy-inference_text"><span>Inference 9 (wasStartedBy-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#unique-wasStartedBy_text"><span>Constraint 29 (unique-wasStartedBy)</span></a><br>
+ <a class="rule-text" href="#unique-startTime_text"><span>Constraint 31 (unique-startTime)</span></a><br>
+ <a class="rule-text" href="#start-precedes-end_text"><span>Constraint 34 (start-precedes-end)</span></a><br>
+ <a class="rule-text" href="#usage-within-activity_text"><span>Constraint 35 (usage-within-activity)</span></a><br>
+ <a class="rule-text" href="#generation-within-activity_text"><span>Constraint 36 (generation-within-activity)</span></a><br>
+ <a class="rule-text" href="#wasInformedBy-ordering_text"><span>Constraint 37 (wasInformedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#wasStartedBy-ordering_text"><span>Constraint 43 (wasStartedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#wasAssociatedWith-ordering_text"><span>Constraint 47 (wasAssociatedWith-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>End</a></td>
+ <td><a class="rule-text" href="#wasEndedBy-inference_text"><span>Inference 10 (wasEndedBy-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#unique-wasEndedBy_text"><span>Constraint 30 (unique-wasEndedBy)</span></a><br>
+ <a class="rule-text" href="#unique-endTime_text"><span>Constraint 32 (unique-endTime)</span></a><br>
+ <a class="rule-text" href="#start-precedes-end_text"><span>Constraint 34 (start-precedes-end)</span></a><br>
+ <a class="rule-text" href="#usage-within-activity_text"><span>Constraint 35 (usage-within-activity)</span></a><br>
+ <a class="rule-text" href="#generation-within-activity_text"><span>Constraint 36 (generation-within-activity)</span></a><br>
+ <a class="rule-text" href="#wasInformedBy-ordering_text"><span>Constraint 37 (wasInformedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#wasEndedBy-ordering_text"><span>Constraint 44 (wasEndedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#wasAssociatedWith-ordering_text"><span>Constraint 47 (wasAssociatedWith-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component1-color">
+ <td class="essential"><a>Invalidation</a></td>
+ <td><a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#unique-invalidation_text"><span>Constraint 28 (unique-invalidation)</span></a><br>
+ <a class="rule-text" href="#generation-precedes-invalidation_text"><span>Constraint 38 (generation-precedes-invalidation)</span></a><br>
+ <a class="rule-text" href="#usage-precedes-invalidation_text"><span>Constraint 40 (usage-precedes-invalidation)</span></a><br>
+ <a class="rule-text" href="#wasStartedBy-ordering_text"><span>Constraint 43 (wasStartedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#wasEndedBy-ordering_text"><span>Constraint 44 (wasEndedBy-ordering)</span></a><br>
+ <a class="rule-text" href="#specialization-invalidation-ordering_text"><span>Constraint 46 <span class="delete">(specialization-invalidation)</span><span class="insert">(specialization-invalidation-ordering)</span></span></a><br>
+ <a class="rule-text" href="#wasAssociatedWith-ordering_text"><span>Constraint 47 (wasAssociatedWith-ordering)</span></a><br>
+ <a class="rule-text" href="#wasAttributedTo-ordering_text"><span>Constraint 48 (wasAttributedTo-ordering)</span></a><br>
+ <a class="rule-text" href="#actedOnBehalfOf-ordering_text"><span>Constraint 49 (actedOnBehalfOf-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+
+<tr class="component2-color">
+ <td class="essential"><a>Derivation</a></td>
+ <td><a class="rule-text" href="#derivation-generation-use-inference_text"><span>Inference 11 <span class="delete">(derivation-generation-use)</span><span class="insert">(derivation-generation-use-inference)</span></span></a><br>
+ <a class="rule-text" href="#derivation-use-inference_text"><span>Inference 12 <span class="delete">(derivation-use)</span><span class="insert">(derivation-use-inference)</span></span></a><br>
+ <a class="rule-text" href="#specific-derivation-inference_text"><span>Inference 13 (specific-derivation-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#derivation-usage-generation-ordering_text"><span>Constraint 41 (derivation-usage-generation-ordering)</span></a><br>
+ <a class="rule-text" href="#derivation-generation-generation-ordering_text"><span>Constraint 42 (derivation-generation-generation-ordering)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+ <td rowspan="5"><a href="http://www.w3.org/TR/prov-dm/#component2">Component 2: Derivations</a></td>
+</tr>
+<tr class="component2-color">
+ <td class="provType"><a>Revision</a></td>
+ <td><a class="rule-text" href="#revision-is-alternate-inference_text"><span>Inference 14 <span class="delete">(revision-is-alternate)</span><span class="insert">(revision-is-alternate-inference)</span></span></a><br></td>
+</tr>
+<tr class="component2-color">
+ <td class="provType"><a>Quotation</a></td>
+ <td></td>
+</tr>
+<tr class="component2-color">
+ <td class="provType"><a>Primary Source</a></td>
+ <td></td>
+</tr>
+<tr class="component2-color">
+ <td><a class="essential">Influence</a></td>
+ <td></td>
+</tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr class="component3-color" style="border-collapse: collapse; ">
+ <td class="essential"><a>Agent</a></td>
+ <td><a class="rule-text" href="#key-object_text"><span>Constraint 25 (key-object)</span></a><br>
+ <a class="rule-text" href="#impossible-object-property-overlap_text"><span>Constraint <span class="delete">53</span><span class="insert">52</span> (impossible-object-property-overlap)</span></a><br>
+ </td>
+ <td rowspan="5"><a href="http://www.w3.org/TR/prov-dm/#component3">Component 3: Agents/Responsibility</a></td>
+</tr>
+<tr class="component3-color">
+ <td class="essential"><a>Attribution</a></td>
+ <td><a class="rule-text" href="#attribution-inference_text"><span>Inference 15 (attribution-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#wasAttributedTo-ordering_text"><span>Constraint 48 (wasAttributedTo-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component3-color">
+ <td class="essential"><a>Association</a></td>
+ <td><a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#wasAssociatedWith-ordering_text"><span>Constraint 47 (wasAssociatedWith-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component3-color">
+ <td class="essential"><a>Delegation</a></td>
+ <td><a class="rule-text" href="#delegation-inference_text"><span>Inference 16 (delegation-inference)</span></a><br>
+ <a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)</span></a><br>
+ <a class="rule-text" href="#actedOnBehalfOf-ordering_text"><span>Constraint 49 (actedOnBehalfOf-ordering)</span></a><br>
+ <a class="rule-text" href="#impossible-property-overlap_text"><span>Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component3-color">
+ <td class="essential"><a>Influence</a></td>
+ <td><a class="rule-text" href="#influence-inference_text"><span>Inference 17 (influence-inference)</span></a><br>
+ <a class="rule-text" href="#key-properties_text"><span>Constraint 26 (key-properties)
+ <span class="delete">Constraint 50 (impossible-influence-reflexive)</span></span></a><br>
+ </td>
+</tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr class="component4-color">
+ <td><a title="bundle">Bundle constructor</a></td>
+ <td></td>
+ <td rowspan="2"><a href="http://www.w3.org/TR/prov-dm/#component4">Component 4: Bundles</a></td>
+</tr>
+<tr class="component4-color">
+ <td class="provType"><a title="bundle">Bundle type</a></td>
+ <td> </td>
+</tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr class="component5-color">
+ <td><a>Alternate</a></td>
+ <td><a class="rule-text" href="#alternate-reflexive_text"><span>Inference 18 (alternate-reflexive)</span></a><br>
+ <a class="rule-text" href="#alternate-transitive_text"><span>Inference 19 (alternate-transitive)</span></a><br>
+ <a class="rule-text" href="#alternate-symmetric_text"><span>Inference 20 (alternate-symmetric)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+ <td rowspan="3"><a href="http://www.w3.org/TR/prov-dm/#component5">Component 5: Alternate Entities</a></td>
+</tr>
+<tr class="component5-color">
+ <td><a>Specialization</a></td>
+ <td><a class="rule-text" href="#specialization-transitive_text"><span>Inference 21 (specialization-transitive)</span></a><br>
+ <a class="rule-text" href="#specialization-alternate-inference_text"><span>Inference 22 <span class="delete">(specialization-alternate)</span><span class="insert">(specialization-alternate-inference)</span></span></a><br>
+ <a class="rule-text" href="#specialization-attributes-inference_text"><span>Inference 23 <span class="delete">(specialization-attributes)</span><span class="insert">(specialization-attributes-inference)</span></span></a><br>
+ <a class="rule-text" href="#specialization-generation-ordering_text"><span>Constraint 45 <span class="delete">(specialization-generation)</span><span class="insert">(specialization-generation-ordering)</span></span></a><br>
+ <a class="rule-text" href="#specialization-invalidation-ordering_text"><span>Constraint 46 <span class="delete">(specialization-invalidation)</span><span class="insert">(specialization-invalidation-ordering)</span></span></a><br>
+ <a class="rule-text" href="#impossible-specialization-reflexive_text"><span>Constraint <span class="delete">51</span><span class="insert">50</span> (impossible-specialization-reflexive)</span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr class="component5-color">
+ <td><a>Mention</a></td>
+ <td><a class="rule-text" href="#mention-specialization-inference_text"><span>Inference 24 <span class="delete">(mention-specialization)</span><span class="insert">(mention-specialization-inference)</span></span></a><br>
+ <a class="rule-text" href="#unique-mention_text"><span>Constraint 33 <span class="delete">(mention-unique)</span><span class="insert">(unique-mention)</span></span></a><br>
+ <a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br>
+ </td>
+</tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr class="component6-color">
+ <td><a>Collection</a></td>
+ <td> </td>
+ <td rowspan="2"><a href="http://www.w3.org/TR/prov-dm/#component6">Component 6: Collections</a></td>
+</tr>
+<tr class="component6-color">
+ <td><a>Membership</a></td>
+ <td><a class="rule-text" href="#typing_text"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a><br></td>
+</tr>
+</tbody></table>
+</div>
+
+
+</div>
+
+</div>
+
+<div id="compliance" class="section">
+<h2><span class="secno">3. </span>Compliance with this document</h2>
+
+<p>
+ For the purpose of compliance, the normative sections of this document
+ are <a href="#compliance" class="sectionRef">section 3. Compliance with this document</a>, <a href="#inferences" class="sectionRef">section 4. Inferences and Definitions</a>, <a href="#constraints" class="sectionRef">section 5. Constraints</a>, and <a href="#normalization-validity-equivalence" class="sectionRef">section 6. Normalization, Validity, and Equivalence</a>.
+
+
+ To be compliant:
+ </p><ol><li>When processing provenance, an
+ application <em class="rfc2119" title="may">may</em> apply the inferences and definitions in <a href="#inferences" class="sectionRef">section 4. Inferences and Definitions</a>.</li>
+ <li>When determining whether a PROV instance is <a href="#dfn-valid" class="internalDFN">valid</a>, an
+ application <em class="rfc2119" title="must">must</em> check that all of the
+ constraints of <a href="#constraints" class="sectionRef">section 5. Constraints</a> are
+ satisfied on the <a href="#dfn-normal-form" class="internalDFN">normal form</a> of the instance.</li>
+ <li> When producing provenance meant for other applications to
+ use, the application <em class="rfc2119" title="should">should</em> produce <a href="#dfn-valid" class="internalDFN">valid</a> provenance, as specified in <a href="#normalization-validity-equivalence" class="sectionRef">section 6. Normalization, Validity, and Equivalence</a>. </li>
+ <li>When determining whether two PROV instances are
+ <a href="#dfn-equivalent" class="internalDFN">equivalent</a>, an application <em class="rfc2119" title="must">must</em> determine whether their
+ normal forms are equal, as specified in <a href="#normalization-validity-equivalence" class="sectionRef">section 6. Normalization, Validity, and Equivalence</a>.
+ </li></ol>
+
+
+ <p>
+ All diagrams are for illustration purposes
+ only. Text in appendices and
+in boxes labeled "Remark" is informative. Where there is any apparent
+ ambiguity between the descriptive text and the formal text in a
+ "definition", "inference" or "constraint" box, the formal text takes
+priority.
+ </p>
+
+ <div class="note"> To reviewers: We specifically invite review for
+ consistency between the informal and formal text.</div>
+
+</div>
+
+
+
+<div id="inferences" class="section">
+<h2><span class="secno">4. </span>Inferences and Definitions</h2>
+<p>
+In this section, we describe <a title="inference" href="#inference" class="internalDFN">inferences</a> and <a title="definition" href="#definition" class="internalDFN">definitions</a> that <em class="rfc2119" title="may">may</em> be used on
+ provenance data, and preserve <a>equivalence</a> on <a href="#dfn-valid" class="internalDFN">valid</a>
+PROV instances (as detailed in <a href="#normalization-validity-equivalence" class="sectionRef">section 6. Normalization, Validity, and Equivalence</a>).
+An <dfn id="inference">inference</dfn> is a rule that can be applied
+ to PROV instances to add new PROV statements. A <dfn id="definition">definition</dfn> is a rule that <span class="insert">can be applied to
+ PROV instances to replace defined expressions with definitions. A definition </span>states that a
+ provenance statement is equivalent to some other <span class="delete">statements;</span><span class="insert">statements, whereas
+ an inference only states one direction of an implication;</span> thus,
+ defined provenance statements can be replaced by their <span class="delete">definitions,
+and vice versa.</span><span class="insert">definitions.</span>
+</p>
+
+<p> Inferences have the following general form:</p>
+<div class="inference-example" id="inference-example"><div class="ruleTitle"><a class="internalDFN" href="#inference-example">Inference-example NNN (inference-example)</a></div>
+<p>
+ <span class="conditional">IF</span> <span class="name">hyp<sub>1</sub></span> and ... and
+<span class="name">hyp<sub>k</sub></span> <span class="conditional">THEN</span>
+ there exists <span class="name">a<sub>1</sub></span> and ... and <span class="name">a<sub>m</sub></span> such that <span class="name">conclusion<sub>1</sub></span> and ... and <span class="name">conclusion<sub>n</sub></span>.</p>
+ </div>
+
+<p> This means that if all of the provenance statements matching
+ <span class="name">hyp<sub>1</sub></span>... <span class="name">hyp<sub>k</sub></span>
+ can be found in a PROV instance, we can add all of the statements
+ <span class="name">concl<sub>1</sub></span> ... <span class="name">concl<sub>n</sub></span> to the instance, possibly after
+ generating fresh identifiers <span class="name">a<sub>1</sub></span>,...,<span class="name">a<sub>m</sub></span> for unknown objects. These fresh
+ identifiers might later be found to be equal to known identifiers;
+ they play a similar role in PROV constraints to existential
+ variables in logic, "labeled nulls" in database theory
+ [<cite><a class="bibref" rel="biblioentry" href="#bib-DBCONSTRAINTS">DBCONSTRAINTS</a></cite>], or to blank nodes in [<cite><a class="bibref" rel="biblioentry" href="#bib-RDF">RDF</a></cite>]. <span class="delete">With a few
+ exceptions (discussed below),</span><span class="insert">In general,</span> omitted optional parameters to
+ [<cite><a class="bibref" rel="biblioentry" href="#bib-PROV-N">PROV-N</a></cite>] statements, or explicit <span class="name">-</span>
+ markers, are placeholders for existentially quantified variables;
+ that is, they denote unknown values. <span class="insert">There are a few exceptions to
+ this general rule, which are specified in </span><a class="rule-ref" href="#optional-placeholders"><span><span class="insert">Definition 4 (optional-placeholders)</span></span></a></p>
+
+<p> Definitions have the following general form:</p>
+
+<div class="definition-example" id="definition-example"><div class="ruleTitle"><a class="internalDFN" href="#definition-example">Definition-example NNN (definition-example)</a></div>
+<p>
+ <span class="name">defined_exp</span> holds <span class="conditional">IF AND ONLY IF</span>
+ there exists <span class="name">a<sub>1</sub></span>,..., <span class="name">a<sub>m</sub></span> such that <span class="name">defining_exp<sub>1</sub></span> and ... and <span class="name">defining_exp<sub>n</sub></span>.</p>
+ </div>
+
+ <p>
+ This means that a provenance statement <span class="name">defined_exp</span> is defined in
+ terms of other statements. This can be viewed as a two-way
+ inference: If <span class="name">defined_exp</span>
+ can be found in a PROV instance, we can add all of the statements
+<span class="name">defining_exp<sub>1</sub></span> ... <span class="name">defining_exp<sub>n</sub></span> to the instance, possibly after generating fresh
+ identifiers <span class="name">a<sub>1</sub></span>,...,<span class="name">a<sub>m</sub></span> for unknown objects. It is safe to replace
+ a defined statement with
+ its definition.
+</p>
+
+<p> Definitions and inferences can be viewed as logical formulas;
+ similar formalisms are often used in rule-based reasoning [<cite><a class="bibref" rel="biblioentry" href="#bib-CHR">CHR</a></cite>]
+ and in databases [<cite><a class="bibref" rel="biblioentry" href="#bib-DBCONSTRAINTS">DBCONSTRAINTS</a></cite>]. In particular, the identifiers
+ <span class="name">a<sub>1</sub></span> ... <span class="name">a<sub>n</sub></span>
+ should be viewed as existentially quantified variables, meaning that
+ through subsequent reasoning steps they may turn out to be equal to
+ other identifiers that are already known, or to other existentially
+ quantified variables. Their treatment is analogous to that of blank
+ nodes in RDF. In contrast, distinct URIs or literal values in PROV
+ are assumed to be distinct for the purpose of checking validity or
+ inferences. This issue is discussed in more detail under <a href="#uniqueness-constraints">Uniqueness Constraints</a> below.
+ </p>
+
+<div id="optional-identifiers-and-attributes" class="section">
+ <h3><span class="secno">4.1 </span>Optional Identifiers and Attributes</h3>
+
+ <p>Many PROV relation statements have an identifier, identifying a
+ link between two or more related objects. Identifiers can sometimes
+ be omitted in [<cite><span class="delete">PROV-N</span><a class="bibref" rel="biblioentry" href="#bib-PROV-O"><span class="insert">PROV-O</span></a></cite>] notation. For the purpose of inference and
+ validity checking, we generate special identifiers called
+ <dfn id="dfn-existential-variables">existential variables</dfn> denoting the unknown values.
+ Existential variables can be <em>substituted</em> with constant
+ identifiers, literals, the placeholder <span class="name">-</span>,
+ or other <a href="#dfn-existential-variables" class="internalDFN">existential variables</a>.
+<span class="delete">We note that</span><a class="rule-ref" href="#optional-identifiers"><span><span class="insert">Definition 1 (optional-identifiers)</span></span></a><span class="insert">,
+</span><a class="rule-ref" href="#optional-attributes"><span><span class="insert">Definition 2 (optional-attributes)</span></span></a><span class="insert">,
+, and
+</span><a class="rule-ref" href="#definition-short-forms"><span><span class="insert">Definition 3 (definition-short-forms)</span></span></a><span class="insert">,
+ explain how to expand the compact forms of PROV-N notation into a
+ normal form.</span> <span class="delete">Definitions 1, 2, and 3 desugar compact PROV-N notation into a normal form.
+</span><a class="rule-ref" href="#optional-placeholders"><span><span class="insert">Definition 4 (optional-placeholders)</span></span></a><span class="insert"> indicates when
+ other optional parameters can be replaced by </span><a href="#dfn-existential-variables" class="internalDFN"><span class="insert">existential
+ variables</span></a><span class="insert">.
+</span></p>
+
+ <div class="definition" id="optional-identifiers"><div class="ruleTitle"><a class="internalDFN" href="#optional-identifiers">Definition 1 (optional-identifiers)</a></div>
+<p>For each <span class="name">r</span> in {
+<span class="name">used</span>,
+<span class="name">wasGeneratedBy</span>,
+<span class="name">wasInvalidatedBy</span>,
+<span class="name">wasInfluencedBy</span>,
+<span class="name">wasStartedBy</span>,
+<span class="name">wasEndedBy</span>,
+<span class="name">wasInformedBy</span>,
+<span class="name">wasDerivedFrom</span>,
+<span class="name">wasAttributedTo</span>,
+<span class="name">wasAssociatedWith</span>,
+<span class="name">actedOnBehalfOf</span>}, the following
+ definitional rules hold:</p>
+ <ol> <li>
+ <span class="name">r(a<sub>1</sub>,...,a<sub>n</sub>) </span> holds <span class="conditional">IF AND ONLY IF</span>
+ there exists <span class="name">id</span> such that <span class="name"><span class="delete">r(id;a</span><span class="insert">r(id; a</span><sub>1</sub>,...,a<sub>n</sub>)</span> holds.</li>
+ <li> <span class="name"><span class="delete">r(-;a</span><span class="insert">r(-; a</span><sub>1</sub>,...,a<sub>n</sub>) </span> holds <span class="conditional">IF AND ONLY IF</span>
+ there exists <span class="name">id</span> such that <span class="name"><span class="delete">r(id;a</span><span class="insert">r(id; a</span><sub>1</sub>,...,a<sub>n</sub>)</span> holds.</li>
+ </ol>
+ </div>
+
+ <p>Likewise, many <span class="delete">PROV</span><span class="insert">PROV-N</span> statements allow for an optional attribute
+ list. If it is omitted, this is the same as specifying an empty
+ attribute list:</p>
+ <div class="definition" id="optional-attributes"><div class="ruleTitle"><a class="internalDFN" href="#optional-attributes">Definition 2 (optional-attributes)</a></div>
+<ol>
+ <li>
+
+ For each <span class="name"><span class="delete">r</span><span class="insert">p</span></span> in {<span class="name">entity</span>, <span class="name">activity</span>,
+ <span class="name">agent</span>}, if <span class="name"><span class="delete">a_n</span><span class="insert">a</span><sub><span class="insert">n</span></sub></span> is not an attribute
+ list parameter then the following definitional rule holds:
+ <p><span class="name"><span class="delete">r(a</span><span class="insert">p(a</span><sub>1</sub>,...,a<sub>n</sub>)</span>
+ holds <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">r(a</span><span class="insert">p(a</span><sub>1</sub>,...,a<sub>n</sub>,[])</span> holds.
+ </p></li>
+
+ <li>
+ For each <span class="name">r</span> in {
+<span class="name">used</span>,
+<span class="name">wasGeneratedBy</span>,
+<span class="name">wasInvalidated</span>,
+<span class="name">wasInfluencedBy</span>,
+<span class="name">wasStartedBy</span>,
+<span class="name">wasEndedBy</span>,
+<span class="name">wasInformedBy</span>,
+<span class="name">wasDerivedFrom</span>,
+<span class="name">wasAttributedTo</span>,
+<span class="name">wasAssociatedWith</span>,
+<span class="name">actedOnBehalfOf</span>}, if <span class="name"><span class="delete">a_n</span><span class="insert">a</span><sub><span class="insert">n</span></sub></span> is not an
+ attribute list parameter then the following definition holds:
+
+ <p> <span class="name"><span class="delete">r(id;a</span><span class="insert">r(id; a</span><sub>1</sub>,...,a<sub>n</sub>)</span> holds
+ <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">r(id;a</span><span class="insert">r(id; a</span><sub>1</sub>,...,a<sub>n</sub>,[])</span> holds.</p></li></ol>
+ </div>
+
+ <p> Finally, many PROV
+ statements have other optional arguments or short forms that can be
+ used if none of the optional arguments is present. These are
+ handled by specific rules listed below. </p>
+
+<div class="definition" id="definition-short-forms"><div class="ruleTitle"><a class="internalDFN" href="#definition-short-forms">Definition 3 (definition-short-forms)</a></div>
+ <p>
+
+ </p><ol>
+ <li> <span class="name">activity(id,attrs)</span> <span class="conditional">IF AND ONLY IF</span> <span class="name">activity(id,-,-,attrs)</span>.
+ </li>
+ <li><span class="name"><span class="delete">wasGeneratedBy(id;e,attrs)</span><span class="insert">wasGeneratedBy(id; e,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">wasGeneratedBy(id;e,-,-,attrs)</span><span class="insert">wasGeneratedBy(id; e,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">used(id;a,attrs)</span><span class="insert">used(id; a,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">used(id;a,-,-,attrs)</span><span class="insert">used(id; a,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">wasStartedBy(id;a,attrs)</span><span class="insert">wasStartedBy(id; a,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">wasStartedBy(id;a,-,-,-,attrs)</span><span class="insert">wasStartedBy(id; a,-,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">wasEndedBy(id;a,attrs)</span><span class="insert">wasEndedBy(id; a,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">wasEndedBy(id;a,-,-,-,attrs)</span><span class="insert">wasEndedBy(id; a,-,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">wasInvalidatedBy(id;e,attrs)</span><span class="insert">wasInvalidatedBy(id; e,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">wasInvalidatedBy(id;e,-,-,attrs)</span><span class="insert">wasInvalidatedBy(id; e,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">wasDerivedFrom(id;e2,e1,attrs)</span><span class="insert">wasDerivedFrom(id; e2,e1,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">wasDerivedFrom(id;e2,e1,-,-,-,attrs)</span><span class="insert">wasDerivedFrom(id; e2,e1,-,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">wasAssociatedWith(id;e,attrs)</span><span class="insert">wasAssociatedWith(id; e,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">wasAssociatedWith(id;e,-,-,attrs)</span><span class="insert">wasAssociatedWith(id; e,-,-,attrs)</span></span>.
+ </li>
+ <li><span class="name"><span class="delete">actedOnBehalfOf(id;a2,a1,attrs)</span><span class="insert">actedOnBehalfOf(id; a2,a1,attrs)</span></span> <span class="conditional">IF AND ONLY IF</span> <span class="name"><span class="delete">actedOnBehalfOf(id;a2,a1,-,attrs)</span><span class="insert">actedOnBehalfOf(id; a2,a1,-,attrs)</span></span>.
+ </li>
+ </ol>
+ </div>
+
+ <div class="remark">
+
+
+ <p>
+
+There
+ are <span class="delete">also </span>no expansion rules for entity, agent, <span class="delete">communiction,
+ </span><span class="insert">communication,
+ </span>attribution, influence, alternate, or specialization, because these
+ have no optional parameters aside
+ from the identifier and <span class="delete">attribute, </span><span class="insert">attributes,
+ </span>which are expanded by <span class="delete">other
+ </span><span class="insert">the </span>rules <span class="delete">above.</span><span class="insert">in </span><a class="rule-ref" href="#optional-attributes"><span><span class="insert">Definition 2 (optional-attributes)</span></span></a><span class="insert">. </span></p>
+ </div>
+
+
+<p id="optional-placeholders_text">Finally, most optional parameters (written <span class="name">-</span>) are, for the purpose of this document,
+ considered to be distinct, fresh existential variables. Thus,
+ before proceeding to apply other definitions or inferences, most
+ occurrences of <span class="name">-</span> <span class="delete">must</span><span class="insert">are to</span> be replaced
+ by fresh existential variables, distinct from any others occurring in
+ the instance.
+ The only <span class="delete">exceptions,</span><span class="insert">exceptions to this general rule,</span> where <span class="name">-</span> <span class="delete">must</span><span class="insert">are to</span> be left
+ in place, are the <a href="http://www.w3.org/TR/prov-dm/#derivation.activity">activity<span class="delete"> parameter</span></a><span class="insert">, </span><a href="http://www.w3.org/TR/prov-dm/#derivation.generation"><span class="insert">generation</span></a><span class="insert">, and </span><a href="http://www.w3.org/TR/prov-dm/#derivation.usage"><span class="insert">usage</span></a><span class="insert"> parameters</span> in <span class="name">wasDerivedFrom</span> and
+ the <a href="http://www.w3.org/TR/prov-dm/#association.plan">plan </a>
+ parameter in <span class="name">wasAssociatedWith</span>.
+ </p>
+
+ <p>The <span class="delete">following table characterizes the</span><span class="insert">treatment of optional parameters is specified formally using
+ the auxiliary concept of</span> <dfn id="dfn-expandable-parameter"><span class="insert">expandable parameter</span></dfn><span class="insert">. An
+ expandable parameter is one that can be omitted using the
+ placeholder </span><span class="name"><span class="insert">-</span></span><span class="insert">, and if so, it is
+ to be replaced by a fresh existential identifier.
+ </span><a href="#expandable-parameters-fig"><span class="insert">Table 2</span></a><span class="insert"> defines the </span><a href="#dfn-expandable-parameter" class="internalDFN">expandable
+ parameter</a>s of the properties of PROV, needed in <span class="delete">the
+ following definition.</span><a class="rule-ref" href="#optional-placeholders"><span><span class="insert">Definition 4 (optional-placeholders)</span></span></a><span class="insert">.</span> For emphasis, the <span class="delete">two</span><span class="insert">four</span> optional parameters
+ that are not <a title="expandable parameter" href="#dfn-expandable-parameter" class="internalDFN">expandable</a> are
+ also listed.</p>
+ <div id="expandable-parameters-fig">
+ <table id="expandable-parameters" border="1" class="thinborder" style="margin-left: auto; margin-right: auto; border-color: black;">
+<caption id="expandable-parameters"><span class="insert">Table 2: Expandable and
+ Non-Expandable Parameters</span></caption>
+<tbody><tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+ <tr>
+ <th>Relation</th>
+ <th>Expandable </th>
+ <th>Non-expandable</th>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasGeneratedBy(id;e,a,t,attrs)</span><span class="insert">wasGeneratedBy(id; e,a,t,attrs)</span></td>
+ <td class="name">id,a,t</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">used(id;a,e,t,attrs)</span><span class="insert">used(id; a,e,t,attrs)</span></td>
+ <td class="name">id,e,t</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasInformedBy(id;a2,a1,attrs)</span><span class="insert">wasInformedBy(id; a2,a1,attrs)</span></td>
+ <td class="name">id</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasStartedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasStartedBy(id; a2,e,a1,t,attrs)</span></td>
+ <td class="name">id,e,a1,t</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasEndedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasEndedBy(id; a2,e,a1,t,attrs)</span></td>
+ <td class="name">id,e,a1,t</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasInvalidatedBy(id;e,a,t,attrs)</span><span class="insert">wasInvalidatedBy(id; e,a,t,attrs)</span></td>
+ <td class="name">id,a,t</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasDerivedFrom(id;e2,e1,a,g2,u1,attrs)</span><span class="insert">wasDerivedFrom(id; e2,e1,a,g2,u1,attrs)</span></td>
+ <td class="name"><span class="delete">id,g2,u1</span><span class="insert">id</span></td>
+ <td class="name"><span class="delete">a</span><span class="insert">a,g2,u1</span></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasDerivedFrom(id;e2,e1,attrs)</span><span class="insert">wasDerivedFrom(id; e2,e1,attrs)</span></td>
+ <td class="name">id</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasAttributedTo(id;e,ag,attr)</span><span class="insert">wasAttributedTo(id; e,ag,attr)</span></td>
+ <td class="name">id</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasAssociatedWith(id;a,ag,pl,attrs)</span><span class="insert">wasAssociatedWith(id; a,ag,pl,attrs)</span></td>
+ <td class="name">id,ag</td>
+ <td class="name">pl</td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">actedOnBehalfOf(id;ag2,ag1,a,attrs)</span><span class="insert">actedOnBehalfOf(id; ag2,ag1,a,attrs)</span></td>
+ <td class="name">id,a</td>
+ <td></td>
+ </tr>
+ <tr>
+ <td class="name"><span class="delete">wasInfluencedBy(id;e2,e1,attrs)</span><span class="insert">wasInfluencedBy(id; e2,e1,attrs)</span></td>
+ <td class="name">id</td>
+ <td></td>
+ </tr>
+</tbody></table>
+ </div>
+
+ <div class="definition" id="optional-placeholders"><div class="ruleTitle"><a class="internalDFN" href="#optional-placeholders">Definition 4 (optional-placeholders)</a></div>
+ <ol><li><span class="delete">
+For each </span><span class="delete">r</span><span class="delete"> in {</span><span class="delete">entity</span><span class="delete">, </span><span class="delete">activity</span><span class="delete">,
+ </span><span class="delete">agent</span><span class="delete">}, the following definition
+ holds:</span>
+
+ <span class="delete">r(a</span><span class="delete">0</span><span class="delete">,...,a</span><span class="delete">i-1</span><span class="delete">, -, a</span><span class="delete">i+1</span><span class="delete">, ...,a</span><span class="delete">n</span><span class="delete">) </span><span class="name"><span class="insert">activity(id,-,t2,attrs)</span></span> <span class="conditional">IF AND ONLY
+ IF</span> there exists <span class="name"><span class="delete">a'</span>
+ <span class="insert">t1</span></span> such that <span class="name"><span class="delete">r(a</span><span class="delete">0</span><span class="delete">,...,a</span><span class="delete">i-1</span><span class="delete">,a',a</span><span class="delete">i+1</span><span class="delete">,...,a</span><span class="delete">n</span><span class="delete">)</span><span class="insert">activity(id,t1,t2,attrs)</span></span>.
+
+ </li>
+
+<li> <span class="name"><span class="insert">activity(id,t1,-,attrs)</span></span> <span class="conditional"><span class="insert">IF AND ONLY
+ IF</span></span><span class="insert"> there exists </span><span class="name"><span class="insert">t2</span></span><span class="insert"> such that </span><span class="name"><span class="insert">activity(id,t1,t2,attrs)</span></span><span class="insert">.
+</span></li>
+
+ <li>For each <span class="name">r</span> in {
+<span class="name">used</span>,
+<span class="name">wasGeneratedBy</span>,
+<span class="name">wasInfluencedBy</span>,
+<span class="name">wasInvalidatedBy</span>,
+<span class="name">wasStartedBy</span>,
+<span class="name">wasEndedBy</span>,
+<span class="name">wasInformedBy</span>,
+<span class="name">wasDerivedFrom</span>,
+<span class="name">wasAttributedTo</span>,
+<span class="name">wasAssociatedWith</span>,
+<span class="name">actedOnBehalfOf</span>}, if the <span class="name">i</span>th parameter
+ of <span class="name">r</span> is an <a href="#dfn-expandable-parameter" class="internalDFN">expandable parameter</a>
+ of <span class="name">r</span> then the following definition holds:
+ <p> <span class="name">r(a<sub>0</sub>;...,a<sub>i-1</sub>, -, a<sub>i+1</sub>, ...,a<sub>n</sub>) </span> <span class="conditional">IF AND ONLY IF</span> there exists <span class="name">a'</span>
+ such that <span class="name">r(a<sub>0</sub>;...,a<sub>i-1</sub>,a',a<sub>i+1</sub>,...,a<sub>n</sub>)</span>.
+ </p></li></ol>
+ </div>
+
+ <div class="remark">
+<p>In an association of the form
+ <span class="name"><span class="delete">wasAssociatedWith(id;a, ag,-,attr)</span><span class="insert">wasAssociatedWith(id; a,ag,-,attr)</span></span>, the
+ absence of a plan means: either no plan exists, or a plan exists but
+ it is not identified. Thus, it is not equivalent to <span class="name"><span class="delete">wasAssociatedWith(id;a,ag,p,attr)</span><span class="insert">wasAssociatedWith(id; a,ag,p,attr)</span></span> where a
+ plan <span class="name">p</span> is given.</p>
+</div>
+ <div class="remark">
+<p><span class="insert"> A derivation</span> <span class="delete">Similarly,</span><span class="name"><span class="insert">wasDerivedFrom(id; e2,e1,a,gen,use,attrs)</span></span><span class="insert"> that
+ specifies an activity explicitly indicates that this activity achieved the derivation, with</span> a<span class="insert"> usage </span><span class="name"><span class="insert">use</span></span><span class="insert"> of entity </span><span class="name"><span class="insert">e1</span></span><span class="insert">, and a generation </span><span class="name"><span class="insert">gen</span></span><span class="insert"> of entity </span><span class="name"><span class="insert">e2</span></span><span class="insert">.
+ It differs from a derivation of the form
+ </span><span class="name"><span class="insert">wasDerivedFrom(id; e2,e1,-,-,-,attrs)</span></span><span class="insert"> with
+ missing activity, generation, and usage. In the latter form, it is not specified
+ if one or more activities are involved in the derivation. </span></p>
+
+ <p><span class="insert">Let us consider a system, in which a derivation is underpinned by multiple activities. Conceptually, one could also model such a system with a new activity that encompasses the two original activities and underpins the derivation. The infererences defined in this specification do not allow the latter modelling to be inferred from the former. Hence, the two</span> <span class="delete">wasDerivedFrom(id;e2,e1,a,gen,use,attrs)</span><span class="delete"> that
+ specifies an activity explicitly is not
+ equivalent to </span><span class="delete">wasDerivedFrom(id;e2,e1,-,gen,use,attrs)</span><span class="delete"> with a
+ missing activity.</span><span class="insert">modellings of the same system are regarded as different in the context of this specification.</span></p>
+ </div>
+</div>
+
+<div id="entities-and-activities" class="section">
+ <h3><span class="secno">4.2 </span>Entities and Activities</h3>
+
+
+
+
+<p id="communication-generation-use-inference_text">Communication between activities is <a title="definition" href="#definition" class="internalDFN">defined</a> as the existence of an underlying
+entity generated by one activity and used by the other.</p>
+
+<div class="inference" id="communication-generation-use-inference"><div class="ruleTitle"><a class="internalDFN" href="#communication-generation-use-inference">Inference 5 (communication-generation-use-inference)</a></div>
+<p>
+<span class="conditional">IF</span>
+<span class="name"><span class="delete">wasInformedBy(_id;a2,a1,_attrs)</span><span class="insert">wasInformedBy(_id; a2,a1,_attrs)</span></span>
+holds <span class="conditional">THEN</span>
+ there exist <span class="name">e</span>, <span class="name">_id1</span>, <span class="name">_t1</span>, <span class="name">_id2</span>, and <span class="name">_t2</span>,
+such that <span class="name"><span class="delete">wasGeneratedBy(_id1;e,a1,_t1,[])</span><span class="delete"> and </span><span class="delete">used(_id2;a2,e,_t2,[])</span><span class="insert">wasGeneratedBy(_id1; e,a1,_t1,[])</span></span><span class="insert"> and </span><span class="name"><span class="insert">used(_id2; a2,e,_t2,[])</span></span> hold.</p>
+</div>
+
+<p id="generation-use-communication-inference_text">
+
+</p><div class="note">
+A final check is required on <a class="rule-text" href="#generation-use-communication-inference_text"><span><span class="insert">Inference 6 (generation-use-communication-inference)</span></span></a> this<span class="delete"> inference</span> to ensure that it does not lead to non-termination, when combined with
+<a class="rule-text" href="#communication-generation-use-inference_text"><span>Inference 5 (communication-generation-use-inference)</span></a>.
+ </div>
+
+ <div class="inference" id="generation-use-communication-inference"><div class="ruleTitle"><a class="internalDFN" href="#generation-use-communication-inference">Inference 6 (generation-use-communication-inference)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasGeneratedBy(_id1;e,a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(_id1; e,a1,_t1,_attrs1)</span></span>
+ and <span class="name"><span class="delete">used(_id2;a2,e,_t2,_attrs2)</span><span class="insert">used(_id2; a2,e,_t2,_attrs2)</span></span> hold
+ <span class="conditional">THEN</span>
+ there exists <span class="name">_id</span>
+such that <span class="name"><span class="delete">wasInformedBy(_id;a2,a1,[])</span><span class="insert">wasInformedBy(_id; a2,a1,[])</span></span>
+</p></div>
+
+
+ <div class="remark">
+<p>The relationship <span class="name">wasInformedBy</span> is not
+<a href="#dfn-transitive" class="internalDFN">transitive</a>. Indeed, consider the following statements.</p>
+<pre class="codeexample">wasInformedBy(a2,a1)
+wasInformedBy(a3,a2)
+</pre>
+<p> We cannot infer <span class="name">wasInformedBy(a3,a1)</span> from these statements. Indeed,
+from
+<span class="name">wasInformedBy(a2,a1)</span>, we know that there exists <span class="name">e1</span> such that <span class="name">e1</span> was generated by <span class="name">a1</span>
+and used by <span class="name">a2</span>. Likewise, from <span class="name">wasInformedBy(a3,a2)</span>, we know that there exists <span class="name">e2</span> such that <span class="name">e2</span> was generated by <span class="name">a2</span>
+and used by <span class="name">a3</span>. The following illustration
+shows a counterexample to transitivity. The
+horizontal axis represents the event line. We see that <span class="name">e1</span> was generated after <span class="name">e2</span> was used. Furthermore, the illustration also shows that
+<span class="name">a3</span> completes before <span class="name">a1</span>. So it is impossible for <span class="name">a3</span> to have used an entity generated by <span class="name">a1</span>. This is illustrated in <a href="#counterexample-wasInformedBy">Figure 1</a>.</p>
+
+<div style="text-align: center;">
+<span class="figure">
+<img src="images/constraints/informedByNonTransitive.png" alt="non transitivity of wasInformedBy">
+<br>
+<span class="figcaption" id="counterexample-wasInformedBy">Figure 1<sup><a class="internalDFN" href="#counterexample-wasInformedBy"><span class="diamond"> ◊:</span></a></sup> Counter-example for transitivity of wasInformedBy</span>
+</span>
+</div>
+</div>
+
+
+
+<hr>
+
+
+
+<p id="entity-generation-invalidation-inference_text">
+From an entity, we can infer <span class="delete">that</span><span class="insert">the</span> existence of
+generation and invalidation events.
+</p>
+<div class="inference" id="entity-generation-invalidation-inference"><div class="ruleTitle"><a class="internalDFN" href="#entity-generation-invalidation-inference">Inference 7 (entity-generation-invalidation-inference)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">entity(e,_attrs)</span> <span class="conditional">THEN</span> there exist
+<span class="name">_id1</span>, <span class="name">_a1</span>, <span class="name">_t1</span>,
+<span class="name">_id2</span>, <span class="name">_a2</span>, and <span class="name">_t2</span> such that
+ <span class="name"><span class="delete">wasGeneratedBy(_id1;e,_a1,_t1,[])</span><span class="delete"> and </span><span class="delete">wasInvalidatedBy(_id2;e,_a2,_t2,[])</span><span class="insert">wasGeneratedBy(_id1; e,_a1,_t1,[])</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasInvalidatedBy(_id2; e,_a2,_t2,[])</span></span>.
+</p></div>
+
+
+<hr>
+
+
+<p id="activity-start-end-inference_text">
+From an activity <span class="delete">statemen,t</span><span class="insert">statement,</span> we can infer<span class="delete"> that</span>
+start and end events <span class="delete">having</span><span class="insert">whose</span> times <span class="delete">matching</span><span class="insert">match</span> the start and end times of
+the <span class="delete">activity.</span><span class="insert">activity, respectively.</span>
+</p>
+<div class="inference" id="activity-start-end-inference"><div class="ruleTitle"><a class="internalDFN" href="#activity-start-end-inference">Inference 8 (activity-start-end-inference)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">activity(a,t1,t2,_attrs)</span> <span class="conditional">THEN</span> there exist <span class="name">_id1</span>, <span class="name">_e1</span>, <span class="name">_id2</span>,
+ and <span class="name">_e2</span> such that
+ <span class="name"><span class="delete">wasStartedBy(_id1;a,_e1,_a1,t1,[])</span><span class="delete"> and </span><span class="delete">wasEndedBy(_id2;a,_e2,_a2,t2,[])</span><span class="insert">wasStartedBy(_id1; a,_e1,_a1,t1,[])</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasEndedBy(_id2; a,_e2,_a2,t2,[])</span></span>.
+</p></div>
+
+
+<hr>
+
+
+<p id="wasStartedBy-inference_text"><span class="delete">Start</span><span class="insert">The start</span> of <span class="insert">an activity </span><span class="name">a</span> <span class="insert">triggered </span>by <span class="delete">trigger</span><span class="insert">entity</span> <span class="name">e1</span><span class="delete"> and starter activity </span><span class="delete">a1</span>
+implies that
+<span class="name">e1</span> was generated by<span class="insert"> the starting activity</span> <span class="name">a1</span>.</p>
+
+<div class="inference" id="wasStartedBy-inference"><div class="ruleTitle"><a class="internalDFN" href="#wasStartedBy-inference">Inference 9 (wasStartedBy-inference)</a></div>
+<p><span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasStartedBy(_id;a,e1,a1,_t,_attrs)</span><span class="insert">wasStartedBy(_id; a,e1,a1,_t,_attrs)</span></span>,
+<span class="conditional">THEN</span> there exist <span class="name">_gen</span> and <span class="name">_t1</span>
+such that
+ <span class="name"><span class="delete">wasGeneratedBy(_gen;e1,a1,_t1,[])</span><span class="insert">wasGeneratedBy(_gen; e1,a1,_t1,[])</span></span>.</p>
+</div>
+<p>
+
+</p><hr>
+
+<p id="wasEndedBy-inference_text">Likewise,
+<span class="delete">end</span><span class="insert">the ending</span> of <span class="insert">activity </span><span class="name">a</span> by <span class="delete">trigger</span><span class="insert">triggering entity</span> <span class="name">e1<span class="delete"> and ender activity </span><span class="delete">a1</span></span> implies that
+<span class="name">e1</span> was generated by<span class="insert"> the ending activity</span> <span class="name">a1</span>.
+</p>
+
+<div class="inference" id="wasEndedBy-inference"><div class="ruleTitle"><a class="internalDFN" href="#wasEndedBy-inference">Inference 10 (wasEndedBy-inference)</a></div>
+<p><span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasEndedBy(_id;a,e1,a1,_t,_attrs)</span><span class="insert">wasEndedBy(_id; a,e1,a1,_t,_attrs)</span></span>,
+<span class="conditional">THEN</span> there exist <span class="name">_gen</span> and <span class="name">_t1</span> such that
+ <span class="name"><span class="delete">wasGeneratedBy(_gen;e1,a1,_t1,[])</span><span class="insert">wasGeneratedBy(_gen; e1,a1,_t1,[])</span></span>.</p>
+</div>
+
+
+
+
+</div>
+
+ <div id="derivations" class="section">
+<h3><span class="secno">4.3 </span>Derivations</h3>
+
+
+<hr>
+<p id="derivation-generation-use-inference_text">Derivations with explicit
+activity, generation, and usage admit the following inference: </p>
+
+<div class="inference" id="derivation-generation-use-inference"><div class="ruleTitle"><a class="internalDFN" href="#derivation-generation-use-inference">Inference 11 <span class="delete">(derivation-generation-use)</span><span class="insert">(derivation-generation-use-inference)</span></a></div>
+<p>
+
+</p><p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasDerivedFrom(_id;e2,e1,a,id2,id1,_attrs)</span><span class="insert">wasDerivedFrom(_id; e2,e1,a,gen2,use1,_attrs)</span></span>,
+ <span class="conditional">THEN</span> there exists <span class="name">_t1</span> and <span class="name">_t2</span> such that <span class="name"><span class="delete">used(id1;a,e1,_t1,[])</span><span class="delete"> and </span><span class="delete">wasGeneratedBy(id2;e2,a,_t2,[])</span><span class="delete"> hold.</span><span class="insert">used(use1; a,e1,_t1,[])</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasGeneratedBy(gen2; e2,a,_t2,[])</span></span><span class="insert">.</span>
+</p>
+</div>
+<p>
+</p><hr>
+
+<span class="delete">Derivations</span><p id="derivation-use-inference_text"><span class="insert">According to </span><a class="rule-text" href="#optional-placeholders_text"><span><span class="insert">Definition 4 (optional-placeholders)</span></span></a><span class="insert">, optional generation and usage in a derivation are not expandable. However, derivations</span> with an explicit activity and
+no specified generation and usage admit the following inference: </p>
+<span class="delete">Final check required. The following inference
+ appears redundant (it can be derived using other rules).
+ </span>
+
+
+<div class="inference" id="derivation-use-inference"><div class="ruleTitle"><a class="internalDFN" href="#derivation-use-inference">Inference 12 <span class="delete">(derivation-use)</span><span class="insert">(derivation-use-inference)</span></a></div>
+<p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasDerivedFrom(id;e2,e1,a,-,-,attrs)</span><span class="delete"> and </span><span class="delete">wasGeneratedBy(gen;e2,a,_t2,_attrs2)</span><span class="insert">wasDerivedFrom(id; e2,e1,a,-,-,attrs)</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasGeneratedBy(gen; e2,a,_t2,_attrs2)</span></span> hold, <span class="conditional">THEN</span> there exist <span class="name">_t1</span> and <span class="name">use</span> such
+ that <span class="name"><span class="delete">used(use;a,e1,_t1,[])</span><span class="delete"> and </span><span class="delete">wasDerivedFrom(id;e2,e1,a,gen,use,attrs)</span><span class="delete"> hold.</span><span class="insert">used(use; a,e1,_t1,[])</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasDerivedFrom(id; e2,e1,a,gen,use,attrs)</span></span><span class="insert">.</span>
+</p></div>
+<p>This inference is justified by the fact that the entity denoted by <span class="name">e2</span> is generated by at most one activity
+(see <a class="rule-text" href="#unique-generation_text"><span>Constraint 27 (unique-generation)</span></a>). Hence, this activity is also the one referred to by the usage of <span class="name">e1</span>.
+</p>
+
+
+<div class="remark" id="derivation-generation-use-inference-remark">
+ <p><span class="delete">The converse inference does</span>
+ <a class="rule-text" href="#derivation-use-inference_text"><span><span class="insert">Inference 12 (derivation-use-inference)</span></span></a><span class="insert"> allows "-" to be replaced by existential variables in a </span><span class="name"><span class="insert">wasDerivedFrom</span></span><span class="insert">, when an activity is explict, and a generation known.</span></p>
+
+<p><span class="insert"> However, a derivation without explicit generation and usage cannot be normalized even when a generation and usage hold.
+</span><span class="conditional"><span class="insert">IF</span></span>
+<span class="name"><span class="insert">wasDerivedFrom(id; e2,e1,a,-,-,attrs)</span></span><span class="insert">,
+</span><span class="name"><span class="insert">wasGeneratedBy(gen; e2,a,_t2,_attrs2)</span></span><span class="insert">,
+and </span><span class="name"><span class="insert">used(use; a,e1,_t1,[])</span></span><span class="insert">, </span><span class="conditional"><span class="insert">IT IS NOT NECESSARILY THE CASE THAT</span></span>
+<span class="name"><span class="insert">wasDerivedFrom(id; e2,e1,a,gen,use,attrs)</span></span><span class="insert">.
+Indeed,
+</span><span class="name"><span class="insert">e1</span></span><span class="insert"> may be used multiple times by
+ </span><span class="name"><span class="insert">a</span></span><span class="insert">, usage </span><span class="name"><span class="insert">use</span></span><span class="insert">
+may</span> not <span class="delete">hold.</span><span class="insert">be involved in the derivation</span> <span class="delete">Informally, from </span><span class="delete">wasDerivedFrom(id;e2,e1,-,-,-,attrs)</span><span class="delete"> and </span><span class="delete">used(use;a,e1,_t1,attrs1)</span><span class="delete">, one cannot derive </span><span class="delete">wasGeneratedBy(gen;e2,a,_t2,attrs2)</span><span class="delete"> because entity </span><span class="delete">e1</span><span class="insert">(for instance, it</span> may <span class="insert">well have taken place after
+the generation of </span><span expanclass="name"><span class="insert">e2</span></span><span class="insert">).</span></p>
+
+
+<p><span class="insert">Derivation is not defined to </span>be<span class="delete"> used by many activities, whereas at most
+one activity could generate the entity </span><span class="delete">e2</span><span class="delete">.
+Even if </span><span class="delete">e2</span><span class="delete"> is used by some activity</span><span class="insert">
+transitive either. Applications may define specializations of this relation</span> that<span class="delete">
+later generates </span><span class="delete">e1</span><span class="delete"> is generated, it is not
+safe to assume that </span><span class="delete">e2</span><span class="delete"> was derived from
+</span><span class="delete">e1</span><span class="delete">. Derivation is not defined to be
+transitive either, following similar reasoning as for </span><span class="delete">wasInformedBy</span><span class="delete">.</span><span class="insert"> are transitive.</span> </p>
+
+
+ </div>
+
+<hr>
+<p id="specific-derivation-inference_text">A derivation
+ specifying activity, generation and use events is a special case of
+ a derivation that leaves these unspecified. (The converse is not
+ the case).</p>
+
+<div class="inference" id="specific-derivation-inference"><div class="ruleTitle"><a class="internalDFN" href="#specific-derivation-inference">Inference 13 (specific-derivation-inference)</a></div>
+<p><span class="conditional">IF</span> <span class="name"><span class="delete">wasDerivedFrom(id;e2,e1,_act,_gen,_use,attrs)</span><span class="delete">
+ holds, </span><span class="insert">wasDerivedFrom(id; e2,e1,_act,_gen,_use,attrs)</span></span><span class="insert">,
+</span><span class="conditional">THEN</span> <span class="name"><span class="delete">wasDerivedFrom(id;e2,e1,-,-,-,attrs)</span><span class="delete"> holds.</span><span class="insert">wasDerivedFrom(id; e2,e1,-,-,-,attrs)</span></span><span class="insert">.</span>
+</p>
+</div>
+
+
+<hr>
+<p id="revision-is-alternate-inference_text">A revision admits the following inference, stating that the two entities
+linked by a revision are also alternates.</p>
+
+<div class="inference" id="revision-is-alternate-inference"><div class="ruleTitle"><a class="internalDFN" href="#revision-is-alternate-inference">Inference 14 <span class="delete">(revision-is-alternate)</span><span class="insert">(revision-is-alternate-inference)</span></a></div>
+<p>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasDerivedFrom(_id;e2,e1,[prov:type='prov:Revision'])</span><span class="insert">wasDerivedFrom(_id; e2,e1,[prov:type='prov:Revision'])</span></span>
+ holds, <span class="conditional">THEN</span> <span class="name">alternateOf(e2,e1)</span> holds.
+</p>
+
+</div>
+
+
+
+</div>
+
+
+<div id="agents" class="section">
+<h3><span class="secno">4.4 </span>Agents</h3>
+
+<p id="attribution-inference_text"> Attribution identifies an agent as responsible for an entity. An
+agent can only be responsible for an entity if it was associated with
+an activity that generated the entity. If the activity, generation
+and association events are not explicit in the instance, they can
+be inferred.</p>
+
+<div class="inference" id="attribution-inference"><div class="ruleTitle"><a class="internalDFN" href="#attribution-inference">Inference 15 (attribution-inference)</a></div>
+<p>
+<span class="conditional">IF</span>
+<span class="name"><span class="delete">wasAttributedTo(_att;e,ag,_attrs)</span><span class="insert">wasAttributedTo(_att; e,ag,_attrs)</span></span> holds for some identifiers
+<span class="name">e</span> and <span class="name">ag</span>,
+<span class="conditional">THEN</span> there exist
+ <span class="name">a</span>,
+ <span class="name">_t</span>,
+<span class="name">_gen</span>,
+<span class="name">_assoc</span>,
+ <span class="name">_pl</span>,
+such that
+<span class="name"><span class="delete">wasGeneratedBy(_gen;e,a,_t,[])</span><span class="insert">wasGeneratedBy(_gen; e,a,_t,[])</span></span> and
+<span class="name"><span class="delete">wasAssociatedWith(_assoc;a,ag,_pl,[])</span><span class="insert">wasAssociatedWith(_assoc; a,ag,_pl,[])</span></span> hold.
+</p>
+</div>
+<hr>
+<p id="delegation-inference_text"> Delegation relates agents where one agent acts on behalf of
+another, in the context of some activity. The supervising agent
+delegates some responsibility for part of the activity to the
+subordinate agent, while retaining some responsibility for the overall
+activity. Both agents are associated with this activity.</p>
+
+
+<div class="inference" id="delegation-inference"><div class="ruleTitle"><a class="internalDFN" href="#delegation-inference">Inference 16 (delegation-inference)</a></div>
+<p>
+<span class="conditional">IF</span>
+<span class="name"><span class="delete">actedOnBehalfOf(_id;ag1,</span><span class="insert">actedOnBehalfOf(_id; ag1,</span> ag2, a, _attrs)</span>
+<span class="conditional">THEN</span> there exist <span class="name">_id1</span>, <span class="name">_pl1</span>, <span class="name">_id2</span>, and <span class="name">_pl2</span> such that <span class="name"><span class="delete">wasAssociatedWith(_id1;a,</span><span class="insert">wasAssociatedWith(_id1; a,</span> ag1, _pl1, [])</span>
+ and <span class="name"><span class="delete">wasAssociatedWith(_id2;a,</span><span class="insert">wasAssociatedWith(_id2; a,</span> ag2, _pl2, [])</span>.
+</p>
+</div>
+
+
+<div class="remark">
+ Note that the two associations between the agents and the activity
+ may have different identifiers, different plans, and different
+ attributes. In particular, the plans of the two agents need not be
+ the same, and one, both, or neither can be the placeholder <span class="name">-</span>
+ indicating that there is no plan, because the existential variables
+ <span class="name">_pl1</span> and <span class="name">_pl2</span> can be replaced with constant identifiers or
+ placeholders <span class="name">-</span> independently.
+ </div>
+
+<hr>
+<p id="influence-inference_text">
+The <span class="name">wasInfluencedBy</span> relation is implied by other relations, including
+usage, start, end, generation, invalidation, communication,
+derivation, attribution, association, and delegation. To capture this
+explicitly, we allow the following inferences:
+</p>
+<div class="inference" id="influence-inference"><div class="ruleTitle"><a class="internalDFN" href="#influence-inference">Inference 17 (influence-inference)</a></div>
+<p>
+ </p><ol>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasGeneratedBy(id;e,a,t,attrs)</span><span class="insert">wasGeneratedBy(id; e,a,t,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; e, a, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">used(id;a,e,t,attrs)</span><span class="insert">used(id; a,e,t,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; a, e, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasInformedBy(id;a2,a1,attrs)</span><span class="insert">wasInformedBy(id; a2,a1,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; a2, a1, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasStartedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasStartedBy(id; a2,e,a1,t,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; a2, e, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasEndedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasEndedBy(id; a2,e,a1,t,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; a2, e, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasInvalidatedBy(id;e,a,t,attrs)</span><span class="insert">wasInvalidatedBy(id; e,a,t,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; e, a, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name">wasDerivedFrom(id; e2, e1, attrs)</span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; e2, e1, attrs)</span>.
+ </li>
+
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasAttributedTo(id;e,ag,attr)</span><span class="insert">wasAttributedTo(id; e,ag,attr)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; e, ag, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">wasAssociatedWith(id;a,ag,pl,attrs)</span><span class="insert">wasAssociatedWith(id; a,ag,pl,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; a, ag, attrs)</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">actedOnBehalfOf(id;ag2,ag1,a,attrs)</span><span class="insert">actedOnBehalfOf(id; ag2,ag1,a,attrs)</span></span> <span class="conditional">THEN</span> <span class="name">wasInfluencedBy(id; ag2, ag1, attrs)</span>.
+ </li>
+</ol>
+</div>
+
+<div class="remark">
+ Note that the inferences above use the same identifier for the more
+ specific relationship and the influence relationship.
+</div>
+
+</div>
+
+
+
+ <div id="alternate-and-specialized-entities" class="section">
+<h3><span class="secno">4.5 </span>Alternate and Specialized Entities</h3>
+
+
+
+
+<hr>
+ <p id="alternate-reflexive_text">The relation <span class="name">alternateOf</span> is an <a href="#dfn-equivalence-relation" class="internalDFN">equivalence <span class="delete">relation:</span><span class="insert">relation</span></a><span class="insert">: that is,
+ it is</span> <a href="#dfn-reflexive" class="internalDFN">reflexive</a>,
+ <a href="#dfn-transitive" class="internalDFN">transitive</a> and <a href="#dfn-symmetric" class="internalDFN">symmetric</a>.<span class="insert"> As a consequence, the
+ following inferences can be applied:</span></p>
+
+
+
+
+<div class="inference" id="alternate-reflexive"><div class="ruleTitle"><a class="internalDFN" href="#alternate-reflexive">Inference 18 (alternate-reflexive)</a></div>
+<p><span class="delete">
+ For any entity </span><span class="delete">e</span><span class="delete">, we have </span>
+<span class="conditional"><span class="insert">IF</span></span> <span class="name"><span class="insert">entity(e)</span></span> <span class="conditional"><span class="insert">THEN</span></span>
+<span class="name">alternateOf(e,e)</span>.
+</p>
+ </div>
+
+<p>
+
+</p><hr>
+ <p id="alternate-transitive_text">
+
+ </p><div class="inference" id="alternate-transitive"><div class="ruleTitle"><a class="internalDFN" href="#alternate-transitive">Inference 19 (alternate-transitive)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">alternateOf(e1,e2)</span> and
+ <span class="name">alternateOf(e2,e3)</span> <span class="conditional">THEN</span> <span class="name">alternateOf(e1,e3)</span>.</p>
+ </div>
+
+<p>
+
+</p><hr>
+ <p id="alternate-symmetric_text">
+
+ </p><div class="inference" id="alternate-symmetric"><div class="ruleTitle"><a class="internalDFN" href="#alternate-symmetric">Inference 20 (alternate-symmetric)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">alternateOf(e1,e2)</span> <span class="conditional">THEN</span> <span class="name">alternateOf(e2,e1)</span>.</p>
+ </div>
+
+<p>
+
+
+</p><hr>
+<p id="specialization-transitive_text">
+Similarly, specialization is a
+ <a href="#dfn-strict-partial-order" class="internalDFN">strict partial order</a>: it is <a href="#dfn-irreflexive" class="internalDFN">irreflexive</a> and
+ <a href="#dfn-transitive" class="internalDFN">transitive</a>. Irreflexivity is handled later as <span class="delete">a
+ constraint.</span><a class="rule-ref" href="#impossible-specialization-reflexive"><span><span class="insert">Constraint 50 (impossible-specialization-reflexive)</span></span></a>
+ </p>
+ <div class="inference" id="specialization-transitive"><div class="ruleTitle"><a class="internalDFN" href="#specialization-transitive">Inference 21 (specialization-transitive)</a></div>
+<p>
+
+<span class="conditional">IF</span> <span class="name">specializationOf(e1,e2)</span>
+ and
+ <span class="name">specializationOf(e2,e3)</span> <span class="conditional">THEN</span> <span class="name">specializationOf(e1,e3)</span>.</p>
+ </div>
+
+<p>
+
+</p><hr>
+
+ <p id="specialization-alternate-inference_text">If one entity specializes another, then they are also
+ alternates:</p>
+
+ <div class="inference" id="specialization-alternate-inference"><div class="ruleTitle"><a class="internalDFN" href="#specialization-alternate-inference">Inference 22 <span class="delete">(specialization-alternate)</span><span class="insert">(specialization-alternate-inference)</span></a></div>
+<p>
+
+<span class="conditional">IF</span> <span class="name">specializationOf(e1,e2)</span> <span class="conditional">THEN</span> <span class="name">alternateOf(e1,e2)</span>.</p>
+ </div>
+
+<hr>
+<p id="specialization-attributes-inference_text">
+ If one entity specializes another then all attributes of the more
+ general entity are also attributes of the more specific one.
+ </p>
+<div class="inference" id="specialization-attributes-inference"><div class="ruleTitle"><a class="internalDFN" href="#specialization-attributes-inference">Inference 23 <span class="delete">(specialization-attributes)</span><span class="insert">(specialization-attributes-inference)</span></a></div>
+ <p>
+
+<span class="conditional">IF</span> <span class="name">entity(e1, attrs)</span> holds for some
+ attributes <span class="name">attrs</span> and <span class="name">specializationOf(e2,e1)</span> holds, <span class="conditional">THEN </span>
+ <span class="name">entity(e2, attrs)</span> also holds.</p>
+ </div>
+
+
+
+ <hr>
+
+ <div class="note">
+<p>Note: The following inference is associated with a feature "<a href="http://www.w3.org/2005/10/Process-20051014/tr#cfi">at risk</a>" and may be removed from this specification based on feedback. Please send feedback to public-prov-comments@w3.org.</p>
+</div>
+
+
+ <p id="mention-specialization-inference_text">If one entity is a mention of another in a bundle, then the former is also a specialization of the latter:</p>
+
+ <div class="inference" id="mention-specialization-inference"><div class="ruleTitle"><a class="internalDFN" href="#mention-specialization-inference">Inference 24 <span class="delete">(mention-specialization)</span><span class="insert">(mention-specialization-inference)</span></a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">mentionOf(e2,e1,b)</span> <span class="conditional">THEN</span> <span class="name">specializationOf(e2,e1)</span>.</p>
+ </div>
+
+
+</div>
+
+
+
+
+
+</div>
+
+
+
+<div id="constraints" class="section">
+<h2><span class="secno">5. </span>Constraints</h2>
+
+
+
+
+<p>
+This section defines a collection of constraints on PROV instances.
+There are three kinds of constraints:
+ </p><ul><li><em>uniqueness constraints</em> that say that a <a>PROV
+ instance</a> can contain at most one statement of each kind with a
+ given identifier. For
+ example, if we describe the same generation event twice, then the
+ two statements should have the same times;
+ </li>
+ <li> <em>event ordering constraints</em> that say that it
+ should be possible to arrange the
+ events (generation, usage, invalidation, start, end) described in a
+ PROV instance into a preorder that corresponds to a sensible
+ "history" (for example, an entity should not be generated after it
+ is used); and
+ </li>
+ <li><em>impossibility constraints</em>, which forbid certain
+ patterns of statements in <a href="#dfn-valid" class="internalDFN">valid</a> PROV instances.
+ </li></ul>
+
+ <div id="uniqueness-constraints" class="section">
+
+
+
+ <h3><span class="secno">5.1 </span>Uniqueness Constraints</h3>
+
+
+
+ <p> In the absence of existential variables, uniqueness constraints
+ could be checked directly by checking that no identifier appears
+ more than once for a given statement. However, in the presence of
+ existential variables, we need to be more careful to combine
+ partial information that might be present in multiple compatible
+ statements, due to inferences. Uniqueness constraints are
+ enforced through <a>merging</a> pairs of statements subject to
+ equalities. For example, suppose we have two activity statements
+ <span class="name"><span class="delete">activity(a,2011-11-16T16:00:00,t1,[a=1])</span><span class="delete"> and </span><span class="delete">activity(a,t2,2011-11-16T18:00:00,[b=2])</span><span class="insert">activity(a,2011-11-16T16:00:00,_t1,[a=1])</span></span><span class="insert"> and </span><span class="name"><span class="insert">activity(a,_t2,2011-11-16T18:00:00,[b=2])</span></span><span class="insert">, with existential variables </span><span class="name"><span class="insert">_t1</span></span><span class="insert"> and </span><span class="name"><span class="insert">_t2</span></span>. The <a>merge</a> of
+ these two statements (describing the same activity <span class="name">a</span>) is <span class="name">activity(a,2011-11-16T16:00:00,2011-11-16T18:00:00,[a=1,b=2])</span>. </p>
+
+ <p> Merging can be applied
+ to a pair of terms, or a pair of attribute lists.
+ The result of merging is either a substitution (mapping
+ existentially quantified variables to terms) or a special symbol
+ <span class="name">undefined</span> indicating that the merge
+ cannot be performed. Merging of pairs of terms, attribute lists,
+ or statements is defined as follows.</p>
+
+ <ul>
+ <li> If <span class="name">t</span> and <span class="name">t'</span> are concrete identifiers or values
+ (including the placeholder <span class="name">-</span>), then
+ their <a>merge</a> exists only if they are equal, otherwise merging
+ is undefined. </li>
+ <li> If <span class="name">x</span> is an existential variable
+ and
+ <span class="name">t'</span> is any term (identifier, constant,
+ placeholder <span class="name">-</span>, or
+ existential variable), then their
+ <a>merge</a> is <span class="name">t'</span>, and the resulting substitution is
+ <span class="name">[x=t']</span>. In the special case where <span class="name">t'=x</span>, the merge is
+ <span class="name">x</span> and the resulting substitution is empty.</li>
+ <li> If <span class="name">t</span> is any term (identifier, constant,
+ placeholder <span class="name">-</span>, or
+ existential variable) and
+ <span class="name">x'</span> is an existential variable, then their
+ merge is the same as the merge of <span class="name">x</span> and <span class="name">t</span>.</li>
+ <li> The <a>merge</a> of two attribute lists <span class="name">attrs1</span> and <span class="name">attrs2</span>
+ is their union, considered as unordered lists, written <span class="name">attrs1 ∪ attrs2</span>. </li>
+</ul>
+
+
+<div class="remark">Merging for terms is analogous to unification in
+ logic programming and theorem proving, restricted to flat terms with
+ no function symbols. No occurs check is needed because there are no
+ function symbols.</div>
+
+ <p>
+A typical uniqueness constraint is as follows:
+ </p>
+ <div class="constraint-example" id="uniqueness-example"><div class="ruleTitle"><a class="internalDFN" href="#uniqueness-example">Constraint-example NNN (uniqueness-example)</a></div>
+<p> <span class="conditional">IF</span> <span class="name">hyp<sub>1</sub></span> and ... and <span class="name">hyp<sub>n</sub></span> <span class="conditional">THEN</span> <span class="name">t<sub>1</sub></span> = <span class="name">u<sub>1</sub></span> and ... and <span class="name">t<sub>n</sub></span> = <span class="name">u<sub>n</sub></span>.</p>
+ </div>
+
+ <p> Such a constraint is enforced as follows:</p>
+ <ol> <li>Suppose PROV instance <span class="math">I</span> contains all of the hypotheses
+ <span class="name">hyp<sub>1</sub></span> and ... and <span class="name">hyp<sub>n</sub></span>.
+ </li>
+ <li>Attempt to merge all of the equated terms in the conclusion
+ <span class="name">t<sub>1</sub></span> = <span class="name">u<sub>1</sub></span> and ... and <span class="name">t<sub>n</sub></span> = <span class="name">u<sub>n</sub></span>.
+ </li>
+ <li>If merging fails, then the constraint
+ is unsatisfiable, so application of the constraint to <span class="math">I</span>
+ fails.<span class="insert"> If this failure occurs during </span><a><span class="insert">normalization</span></a><span class="insert"> prior to
+validation, then </span><span class="math"><span class="insert">I</span></span><span class="insert"> is invalid, as explained in </span><a href="#normalization-validity-equivalence"><span class="insert">Section 6</span></a><span class="insert">.
+ </span></li>
+ <li>If merging succeeds with a substitution <span class="math">S</span>, then
+ <span class="math">S</span> is applied to the instance <span class="math">I</span>, yielding result <span class="math">I(S)</span>.</li>
+ </ol>
+
+<p> In the common case that a particular field of a relation uniquely
+ determines the other fields, we call the uniqueness constraint a
+ <a>key constraint</a>. Key constraints are written as follows:
+ </p>
+
+ <div class="constraint-example" id="key-example"><div class="ruleTitle"><a class="internalDFN" href="#key-example">Constraint-example NNN (key-example)</a></div>
+ <p>The <span class="name">a<sub>k</sub></span> field is a <span class="conditional">KEY</span> for relation <span class="name">r(a<sub>0</sub><span class="delete">;a</span><span class="insert">; a</span><sub>1</sub>,...,a<sub>n</sub>)</span>. </p></div>
+
+ <p> Because of the presence of attributes, key constraints do not
+ reduce directly to uniqueness constraints. Instead, we enforce key
+ constraints as follows. </p>
+ <ol>
+ <li> Suppose <span class="name">r(a<sub>0</sub><span class="delete">;a</span><span class="insert">; a</span><sub>1</sub>,...a<sub>n</sub>,attrs1)</span> and <span class="name">r(b<sub>0</sub><span class="delete">;b</span><span class="insert">; b</span><sub>1</sub>,...b<sub>n</sub>,attrs2)</span> hold in PROV instance <span class="math">I</span>, where the key fields <span class="name">a<sub>k</sub> = b<sub>k</sub></span> are equal.</li>
+ <li> Attempt to merge all of the corresponding parameters <span class="name">a<sub>0</sub> = b<sub>0</sub> </span> and ... and <span class="name">a<sub>n</sub> = b<sub>n</sub></span>.
+ </li>
+ <li>If merging fails, then the constraint is unsatisfiable, so
+ application of the key constraint to <span class="math">I</span> fails.
+ </li>
+ <li>If merging succeeds with substitution <span class="math">S</span>, then we remove <span class="name">r(a<sub>0</sub><span class="delete">;a</span><span class="insert">; a</span><sub>1</sub>,...a<sub>n</sub>,attrs1)</span> and <span class="name">r(b<sub>0</sub><span class="delete">;b</span><span class="insert">; b</span><sub>1</sub>,...b<sub>n</sub>,attrs2)</span> from <span class="math">I</span>, obtaining
+ instance <span class="math">I'</span>, and return instance <span class="name">{r(S(a<sub>0</sub><span class="delete">);S(a</span><span class="insert">); S(a</span><sub>1</sub>),...S(a<sub>n</sub>),attrs1 ∪
+ attrs2)}</span> ∪ <span class="math">S(I')</span>.
+ </li></ol>
+
+
+<p>Thus, if a PROV instance contains an apparent violation of a uniqueness
+ constraint or key constraint, merging can be used to determine
+ whether the constraint can be satisfied by instantiating some existential
+ variables with other terms. For key constraints, this is the same
+ as merging pairs of statements whose keys are equal and whose
+ coresponding arguments are compatible, because after
+ merging respective arguments and attribute lists, the two statements
+ become equal and one can be omitted. </p>
+
+
+
+
+
+
+<p>
+</p><hr>
+
+ <p id="key-object_text"> We assume that the various identified objects of PROV have
+ unique statements describing them within a PROV instance, through
+ the following key constraints:
+ </p>
+ <div class="constraint" id="key-object"><div class="ruleTitle"><a class="internalDFN" href="#key-object">Constraint 25 (key-object)</a></div>
+<p></p><ol>
+ <li>The identifier field <span class="name">e</span> is a <span class="conditional">KEY</span> for
+ the <span class="name">entity(e,attrs)</span> statement.
+ </li>
+ <li>The identifier field <span class="name">a</span> is a <span class="conditional">KEY</span> for
+ the <span class="name">activity(a,t1,t2,attrs)</span> statement.
+ </li>
+<li>The identifier field <span class="name">ag</span> is a <span class="conditional">KEY</span> for
+ the <span class="name">agent(ag,attrs)</span> statement.
+ </li>
+ </ol>
+ </div>
+
+ <hr>
+ <p id="key-properties_text"> Likewise, <span class="delete">we assume</span><span class="insert">the statements
+in a valid PROV instance must provide consistent information about
+ each identified object or relationship. The following key
+ constraints require</span> that <span class="delete">the identifiers</span><span class="insert">all of the information about each identified</span>
+ <span class="delete">of relationships in PROV uniquely identify the corresponding statements</span><span class="insert">statement can be merged into</span> a <span class="delete">PROV instance, through
+ the following key constraints:</span><span class="insert">single, consistent statement:</span>
+ </p>
+ <div class="constraint" id="key-properties"><div class="ruleTitle"><a class="internalDFN" href="#key-properties">Constraint 26 (key-properties)</a></div>
+<p></p><ol>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasGeneratedBy(id;e,a,t,attrs)</span><span class="insert">wasGeneratedBy(id; e,a,t,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">used(id;a,e,t,attrs)</span><span class="insert">used(id; a,e,t,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasInformedBy(id;a2,a1,attrs)</span><span class="insert">wasInformedBy(id; a2,a1,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasStartedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasStartedBy(id; a2,e,a1,t,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasEndedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasEndedBy(id; a2,e,a1,t,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasInvalidatedBy(id;e,a,t,attrs)</span><span class="insert">wasInvalidatedBy(id; e,a,t,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name">wasDerivedFrom(id; e2, e1, attrs)</span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name">wasDerivedFrom(id; e2, e1, a, g2, u1, attrs)</span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasAttributedTo(id;e,ag,attr)</span><span class="insert">wasAttributedTo(id; e,ag,attr)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasAssociatedWith(id;a,ag,pl,attrs)</span><span class="insert">wasAssociatedWith(id; a,ag,pl,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasAssociatedWith(id;a,ag,-,attrs)</span><span class="insert">wasAssociatedWith(id; a,ag,-,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">actedOnBehalfOf(id;ag2,ag1,a,attrs)</span><span class="insert">actedOnBehalfOf(id; ag2,ag1,a,attrs)</span></span> statement.
+ </li>
+ <li>The identifier field <span class="name">id</span> is a <span class="conditional">KEY</span> for
+ the <span class="name"><span class="delete">wasInfluencedBy(id;o2,o1,attrs)</span><span class="insert">wasInfluencedBy(id; o2,o1,attrs)</span></span> statement.
+ </li>
+</ol>
+ </div>
+
+
+
+<hr>
+
+
+<div id="unique-generation_text">
+<p>We assume that an entity has exactly one generation and
+invalidation event (either or both may, however, be left implicit).
+ Note that together with the key constraints above, this implies that
+ <span class="name">e</span> is also a key for generation and
+ invalidation statements.
+</p>
+</div>
+
+
+<div class="constraint" id="unique-generation"><div class="ruleTitle"><a class="internalDFN" href="#unique-generation">Constraint 27 (unique-generation)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasGeneratedBy(id1;e,_a1,_t1,_attrs1)</span><span class="delete"> and </span><span class="delete">wasGeneratedBy(id2;e,_a2,_t2,_attrs2)</span><span class="insert">wasGeneratedBy(id1; e,_a1,_t1,_attrs1)</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasGeneratedBy(id2; e,_a2,_t2,_attrs2)</span></span>,
+<span class="conditional">THEN</span> <span class="name">id1</span> = <span class="name">id2</span>.</p>
+</div>
+
+<hr>
+
+<div id="unique-invalidation_text">
+
+<div class="constraint" id="unique-invalidation"><div class="ruleTitle"><a class="internalDFN" href="#unique-invalidation">Constraint 28 (unique-invalidation)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasInvalidatedBy(id1;e,_a1,_t1,_attrs1)</span><span class="delete"> and </span><span class="delete">wasInvalidatedBy(id2;e,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(id1; e,_a1,_t1,_attrs1)</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasInvalidatedBy(id2; e,_a2,_t2,_attrs2)</span></span>,
+<span class="conditional">THEN</span> <span class="name">id1</span> = <span class="name">id2</span>.</p>
+</div>
+
+
+<p> It follows from the above constraints that the generation and
+invalidation times of
+an entity are unique, if specified.
+</p><p>
+
+
+
+</p><hr>
+<p id="unique-wasStartedBy_text">
+We assume that an activity has exactly one start and
+end event (either or both may, however, be left implicit). Again,
+together with above key constraints these constraints imply that the
+activity is a key for activity start and end statements.
+</p>
+
+<div class="constraint" id="unique-wasStartedBy"><div class="ruleTitle"><a class="internalDFN" href="#unique-wasStartedBy">Constraint 29 (unique-wasStartedBy)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasStartedBy(id1;a,_e1,_a1,_t1,_attrs1)</span><span class="delete"> and </span><span class="delete">wasStartedBy(id2;a,_e2,_a2,_t2,_attrs2)</span><span class="insert">wasStartedBy(id1; a,_e1,_a1,_t1,_attrs1)</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasStartedBy(id2; a,_e2,_a2,_t2,_attrs2)</span></span>, <span class="conditional">THEN</span> <span class="name"><span class="delete">id</span><span class="insert">id1</span></span> =<span class="delete">id'</span> <span class="name"><span class="insert">id2</span></span>.</p>
+</div>
+
+<hr>
+<p id="unique-wasEndedBy_text">
+
+</p><div class="constraint" id="unique-wasEndedBy"><div class="ruleTitle"><a class="internalDFN" href="#unique-wasEndedBy">Constraint 30 (unique-wasEndedBy)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">wasEndedBy(id1;a,_e1,_a1,_t1,_attrs1)</span><span class="delete"> and </span><span class="delete">wasEndedBy(id2;a,_e2,_a2,_t2,_attrs2)</span><span class="insert">wasEndedBy(id1; a,_e1,_a1,_t1,_attrs1)</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasEndedBy(id2; a,_e2,_a2,_t2,_attrs2)</span></span>, <span class="conditional">THEN</span> <span class="name"><span class="delete">id</span><span class="insert">id1</span></span> =<span class="delete">id'</span> <span class="name"><span class="insert">id2</span></span>.</p>
+</div>
+
+
+
+
+<p>
+
+
+
+ </p><p id="unique-startTime_text">An <a href="#dfn-start-event" class="internalDFN">activity start event</a> is the <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> that marks the instant an activity starts. It allows for an optional time attribute. <span id="optional-start-time">Activities also allow for an optional start time attribute. If both are specified, they <em class="rfc2119" title="must">must</em> be the same, as expressed by the following constraint.</span>
+</p>
+
+<div class="constraint" id="unique-startTime"><div class="ruleTitle"><a class="internalDFN" href="#unique-startTime">Constraint 31 (unique-startTime)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">activity(a,t,_t',_attrs)</span> and <span class="name"><span class="delete">wasStartedBy(id;a,_e1,_a1,t1,_attrs1)</span><span class="insert">wasStartedBy(id; a,_e1,_a1,t1,_attrs1)</span></span>, <span class="conditional">THEN</span> <span class="name">t</span>=<span class="name">t1</span>.</p>
+</div>
+
+<hr>
+
+<p id="unique-endTime_text">An <a href="#dfn-end-event" class="internalDFN">activity end event</a> is the <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> that marks the instant an activity ends. It allows for an optional time attribute. <span id="optional-end-time">Activities also allow for an optional end time attribute. If both are specified, they <em class="rfc2119" title="must">must</em> be the same, as expressed by the following constraint.</span>
+</p>
+
+<div class="constraint" id="unique-endTime"><div class="ruleTitle"><a class="internalDFN" href="#unique-endTime">Constraint 32 (unique-endTime)</a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">activity(a,_t,t',_attrs)</span> and <span class="name"><span class="delete">wasEndedBy(id;a,_e1,_a1,t1,_attrs1)</span><span class="insert">wasEndedBy(id; a,_e1,_a1,t1,_attrs1)</span></span>, <span class="conditional">THEN</span> <span class="name">t'</span> = <span class="name">t1</span>.</p>
+</div>
+
+<p>
+
+
+</p><hr>
+
+
+<div class="note">
+<p>Note: The following constraint is associated with a feature "<a href="http://www.w3.org/2005/10/Process-20051014/tr#cfi">at risk</a>" and may be removed from this specification based on feedback. Please send feedback to public-prov-comments@w3.org.</p>
+</div>
+
+
+<div id="unique-mention_text">
+<p>An entity can be the subject of at most one mention relation.</p>
+</div>
+
+
+<div class="constraint" id="unique-mention"><div class="ruleTitle"><a class="internalDFN" href="#unique-mention">Constraint 33 <span class="delete">(mention-unique)</span><span class="insert">(unique-mention)</span></a></div>
+<p>
+<span class="conditional">IF</span> <span class="name">mentionOf(e, e1, b1)</span> and <span class="name">mentionOf(e, e2, b2)</span>,
+<span class="conditional">THEN</span> <span class="name">e1</span>=<span class="name">e2</span> and <span class="name">b1</span>=<span class="name">b2</span>.</p>
+</div>
+
+
+
+
+
+
+</div></div>
+
+<div id="event-ordering-constraints" class="section">
+<h3><span class="secno">5.2 </span>Event Ordering Constraints</h3>
+
+
+<p>Given that provenance consists of a description of past entities
+and activities, <a href="#dfn-valid" class="internalDFN">valid</a> provenance instances <em class="rfc2119" title="must">must</em>
+satisfy <em>ordering constraints</em> between instantaneous events, which we introduce in
+this section. For instance, an entity can only be used after it was
+generated; hence, we say that an entity's <a title="entity generation
+event" href="#dfn-generation-event" class="internalDFN">generation event</a> precedes any of this
+entity's <a title="entity usage event" href="#dfn-usage-event" class="internalDFN">usage events</a>. Should this
+ordering constraint be violated, the associated generation and
+usage would not be credible. The rest of this section defines
+the <dfn id="dfn-temporal-interpretation">temporal interpretation</dfn> of provenance instances as a
+set of instantaneous event ordering constraints. </p>
+
+
+<p>To allow for minimalistic clock assumptions, like Lamport
+[<cite><a class="bibref" rel="biblioentry" href="#bib-CLOCK">CLOCK</a></cite>], PROV relies on a notion of relative ordering of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous events</a>,
+without using physical clocks. This specification assumes that a preorder exists between <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous events</a>.
+</p>
+
+
+<p>Specifically, <dfn id="dfn-precedes">precedes</dfn> is a <a href="#dfn-preorder" class="internalDFN">preorder</a>
+between <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous events</a>. When
+we say <span class="name">e1</span> precedes <span class="name">e2</span>, this means that <span class="name">e1</span>
+happened at the same time as or before <span class="name">e2</span>.
+For symmetry, <dfn id="dfn-follows">follows</dfn> is defined as the
+inverse of <a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>; that is, when we say
+<span class="name">e1</span> follows <span class="name">e2</span>,
+this means that <span class="name">e1</span> happened at the same time
+as or after <span class="name">e2</span>. Both relations are
+<a href="#dfn-preorder" class="internalDFN">preorder</a>s, meaning that they are <a href="#dfn-reflexive" class="internalDFN">reflexive</a> and
+<a href="#dfn-transitive" class="internalDFN">transitive</a>. Moreover, we sometimes consider <em>strict</em> forms of these
+orders: we say <span class="name">e1</span> strictly precedes <span class="name">e2</span> to indicate that <span class="name">e1</span>
+happened before <span class="name">e2</span>. This is a
+<a href="#dfn-transitive" class="internalDFN">transitive</a> relation. </p>
+
+
+<p>PROV also allows for time observations to be inserted in
+specific provenance statements, for each of the five kinds of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous events</a> introduced in
+this specification. Times in provenance records arising from
+different sources might be with respect to different timelines
+(e.g. different time zones) leading to apparent inconsistencies. For
+the purpose of checking ordering constraints, the times associated
+with events are irrelevant; thus, there is no inference that time ordering
+implies event ordering, or vice versa. However, an application <em class="rfc2119" title="may">may</em> flag time values
+that appear inconsistent with the event ordering as possible
+inconsistencies. When generating provenance, an application <em class="rfc2119" title="should">should</em>
+use a consistent timeline for related PROV statements within an
+instance.</p>
+
+
+<p> A typical ordering constraint is as follows.</p>
+
+ <div class="constraint-example" id="ordering-example"><div class="ruleTitle"><a class="internalDFN" href="#ordering-example">Constraint-example NNN (ordering-example)</a></div>
+ <p><span class="conditional">IF</span> <span class="name">hyp<sub>1</sub></span> and ... and <span class="name">hyp<sub>n</sub></span> <span class="conditional">THEN</span> <span class="name">evt1</span> <a href="#dfn-precedes" class="internalDFN">precedes</a>/<a title="precedes" href="#dfn-precedes" class="internalDFN">strictly precedes</a> <span class="name">evt2</span>. </p></div>
+ <p>
+ The conclusion of an ordering constraint is either <a href="#dfn-precedes" class="internalDFN">precedes</a>
+ or <a title="precedes" href="#dfn-precedes" class="internalDFN">strictly precedes</a>. To check ordering constraints, we
+ generate all <a href="#dfn-precedes" class="internalDFN">precedes</a> and <a title="precedes" href="#dfn-precedes" class="internalDFN">strictly
+ precedes</a>
+ relationships arising from the ordering constraints to form a directed graph, with edges marked <a href="#dfn-precedes" class="internalDFN">precedes</a> or
+ <a title="precedes" href="#dfn-precedes" class="internalDFN">strictly precedes</a>, and check that there is no cycle
+ containing a <a title="precedes" href="#dfn-precedes" class="internalDFN">strictly precedes</a> edge.
+ </p>
+
+
+
+
+
+<div id="activity-constraints" class="section">
+<h4><span class="secno">5.2.1 </span>Activity constraints</h4>
+
+<p>
+In this section we discuss constraints from the perspective of
+the <a href="#lifetime" class="internalDFN">lifetime</a> of an activity. An activity starts, then during
+its lifetime uses, generates or invalidates entities, and communicates with or starts
+other
+activities, and finally ends. The following constraints amount to
+checking that all of the events associated with an activity take place
+within the activity's lifetime, and the start and end events mark the
+start and endpoints of its lifetime.
+</p>
+
+<p><a href="#ordering-activity">Figure 2</a> summarizes the ordering
+ constraints on activities in a
+graphical manner. For this and subsequent figures, an event time line points to the
+right. Activities are represented by rectangles, whereas entities are
+represented by circles. Usage, generation and invalidation are
+represented by the corresponding edges between entities and
+activities. The five kinds of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous events</a> are represented by vertical
+dotted lines (adjacent to the vertical sides of an activity's
+rectangle, or intersecting usage and generation edges). The ordering
+constraints are represented by triangles: an occurrence of a triangle between two <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> vertical dotted lines represents that the event denoted by the left
+line precedes the event denoted by the right line.</p>
+ <div class="note"> Miscellanous suggestions about figures
+ (originally from Tim Lebo):
+<ul>
+ <li>
+ I think it would help if the "corresponding edges between entities and activities" where the same visual style as the vertical line marking the time the Usage, generation and derivation occurred. A matching visual style provides a Gestalt that matches the concept. I am looking at subfigures b and c in 5.2. </li></ul>
+ </div>
+
+ <div style="text-align: center;">
+
+<span class="figure" id="ordering-activity">
+<img src="images/constraints/ordering-activity.png" alt="constraints between events">
+<br>
+<span class="figcaption" id="ordering-activity-fig">Figure 2<sup><a class="internalDFN" href="#ordering-activity-fig"><span class="diamond"> ◊:</span></a></sup> Summary of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> ordering constraints for activities</span>
+</span>
+</div>
+
+
+<p>
+
+</p><hr>
+
+<p id="start-precedes-end_text">
+The existence of an activity implies that the <a href="#dfn-start-event" class="internalDFN">activity start
+event</a> always <a href="#dfn-precedes" class="internalDFN">precedes</a> the corresponding <a href="#dfn-end-event" class="internalDFN">activity end
+event</a>. This is illustrated by
+<a href="#ordering-activity">Figure 2</a>
+(a) and expressed by <a class="rule-ref" href="#start-precedes-end"><span>Constraint 34 (start-precedes-end)</span></a>.</p>
+
+<div class="constraint" id="start-precedes-end"><div class="ruleTitle"><a class="internalDFN" href="#start-precedes-end">Constraint 34 (start-precedes-end)</a></div>
+<p>
+<span class="conditional">IF</span>
+<span class="name"><span class="delete">wasStartedBy(start;a,_e1,_a1,_t1,_attrs1)</span><span class="insert">wasStartedBy(start; a,_e1,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasEndedBy(end;a,_e2,_a2,_t2,_attrs2)</span><span class="insert">wasEndedBy(end; a,_e2,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">start</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">end</span>.
+</p>
+</div>
+<p>
+</p><hr>
+
+<p id="usage-within-activity_text">A usage implies ordering of <a title="instantaneous event" href="#dfn-event" class="internalDFN">events</a>, since the <a title="entity usage event" href="#dfn-usage-event" class="internalDFN">usage event</a> had to occur during the associated activity. This is
+illustrated by <a href="#ordering-activity">Figure 2</a> (b) and expressed by <a class="rule-ref" href="#usage-within-activity"><span>Constraint 35 (usage-within-activity)</span></a>.</p>
+
+<div class="constraint" id="usage-within-activity"><div class="ruleTitle"><a class="internalDFN" href="#usage-within-activity">Constraint 35 (usage-within-activity)</a></div>
+<ol>
+ <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">used(use;a,e,_t,_attrs)</span><span class="insert">used(use; a,e,_t,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasStartedBy(start;a,_e1,_a1,_t1,_attrs1)</span><span class="insert">wasStartedBy(start; a,_e1,_a1,_t1,_attrs1)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">start</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">use</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">used(use;a,e,_t,_attrs)</span><span class="insert">used(use; a,e,_t,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasEndedBy(end;a,_e1,_a1,_t1,_attrs1)</span><span class="insert">wasEndedBy(end; a,_e2,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">use</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">end</span>.
+ </li>
+ </ol>
+</div>
+
+<p>
+
+</p><hr>
+
+
+<p id="generation-within-activity_text">A generation implies ordering of <a title="instantaneous event" href="#dfn-event" class="internalDFN">events</a>, since the <a title="entity generation event" href="#dfn-generation-event" class="internalDFN">generation event</a> had to occur during the associated activity. This is
+illustrated by <a href="#ordering-activity">Figure 2</a> (c) and expressed by <a class="rule-ref" href="#generation-within-activity"><span>Constraint 36 (generation-within-activity)</span></a>.</p>
+
+<div class="constraint" id="generation-within-activity"><div class="ruleTitle"><a class="internalDFN" href="#generation-within-activity">Constraint 36 (generation-within-activity)</a></div>
+ <ol>
+ <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasGeneratedBy(gen;_e,a,_t,_attrs)</span><span class="insert">wasGeneratedBy(gen; _e,a,_t,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasStartedBy(start;a,_e1,_a1,_t1,_attrs1)</span><span class="insert">wasStartedBy(start; a,_e1,_a1,_t1,_attrs1)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">start</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">gen</span>.
+ </li>
+ <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasGeneratedBy(gen;_e,a,_t,_attrs)</span><span class="insert">wasGeneratedBy(gen; _e,a,_t,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasEndedBy(end;a,_e1,_a1,_t1,_attrs1)</span><span class="insert">wasEndedBy(end; a,_e1,_a1,_t1,_attrs1)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">end</span>.
+ </li>
+ </ol>
+</div>
+
+<p>
+
+</p><hr>
+<p id="wasInformedBy-ordering_text">
+Communication between two activities <span class="name">a1</span>
+and <span class="name">a2</span> also implies ordering
+of <a title="instantaneous event" href="#dfn-event" class="internalDFN">events</a>, since some entity must
+have been generated by the former and used by the latter, which
+implies that the start event of <span class="name">a1</span> cannot
+follow the end event of <span class="name">a2</span>. This is
+illustrated by
+<a href="#ordering-activity">Figure 2</a>
+(d) and expressed by <a class="rule-ref" href="#wasInformedBy-ordering"><span>Constraint 37 (wasInformedBy-ordering)</span></a>.</p>
+
+<div class="constraint" id="wasInformedBy-ordering"><div class="ruleTitle"><a class="internalDFN" href="#wasInformedBy-ordering">Constraint 37 (wasInformedBy-ordering)</a></div>
+<p>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasInformedBy(_id;a2,a1,_attrs)</span><span class="insert">wasInformedBy(_id; a2,a1,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasStartedBy(start;a1,_e1,_a1',_t1,_attrs1)</span><span class="insert">wasStartedBy(start; a1,_e1,_a1',_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasEndedBy(end;a2,_e2,_a2',_t2,_attrs2)</span><span class="insert">wasEndedBy(end; a2,_e2,_a2',_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">start</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">end</span>.
+</p>
+</div>
+<p>
+
+
+
+</p></div>
+
+<div id="entity-constraints" class="section">
+<h4><span class="secno">5.2.2 </span> Entity constraints</h4>
+
+
+<div class="note">The figure(s) in this section should have vertical lines with visual styles that match the diagonal arrow that they go with. </div>
+
+<p>
+As with activities, entities have lifetimes: they are generated, then
+can be used, <span class="delete">revised, or </span>other entities can be derived from them, and
+ finally they<span class="delete"> may</span><span class="insert">
+can</span> be invalidated. The constraints on these events are
+illustrated graphically in <a href="#ordering-entity">Figure 3</a> and
+<a href="#ordering-entity-trigger">Figure 4</a>.
+</p>
+
+
+
+<div style="text-align: center;">
+<span class="figure" id="ordering-entity">
+<img src="images/constraints/ordering-entity.png" alt="ordering constraints for entities">
+<br>
+<span class="figcaption" id="ordering-entity-fig">Figure 3<sup><a class="internalDFN" href="#ordering-entity-fig"><span class="diamond"> ◊:</span></a></sup> Summary of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> ordering constraints for entities</span></span>
+</div>
+
+<p>
+
+</p><hr>
+
+<p id="generation-precedes-invalidation_text">
+Generation of an entity precedes its invalidation. (This
+follows from other constraints if the entity is used, but we state it
+explicitly to cover the case of an entity that is generated and
+invalidated without being used.)</p>
+
+<div class="constraint" id="generation-precedes-invalidation"><div class="ruleTitle"><a class="internalDFN" href="#generation-precedes-invalidation">Constraint 38 (generation-precedes-invalidation)</a></div>
+<p>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasGeneratedBy(gen;e,_a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(gen; e,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;e,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN"><span class="delete">strictly </span>precedes</a>
+<span class="name">inv</span>.
+</p>
+</div>
+
+<p>
+
+
+</p><hr>
+
+<p id="generation-precedes-usage_text">
+A usage and a generation for a given entity implies ordering of <a title="instantaneous event" href="#dfn-event" class="internalDFN">events</a>, since the <a title="entity generation
+event" href="#dfn-generation-event" class="internalDFN">generation event</a> had to precede the <a title="entity usage event" href="#dfn-usage-event" class="internalDFN">usage event</a>. This is
+illustrated by <a href="#ordering-entity">Figure 3</a>(a) and expressed by <a class="rule-ref" href="#generation-precedes-usage"><span>Constraint 39 (generation-precedes-usage)</span></a>.</p>
+
+<div class="constraint" id="generation-precedes-usage"><div class="ruleTitle"><a class="internalDFN" href="#generation-precedes-usage">Constraint 39 (generation-precedes-usage)</a></div>
+<p> <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasGeneratedBy(gen;e,_a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(gen; e,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">used(use;_a2,e,_t2,_attrs2)</span><span class="insert">used(use; _a2,e,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">use</span>.
+</p>
+</div>
+
+<p>
+</p><hr>
+
+<p id="usage-precedes-invalidation_text">All usages of an entity precede its invalidation, which is captured by <a class="rule-ref" href="#usage-precedes-invalidation"><span>Constraint 40 (usage-precedes-invalidation)</span></a> (without any explicit graphical representation).</p>
+
+<div class="constraint" id="usage-precedes-invalidation"><div class="ruleTitle"><a class="internalDFN" href="#usage-precedes-invalidation">Constraint 40 (usage-precedes-invalidation)</a></div>
+<p>
+<span class="conditional">IF</span>
+<span class="name"><span class="delete">used(use;_a1,e,_t1,_attrs1)</span><span class="insert">used(use; _a1,e,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;e,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">use</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">inv</span>.</p>
+</div>
+
+<p>
+
+</p><hr>
+
+
+
+
+<p id="derivation-usage-generation-ordering_text">If there is a
+derivation relationship linking <span class="name">e2</span> and <span class="name">e1</span>, then
+this means that the entity <span class="name">e1</span> had some influence on the entity <span class="name">e2</span>; for this to be possible, some event ordering must be satisfied.
+First, we consider derivations, where the activity and usage are known. In that case, the <a title="entity usage event" href="#dfn-usage-event" class="internalDFN">usage</a> of <span class="name">e1</span> has to precede the <a title="entity generation
+event" href="#dfn-generation-event" class="internalDFN">generation</a> of <span class="name">e2</span>.
+This is
+illustrated by <a href="#ordering-entity-fig">Figure 3</a> (b) and expressed by <a class="rule-ref" href="#derivation-usage-generation-ordering"><span>Constraint 41 (derivation-usage-generation-ordering)</span></a>.</p>
+
+
+<div class="constraint" id="derivation-usage-generation-ordering"><div class="ruleTitle"><a class="internalDFN" href="#derivation-usage-generation-ordering">Constraint 41 (derivation-usage-generation-ordering)</a></div>
+<p>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasDerivedFrom(_d;_e2,_e1,_a,gen2,use1,_attrs)</span><span class="insert">wasDerivedFrom(_d; _e2,_e1,_a,gen2,use1,_attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">use1</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">strictly precedes</a>
+<span class="name">gen2</span>.
+</p>
+</div>
+<p>
+</p><hr>
+
+<p id="derivation-generation-generation-ordering_text">
+When the activity, generation or usage is unknown, a similar constraint exists, except that the constraint refers to its
+generation event, as
+illustrated by <a href="#ordering-entity-fig">Figure 3</a> (c) and expressed by <a class="rule-ref" href="#derivation-generation-generation-ordering"><span>Constraint 42 (derivation-generation-generation-ordering)</span></a>.</p>
+
+<div class="constraint" id="derivation-generation-generation-ordering"><div class="ruleTitle"><a class="internalDFN" href="#derivation-generation-generation-ordering">Constraint 42 (derivation-generation-generation-ordering)</a></div>
+<p>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasDerivedFrom(_d;e2,e1,attrs)</span><span class="delete">
+ and
+</span><span class="delete">wasGeneratedBy(gen1;e1,_a1,_t1,_attrs1)</span><span class="delete">
+ and
+</span><span class="delete">wasGeneratedBy(gen2;e2,_a2,_t2,_attrs2)</span><span class="insert">wasDerivedFrom(_d; e2,e1,attrs)</span></span><span class="insert">
+ and
+</span><span class="name"><span class="insert">wasGeneratedBy(gen1; e1,_a1,_t1,_attrs1)</span></span><span class="insert">
+ and
+</span><span class="name"><span class="insert">wasGeneratedBy(gen2; e2,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen1</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">strictly precedes</a>
+<span class="name">gen2</span>.
+</p>
+ </div>
+
+<p>Note that event ordering is between generations of <span class="name">e1</span>
+and <span class="name">e2</span>, as opposed to derivation where usage is known,
+which implies ordering between the usage of <span class="name">e1</span> and
+generation of <span class="name">e2</span>. </p>
+
+<hr>
+
+<p id="wasStartedBy-ordering_text">
+The entity that triggered the start of an activity must exist before the activity starts.
+This is
+illustrated by <a href="#ordering-entity-trigger">Figure 4</a>(a) and expressed by <a class="rule-ref" href="#wasStartedBy-ordering"><span>Constraint 43 (wasStartedBy-ordering)</span></a>.</p>
+
+
+<div class="constraint" id="wasStartedBy-ordering"><div class="ruleTitle"><a class="internalDFN" href="#wasStartedBy-ordering">Constraint 43 (wasStartedBy-ordering)</a></div>
+ <ol>
+ <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasStartedBy(start;_a,e,_a1,_t1,_attrs1)</span><span class="insert">wasStartedBy(start; _a,e,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasGeneratedBy(gen;e,_a2,_t2,_attrs2)</span><span class="insert">wasGeneratedBy(gen; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">start</span>.
+ </li><li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasStartedBy(start;_a,e,_a1,_t1,_attrs1)</span><span class="insert">wasStartedBy(start; _a,e,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;e,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">start</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">inv</span>.
+ </li>
+ </ol>
+</div>
+<p>
+</p><hr>
+
+<p id="wasEndedBy-ordering_text"> Similarly, the entity that triggered
+the end of an activity must exist before the activity ends, as
+illustrated by
+<a href="#ordering-entity-trigger">Figure 4</a>(b).</p>
+
+
+<div class="constraint" id="wasEndedBy-ordering"><div class="ruleTitle"><a class="internalDFN" href="#wasEndedBy-ordering">Constraint 44 (wasEndedBy-ordering)</a></div>
+ <ol>
+ <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasEndedBy(end;_a,e,_a1,_t1,_attrs1)</span><span class="insert">wasEndedBy(end; _a,e,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasGeneratedBy(gen;e,_a2,_t2,_attrs2)</span><span class="insert">wasGeneratedBy(gen; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">end</span>.
+ </li><li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasEndedBy(end;_a,e,_a1,_t1,_attrs1)</span><span class="insert">wasEndedBy(end; _a,e,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;e,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">end</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">inv</span>.
+ </li>
+ </ol>
+</div>
+
+<div style="text-align: center; ">
+<span class="figure" id="ordering-entity-trigger">
+<img src="images/constraints/ordering-entity-trigger.png" alt="ordering constraints for trigger entities">
+<br>
+<span class="figcaption" id="ordering-entity-trigger-fig">Figure 4<sup><a class="internalDFN" href="#ordering-entity-trigger-fig"><span class="diamond"> ◊:</span></a></sup> Summary of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> ordering constraints for trigger entities</span>
+</span>
+</div>
+
+<hr>
+<p id="specialization-generation-ordering_text">
+If an entity <span class="delete">specalizes</span><span class="insert">is a specialization of</span> another, then <span class="delete">its generation</span><span class="insert">the more
+specific entity</span> must <span class="delete">follow the
+specialized entity's generation.</span><span class="insert">have been generated after the
+less specific entity was generated.</span>
+</p>
+<div class="constraint" id="specialization-generation-ordering"><div class="ruleTitle"><a class="internalDFN" href="#specialization-generation-ordering">Constraint 45 <span class="delete">(specialization-generation)</span><span class="insert">(specialization-generation-ordering)</span></a></div>
+ <p>
+<span class="conditional">IF</span> <span class="name">specializationOf(e2,e1)</span> and <span class="name"><span class="delete">wasGeneratedBy(gen1;e1,_a1,_t1,_attrs1)</span><span class="delete"> and
+ </span><span class="delete">wasGeneratedBy(gen2;e2,_a2,_t2,_attrs2)</span><span class="insert">wasGeneratedBy(gen1; e1,_a1,_t1,_attrs1)</span></span><span class="insert"> and
+ </span><span class="name"><span class="insert">wasGeneratedBy(gen2; e2,_a2,_t2,_attrs2)</span></span>
+ <span class="conditional">THEN</span> <span class="name">gen1</span> <a href="#dfn-precedes" class="internalDFN">precedes</a> <span class="name">gen2</span>.
+</p></div>
+
+<p>
+
+</p><hr>
+<p id="specialization-invalidation-ordering_text">
+Similarly, if an entity <span class="delete">specalizes another, </span><span class="insert">is a specialization of another entity, and
+</span>then<span class="delete"> its</span><span class="insert">
+the</span> invalidation <span class="delete">must follow the
+specialized entity's invalidation.</span><span class="insert">event of the more specific entity precedes that of
+the less specific entity.</span>
+</p><div class="constraint" id="specialization-invalidation-ordering"><div class="ruleTitle"><a class="internalDFN" href="#specialization-invalidation-ordering">Constraint 46 <span class="delete">(specialization-invalidation)</span><span class="insert">(specialization-invalidation-ordering)</span></a></div>
+ <p>
+<span class="conditional">IF</span> <span class="name"><span class="delete">specializationOf(e2,e1)</span><span class="delete"> and </span><span class="delete">wasInvalidatedBy(inv1;e1,_a1,_t1,_attrs1)</span><span class="delete"> and
+ </span><span class="delete">wasInvalidatedBy(inv2;e2,_a2,_t2,_attrs2)</span><span class="insert">specializationOf(e1,e2)</span></span><span class="insert"> and </span><span class="name"><span class="insert">wasInvalidatedBy(inv2; e2,_a2,_t2,_attrs2)</span></span><span class="insert"> and
+ </span><span class="name"><span class="insert">wasInvalidatedBy(inv1; e1,_a1,_t1,_attrs1)</span></span>
+ <span class="conditional">THEN</span> <span class="name"><span class="delete">inv2</span><span class="insert">inv1</span></span> <a href="#dfn-precedes" class="internalDFN">precedes</a> <span class="name"><span class="delete">inv1</span><span class="insert">inv2</span></span>.
+</p>
+ </div>
+
+</div>
+
+<div id="agent-constraints" class="section">
+<h4><span class="secno">5.2.3 </span> Agent constraints</h4>
+
+<p>
+ Like entities and activities, agents have lifetimes that follow a
+familiar <span class="delete">pattern:</span><span class="insert">pattern. An agent that is also</span> an <span class="insert">entity can be generated
+and invalidated; an </span>agent <span class="insert">that </span>is <span class="delete">generated,</span><span class="insert">also an activity</span> can <span class="insert">be started or
+ended. During its lifetime, an agent can </span>participate in
+ interactions
+such as <span class="delete">starting,</span><span class="insert">starting or</span> ending <span class="insert">other activities, association with an
+activity, attribution, </span>or <span class="delete">association with an
+activity, attribution, or delegation, and finally the agent is invalidated.
+</span><span class="insert">delegation.
+
+</span></p>
+ <p>Further constraints associated with agents appear in <a href="#ordering-agents">Figure 5</a> and are discussed below.</p>
+
+<div style="text-align: center;">
+<span class="figure" id="ordering-agents-fig">
+<img src="images/constraints/ordering-agents.png" alt="ordering constraints for agents">
+<br>
+<span class="figcaption" id="ordering-agents">Figure 5<sup><a class="internalDFN" href="#ordering-agents"><span class="diamond"> ◊:</span></a></sup> Summary of <a title="instantaneous event" href="#dfn-event" class="internalDFN">instantaneous event</a> ordering
+ constraints for agents</span>
+</span>
+</div>
+
+<hr>
+
+
+<p id="wasAssociatedWith-ordering_text">An activity that was associated with an agent must have some overlap with the agent. The agent may be generated, or may only become associated with the activity, after the activity start: so, the agent is required to exist before the activity end. Likewise, the agent may be destructed, or may terminate its association with the activity, before the activity end: hence, the agent invalidation is required to happen after the activity start.
+This is
+illustrated by <a href="#ordering-agents">Figure 5</a> (a) and expressed by <a class="rule-ref" href="#wasAssociatedWith-ordering"><span>Constraint 47 (wasAssociatedWith-ordering)</span></a>.</p>
+
+
+<div class="constraint" id="wasAssociatedWith-ordering"><div class="ruleTitle"><a class="internalDFN" href="#wasAssociatedWith-ordering">Constraint 47 (wasAssociatedWith-ordering)</a></div>
+ <ol> <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasAssociatedWith(_assoc;a,ag,_pl,_attrs)</span><span class="insert">wasAssociatedWith(_assoc; a,ag,_pl,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasStartedBy(start;a,_e1,_a1,_t1,_attrs1)</span><span class="insert">wasStartedBy(start; a,_e1,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;ag,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; ag,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">start</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">inv</span>.
+ </li><li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasAssociatedWith(_assoc;a,ag,_pl,_attrs)</span><span class="insert">wasAssociatedWith(_assoc; a,ag,_pl,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasGeneratedBy(gen;ag,_a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(gen; ag,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasEndedBy(end;a,_e2,_a2,_t2,_attrs2)</span><span class="insert">wasEndedBy(end; a,_e2,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">end</span>.
+ </li>
+ </ol>
+</div>
+
+
+<p>
+
+</p><hr>
+
+<p id="wasAttributedTo-ordering_text">An entity that was attributed to an agent must have some overlap
+with the agent. The agent is required to exist before the entity
+invalidation. Likewise, the entity generation must precede the agent destruction.
+This is
+illustrated by <a href="#ordering-agents">Figure 5</a> (b) and expressed by <a class="rule-ref" href="#wasAttributedTo-ordering"><span>Constraint 48 (wasAttributedTo-ordering)</span></a>.</p>
+
+
+
+
+<div class="constraint" id="wasAttributedTo-ordering"><div class="ruleTitle"><a class="internalDFN" href="#wasAttributedTo-ordering">Constraint 48 (wasAttributedTo-ordering)</a></div>
+ <ol> <li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasAttributedTo(_at;e,ag,_attrs)</span><span class="insert">wasAttributedTo(_at; e,ag,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasGeneratedBy(gen;e,_a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(gen2; e,_a2,_t2,_attrs2)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;ag,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv1; ag,_a1,_t1,_attrs1)</span></span>
+<span class="conditional">THEN</span>
+<span class="name"><span class="delete">gen</span><span class="insert">gen1</span></span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name"><span class="delete">inv</span><span class="insert">inv2</span></span>.
+ </li><li>
+ <span class="conditional">IF</span>
+<span class="name"><span class="delete">wasAttributedTo(_at;e,ag,_attrs)</span><span class="insert">wasAttributedTo(_at; e,ag,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasGeneratedBy(gen;ag,_a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(gen; ag,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;e,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; e,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">inv</span>.
+ </li>
+ </ol>
+</div>
+
+<p>
+</p><hr>
+
+<p id="actedOnBehalfOf-ordering_text">For delegation, two agents need to have some overlap in their lifetime.</p>
+
+
+<div class="constraint" id="actedOnBehalfOf-ordering"><div class="ruleTitle"><a class="internalDFN" href="#actedOnBehalfOf-ordering">Constraint 49 (actedOnBehalfOf-ordering)</a></div>
+<p> <span class="conditional">IF</span>
+<span class="name"><span class="delete">actedOnBehalfOf(_del;ag2,ag1,_a,_attrs)</span><span class="insert">actedOnBehalfOf(_del; ag2,ag1,_a,_attrs)</span></span>
+and
+<span class="name"><span class="delete">wasGeneratedBy(gen;ag1,_a1,_t1,_attrs1)</span><span class="insert">wasGeneratedBy(gen; ag1,_a1,_t1,_attrs1)</span></span>
+and
+<span class="name"><span class="delete">wasInvalidatedBy(inv;ag2,_a2,_t2,_attrs2)</span><span class="insert">wasInvalidatedBy(inv; ag2,_a2,_t2,_attrs2)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">gen</span>
+<a title="precedes" href="#dfn-precedes" class="internalDFN">precedes</a>
+<span class="name">inv</span>.
+</p>
+</div>
+
+</div>
+
+</div>
+
+<div id="impossibility-constraints" class="section">
+<h3><span class="secno">5.3 </span>Impossibility constraints</h3>
+
+<p> Impossibility constraints require that certain patterns of
+statements never appear in <a href="#dfn-valid" class="internalDFN">valid</a> PROV instances. Impossibility
+constraints have the following general form:
+</p>
+
+<div class="constraint-example" id="impossible-example"><div class="ruleTitle"><a class="internalDFN" href="#impossible-example">Constraint-example NNN (impossible-example)</a></div>
+ <p><span class="conditional">IF</span> <span class="name">hyp<sub>1</sub></span> and ... and <span class="name">hyp<sub>n</sub></span> <span class="conditional">THEN</span> <span class="conditional">INVALID</span>.</p>
+ </div>
+
+<p> To check an impossibility constraint on instance <span class="math">I</span>, we check whether there is
+any way of matching the pattern <span class="name">hyp<sub>1</sub></span>, ..., <span class="name">hyp<sub>n</sub></span>. If there
+is, then checking the constraint on <span class="math">I</span> fails (which implies that
+<span class="math">I</span> is invalid).
+
+
+
+
+
+
+
+</p>
+
+<span class="delete">Influence is required to
+ be </span><span class="delete">irreflexive</span><span class="delete">, that is, it is impossible for something to
+ influence itself.</span>
+
+ <span class="delete">Constraint 50 (impossible-influence-reflexive)</span>
+ <span class="delete">IF</span> <span class="delete">wasInfluencedBy(e,e)</span> <span class="delete">THEN</span> <span class="delete">INVALID</span><span class="delete">.</span>
+
+
+
+
+
+<hr>
+
+<p id="impossible-specialization-reflexive_text">As noted previously, specialization is a
+ <a href="#dfn-strict-partial-order" class="internalDFN">strict partial order</a>: it is <a href="#dfn-irreflexive" class="internalDFN">irreflexive</a> and
+ <a href="#dfn-transitive" class="internalDFN">transitive</a>.</p>
+
+ <div class="constraint" id="impossible-specialization-reflexive"><div class="ruleTitle"><a class="internalDFN" href="#impossible-specialization-reflexive">Constraint <span class="delete">51</span><span class="insert">50</span> (impossible-specialization-reflexive)</a></div>
+
+ <p> <span class="conditional">IF</span> <span class="name">specializationOf(e,e)</span> <span class="conditional">THEN</span> <span class="conditional">INVALID</span>.</p>
+ </div>
+
+
+
+
+
+ <hr>
+
+
+ <p id="impossible-property-overlap_text"> Furthermore, identifiers
+ of basic relationships are disjoint.
+ </p>
+ <div class="constraint" id="impossible-property-overlap"><div class="ruleTitle"><a class="internalDFN" href="#impossible-property-overlap">Constraint <span class="delete">52</span><span class="insert">51</span> (impossible-property-overlap)</a></div>
+ <p>
+For each <span class="name">r</span> and <span class="name">s</span>
+ in {
+<span class="name">used</span>,
+<span class="name">wasGeneratedBy</span>,
+<span class="name">wasInvalidatedBy</span>,
+<span class="name">wasStartedBy</span>,
+<span class="name">wasEndedBy</span>,
+<span class="name">wasInformedBy</span>,
+<span class="name">wasAttributedTo</span>,
+<span class="name">wasAssociatedWith</span>,
+<span class="name">actedOnBehalfOf</span>} such that <span class="name">r</span> and <span class="name">s</span>
+ are different <span class="delete">relations,</span><span class="insert">relation names,</span> the
+ following constraint holds:
+</p>
+ <p>
+ <span class="conditional">IF</span> <span class="name"><span class="delete">r(id;a</span><span class="insert">r(id; a</span><sub>1</sub>,...,a<sub>n</sub>)</span> and <span class="name"><span class="delete">s(id;b</span><span class="insert">s(id; b</span><sub>1</sub>,...,b<sub>n</sub>)</span> <span class="conditional">THEN INVALID</span>.
+ </p>
+ </div>
+
+ <div class="remark">
+ Since <span class="name">wasInfluencedBy</span> is a superproperty of many other
+ properties, it is excluded from the set of properties whose
+ identifiers are required to be pairwise disjoint.
+ </div>
+
+ <p id="impossible-object-property-overlap_text"> Identifiers of entities,
+ agents and activities cannot also be identifiers of properties.
+ </p>
+ <div class="constraint" id="impossible-object-property-overlap"><div class="ruleTitle"><a class="internalDFN" href="#impossible-object-property-overlap">Constraint <span class="delete">53</span><span class="insert">52</span> (impossible-object-property-overlap)</a></div>
+ <p>
+For each <span class="name"><span class="delete">r</span><span class="insert">p</span></span> in <span class="name">entity</span>, <span class="name">activity</span>
+ or <span class="name">agent</span> and for each <span class="name"><span class="delete">s</span><span class="insert">r</span></span> in {
+<span class="name">used</span>,
+<span class="name">wasGeneratedBy</span>,
+<span class="name">wasInvalidatedBy</span>,
+<span class="name">wasInfluencedBy</span>,
+<span class="name">wasStartedBy</span>,
+<span class="name">wasEndedBy</span>,
+<span class="name">wasInformedBy</span>,
+<span class="name">wasDerivedFrom</span>,
+<span class="name">wasAttributedTo</span>,
+<span class="name">wasAssociatedWith</span>,
+<span class="name">actedOnBehalfOf</span>}, the following
+ impossibility constraint holds:</p>
+
+<p> <span class="conditional">IF</span> <span class="name"><span class="delete">r(id,a</span><span class="insert">p(id,a</span><sub>1</sub>,...,a<sub>n</sub>)</span> and
+ <span class="name"><span class="delete">s(id;b</span><span class="insert">r(id; b</span><sub>1</sub>,...,b<sub>n</sub>)</span> <span class="conditional">THEN INVALID</span>.
+ </p>
+ </div>
+
+
+
+</div>
+
+<div id="type-constraints" class="section">
+<h3><span class="secno">5.4 </span>Type Constraints</h3>
+
+<p id="typing_text">The following rule establishes types denoted by identifiers from their use within expressions.
+For this, the function <span class="name">typeOf</span> gives the set of types denoted by an identifier.
+For example, <span class="name">typeOf(e)</span> returns the set of types associated with identifier <span class="name">e</span>. The function <span class="name">typeOf</span> is not a term of PROV, but a construct introduced to validate PROV statements.
+</p>
+
+
+
+
+<p>
+ For any identifier <span class="name">id</span>, <span class="name">typeOf(id)</span> is a subset of {<span class="name">'entity'</span>, <span class="name">'activity'</span>, <span class="name">'agent'</span>, <span class="name">'prov:Collection'</span>, <span class="name">'prov:EmptyCollection'</span>}.
+For identifiers that do not have a type, <span class="name">typeOf</span> gives the empty set.
+</p>
+
+<p>To check if a PROV instance satisfies type constraints, one obtains the types of identifiers by application of
+<a class="rule-ref" href="#typing"><span>Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</span></a>
+and check <span class="delete">no</span><span class="insert">that none of the</span> impossibility <span class="delete">results from rules
+</span><span class="insert">constraints
+</span><a class="rule-ref" href="#entity-activity-disjoint"><span>Constraint <span class="delete">55</span><span class="insert">54</span> (entity-activity-disjoint)</span></a> and
+<a class="rule-ref" href="#membership-empty-collection"><span>Constraint <span class="delete">56</span><span class="insert">55</span> (membership-empty-collection)</span></a><span class="delete">.</span><span class="insert"> are
+ violated as a result.</span></p>
+
+
+<div class="constraint" id="typing"><div class="ruleTitle"><a class="internalDFN" href="#typing">Constraint <span class="delete">54</span><span class="insert">53</span> (typing)</a></div>
+
+
+<ul>
+<li>
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasGeneratedBy(gen;e,a,t,attrs)</span><span class="insert">wasGeneratedBy(gen; e,a,t,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e)</span> AND
+<span class="name">'activity' ∈ typeOf(a)</span>.
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">entity(e,attrs)</span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e)</span>.
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">agent(ag,attrs)</span>
+<span class="conditional">THEN</span>
+<span class="name">'agent' ∈ typeOf(ag)</span>.
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">activity(a,attrs)</span>
+<span class="conditional">THEN</span>
+<span class="name">'activity' ∈ typeOf(a)</span>.
+
+
+</li><li>
+
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">used(u;a,e,t,attrs)</span><span class="insert">used(u; a,e,t,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'activity' ∈ typeOf(a)</span> AND
+<span class="name">'entity' ∈ typeOf(e)</span>.
+
+
+</li><li>
+
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasInformedBy(id;a2,a1,attrs)</span><span class="insert">wasInformedBy(id; a2,a1,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'activity' ∈ typeOf(a2)</span> AND
+<span class="name">'activity' ∈ typeOf(a1)</span>.
+
+</li><li>
+
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasStartedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasStartedBy(id; a2,e,a1,t,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'activity' ∈ typeOf(a2)</span> AND
+<span class="name">'entity' ∈ typeOf(e)</span> AND
+<span class="name">'activity' ∈ typeOf(a1)</span>.
+
+
+
+</li><li>
+
+
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasEndedBy(id;a2,e,a1,t,attrs)</span><span class="insert">wasEndedBy(id; a2,e,a1,t,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'activity' ∈ typeOf(a2)</span> AND
+<span class="name">'entity' ∈ typeOf(e)</span> AND
+<span class="name">'activity' ∈ typeOf(a1)</span>.
+
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasInvalidatedBy(id;e,a,t,attrs)</span><span class="insert">wasInvalidatedBy(id; e,a,t,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e)</span> AND
+<span class="name">'activity' ∈ typeOf(a)</span>.
+
+
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">wasDerivedFrom(id; e2, e1, a, g2, u1, attrs)</span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e2)</span> AND
+<span class="name">'entity' ∈ typeOf(e1)</span> AND
+<span class="name">'activity' ∈ typeOf(a)</span>.
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasAttributedTo(id;e,ag,attr)</span><span class="insert">wasAttributedTo(id; e,ag,attr)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e)</span> AND
+<span class="name">'agent' ∈ typeOf(ag)</span>.
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">wasAssociatedWith(id;a,ag,pl,attrs)</span><span class="insert">wasAssociatedWith(id; a,ag,pl,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'activity' ∈ typeOf(a)</span> AND
+<span class="name">'agent' ∈ typeOf(ag)</span> AND
+<span class="name">'entity' ∈ typeOf(pl)</span>.
+
+
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name"><span class="delete">actedOnBehalfOf(id;ag2,ag1,a,attrs)</span><span class="insert">actedOnBehalfOf(id; ag2,ag1,a,attrs)</span></span>
+<span class="conditional">THEN</span>
+<span class="name">'agent' ∈ typeOf(ag2)</span> AND
+<span class="name">'agent' ∈ typeOf(ag1)</span> AND
+<span class="name">'activity' ∈ typeOf(a)</span>.
+
+
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">alternateOf(e2, e1)</span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e2)</span> AND
+<span class="name">'entity' ∈ typeOf(e1)</span>.
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">specializationOf(e2, e1)</span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e2)</span> AND
+<span class="name">'entity' ∈ typeOf(e1)</span>.
+
+
+</li><li>
+<span class="conditional">IF</span>
+ <span class="name">mentionOf(e2,e1,b)</span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(e2)</span> AND
+<span class="name">'entity' ∈ typeOf(e1)</span> AND
+<span class="name">'entity' ∈ typeOf(b)</span>.
+
+
+</li><li>
+
+<span class="conditional">IF</span>
+ <span class="name">hadMember(c,e)</span>
+<span class="conditional">THEN</span>
+<span class="name">'prov:Collection' ∈ typeOf(c)</span> AND
+<span class="name">'entity' ∈ typeOf(c)</span> AND
+<span class="name">'entity' ∈ typeOf(e)</span>.
+
+
+</li><li>
+
+<span class="conditional">IF</span>
+ <span class="name">entity(c,[prov:type='prov:EmptyCollection'])</span>
+<span class="conditional">THEN</span>
+<span class="name">'entity' ∈ typeOf(c)</span> AND
+<span class="name">'prov:EmptyCollection' ∈ typeOf(c)</span>.
+
+</li></ul>
+</div>
+
+
+ <hr>
+ <p id="entity-activity-disjoint_text"> The set of entities and activities are disjoint, expressed by
+ the following constraint:
+ </p>
+ <div class="constraint" id="entity-activity-disjoint"><div class="ruleTitle"><a class="internalDFN" href="#entity-activity-disjoint">Constraint <span class="delete">55</span><span class="insert">54</span> (entity-activity-disjoint)</a></div>
+
+
+<p>
+ <span class="conditional">IF</span>
+<span class="name">'entity' ∈ typeOf(id)</span> AND
+<span class="name">'activity' ∈ typeOf(id)</span>
+<span class="conditional">THEN</span> <span class="conditional">INVALID</span>.</p>
+ </div>
+ <div class="remark">
+ <span class="delete">Note that there</span><span class="insert">There</span> is no disjointness between entities and agents. This is because one might want to make statements about the provenance of an agent, by making it an entity.
+ Therefore, users <em class="rfc2119" title="may">may</em> assert both <span class="name">entity(a1)</span> and <span class="name">agent(a1)</span> in a valid PROV instance.
+
+ <span class="insert">
+ Similarly, there is no disjointness between activities and
+ agents, and it is possbile to assert that an object is both an
+ activity and an agent in a valid PROV instance.
+
+ </span></div>
+
+
+ <hr>
+ <p id="membership-empty-collection_text"> An empty collection cannot contain any member, expressed by
+ the following constraint:
+ </p>
+ <div class="constraint" id="membership-empty-collection"><div class="ruleTitle"><a class="internalDFN" href="#membership-empty-collection">Constraint <span class="delete">56</span><span class="insert">55</span> (membership-empty-collection)</a></div>
+<p> <span class="conditional">IF</span>
+ <span class="name">hasMember(c,e)</span> and
+<span class="name">'prov:EmptyCollection' ∈ typeOf(c)</span>
+<span class="conditional">THEN</span> <span class="conditional">INVALID</span>.</p>
+ </div>
+
+
+</div>
+
+
+</div>
+
+ <div id="normalization-validity-equivalence" class="section">
+<h2><span class="secno">6. </span>Normalization, Validity, and Equivalence</h2>
+
+
+ <p>We define the notions of <a title="normal form" href="#dfn-normal-form" class="internalDFN">normalization</a>, <a title="valid" href="#dfn-valid" class="internalDFN">validity</a> and
+<a title="equivalence">equivalence</a> of PROV instances. We first define these concepts
+for PROV instances that consist of a single, unnamed <a>bundle</a> of
+statements, called the <dfn id="dfn-toplevel-bundle">toplevel bundle</dfn>.</p>
+
+
+
+
+
+<div class="remark"><span class="insert">
+
+ Implementations should decide up front what reasoning about
+ coreference should be applied, and rewrite the instance (by
+ replacing coreferent identifiers with a single common identifier) to
+ make this explicit, before doing validation, equivalence checking,
+ or normalization.
+ All of the following definitions assume that the application has
+ already determined which URIs in the PROV instance are co-referent
+ (e.g. </span><span class="name"><span class="insert">owl:sameAs</span></span><span class="insert"> as a result of OWL
+ reasoning).
+ </span></div>
+
+<p> We define the <dfn id="dfn-normal-form">normal form</dfn> of a PROV instance as the set
+of provenance statements resulting from merging to resolve all
+uniqueness constraints in the instance and applying all possible
+inference rules to this set. </p>
+
+
+
+ <ol>
+ <li>
+ Apply all definitions to <span class="math">I</span> by replacing each defined statement by its
+ definition (possibly introducing fresh existential variables in
+ the process), yielding an instance <span class="math">I<sub>1</sub></span>.
+ </li>
+ <li>
+ Apply all inferences to <span class="math">I<sub>1</sub></span> by adding the conclusion of each inference
+ whose hypotheses are satisfied and whose entire conclusions do not
+ already hold (again, possibly introducing fresh existential
+ variables), yielding an instance <span class="math">I<sub>2</sub></span>.
+ </li>
+ <li>
+ Apply all uniqueness constraints to <span class="math">I<sub>2</sub></span> by merging terms or statements
+ and applying the resulting substitution to the instance, yielding
+ an instance <span class="math">I<sub>3</sub></span>. If some uniqueness constraint cannot be
+ applied, then normalization fails.
+ </li>
+ <li>If no definitions, inferences, or uniqueness constraints can be applied to instance <span class="math">I<sub>3</sub></span>, then <span class="math">I<sub>3</sub></span> is the
+ normal form of <span class="math">I</span>.</li>
+ <li>Otherwise, the normal form of <span class="math">I</span> is the same as the normal form
+ of <span class="math">I<sub>3</sub></span> (that is, proceed by recursively normalizing <span class="math">I<sub>3</sub></span>).
+ </li></ol>
+
+<p>Because of the potential interaction among <span class="insert">definitions, </span>inferences,<span class="delete"> definitions</span> and
+ constraints, the above algorithm is recursive. Nevertheless,
+ all of our constraints fall into a class of <a>tuple-generating
+ dependencies</a> and <a>equality-generating dependencies</a> that
+ satisfy a termination condition called <a>weak acyclicity</a> that
+ has been studied in the context of relational databases
+ [<cite><a class="bibref" rel="biblioentry" href="#bib-DBCONSTRAINTS">DBCONSTRAINTS</a></cite>]. Therefore, the above algorithm terminates, independently
+ of the order in which inferences and constraints are applied.
+ <a href="#termination">Appendix C</a> gives a proof that normalization terminates and produces
+ a unique (up to isomorphism) normal form.
+</p>
+
+ <p>
+ A PROV instance is <dfn id="dfn-valid">valid</dfn>
+if its normal form exists and satisfies all of
+ the validity constraints; this implies that the instance satisfies
+ all of the <span class="insert">definitions, </span>inferences,<span class="delete"> definitions</span> and constraints.
+ The following algorithm can be used to test
+ validity:</p>
+
+<ol>
+ <li>Normalize the instance, obtaining normalized instance <span class="math">I'</span>. If
+ normalization fails, then <span class="math">I</span> is not <a href="#dfn-valid" class="internalDFN">valid</a>.
+ </li>
+ <li>Apply all event ordering constraints to <span class="math">I'</span> to build a graph <span class="math">G</span> whose nodes
+ are event identifiers and edges
+ are labeled by "precedes"
+ and "strictly precedes" relationships among events induced by the constraints.</li>
+ <li> Determine whether there is a cycle in <span class="math">G</span> that contains a
+ "strictly precedes" edge. If so, then <span class="math">I</span> is not <a href="#dfn-valid" class="internalDFN">valid</a>.
+ </li>
+ <li>
+ If no
+ such cycle exists, and none of the impossibility constraints <a href="#impossibility-constraints">(section 5.3)</a> and type constraints <a href="#type-constraints">(section 5.4)</a> are
+ violated, then <span class="math">I</span> is <a href="#dfn-valid" class="internalDFN">valid</a>.
+ </li>
+ </ol>
+
+<p>A normal form of a PROV instance <span class="delete">may</span><span class="insert">does</span> not exist when a uniqueness constraint fails due to merging failure. </p>
+
+
+ <p>Two PROV instances are <dfn id="dfn-equivalent">equivalent</dfn> if they have the
+isomorphic normal forms (that is, after applying all possible inference
+rules, the two instances produce the same set of PROV statements,
+up to reordering of statements and attributes within attribute lists,
+ and renaming of existential variables).
+Equivalence has the following characteristics: </p>
+
+<ul>
+ <li>
+ The order of provenance statements is irrelevant to the meaning of
+ a PROV instance. That is, a
+ PROV instance is equivalent to any other instance obtained by
+ permuting its statements.
+ </li>
+ <li>The order of attribute-value pairs in attribute lists is
+ irrelevant to the meaning of a PROV statement. That is, a PROV
+ statement carrying attributes is equivalent to any other statement
+ obtained by permuting attribute-value pairs.
+ </li>
+ <li>The particular choices of names of existential variables are irrelevant to the meaning
+ of an instance; that is, the names can be permuted without changing
+ the meaning. (Replacing two different names with equal names does
+ change the meaning.)</li>
+ <li>
+ Applying inference rules, definitions, and uniqueness constraints preserves equivalence. That is, a <a>PROV
+ instance</a> is equivalent to the instance obtained by applying any
+ inference rule or definition, or by <a>merging</a> two statements to
+ enforce a uniqueness constraint.
+ </li>
+ <li>Equivalence is <a href="#dfn-reflexive" class="internalDFN">reflexive</a>, <a href="#dfn-symmetric" class="internalDFN">symmetric</a>, and <a href="#dfn-transitive" class="internalDFN">transitive</a>.</li>
+</ul>
+
+<p> An application that processes PROV data <em class="rfc2119" title="should">should</em> handle
+equivalent instances in the same way. (Common exceptions to this rule
+include, for example, pretty-printers that seek to preserve the
+original order of statements in a file and avoid expanding
+inferences.) </p>
+
+
+<div id="bundle-constraints" class="section">
+<h3><span class="secno">6.1 </span>Bundles</h3>
+
+
+<p>The definitions, inferences, and constraints, and
+the resulting notions of normalization, validity and equivalence,
+assume a PROV instance <span class="delete">with</span><span class="insert">that consists of</span> exactly one <a>bundle</a>, the <a href="#dfn-toplevel-bundle" class="internalDFN">toplevel
+bundle</a>, <span class="delete">consisting</span><span class="insert">containing all PROV statements in the top level</span> of <span class="delete">all PROV statements in the toplevel of the
+instance</span><span class="insert">the
+bundle</span> (that is, not enclosed in a named <a>bundle</a>). In this section, we describe how to deal with PROV
+instances consisting of multiple<span class="insert"> named</span> bundles. Briefly, each bundle is
+handled independently; there is no interaction between bundles from
+the perspective of applying definitions, inferences, or constraints,
+computing normal forms, or checking validity or equivalence.</p>
+
+<p> We model a general PROV instance, containing <span class="name">n</span> named bundles
+<span class="name">b<sub>1</sub>...b<sub>n</sub></span>, as a tuple
+<span class="name">(B<sub>0</sub>,[b<sub>1</sub>=B<sub>1</sub>,...,b<sub>n</sub>=B<sub>n</sub>])</span>
+where <span class="name">B<sub>0</sub></span> is the set of
+statements of the <a href="#dfn-toplevel-bundle" class="internalDFN">toplevel bundle</a>, and for each <span class="name">i</span>, <span class="name">B<sub>i</sub></span> is the set of
+statements of bundle <span class="name">b<sub>i</sub></span>. <span class="insert">Names </span><span class="name"><span class="insert">b</span><sub><span class="insert">1</span></sub><span class="insert">...b</span><sub><span class="insert">n</span></sub></span><span class="insert"> are assumed to be distinct. </span>This notation is shorthand for the
+following PROV-N syntax:</p>
+<pre>B<sub>0</sub>
+bundle b<sub>1</sub>
+ B<sub>1</sub>
+endBundle
+...
+bundle b<sub>n</sub>
+ B<sub>n</sub>
+endBundle
+</pre>
+
+<p> The <a href="#dfn-normal-form" class="internalDFN">normal form</a> of a general PROV instance
+<span class="name">(B<sub>0</sub>,[b<sub>1</sub>=B<sub>1</sub>,...,[b<sub>n</sub>=B<sub>n</sub>])</span> is <span class="name">(B'<sub>0</sub>,[b<sub>1</sub>=B'<sub>1</sub>,...,b<sub>n</sub>=B'<sub>n</sub>])</span>
+where <span class="name">B'<sub>i</sub></span> is the normal
+form of <span class="name">B<sub>i</sub></span> for each <span class="name">i</span> between 0 and <span class="name">n</span>. </p>
+
+<p>A general PROV instance is <a href="#dfn-valid" class="internalDFN">valid</a> if each of the bundles <span class="name">B<sub>0</sub></span>,
+..., <span class="name">B<sub>n</sub></span> are valid and none of the bundle identifiers <span class="name">b<sub>i</sub></span> are repeated.</p>
+
+<p>Two (valid) general PROV instances <span class="name">(B<sub>0</sub>,[b<sub>1</sub>=B<sub>1</sub>,...,b<sub>n</sub>=B<sub>n</sub>])</span> and
+<span class="name">(B'<sub>0</sub>,[b<sub>1</sub>'=B'<sub>1</sub>,...,b'<sub>m</sub>=B'<sub>m</sub>])</span> are <a href="#dfn-equivalent" class="internalDFN">equivalent</a> if <span class="name">B<sub>0</sub></span> is
+equivalent to <span class="name">B'<sub>0</sub></span> and <span class="name">n = m</span> and
+there exists a permutation <span class="name">P : {1..n} -> {1..n}</span> such that for each <span class="name">i</span>, <span class="name">b<sub>i</sub> =
+b'<sub>P(i)</sub></span> and <span class="name">B<sub>i</sub></span> is equivalent to <span class="name">B'<sub>P(i)</sub></span>.
+</p>
+
+</div>
+
+
+</div>
+
+
+
+
+
+
+
+
+
+
+<div class="appendix section" id="acknowledgements">
+ <h2><span class="secno">A. </span>Acknowledgements</h2>
+ <p>
+ WG membership to be listed here.
+ </p>
+ </div>
+
+<div class="glossary section" id="glossary">
+ <h2><span class="secno">B. </span>Glossary</h2>
+
+ <ul>
+ <li> <dfn id="dfn-antisymmetric">antisymmetric</dfn>: A relation <span class="math">R</span> over <span class="math">X</span> is <a href="#dfn-antisymmetric" class="internalDFN">antisymmetric</a> if
+ for any elements <span class="math">x</span>, <span class="math">y</span> of <span class="math">X</span>, if <span class="math">x R y</span> and <span class="math">y R x</span> then <span class="math">x = y</span>.</li>
+ <li> <dfn id="dfn-asymmetric">asymmetric</dfn>: A relation <span class="math">R</span> over <span class="math">X</span> is <a href="#dfn-asymmetric" class="internalDFN">asymmetric</a> if
+ <span class="math">x R y</span> and <span class="math">y R x</span> do not hold for any elements <span class="math">x</span>, <span class="math">y</span> of <span class="math">X</span>.</li>
+ <li><dfn id="dfn-equivalence-relation"><span class="insert">equivalence relation</span></dfn><span class="insert">: An equivalence relation is a relation
+ that is </span><a href="#dfn-reflexive" class="internalDFN"><span class="insert">reflexive</span></a><span class="insert">, </span><a href="#dfn-symmetric" class="internalDFN"><span class="insert">symmetric</span></a><span class="insert">, and
+ </span><a href="#dfn-transitive" class="internalDFN"><span class="insert">transitive</span></a><span class="insert">.</span></li>
+ <li> <dfn id="dfn-irreflexive">irreflexive</dfn>: A relation <span class="math">R</span> over <span class="math">X</span> is <a href="#dfn-irreflexive" class="internalDFN">irreflexive</a> if
+ for <span class="math">x R x</span> does not hold for any element <span class="math">x</span> of <span class="math">X</span>.</li>
+ <li> <dfn id="dfn-reflexive">reflexive</dfn>: A relation <span class="math">R</span> over <span class="math">X</span> is <a href="#dfn-reflexive" class="internalDFN">reflexive</a> if
+ for any element <span class="math">x</span> of <span class="math">X</span>, we have <span class="math">x R x</span>.</li>
+ <li><dfn id="dfn-partial-order">partial order</dfn>: A partial order is a relation
+ that is <a href="#dfn-reflexive" class="internalDFN">reflexive</a>, <a href="#dfn-antisymmetric" class="internalDFN">antisymmetric</a>, and <a href="#dfn-transitive" class="internalDFN">transitive</a>.</li>
+ <li><dfn id="dfn-preorder">preorder</dfn>: A preorder is a relation that is
+ <a href="#dfn-reflexive" class="internalDFN">reflexive</a> and <a href="#dfn-transitive" class="internalDFN">transitive</a>. (It is not necessarily antisymmetric,
+ meaning there can be cycles of distinct elements <span class="math">x<sub>1</sub> R x<sub>2</sub> R ... R
+ x<sub>n</sub> R x<sub>1</sub>.</span></li>
+ <li><dfn id="dfn-strict-partial-order">strict partial order</dfn>: A strict partial order is a
+ relation that is <a href="#dfn-irreflexive" class="internalDFN">irreflexive</a>, <a href="#dfn-asymmetric" class="internalDFN">asymmetric</a> and <a href="#dfn-transitive" class="internalDFN">transitive</a>.</li>
+ <li><dfn id="dfn-strict-preorder">strict preorder</dfn>: A strict preorder is a relation
+ that is <a href="#dfn-irreflexive" class="internalDFN">irreflexive</a> and <a href="#dfn-transitive" class="internalDFN">transitive</a>.</li>
+ <li> <dfn id="dfn-symmetric">symmetric</dfn>: A relation <span class="math">R</span> over <span class="math">X</span> is <a href="#dfn-symmetric" class="internalDFN">symmetric</a> if
+ for any elements <span class="math">x</span>, <span class="math">y</span> of <span class="math">X</span>, if <span class="math">x R y</span> then <span class="math">y R x</span>.</li>
+ <li> <dfn id="dfn-transitive">transitive</dfn>: A relation <span class="math">R</span> over <span class="math">X</span> is <a href="#dfn-transitive" class="internalDFN">transitive</a> if
+ for any elements <span class="math">x</span>, <span class="math">y</span>, <span class="math">z</span> of <span class="math">X</span>, if <span class="math">x R y</span> and <span class="math">y R z</span> then <span class="math">x R z</span>.</li>
+
+
+ </ul>
+ </div>
+
+
+ <div class="appendix informative section" id="termination">
+ <h2><span class="secno">C. </span>Termination of normalization</h2><p><em><span class="insert">This section is non-normative.</span></em></p>
+<div class="note">TODO: give proof that normalization terminates and
+ produces unique normal forms.
+ </div>
+</div>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+<div id="references" class="appendix section"><h2><span class="secno">D. </span>References</h2><div id="normative-references" class="section"><h3><span class="secno">D.1 </span>Normative references</h3><dl class="bibliography"><span class="delete">[PROV-N]</span><dt id="bib-RDF"><span class="insert">[RDF]</span></dt><dd><span class="delete">Luc Moreau and Paolo Missier (eds.), James Cheney, Stian Soiland-Reyes </span><span class="insert">Graham Klyne and Jeremy J. Carroll (eds.) </span><a href="http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/"><cite><span class="delete">PROV-N: The Provenance Notation</span><span class="insert">Resource Description Framework (RDF): Concepts and Abstract Syntax</span></cite></a>. <span class="delete">2011, Working Draft.</span><span class="insert">2004, W3C Recommendation.</span> URL: <span class="delete">http://www.w3.org/TR/prov-n/</span><a href="http://www.w3.org/TR/2004/REC-rdf-concepts-20040210//"><span class="insert">http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/</span></a>
+</dd><dt id="bib-RFC2119">[RFC2119]</dt><dd>S. Bradner. <a href="http://www.ietf.org/rfc/rfc2119.txt"><cite>Key words for use in RFCs to Indicate Requirement Levels.</cite></a> March 1997. Internet RFC 2119. URL: <a href="http://www.ietf.org/rfc/rfc2119.txt">http://www.ietf.org/rfc/rfc2119.txt</a>
+</dd></dl></div><div id="informative-references" class="section"><h3><span class="secno">D.2 </span>Informative references</h3><dl class="bibliography"><dt id="bib-CHR">[CHR]</dt><dd>Thom Frühwirth <a href="http://constraint-handling-rules.org/"><cite>Constraint Handling Rules</cite></a>. Cambridge University Press URL: <a href="http://constraint-handling-rules.org/">http://constraint-handling-rules.org/</a>
+</dd><dt id="bib-CLOCK">[CLOCK]</dt><dd>Lamport, L. <a href="http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf"><cite>Time, clocks, and the ordering of events in a distributed system</cite></a>. Communications of the ACM 21 (7): 558–565. 1978. URL: <a href="http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf">http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf</a> DOI: doi:10.1145/359545.359563.
+</dd><dt id="bib-DBCONSTRAINTS">[DBCONSTRAINTS]</dt><dd> Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa <a href="http://dx.doi.org/10.1016/j.tcs.2004.10.033"><cite>Data exchange: Semantics and query answering</cite></a>. Theoretical computer science 336(1):89-124 Elsevier URL: <a href="http://dx.doi.org/10.1016/j.tcs.2004.10.033">http://dx.doi.org/10.1016/j.tcs.2004.10.033</a>
+</dd><dt id="bib-Logic">[Logic]</dt><dd>W. E. Johnson<a href="http://www.ditext.com/johnson/intro-3.html"><cite>Logic: Part III</cite></a>.1924. URL: <a href="http://www.ditext.com/johnson/intro-3.html">http://www.ditext.com/johnson/intro-3.html</a>
+</dd><dt id="bib-PROV-DM">[PROV-DM]</dt><dd>Luc Moreau and Paolo Missier (eds.) Khalid Belhajjame, Reza B'Far, James Cheney, Stephen Cresswell, Yolanda Gil, Paul Groth, Graham Klyne, Jim McCusker, Simon Miles, James Myers, Satya Sahoo, and Curt Tilmes <a href="http://www.w3.org/TR/prov-dm/"><cite>PROV-DM: The PROV Data Model</cite></a>. 2012, Working Draft. URL: <a href="http://www.w3.org/TR/prov-dm/">http://www.w3.org/TR/prov-dm/</a>
+</dd><dt id="bib-PROV-N"><span class="insert">[PROV-N]</span></dt><dd><span class="insert">Luc Moreau and Paolo Missier (eds.), James Cheney, Stian Soiland-Reyes </span><a href="http://www.w3.org/TR/prov-n/"><cite><span class="insert">PROV-N: The Provenance Notation</span></cite></a><span class="insert">. 2011, Working Draft. URL: </span><a href="http://www.w3.org/TR/prov-n/"><span class="insert">http://www.w3.org/TR/prov-n/</span></a>
+</dd><dt id="bib-PROV-O"><span class="insert">[PROV-O]</span></dt><dd><span class="insert">Timothy Lebo, Satya Sahoo and Deborah McGuinness (eds.) Khalid Belhajjame, James Cheney, David Corsar, Daniel Garijo, Stian Soiland-Reyes, and Stephan Zednik </span><a href="http://www.w3.org/TR/prov-o/"><cite><span class="insert">Provenance Formal Model</span></cite></a><span class="insert">. 2011, Working Draft. URL: </span><a href="http://www.w3.org/TR/prov-o/"><span class="insert">http://www.w3.org/TR/prov-o/</span></a>
+</dd><dt id="bib-PROV-SEM">[PROV-SEM]</dt><dd>James Cheney <a href="http://www.w3.org/2011/prov/wiki/FormalSemanticsStrawman"><cite>Formal Semantics Strawman</cite></a>. 2011, Work in progress. URL: <a href="http://www.w3.org/2011/prov/wiki/FormalSemanticsStrawman">http://www.w3.org/2011/prov/wiki/FormalSemanticsStrawman
+<span class="delete">[RDF]</span><span class="delete">Graham Klyne and Jeremy J. Carroll (eds.) </span><span class="delete">Resource Description Framework (RDF): Concepts and Abstract Syntax</span><span class="delete">. 2004, W3C Recommendation. URL: </span><span class="delete">http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/</span></a>
+</dd></dl></div></div></body></html>
+