--- a/ontology/ProvenanceFormalModel.html Wed Oct 26 12:07:22 2011 +0100
+++ b/ontology/ProvenanceFormalModel.html Wed Oct 26 14:55:04 2011 +0100
@@ -65,7 +65,8 @@
// 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"],
+ extraCSS:
+ ["http://dev.w3.org/2009/dap/ReSpec.js/css/respec.css", "./extra.css"],
// editors, add as many as you like
// only "name" is required
@@ -1049,6 +1050,243 @@
</div>
</section>
+
+ <section id="collections">
+ <h3>Collections</h3>
+ <p>A <code>Collection</code> is a type of
+ <code>Entity</code> which have been composed of other
+ entities. A PROV-O <code>Collection</code> can represent
+ any kind of collection, such as a ordered list, array,
+ associative list, dictionary, hashtable, map. It is out of scope
+ for PROV to further define the exact nature of the collection, but
+ PROV-O defines shortcuts for defining that a entity have
+ been added or removed to a collection. These operations are
+ modelled as subproperties of <code>wasDerivedFrom</code>
+ between two static collections, corresponding to <a
+ href="http://www.w3.org/TR/prov-dm/#expression-Collection">collection
+ assertions</a> [[PROV-DM]].
+ </p>
+
+ <section id="collection-adding">
+ <h4>Expansion</h4>
+ <p>
+ An <code>Entity</code> can be added to a
+ <code>Collection</code>, producing a new (derived)
+ <code>Collection</code> which contains the new item
+ in addition to the items of the old collection.
+ The item can be added at a certain <em>key</em> (represented
+ as another <code>Entity</code>), which could be
+ a <em>position</em> (for ordered lists), a <em>hash key</em>
+ for a dictionary, or the value itself (for sets).
+ In PROV-O the addition is specified using the functional
+ properties <code>wasExpandedFrom</code>,
+ </code>wasExpandedBy</code> and <code>wasExpandedAt</code>.
+ These correspond to the PROV-ASN <a
+ href="http://www.w3.org/TR/prov-dm/#expression-Collection">collection
+ assertions</a>
+ <code>wasAddedTo_Coll</code> (the expanded collection),
+ <code>wasAddedTo_Entity</code> (the expansion)
+ and <code>wasAddedTo_Key</code> (the key it was expanded at). The properties are
+ functional so that only one expansion is asserted at a time,
+ relating the three properties without requiring an
+ explicit "Expansion" class, and also asserting that no other
+ entities have been added or removed to the two
+ collections related using <code>prov:wasExpandedBy</code>.
+ </p>
+ <div class="issue">[[PROV-DM]] does not make the guarantee
+ that other entities have not been added. Is it fair to make
+ such an assumption here?
+ </div>
+ <div class="exampleOuter">
+ <pre class="example">
+ :col1 a prov:Collection ;
+ prov:wasExpandedFrom :col0 ;
+ prov:wasExpandedBy :e1 ;
+ prov:wasExpandedAt :key1 .
+
+ :col2 a prov:Collection ;
+ prov:wasExpandedFrom :col1 ;
+ prov:wasExpandedBy :e2 ;
+ prov:wasExpandedAt :key2 .
+ </pre>
+ </div>
+ <p>
+ The above example describes collections <code>:col0</code>,
+ <code>:col1</code> and <code>:col2</code>. We know that
+ <code>:col2:</code> has the entries:
+ <code>(:key2, :e2)</code> and <code>(:key1, :e2)</code>. As
+ we don't have the provenance of :col0 it might or might not
+ contain other keys and entities.
+ </p>
+ <div class="constraint" id="expanded-collection">
+ If a Collection has one of the functional
+ <code>prov:wasExpandedFrom</code>,
+ <code>prov:wasExpandedBy</code> or
+ <code>prov:wasExpandedAt</code> properties asserted, then it
+ is an <code>ExpandedCollection</code> and the
+ existence of the remaining <code>wasExpanded*</code> properties are implied.
+ </div>
+ <div class="issue">TODO: Express the constraint <em>expanded-collection</em> in the OWL ontology</div>
+ <div class="issue">TODO: Write Collection examples as RDF/XML</div>
+ <div class="issue">Does prov:Collection allow replacement or
+ multiple additions on the same key?
+ If we do a second expansion using the :key1,
+ will :e1 still be in the collection? We
+ recommend that for <em>map</em> functionality replacement
+ should always be represented by first an explicit removal
+ (wasReducedBy) followed by insertion (wasExpandedBy).
+ </div>
+ </section>
+
+ <section id="collection-removal">
+ <h4>Reduction</h4>
+ <p>
+ Removing from a collection is modelled in a similar way as
+ expansion, by deriving a new <em>reduced</em> collection
+ which does not have the removed item or key. This is done
+ using the properties <code>prov:wasReducedFrom</code>,
+ <code>prov:wasReducedBy</code> and
+ <code>prov:wasReducedAt</code>, which correspond go
+ [[PROV-DM]] properties <code>wasRemovedFrom_Coll</code>
+ and <code>wasRemovedFrom_Key</code>.
+ </p>
+ <div class="exampleOuter">
+ <pre class="example">
+ :col3 a prov:Collection ;
+ prov:wasReducedFrom :col2 ;
+ prov:wasReducedAt :key1 .
+
+ :col4 a prov:Collection ;
+ prov:wasReducedFrom :col3 ;
+ prov:wasReducedBy :e2 ;
+ prov:wasReducedAt :key2 .
+ </pre>
+ </div>
+ <p>
+ The example above says that in :col3 does not contain
+ what :col2 had at <code>:key1</code>, e.g. (:key1, :e1).
+ :col4 does not contain (:key2, :e2).
+ </p>
+ <div class="constraint" id="reduced-collection">
+ If a Collection has one of the functional
+ <code>prov:wasReducedFrom</code>,
+ <code>prov:wasReducedBy</code> or
+ <code>prov:wasReducedAt</code> properties asserted, then it
+ is a <code>ReducedCollection</code> and the
+ existence of the remaining <code>wasReduced*</code> properties are
+ implied. A <code>ReducedCollection</code> is disjoint from a
+ <code>ExpandedCollection</code>, so it is not possible to
+ combine any <code>wasReduced*</code> property with any
+ <code>wasExpanded*</code> property.
+ </div>
+ <div class="issue">TODO: Express the constraint <em>reduced-collection</em> in the OWL ontology</div>
+ <div class="issue">
+ Does removal at :key1 mean it is no longer present in
+ the collection? What if the collection is a linked list,
+ where :key1 is a position? (:e2 would now be at :key1).
+ Does removal assert that the key existed in the
+ collection, or simply that it no longer is in the
+ collection? If it is possible to insert several values
+ at the same key, is it possible to remove only one of
+ these at a given key?
+ </div>
+ <p>
+ Asserting <code>prov:wasReducedBy</code> is optional, as
+ <code>prov:wasReducedAt</code> will remove any value at that
+ key. (PROV-DM does not describe wasRemovedFrom_Entity).
+ </p>
+ </section>
+ <section class="collection-empty">
+ <h4>EmptyCollection</h4>
+ <p>PROV-O defines
+ a subclass of <code>Collection</code> called
+ <code>EmptyCollection</code>. Asserting that a
+ collection is empty means that it does not contain
+ any key/value pairs. Combined with expansion and
+ reduction statements this allows the assertion of
+ the complete content of a collection.
+ </p>
+ <div class="exampleOuter">
+ <pre class="example">
+ :col0 a prov:EmptyCollection .
+ :col4 a prov:EmptyCollection .
+ </pre>
+ </div>
+ <div class="issue">[[PROV-DM]] does not describe the concept
+ of an empty collection</div>
+ <p>
+ With the additional information given above, one can
+ conclude that <code>:col1</code> (which
+ <code>prov:wasExpandedFrom :col0</code>) only
+ contains the expanded entity <code>:e1</code>, and that
+ <code>:col2</code> only contains the keys <code>:key1</code>
+ and <code>:key2</code>.</p>
+
+
+ <div class="constraint" id="empty-collection-disjoint">
+ An EmptyCollection is disjoint from an ExpandedCollection.
+ </div>
+ <div class="constraint" id="empty-collection-range">It is not valid for an asserted
+ <code>EmptyCollection</code> to be
+ in the domain of <code>prov:wasExpandedFrom</code> or
+ in the range of <code>prov:wasReducedFrom</code>.
+ </div>
+ <div class="issue">TODO: Include the constraints
+ <em>empty-collection-disjoint</em> and
+ <em>empty-collection-range</em> in the OWL ontology</div>
+ </section>
+ <section>
+ <h4>Collection content</h4>
+ <p>To describe the complete content of a Collection (its
+ keys and values), an asserter can form a chain of
+ <code>wasExpandedFrom</code> assertions starting from an
+ <code>EmptyCollection</code>. Note that although this does
+ enforce an ordering of the addition of the elements to the
+ final collection, it does not neccessarily assert that this
+ happened sequentially, as the corresponding implied
+ <code>ProcessExecution</code>s could have had zero duration.
+ To assert that the intermediate expansions occurred
+ "instantly" and not expose any temporal ordering of the
+ insertions, you may state that the <em>generation time</em>
+ of the initial and final collection is the same:
+ </p>
+ <div class="exampleOuter">
+ <pre class="example">
+ :col0 a prov:EmptyCollection ;
+ <b>prov:wasGeneratedAt :t0 .</b>
+ :col1 a prov:Collection ;
+ prov:wasExpandedFrom :col0 ;
+ prov:wasExpandedBy :e1 .
+ :col2 a prov:Collection ;
+ prov:wasExpandedFrom :col1 ;
+ prov:wasExpandedBy :e2 ;
+ <b>prov:wasGeneratedAt :t0 .</b>
+ </pre>
+ </div>
+ <p>The collection <code>:col2</code> described above was
+ created with the entities
+ <code>:e1</code> and <code>:e2</code>. Both items were
+ inserted at the same time <code>:t0</code>. (The
+ wasGeneratedAt :t0 for :col1 is implied above due to the
+ <a
+ href="http://www.w3.org/TR/prov-dm/#derivation-use-generation-ordering">derivation-use-generation-ordering</a>
+ constraint.)
+ </p>
+ <div class="issue">
+ FIXME: What if the asserter knows and want to assert the
+ content, and she knows it was inserted in a temporal order - but
+ don't know that order? (for instance "members of the Royal
+ Society"). Should there be a prov:hadContent property? Is it
+ possible to use rdf collections for such a shorthand?
+ </div>
+ <div class="issue">
+ Is it possible to express set operations (union, difference,
+ intersection, negation) between two collections without
+ having to express all the individual members?
+ </div>
+ </section>
+ </section>
+
<section id="overview-of-the-ontology">
<h3>Overview of the ontology</h3>
<p>The following diagram illustrates the complete PROV ontology. </p>