--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/dictionary/prov-dictionary.html Mon Dec 10 13:07:15 2012 +0100
@@ -0,0 +1,1607 @@
+<!DOCTYPE html
+>
+
+<html><head>
+ <title>PROV Dictionary</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
+
+<script src="../model/prov-magic.js" class="remove"></script>
+
+<script src="../model/grammar/ll.js" class="remove"></script>
+<script src="../model/provbib.js" class="remove"></script>
+<script src="../model/glossary.js" class="remove"></script>
+
+<script src="http://www.w3.org/Tools/respec/respec-w3c-common" class="remove" async></script>
+
+<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js" class="remove"></script>
+
+<style type="text/css">
+ .note { font-size:small; margin-left:50px }
+
+ .entity {
+ border: 1px solid navy;
+ margin:5px 0px 5px 0px;
+ padding: 5px;
+ }
+
+
+
+ .description {
+ border-top: 1px dashed gray;
+ border-bottom: 1px dashed gray;
+ background-color: rgb(242, 243, 244);
+ margin-top:5px;
+ padding-bottom:5px;
+ }
+
+ .description dl {
+ background-color: rgb(242, 243, 244);
+ }
+
+ .description ul {
+ padding-left: 12px;
+ margin-top: 0px;
+ }
+
+code {
+ color: black !important;
+}
+
+.diamond {
+ font-weight: normal;
+ font-style: normal;
+ font-size:100%;
+ font-family: sans-serif;
+}
+
+table.thinborder {
+ border-width: 1px;
+ border-spacing: 0px;
+ border-style: none;
+ border-color: gray;
+ border-collapse: collapse;
+}
+table.thinborder th {
+ border-width: 1px;
+ padding: 0px;
+ border-style: solid;
+ border-color: gray;
+}
+table.thinborder td {
+ border-width: 1px;
+ padding: 2px;
+ border-style: solid;
+ border-color: gray;
+}
+
+/* --- EDITORIAL NOTES --- */
+.pending {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #BFEFFF;
+}
+
+.pending::before {
+ content: "Pending Review";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #f00;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+
+
+
+.resolved {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #9BCD9B;
+}
+
+.resolved::before {
+ content: "Resolved";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #f00;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+
+.inference {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #fff;
+}
+
+
+.inference-example {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #fff;
+}
+
+.syntax {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #fff;
+}
+
+.syntax[id]::before {
+ content: "Syntax: " attr(id);
+ width: 380px; /* How can we compute the length of "Constraint: " attr(id) */
+}
+
+
+.syntax::before {
+ content: "Syntax";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #f00;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+.unamedconstraint {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #00f;
+ background: #fff;
+}
+
+
+.unamedconstraint::before {
+ content: "Constraint";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #00f;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+
+
+.constraint {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #00f;
+ background: #fff;
+}
+
+.constraint-example {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #00f;
+ background: #fff;
+}
+
+
+.interpretation {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #00f;
+ background: #fff;
+}
+
+.interpretation[id]::before {
+ content: "Interpretation: " attr(id);
+ width: 380px; /* How can we compute the length of "Interpretation: " attr(id) */
+}
+
+
+.interpretation::before {
+ content: "Interpretation";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #00f;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+.definition {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #777;
+ background: #fff;
+}
+
+.definition-example {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #777;
+ background: #fff;
+}
+
+.deprecatedconstraint {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #00f;
+ background: #fff;
+}
+
+.deprecatedconstraint[id]::before {
+ content: "Deprecated: " attr(id);
+ width: 380px; /* How can we compute the length of "Deprecatedconstraint: " attr(id) */
+}
+
+
+.deprecatedconstraint::before {
+ content: "Deprecated";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #00f;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+.glossary-ref {
+ font-style: italic;
+}
+
+.dfn {
+ font-weight: bold;
+}
+
+
+.attribute {
+ font-style: italic;
+}
+
+
+.conditional {
+ color: blue;
+}
+
+.grammar {
+ margin-top: 1ex;
+ margin-bottom: 1ex;
+ padding-left: 1ex;
+ padding-right: 1ex;
+ padding-top: 1ex;
+ padding-bottom: 0.6ex;
+ border: 1px dashed #2f6fab;
+ font-size: 95%;
+}
+.nonterminal {
+ font-weight: bold;
+ font-family: sans-serif;
+ font-size: 95%;
+}
+
+.name {
+ font-family: monospace;
+}
+
+.math {
+ font-family: roman;
+ font-style:italic;
+}
+
+
+.xmpl {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px solid #f00;
+ background: #fff;
+}
+
+.xmpl::before {
+ content: "Example";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #f00;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+
+.anexample {
+ margin-top: 1ex;
+ margin-bottom: 1ex;
+ padding-left: 1ex;
+ padding-right: 1ex;
+ padding-top: 1ex;
+ padding-bottom: 0.6ex;
+ border: 1px dashed #2f6fab;
+ background-color: #f9f9f9;
+}
+.anexample table {
+ background-color: #f9f9f9;
+}
+
+.conceptexample:before {
+ content: "Example:";
+ font-family: sans-serif;
+ font-size: 1.6ex;
+ font-weight: bold;
+}
+.conceptexample {
+ margin-top: 1ex;
+ margin-bottom: 1ex;
+ padding-left: 1ex;
+ padding-right: 1ex;
+ padding-top: 1ex;
+ padding-bottom: 0.6ex;
+ border: 1px dashed #2f6fab;
+ background-color: #f9f9f9;
+}
+
+.pnExpression {
+ font-weight: normal;
+ font-size:120%;
+ font-family: monospace;
+}
+
+
+div[class="grammar"] span[class="name"]:before {
+ content: "'";
+}
+
+div[class="grammar"] span[class="name"]:after {
+ content: "'";
+}
+
+
+div[class="grammar"] span[class="optional"]:before {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: "(";
+}
+
+div[class="grammar"] span[class="optional"]:after {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: ")?";
+}
+
+
+div[class="grammar"] span[class="plus"]:before {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: "(";
+}
+
+div[class="grammar"] span[class="plus"]:after {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: ")+";
+}
+
+
+div[class="grammar"] span[class="star"]:before {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: "(";
+}
+
+div[class="grammar"] span[class="star"]:after {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: ")*";
+}
+
+div[class="grammar"] span[class="choice"]:before {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: "(";
+}
+
+div[class="grammar"] span[class="choice"]:after {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: ")";
+}
+
+div[class="grammar"] span[class="group"]:before {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: "(";
+}
+
+div[class="grammar"] span[class="group"]:after {
+ font-weight: normal;
+ font-size:130%;
+ font-family: monospace;
+ content: ")";
+}
+
+table {
+ background-color: #f9f9f9;
+}
+
+.component1-color {
+ background-color: rgba(255,42,42,0.2);
+}
+
+.component2-color {
+ background-color: rgba(0,68,170,0.2);
+}
+
+.component3-color {
+ background-color: rgba(0,170,0,0.2);
+}
+.component4-color {
+ background-color: rgba(204,255,0,0.2);
+}
+
+.component5-color {
+ background-color: rgba(11,40,40,0.2);
+}
+
+.component6-color {
+ background-color: rgba(244,105,14,0.2);
+}
+
+.interpretation-forward::before {
+ content: "Interpretation: ";
+ font-weight: bold;
+}
+
+.structural-forward::before {
+ content: "Structural constraint: ";
+ font-weight: bold;
+}
+
+
+code {
+ color: black;
+}
+
+.ruleTitle {
+ font-family: sans-serif;
+ font-size: 1.6ex;
+ font-weight: bold;
+}
+
+
+
+
+.remark {
+ padding: 1em;
+ margin: 1em 0em 0em;
+ border: 1px dashed #000;
+ background: #F0F0F0;
+}
+
+.remark::before {
+ content: "Remark";
+ display: block;
+ width: 150px;
+ margin: -1.5em 0 0.5em 0;
+ font-weight: bold;
+ border: 1px solid #000;
+ background: #fff;
+ padding: 3px 1em;
+}
+
+table.thinborder {
+ border-width: 1px;
+ border-spacing: 0px;
+ border-style: none;
+ border-color: gray;
+ border-collapse: collapse;
+}
+table.thinborder th {
+ border-width: 1px;
+ padding: 0px;
+ border-style: solid;
+ border-color: gray;
+}
+table.thinborder td {
+ border-width: 1px;
+ padding: 2px;
+ border-style: solid;
+ border-color: gray;
+}
+
+
+</style>
+
+
+ <script type="text/javascript">
+/*
+ Written by Jonathan Snook, http://www.snook.ca/jonathan
+ Add-ons by Robert Nyman, http://www.robertnyman.com
+ Author says "The credit comment is all it takes, no license. Go crazy with it!"
+ From http://www.robertnyman.com/2005/11/07/the-ultimate-getelementsbyclassname/
+*/
+
+function getElementsByClassName(oElm, strTagName, oClassNames){
+ var arrElements = (! (! (strTagName == "*") || ! (oElm.all)))? oElm.all : oElm.getElementsByTagName(strTagName);
+ var arrReturnElements = new Array();
+ var arrRegExpClassNames = new Array();
+ if(typeof oClassNames == "object"){
+ for(var i=0; !(i>=oClassNames.length); i++){ /*>*/
+ arrRegExpClassNames.push(new RegExp("(^|\s)" + oClassNames[i].replace(/\-/g, "\-") + "(\s|$)"));
+ }
+ }
+ else{
+ arrRegExpClassNames.push(new RegExp("(^|\s)" + oClassNames.replace(/\-/g, "\-") + "(\s|$)"));
+ }
+ var oElement;
+ var bMatchesAll;
+ for(var j=0; !(j>=arrElements.length); j++){ /*>*/
+ oElement = arrElements[j];
+ bMatchesAll = true;
+ for(var k=0; !(k>=arrRegExpClassNames.length); k++){ /*>*/
+ if(!arrRegExpClassNames[k].test(oElement.className)){
+ bMatchesAll = false;
+ break;
+ }
+ }
+ if(bMatchesAll){
+ arrReturnElements.push(oElement);
+ }
+ }
+ return (arrReturnElements)
+}
+
+function set_display_by_class(el, cls, newValue) {
+ var e = getElementsByClassName(document, el, cls);
+ if (e != null) {
+ for (var i=0; !(i>=e.length); i++) {
+ e[i].style.display = newValue;
+ }
+ }
+}
+
+function set_display_by_id(id, newValue) {
+ var e = document.getElementById(id);
+ if (e != null) {
+ e.style.display = newValue;
+ }
+}
+</script>
+
+
+ <script type="text/javascript" class="remove">
+
+
+ $(document).ready(function(){
+ // if glossary is in a string:
+ $('#glossary_div').html(glossary_string)
+ $('#grammar_div').html(grammar_string);
+ updateGlossaryRefs();
+ updateFigCaptions();
+ updateCaptions();
+ updateGrammarRefs();
+ updateExamples();
+ updateExamplesRefs();
+
+ if (typeof String.prototype.startsWith != 'function') {
+ String.prototype.startsWith = function (str){
+ return this.indexOf(str) == 0;
+ };
+ }
+
+ });
+
+ </script>
+ <script class="remove">
+ function updateGrammarRefs() {
+ $('.grammar-ref').each(function(index) {
+ var ref=$(this).attr('data-ref');
+ console.log( "updating grammar for " + ref);
+// $('#'+ref).parents("tbody").clone().appendTo($(this));
+
+
+ // $(this).replaceWith(function() {return $('#'+ref).parents("tbody").clone()});
+
+ $(this).replaceWith($('#'+ref).parents("tbody").clone());
+
+ });
+ }
+ </script>
+ <script class="remove">
+ var addExtraReferences = function() {
+ for (var k in extraReferences)
+ berjon.biblio[k] = extraReferences[k];
+ };
+ var extraReferences = {
+
+ };
+ var respecConfig = {
+ // specification status (e.g. WD, LCWD, NOTE, etc.). If in doubt use ED.
+ specStatus: "ED", //FPWD-NOTE
+
+ // the specification's short name, as in http://www.w3.org/TR/short-name/
+ shortName: "prov-dictionary",
+
+ // if your specification has a subtitle that goes below the main
+ // formal title, define it here
+ //subtitle : "A single document for prov-mention related material",
+
+
+ // if you wish the publication date to be other than today, set this
+ //publishDate: "2012-12-11",
+
+ // if the specification's copyright date is a range of years, specify
+ // the start date here:
+ //copyrightStart: "2011",
+
+ // if there is a previously published draft, uncomment this and set its YYYY-MM-DD date
+ // and its maturity status
+ //previousPublishDate: "2012-07-24",
+ //previousMaturity: "ED",
+
+ // if there a publicly available Editor's Draft, this is the link
+ edDraftURI: "http://dvcs.w3.org/hg/prov/raw-file/default/dictionary/prov-dictionary.html",
+
+ // if this is a LCWD, uncomment and set the end of its review period
+ //lcEnd: "2012-09-18",
+
+ // if you want to have extra CSS, append them to this list
+ // it is recommended that the respec.css stylesheet be kept
+ extraCSS: ["http://dev.w3.org/2009/dap/ReSpec.js/css/respec.css"],
+
+ // editors, add as many as you like
+ // only "name" is required
+ editors: [
+ { name: "Tom De Nies", url: "http://users.ugent.be/~tdenies/",
+ company: "IBBT - Ghent University" },
+ { name: "Sam Coppens",
+ company: "IBBT - Ghent University" },
+ ],
+
+ // authors, add as many as you like.
+ // This is optional, uncomment if you have authors as well as editors.
+ // only "name" is required. Same format as editors.
+
+ authors: [ {name: "Orginal PROV-DM authors"}
+ ],
+
+ // name of the WG
+ wg: "Provenance Working Group",
+
+ // URI of the public WG page
+ wgURI: "http://www.w3.org/2011/prov/",
+
+ // name (with the @w3c.org) of the public mailing to which comments are due
+ wgPublicList: "public-prov-comments",
+
+ // URI of the patent status for this WG, for Rec-track documents
+ // !!!! IMPORTANT !!!!
+ // This is important for Rec-track documents, do not copy a patent URI from a random
+ // document unless you know what you're doing. If in doubt ask your friendly neighbourhood
+ // Team Contact.
+ wgPatentURI: "http://www.w3.org/2004/01/pp-impl/46974/status",
+
+ // Add extraReferences to bibliography database
+ preProcess: [addExtraReferences, addProvReferences],
+
+ postProcess: [updateSectionRefs, updateDfn, updateFigures],
+ };
+ </script>
+ </head>
+ <body>
+
+ <section id="abstract">
+<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.
+</p>
+
+<p>The <a href="http://www.w3.org/TR/2012/WD-prov-overview-20121211/">PROV Document Overview</a> describes the overall state of PROV, and should be read before other PROV documents.</p>
+
+ </section>
+
+<section id="sotd">
+<h4>PROV Family of Documents</h4>
+This document is part of the PROV family of documents, a set of documents defining various aspects that are necessary to achieve the vision of inter-operable
+interchange of provenance information in heterogeneous environments such as the Web. These documents are:
+<ul>
+<li> <a href="http://www.w3.org/TR/2012/WD-prov-overview-20121211/">PROV-OVERVIEW</a> (To be published as Note), an overview of the PROV family of documents [[PROV-OVERVIEW]];</li>
+<li> <a href="http://www.w3.org/TR/2012/WD-prov-primer-20121211/">PROV-PRIMER</a> (To be published as Note), a primer for the PROV data model [[PROV-PRIMER]];</li>
+<li> <a href="http://www.w3.org/TR/2012/CR-prov-o-20121211/">PROV-O</a> (Candidate Recommendation), the PROV ontology, an OWL2 ontology allowing the mapping of PROV to RDF [[PROV-O]];</li>
+<li> <a href="http://www.w3.org/TR/2012/CR-prov-dm-20121211/">PROV-DM</a> (Candidate Recommendation), the PROV data model for provenance [[PROV-DM]];</li>
+<li> <a href="http://www.w3.org/TR/2012/CR-prov-n-20121211/">PROV-N</a> (Candidate Recommendation), a notation for provenance aimed at human consumption [[PROV-N]];</li>
+<li> <a href="http://www.w3.org/TR/2012/CR-prov-constraints-20121211/">PROV-CONSTRAINTS</a> (Candidate Recommendation), a set of constraints applying to the PROV data model [[PROV-CONSTRAINTS]];</li>
+<li> <a href="http://www.w3.org/TR/2012/WD-prov-aq-20120619/">PROV-AQ</a> (To be published as Note), the mechanisms for accessing and querying provenance [[PROV-AQ]]; </li>
+<li> <a href="http://www.w3.org/TR/2012/WD-prov-xml-20121211/">PROV-XML</a> (To be published as Note), an XML schema for the PROV data model [[PROV-XML]];</li>
+<li> <a href="http://www.w3.org/TR/2012/WD-prov-links-20121211/">PROV-LINKS</a> (To be published as Note), introduces a mechanism to link across bundles.</li>
+<li> <a href="#">PROV-DICTIONARY</a> (To be published as Note), introduces a specific type of collection, consisting of key-entity pairs (this document).</li>
+
+</ul>
+<h4>How to read the PROV Family of Documentation</h4>
+<ul>
+<li>[[PROV-OVERVIEW]] overviews the PROV family of documents. </li>
+<li>The primer [[PROV-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. </li>
+<li>The XML community should focus on [[PROV-XML]] defining an XML schema for PROV. Further details can also be found in [[PROV-DM]] and [[PROV-CONSTRAINTS]].</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]], [[PROV-N]], and [[PROV-XML]] offer examples of mapping to RDF, text, and XML, respectively.</li>
+</ul>
+</section>
+
+
+
+
+
+
+
+
+
+
+ <section id="introduction">
+<h2>Introduction</h2>
+
+<p>
+<a href="http://www.w3.org/TR/2012/CR-prov-dm-20121211/">Provenance</a>
+is a record that describes the people, institutions, entities, and
+activities involved in producing, influencing, or delivering a piece
+of data or a thing. The specifications [[PROV-O]], [[PROV-DM]],
+[[PROV-N]], and [[PROV-XML]] have respectively defined the PROV
+ontology, the PROV conceptual model, the PROV notation, and the PROV
+XML schema, allowing provenance descriptions to be expressed,
+represented in various representations, and interchanged between systems across the Web.
+</p>
+<p>[[PROV-DM]] specifies Collection as an entity that provides a structure to some constituents, which are themselves entities. However, some applications may need a mechanism to specify mor structure to a Collection, in order to accurately describe its provenance.</p>
+
+<p>Therefore, this document introduces a new concept, <a>Dictionary</a>, that has a logical structure consisting of key-entity pairs. The Provenance Working Group is seeking feedback from the community on its usefulness in practical scenarios.</p>
+</section>
+
+
+
+<section id="data-model-components">
+
+<h2>Dictionary</h2>
+
+<p>Provenance concepts, expressed as PROV-DM types and relations, are organized according to six components that are defined in this section.
+The components and their dependencies are illustrated in <a href="#prov-dm-components">Figure 4</a>. A component that relies on concepts defined in another is displayed above it in the figure. So, for example, component 6 (collections) depends on concepts defined in component 3 (derivation), itself dependen on concepts defined in component 1 (entity and activity).
+</p>
+
+
+<section id="component6">
+<h3>Component 6: Collections</h3>
+
+<p>The sixth component of PROV-DM is concerned with the notion of collections.
+A collection is an entity that has some members. The members are themselves entities, and therefore their provenance can be expressed. Some applications need to be able to express the provenance of the collection itself: e.g. who maintains the collection (attribution), which members it contains as it evolves, and how it was assembled. The purpose of Component 6 is to define the types and relations that are useful to express the provenance of collections. In PROV, the concept of Collection is implemented by means of dictionaries, which we introduce in this section. </p>
+
+<p><a href="#figure-component6">Figure 10</a> depicts
+the sixth component with four new classes (Collection, Dictionary, EmptyDictionary, and Pair) and three associations (insertion, removal, and memberOf).
+</p>
+
+
+<div style="text-align: center;">
+<figure>
+<!-- <img src="images/Dictionaries.png" alt="dictionaries"/> -->
+<img src="uml/Component-Dictionary.png" alt="dictionaries"/>
+
+<figcaption id="figure-component6">Figure 10: Collections Component Overview</figcaption>
+</figure>
+</div>
+
+
+<p>The intent of these relations and types is to express the <em>history of changes that occurred to a collection</em>.
+Changes to collections are about the insertion of entities into, and the removal of entities from the collection.
+Indirectly, such history provides a way to reconstruct the contents of the collection.</p>
+
+<section id="term-collection">
+<h3>Collection</h3>
+
+<span class="glossary-ref" data-ref="glossary-collection"></span>
+
+<p>A collection is a multiset of entities (it is a multiset, rather than a set, because it may not be possible to verify that two distinct entity identitifiers do not denote, in fact, the same entity).</p>
+
+<span class="glossary-ref" data-ref="glossary-empty-collection"></span>
+
+
+<p>PROV-DM defines the following types related to collections:</p>
+
+<ul>
+ <li> <span class="name">prov:Collection</span> denotes an entity of type Collection, i.e. an entity that can participate in relations amongst collections;
+
+ <li><span class="name">prov:EmptyCollection</span> denotes an empty collection.
+</ul>
+
+
+<div class="anexample">
+<pre class="codeexample">
+entity(c0, [prov:type='prov:EmptyCollection' ]) // c0 is an empty collection
+entity(c1, [prov:type='prov:Collection' ]) // c1 is a collection, with unknown content
+</pre>
+</div>
+
+<p>In PROV, the concept of Collection is provided as an extensibility point for specialized kinds of collections. One of these, Dictionary, is defined next. </p>
+
+</section>
+
+<section id="term-collection-membership">
+<h3>Collection Memberhsip</h3>
+
+<p>A <strong>collection membership</strong> relation is defined, to allow stating the members of a Collection. </p>
+
+<span class="glossary-ref" data-ref="glossary-collection-membership"></span>
+
+
+<p>
+<div class="attributes" id="attributes-memberOf">
+ A <dfn title="memberOf">membership</dfn> relation, written <span class="pnExpression">memberOf(id; c, {e_1, ..., e_n}, cplt, attrs)</span>, has:
+<ul>
+<li><span class='attribute' id="membership.id">id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute' id="membership.collection">collection</span>: an identifier (<span class="name">c</span>) for the collection whose members are asserted; </li>
+<li><span class='attribute' id="membership.entity-set">entity-set</span>: a set of entities <span class="name">e_1</span>, ..., <span class="name">e_n</span> that are members of the collection;</li>
+<li><span class='attribute' id="membership.complete">complete</span>: an OPTIONAL boolean
+<a title="value">Value</a> (<span class="name">cplt</span>). It is interpreted as follows:
+<ul>
+<li>if it is present and set to true, then c is believed to include all and only the members specified in the entity-set;
+<li>if it is present and set to false, then c is believed to include more members in addition to those specified in the entity-set;
+<li>if it is not present, then c is believed to include all the members specified in the entity-set, and it MAY include more.
+</ul>
+
+<li><span class='attribute' id="membership.attributes">attributes</span>: an OPTIONAL set (<span class="name">attrs</span>) of attribute-value pairs representing additional information about this relation.</li>
+</ul>
+
+</div>
+
+<p id="complete-attribute-note">
+Note that the attribute <a href="#membership.complete">complete</a> indicates that the <a title="memberOf">membership</a> relation provides a complete description of the collection membership. It is possible for different provenance descriptions to provide different membership statements regarding the same collection. The resolution of any potential conflict amongst such membership statements is defined by applications.</p>
+
+
+</section>
+
+<section id="term-dictionary">
+<h3>Dictionary</h3>
+
+<p>PROV-DM defines a specific type of collection, specified as follows.</p>
+
+
+<span class="glossary-ref" data-ref="glossary-dictionary"></span>
+
+<p>Conceptually, a dictionary has a logical structure consisting of key-entity pairs. This structure is often referred to as a <em>map</em>, and is a generic indexing mechanism that can abstract commonly used data structures, including associative lists, relational tables, ordered lists, and more. The specification of such specialized structures in terms of key-value pairs is out of the scope of this document.</p>
+
+<p>A given dictionary forms a given structure for its members. A different structure (obtained either by insertion or removal of members) constitutes a different dictionary. Hence,
+ for the purpose of provenance, a dictionary entity is viewed as a snapshot of a structure. Insertion and removal operations result in new snapshots, each snapshot forming an identifiable dictionary entity.</p>
+
+<!--
+<span class="glossary-ref" data-ref="glossary-empty-dictionary"></span>
+-->
+
+
+<p>Following the earlier definitions for generic collections, PROV-DM defines the following types related to dictionaries:</p>
+
+<ul>
+ <li> <span class="name">prov:Dictionary</span> is a subtype of <span class="name">prov:Collection</span>. It denotes an entity of type dictionary, i.e. an entity that can participate in relations amongst dictionaries;
+
+ <li><span class="name">prov:EmptyDictionary</span> is a subtype of <span class="name">prov:EmptyCollection</span>. It denotes an empty dictionary.
+</ul>
+
+
+<div class="anexample">
+<pre class="codeexample">
+entity(d0, [prov:type='prov:EmptyDictionary' ]) // d0 is an empty dictionary
+entity(d1, [prov:type='prov:Dictionary' ]) // d1 is a dictionary, with unknown content
+</pre>
+</div>
+
+</section> <!-- end of dictionary-types -->
+
+<section id="term-dictionary-membership">
+<h3>Dictionary Membership</h3>
+
+
+<span class="glossary-ref" data-ref="glossary-dictionary-membership"></span>
+
+The <strong>dictionary membership</strong> has the same purpose as the <a href="#term-collection-membership">collection membership</a> relation, but it applies to entities having <span class="name">prov:type = 'prov:Dictionary'</span>. It allows stating the members of a Dictionary.
+
+<!--
+<p>
+The insertion and removal relations make insertions and removals explicit as part of the history of a dictionary. This, however, requires explicit reference to the dictionary that existed prior to each operation. The membership relation removes this need, allowing the membership of a dictionary to be expressed without having to introduce a prior dictionary.</p>
+-->
+
+<p>
+<div class="attributes" id="attributes-memberOf-d">
+ A <dfn title="memberOf-d">membership</dfn> relation, written <span class="pnExpression">memberOf(id; c, {(key_1, e_1), ..., (key_n, e_n)}, cplt, attrs)</span>, has:
+<ul>
+<li><span class='attribute' id="membership-d.id">id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute' id="membership-d.dictionary">dictionary</span>: an identifier (<span class="name">c</span>) for the dictionary whose members are asserted; </li>
+<li><span class='attribute' id="membership-d.key-entity-set">key-entity-set</span>: a set of key-entity pairs <span class="name">(key_1, e_1)</span>, ..., <span class="name">(key_n, e_n)</span> that are members of the dictionary;</li>
+<li><span class='attribute' id="membership-d.complete">complete</span>: an OPTIONAL boolean
+<a title="value">Value</a> (<span class="name">cplt</span>). It is interpreted as follows:
+<ul>
+<li>if it is present and set to true, then c is believed to include all and only the members specified in the key-entity-set;
+<li>if it is present and set to false, then c is believed to include more members in addition to those specified in the key-entity-set;
+<li>if it is not present, then c is believed to include all the members specified in the key-entity-set, and it MAY include more.
+</ul>
+
+<!-- if true, it indicates that no other member belongs to the dictionary; if false, it indicates that other members belong to the dictionary; if unspecified, other members MAY belong to the dictionary; -->
+<li><span class='attribute' id="membership-d.attributes">attributes</span>: an OPTIONAL set (<span class="name">attrs</span>) of attribute-value pairs representing additional information about this relation.</li>
+</ul>
+
+</div>
+
+<p id="complete-attribute-note-d">
+The attribute <a href="#membership-d.complete">complete</a> is interpreted as for the general <a href="#term-collection">collection membership</a> relation.
+
+<div class="anexample">
+<pre class="codeexample">
+entity(d1, [prov:type='prov:Dictionary' ]) // d1 is a dictionary, with unknown content
+entity(d2, [prov:type='prov:Dictionary' ]) // d2 is a dictionary, with unknown content
+
+entity(e1)
+entity(e2)
+
+memberOf(d1, {("k1", e1), ("k2", e2)} )
+memberOf(d2, {("k1", e1), ("k2", e2)}, true)
+
+</pre>
+From these descriptions, we conclude:
+<ul>
+<li> <span class="name">d1</span> has the following pairs as members: <span class="name">("k1", e1), ("k2", e2)</span>, and may contain others.
+<li> <span class="name">d2</span> exactly has the following pairs as members: <span class="name">("k1", e1), ("k2", e2)</span>, and does not contain any other.
+</ul>
+<p> Thus, the membership of <span class="name">d1</span> is only partially known.</p>
+</div>
+
+</section> <!-- Membership -->
+
+
+<section id="term-dictionary-insertion">
+<h3>Dictionary Insertion</h3>
+
+<span class="glossary-ref" data-ref="glossary-insertion"></span>
+
+<p><div class="attributes" id="attributes-derivedByInsertionFrom">
+<p>An <dfn title="derivedByInsertionFrom">Insertion</dfn> relation<span class="withPn">, written <span class="pnExpression">derivedByInsertionFrom(id; d2, d1, {(key_1, e_1), ..., (key_n, e_n)}, attrs)</span>,</span> has:</p>
+<ul>
+<li><span class='attribute' id="insertion.id">id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute' id="insertion.after">after</span>: an identifier (<span class="name">d2</span>) for the dictionary <em>after</em> insertion; </li>
+<li><span class='attribute' id="insertion.before">before</span>: an identifier (<span class="name">d1</span>) for the dictionary <em>before</em> insertion;</li>
+<li><span class='attribute' id="insertion.key-entity-set">key-entity-set</span>: the inserted key-entity pairs <span class="name">(key_1, e_1)</span>, ..., <span class="name">(key_n, e_n)</span> in which each <span class="name">key_i</span> is a <a>value</a>, and <span class="name">e_i</span> is an identifier for the entity that has been inserted with the key;
+ each <span class="name">key_i</span> is expected to be unique for the key-entity-set;
+</li>
+<li><span class='attribute' id="insertion.attributes">attributes</span>: an OPTIONAL set (<span class="name">attrs</span>) of attribute-value pairs representing additional information about this relation.</li>
+</ul>
+</div>
+
+<p>
+An Insertion relation <span class="name">derivedByInsertionFrom(id; d2, d1, {(key_1, e_1), ..., (key_n, e_n)})</span> states that <span class="name">d2</span> is the dictionary
+following the insertion of pairs <span class="name">(key_1, e_1)</span>, ..., <span class="name">(key_n, e_n)</span> into dictionary <span class="name">d1</span>.</p>
+
+
+<div class="anexample">
+<pre class="codeexample">
+entity(d0, [prov:type='prov:EmptyDictionary' ]) // d0 is an empty dictionary
+entity(e1)
+entity(e2)
+entity(e3)
+entity(d1, [prov:type='prov:Dictionary' ])
+entity(d2, [prov:type='prov:Dictionary' ])
+
+derivedByInsertionFrom(d1, d0, {("k1", e1), ("k2", e2)})
+derivedByInsertionFrom(d2, d1, {("k3", e3)})
+</pre>
+From this set of descriptions, we conclude:
+<ul>
+<li> <span class="name">d0</span> is the set <span class="name">{ }</span>
+<li> <span class="name">d1</span> is the set <span class="name">{ ("k1", e1), ("k2", e2) }</span>
+<li> <span class="name">d2</span> is the set <span class="name">{ ("k1", e1), ("k2", e2), ("k3", e3) }</span>
+</ul>
+</div>
+
+<p>Insertion provides an "update semantics" for the keys that are already present in a dictionary,
+since a new pair replaces an existing pair with the same key in the new dictionary. This is illustrated by the following example.</p>
+
+<div class="anexample">
+<pre class="codeexample">
+entity(d0, [prov:type='prov:EmptyDictionary' ]) // d0 is an empty dictionary
+entity(e1)
+entity(e2)
+entity(e3)
+entity(d1, [prov:type='prov:Dictionary' ])
+entity(d2, [prov:type='prov:Dictionary' ])
+
+derivedByInsertionFrom(d1, d0, {("k1", e1), ("k2", e2)})
+derivedByInsertionFrom(d2, d1, {("k1", e3)})
+</pre>
+ This is a case of <em>update</em> of <span class="name">e1</span> to <span class="name">e3</span> for the same key, <span class="name">"k1"</span>. <br/>
+ From this set of descriptions, we conclude:
+<ul>
+<li> <span class="name">d0</span> is the set <span class="name">{ }</span>
+<li> <span class="name">d1</span> is the set <span class="name">{ ("k1", e1), ("k2", e2) }</span>
+<li> <span class="name">d2</span> is the set <span class="name">{ ("k1", e3), ("k2", e2) }</span>
+</ul>
+</div>
+
+</section> <!-- insertion -->
+
+
+<section id="term-dictionary-removal">
+<h3>Dictionary Removal</h3>
+
+<span class="glossary-ref" data-ref="glossary-removal"></span>
+
+
+<p>
+<div class="attributes" id="attributes-derivedByRemovalFrom">
+<p> A <dfn title="derivedByRemovalFrom">Removal</dfn> relation, written <span class="pnExpression">derivedByRemovalFrom(id; d2, d1, {key_1, ... key_n}, attrs)</span>, has:</p>
+<ul>
+<li><span class='attribute' id="removal.id">id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute' id="removal.after">after</span>: an identifier (<span class="name">d2</span>) for the dictionary <em>after</em> the deletion; </li>
+<li><span class='attribute' id="removal.before">before</span>: an identifier (<span class="name">d1</span>) for the dictionary <em>before</em> the deletion;</li>
+<li><span class='attribute' id="removal.key-set">key-set</span>: a set of deleted keys <span class="name">key_1</span>, ..., <span class="name">key_n</span>, for which each <span class="name">key_i</span> is a <a>value</a>;</li>
+<li><span class='attribute' id="removal.attributes">attributes</span>: an OPTIONAL set (<span class="name">attrs</span>) of attribute-value pairs representing additional information about this relation.</li>
+</ul>
+</div>
+
+<p>A Removal relation <span class="name">derivedByRemovalFrom(id; d2,d1, {key_1, ..., key_n})</span> states that <span class="name">d2</span> is the dictionary following the removal of the set of pairs corresponding to keys <span class="name">key_1...key_n</span> from <span class="name">d1</span>.
+
+<div class="anexample">
+<pre class="codeexample">
+entity(d0, [prov:type="prov:EmptyDictionary"]) // d0 is an empty dictionary
+entity(e1)
+entity(e2)
+entity(e3)
+entity(d1, [prov:type="prov:Dictionary"])
+entity(d2, [prov:type="prov:Dictionary"])
+
+derivedByInsertionFrom(d1, d0, {("k1", e1), ("k2",e2)})
+derivedByInsertionFrom(d2, d1, {("k3", e3)})
+derivedByRemovalFrom(d3, d2, {"k1", "k3"})
+</pre>
+From this set of descriptions, we conclude:
+<ul>
+<li><span class="name">d0</span> is the set <span class="name">{ }</span>
+<li><span class="name">d1</span> is the set <span class="name">{ ("k1", e1), ("k2", e2) }</span>
+<li><span class="name">d2</span> is the set <span class="name">{ ("k1", e1), ("k2", e2), ("k3", e3) }</span>
+<li><span class="name">d3</span> is the set <span class="name">{ ("k2", e2) }</span>
+</ul>
+
+
+</div>
+
+</section> <!-- removal -->
+
+
+<p>Further considerations: </p>
+
+<ul>
+
+<!--
+<li>The state of a dictionary (i.e., the set of key-entity pairs it contains) at a given point in a sequence of operations is never stated explicitly. Rather, it can be obtained by querying the chain of derivations involving insertions and removals. Entity type <span class="name">emptyDictionary</span> can be used in this context as it marks the start of a sequence of dictionary operations.</li>
+-->
+
+<li>The representation of a dictionary through these relations makes no assumption regarding the underlying data structure used to store and manage dictionaries. In particular, no assumptions are needed regarding the mutability of a data structure that is subject to updates. Entities, however, are immutable and this applies to those entities that represent dictionaries. This is reflected in the constraints listed in [[PROV-CONSTRAINTS]]. </li>
+</ul>
+
+
+</section> <!-- end dictionaries-->
+</section>
+<section>
+<h2>PROV Notation</h2>
+
+<section id="expression-collection-membership">
+<h3>Membership</h3>
+
+<!--
+<div class="grammar">
+ <span class="nonterminal">membershipExpression</span> ::=
+<span class="name">isMemberOf</span>
+ <span class="name">(</span>
+ <span class="optional"><span class="nonterminal">identifier</span>
+ <span class="name">,</span></span>
+<span class="nonterminal">cIdentifier</span>
+ <span class="name">,</span>
+ <span class="name">{</span>
+ <span class="nonterminal">keyValuePairs</span>
+ <span class="name">}</span>
+<span class="nonterminal">optional-attribute-values</span>
+ <span class="name">)</span>
+ <br>
+</div>
+-->
+
+<table class="grammar">
+<tbody class="grammar-ref" data-ref="prod-dictMembershipExpression"></tbody>
+<tbody class="grammar-ref" data-ref="prod-complete"></tbody>
+<tbody class="grammar-ref" data-ref="prod-entitySet"></tbody>
+</table>
+
+
+<p>The following table summarizes how each constituent of a PROV-DM Membership maps to a non-terminal.</p>
+
+<div style="text-align: left; ">
+<table class="thinborder" style="margin-left: auto; margin-right: auto;">
+<tr><td><b>Dictionary Membership</b></td><td><b>Non-Terminal</b></td></tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#membership-d.id"><span class='attribute' id="membership-d.id">id</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-optionalIdentifier">optionalIdentifier</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#membership-d.dictionary"><span class='attribute' id="membership-d.dictionary">dictionary</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-dIdentifier">dIdentifier</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#membership-d.key-entity-set"><span class='attribute' id="membership-d.key-entity-set">key-entity-set</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-keyEntitySet">keyEntitySet</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#membership-d.complete"><span class='attribute' id="membership-d.complete">complete</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-complete">complete</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#membership-d.attributes"><span class='attribute' id="membership-d.attributes">attributes</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-optionalAttributeValuePairs">optionalAttributeValuePairs</a></code></td></tr>
+</table>
+</div>
+
+
+
+<div class="anexample">
+ <pre class="codeexample">
+ memberOf(mId, c, {e1, e2, e3}, []) // Collection membership
+ memberOf(mId, c, {("k4", v4), ("k5", v5)}, []) // Dictionary membership
+ </pre>
+<p> Here
+ <span class="name">mid</span> is the optional membership identifier,
+ <span class="name">c</span> is the identifier for the collection whose membership is stated,
+ <span class="name"> {("k4", v4), ("k5", v5)}</span> is the set of key-value pairs that are members of
+ <span class="name">c</span>,
+ and <span class="name">[]</span> is the optional (empty) set of attributes. </p>
+The remaining examples show cases for Dictionaries, where some of the optionals are omitted. Key-entity sets are replaced with Entity sets for the corresponding generic Collections examples.
+
+<pre class="codeexample">
+memberOf(c3, {("k4", v4), ("k5", v5)})
+memberOf(c3, {("k4", v4)})
+memberOf(c3, {("k4", v4)}, false)
+memberOf(c3, {("k4", v4)}, true)
+memberOf(c3, {("k4", v4), ("k5", v5)},[])
+memberOf(c3, {("k4", v4), ("k5", v5)},true, [])
+</pre>
+</div>
+
+</section>
+
+
+
+<section id="expression-collection-insertion">
+<h3>Insertion</h3>
+
+<!--
+<div class="grammar">
+ <span class="nonterminal">derivationByInsertionFromExpression</span> ::=
+<span class="name">derivedByInsertionFrom</span>
+ <span class="name">(</span>
+ <span class="optional"><span class="nonterminal">identifier</span>
+ <span class="name">,</span></span>
+<span class="nonterminal">cIdentifier</span>
+ <span class="name">,</span>
+<span class="nonterminal">cIdentifier</span>
+ <span class="name">,</span>
+ <span class="name">{</span>
+ <span class="nonterminal">keyValuePairs</span>
+ <span class="name">}</span>
+<span class="nonterminal">optional-attribute-values</span>
+ <span class="name">)</span>
+</div>
+-->
+
+<table class="grammar">
+<tbody class="grammar-ref" data-ref="prod-insertionExpression"></tbody>
+<tbody class="grammar-ref" data-ref="prod-keyEntitySet"></tbody>
+</table>
+
+
+<p>The following table summarizes how each constituent of a PROV-DM Insertion maps to a non-terminal.</p>
+<div style="text-align: left; ">
+<table class="thinborder" style="margin-left: auto; margin-right: auto;">
+<tr><td><b>Insertion</b></td><td><b>Non-Terminal</b></td></tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#insertion.id"><span class='attribute' id="insertion.id">id</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-optionalIdentifier">optionalIdentifier</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#insertion.after"><span class='attribute' id="insertion.after">after</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-cIdentifier">cIdentifier</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#insertion.before"><span class='attribute' id="insertion.before">before</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-cIdentifier">cIdentifier</a></code></td></tr>
+
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#insertion.key-entity-set"><span class='attribute' id="insertion.key-entity-set">key-entity-set</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-keyEntitySet">keyEntitySet</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#insertion.attributes"><span class='attribute' id="insertion.attributes">attributes</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-optionalAttributeValuePairs">optionalAttributeValuePairs</a></code></td></tr>
+</table>
+</div>
+
+
+<div class="anexample">
+ <pre class="codeexample">
+ derivedByInsertionFrom(id; c1, c, {("k1", v1), ("k2", v2)}, [])
+ </pre>
+<p> Here
+ <span class="name">id</span> is the optional insertion identifier,
+ <span class="name">c1</span> is the identifier for the collection after the insertion,
+ <span class="name">c</span> is the identifier for the collection before the insertion,
+ <span class="name"> {("k1", v1), ("k2", v2)}</span> is the set of key-value pairs that have been inserted in
+ <span class="name">c</span>,
+ and <span class="name">[]</span> is the optional (empty) set of attributes. </p>
+The remaining examples show cases where some of the optionals are omitted.
+
+ <pre class="codeexample">
+ derivedByInsertionFrom(c1, c, {("k1", v1), ("k2", v2)})
+ derivedByInsertionFrom(c1, c, {("k1", v1)})
+ derivedByInsertionFrom(c1, c, {("k1", v1), ("k2", v2)}, [])
+</pre>
+</div>
+
+
+</section>
+
+<section id="expression-collection-removal">
+<h3>Removal</h3>
+
+<!--
+<div class="grammar">
+ <span class="nonterminal">derivationByRemovalFromExpression</span> ::=
+<span class="name">derivedByRemovalFrom</span>
+ <span class="name">(</span>
+ <span class="optional"><span class="nonterminal">identifier</span>
+ <span class="name">,</span></span>
+<span class="nonterminal">cIdentifier</span>
+ <span class="name">,</span>
+<span class="nonterminal">cIdentifier</span>
+ <span class="name">,</span>
+ <span class="name">{</span>
+ <span class="nonterminal">keySet</span>
+ <span class="name">}</span>
+<span class="nonterminal">optional-attribute-values</span>
+ <span class="name">)</span>
+ <br>
+</div>
+-->
+
+<table class="grammar">
+<tbody class="grammar-ref" data-ref="prod-removalExpression"></tbody>
+<tbody class="grammar-ref" data-ref="prod-keySet"></tbody>
+</table>
+
+<p>The following table summarizes how each constituent of a PROV-DM Removal maps to a non-terminal.</p>
+<div style="text-align: left; ">
+<table class="thinborder" style="margin-left: auto; margin-right: auto;">
+<tr><td><b>Removal</b></td><td><b>Non-Terminal</b></td></tr>
+<tr><td style="border-width: 0px; "></td><td style="border-width: 0px; "></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#removal.id"><span class='attribute' id="removal.id">id</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-optionalIdentifier">optionalIdentifier</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#removal.after"><span class='attribute' id="removal.after">after</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-cIdentifier">cIdentifier</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#removal.before"><span class='attribute' id="removal.before">before</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-cIdentifier">cIdentifier</a></code></td></tr>
+
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#removal.key-set"><span class='attribute' id="removal.key-set">key-set</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-keySet">keySet</a></code></td></tr>
+
+<tr><td><a href="http://www.w3.org/TR/prov-dm/#removal.attributes"><span class='attribute' id="removal.attributes">attributes</span></a></td><td><code class="content"><a class="grammarRef" href="#prod-optionalAttributeValuePairs">optionalAttributeValuePairs</a></code></td></tr>
+</table>
+</div>
+
+
+
+
+<div class="anexample">
+ <pre class="codeexample">
+ derivedByRemovalFrom(id; c3, c, {"k1", "k3"}, [])
+ </pre>
+<p> Here
+ <span class="name">id</span> is the optional removal identifier,
+ <span class="name">c1</span> is the identifier for the collection after the removal,
+ <span class="name">c</span> is the identifier for the collection before the removal,
+ <span class="name"> {("k1", v1), ("k2", v2)}</span> is the set of key-value pairs that have been removed from
+ <span class="name">c</span>,
+ and <span class="name">[]</span> is the optional (empty) set of attributes. </p>
+ The remaining examples show cases where some of the optionals are omitted.
+
+ <pre class="codeexample">
+ derivedByRemovalFrom(c3, c1, {"k1", "k3"})
+ derivedByRemovalFrom(c3, c1, {"k1"})
+ derivedByRemovalFrom(c3, c1, {"k1", "k3"}, [])
+</pre>
+ </div>
+
+</section>
+
+</section>
+
+<section id="dictionary-constraints">
+<h2>Dictionary Constraints</h2>
+
+
+ <div class="note">
+ As resolved at F2F3, the material in this section goes, if
+ anywhere, into the PROV-COLLECTIONS note.
+ </div>
+
+<hr>
+
+<p id='membership-as-insertion_text'>Membership is a convenience notation, since it can be expressed in terms of an insertion into some dictionary. The membership definition is formalized by <a class="rule-ref" href="#membership-as-insertion"><span/></a>.</p>
+
+<div class='definition' id='membership-as-insertion'>
+<p>
+ <span class="name">memberOf(d, {(k1, v1), ...})</span> holds
+<span class='conditional'>IF AND ONLY IF</span> there exists a dictionary <span class="name">d0</span>, such that
+<span class="name">derivedByInsertionFrom(d, d0, {(k1, v1), ...})</span>.</p>
+</div>
+
+<p>
+
+<hr>
+
+<p id='dictionary-unique-derivation_text'>A dictionary may be obtained by insertion or removal, or said to satisfy the membership relation.
+To provide an interpretation of dictionaries, PROV-DM
+ restricts one dictionary to be involved in a single derivation by insertion or removal, or to one membership relation.
+PROV-DM does not provide an interpretation for statements that consist of two (or more) insertion, removal, membership relations that result in the same dictionary.</p>
+
+
+
+<p>The following constraint ensures unique derivation.</p>
+
+
+<div class='note'> The following constraint is unclear.</div>
+<div class='constraint' id='dictionary-unique-derivation'>
+<p>A dictionary MUST NOT be derived through multiple insertions, removal,
+ or membership relations. </p>
+</div>
+
+<div class="anexample">
+Consider the following statements about three dictionaries.
+ <pre class="codeexample">
+entity(d1, [prov:type='prov:Dictionary'])
+entity(d2, [prov:type='prov:Dictionary'])
+entity(d3, [prov:type='prov:Dictionary'])
+
+
+derivedByInsertionFrom(d3, d1, {("k1", e1), ("k2", e2)})
+derivedByInsertionFrom(d3, d2, {("k3", e3)})
+</pre>
+<p>There is no interpretation for such statements since <span class="name">d3</span> is derived multiple times by insertion.</p>
+</div>
+
+
+<div class="anexample">
+<p>As a particular case, dictionary <span class="name">d</span> is derived multiple times from the same <span class="name">d1</span>. </p>
+<pre class="codeexample">
+derivedByInsertionFrom(id1, d, d1, {("k1", e1), ("k2", e2)})
+derivedByInsertionFrom(id2, d, d1, {("k3", e3), ("k4", e4)})
+</pre>
+<p>The interpretation of such statements is also unspecified. </p>
+<p>To describe the insertion of the 4 key-entity pairs, one would instead write:</p>
+<pre class="codeexample">
+derivedByInsertionFrom(id1, d, d1, {("k1", e1), ("k2", e2), ("k3", e3), ("k4", e4)})
+</pre>
+</div>
+
+The same is true for any combination of insertions, removals, and membership relations:
+<div class="anexample">
+<p>The following statements</p>
+<pre class="codeexample">
+derivedByInsertionFrom(d, d1, {("k1", e1)})
+derivedByRemovalFrom(d, d2, {"k2"})
+</pre>
+have no interpretation.
+Nor have the following:
+<pre class="codeexample">
+derivedByInsertionFrom(d, d1, {("k1", e1)})
+memberOf(d, {"k2",e2})
+</pre>
+</div>
+
+
+
+<section id="dictionary-branching">
+<h4>Dictionary branching</h4>
+
+It is allowed to have multiple derivations from a single root dictionary, as long as the resulting entities are distinct, as shown in the following example.
+
+<div class="anexample">
+<pre class="codeexample">
+entity(d0, [prov:type='prov:EmptyDictionary']) // d0 is an empty dictionary
+entity(d1, [prov:type='prov:Dictionary'])
+entity(d2, [prov:type='prov:Dictionary'])
+entity(d3, [prov:type='prov:Dictionary'])
+entity(e1)
+entity(e2)
+entity(e3)
+
+derivedByInsertionFrom(d1, d0, {("k1", e1)})
+derivedByInsertionFrom(d2, d0, {("k2", e2)})
+derivedByInsertionFrom(d3, d1, {("k3", e3)})
+</pre>
+From this set of statements, we conclude:
+<pre class="codeexample">
+ d1 = { ("k1", e1) }
+ d2 = { ("k2", e2) }
+ d3 = { ("k1", e1), ("k3", e3)}
+</pre>
+</div>
+
+</section>
+
+
+
+<section id="dictionaries-and-derivation">
+
+
+<h4>Dictionaries and Weaker Derivation Relation</h4>
+
+<p>Since a
+set of statements regarding a dictionary's evolution may be
+incomplete, so is the reconstructed state obtained by querying those
+statements. In general, all statements reflect partial knowledge regarding a sequence of data transformation events. In the particular case of dictionary evolution, in which some of the state changes may have been missed, the more generic derivation relation should be used to signal that some updates may have occurred, which cannot be expressed as insertions or removals. The following example illustrates this.</p>
+
+
+
+ <div class="anexample">
+In the example, the state of <span class="name">d2</span> is only partially known because the dictionary is constructed from partially known other dictionaries.
+ <pre class="codeexample">
+entity(d0, [prov:type='prov:EmptyDictionary']) // d0 is an empty dictionary
+entity(d1, [prov:type='prov:Dictionary'])
+entity(d2, [prov:type='prov:Dictionary'])
+entity(d3, [prov:type='prov:Dictionary'])
+entity(e1)
+entity(e2)
+
+derivedByInsertionFrom(d1, d0, {("k1", e1)})
+wasDerivedFrom(d2, d1)
+derivedByInsertionFrom(d3, d2, {("k2", e2)})
+ </pre>
+From this set of statements, we conclude:
+<ul>
+<li> <span class="name">d1 = { ("k1", e1) }</span>
+<li> <span class="name">d2</span> is somehow derived from <span class="name">d1</span>, but the precise sequence of updates is unknown
+<li> <span class="name">d3</span> includes <span class="name">("k2", e2)</span> but the earlier "gap" leaves uncertainty regarding <span class="name">("k1", e1)</span> (it may have been removed) or any other pair that may have been added as part of the derivation activities.
+</ul>
+ </div>
+
+</section>
+
+
+<div class='note'>
+ Do the insertion/removal derivation steps imply wasDerivedFrom,
+ wasVersionOf, alternateOf?
+ </div>
+
+
+
+<section id="dictionaries-and-contents">
+
+
+<h4>Dictionaries and Contents</h4>
+
+<div class="note">
+Axiomatisation of dictionaries to be expressed here. See <a href="./working-copy/wd6-collections-constraints.html">here</a>.
+</div>
+</section>
+
+</section> <!-- dictionary-constraints -->
+
+
+<div id="glossary_div" class="remove">
+<!-- glossary loaded from glossary.js will be hooked up here,
+ class remove, will remove this element from the final output.
+-->
+</div>
+<div id="grammar_div" class="remove">
+<!-- grammar loaded from glossary.js will be hooked up here,
+ class remove, will remove this element from the final output.
+-->
+</div>
+
+
+
+
+ <section id="description-collections-terms"> <!-- section 3.1 -->
+ <!-- This section was taken from http://dvcs.w3.org/hg/prov/file/a1d1ff134131/ontology/prov-o-html-sections/description-collections.inc.html -->
+
+ <!-- Khalid's desired take away: Relations between the starting point classes can be specified using the starting object properties. However, in certain cases, users may want to provide elaborated info
+rmation about such relations. Qualified classes and properties provides users with the means to do so. -->
+ <-p><strong>Collection classes and properties</strong> are specializations of the Starting Point and Qualified terms that describe the provenance of collections as key-value pairs that are inserted a
+nd removed to create new collections.
+ The classes and properties in this category are listed below and are discussed in <a href="#description-collections-terms">Section 3.4</a>.</p>
+ <div id="prov-collections-owl-terms-at-a-glance">
+ need to include aquarius:"includes/at-a-glance-collections.html"
+ </div>
+
+
+ <h3>Collections Terms</h3>
+
+ <p> A <code><a class="qname"
+href='#Dictionary'>prov:Dictionary</a></code> is an <code
+class="repeated">prov:Entity</code> that acts as a container to some members,
+which are themselves entities.
+Specifically, a dictionary is composed of set of key-value pairs, where a
+literal key is used to identify a constituent entity within the dictionary.
+
+To illustrate this, the example below describes a dictionary <code>:c1</code>
+that has as members the two key value pairs <code>("k1", :e1)</code>
+and <code>("k2", :e2)</code>.
+</p>
+
+<div about="#narrative-example-dictionaries-1" typeof="prov:Entity" class="exampleOuter" xmlns:prov="http://www.w3.org/ns/prov#">
+ <pre rel="prov:wasQuotedFrom" resource="http://dvcs.w3.org/hg/prov/raw-file/tip/examples/eg-26-provo-collections-narrative/rdf/membership.ttl"
+ class="example">{% escape %}{% include "includes/prov/examples/eg-26-provo-collections-narrative/rdf/membership.ttl" %}{% endescape %}</pre>
+</div>
+
+<p>It is worth noting that <code>:c1</code> MAY also
+have other members (i.e. <code class="repeated">prov:knownMembership</code> is
+not functional). A dictionary MAY be empty and thus not have any known
+memberships, in which case it SHOULD be described as an instance of the
+subclass <a class="qname"
+href='#EmptyDictionary'><code>prov:EmptyDictionary</code></a>.
+</p>
+
+ <p> To describe the provenance of a dictionary, PROV-O provides two
+kinds of involvements: <code><a class="qname"
+href="#qualifiedInsertion">prov:qualifiedInsertion</a></code> is used to
+describe that a dictionary was obtained from an existing dictionary by
+<em>inserting</em> a set of key-value pairs. <code><a class="qname"
+href="#qualifiedRemoval">prov:qualifiedRemoval</a></code> is used to specify
+that a given dictionary was obtained from an existing dictionary by
+<em>removing</em> a set of key-value pairs. The example below specifies that
+the dictionary <code>:c1</code> was obtained from the empty dictionary
+<code>:c</code> by <em>inserting</em> the key-value pairs <code>("k1",
+:e1)</code> and <code>("k2", :e2)</code>.
+</p>
+
+<div about="#narrative-example-dictionaries-2" typeof="prov:Entity" class="exampleOuter" xmlns:prov="http://www.w3.org/ns/prov#">
+<pre rel="prov:wasQuotedFrom" resource="http://dvcs.w3.org/hg/prov/raw-file/tip/examples/eg-26-provo-collections-narrative/rdf/insertion.ttl"
+ class="example">{% escape %}{% include "includes/prov/examples/eg-26-provo-collections-narrative/rdf/insertion.ttl" %}{% endescape %}</pre>
+</div>
+
+
+ <p>
+ Similarly, the example below specifies that the dictionary
+ <code>:c3</code> was obtained by <em>removing</em> the key-value pairs associated with
+ the keys <code>"k1"</code> and <code>"k2"</code> from the dictionary
+ <code>:c2</code>. Thus, <code>:c3</code> does not contain the
+ members <code>("k1", :e1)</code> and <code>("k2",
+ :e2(</code> from <code>:c2</code>.
+ </p>
+
+<div about="#narrative-example-dictionaries-3" typeof="prov:Entity" class="exampleOuter" xmlns:prov="http://www.w3.org/ns/prov#">
+ <pre rel="prov:wasQuotedFrom" resource="http://dvcs.w3.org/hg/prov/raw-file/tip/examples/eg-26-provo-collections-narrative/rdf/removal.ttl"
+ class="example">{% escape %}{% include "includes/prov/examples/eg-26-provo-collections-narrative/rdf/removal.ttl" %}{% endescape %}</pre>
+</div>
+
+ </section>
+
+
+<section id="cross-reference-collection-terms">
+ <h3>Collection Terms</h3>
+ <p>The terms used to describe the provenance of collections of key-value pairs are discussed in <a href="#description-collections-terms">Section 3.4</a>.</p>
+ need to include aquarius:"includes/at-a-glance-collections.html"
+ need to include aquarius:"includes/cross-reference-collections.html"
+</section>
+
+
+<section class="appendix">
+ <h2>Acknowledgements</h2>
+ <p>
+ WG membership to be listed here.
+ </p>
+ </section>
+
+ </body>
+</html>
+
+
+