PROV-Dictionary: Modeling Provenance for Dictionary Data Structures

W3C Working Group Note 30 April 2013

This version:: http://www.w3.org/TR/2013/NOTE-prov-dictionary-20130430/
Latest published version:: http://www.w3.org/TR/prov-dictionary/
Previous version:: http://www.w3.org/TR/2013/WD-prov-dictionary-20130312/
Editors:: Tom De Nies, iMinds - Ghent University; Sam Coppens, iMinds - Ghent University
Authors:: Paolo Missier, Newcastle University; Luc Moreau, University of Southampton; James Cheney, University of Edinburgh; Timothy Lebo, Rensselaer Polytechnic Institute; Stian Soiland-Reyes, University of Manchester

Abstract

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. This document describes extensions to PROV to facilitate the modeling of provenance for dictionary data structures. [PROV-DM] specifies a Collection as an entity that provides a structure to some constituents, which are themselves entities. However, some applications may need a mechanism to specify more structure to a Collection, in order to accurately describe its provenance. Therefore, in this document, we introduce Dictionary, a specific type of Collection with a logical structure consisting of key-entity pairs.

The PROV Document Overview describes the overall state of PROV, and should be read before other PROV documents.

Status of This Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

PROV Family of Documents

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 listed below. Please consult the [PROV-OVERVIEW] for a guide to reading these documents.

PROV-OVERVIEW (Note), an overview of the PROV family of documents [PROV-OVERVIEW];
PROV-PRIMER (Note), a primer for the PROV data model [PROV-PRIMER];
PROV-O (Recommendation), the PROV ontology, an OWL2 ontology allowing the mapping of the PROV data model to RDF [PROV-O];
PROV-DM (Recommendation), the PROV data model for provenance [PROV-DM];
PROV-N (Recommendation), a notation for provenance aimed at human consumption [PROV-N];
PROV-CONSTRAINTS (Recommendation), a set of constraints applying to the PROV data model [PROV-CONSTRAINTS];
PROV-XML (Note), an XML schema for the PROV data model [PROV-XML];
PROV-AQ (Note), mechanisms for accessing and querying provenance [PROV-AQ];
PROV-DICTIONARY (Note) introduces a specific type of collection, consisting of key-entity pairs (this document);
PROV-DC (Note) provides a mapping between PROV-O and Dublin Core Terms [PROV-DC];
PROV-SEM (Note), a declarative specification in terms of first-order logic of the PROV data model [PROV-SEM];
PROV-LINKS (Note) introduces a mechanism to link across bundles [PROV-LINKS].

Implementations Encouraged

The Provenance Working Group encourages implementation of the material defined in this document. Although work on this document by the Provenance Working Group is complete, errors may be recorded in the errata or and these may be addressed in future revisions.

Please Send Comments

This document was published by the Provenance Working Group as a Working Group Note. If you wish to make comments regarding this document, please send them to public-prov-comments@w3.org (subscribe, archives). All comments are welcome.

Publication as a Working Group Note does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

1. Introduction

Provenance 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.

[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 more structure to a Collection, in order to accurately describe its provenance.

Therefore, this document introduces a new concept, Dictionary, that has a logical structure consisting of key-entity pairs.

2. PROV Namespace

The PROV namespace URI is http://www.w3.org/ns/prov# and prefix prov.

All the concepts, reserved names, classes, properties, attributes introduced in this specification belong to the PROV namespace.

3. Conceptual Definition of Dictionary

In this section a specific type of collection, as specified in [PROV-DM], is introduced. This new type of collection, Dictionary, is specified as follows.

Conceptually, a dictionary has a logical structure consisting of key-entity pairs. This structure is often referred to as a map, and is a generic indexing mechanism that can abstract commonly used data structures, including associative lists, relational tables, ordered lists, and more. This document provides a mechanism to assert the provenance for these types of data structures, in the most general way, as a collection of key-entity pairs, modified through insertions and deletions. Any more specialized structures can be modeled to some extent in terms of these key-entity pairs. Here, we will discuss the provenance of dictionaries structured in terms of key-entity pairs. However, how this key-entity pair structure is translated to more specialized data structures, is beyond the scope of this document.

In this document, a dictionary is viewed as a snapshot of a data structure with key-entity pairs, following a sequence of state-changing insertion and removal operations. These operations result in new snapshots, each snapshot forming a distinct and identifiable dictionary entity. Thus, when the structure of a dictionary changes (through insertions or removals), a new dictionary entity is defined, whereas the older dictionary entity remains the same. The concepts defined in this document can be used to specify the differences between these dictionary entities.

Following the definition of prov:Collection, PROV-Dictionary defines the following types related to dictionaries:

prov:Dictionary is a subtype of prov:Collection. It denotes an entity of type dictionary, i.e. an entity that can participate in relations that involve dictionaries and their member entities;
prov:EmptyDictionary is a subtype of both prov:EmptyCollection and prov:Dictionary. It denotes an empty dictionary.

Note that the complete content of a dictionary is unknown unless it can be traced back to an empty dictionary through a series of insertions and removals. If an asserter wants to explicitly state that a dictionary is empty, it is recommended that the prov:type prov:EmptyDictionary is used.

Example 1^◊

entity(d0, [prov:type='prov:EmptyDictionary' ])  // d0 is an empty dictionary
entity(d1, [prov:type='prov:Dictionary'  ])      // d1 is a dictionary, with (so far) unknown content

3.1 Dictionary Membership

Similar to the collection membership relation, the dictionary membership allows stating the members of a Dictionary. However, it provides additional structure. Note that dictionary membership implies collection membership, but not vice versa. This implication is formalized in Inference D1.

A dictionary membership^◊ relation, written prov:hadDictionaryMember(d, e_1, key_1), has:

dictionary: an identifier (d) for the dictionary whose members are asserted;
entity: an entity e_1 that is associated with the key and is a member of the dictionary;
key: a key key_1 that is associated with the specified entity. key_1 is a value ;

Keys cannot be repeated in the same dictionary. However, a dictionary can contain the same entity more than once, as long as it is associated with different keys.

Note that the collection membership relation, written hadMember(c, e), can be used when c has prov:type = 'prov:Collection' or prov:type = 'prov:Dictionary'. However, the dictionary membership, written hadDictionaryMember(d, e, "k"), can only be used when d has prov:type = 'prov:Dictionary'.

Example 2^◊

entity(d, [prov:type='prov:Dictionary' ])    // d is a dictionary, with (so far) unknown content

entity(e1)
entity(e2)

prov:hadDictionaryMember(d, e1, "k1")  
prov:hadDictionaryMember(d, e2, "k2")

From these descriptions, we conclude:

d had the following key-entity pairs as members: ("k1", e1), ("k2", e2), and may have contained others.

Thus, the membership of d is only partially known, unless it was derived through insertions and removals from an empty dictionary (See Completeness constraints).

3.2 Dictionary Insertion

An Insertion^◊ relation, written prov:derivedByInsertionFrom(id; d2, d1, {(key_1, e_1), ..., (key_n, e_n)}, attrs), has:

id: an OPTIONAL identifier identifying the relation;
after: an identifier (d2) for the dictionary after insertion;
before: an identifier (d1) for the dictionary before insertion;
key-entity-set: all inserted key-entity pairs (key_1, e_1), ..., (key_n, e_n). Here, each key_i is a value, and e_i is an identifier for the entity that has been inserted with the key; each key_i is expected to be unique for the key-entity-set, as formalized in Inference D3;
attributes: an OPTIONAL set (attrs) of attribute-value pairs representing additional information about this relation.

An Insertion relation prov:derivedByInsertionFrom(id; d2, d1, {(key_1, e_1), ..., (key_n, e_n)}) states that d2 is the dictionary following the insertion of key-entity pairs (key_1, e_1), ..., (key_n, e_n) into dictionary d1. In other words, the set of key-entity pairs {(key_1, e_1), ...,(key_n, e_n)} is to be seen as the difference between d1 and d2. Note that this key-entity-set is considered to be complete. This means that we assume that no unknown keys were inserted in or removed from a dictionary derived by an insertion relation. This is formalized in Inference D4.

Example 3^◊

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' ])

prov:derivedByInsertionFrom(d1, d0, {("k1", e1), ("k2", e2)})       
prov:derivedByInsertionFrom(d2, d1, {("k3", e3)}, [ dcterms:description ="A second insertion" ])    //an insertion with optional attribute dcterms:description

From this set of descriptions, we conclude:

d0 was the dictionary { }
d1 was the dictionary { ("k1", e1), ("k2", e2) }
d2 was the dictionary { ("k1", e1), ("k2", e2), ("k3", e3) }

Futhermore, 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.

Example 4^◊

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' ])

prov:derivedByInsertionFrom(d1, d0, {("k1", e1), ("k2", e2)})       
prov:derivedByInsertionFrom(d2, d1, {("k1", e3)})

This is a case of update of e1 to e3 for the same key, "k1".
From this set of descriptions, we conclude:

d0 was the dictionary { }
d1 was the dictionary { ("k1", e1), ("k2", e2) }
d2 was the dictionary { ("k1", e3), ("k2", e2) }

3.3 Dictionary Removal

A Removal^◊ relation, written prov:derivedByRemovalFrom(id; d2, d1, {key_1, ... key_n}, attrs), has:

id: an OPTIONAL identifier identifying the relation;
after: an identifier (d2) for the dictionary after the deletion;
before: an identifier (d1) for the dictionary before the deletion;
key-set: the set of deleted keys key_1, ..., key_n. Here, each key_i is a value;
attributes: an OPTIONAL set (attrs) of attribute-value pairs representing additional information about this relation.

A Removal relation prov:derivedByRemovalFrom(id; d2,d1, {key_1, ..., key_n}) states that d2 is the dictionary following the removal of the set of pairs corresponding to keys key_1...key_n from d1. In other words, the key-set {key_1,...,key_n} is to be seen as the difference in keys and corresponding entities between d1 and d2. Note that this key-set is considered to be complete. This means that we assume that no unknown keys were inserted in or removed from a dictionary derived by a removal relation. This is formalized in Inference D5.

Example 5^◊

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"])
entity(d3, [prov:type="prov:Dictionary"])
entity(d4, [prov:type="prov:Dictionary"])

prov:derivedByInsertionFrom(d1, d0, {("k1", e1), ("k2",e2)})       
prov:derivedByInsertionFrom(d2, d1, {("k3", e3)})
prov:derivedByRemovalFrom(d3, d2, {"k1", "k3"})   
prov:derivedByRemovalFrom(d4, d3, {"k1"})

From this set of descriptions, we conclude:

d0 was the dictionary { }
d1 was the dictionary { ("k1", e1), ("k2", e2) }
d2 was the dictionary { ("k1", e1), ("k2", e2), ("k3", e3) }
d3 was the dictionary { ("k2", e2) }
d4 was the dictionary { ("k2", e2) }

Note that there is no constraint stating that removed keys had to be present in the original dictionary. For example, "k1" was not present in d3, and thus its removal to obtain d4 did not change the contents of the dictionary.

4. PROV-N Notation of Dictionary Concepts

The notation used for dictionaries in this document extends the standard PROV-N according to the principles described in the PROV-N extensibility chapter. The [Grammar for PROV-Dictionary] is available for download.

4.1 Dictionary and EmptyDictionary Expression

PROV-Dictionary provides no dedicated syntax for Dictionary and EmptyDictionary. Dictionaries are declared in the same way as Collections. A Dictionary or an EmptyDictionary MUST be expressed as an entityExpression with attribute prov:type='prov:Dictionary', or prov:type='prov:EmptyDictionary', respectively.

Example 6^◊

The following two expressions are about a dictionary and an empty dictionary, respectively.

  entity(ex:d1,   [ prov:type='prov:Dictionary' ])
  entity(ex:d2,   [ prov:type='prov:EmptyDictionary' ])

4.2 Dictionary Membership

[1] dictionaryMembershipExpression ::= "prov:hadDictionaryMember" "(" dIdentifier "," eIdentifier "," key ")"

The following table summarizes how each constituent of a PROV-Dictionary Membership maps to a non-terminal.

Dictionary Membership	Non-Terminal

dictionary	`dIdentifier`
entity	`eIdentifier`
key	`key`

Example 7^◊

In this example, d is a dictionary known to have e0 as member, and may have other members.

entity(e0)

entity(d, [prov:type='prov:Dictionary'  ]) 
prov:hadDictionaryMember(d, e0, "k0")

4.3 Insertion

[2] derivationByInsertionFromExpression ::= "prov:derivedByInsertionFrom" "(" (optionalIdentifier ";")? dIdentifier "," dIdentifier "," "{" keyEntityPairs "}" optionalAttributeValuePairs ")"

The following table summarizes how each constituent of a PROV-Dictionary Insertion maps to a non-terminal.

Insertion	Non-Terminal

id	`optionalIdentifier`
after	`dIdentifier`
before	`dIdentifier`
key-entity-pairs	`keyEntityPairs`
attributes	`optionalAttributeValuePairs`

Example 8^◊

 prov:derivedByInsertionFrom(id; d1, d, {("k1", e1), ("k2", e2)}, [])

Here id is the optional insertion identifier, d1 is the identifier for the dictionary after the insertion, d is the identifier for the dictionary before the insertion, {("k1", e1), ("k2", e2)} is the set of key-entity pairs that have been inserted in d, and [] is the optional (empty) set of attributes.

The remaining examples show cases where some of the optionals are omitted.

 prov:derivedByInsertionFrom(d1, d, {("k1", e1), ("k2", e2)})  
 prov:derivedByInsertionFrom(d1, d, {("k1", e1)})  
 prov:derivedByInsertionFrom(d1, d, {("k1", e1), ("k2", e2)}, [])

4.4 Removal

[3] derivationByRemovalFromExpression ::= "prov:derivedByRemovalFrom" "(" (optionalIdentifier ";")? dIdentifier "," dIdentifier "," "{" keySet "}" optionalAttributeValuePairs ")"

The following table summarizes how each constituent of a PROV-Dictionary Removal maps to a non-terminal.

Removal	Non-Terminal

id	`optionalIdentifier`
after	`dIdentifier`
before	`dIdentifier`
key-set	`keySet`
attributes	`optionalAttributeValuePairs`

Example 9^◊

 prov:derivedByRemovalFrom(id; d3, d, {"k1", "k2"}, [])

Here id is the optional removal identifier, d3 is the identifier for the collection after the removal, d is the identifier for the collection before the removal, {"k1", "k2"} is the set of keys that have been removed from d, and [] is the optional (empty) set of attributes.

The remaining examples show cases where some of the optionals are omitted.

   prov:derivedByRemovalFrom(d2, d, {"k1", "k2"})               
   prov:derivedByRemovalFrom(d2, d, {"k1"})               
   prov:derivedByRemovalFrom(d2, d, {"k1", "k2"}, [])

4.5 Other expressions

For the notation of dictionaries, we used some new non-terminals. We provide their production rules here.

[4]	`dIdentifier`	::=	`identifier`
[5]	`key`	::=	`literal`
[6]	`keyEntityPairs`	::=	`keyEntityPair ("," keyEntityPair)*`
[7]	`keyEntityPair`	::=	`"(" key "," eIdentifier ")"`
[8]	`keySet`	::=	`key ("," key)*`

5. PROV-O Representation of Dictionary

In this section, the ontological definition of prov:Dictionary is given, in order to extend [PROV-O] with dictionaries. For more information on the terminology, syntax and conventions used in this section, we refer to [PROV-O].

The classes and properties defined in this document are included in the default namespace of PROV. Users of the ontology have the option of importing <http://www.w3.org/ns/prov#>, which includes all extensions, including PROV-Dictionary. Additionally, the [OWL file for PROV-Dictionary] is available for download.

A prov:Dictionary is a prov:Entity that acts as a container to some members, which are themselves entities. Specifically, a dictionary is composed of set of key-entity pairs, where a literal key is used to identify a constituent entity within the dictionary.

Example 1

@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix :     <http://example.org/> .

:e1 a prov:Entity .
:e2 a prov:Entity .

:d1 a prov:Dictionary;
    prov:hadDictionaryMember [ 
       a prov:KeyEntityPair;
       prov:pairKey   "k1"^^xsd:string;
       prov:pairEntity :e1
     ], [ 
       a prov:KeyEntityPair;
       prov:pairKey   "k2"^^xsd:string;
       prov:pairEntity :e2
     ];
.

It is worth noting that :d1 MAY also have other members. If one wants to explicitly state that a dictionary has no members, that dictionary can be described as an instance of the subclass prov:EmptyDictionary.

To describe the provenance of a dictionary, PROV-Dictionary provides two kinds of influence: prov:qualifiedInsertion is used to describe that a dictionary was obtained from an existing dictionary by inserting a set of key-entity pairs. prov:qualifiedRemoval is used to specify that a given dictionary was obtained from an existing dictionary by removing a set of key-entity pairs. The example below specifies that the dictionary :d1 was obtained from the empty dictionary :d by inserting the key-entity pairs ("k1", :e1) and ("k2", :e2).

Example 2

@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix :     <http://example.org/> .

:e1 a prov:Entity .
:e2 a prov:Entity .

:d  a prov:EmptyDictionary .

:d1 a prov:Dictionary;
   prov:derivedByInsertionFrom :d;
   prov:qualifiedInsertion [ 
      a prov:Insertion;
      prov:dictionary :d;
      prov:insertedKeyEntityPair [ 
         a prov:KeyEntityPair;
         prov:pairKey   "k1"^^xsd:string;
         prov:pairEntity :e1;
      ], [ 
         a prov:KeyEntityPair;
         prov:pairKey   "k2"^^xsd:string;
         prov:pairEntity :e2;
      ];
   ]; 
.

Similarly, the example below specifies that the dictionary :d3 was obtained by removing the key-entity pairs associated with the keys "k1" and "k2" from the dictionary :d2. Thus, :d3 does not contain the members ("k1", :e1) and ("k2", :e2) from :d2.

Example 3

@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix :     <http://example.org/> .

:d2 a prov:Dictionary .

:d3 a prov:Dictionary;
   prov:derivedByRemovalFrom :d2;
   prov:qualifiedRemoval [ 
      a prov:Removal;
      prov:dictionary :d2;
      prov:removedKey    "k1"^^xsd:string, 
                      "k3"^^xsd:string;
   ];
.

5.1 Overview

These terms are used to describe the provenance of dictionaries.

prov:Dictionary
prov:EmptyDictionary
prov:Insertion
prov:KeyEntityPair
prov:Removal
prov:derivedByInsertionFrom
prov:derivedByRemovalFrom
prov:dictionary
prov:insertedKeyEntityPair
prov:hadDictionaryMember
prov:pairKey
prov:pairEntity
prov:qualifiedInsertion
prov:qualifiedRemoval
prov:removedKey

5.2 Dictionary Classes

Class: prov:Dictionary

back to overview

IRI:http://www.w3.org/ns/prov#Dictionary

A dictionary is an entity that provides a structure to some constituents, which are themselves entities. These constituents are said to be members of the dictionary.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix my:     <http://example.org/ontology#> .
@prefix dcterms: <http://purl.org/dc/terms/> .
@prefix :     <http://example.org/> .

:seating_chart_2012
   a prov:Dictionary, prov:Collection, prov:Entity, my:SeatingChart;
   prov:derivedByInsertionFrom :seating_chart_2011;
   dcterms:date "2012";
   my:hasTotalStudents 45;
.

This concept allows for the provenance of the dictionary, but also of its constituents to be expressed. Such a notion of dictionary corresponds to a wide variety of concrete data structures, such as a maps or associative arrays.; 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.
is subclass of: prov:Collection
described with properties: prov:hadDictionaryMember^op prov:derivedByInsertionFrom^op prov:qualifiedRemoval^op prov:qualifiedInsertion^op prov:derivedByRemovalFrom^op
in range of: prov:derivedByInsertionFrom^op prov:derivedByRemovalFrom^op prov:dictionary^op
has subclass: prov:EmptyDictionary

Class: prov:EmptyDictionary

back to overview

IRI:http://www.w3.org/ns/prov#EmptyDictionary

An empty dictionary is a dictionary that has no members.

Example

@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix :     <http://example.org/> .

:e1 a prov:Entity .
:e2 a prov:Entity .

:d  a prov:EmptyDictionary
.

is subclass of: prov:Dictionary prov:EmptyCollection

Class: prov:KeyEntityPair

back to overview

IRI:http://www.w3.org/ns/prov#KeyEntityPair

A key-entity pair. Part of a prov:Dictionary through prov:hadDictionaryMember. The key is any RDF Literal, the value is a prov:Entity.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .


:our-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
    prov:hadDictionaryMember [
       a prov:KeyEntityPair;
       prov:pairKey "first-baseman"^^xsd:string;
       prov:pairEntity :george;
    ];
    prov:hadDictionaryMember [
       a prov:KeyEntityPair;
       prov:pairKey "pitcher"^^xsd:string;
       prov:pairEntity :carl;
    ];
.

:george a prov:Entity .
:carl   a prov:Entity .

described with properties: prov:pairKey^dp prov:pairEntity^op
in range of: prov:hadDictionaryMember^op prov:insertedKeyEntityPair^op

Class: prov:Insertion

back to overview

IRI:http://www.w3.org/ns/prov#Insertion

Insertion is a derivation that describes the transformation of a dictionary into another, by insertion of one or more key-entity pairs.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:our-NEW-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
   prov:derivedByInsertionFrom :our-old-baseball-team-field-positions;
   prov:qualifiedInsertion [ 
      a prov:Insertion;
      prov:dictionary :our-old-baseball-team-field-positions;
      prov:insertedKeyEntityPair [ 
         a prov:KeyEntityPair;
         prov:pairKey   "first-baseman"^^xsd:string;
         prov:pairEntity <http://dbpedia.org/resource/Jim_Thorpe>;
      ];
   ];
.

<http://dbpedia.org/resource/Jim_Thorpe> a prov:Entity .

:our-old-baseball-team-field-positions a prov:Dictionary .

is subclass of: prov:Derivation
described with properties: prov:dictionary prov:insertedKeyEntityPair
in range of: prov:qualifiedInsertion^op
qualifies: prov:derivedByInsertionFrom

Class: prov:Removal

back to overview

IRI:http://www.w3.org/ns/prov#Removal

Removal is a derivation that describes the transformation of a dictionary into another, by removing one or more keys.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:d1 a prov:Dictionary .

:d2 
   a prov:Dictionary, 
     prov:Entity;
   prov:derivedByRemovalFrom :d1;
   prov:qualifiedRemoval [
      a prov:Removal, prov:DictionaryInvolvement;
      prov:dictionary :d1;
      prov:removedKey "k1"^^xsd:string, 
                      "k2"^^xsd:string;
   ];
.

is subclass of: prov:Derivation
described with properties: prov:dictionary prov:removedKey^dp
in range of: prov:qualifiedRemoval^op
qualifies: prov:derivedByRemovalFrom

5.3 Dictionary Properties

Property: prov:derivedByInsertionFrom^op

back to overview

IRI:http://www.w3.org/ns/prov#derivedByInsertionFrom

The dictionary was derived from the other by insertion. Can be qualified with prov:qualifiedInsertion, which shows details of the insertion, in particular the inserted key-entity pairs.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .


:e1 a prov:Entity .
:e2 a prov:Entity .

:d  a prov:EmptyDictionary .

:d1 a prov:Dictionary;
   prov:derivedByInsertionFrom :d;
   prov:qualifiedInsertion [ 
      a prov:Insertion;
      prov:dictionary :d;
      prov:insertedKeyEntityPair [ 
         a prov:KeyEntityPair;
         prov:pairKey   "k1"^^xsd:string;
         prov:pairEntity :e1;
      ], [ 
         a prov:KeyEntityPair;
         prov:pairKey   "k2"^^xsd:string;
         prov:pairEntity :e2;
      ];
   ]; 
.

has super-properties

prov:wasDerivedFrom

has domain

prov:Dictionary

has range

prov:Dictionary

can be qualified with

prov:qualifiedInsertion
prov:Insertion

Property: prov:derivedByRemovalFrom^op

back to overview

IRI:http://www.w3.org/ns/prov#derivedByRemovalFrom

The dictionary was derived from the other by removal. Can be qualified with prov:qualifiedRemoval, which shows details of the removal, in particular the removed keys.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:d1 a prov:Dictionary .

:d2 
   a prov:Dictionary, prov:Entity;
   prov:derivedByRemovalFrom :d1;
   prov:qualifiedRemoval [
      a prov:Removal;
      prov:dictionary :d1;
      prov:removedKey "k1"^^xsd:string, 
                      "k2"^^xsd:string;
   ];
.

has super-properties

prov:wasDerivedFrom

has domain

prov:Dictionary

has range

prov:Dictionary

can be qualified with

prov:qualifiedRemoval
prov:Removal

Property: prov:dictionary^op

back to overview

IRI:http://www.w3.org/ns/prov#dictionary

The property used by a prov:Insertion and prov:Removal to cite the prov:Dictionary that was prov:derivedByInsertionFrom or prov:derivedByRemovalFrom another dictionary.

Example

@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix :     <http://example.org/> .

:e1 a prov:Entity .

:d  a prov:EmptyDictionary .

:d1 a prov:Dictionary;
   prov:derivedByInsertionFrom :d;
   prov:qualifiedInsertion [ 
      a prov:Insertion;
      prov:dictionary :d;
      prov:insertedKeyEntityPair [ 
         a prov:KeyEntityPair;
         prov:pairKey   "k1"^^xsd:string;
         prov:pairEntity :e1;
      ];
   ]; 
.

has super-properties

prov:entity

has domain

prov:Insertion or prov:Removal

has range

prov:Dictionary

Property: prov:insertedKeyEntityPair^op

back to overview

IRI:http://www.w3.org/ns/prov#insertedKeyEntityPair

An object property to refer to the prov:KeyEntityPair inserted into a prov:Dictionary.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:our-NEW-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
   prov:derivedByInsertionFrom :our-old-baseball-team-field-positions;
   prov:qualifiedInsertion [ 
      a prov:Insertion;
      prov:dictionary :our-old-baseball-team-field-positions;
      prov:insertedKeyEntityPair [ 
         a prov:KeyEntityPair;
         prov:pairKey   "first-baseman"^^xsd:string;
         prov:pairEntity <http://dbpedia.org/resource/Jim_Thorpe>;
      ];
   ];
.

<http://dbpedia.org/resource/Jim_Thorpe> a prov:Entity .

:our-old-baseball-team-field-positions a prov:Dictionary .

has domain

prov:Insertion

has range

prov:KeyEntityPair

Property: prov:hadDictionaryMember^op

back to overview

IRI:http://www.w3.org/ns/prov#hadDictionaryMember

Describes the key-entity pair that was member of a prov:Dictionary. A dictionary can have multiple members.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:our-old-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
      prov:hadDictionaryMember [
         a prov:KeyEntityPair;
         prov:pairKey "first-baseman"^^xsd:string;
         prov:pairEntity :george;
      ], [
         a prov:KeyEntityPair;
         prov:pairKey "pitcher"^^xsd:string;
         prov:pairEntity :carl;
      ];
.

:george a prov:Entity .
:carl   a prov:Entity .

has domain

prov:Dictionary

has range

prov:KeyEntityPair

Property: prov:pairKey^dp

back to overview

IRI:http://www.w3.org/ns/prov#pairKey

The key of a prov:KeyEntityPair, which is an element of a prov:Dictionary.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:our-old-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
      prov:hadDictionaryMember [
         a prov:KeyEntityPair;
         prov:pairKey "first-baseman"^^xsd:string;
         prov:pairEntity :george;
      ], [
         a prov:KeyEntityPair;
         prov:pairKey "pitcher"^^xsd:string;
         prov:pairEntity :carl;
      ];
.

:george a prov:Entity .
:carl   a prov:Entity .

has characteristics Functional

has domain

prov:KeyEntityPair

has range

rdfs:Literal

Property: prov:pairEntity^op

back to overview

IRI:http://www.w3.org/ns/prov#pairEntity

The entity of a prov:KeyEntityPair, which is an element of a prov:Dictionary.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:our-old-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
      prov:hadDictionaryMember [
         a prov:KeyEntityPair;
         prov:pairKey "first-baseman"^^xsd:string;
         prov:pairEntity :george;
      ], [
         a prov:KeyEntityPair;
         prov:pairKey "pitcher"^^xsd:string;
         prov:pairEntity :carl;
      ];
.

:george a prov:Entity .
:carl   a prov:Entity .

has characteristics Functional

has domain

prov:KeyEntityPair

has range

prov:Entity

Property: prov:qualifiedInsertion^op

back to overview

IRI:http://www.w3.org/ns/prov#qualifiedInsertion

prov:qualifiedInsertion shows the details of an insertion, in particular the inserted key-entity pairs.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:our-NEW-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions;
   prov:derivedByInsertionFrom :our-old-baseball-team-field-positions;
   prov:qualifiedInsertion [ 
      a prov:Insertion;
      prov:dictionary :our-old-baseball-team-field-positions;
      prov:insertedKeyEntityPair [ 
         a prov:KeyEntityPair;
         prov:pairKey   "first-baseman"^^xsd:string;
         prov:pairEntity <http://dbpedia.org/resource/Jim_Thorpe>;
      ];
   ];
.

<http://dbpedia.org/resource/Jim_Thorpe> a prov:Entity .

:our-old-baseball-team-field-positions
   a prov:Dictionary, 
         :FieldPositions  .

has super-properties

prov:qualifiedDerivation

has domain

prov:Dictionary

has range

prov:Insertion

qualifies

prov:derivedByInsertionFrom

Property: prov:qualifiedRemoval^op

back to overview

IRI:http://www.w3.org/ns/prov#qualifiedRemoval

prov:qualifiedRemoval shows the details of a removal, in particular the removed keys.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:d1 a prov:Dictionary .

:d2 
   a prov:Dictionary, prov:Entity;
   prov:derivedByRemovalFrom :d1;
   prov:qualifiedRemoval [
      a prov:Removal;
      prov:dictionary :d1;
      prov:removedKey "k1"^^xsd:string, 
                      "k2"^^xsd:string;
   ];
.

The dictionary was derived from the other by removal. prov:qualifiedRemoval shows details of the removal, in particular the removed keys.

has super-properties

prov:qualifiedDerivation

has domain

prov:Dictionary

has range

prov:Removal

qualifies

prov:derivedByRemovalFrom

Property: prov:removedKey^dp

back to overview

IRI:http://www.w3.org/ns/prov#removedKey

The key removed in a Removal.

Example

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix xsd:  <http://www.w3.org/2001/XMLSchema#> .
@prefix owl:  <http://www.w3.org/2002/07/owl#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix :     <http://example.com/> .

:d2 
   a prov:Dictionary, 
     prov:Entity;
   prov:derivedByRemovalFrom :d1;
   prov:qualifiedRemoval [
      a prov:Removal, 
        prov:DictionaryInvolvement;
      prov:dictionary :d1;
      prov:removedKey "k1"^^xsd:string, 
                       1337, 
                       3.14;
   ];
.

has domain

prov:Removal

has range

rdfs:Literal

6. PROV-XML Representation of Dictionary

This section details how to describe dictionaries with the [PROV-XML] serialization. The [XML schema for PROV-Dictionary] is available for download, and includes prov-core.xsd, the core schema of PROV. Alternatively, the default schema, prov.xsd can be used, which imports prov-core.xsd and all extension schemas developed by the Working Group.

6.1 Dictionary

To specialize an Entity as a prov:Dictionary or prov:EmptyDictionary, the element <prov:dictionary> or <prov:emptyDictionary> is used, respectively.

<xs:complexType xmlns:xs="http://www.w3.org/2001/XMLSchema" name="Dictionary"  >
  <xs:complexContent>
  <xs:extension base="prov:Collection"></xs:extension>
  </xs:complexContent>
</xs:complexType>

Usage in XML:

<xs:element name="dictionary" type="prov:Dictionary" substitutionGroup="prov:internalElement" />

An EmptyDictionary is asserted with the prov:type "prov:EmptyDictionary" and denotes a Dictionary with no members.

<xs:complexType xmlns:xs="http://www.w3.org/2001/XMLSchema" name="EmptyDictionary"  >
  <xs:complexContent>
  <xs:extension base="prov:Dictionary"></xs:extension>
  </xs:complexContent>
</xs:complexType>

Usage in XML:

<xs:element name="emptyDictionary" type="prov:EmptyDictionary" substitutionGroup="prov:internalElement" />

Example 4

<prov:document
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
    xmlns:prov="http://www.w3.org/ns/prov#"
    xmlns:ex="http://example.com/ns/ex#">

  <!-- d0 is an empty dictionary -->
  <prov:emptyDictionary prov:id="d0" />

  <!-- d1 is a dictionary, with (so far) unknown content -->
  <prov:dictionary prov:id="d1" />

</prov:document>

6.2 Key-Entity Pair

Key-entity pairs are used to identify the members of a dictionary.

<xs:complexType xmlns:xs="http://www.w3.org/2001/XMLSchema" name="KeyEntityPair"  >
  <xs:sequence>
    <xs:element name="key" type="xs:anySimpleType" />
    <xs:element name="entity" type="prov:IDRef" />
  </xs:sequence>
</xs:complexType>

<xs:element xmlns:xs="http://www.w3.org/2001/XMLSchema" name="keyEntityPair" type="prov:KeyEntityPair" substitutionGroup="prov:internalElement"/>

Example 5

<prov:document
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
    xmlns:prov="http://www.w3.org/ns/prov#"
    xmlns:ex="http://example.com/ns/ex#">

  <prov:entity prov:id="e0"/>
  <prov:entity prov:id="e1"/>
  
  <prov:keyEntityPair>
    <prov:key>k0</prov:key>
    <prov:entity prov:ref="e0"/>
  </prov:keyEntityPair>
  
  <prov:keyEntityPair>
    <prov:key>k1</prov:key>
    <prov:entity prov:ref="e1"/>
  </prov:keyEntityPair>
</prov:document>

6.3 Dictionary Membership

The members of a dictionary are specified by listing key-entity pairs inside a prov:DictionaryMembership element

<xs:complexType xmlns:xs="http://www.w3.org/2001/XMLSchema" name="DictionaryMembership">
  <xs:sequence>
    <xs:element name="dictionary" type="prov:IDRef"/>
    <xs:element name="keyEntityPair type="prov:KeyEntityPair" minOccurs="1" maxOccurs="unbounded"/>
  </xs:sequence>
</xs:complexType>

<xs:element xmlns:xs="http://www.w3.org/2001/XMLSchema" name="hadDictionaryMember" type="prov:DictionaryMembership" substitutionGroup="prov:internalElement"/>

Example 6

<prov:document
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
    xmlns:prov="http://www.w3.org/ns/prov#">

  <prov:entity prov:id="e0"/>
  <prov:entity prov:id="e1"/>
  <prov:entity prov:id="e2"/>

  <prov:dictionary prov:id="d" />

  <prov:hadDictionaryMember>
    <prov:dictionary prov:ref="d"/>
    <prov:keyEntityPair>
      <prov:key>k0</prov:key>
      <prov:entity prov:ref="e0"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>k1</prov:key>
      <prov:entity prov:ref="e1"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>k2</prov:key>
      <prov:entity prov:ref="e2"/>
    </prov:keyEntityPair>
  </prov:hadDictionaryMember>

</prov:document>

6.4 Insertion

To specify that one dictionary was derived by insertion of key-entity pairs into another one, a prov:Insertion element is used.

<xs:complexType xmlns:xs="http://www.w3.org/2001/XMLSchema" name="Insertion">
  <xs:sequence>
    <xs:element name="newDictionary" type="prov:IDRef"/>
    <xs:element name="oldDictionary" type="prov:IDRef"/>
    <xs:element name="keyEntityPair type="prov:KeyEntityPair" minOccurs="1" maxOccurs="unbounded"/>
    <xs:element ref="prov:label" minOccurs="0" maxOccurs="unbounded"/>
    <xs:element ref="prov:type" minOccurs="0" maxOccurs="unbounded"/>
    <xs:any namespace="##other" processContents="lax" minOccurs="0" maxOccurs="unbounded"/>
  </xs:sequence>
  <xs:attribute ref="prov:id"/>
</xs:complexType>

<xs:element xmlns:xs="http://www.w3.org/2001/XMLSchema" name="derivedByInsertionFrom" type="prov:Insertion" substitutionGroup="prov:internalElement"/>

Example 7

<prov:document
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
    xmlns:prov="http://www.w3.org/ns/prov#">

  <prov:entity prov:id="e0"/>
  <prov:entity prov:id="e1"/>
  <prov:entity prov:id="e2"/>

  <prov:dictionary prov:id="d1" />
  
  <prov:dictionary prov:id="d2" />

  <prov:hadDictionaryMember>
    <prov:dictionary prov:ref="d1"/>
    <prov:keyEntityPair>
      <prov:key>k0</prov:key>
      <prov:entity prov:ref="e0"/>
    </prov:keyEntityPair>
  </prov:hadDictionaryMember>
  
  <prov:derivedByInsertionFrom>
    <prov:newDictionary prov:ref="d2"/>
    <prov:oldDictionary prov:ref="d1"/>
    <prov:keyEntityPair>
      <prov:key>k1</prov:key>
      <prov:entity prov:ref="e1"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>k2</prov:key>
      <prov:entity prov:ref="e2"/>
    </prov:keyEntityPair>
  </prov:derivedByInsertionFrom>
  
</prov:document>

6.5 Removal

To specify that one dictionary was derived by removal of key-entity pairs from another one, a prov:Removal element is used.

<xs:complexType xmlns:xs="http://www.w3.org/2001/XMLSchema" name="Removal">
  <xs:sequence>
    <xs:element name="newDictionary" type="prov:IDRef"/>
    <xs:element name="oldDictionary" type="prov:IDRef"/>
    <xs:element name="key" type="xs:anySimpleType" minOccurs="1" maxOccurs="unbounded" />
    <xs:element ref="prov:label" minOccurs="0" maxOccurs="unbounded"/>
    <xs:element ref="prov:type" minOccurs="0" maxOccurs="unbounded"/>
    <xs:any namespace="##other" processContents="lax" minOccurs="0" maxOccurs="unbounded"/>
  </xs:sequence>
  <xs:attribute ref="prov:id"/>
</xs:complexType>

<xs:element xmlns:xs="http://www.w3.org/2001/XMLSchema" name="derivedByRemovalFrom" type="prov:Removal" substitutionGroup="prov:internalElement"/>

Example 8

<prov:document
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
    xmlns:prov="http://www.w3.org/ns/prov#">

  <prov:entity prov:id="e0"/>
  <prov:entity prov:id="e1"/>
  <prov:entity prov:id="e2"/>

  <prov:dictionary prov:id="d1" />
  
  <prov:dictionary prov:id="d2" />

  <prov:hadDictionaryMember>
    <prov:dictionary prov:ref="d1"/>
    <prov:keyEntityPair>
      <prov:key>k0</prov:key>
      <prov:entity prov:ref="e0"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>k1</prov:key>
      <prov:entity prov:ref="e1"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>k2</prov:key>
      <prov:entity prov:ref="e2"/>
    </prov:keyEntityPair>
  </prov:hadDictionaryMember>
  
  <prov:derivedByRemovalFrom>
    <prov:newDictionary prov:ref="d2"/>
    <prov:oldDictionary prov:ref="d1"/>
    <prov:key>k1</prov:key>
    <prov:key>k2</prov:key>
  </prov:derivedByRemovalFrom>
  
</prov:document>

7. Constraints Associated with Dictionary

In this section, we specify some inferences and constraints associated with dictionaries. These inferences and constraints MAY be applied to obtain valid provenance when using dictionaries. For more information about valid provenance and its purpose, we refer to the disclaimer in [PROV-CONSTRAINTS]. Whereas collections were deliberately left unconstrained in [PROV-DM] and [PROV-CONSTRAINTS] to remain as general as possible, dictionaries are intended to provide more structure, and thus, are constrained more strictly. For more information on how to read this section, we refer to [PROV-CONSTRAINTS].

7.1 Notation and Conventions

In the constraints below, statements are made concerning the equality of sets of key-entity pairs and sets of keys. For the sake of clarity, we will explain the used notations here.

To state that a set of keys K1 and another set of keys K2 hold exactly the same keys, we use the notation K1 = K2.
To state that a set of key-entity pairs KV1 and another set of key-entity pairs KV2 hold exactly the same keys, with each key in KV1 mapped to exactly the same entity as the same key in KV2, we use the notation KV1 = KV2.

For example. the sets of keys {"k1", "k2"} and {"k1", "k3", "k4"} are not considered equal, since one of the sets holds keys the other does not. Analogously, the set of key-entity pairs {("k1", e1),("k2", e2)} and the set {("k1", e2),("k2", e3)} are not considered equal, since the keys in the latter set map to different values than the same keys in the former set. The sets {("k1",e1),("k2",e2)} and {("k2",e2),("k1",e1)} are equal, because they hold the same keys, mapped to the same values, regardless of ordering.

7.2 Inferences

Dictionary membership implies collection membership.

Inference D1 (dictionary-membership-collection-membership)

IF prov:hadDictionaryMember(d, e1, k1) THEN hadMember(d, e1)

Collection membership for collections that are dictionaries implies dictionary membership.

Inference D2 (collection-membership-dictionary-membership)

IF hadMember(d, e) and 'prov:Dictionary' ∈ typeOf(d) THEN there exists a key k such that prov:hadDictionaryMember(d, e, k)

Each key maps to a single entity.

Inference D3 (key-single-entity)

IF prov:hadDictionaryMember(d1, e1, k1) and prov:hadDictionaryMember(d1, e2, k1) THEN e1 = e2

No key-entity pairs were added to or removed from a dictionary derived by insertion, except those added or updated by the insertion.

Inference D4 (membership-insertion-membership)

Here, KV1 is a set of key-entity pairs and K1 is the key-set of KV1.

IF prov:hadDictionaryMember(d1, e, k) and prov:derivedByInsertionFrom(d2, d1, KV1) and k ∉ K1 THEN prov:hadDictionaryMember(d2, e, k)
IF prov:hadDictionaryMember(d2, e, k) and prov:derivedByInsertionFrom(d2, d1, KV1) and k ∉ K1 THEN prov:hadDictionaryMember(d1, e, k)

No key-entity pairs were added to or removed from a dictionary derived by removal, except those specified by the removal.

Inference D5 (membership-removal-membership)

Here, K1 is a set of keys.

IF prov:hadDictionaryMember(d1, e, k) and prov:derivedByRemovalFrom(d2, d1, K1) and k ∉ K1 THEN prov:hadDictionaryMember(d2, e, k)
IF prov:hadDictionaryMember(d2, e, k) and prov:derivedByRemovalFrom(d2, d1, K1) THEN prov:hadDictionaryMember(d1, e, k)

Note that inferences D4 and D5, together with constraints D9, D10 , D11 and D12, and the fact that an EmptyDictionary does not contain any key-entity pairs (as formalized in PROV-Constraints), guarantee completeness of a dictionary, if it can be traced back to an EmptyDictionary through insertions and removals. Here, completeness means that all key-entity pairs of the dictionary are known through a hadDictionaryMember statement.

A dictionary that was derived by an insertion of key-entity pairs, holds all these specified key-entity pairs. This inference also means that Insertion provides an "update semantics" for the keys that are already present in a dictionary.

Inference D6 (insertion-membership)

Here, KV1 is a set of key-entity pairs.

IF prov:derivedByInsertionFrom(d2, d1, KV1) THEN prov:hadDictionaryMember(d2, e, k) for each (k, e) ∈ KV1

Insertion and removal are special cases of derivation.

Inference D7 (insertion-derivation)

Here, KV1 is a set of key-entity pairs.

IF prov:derivedByInsertionFrom(d2, d1, KV1) THEN prov:wasDerivedFrom(d2, d1)

Inference D8 (removal-derivation)

Here, K1 is a set of keys.

IF prov:derivedByRemovalFrom(d2, d1, K1) THEN prov:wasDerivedFrom(d2, d1)

7.3 Constraints

A dictionary that was derived by removal from another dictionary, cannot contain the key-entity pairs that were removed from the latter.

Constraint D9 (impossible-removal-membership)

Here, K1 is a set of key-entity pairs.

IF prov:derivedByRemovalFrom(d2, d1, K1) and prov:hadDictionaryMember(d2, e, k) and k ∈ K1 THEN INVALID

A dictionary must not be derived through multiple insertion or removal relations.

Constraint D10 (impossible-removal-insertion)

Here, K0 is a set of keys and KV1 is a set of key-entity pairs.

IF prov:derivedByRemovalFrom(d2, d0, K0) and prov:derivedByInsertionFrom(d2, d1, KV1)THEN INVALID

Constraint D11 (unique-insertion)

Here, KV0 and KV1 are sets of key-entity pairs.

IF prov:derivedByInsertionFrom(d2, d0, KV0) and prov:derivedByInsertionFrom(d2, d1, KV1)THEN d0 = d1 and KV1 = KV2

Constraint D12 (unique-removal)

Here, K0 and K1 are sets of keys.

IF prov:derivedByRemovalFrom(d2, d0, K0) and prov:derivedByRemovalFrom(d2, d1, K1)THEN d0 = d1 and K1 = K2

7.4 Typing

Constraint D13 (typing)

IF entity(d, [prov:type='prov:Dictionary']) THEN 'prov:Dictionary' ∈ typeOf(d) and 'prov:Collection' ∈ typeOf(d) and 'entity' ∈ typeOf(d)
IF entity(d, [prov:type='prov:EmptyDictionary']) THEN 'prov:EmptyDictionary' ∈ typeOf(d) and 'prov:Dictionary' ∈ typeOf(d) and 'prov:Collection' ∈ typeOf(d) and 'prov:EmptyCollection' ∈ typeOf(d) and 'entity' ∈ typeOf(d)
IF prov:hadDictionaryMember(d, e, "k") THEN 'prov:Dictionary' ∈ typeOf(d) and 'prov:Collection' ∈ typeOf(d) and 'entity' ∈ typeOf(d) and 'entity' ∈ typeOf(e)
Here, KV is a set of key-entity pairs

IF prov:derivedByInsertionFrom(d2, d1, KV) THEN 'prov:Dictionary' ∈ typeOf(d1) and 'prov:Dictionary' ∈ typeOf(d2) and 'prov:Collection' ∈ typeOf(d1) and 'entity' ∈ typeOf(d1) and 'prov:Collection' ∈ typeOf(d2) and 'entity' ∈ typeOf(d2) and 'entity' ∈ typeOf(e1)
Here, K is a set of keys

IF prov:derivedByRemovalFrom(d2, d1, K) THEN 'prov:Dictionary' ∈ typeOf(d1) and 'prov:Dictionary' ∈ typeOf(d2) and 'prov:Collection' ∈ typeOf(d1) and 'entity' ∈ typeOf(d1) and 'prov:Collection' ∈ typeOf(d2) and 'entity' ∈ typeOf(d2)

A. Example

To further clarify the use of PROV-Dictionary, we present its use in a practical scenario: tracking the provenance of a baseball team and its field positions. In this scenario, we consider the players of the team in two consecutive seasons, and the field positions of the two opening day lineups. As example data, we use the information that is publicly available on the Wikipedia page of the Boston Red Sox 2011 season and 2012 season.

A.1 Data

Player roster in 2011:

Uniform Number	Player	Uniform Number	Player	Uniform Number	Player	Uniform Number	Player

91	Alfredo Aceves	32	Matt Albers	48	Scott Atchison	51	Daniel Bard
19	Josh Beckett	23	Érik Bédard	64	Michael Bowden	11	Clay Buchholz
61	Félix Doubront	53	Rich Hill	68	Tommy Hottovy	52	Bobby Jenks
41	John Lackey	31	Jon Lester	18	Daisuke Matsuzaka	30	Andrew Miller
56	Trever Miller	46	Franklin Morales	37	Hideki Okajima	58	Jonathan Papelbon
59	Dennys Reyes	63	Junichi Tazawa	49	Tim Wakefield	70	Kyle Weiland
35	Dan Wheeler	43	Randy Williams	60	Ryan Lavarnway	39	Jarrod Saltalamacchia
33	Jason Varitek	62	Lars Anderson	3	Mike Avilés	28	Adrian Gonzalez
76	José Iglesias	12	Jed Lowrie	60	Yamaico Navarro	34	David Ortiz
15	Dustin Pedroia	10	Marco Scutaro	71	Nate Spears	44	Drew Sutton
20	Kevin Youkilis	23	Mike Cameron	13	Carl Crawford	7	J. D. Drew
2	Jacoby Ellsbury	55	Joey Gathright	36	Conor Jackson	54	Darnell McDonald
16	Josh Reddick

Player roster in 2012:

Uniform Number	Player	Uniform Number	Player	Uniform Number	Player	Uniform Number	Player

91	Alfredo Aceves	32	Matt Albers	48	Scott Atchison	40	Andrew Bailey
51	Daniel Bard	54	Pedro Beato	19	Josh Beckett	64	Michael Bowden
32	Craig Breslow	11	Clay Buchholz	52	Chris Carpenter	35	Aaron Cook
61	Félix Doubront	47	Justin Germano	53	Rich Hill	31	Jon Lester
18	Daisuke Matsuzaka	37	Mark Melancon	30	Andrew Miller	46	Franklin Morales
59	Clayton Mortensen	44	Vicente Padilla	47	Zach Stewart	63	Junichi Tazawa
78	Justin Thomas	60	Ryan Lavarnway	62	Guillermo Quiróz	39	Jarrod Saltalamacchia
10	Kelly Shoppach	62	Lars Anderson	3	Mike Avilés	77	Pedro Ciriaco
56	Iván DeJesús, Jr.	50	Mauro Gomez	28	Adrian Gonzalez	58	José Iglesias
23	Brent Lillibridge	22	James Loney	64	Will Middlebrooks	34	David Ortiz
15	Dustin Pedroia	5	Nick Punto	71	Nate Spears	23	Danny Valencia
20	Kevin Youkilis	23	Marlon Byrd	13	Carl Crawford	2	Jacoby Ellsbury
70	Ryan Kalish	85	Che-Hsuan Lin	54	Darnell McDonald	66	Daniel Nava
26	Scott Podsednik	16	Jason Repko	7	Cody Ross	12	Ryan Sweeney

Field positions of opening game in 2011:

Position	Player

CF	Jacoby Ellsbury
2B	Dustin Pedroia
1B	Adrian Gonzalez
DH	David Ortiz
3B	Kevin Youkilis
RF	Mike Cameron
LF	Carl Crawford
C	Jarrod Saltalamacchia
SS	Marco Scutaro
SP	Jon Lester

Field positions of opening game in 2012:

Position	Player

CF	Jacoby Ellsbury
2B	Dustin Pedroia
1B	Adrian Gonzalez
DH	David Ortiz
3B	Kevin Youkilis
RF	Ryan Sweeney
LF	Cody Ross
C	Jarrod Saltalamacchia
SS	Mike Avilés
SP	Jon Lester

A.2 Provenance

In this section, the provenance of the data is asserted in each of the three serializations described in this document.

A.2.1 PROV-N

The following is an excerpt of the complete provenance, not listing all the player entities to avoid overloading this document. The complete provenance is available for download as a separate file.

document
  prefix ex <http://example.org>
  prefix dbpedia <http://dbpedia.org/resource/>
  ////////////////
  //All Players//
  ////////////////
  ... //see external file for complete provenance
  ///////////////
  //2011 Roster//
  ///////////////
  entity(ex:roster_2011, [prov:type="prov:Dictionary])
  ... //see external file for complete provenance
  ///////////////////////////
  //2011 Opening Day lineup//
  ///////////////////////////
  entity(ex:opening_day_lineup_2011, [prov:type="prov:Dictionary])
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Jacoby_Ellsbury, "CF")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Dustin_Pedroia, "2B")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Adrian_Gonzalez, "1B")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:David_Ortiz, "DH")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Kevin_Youkilis, "3B")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Mike_Cameron, "RF")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Carl_Crawford, "LF")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Jarrod_Saltalamacchia, "C")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Marco_Scutaro, "SS")
  prov:hadDictionaryMember(ex:opening_day_lineup_2011, dbpedia:Jon_Lester, "SP")
  //////////////////////////////////////////////////////////////////////////////////////////////////
  //2011 roster without players that left the team after the 2011 season or changed uniform number//
  //////////////////////////////////////////////////////////////////////////////////////////////////
  entity(ex:roster_2011_after_removals, prov:type="prov:Dictionary")
  prov:wasDerivedByRemovalFrom(ex:roster_2011_after_removals, ex:roster_2011, 
    {"10", "12", "16", "23", "23", "33", "35", "36", "37", "41", "43", "44", "49", "52", "55", "56",
    "58", "59", "60", "68", "7", "70", "76"})
  ///////////////
  //2012 Roster//
  ///////////////
  entity(ex:roster_2012, [prov:type="prov:Dictionary])
  prov:wasDerivedByInsertionFrom(ex:roster_2012, ex:roster_2011_after_removals, {
    ("10", dbpedia:Kelly_Shoppach),
    ("12", dbpedia:Ryan_Sweeney),
    ("16", dbpedia:Jason_Repko),
    ("22", dbpedia:James_Loney_(baseball)),
    ("23", dbpedia:Brent_Lillibridge),
    ("23", dbpedia:Danny_Valencia),
    ("23", dbpedia:Marlon_Byrd),
    ("26", dbpedia:Scott_Podsednik),
    ("32", dbpedia:Craig_Breslow),
    ("35", dbpedia:Aaron_Cook_(baseball)),
    ("37", dbpedia:Mark_Melancon),
    ("40", dbpedia:Andrew_Bailey_(baseball)),
    ("44", dbpedia:Vicente_Padilla),
    ("47", dbpedia:Justin_Germano),
    ("47", dbpedia:Zach_Stewart),
    ("5", dbpedia:Nick_Punto),
    ("50", dbpedia:Mauro_Gomez),
    ("52", dbpedia:Chris_Carpenter),
    ("54", dbpedia:Pedro_Beato),
    ("56", dbpedia:Ivan_DeJesus,_Jr.),
    ("58", dbpedia:Jose_Iglesias_(baseball)),
    ("59", dbpedia:Clayton_Mortensen),
    ("62", dbpedia:Guillermo_Quiroz),
    ("64", dbpedia:Will_Middlebrooks),
    ("66", dbpedia:Daniel_Nava),
    ("7", dbpedia:Cody_Ross),
    ("70", dbpedia:Ryan_Kalish),
    ("77", dbpedia:Pedro_Ciriaco),
    ("78", dbpedia:Justin_Thomas),
    ("85", dbpedia:Che-Hsuan_Lin)
  })
  ///////////////////////////////////////////////////////
  //2012 Opening Day lineup (update of 2011 dictionary)//
  ///////////////////////////////////////////////////////
  entity(ex:opening_day_lineup_2012, [prov:type="prov:Dictionary])
  prov:wasDerivedByInsertionFrom(ex:opening_day_lineup_2012, ex:opening_day_lineup_2011, {
    ("RF", dbpedia:Ryan_Sweeney"),
    ("LF", dbpedia:Cody_Ross"),
    ("SS", dbpedia:Mike_Aviles"),
  })
  
endDocument

A.2.2 PROV-O

The following is an excerpt of the complete provenance, not listing all the player entities to avoid overloading this document. The complete provenance is available for download as a separate file.

@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix dbpedia: <http://dbpedia.org/resource/> .
@prefix ex: <http://example.com/> .

#All Player Entities, see complete provenance file.
...
 
#2011 Roster
ex:roster_2011 
  a prov:Entity, prov:Dictionary;
  ... #For all dictionary members, see complete provenance file.
  .
  
#2011 Opening Day lineup
ex:opening_day_lineup_2011 
  a prov:Entity, prov:Dictionary;
  prov:hadDictionaryMember [
    a prov:KeyEntityPair;
    prov:pairKey "CF"^^xsd:string;
    prov:pairEntity dbpedia:Jacoby_Ellsbury;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "2B"^^xsd:string;
    prov:pairEntity dbpedia:Dustin_Pedroia;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "1B"^^xsd:string;
    prov:pairEntity dbpedia:Adrian_Gonzalez;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "DH"^^xsd:string;
    prov:pairEntity dbpedia:David_Ortiz;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "3B"^^xsd:string;
    prov:pairEntity dbpedia:Kevin_Youkilis;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "RF"^^xsd:string;
    prov:pairEntity dbpedia:Mike_Cameron;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "LF"^^xsd:string;
    prov:pairEntity dbpedia:Carl_Crawford;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "C"^^xsd:string;
    prov:pairEntity dbpedia:Jarrod_Saltalamacchia;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "SS"^^xsd:string;
    prov:pairEntity dbpedia:Marco_Scutaro;
  ],  [ 
    a prov:KeyEntityPair;
    prov:pairKey "SP"^^xsd:string;
    prov:pairEntity dbpedia:Jon_Lester;
  ] .
  
#2011 roster without players that left the team after the 2011 season or changed uniform number
ex:roster_2011_after_removals
  a prov:Entity, prov:Dictionary;
  prov:derivedByRemovalFrom ex:roster_2011;
  prov:qualifiedRemoval [
    a prov:Removal;
    prov:dictionary ex:roster_2011;
    prov:removedKey "10"^^xsd:string, "12"^^xsd:string, "16"^^xsd:string, "23"^^xsd:string,
                    "23"^^xsd:string, "33"^^xsd:string, "35"^^xsd:string, "36"^^xsd:string,
                    "37"^^xsd:string, "41"^^xsd:string, "43"^^xsd:string, "44"^^xsd:string,
                    "49"^^xsd:string, "52"^^xsd:string, "55"^^xsd:string, "56"^^xsd:string,
                    "58"^^xsd:string, "59"^^xsd:string, "60"^^xsd:string, "68"^^xsd:string,
                    "7"^^xsd:string, "70"^^xsd:string, "76"^^xsd:string;
    ] .
    
#2012 Roster
ex:roster_2012
  a prov:Entity, prov:Dictionary;
  prov:derivedByInsertionFrom ex:roster_2011_after_removals;
  prov:qualifiedInsertion [
    a prov:Insertion;
    prov:insertedKeyEntityPair [ 
      prov:pairKey "10"^^xsd:string;
      prov:pairEntity dbpedia:Kelly_Shoppach;
    ], [
      prov:pairKey "12"^^xsd:string;
      prov:pairEntity dbpedia:Ryan_Sweeney;
    ], [
      prov:pairKey "16"^^xsd:string;
      prov:pairEntity dbpedia:Jason_Repko;
    ], [
      prov:pairKey "22"^^xsd:string;
      prov:pairEntity <http://dbpedia.org/resource/James_Loney_(baseball)>;
    ], [
      prov:pairKey "23"^^xsd:string;
      prov:pairEntity dbpedia:Brent_Lillibridge;
    ], [
      prov:pairKey "23"^^xsd:string;
      prov:pairEntity dbpedia:Danny_Valencia;
    ], [
      prov:pairKey "23"^^xsd:string;
      prov:pairEntity dbpedia:Marlon_Byrd;
    ], [
      prov:pairKey "26"^^xsd:string;
      prov:pairEntity dbpedia:Scott_Podsednik;
    ], [
      prov:pairKey "32"^^xsd:string;
      prov:pairEntity dbpedia:Craig_Breslow;
    ], [
      prov:pairKey "35"^^xsd:string;
      prov:pairEntity <http://dbpedia.org/resource/Aaron_Cook_(baseball)>;
    ], [
      prov:pairKey "37"^^xsd:string;
      prov:pairEntity dbpedia:Mark_Melancon;
    ], [
      prov:pairKey "40"^^xsd:string;
      prov:pairEntity <http://dbpedia.org/resource/Andrew_Bailey_(baseball)>;
    ], [
      prov:pairKey "44"^^xsd:string;
      prov:pairEntity dbpedia:Vicente_Padilla;
    ], [
      prov:pairKey "47"^^xsd:string;
      prov:pairEntity dbpedia:Justin_Germano;
    ], [
      prov:pairKey "47"^^xsd:string;
      prov:pairEntity dbpedia:Zach_Stewart;
    ], [
      prov:pairKey "5"^^xsd:string;
      prov:pairEntity dbpedia:Nick_Punto;
    ], [
      prov:pairKey "50"^^xsd:string;
      prov:pairEntity dbpedia:Mauro_Gomez;
    ], [
      prov:pairKey "52"^^xsd:string;
      prov:pairEntity dbpedia:Chris_Carpenter;
    ], [
      prov:pairKey "54"^^xsd:string;
      prov:pairEntity dbpedia:Pedro_Beato;
    ], [
      prov:pairKey "56"^^xsd:string;
      prov:pairEntity <http://dbpedia.org/resource/Ivan_DeJesus,_Jr.>;
    ], [
      prov:pairKey "58"^^xsd:string;
      prov:pairEntity <http://dbpedia.org/resource/Jose_Iglesias_(baseball)>;
    ], [
      prov:pairKey "59"^^xsd:string;
      prov:pairEntity dbpedia:Clayton_Mortensen;
    ], [
      prov:pairKey "62"^^xsd:string;
      prov:pairEntity dbpedia:Guillermo_Quiroz;
    ], [
      prov:pairKey "64"^^xsd:string;
      prov:pairEntity dbpedia:Will_Middlebrooks;
    ], [
      prov:pairKey "66"^^xsd:string;
      prov:pairEntity dbpedia:Daniel_Nava;
    ], [
      prov:pairKey "7"^^xsd:string;
      prov:pairEntity dbpedia:Cody_Ross;
    ], [
      prov:pairKey "70"^^xsd:string;
      prov:pairEntity dbpedia:Ryan_Kalish;
    ], [
      prov:pairKey "77"^^xsd:string;
      prov:pairEntity dbpedia:Pedro_Ciriaco;
    ], [
      prov:pairKey "78"^^xsd:string;
      prov:pairEntity dbpedia:Justin_Thomas;
    ], [
      prov:pairKey "85"^^xsd:string;
      prov:pairEntity dbpedia:Che-Hsuan_Lin;
    ];
  ] .

#2012 Opening Day lineup (update of 2011 dictionary)
ex:opening_day_lineup_2012
  a prov:Entity, prov:Dictionary;
  prov:wasDerivedByInsertionFrom ex:opening_day_lineup_2011;
  prov:qualifiedInsertion [
    a prov:Insertion;
    prov:insertedKeyEntityPair [
      a prov:KeyEntityPair;
      prov:pairKey "RF"^^xsd:string;
      prov:pairEntity dbpedia:Ryan_Sweeney;
    ],[
      a prov:KeyEntityPair;
      prov:pairKey "LF"^^xsd:string;
      prov:pairEntity dbpedia:Cody_Ross;
    ],[
      a prov:KeyEntityPair;
      prov:pairKey "SS"^^xsd:string;
      prov:pairEntity dbpedia:Mike_Aviles;
    ];
  ] .

A.2.3 PROV-XML

The following is an excerpt of the complete provenance, not listing all the player entities to avoid overloading this document. The complete provenance is available for download as a separate file.

<?xml version="1.0" encoding="UTF-8"?>
<prov:document
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
    xmlns:prov="http://www.w3.org/ns/prov#"
    xmlns:dbpedia="http://dbpedia.org/resource/"
    xmlns:ex="http://example.com/"
    xsi:schemaLocation="http://www.w3.org/ns/prov#
http://www.w3.org/ns/prov.xsd ">
  <!-- All Player Entities -->
  ... <!-- See complete provenance file -->
  
  <!-- 2011 Roster -->
  <prov:dictionary prov:id="ex:roster_2011" />
  <prov:hadDictionaryMember>
    <prov:dictionary prov:ref="ex:roster_2011"/>
    ... <!-- See complete provenance file -->
  </prov:hadDictionaryMember>
  
  <!-- 2011 Opening Day lineup -->
  <prov:dictionary prov:id="ex:opening_day_lineup_2011" />
  <prov:hadDictionaryMember>
    <prov:dictionary prov:ref="ex:opening_day_lineup_2011"/>
    <prov:keyEntityPair>
      <prov:key>CF</prov:key>
      <prov:entity prov:ref="dbpedia:Jacoby_Ellsbury"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>2B</prov:key>
      <prov:entity prov:ref="dbpedia:Dustin_Pedroia"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>1B</prov:key>
      <prov:entity prov:ref="dbpedia:Adrian_Gonzalez"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>DH</prov:key>
      <prov:entity prov:ref="dbpedia:David_Ortiz"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>3B</prov:key>
      <prov:entity prov:ref="dbpedia:Kevin_Youkilis"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>RF</prov:key>
      <prov:entity prov:ref="dbpedia:Mike_Cameron"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>LF</prov:key>
      <prov:entity prov:ref="dbpedia:Carl_Crawford"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>C</prov:key>
      <prov:entity prov:ref="dbpedia:Jarrod_Saltalamacchia"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>SS</prov:key>
      <prov:entity prov:ref="dbpedia:Marco_Scutaro"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair> 
      <prov:key>SP</prov:key>
      <prov:entity prov:ref="dbpedia:Jon_Lester"/>
    </prov:keyEntityPair>
  </prov:hadDictionaryMember>
  
  <!-- 2011 roster without players that left the team after the 2011 season or changed uniform number -->
  <prov:dictionary prov:id="ex:roster_2011_after_removals" />
  <prov:derivedByRemovalFrom>
    <prov:newDictionary prov:ref="ex:roster_2011_after_removals"/>
    <prov:oldDictionary prov:ref="ex:roster_2011"/>
    <prov:key>10</prov:key>
    <prov:key>12</prov:key>
    <prov:key>16</prov:key>
    <prov:key>23</prov:key>
    <prov:key>23</prov:key>
    <prov:key>33</prov:key>
    <prov:key>35</prov:key>
    <prov:key>36</prov:key>
    <prov:key>37</prov:key>
    <prov:key>41</prov:key>
    <prov:key>43</prov:key>
    <prov:key>44</prov:key>
    <prov:key>49</prov:key>
    <prov:key>52</prov:key>
    <prov:key>55</prov:key>
    <prov:key>56</prov:key>
    <prov:key>58</prov:key>
    <prov:key>59</prov:key>
    <prov:key>60</prov:key>
    <prov:key>68</prov:key>
    <prov:key>7</prov:key>
    <prov:key>70</prov:key>
    <prov:key>76</prov:key>
  </prov:derivedByRemovalFrom>
  
  <!-- 2012 Roster -->
  <prov:dictionary prov:id="ex:roster_2012" />
  <prov:derivedByInsertionFrom>
    <prov:newDictionary prov:ref="ex:roster_2012"/>
    <prov:oldDictionary prov:ref="ex:roster_2011_after_removals"/>
    <prov:keyEntityPair> 
      <prov:key>10</prov:key>
      <prov:entity prov:ref="dbpedia:Kelly_Shoppach"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>12</prov:key>
      <prov:entity prov:ref="dbpedia:Ryan_Sweeney"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>16</prov:key>
      <prov:entity prov:ref="dbpedia:Jason_Repko"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>22</prov:key>
      <prov:entity xmlns:dbpedia="http://dbpedia.org/resource/James_Loney_(baseball)#" prov:ref="dbpedia:James_Loney_baseball"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>23</prov:key>
      <prov:entity prov:ref="dbpedia:Brent_Lillibridge"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>23</prov:key>
      <prov:entity prov:ref="dbpedia:Danny_Valencia"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>23</prov:key>
      <prov:entity prov:ref="dbpedia:Marlon_Byrd"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>26</prov:key>
      <prov:entity prov:ref="dbpedia:Scott_Podsednik"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>32</prov:key>
      <prov:entity prov:ref="dbpedia:Craig_Breslow"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>35</prov:key>
      <prov:entity xmlns:dbpedia="http://dbpedia.org/resource/Aaron_Cook_(baseball)#" prov:ref="dbpedia:Aaron_Cook_baseball"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>37</prov:key>
      <prov:entity prov:ref="dbpedia:Mark_Melancon"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>40</prov:key>
      <prov:entity xmlns:dbpedia="http://dbpedia.org/resource/Andrew_Bailey_(baseball)#" prov:ref="dbpedia:Andrew_Bailey_baseball"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>44</prov:key>
      <prov:entity prov:ref="dbpedia:Vicente_Padilla"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>47</prov:key>
      <prov:entity prov:ref="dbpedia:Justin_Germano"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>47</prov:key>
      <prov:entity prov:ref="dbpedia:Zach_Stewart"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>5</prov:key>
      <prov:entity prov:ref="dbpedia:Nick_Punto"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>50</prov:key>
      <prov:entity prov:ref="dbpedia:Mauro_Gomez"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>52</prov:key>
      <prov:entity prov:ref="dbpedia:Chris_Carpenter"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>54</prov:key>
      <prov:entity prov:ref="dbpedia:Pedro_Beato"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>56</prov:key>
      <prov:entity prov:ref="dbpedia:Ivan_DeJesus_Jr."/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>58</prov:key>
      <prov:entity xmlns:dbpedia="http://dbpedia.org/resource/Jose_Iglesias_(baseball)#" prov:ref="dbpedia:Jose_Iglesias_baseball"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>59</prov:key>
      <prov:entity prov:ref="dbpedia:Clayton_Mortensen"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>62</prov:key>
      <prov:entity prov:ref="dbpedia:Guillermo_Quiroz"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>64</prov:key>
      <prov:entity prov:ref="dbpedia:Will_Middlebrooks"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>66</prov:key>
      <prov:entity prov:ref="dbpedia:Daniel_Nava"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>7</prov:key>
      <prov:entity prov:ref="dbpedia:Cody_Ross"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>70</prov:key>
      <prov:entity prov:ref="dbpedia:Ryan_Kalish"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>77</prov:key>
      <prov:entity prov:ref="dbpedia:Pedro_Ciriaco"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>78</prov:key>
      <prov:entity prov:ref="dbpedia:Justin_Thomas"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>85</prov:key>
      <prov:entity prov:ref="dbpedia:Che-Hsuan_Lin"/>
    </prov:keyEntityPair>
  </prov:derivedByInsertionFrom>
  
  <!-- 2012 Opening Day lineup (update of 2011 dictionary) -->
  <prov:dictionary prov:id="ex:opening_day_lineup_2012" />
  <prov:derivedByInsertionFrom>
    <prov:newDictionary prov:ref="ex:opening_day_lineup_2012"/>
    <prov:oldDictionary prov:ref="ex:opening_day_lineup_2011"/>
    <prov:keyEntityPair>
      <prov:key>RF</prov:key>
      <prov:entity prov:ref="dbpedia:Ryan_Sweeney"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>LF</prov:key>
      <prov:entity prov:ref="dbpedia:Cody_Ross"/>
    </prov:keyEntityPair>
    <prov:keyEntityPair>
      <prov:key>SS</prov:key>
      <prov:entity prov:ref="dbpedia:Mike_Aviles"/>
    </prov:keyEntityPair>
  </prov:derivedByInsertionFrom>
</prov:document>

Note that certain disambiguated dbpedia URIs contain parentheses, and thus cannot be turned into valid XML namespace-qualified names (QName). For URIs like these, we add a valid NCName (derived by removing the invalid characters) as a fragment, and split the URI after the # symbol. The first part of the URI is then used to override the dbpedia: prefix in the element that uses the URI as an identifier, and the valid NCName is used as the LocalPart of the QName.

For example:
<prov:entity xmlns:dbpedia="http://dbpedia.org/resource/Jose_Iglesias_(baseball)#" prov:ref="dbpedia:Jose_Iglesias_baseball"/>

While it can be argued whether or not this practice is entirely desirable, it does follow the guidance given in the RDF/XML Syntax Specification.

B. Change Log

B.1 Change Log Since First Public Working Draft

Added the full title of the document.
Added namespace and convention sections.
Made prov: prefix explicit.
Changed all mentions of "key-value pair" to the more accurate "key-entity pair".
Clarified that insertions and removals are to be seen as differences rather than as operations in the context of provenance.
Updated PROV-N grammar (renaming of concepts and restyling).
Made prov:qualifiedInsertion and prov:qualifiedRemoval sub-properties of qualifiedDerivation.
Updated XML schema definition.
Added an notations and conventions paragraph to the constraints.
Updated constraints after discussion within the Working Group.
Added example to the appendix.
Various corrections.

C. Acknowledgements

This document has been produced by the PROV Working Group, and its contents reflect extensive discussion within the Working Group as a whole. The editors would especially like to thank Paolo Missier, James Cheney, Luc Moreau, Paul Groth, Stian Soiland-Reyes, Khalid Belhajjame, Timothy Lebo, Curt Tilmes, Stephan Zednik, Graham Klyne and Simon Miles for their contributions and their detailed reviews of this document.

Members of the Provenance Working Group at the time of publication of this document were: Ilkay Altintas (Invited expert), Reza B'Far (Oracle Corporation), Khalid Belhajjame (University of Manchester), James Cheney (University of Edinburgh, School of Informatics), Sam Coppens (iMinds - Ghent University), David Corsar (University of Aberdeen, Computing Science), Stephen Cresswell (The National Archives), Tom De Nies (iMinds - Ghent University), Helena Deus (DERI Galway at the National University of Ireland, Galway, Ireland), Simon Dobson (Invited expert), Martin Doerr (Foundation for Research and Technology - Hellas(FORTH)), Kai Eckert (Invited expert), Jean-Pierre EVAIN (European Broadcasting Union, EBU-UER), James Frew (Invited expert), Irini Fundulaki (Foundation for Research and Technology - Hellas(FORTH)), Daniel Garijo (Universidad Politécnica de Madrid), Yolanda Gil (Invited expert), Ryan Golden (Oracle Corporation), Paul Groth (Vrije Universiteit), Olaf Hartig (Invited expert), David Hau (National Cancer Institute, NCI), Sandro Hawke (W3C/MIT), Jörn Hees (German Research Center for Artificial Intelligence (DFKI) Gmbh), Ivan Herman, (W3C/ERCIM), Ralph Hodgson (TopQuadrant), Hook Hua (Invited expert), Trung Dong Huynh (University of Southampton), Graham Klyne (University of Oxford), Michael Lang (Revelytix, Inc.), Timothy Lebo (Rensselaer Polytechnic Institute), James McCusker (Rensselaer Polytechnic Institute), Deborah McGuinness (Rensselaer Polytechnic Institute), Simon Miles (Invited expert), Paolo Missier (School of Computing Science, Newcastle university), Luc Moreau (University of Southampton), James Myers (Rensselaer Polytechnic Institute), Vinh Nguyen (Wright State University), Edoardo Pignotti (University of Aberdeen, Computing Science), Paulo da Silva Pinheiro (Rensselaer Polytechnic Institute), Carl Reed (Open Geospatial Consortium), Adam Retter (Invited Expert), Christine Runnegar (Invited expert), Satya Sahoo (Invited expert), David Schaengold (Revelytix, Inc.), Daniel Schutzer (FSTC, Financial Services Technology Consortium), Yogesh Simmhan (Invited expert), Stian Soiland-Reyes (University of Manchester), Eric Stephan (Pacific Northwest National Laboratory), Linda Stewart (The National Archives), Ed Summers (Library of Congress), Maria Theodoridou (Foundation for Research and Technology - Hellas(FORTH)), Ted Thibodeau (OpenLink Software Inc.), Curt Tilmes (National Aeronautics and Space Administration), Craig Trim (IBM Corporation), Stephan Zednik (Rensselaer Polytechnic Institute), Jun Zhao (University of Oxford), Yuting Zhao (University of Aberdeen, Computing Science).

D. References

D.1 Informative references

[PROV-AQ]: Graham Klyne; Paul Groth; eds. Provenance Access and Query. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-aq-20130430/
[PROV-CONSTRAINTS]: James Cheney; Paolo Missier; Luc Moreau; eds. Constraints of the PROV Data Model. 30 April 2013, W3C Recommendation. URL: http://www.w3.org/TR/2013/REC-prov-constraints-20130430/
[PROV-DC]: Daniel Garijo; Kai Eckert; eds. Dublin Core to PROV Mapping. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-dc-20130430/
[PROV-DM]: Luc Moreau; Paolo Missier; eds. PROV-DM: The PROV Data Model. 30 April 2013, W3C Recommendation. URL: http://www.w3.org/TR/2013/REC-prov-dm-20130430/
[PROV-LINKS]: Luc Moreau; Timothy Lebo; eds. Linking Across Provenance Bundles. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-links-20130430/
[PROV-N]: Luc Moreau; Paolo Missier; eds. PROV-N: The Provenance Notation. 30 April 2013, W3C Recommendation. URL: http://www.w3.org/TR/2013/REC-prov-n-20130430/
[PROV-O]: Timothy Lebo; Satya Sahoo; Deborah McGuinness; eds. PROV-O: The PROV Ontology. 30 April 2013, W3C Recommendation. URL: http://www.w3.org/TR/2013/REC-prov-o-20130430/
[PROV-OVERVIEW]: Paul Groth; Luc Moreau; eds. PROV-OVERVIEW: An Overview of the PROV Family of Documents. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-overview-20130430/
[PROV-PRIMER]: Yolanda Gil; Simon Miles; eds. PROV Model Primer. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-primer-20130430/
[PROV-SEM]: James Cheney; ed. Semantics of the PROV Data Model. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-sem-20130430.
[PROV-XML]: Hook Hua; Curt Tilmes; Stephan Zednik; eds. PROV-XML: The PROV XML Schema. 30 April 2013, W3C Note. URL: http://www.w3.org/TR/2013/NOTE-prov-xml-20130430/

PROV-Dictionary: Modeling Provenance for Dictionary Data Structures

W3C Working Group Note 30 April 2013

Abstract

Status of This Document

PROV Family of Documents

Implementations Encouraged

Please Send Comments

Table of Contents

1. Introduction

2. PROV Namespace

3. Conceptual Definition of Dictionary

3.1 Dictionary Membership

3.2 Dictionary Insertion

3.3 Dictionary Removal

4. PROV-N Notation of Dictionary Concepts

4.1 Dictionary and EmptyDictionary Expression

4.2 Dictionary Membership

4.3 Insertion

4.4 Removal

4.5 Other expressions

5. PROV-O Representation of Dictionary

5.1 Overview

5.2 Dictionary Classes

Class: prov:Dictionary

Class: prov:EmptyDictionary

Class: prov:KeyEntityPair

Class: prov:Insertion

Class: prov:Removal

5.3 Dictionary Properties

Property: prov:derivedByInsertionFromop

Property: prov:derivedByRemovalFromop

Property: prov:dictionaryop

Property: prov:insertedKeyEntityPairop

Property: prov:hadDictionaryMemberop

Property: prov:pairKeydp

Property: prov:pairEntityop

Property: prov:qualifiedInsertionop

Property: prov:qualifiedRemovalop

Property: prov:removedKeydp

6. PROV-XML Representation of Dictionary

6.1 Dictionary

6.2 Key-Entity Pair

6.3 Dictionary Membership

6.4 Insertion

6.5 Removal

7. Constraints Associated with Dictionary

7.1 Notation and Conventions

7.2 Inferences

7.3 Constraints

7.4 Typing

A. Example

A.1 Data

A.2 Provenance

A.2.1 PROV-N

A.2.2 PROV-O

A.2.3 PROV-XML

B. Change Log

B.1 Change Log Since First Public Working Draft

C. Acknowledgements

D. References

D.1 Informative references

Property: prov:derivedByInsertionFrom^op

Property: prov:derivedByRemovalFrom^op

Property: prov:dictionary^op

Property: prov:insertedKeyEntityPair^op

Property: prov:hadDictionaryMember^op

Property: prov:pairKey^dp

Property: prov:pairEntity^op

Property: prov:qualifiedInsertion^op

Property: prov:qualifiedRemoval^op

Property: prov:removedKey^dp