--- a/model/working-copy/wd5-prov-dm-collections.html Wed Mar 21 10:42:41 2012 +0000
+++ b/model/working-copy/wd5-prov-dm-collections.html Wed Mar 21 10:43:06 2012 +0000
@@ -206,284 +206,6 @@
<section id="term-Collection">
<h3>Collections</h3>
-<p><strong>Collection relations and entity types</strong> address the need to describe the evolution of entities that have a collection structure, that is, which may contain other entities. The intent of these relations and entity types is to capture the <em>history of changes that occurred to a collection</em>. Indirectly, such history provides a way to reconstruct, with some limitations discussed <a href="#term-collection-weak-derivation">below</a>, the contents of a collection entity. Thus, for the purpose of provenance a collection entity is viewed an immutable representation of the state of a collection data structure, following a sequence of insertion and deletion operations.
-
-<br/>A collection entity is an entity that has a logical internal structure consisting of key-value pairs, often referred to as a <strong>map</strong>. This collection type provides a generic indexing structure that can be used to model commonly used data structures, including associative lists (also known as "dictionaries" in some programming languages), 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).
-
-<section id="term-collection-types">
-<h3>Collection types</h3>
-
-The following new entity types are introduced:
-
-<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(c, [prov:type="EmptyCollection"]) // e is an empty collection
- entity(c1, [prov:type="Collection"]) // c1 is a collection, with unknown content
-</pre>
-</div>
-
-</section> <!-- end of collection-types -->
-
-
-<section id="term-collection-insertion">
-<h3>Insertion</h3>
-
-
-<strong>Derivation-by-Insertion</strong> relation <span class="name">derivedByInsertionFrom(c2, c1, k, v)</span> states that <span class="name">c2</span> is the state of the collection
-following the insertion of pair <span class="name">(k,v)</span> into collection <span class="name">c1</span>.
-
-<p> A Derivation-by-Insertion relation<span class="withPn">, written <span class="pnExpression"> derivedByInsertionFrom(id, collAfter, collBefore, key, value, attrs)</span>,</span> contains:</p>
-<ul>
-<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
-<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> insertion; </li>
-<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> insertion;</li>
-<li><span class='attribute'>key</span>: the key that has been inserted</li>
-<li><span class='attribute'>value</span>: an identifier for the value that has been inserted with the key.</li>
-<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
-</ul>
-
-
-<div class="anexample">
-<pre class="codeexample">
- entity(c, [prov:type="EmptyCollection"]) // c is an empty collection
- entity(v1)
- entity(v2)
- entity(c1, [prov:type="Collection"])
- entity(c2, [prov:type="Collection"])
-
- derivedByInsertionFrom(c1, c, "k1", v1)
- derivedByInsertionFrom(c2, c1, "k2", v2)
-</pre>
- From this set of assertions, we conclude:
- <pre class="codeexample">
- c = { }
- c1 = { ("k1",v1) }
- c2 = { ("k1",v1), ("k2", v2) }
- </pre>
-</div>
-
-</section>
-
-
-<section id="term-collection-removal">
-<h3>Removal</h3>
-
-<strong>Derivation-by-Removal</strong> relation <span class="name">derivedByRemovalFrom(c2,c1, k)</span> states that <span class="name">c2</span> is the state of the collection following the removal of the pair corresponding to key <span class="name">k</span> from <span class="name">c1</span>.
-
-<p> A Derivation-by-Removal relation, written <span class="pnExpression"> derivedByRemovalFrom(id, collAfter, collBefore, key, attrs)</span>, contains:</p>
-<ul>
-<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
-<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> the deletion; </li>
-<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> the deletion;</li>
-<li><span class='attribute'>key</span>: the key corresponding to the (key, value) pair that has been deleted from the collection.</li>
-<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
-</ul>
-
-
-<div class="anexample">
-<pre class="codeexample">
- entity(c, [prov:type="EmptyCollection"]) // e is an empty collection
- entity(v1)
- entity(v2)
- entity(c1, [prov:type="Collection"])
- entity(c2, [prov:type="Collection"])
-
- derivedByInsertionFrom(c1, c, "k1", v1)
- derivedByInsertionFrom(c2, c1, "k2", v2)
- derivedByRemovalFrom(c3, c2, k1)
-</pre>
- From this set of assertions, we conclude:
- <pre class="codeexample">
- c = { }
- c1 = { ("k1",v1) }
- c2 = { ("k1",v1), ("k2", v2) }
- c3 = { ("k2",v2) }
- </pre>
-
-
-</div>
-
-</section>
-
-<section id="term-collection-containment">
-<h3>Containment</h3>
-
-<strong>Containment</strong> relation <span class="name">contained(c, k, v)</span> states that collection <span class="name">c</span> contained pair <span class="name">(k,v)</span>.
-
-
-<p> A Containment relation, written <span class="pnExpression"> contained(id, coll, key, values, attrs)</span>, contains:</p>
-<ul>
-<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
-<li><span class='attribute'>after</span>: an identifier for the collection whose members are asserted; </li>
-<li><span class='attribute'>key</span>: the key of the pair contained by the collection;</li>
-<li><span class='attribute'>value</span>: an identifier for the value corresponding to the key;</li>
-<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
-</ul>
-
-The insertion and removal relations make insertions and removals explicit as part of the history of a collection. The containment relation is typically used when the content of a collection is at least partially known, but no insertions have been witnessed. This is the case for example of a workflow block that produces a new collection <span class="name">c</span> with known content. In this case,
-<span class="name">contained(c,k, v)</span> asserts that <span class="name">c</span> is known to contain <span class="name">(k,v)</span>, regardless of explicit insertion operations.
-
-
-<div class="anexample">
-<pre class="codeexample">
- entity(c, [prov:type="Collection"]) // e is a collection, with unknown content
- activity(a)
- wasGeneratedBy(c,a) // a produced c
-
- entity(v1)
- entity(v2)
- contained(c, "k1", v1)
- contained(c, "k1", v2) // c is contains at least ("k1", v1) and ("k2", v2)
-
- entity(v2)
- entity(c1, [prov:type="Collection"])
-
- derivedByInsertionFrom(c1, c, "k3", v3)
-</pre>
- From this set of assertions, we conclude:
- <pre class="codeexample">
- c contains ("k1", v1), ("k2", v2)
- c1 contains ("k1", v1), ("k2", v2), ("k3", v3)
- </pre>
- Note that the state of <span class="name">c1</span> after these assertions is only partially known, because the initial state of <span class="name">c</span> is unknown. Alternatively, had the first assertion been
- <span class="name"> entity(c, [prov:type="EmptyCollection"])</span>,
- one would conclude that, based on these assertions, <span class="name">c1 = {("k1", v1) ("k2", v2), ("k3",v3)}</span>.
-</div>
-
-</section>
-
-Further considerations: <p/>
-
-<ul>
-<li>In Key-Value pairs, Keys are <a href="#term-value">values</a>, and Values are entities. This allows expressing nested collections, that is, collections whose values include entities of type collection.</li>
-
-<li>As the relation names suggest, insertion and removal relations are a particular case of <a href="#Derivation-Relation">derivation</a>.</li>
-
-
-
-<li>The state of a collection (i.e., the set of key-value 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">emptyCollection</span> can be used in this context as it marks the start of a sequence of collection operations.</li>
-
-
-<li>The representation of a collection through these relations, makes no assumption regarding the underlying data structure used to store and manage collections. 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 collections. This is reflected in the constraints listed in Part II. </li>
-</ul>
-
-<section id="collection-convenience-relations">
-<h3>Convenience relations</h3>
-
-As a convenience, corresponding relations for <em>bulk operations</em> involving a set of key-value pairs are introduced, as follows.
-
-<p> A Derivation-by-Bulk-Insertion relation <span class="withPn">, written <span class="pnExpression"> derivedByBulkInsertionFrom(id, collAfter, collBefore, key-value-set, attrs)</span>,</span> contains:</p>
-<ul>
-<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
-<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> insertion; </li>
-<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> insertion;</li>
-<li><span class='attribute'>key-value-set</span>: a set of inserted key-value pairs, of the form {(key_1, value_1), ..., (key_n, value_n)}</li>
-<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
-</ul>
-
-<p> A Derivation-by-Bulk-Removal relation, written <span class="pnExpression"> derivedByBulkRemovalFrom(id, collAfter, collBefore, key-set, attrs)</span>, contains:</p>
-<ul>
-<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
-<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> the deletion; </li>
-<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> the deletion;</li>
-<li><span class='attribute'>key-set</span>: a set of deleted keys, of the form {key_1,..., key_n}</li>
-<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
-</ul>
-
-
-<p> A Bulk-Containment relation, written <span class="pnExpression"> containedBulk(id, coll, key-value-set, attrs)</span>, contains:</p>
-<ul>
-<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
-<li><span class='attribute'>after</span>: an identifier for the collection whose members are asserted; </li>
-<li><span class='attribute'>key-value-set</span>: a set of key-value pairs contained in the collection, of the form {(key_1, value_1), ..., (key_n, value_n)}</li>
-<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
-</ul>
-
-<div class="anexample">
-<pre class="codeexample">
- entity(c, [prov:type="EmptyCollection"]) // e is a collection, with unknown content
-
- entity(v1)
- entity(v2)
- derivedByBulkInsertionFrom(c1, c, {("k1", v1), ("k2", v2)})
- derivedByInsertionFrom(c2, c1, "k3", v3)
- derivedByBulkRemovalFrom(c3, c1, {"k1", "k3"})
-
- containedBulk(c3, {("k4", v4), ("k5", v5)})
-</pre>
- From this set of assertions, we conclude:
- <pre class="codeexample">
- c = { }
- c1 = { ("k1", v1) ("k2", v2)}
- c2 = { ("k1", v1) ("k2", v2), ("k3", v3)}
- c3 = { ("k2", v2), ("k4", v4), ("k5", v5)}
- </pre>
-</div>
-
-
-</section> <!-- convenience relations -->
-
-<section id="term-collection-state">
-
-<h3>State of collections and use of weaker <a href="#Derivation-Relation">derivation</a> relation</h3>
-
-<p>The state of a collection is only known to the extent that a chain of derivations starting from an empty collection can be found. Since a set of assertions regarding a collection's evolution may be incomplete, so is the reconstructed state obtained by querying those assertions. In general, all assertions reflect partial knowledge reagrding a sequence of data transformation events. In the particular case of collection evolution, in which some of the state changes may have been missed, the more generic <a href="#Derivation-Relation">derivation</a> relation should be used to signal that some updates may have occurred, which cannot be precisely asserted as insertions or removals. The following two examples illustrate this.</p>
-
-<div class="anexample">
-<pre class="codeexample">
- entity(c, [prov:type="collection"]) // c is a collection, possibly not empty
- entity(v1)
- entity(v2, [prov:type="collection"]) // v2 is a collection
-
- entity(c1, [prov:type="collection"])
- entity(c2, [prov:type="collection"])
-
- derivedByInsertionFrom(c1, c, k1, v1)
- derivedByInsertionFrom(c2, c1, k2, v2)
-</pre>
- From this set of assertions, we conclude:
- <pre class="codeexample">
- c1 includes (k1,v1) but may contain additional unknown pairs
- c2 includes (k1,v1), (k2 v2) (and possibly more pairs), where v2 is a collection with unknown state
- </pre>
-
-</div>
- In the example, the state of <span class="name">c2</span> is only partially known because the collection is constructed from partially known other collections.
-
-<div class="anexample">
-<pre class="codeexample">
- entity(c, [prov:type="emptyCollection"]) // c is an empty collection
- entity(v1)
- entity(v2)
- entity(c1, [prov:type="collection"])
- entity(c2, [prov:type="collection"])
- entity(c3, [prov:type="collection"])
-
- derivedByInsertionFrom(c1, c, k1, v1)
- wasDerivedFrom(c2, c1)
- derivedByInsertionFrom(c3, c2, k2, v2)
-</pre>
- From this set of assertions, we conclude:
- <pre class="codeexample">
- c1 = { (k1,v1) }
- c2 is somehow derived from c1, but the precise sequence of updates is unknown
- c3 includes (k2 v2) but the earlier "gap" leaves uncertainty regarding (k1,v1) <br/> (it may have been removed) or any other pair that may have been added as part of the derivation activities.
- </pre>
-</div>
-
-</section> <!-- end of collections-weaker-derivation -->
-
-
-
-
-</section> <!-- end collections-->
-
<section id="collection-constraints">
<h3>PROV-DM Collection Constraints [to go in part II]</h3>
--- a/model/working-copy/wd5-prov-dm-components.html Wed Mar 21 10:42:41 2012 +0000
+++ b/model/working-copy/wd5-prov-dm-components.html Wed Mar 21 10:43:06 2012 +0000
@@ -1816,30 +1816,87 @@
<section id="component5">
<h3>Component 5: Collections</h3>
-<p><strong>Collection relations</strong> address the need to describe the evolution of entities that have a collection structure, that is, which may contain other entities. Specifically, this section exploits the built-in type for entities, called <a title="concept-collection">collection</a>, and two relations to describe the effect of adding elements to, and removing elements from, a collection entity.
-The intent of these relations and entity types is to capture the <em>history of changes that occurred to a collection</em>.
-Thus, a collection entity is an immutable representation of the state of a collection data structure following a sequence of insertion and deletion operations.
-</p>
-
-<p>A collection is an entity that has a logical internal structure consisting of key-value pairs, often referred to as a map.
-More precisely, the following entity types are introduced:
+
+<p><strong>Collection relations and entity types</strong> address the need to describe the evolution of entities that have a collection structure, that is, which may contain other entities. The intent of these relations and entity types is to capture the <em>history of changes that occurred to a collection</em>. Indirectly, such history provides a way to reconstruct, with some limitations discussed <a href="#term-collection-state">below</a>, the contents of a collection entity. Thus, for the purpose of provenance a collection entity is viewed an immutable representation of the state of a collection data structure, following a sequence of insertion and deletion operations.
+
+<br/>A collection entity is an entity that has a logical internal structure consisting of key-value pairs, often referred to as a <strong>map</strong>. This collection type provides a generic indexing structure that can be used to model commonly used data structures, including associative lists (also known as "dictionaries" in some programming languages), 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).
+
+<section id="term-collection-types">
+<h3>Collection types</h3>
+
+The following new entity types are introduced:
<ul>
- <li> <span class="name">Collection</span> denotes an entity of type collection, i.e. an entity that can participate in insertion and removal relations;
-
- <li><span class="name">EmptyCollection</span> denotes an empty collection.
+ <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>
-The following relations relate a collection <span class="name">c1</span> with a collection <span class="name">c2</span> obtained after adding or removing a new pair to (resp. from) <span class="name">c1</span>:
-
+<div class="anexample">
+<pre class="codeexample">
+ entity(c, [prov:type="EmptyCollection"]) // e is an empty collection
+ entity(c1, [prov:type="Collection"]) // c1 is a collection, with unknown content
+</pre>
+</div>
+
+</section> <!-- end of collection-types -->
+
+
+<section id="term-collection-insertion">
+<h3>Insertion</h3>
+
+
+<strong>Derivation-by-Insertion</strong> relation <span class="name">derivedByInsertionFrom(c2, c1, k, v)</span> states that <span class="name">c2</span> is the state of the collection
+following the insertion of pair <span class="name">(k,v)</span> into collection <span class="name">c1</span>.
+
+<p> A Derivation-by-Insertion relation<span class="withPn">, written <span class="pnExpression"> derivedByInsertionFrom(id, collAfter, collBefore, key, value, attrs)</span>,</span> contains:</p>
<ul>
- <li>Insertion relation <span class="name">CollectionAfterInsertion(c2, c1, k, v)</span> states that <span class="name">c2</span> is the state of the collection
-following the insertion of pair <span class="name">(k,v)</span> into collection <span class="name">c1</span>;</li>
-
-<li> Removal relation <span class="name">CollectionAfterRemoval(c2,c1, k)</span> states that <span class="name">c2</span> is the state of the collection following the removal of the pair corresponding to key <span class="name">k</span> from <span class="name">c1</span>.</li>
-
+<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> insertion; </li>
+<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> insertion;</li>
+<li><span class='attribute'>key</span>: the key that has been inserted</li>
+<li><span class='attribute'>value</span>: an identifier for the value that has been inserted with the key.</li>
+<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
</ul>
+
+<div class="anexample">
+<pre class="codeexample">
+ entity(c, [prov:type="EmptyCollection"]) // c is an empty collection
+ entity(v1)
+ entity(v2)
+ entity(c1, [prov:type="Collection"])
+ entity(c2, [prov:type="Collection"])
+
+ derivedByInsertionFrom(c1, c, "k1", v1)
+ derivedByInsertionFrom(c2, c1, "k2", v2)
+</pre>
+ From this set of assertions, we conclude:
+ <pre class="codeexample">
+ c = { }
+ c1 = { ("k1",v1) }
+ c2 = { ("k1",v1), ("k2", v2) }
+ </pre>
+</div>
+
+</section> <!-- insertion -->
+
+
+<section id="term-collection-removal">
+<h3>Removal</h3>
+
+<strong>Derivation-by-Removal</strong> relation <span class="name">derivedByRemovalFrom(c2,c1, k)</span> states that <span class="name">c2</span> is the state of the collection following the removal of the pair corresponding to key <span class="name">k</span> from <span class="name">c1</span>.
+
+<p> A Derivation-by-Removal relation, written <span class="pnExpression"> derivedByRemovalFrom(id, collAfter, collBefore, key, attrs)</span>, contains:</p>
+<ul>
+<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> the deletion; </li>
+<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> the deletion;</li>
+<li><span class='attribute'>key</span>: the key corresponding to the (key, value) pair that has been deleted from the collection.</li>
+<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
+</ul>
+
+
<div class="anexample">
<pre class="codeexample">
entity(c, [prov:type="EmptyCollection"]) // e is an empty collection
@@ -1848,69 +1905,167 @@
entity(c1, [prov:type="Collection"])
entity(c2, [prov:type="Collection"])
- CollectionAfterInsertion(c1, c, "k1", v1) // c1 = { ("k1",v1) }
- CollectionAfterInsertion(c2, c1, "k2", v2) // c2 = { ("k1",v1), ("k2", v2) }
- CollectionAfterRemoval(c3, c2, k1) // c3 = { ("k2",v2) }
+ derivedByInsertionFrom(c1, c, "k1", v1)
+ derivedByInsertionFrom(c2, c1, "k2", v2)
+ derivedByRemovalFrom(c3, c2, k1)
</pre>
+ From this set of assertions, we conclude:
+ <pre class="codeexample">
+ c = { }
+ c1 = { ("k1",v1) }
+ c2 = { ("k1",v1), ("k2", v2) }
+ c3 = { ("k2",v2) }
+ </pre>
+
+
</div>
-
-<p> A relation CollectionAfterInsertion<span class="withPn">, written <span class="pnExpression"> CollectionAfterInsertion(collAfter, collBefore, key, value)</span>,</span> contains:</p>
+</section> <!-- removal -->
+
+
+
+<section id="collection-convenience-relations">
+<h3>Convenience relations</h3>
+
+The following set of additional relations are introduced to simplify assertions about the state and state changes of collections.
+
+<section id="term-collection-bulk">
+<h3>Bulk insertion and removal</h3>
+
+The following relations allow for insertion and removal assertions involving a set of key-value pairs..
+
+<p> A Derivation-by-Bulk-Insertion relation <span class="withPn">, written <span class="pnExpression"> derivedByBulkInsertionFrom(id, collAfter, collBefore, key-value-set, attrs)</span>,</span> contains:</p>
<ul>
+<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> insertion; </li>
<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> insertion;</li>
-<li><span class='attribute'>key</span>: the key that has been inserted</li>
-<li><span class='attribute'>value</span>: an identifier for the value that has been inserted with the key.</li>
+<li><span class='attribute'>key-value-set</span>: a set of inserted key-value pairs, of the form {(key_1, value_1), ..., (key_n, value_n)}</li>
+<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
</ul>
-<p> A relation CollectionAfterDeletion, written <span class="pnExpression"> CollectionAfterDeletion(collAfter, collBefore, key)</span>, contains:</p>
+<p> A Derivation-by-Bulk-Removal relation, written <span class="pnExpression"> derivedByBulkRemovalFrom(id, collAfter, collBefore, key-set, attrs)</span>, contains:</p>
<ul>
+<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
<li><span class='attribute'>after</span>: an identifier for the collection <em>after</em> the deletion; </li>
<li><span class='attribute'>before</span>: an identifier for the collection <em>before</em> the deletion;</li>
-<li><span class='attribute'>key</span>: the key corresponding to the (key, value) pair that has been deleted from the collection.</li>
+<li><span class='attribute'>key-set</span>: a set of deleted keys, of the form {key_1,..., key_n}</li>
+<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
</ul>
-<div class='note'>
-I propose to call them afterInsertion instead of CollectionAfterInsertion (likewise, for deletion).
-What about attributes and optional Id?
-</div>
-
-
-<p>Further considerations:</p>
-
+
+<p> A Bulk-Containment relation, written <span class="pnExpression"> containedBulk(id, coll, key-value-set, attrs)</span>, contains:</p>
<ul>
- <li>The <strong>map</strong> collection type provides a generic indexing structure that can be used to model commonly used data structures, including associative lists (also known as "dictionaries" in some programming languages), 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).</li>
-
-<li>Keys are literals, and values are entities. This allows expressing nested collections, that is, collections whose values include entities of type collection.</li>
-
-<li>Insertion and removal relations are a particular case of <a href="#Derivation-Relation">derivation</a>.</li>
-
- <li>This representation of a collection's evolution makes no assumption regarding the underlying data structure used to store and manage collections. In particular, no assumptions are needed regarding the mutability of a data structure that is subject to updates. In fact, the state of a collection (i.e., the set of key-value 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">emptyCollection</span> can be used in this context as it marks the start of a sequence of collection operations.</li>
-
-<li>The state of a collection (i.e., the set of key-value 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">emptyCollection</span> can be used in this context as it marks the start of a sequence of collection operations.</li>
-
- <li> One can have multiple assertions regarding the state of a collection following a <em>set</em> of insertions, for example:<br/>
-<span class="name">CollectionAfterInsertion(c2,c1, k1, v1)</span><br/>
-<span class="name">CollectionAfterInsertion(c2,c1, k2, v2)</span><br/>
- <span class="name">...</span><br/>
-This is interpreted as <em>" <span class="name">c2</span> is the state that results from inserting <span class="name">(k1, v1)</span>, <span class="name">(k2, v2)</span> etc. into <span class="name">c1</span>"</em></li></p>
-
-<li> It is possible to have multiple derivations from a single root collection, possibly by different asserters, as shown in the following example.
+<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute'>after</span>: an identifier for the collection whose members are asserted; </li>
+<li><span class='attribute'>key-value-set</span>: a set of key-value pairs contained in the collection, of the form {(key_1, value_1), ..., (key_n, value_n)}</li>
+<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
+</ul>
<div class="anexample">
<pre class="codeexample">
- entity(c0, [prov:type="EmptyCollection"]) // e is an empty collection
- activity(a)
- entity(c1, [prov:type="Collection"])
- wasGeneratedBy(c1,a)
- derivedByBulkInsertionFrom(c1, c0, {("k1", v1), {("k2", v2) ) // c1 = { ("k1",v1), ("k2",v2) }
+ entity(c, [prov:type="EmptyCollection"]) // e is a collection, with unknown content
+
+ entity(v1)
+ entity(v2)
+ derivedByBulkInsertionFrom(c1, c, {("k1", v1), ("k2", v2)})
+ derivedByInsertionFrom(c2, c1, "k3", v3)
+ derivedByBulkRemovalFrom(c3, c1, {"k1", "k3"})
+
+ containedBulk(c3, {("k4", v4), ("k5", v5)})
</pre>
+ From this set of assertions, we conclude:
+ <pre class="codeexample">
+ c = { }
+ c1 = { ("k1", v1) ("k2", v2)}
+ c2 = { ("k1", v1) ("k2", v2), ("k3", v3)}
+ c3 = { ("k2", v2), ("k4", v4), ("k5", v5)}
+ </pre>
</div>
+</section> <!-- bulk ops -->
+
+<section id="term-collection-containment">
+<h3>Containment</h3>
+
+The insertion and removal relations make insertions and removals explicit as part of the history of a collection. This, however, requires explicit mention of the state of the collection prior to each insertion. The containment relation removes this needs, allowing the state of a collection <span class="name">c</span> to be asserted without having to introduce a prior state. This allows for the natural expression of a collection state, for instance in cases where a program or workflow block produces a new collection <span class="name">c</span> with known content. In such cases,
+<span class="name">contained(c,k, v)</span> asserts that <span class="name">c</span> is known to contain <span class="name">(k,v)</span>, without having to introduce an initial state. <br/>
+This relation is introduced as a convenience, as it can be rewritten as an insertion operation by introducing a prior state: <br/>
+<span class="name">contained(c,k, v)</span> iff there exists a collection <span class="name">c0</span> such that <span class="name">derivedByInsertionFrom(c, c0, k, v)</span>.
+
+
+<p> A Containment relation, written <span class="pnExpression"> contained(id, coll, key, values, attrs)</span>, contains:</p>
+<ul>
+<li><span class='attribute'>id</span>: an OPTIONAL identifier identifying the relation;</li>
+<li><span class='attribute'>after</span>: an identifier for the collection whose members are asserted; </li>
+<li><span class='attribute'>key</span>: the key of the pair contained by the collection;</li>
+<li><span class='attribute'>value</span>: an identifier for the value corresponding to the key;</li>
+<li><span class='attribute'>attributes</span>: an OPTIONAL set of attribute-value pairs to further describe the properties of the relation.</li>
+
</ul>
-<div class='note'>Deleted further items. Some of them are constraints which belong to part 2.</div>
-
-
+
+
+<div class="anexample">
+<pre class="codeexample">
+ entity(c, [prov:type="Collection"]) // e is a collection, with unknown content
+ activity(a)
+ wasGeneratedBy(c,a) // a produced c
+
+ entity(v1)
+ entity(v2)
+ contained(c, "k1", v1)
+ contained(c, "k1", v2) // c is contains at least ("k1", v1) and ("k2", v2)
+
+ entity(v2)
+ entity(c1, [prov:type="Collection"])
+
+ derivedByInsertionFrom(c1, c, "k3", v3)
+</pre>
+ From this set of assertions, we conclude:
+ <pre class="codeexample">
+ c contains ("k1", v1), ("k2", v2)
+ c1 contains ("k1", v1), ("k2", v2), ("k3", v3)
+ </pre>
+ Note that the state of <span class="name">c1</span> after these assertions is only partially known, because the initial state of <span class="name">c</span> is unknown. Alternatively, had the first assertion been
+ <span class="name"> entity(c, [prov:type="EmptyCollection"])</span>,
+ one would conclude that, based on these assertions, <span class="name">c1 = {("k1", v1) ("k2", v2), ("k3",v3)}</span>.
+</div>
+
+</section> <!-- Containment -->
+
+
+</section> <!-- convenience relations -->
+
+<section id="term-collection-state">
+
+<h3>State of collections and use of weaker <a href="#Derivation-Relation">derivation</a> relation</h3>
+
+<p>The state of a collection is only known to the extent that a chain of derivations starting from an empty collection can be found. Since a set of assertions regarding a collection's evolution may be incomplete, so is the reconstructed state obtained by querying those assertions. In general, all assertions reflect partial knowledge reagrding a sequence of data transformation events. In the particular case of collection evolution, in which some of the state changes may have been missed, the more generic <a href="#Derivation-Relation">derivation</a> relation should be used to signal that some updates may have occurred, which cannot be precisely asserted as insertions or removals. The following two examples illustrate this.</p>
+
+<div class="anexample">
+<pre class="codeexample">
+ entity(c, [prov:type="collection"]) // c is a collection, possibly not empty
+ entity(v1)
+ entity(v2, [prov:type="collection"]) // v2 is a collection
+</pre></div>
+
+Further considerations: <p/>
+
+<ul>
+<li>In Key-Value pairs, Keys are <a href="#term-value">values</a>, and Values are entities. This allows expressing nested collections, that is, collections whose values include entities of type collection.</li>
+
+<li>As the relation names suggest, insertion and removal relations are a particular case of <a href="#Derivation-Relation">derivation</a>.</li>
+
+
+
+<li>The state of a collection (i.e., the set of key-value 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">emptyCollection</span> can be used in this context as it marks the start of a sequence of collection operations.</li>
+
+
+<li>The representation of a collection through these relations, makes no assumption regarding the underlying data structure used to store and manage collections. 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 collections. This is reflected in the constraints listed in Part II. </li>
+</ul>
+
+
+ </section> <!-- term-collection-state -->
+
</section> <!-- end collections-->