Overview

See also FormalSemantics

The idea of this document is to sketch what aspects of the provenance model can be formalized and how they can be formalized, as a first step towards establishing a consensus on the (intended) meaning of the components of the model and the consistency constraints or inferences that can be applied to the model to distinguish good from bad provenance records.

Idea of the semantics

As a starting point, I will assume that we intend the assertions made in a PROV-DM instance to be intended to describe one, consistent state of the world, much like a logical formula is said to be satisfied in a mathematical model. That is, I propose an approach similar to that taken in model theory, where the PROV-DM instance corresponds to a formula or theory of a logic, and the semantics corresponds to what logicians call a model.

For example, the formula <math>\forall x. x \geq 0</math> is satisfied in a mathematical model where the individual elements denotable by <math>x</math> are natural numbers, and the ordering relation symbol <math>\geq</math> is interpreted as the usual ordering relation on natural numbers. Here, the goal is to come up with a plausible "intended model" for interpreting PROV-DM instances, where the formulas are assertions in PROV-DM and the individuals are things and agents. This is complicated by the fact that many statements about provenance involve talking about objects that change over time.

The modeling methodology I'm using below is similar to that used in some (old, but still relevant) work on preservation: see [1]

The word "world" is used in PROV-DM to talk about the actual state of affairs that the PROV-DM instance describes, which is what I would usually call a "model". The word "model" is used in PROV-DM mainly in the sense of "data model", that is, to talk about what I would otherwise call the syntax of PROV-DM. To avoid confusion with the uses of terms in PROV-DM, I will use "world" to describe the actual state of affairs, and will try to avoid ambiguous uses of the word "model".

Basics

I will use syntax for PROV-DM assertions (= formulas) as described in the second working draft of PROV-DM.

A PROV-DM instance consisting of assertions <math>\phi_1</math>...<math>\phi_n</math> is interpreted as a conjunction, that is, the overall instance is considered to hold if each atomic formula in it holds.

The rest of the document will discuss the structure of the worlds and when an atomic assertion holds in a given world.

Identifiers

A lowercase symbol <math>x,y,...</math> on its own denotes an identifier. Identifiers may or may not be URIs. I view identifiers as being like variables in logic (or blank nodes in RDF): just because we have two different identifiers <math>x</math> and <math>y</math> doesn't tell us that they denote different things, since we could discover that they are actually the same later.

Times and Intervals

We assume an ordered set <math>(T,\leq)</math> of time instants. This could be a total order (i.e. a linear timeline) or a partial order describing events that are not necessarily reconciled to a single global clock. We also consider a set <math>Intervals</math> of pairs of times <math>[t_1,t_2]</math> such that <math>t_1 \leq t_2</math>. Intuitively, an interval denotes the set of all time instants between <math>t_1</math> and <math>t_2</math>, that is, <math>\{t \mid t_1 \leq t \leq t_2\}</math>.

Attributes and Values

We assume a set <math>Attributes</math> of attribute labels and a set <math>Values</math> of possible values of attributes.

Formulas

Summary of syntax of formulas from PROV-DM.

 formula ::= element_formula
          |  relation_formula
          |  ...
 element_formula
         ::= entity(id,attrs) 
          |  activity(id,st,et,attrs)
          |  agent(id,attrs)
          |  note(id, attrs)
 relation_formula
         ::= wasGeneratedBy(id,e,a,attrs,t)
          |  used(id,e,a,attrs,t)
          |  wasStartedBy(id,a,ag,attrs)
          |  wasEndedBy(id,a,ag,attrs)
          |  hasAnnotation(r,n,attrs)
          |  alternateOf(e1,e2)
          |  specializationOf(e1,e2)
          | ...

Some additional formulas defined in PROV-DM but not yet handled in the semantics are omitted.

Worlds

Things

Things are things in the world. Each thing has a lifetime during which it exists and attributes whose values can change over time.

To model this, a world includes

• a set <math>Things</math> of things
• a function <math>lifetime : Things \to Intervals</math> from objects to time intervals
• a function <math>value : Things \times Attributes \times Times \to Values</math>

Note that this description does not say what the structure of an object is, only how it may be described in terms of its time interval and attribute values. An object could just be a record of fixed attribute values; it could be a bear; it could be the Royal Society; it could be a transcendental number like <math>\pi</math>. All that matters from our point of view is that we know how to map the object to its time interval and attribute mapping.

It is possible for two Things to be indistinguishable by their attribute values and lifetime, but have different identity.

Objects

A Object is described by a time interval and attributes with unchanging values. Objects encompass entities, agents, events and activities.

To model this, a world includes

• a set <math>Objects</math>
• a function <math>lifetime : Objects \to Intervals</math> from objects to time intervals
• a function <math>value : Objects \times Attributes \to Values</math>

Intuitively, <math>lifetime(e)</math> is the time interval during which object <math>e</math> exists; and for each <math>t \in lifetime(e)</math>, the value <math>value(e,a)</math> is the value of attribute <math>a</math> during the object's lifetime.

As with Things, it is also possible to have two different objects that are indistinguishable by their attributes and time intervals.

Entities

An entity is a kind of object that describes a time-slice of a thing, during which some of the thing's attributes are fixed. We assume:

• a set <math>Entities \subseteq Objects</math> of entities, disjoint from <math>Activities</math> and <math>Events</math> below.
• a function <math>thingOf : Entities \to Things</math> that associates each Entity with a Thing, such that for each <math>t \in lifetime(obj)</math>, and each attribute defined by <math>obj</math>, we have <math>value(obj,a) = value(thingOf(obj),a,t)</math>

Agents

An agent is an entity that can act, by controlling, starting, ending, or participating in activities. Agents can act on behalf of other agents. We introduce:

• a set <math>Agents \subseteq Entities</math> of agents, which is also necessarily disjoint from <math>Activities</math> and <math>Events</math>
• a relation <math>ActsFor \subseteq Agents \times Agents</math> [TODO: This probably needs to be made time- and activity-dependent]

Events

(Note: The term event is controversial).

An event is an object whose lifetime is a single time instant, and relates an activity to an entity (which could be an agent). We introduce:

• A set <math>Events</math> of events, disjoint from <math>Entities</math> and <math>Activities</math>
• A function <math>time : Events \to Times</math> giving the time of each event
• The derived ordering on events given by <math>evt_1 \leq evt_2 \iff t(evt_1) \leq t(evt_2)</math>
• A function <math>type: Events \to \{start,end,use,generate\}</math>
• A relation <math>Used \subseteq Events \times Entities</math> saying when an event used an entity. An event can use at most one entity, and if <math>(evt,e)\in Used</math> then <math>time(evt) \in lifetime(e)</math> must hold.
• A relation <math>Generated \subseteq Events \times Entities</math> saying when an event generated an entity. An event can generate at most one entity, and an entity is generated by at most one event, and , and if <math>(evt,e)\in Generated</math> then <math>lifetime(e) = [time(evt),\_]</math> must hold.

Actvities

An activity is an object that encompasses a set of events. We introduce

• a set <math>Activities \subseteq Objects</math> of activities, disjoint from <math>Entities</math> and <math>Events</math>
• a relation <math>ActivityEvent \subseteq Activities \times Events</math> associating activities with events, satisfying <math>time(evt) \in lifetime(act)</math> whenever <math>(act,evt) \in ActivitiesEvents</math>.

1. Question: Does every activity need to be associated with some event?
2. Question: Does every event need to be associated with some activity?
3. Question: Can an event be associated with more than one activity?

(ISSUE-214: Luc suggests replaces <math>Generated,ActivityEvents</math> with <math>Generated : Events \times Entities \times Activities</math> and similar for <math>Used</math>).

Semantics

Interpretations

Note that the above discussion does not mention identifiers. We need to add structure to the world to link identifiers to the objects they denote. We do this using a function which we shall call an interpretation.

I will assume that the mapping from identifiers to objects may not change over time. Thus, we consider interpretations as follows:

• An interpretation function <math>I : Identifiers \to Objects</math> describing which object is the target of each identifier. We write the time argument as a subscript, i.e., <math>I(id)</math>.

Satisfaction

Consider an assertion <math>\phi</math>, a world <math>W</math> and an interpretation <math>I</math>. We define notation <math>W,I \models \phi</math> which means that <math>\phi</math> is satisfied in <math>W,I</math>. For basic assertions, the definition of the satisfaction relation is given in the next few subsections. For a conjunction of assertions <math>\phi_1,\ldots,\phi_n</math> we write <math>W,I \models \phi_1,\ldots,\phi_n</math> to indicate that <math>W,I \models \phi_1</math> and ... and <math>W,I \models \phi_n</math> hold.

Semantics of records

Entity Records

PROV-DM refers to entity assertions <math>entity(id,[attr_1=val_1,...])</math>.

Entity assertions can be interpreted as follows:

• <math>W,I \models entity(id,[attr_1=val_1,...])</math> if and only if:

1. <math>I(id) \in Entities</math>
2. for each attribute <math>attr_i</math>, we have <math>value(I(id),attr_i) = val_i</math>.

Activity Records

An activity record is of the form <math>activity(id,plan,st,et,attrs)</math> where <math>id</math> is a identifier referring to the activity, <math>st</math> is a start time and <math>et</math> is an end time. There is also a set of attribute-value pairs describing additional features of the activity. We don't do anything to interpret the plan here, it is purely an annotation (e.g. pointing to a web page describing the program or service that was executed, to source code, or to some other information that might be useful).

• We say that <math>W,I \models activity(id,plan,st,et,attrs)</math> if and only if:

1. The identifier <math>id</math> maps to an element of <math>Activities</math>, i.e. <math>I(id) \in Activities</math>
2. If <math>st</math> is specified then it is equal to the start time of the activity, that is: <math>lifetime(id) = [st,\_]</math>
3. If <math>et</math> is specified then it is equal to the end time of the activity, that is: <math>lifetime(id) = [\_,et]</math>
4. The values of attributes given in <math>attrs</math> satisfy <math>value(I(id),attr_i) = val_i</math>.

Agent Records

For the purpose of the semantics so far, an agent record holds at a time instant or interval if the corresponding entity record holds and the entity denoted by the record identifier is an agent. [TODO: Write this out more carefully.]

Note records

The note records represent ad hoc annotations to other parts of PROV-DM. As such, there is little we can say about their meaning, and so we won't discuss note records in the formal semantics. However, dialects of PROV-DM that use annotations in a systematic way could be justified by extending the semantics and interpreting note records.

Semantics of Relations

Generation

The generation assertion is of the form <math>wasGeneratedBy(id,e,a,attrs,t)</math> where <math>id</math> is an event (identifier), <math>e</math> is an object identifier, <math>a</math> is an activity identifier, <math>attrs</math> is a set of attribute-value pairs, and <math>t</math> is an optional time.

• <math>W,I \models wasGeneratedBy(id,e,a,attrs,t)</math> if and only if:

1. The identifier <math>id</math> denotes an event <math>evt = I(id) \in Events</math>
2. The identifier <math>e</math> denotes an object <math>obj = I(e) \in Objects</math>
3. The identifier <math>a</math> denotes an activity <math>act = I(a) \in Activities</math>.
4. The event <math>evt</math> is part of <math>act</math>, that is, such that <math>(act,evt) \in ActivityEvents</math>.
5. The type of <math>evt</math> is <math>generation</math>, i.e. <math>type(evt) = generation</math>
6. The event <math>evt</math> occurred at time <math>t</math>, i.e. <math>time(evt) = t</math>
7. The object <math>obj</math> came into existence at time <math>t</math>, that is, <math>lifetime(I(e)) = [t,\_]</math>
8. The event <math>evt</math> generated <math>obj</math>, i.e. <math>(evt,obj) \in Generated</math>
9. The attribute values are correct, i.e., for each attribute-value pair <math>attr_i,val_i</math> in <math>attrs</math> we have <math>value(evt,attr_i) = val_i</math>.

Question: How should we enforce the intuitive constraint that an object is created by exactly one event/PE?

Question: How to enforce the constraint that <math>e</math>'s attribute values are determined by the activity's "state" at time t?

Question: Should uses refer to an activity or to the specific event? A use event might be part of more than one activity?

Use

The use assertion is of the form <math>used(id,a,e,attrs,t)</math> where <math>id</math> denotes an event, <math>a</math> is an activity identifier, <math>e</math> is an object identifier, <math>attrs</math> is a set of attribute-value pairs, and <math>t</math> is an optional time.

• <math>W,I \models used(id,a,e,attrs,t)</math> if and only if:

1. The identifier <math>id</math> denotes an event <math>evt = I(id)

\in Events</math>.

1. The identifier <math>a</math> denotes an activity <math>act = I(id) \in Activities</math>
2. The identifier <math>e</math> denotes an object <math>obj = I(e) \in Objects</math>
3. The event <math>evt</math> is part of <math>act</math>, i.e. <math>(act,evt) \in ActivityEvents</math>.
4. The type of <math>evt</math> is <math>use</math>, i.e., <math>type(evt) = use</math>.
5. The event <math>evt</math> occurred at time <math>t</math>, i.e. <math>time(evt) = t</math>
6. The entity <math>obj</math> existed at time <math>t</math>, i.e., <math>t \in lifetime(obj)</math>.
7. The event <math>evt</math> used <math>obj</math>, i.e. <math>(evt,obj) \in Used</math>.
8. The attribute values are correct, i.e., for each attribute-value pair <math>attr_i,val_i</math> in <math>attrs</math> we have <math>value(evt,attr_i) = val_i</math>.

Association Records

We probably need a relation to connect agents to activities in order to interpret association. [TODO]

Start Records

A start record is interpreted as follows:

• <math>W,I \models wasStartedBy(id,a,ag,attrs)</math> holds if and only if:

1. <math>id</math> denotes an event <math>evt = I(id)</math>
2. <math>a</math> denotes an activity <math>act = I(a)</math>
3. <math>ag</math> denotes an agent <math>agent = I(ag)</math>
4. The event <math>evt</math> has type <math>start</math>, i.e. <math>type(evt) = start</math>.
5. [TODO] The agent was associated with the event.
6. The event was part of the activity, that is, <math>(act,evt) \in ActivitiesEvents</math>, and <math>lifetime(act) = [time(evt),\_]</math>.
7. The attribute values are correct, i.e., for each attribute-value pair <math>attr_i,val_i</math> in <math>attrs</math> we have <math>value(evt,attr_i) = val_i</math>.

End Records

An activity end record is interpreted as follows:

• <math>W,I \models wasEndedBy(id,a,ag,attrs)</math> holds if and only if:

1. <math>id</math> denotes an event <math>evt = I(id)</math>
2. <math>a</math> denotes an activity <math>act = I(a)</math>
3. <math>ag</math> denotes an agent <math>agent = I(ag)</math>
4. The event <math>evt</math> has type <math>end</math>, i.e. <math>type(evt) = start</math>.
5. [TODO] The agent was associated with the event.
6. The event was part of the activity, that is, <math>(act,evt) \in ActivitiesEvents</math>, and <math>lifetime(act) = [\_,time(evt)]</math>.
7. The attribute values are correct, i.e., for each attribute-value pair <math>attr_i,val_i</math> in <math>attrs</math> we have <math>value(evt,attr_i) = val_i</math>.

Responsibility

The <math>actedOnBehalfOf</math> relation is interpreted using the <math>ActsFor</math> relation. [TODO]

Derivation

The derivation relations are complicated and are not yet modeled. [TODO]

Specialization

This section is an attempt to formally describe the new <math>specializationOf</math> relation, which indicates when one entity record "provides a more concrete characterization of" another.

• <math>W,I \models specializationOf(a,b)</math> if and only if:

1. Both <math>a</math> and <math>b</math> are entity identifiers, denoting <math>obj_1 = I(a)</math> and <math>obj_2 = I(b)</math>.
2. The two Entities refer to the same Thing, that is, <math>thingOf(obj_1) = thingOf(obj_2)</math>.
3. The lifetime of <math>obj_1</math> is contained in that of <math>obj_2</math>
4. Every attribute <math>attr</math> of <math>obj_2</math> is also an attribute of <math>obj_1</math>, and for each such attribute we have <math>value(obj_1,attr) = value(obj_2,attr)</math>.

The second criterion says that the two Entities are descriptions of the same Things. Note that the third criterion allows <math>obj_1</math> and <math>obj_2</math> to have the same lifetime (or that of <math>obj_2</math> can be larger). The last criterion allows <math>obj_1</math> to define more attributes than <math>obj_2</math>, but they must agree on their common attributes.

Question: There has been controversy over whether <math>specializationOf</math> is transitive and/oranti-symmetric:

• Transitivity: If <math>specializationOf(a,b)</math> and <math>specializationOf(b,c)</math> hold then <math>specializationOf(a,c)</math> hold. This holds for the above definition.
• Antisymmetry: If <math>specializationOf(a,b)</math> and <math>specializationOf(b,a)</math> hold then <math>a=b</math>. This doesn't follow from the current definition (but it would if we stipulated that two entities that have the same interval, attribute and thing are equal).

Alternate

The <math>alternateOf</math> relation indicates when two entity records "provide different characterizations of the same thing".

• <math>W,I \models alternateOf(a,b)</math> if and only if:

1. Both <math>a</math> and <math>b</math> are entity identifiers, denoting <math>obj_1 = I(a)</math> and <math>obj_2 = I(b)</math>.
2. The lifetime of <math>obj_1</math> overlaps that of <math>obj_2</math>. That is, <math>lifetime(obj_1) \cap lifetime(obj_2) \neq \emptyset</math>.
3. The two objects refer to the same underlying Thing <math>thingOf(obj_1) \neq thingOf(obj_2)</math>
4. For every attribute <math>attr</math> common to both <math>obj_1</math> and <math>obj_2</math>, we have <math>value(obj_1,attr) = value(obj_2,attr)</math>.

Question: There has been controversy whether <math>alternateOf</math> is symmetric and transitive:

• Transitivity: If <math>alternateOf(a,b)</math> holds then <math>alternateOf(b,a)</math> holds.
• Symmetry: If <math>alternateOf(a,b)</math> and <math>alternateOf(b,c)</math> hold then <math>alternateOf(a,c)</math> hold. This does not hold of the above definition because we require the intervals to overlap (<math>a</math> and <math>c</math> do not necessarily have overlapping lifetimes.)

We also consider the following properties which have been suggested:

• <math>specializationOf(e_1,e_2)</math> implies <math>alternateOf(e_1,e_2)</math>? (This holds at the moment.)
• <math>alternateOf(a, b)</math> if and only if there exists c such that <math>specializationOf(a,c)</math> and <math>specializationOf(b,c)</math>? (This does not necessarily hold without further assumptions about the Entities).

Problem: The above definition is symmetric. However, it is not transitive. Suppose

• <math>lifetime(obj_1) = [1,2]</math>
• <math>lifetime(obj_2) = [2,3]</math>
• <math>lifetime(obj_3) = [3,4]</math>

and suppose <math>alternateOf(obj_1,obj_2)</math> and <math>alternateOf(obj_2,obj_3)</math> hold. Then <math>alternateOf(obj_1,obj_3)</math> cannot hold since the intervals of <math>obj_1,obj_3</math> do not overlap.

Annotation records

As with note assertions, annotation records are considered out of scope of the formal semantics.

Semantics of Accounts

[TODO]