--- a/model/ProvenanceModel.html Wed Feb 22 09:23:51 2012 +0000
+++ b/model/ProvenanceModel.html Wed Feb 22 15:42:21 2012 +0000
@@ -3485,22 +3485,34 @@
Section in flux to address
various comments about collections:
<a href="http://www.w3.org/2011/prov/track/issues/135">ISSUE-135</a>,
-<a href="http://www.w3.org/2011/prov/track/issues/135">ISSUE-136</a>,
-<a href="http://www.w3.org/2011/prov/track/issues/135">ISSUE-137</a>,
-<a href="http://www.w3.org/2011/prov/track/issues/135">ISSUE-138</a>
-<a href="http://www.w3.org/2011/prov/track/issues/135">ISSUE-139</a>
+<a href="http://www.w3.org/2011/prov/track/issues/136">ISSUE-136</a>,
+<a href="http://www.w3.org/2011/prov/track/issues/137">ISSUE-137</a>,
+<a href="http://www.w3.org/2011/prov/track/issues/138">ISSUE-138</a>
</div>
The intent of the <em>collection</em> record types relations introduced in this section is to account for <strong>part-of</strong> relationships that may exist amongst entities. Specifically, this section:
<ul>
- <li>introduces a new built-in type <span class="name">collection</span>, and </li>
- <li>introduces relations that let asserters describe how the content of entities of type collection changes over time, as a consequence of insertion and deletion operations.</li>
+ <li>introduces a new built-in type <span class="name">prov:Collection</span>, and </li>
+ <li>introduces relations that let asserters describe how the content
+ of entities of type collection changes over time, as a consequence of
+ insertion and removal operations.</li>
</ul>
-<p>We adopt a very generic form of collection for the purpose, namely an abstract data types consisting of <strong>set of key-value pairs</strong>, often referred to as a <strong>map</strong>. This provides a generic indexing structure that can be used to model commonly used data structures, including associative lists (also known as "dictionaries" or maps 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).</p>
-
-<p>Keys and values used in collections are literals. This allows expressing nested collections, that is, collections whose values include entities of type collection.</p>
+<p>We adopt a very generic form of collection for the purpose, namely an
+abstract data types consisting of <strong>set of key-value
+pairs</strong>, often referred to as a <strong>map</strong>. This
+provides a generic indexing structure that can be used to model commonly
+used data structures, including associative lists (also known as
+"dictionaries" or maps 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).</p>
+
+<p>Keys and values used in collections are entities. This allows
+expressing nested collections, that is, collections whose values include
+entities of type collection. PROV-DM does not specify how to relate
+these entities to literals such as <code>"key1"</code> or <code>1337</code>.</p>
<p>The following relations and corresponding record types are introduced to model (a) insertion of a new key-value pair into a collection and (b) removal of a key-value pair from a collection.</p>
@@ -3520,9 +3532,9 @@
The following entity types are introduced:
<ul>
- <li> <span class="name">prov:type="Collection"%%xsd:QName</span> denotes that the entity is a collection, that is, it can participate in <span class="name">CollectionAfterInsertion</span> and <span class="name">CollectionAfterDeletion</span> relations;
-
- <li><span class="name">prov:type="emptyCollection"%%xsd:QName</span> denotes that the entity is a collection, and furthermore that it does not contain any key-value pairs.
+ <li> <span class="name">prov:type="prov:Collection"%%xsd:QName</span> denotes that the entity is a collection, that is, it can participate in <span class="name">CollectionAfterInsertion</span> and <span class="name">CollectionAfterDeletion</span> relations;
+
+ <li><span class="name">prov:type="prov:EmptyCollection"%%xsd:QName</span> denotes that the entity is a collection, and furthermore that it does not contain any key-value pairs.
</ul>
<div class="note">Given the specific nature of the derivation, the intervening activity that accounts for imprecise-1 derivation should have an equally specific type, such as"
@@ -3534,45 +3546,50 @@
<div class="anexample">
<pre class="codeexample">
- entity(c, [prov:type="EmptyCollection"]) // e is an empty collection
+ entity(c, [prov:type="prov:EmptyCollection"%%xsd:QName]) // e is an empty collection
entity(k1)
entity(v1)
entity(k2)
entity(v2)
- entity(c1, [prov:type="Collection"])
- entity(c2, [prov:type="Collection"])
+ entity(c1, [prov:type="prov:Collection"%%xsd:QName])
+ entity(c2, [prov:type="prov:Collection"%%xsd:QName])
- 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) }
+ 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) }
</pre>
</div>
-<p>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 derivation assertions involving insertions and removals. Entity type <span class="name">prov:type="emptyCollection"</span> can be used in this context as it marks the start of a sequence of collection operations.</p>
+<p>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 derivation
+assertions involving insertions and removals. Entity type <span
+class="name">prov:type="prov:EmptyCollection"%%xsd:QName</span> can be
+used in this context as it marks the start of a sequence of collection
+operations.</p>
<p>Observations:</p>
<ul>
- <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>
<li> It is possible to have multiple derivations from a single root collection, possibly by different asserters, as shown in the following example.
<div class="anexample">
<pre class="codeexample">
- entity(c, [prov:type="EmptyCollection"]) // e is an empty collection
+ entity(c, [prov:type="prov:EmptyCollection"%%xsd:QName])
entity(k1)
entity(v1)
entity(k2)
entity(v2)
entity(k3)
entity(v3)
- entity(c1, [prov:type="Collection"])
- entity(c2, [prov:type="Collection"])
- entity(c3, [prov:type="Collection"])
+ entity(c1, [prov:type="prov:Collection"%%xsd:QName])
+ entity(c2, [prov:type="prov:Collection"%%xsd:QName])
+ entity(c3, [prov:type="prov:Collection"%%xsd:QName])
CollectionAfterInsertion(c1, c, k1, v1) // c1 = { (k1,v1) }
CollectionAfterInsertion(c2, c, k2, v2) // c2 = { (k2 v2) }
@@ -3580,6 +3597,16 @@
</pre>
</div>
</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>
+<div class="issue">This contradicts the observation below about
+functional relations. This is <a
+href="http://www.w3.org/2011/prov/track/issues/136">ISSUE-136</a></div>
+
+</li>
<li>Both relations are functional, in the sense that they represent a state change following a unique insertion/removal operation (or a unique set of them). Thus, from the pair of assertions:
@@ -3600,11 +3627,11 @@
<div class="anexample">
<pre class="codeexample">
- entity(c, [prov:type="collection"]) // e is a collection, possibly not empty
+ entity(c, [prov:type="prov:Collection"%%xsd:QName]) // e is a collection, possibly not empty
entity(k1)
entity(v1)
entity(k2)
- entity(v2, [prov:type="collection"]) // v2 is a collection
+ entity(v2, [prov:type="prov:Collection"%%xsd:QName]) // v2 is a collection
CollectionAfterInsertion(c1, c, k1, v1) // c1 <em>includes</em> { (k1,v1) } but may contain additional unknown pairs
CollectionAfterInsertion(c2, c1, k2, v2) // c2 includes { (k1,v1), (k2 v2) } where v2 is a collection with unknown state
@@ -3614,15 +3641,15 @@
<div class="anexample">
<pre class="codeexample">
- entity(c, [prov:type="emptyCollection"]) // e is an empty collection
+ entity(c, [prov:type="prov:EmptyCollection"%%xsd:QName])
entity(k1)
entity(v1)
entity(k2)
entity(v2)
CollectionAfterInsertion(c1, c, k1, v1) // c1 = { (k1,v1) }
- wasDerivedFrom(c2, c1) // the asserted knows that c2 is somehow derived from c1, but cannot assert the precise sequence of updates
- CollectionAfterInsertion(c3, c2, k2, v2)
+ wasDerivedFrom(c2, c1) // the asserter knows that c2 is somehow derived from c1, but cannot assert the precise sequence of updates
+ CollectionAfterInsertion(c3, c2, k2, v2)
</pre>
</div>
Here <span class="name">c3</span> includes <span class="name">{ (k2 v2) }</span> but the earlier "gap" leaves uncertainty regarding <span class="name">(k1,v1)</span> (it may have been removed) or any other pair that may have been added as part of the derivation activities.
@@ -3637,7 +3664,8 @@
<li><em>source</em>: an identifier <span class="name">value</span> for the value corresponding to the key that has been inserted into <span class="name">collBefore</span></li>
</ul>
-<p> An assertion CollectionAfterDeletion, written <span class="name"> CollectionAfterDeletion(collAfter, collBefore, key)</span>, contains:</p>
+<p> An assertion CollectionAfterRemoval, written <span class="name">
+CollectionAfterRemoval(collAfter, collBefore, key)</span>, contains:</p>
<ul>
<li><em>entity</em>: an identifier <span class="name">collAfter</span> for the collection record representing the collection <em>after</em> the deletion; </li>
<li><em>source</em>: an identifier <span class="name">collBefore</span> for the collection record representing the collection <em>before</em> the deletion;</li>