From Provenance WG Wiki

(Difference between revisions)

Revision as of 12:50, 22 November 2012

Overview

Status

This is work in progress. The semantics is being updated to be consistent with the Candidate Recommendation of PROV. The plan is to release the semantics as a Note over the next few months. At that point, the wiki pages containing drafts of the semantics will be superseded.

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 $\forall x. x \geq 0$ is satisfied in a mathematical model where the individual elements denotable by $x$ are natural numbers, and the ordering relation symbol $\geq$ 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 model" to describe the mathematical structure that corresponds to actual state of affairs, and will try to avoid ambiguous, unqualified uses of the word "model".

Axiomatization and relationship to PROV-CONSTRAINTS

One goal of the semantics is to link the procedural specification of validity and equivalence with traditional notions of logical consistency and equivalence of theories, for example in first-order logic. A first-order axiomatization that corresponds to the formal constraints and is sound for reasoning about the models described below is in progress at the end of the document.

Basics

I will use syntax for PROV-DM records (which I will usually call formulas) as described in the third working draft of PROV-DM (PROV-DM 3PWD).

A PROV-DM instance consisting of assertions $φ 1$ ... $φ n$ 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 $x, y,...$ 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 $x$ and $y$ 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 $(T,\leq)$ 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 $I n t e r v a l s$ of sets of time instants closed under "convexity", that is, such that if $t_1 \leq t \leq t_2$ and $t_1,t_2 \in I$ then $t \in I$ . Sets of the form ${t \mid t_1 \leq t \leq t_2}$ are called basic intervals - there can also be other intervals.

The common case is that $T$ is a finite, linear order, for example, the set of time instants in a single place/time zone. In this case, we can represent all intervals as basic intervals, giving only the starting and ending time $[t 1, t 2]$ . (If the order is infinite or dense, like the reals or rational numbers, then we need open intervals and infinite intervals too.)

Example

First consider an ordinary linear order $M o n d a y < T u e s d a y < W e d n e s d a y < T h u r s d a y < F r i d a y$ . Then all of the intervals are of the form $[M o n d a y, W e d n e s d a y]$ or $[T u e s d a y, F r i d a y]$ .

Now consider the time point set ${M o n d a y, T u e s d a y, T u e s d a y, W e d n e s d a y N Y, W e d n e s d a y C A}$ , where $M o n d a y < T u e s d a y < W e d n e s d a y N Y$ and $M o n d a y < T u e s d a y < W e d n e s d a y C A$ are two basic intervals. The set of all time points in this example is also an interval, but it cannot be defined by taking just two time points.

Attributes and Values

We assume a set $A t t r i b u t e s$ of attribute labels and a set $V a l u e s$ of possible values of attributes.

Formulas

Summary of syntax of formulas from PROV-DM.

$\begin{array}{rcl} formula &::=& element\_formula\\ & | & relation\_formula\\ element\_formula &::= &entity(id,attrs) \\ & |& activity(id,st,et,attrs)\\ & |& agent(id,attrs)\\ relation\_formula &::=& wasGeneratedBy(id,e,a,t,attrs)\\ & |& used(id,e,a,t,attrs)\\ & |& wasAssociatedWith(id,ag,act,pl,attrs)\\ & |& wasStartedBy(id,a,ag,attrs)\\ & |& wasEndedBy(id,a,ag,attrs)\\ & |& actedOnBehalfOf(if,ag2,ag1,act,attrs)\\ & |& wasDerivedFrom(id,e2,e1,act,g,u,attrs)\\ & |& wasDerivedFrom(id,e2,e1,t,[prov:steps=single,attrs])\\ & |& wasDerivedFrom(id,e2,e1,t,[prov:steps=any,attrs])\\ & |& alternateOf(e1,e2)\\ & |& specializationOf(e1,e2) \end{array}$

Some additional features defined in PROV-DM 3PWD but not yet handled in the semantics are omitted. We exclude from attention derivation, annotations, accounts, and containers, since these features are in flux and non-obvious how to formalize. Also, we omit identifiers and attributes on alternateOf and specializationOf, anticipating that these features will be removed in future drafts.

World Models

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 model $W$ includes

a set $T h i n g s$ of things
a function $lifetime : Things \to Intervals$ from objects to time intervals
a function $value : Things \times Attributes \times Times \to Values$

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 $π$ . 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, interactions, and activities.

To model this, a world includes

a set $O b j e c t s$
a function $lifetime : Objects \to Intervals$ from objects to time intervals
a function $value : Objects \times Attributes \to Values$

Intuitively, $l i f e t i m e (e)$ is the time interval during which object $e$ exists; and for each $t \in lifetime(e)$ , the value $v a l u e (e, a)$ is the value of attribute $a$ 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 $Entities \subseteq Objects$ of entities, disjoint from $A c t i v i t i e s$ and $E v e n t s$ below.
a function $thingOf : Entities \to Things$ that associates each Entity with a Thing, such that for each $t \in lifetime(obj)$ , and each attribute defined by $o b j$ , we have $v a l u e (o b j, a) = v a l u e (t h i n g O f (o b j), a, t)$

Plans

We identify a specific subset of the entities called plans, $Plans \subseteq Entities$ .

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 $Agents \subseteq Entities$ of agents, which is disjoint from $P l a n s$ and also necessarily disjoint from $A c t i v i t i e s$ and $E v e n t s$

Interactions

We consider Interactions which are split into Events between entities and activities, Associations between agents and activities, and Derivations that describe chains of generation and usage steps. (The first two sets may overlap.)

$Interactions = (Events \cup Associations) \uplus Derivations$

Events

An Event is an interaction whose lifetime is a single time instant, and relates an activity to an entity (which could be an agent). Events have types including usage, generation, starting and ending (possibly more may be added such as destruction/invalidation of an entity). Events are instantaneous. We introduce:

A set $Events \subseteq Interactions$ of events.
A function $time : Events \to Times$ giving the time of each event; i.e. $l i f e t i m e (e v t) = t i m e (t)$ .
The derived ordering on events given by $evt_1 \leq evt_2 \iff t(evt_1) \leq t(evt_2)$
A function $type: Events \to \{start,end,use,generate\}$ such that Events have types in ${s t a r t, e n d, u s e, g e n e r a t e}$ .

Associations

An Association is an interaction relating an agent to an activity. Associations can overlap with events; for example, a start event is also an association. To model associations, we introduce:

A set $Associations \subseteq Interactions$ , such that every event $evt \in Events$ that is a start or end event is also an association. That is, $type(evt) \in \{start,end\}$ implies $evt \in Associations$

Associations are used below in the $A c t s F o r$ and $A s s o c i a t e d W i t h$ relations.

Derivations

A Derivation is an interaction chaining one or more generation and use steps. Derivations can also carry attributes, so we introduce an explicit kind of interaction for them that can carry attributes.

A set $Derivations \subseteq Interactions$ , disjoint from $Events \cup Associations$ .

See below for the associated derivation path and DerivedFrom relation.

Actvities

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

a set $Activities \subseteq Objects$ of activities, disjoint from $E n t i t i e s$ and $E v e n t s$

Relations

(ISSUE-214: Luc suggests replaces $G e n e r a t e d, E v e n t A c t i v i t i e s$ with $Generated : Events \times Entities \times Activities$ and similar for $U s e d$ ).

Simple relations

The entities, interactions, and activities in a world model are related in the following ways:

A relation $Used \subseteq Events \times Entities$ saying when an event used an entity. An event can use at most one entity, and if $(evt,e)\in Used$ then $time(evt) \in lifetime(e)$ must hold.
A relation $Generated \subseteq Events \times Entities$ 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 if $(evt,e)\in Generated$ then $m i n (l i f e t i m e (e)) = t i m e (e v t)$ must hold.
A relation $EventActivity \subseteq Events \times Activities$ associating activities with events, such that $(act,evt) \in EventActivity$ implies $time(evt) \in lifetime(act)$ .
A relation $AssociatedWith \subseteq Association \times Agents \times Activities \times Plans^?$ indicating when an agent is associated with an activity, and giving the identity of the association relationship, and an optional plan. This must satisfy the constraint that if $(assoc,ag,act,pl) \in AssociatedWith$ then $lifetime(assoc) \subseteq lifetime(ag) \cap lifetime(act)$ , i.e. the duration of the association must be within the lifetime of both the agent and the activity.
A relation $ActsFor \subseteq Agents \times Agents \times Activities$ indicating when one agent acts on behalf of another with respect to a given activity. This must satisfy the constraint that if $(ag_2,ag_1,act) \in ActsFor$ then there is an association such that $(assoc,ag_1,act),(assoc,ag_2,act) \in AssociatedWith$ , hence, both agents' lifetimes must overlap with some common time point in the lifetime of the activity.

Derivation paths and DerivedFrom

Recall that above we introduced a subset of interactions called Derivations. These identify paths of the form

$ent_n\cdot g_n\cdot act_n\cdot u_n\cdot ent_{n-1}\cdot ...\cdot ent_1\cdot g_1\cdot act_1\cdot u_1\cdot ent_0$ where the $e n t i$ are entities, $a c t i$ are activities, $g i$ are generations, and $u i$ are usages.

Formally, we consider the (regular) language:

$DerivationPaths = Entities \cdot (Events \cdot Activities \cdot Events \cdot Entities)^+$

and we use this language to give meaning to derivations:

A relation $derivedFrom : Derivations \to DerivationPaths$ with the constraints that for each derivation path:

for each substring $ent\cdot g \cdot act$ we have $(g,ent) \in Generated$ (hence, $t y p e (g) = g e n e r a t i o n$ ) and $(g,act) \in EventActivities$ , and
for each substring $act \cdot u \cdot ent$ we have $(u,ent) \in Used$ (hence, $t y p e (u) = u s e d$ ) and $(u,act) \in EventActivities$ .

Note: The reason why we need paths and not just individual derivation steps is that imprecise-n wasDerivedFrom edges can represent multiple derivation steps. Without this, we can simplify here.

Putting it all together

A world model W is a structure containing all of the above described data. If we need to talk about the objects or relations of more than one world model then we may write $W 1 . O b j e c t s$ ; otherwise, to decrease notational clutter, when we consider a fixed world model then the names of the sets, relations and functions above refer to the components of that model.

Semantics

In what follows, let $W$ be a fixed world model with the associated sets and relations discussed in the previous section, and let $I$ be an interpretation of identifiers as objects in $W$ .

The annotations [WF] refer to well-formedness constraints that could in principle be enforced by requiring a consistent typing of identifiers (i.e. by assuming that each identifier is associated with and can only denote an element of Entity, Agent, Note, Activity, Event, Association or Note). These could be factored out or eliminated for readability.

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.

The mapping from identifiers to objects may not change over time. Thus, we consider interpretations as follows:

An interpretation function $I : Identifiers \to Objects$ describing which object is the target of each identifier. This is time-independent.

Satisfaction

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

Attribute validity

Objects have attributes, and many

We say that an object $o b j$ has valid attributes $[a t t r 1 = v a l 1,...]$ in world $W$ provided:

for each attribute $a t t r i$ , we have $W . v a l u e (o b j, a t t r i) = v a l i$ .

This is sometimes abbreviated as: $v a l i d (W, o b j, a t t r s)$

Semantics of Element Records

Entity Records

PROV-DM refers to entity assertions $e n t i t y (i d, a t t r s)$ .

Entity assertions $e n t i t y (i d, a t t r s)$ can be interpreted as follows:

$W,I \models entity(id,attrs)$ if and only if:

[WF] $i d$ denotes an entity $ent = I(id) \in Entities$
the attributes are valid: $v a l i d (W, e n t, a t t r s)$ .

Activity Records

An activity record is of the form $a c t i v i t y (i d, p l a n, s t, e t, a t t r s)$ where $i d$ is a identifier referring to the activity, $s t$ is a start time and $e t$ 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 $W,I \models activity(id,st,et,attrs)$ if and only if:

[WF] The identifier $i d$ maps to an activity $act = I(id) \in Activities$
If $s t$ is specified then it is equal to the start time of the activity, that is: $m i n (l i f e t i m e (i d)) = s t$
If $e t$ is specified then it is equal to the end time of the activity, that is: $m a x (l i f e t i m e (i d)) = e t$
The attributes are valid: $v a l i d (W, a c t, a t t r s)$ .

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.

Agent assertions $a g e n t (i d, a t t r s)$ can be interpreted as follows:

$W,I \models agent(id,attrs)$ if and only if:

[WF] $i d$ denotes an agent $ag = I(id) \in Agents$
The attributes are valid: $v a l i d (W, a g, a t t r s)$ .

Note records

Out of scope of the formalization.

Semantics of Relations

Entity-Activity

Generation

The generation assertion is of the form $w a s G e n e r a t e d B y (i d, e, a, t, a t t r s)$ where $i d$ is an event (identifier), $e$ is an object identifier, $a$ is an activity identifier, $a t t r s$ is a set of attribute-value pairs, and $t$ is an optional time.

$W,I \models wasGeneratedBy(id,e,a,t,attrs)$ if and only if:

[WF] The identifier $i d$ denotes an event $evt = I(id) \in Events$
[WF] The identifier $e$ denotes an object $obj = I(e) \in Objects$
[WF] The identifier $a$ denotes an activity $act = I(a) \in Activities$ .
The event $e v t$ is involved in $a c t$ , that is, such that $(evt,act) \in EventActivities$ .
The type of $e v t$ is $g e n e r a t i o n$ , i.e. $t y p e (e v t) = g e n e r a t i o n$
The event $e v t$ occurred at time $t$ , i.e. $t i m e (e v t) = t$
[Redundant?] The object $o b j$ came into existence at time $t$ , that is, $m i n (l i f e t i m e (I (e))) = t$ .
The event $e v t$ generated $o b j$ , i.e. $(evt,obj) \in Generated$ .
The attribute values are valid: $v a l i d (W, e v t, a t t r s)$

Use

The use assertion is of the form $u s e d (i d, a, e, t, a t t r s)$ where $i d$ denotes an event, $a$ is an activity identifier, $e$ is an object identifier, $a t t r s$ is a set of attribute-value pairs, and $t$ is an optional time.

$W,I \models used(id,a,e,t,attrs)$ if and only if:

The identifier $i d$ denotes an event $evt = I(id) \in Events$ .
[WF] The identifier $i d$ denotes an event $evt = I(id) \in Events$
[WF] The identifier $a$ denotes an activity $act = I(id) \in Activities$
[WF] The identifier $e$ denotes an object $obj = I(e) \in Objects$
The event $e v t$ is part of $a c t$ , i.e. $(evt,act) \in EventActivities$ .
The type of $e v t$ is $u s e$ , i.e., $t y p e (e v t) = u s e$ .
The event $e v t$ occurred at time $t$ , i.e. $t i m e (e v t) = t$
[Redundant?] The entity $o b j$ existed at time $t$ , i.e., $t \in lifetime(obj)$ .
The event $e v t$ used $o b j$ , i.e. $(evt,obj) \in Used$ .
The attribute values are valid: $v a l i d (W, e v t, a t t r s)$

Agent-Activity

Association Records

An association record has the form $w a s A s s o c i a t e d W i t h (i d, a, a g, p l, a t t r s)$ .

$W,I \models wasAssociatedWith(id,a,ag,pl,attrs)$ holds if and only if:

[WF] $a s s o c$ denotes an association $assoc = I(id) \in Associations$ is an association interaction
[WF] $a$ denotes an activity $act = I(a) \in Activities$ is an activity.
[WF] $a g$ denotes an agent $agent = I(ag) \in Agents$ is an agent.
[WF] $p l$ denotes a plan $plan=I(pl) \in Plans$ is a plan.
The association associates the agent with the activity and plan, i.e. $(assoc,agent,act,plan) \in AssociatedWith$ .
The attributes are valid: $v a l i d (W, a s s o c, a t t r s)$ .

Start Records

A start record $w a s S t a r t e d B y (i d, a, a g, a t t r s)$ is interpreted as follows:

$W,I \models wasStartedBy(id,a,ag,attrs)$ holds if and only if:

[WF] $i d$ denotes an event $evt = I(id) \in Events$ that is also an association $evt \in Associations$
[WF] $a$ denotes an activity $a c t = I (a)$
[WF] $a g$ denotes an agent $a g e n t = I (a g)$
The event $e v t$ has type $s t a r t$ , i.e. $t y p e (e v t) = s t a r t$ .
The agent was associated with the activity, i.e. $(id,ag,act) \in AssociatedWith$
The event was part of the activity, that is, $(act,evt) \in ActivitiesEvents$ , and $m i n (l i f e t i m e (a c t)) = t i m e (e v t)$ .
The attributes are valid: $v a l i d (W, e v t, a t t r s)$ .

End Records

An activity end record $w a s E n d e d B y (i d, a, a g, a t t r s)$ is interpreted as follows:

$W,I \models wasEndedBy(id,a,ag,attrs)$ holds if and only if:

[WF] $i d$ denotes an event $e v t = I (i d)$ that is also an association $evt \in Associations$
[WF] $a$ denotes an activity $a c t = I (a)$
[WF] $a g$ denotes an agent $a g e n t = I (a g)$
The event $e v t$ has type $e n d$ , i.e. $t y p e (e v t) = e n d$ .
The agent was associated with the activity, i.e. $(id,ag,act) \in AssociatedWith$
The event was part of the activity, that is, $(act,evt) \in ActivitiesEvents$ , and $m a x (l i f e t i m e (a c t)) = t i m e (e v t)$ .
The attributes are valid: $v a l i d (W, e v t, a t t r s)$ .

Agent-Agent or Entity-Entity

Responsibility

The $a c t e d O n B e h a l f O f (i d, a g 2, a g 1, a c t, a t t r s)$ relation is interpreted using the $A c t s F o r$ relation as follows:

$W,I \models actedOnBehalfOf(id,ag2,ag1,act,attrs)$ holds if and only if:

[WF] $i d$ denotes an association $assoc=I(id) \in Associations$ that is an association interaction, and $t y p e (i d) = r e s p o n s i b i l i t y$ .
[WF] $a$ denotes an activity $act=I(a) \in Activities$ is an activity.
[WF] $a g 1, a g 2$ denote agents $agent1=I(ag1), agent2=I(ag2) \in Agents$ are agents.
The agent $a g e n t 2$ acts for the agent $a g e n t 1$ with respect to the activity $a c t$ , i.e. $(agent2,agent1,act) \in ActsFor$ .
[Redundant?] The association $i d$ associates both agents with the activity, i.e. $(assoc,agent1,act),(assoc,agent2,act) \in AssociatedWith$ .
The attributes are valid: $v a l i d (W, a s s o c, a t t r s)$ .

Derivation

Precise-1

A precise-1 derivation record has the form $w a s D e r i v e d F r o m (i d, e 2, e 1, a, g, u, a t t r s)$ .

$W,I \models wasDerivedFrom(id,e2,e1,act,g,u,attrs)$ if and only if:

[WF] $i d$ denotes a derivation $deriv = I(id) \in Derivations$
[WF] $e 1, e 2$ denote entities $ent1 = I(e1), ent2=I(e2) \in Entities$
[WF] $a$ denotes an activity $act = I(a) \in Activities$
[WF] $g$ denotes a generation event $gen = I(g) \in Events$ and $t y p e (I (g)) = g e n e r a t i o n$
[WF] $u$ denotes a use event $I(u) \in Events$ and $t y p e (I (u)) = u s e d$
The derivation denotes a valid one-step derivation $derivedFrom(deriv) = I(e2) \cdot I(g) \cdot I(act) \cdot I(u) \cdot I(e1))$
The attribute values are valid: $v a l i d (W, d e r i v, a t t r s)$ .

Imprecise-1

An imprecise-1 derivation record has the form $w a s D e r i v e d F r o m (i d, e 2, e 1, t,[p r o v : s t e p s = s i n g l e, a t t r s])$ .

$W,I \models wasDerivedFrom(id,e2,e1,t,[prov:steps=single,attrs])$ if and only if there exist $act \in Activities$ , $g \in Events$ , and $u \in Events$ such that:

[WF] $i d$ denotes a derivation $deriv = I(id) \in Derivations$
[WF] $e 1, e 2$ denote entities $ent1 = I(e1), ent2=I(e2) \in Entities$
$t y p e (u) = u s e d$ and $t y p e (g) = g e n e r a t i o n$ and $t i m e (g) = t$
$derivedFrom(deriv) = ent2 \cdot g \cdot act \cdot u \cdot ent1)$
The attribute values are valid: $v a l i d (W, d e r i v, a t t r s)$ .

Imprecise-n

An imprecise-n derivation record has the form $w a s D e r i v e d F r o m (i d, e 2, e 1, t,[p r o v : s t e p s = a n y, a t t r s])$ .

$W,I \models wasDerivedFrom(id,e2,e1,t,[prov:steps=any,attrs])$ if and only if there exists $path \in DerivationPaths$ such that:

[WF] $i d$ denotes a derivation $deriv = I(id) \in Derivations$
[WF] $e 1, e 2$ denote entities $ent1 = I(e1), ent2=I(e2) \in Entities$
$derivedFrom(deriv)= ent2 \cdot g \cdot w \cdot ent1$ and $t i m e (g) = t$
The attribute values are valid: $v a l i d (W, d e r i v, a t t r s)$ .

Specialization

The $s p e c i a l i z a t i o n O f (e 1, e 2)$ relation indicates when one entity record "provides a more concrete characterization of" another. This concept (like alternateOf) is in flux, but we attempt to provide a formalization to aid discussion.

$W,I \models specializationOf(a,b)$ if and only if:

[WF] Both $a$ and $b$ are entity identifiers, denoting $o b j 1 = I (a)$ and $o b j 2 = I (b)$ .
The two Entities refer to the same Thing, that is, $t h i n g O f (o b j 1) = t h i n g O f (o b j 2)$ .
The lifetime of $o b j 1$ is contained in that of $o b j 2$ ,i.e. $lifetime(obj_1) \subseteq lifetime(obj_2)$ .
Every attribute $a t t r$ of $o b j 2$ is also an attribute of $o b j 1$ , and for each such attribute we have $v a l u e (o b j 1, a t t r) = v a l u e (o b j 2, a t t r)$ .

The second criterion says that the two Entities are descriptions of the same Things. Note that the third criterion allows $o b j 1$ and $o b j 2$ to have the same lifetime (or that of $o b j 2$ can be larger). The last criterion allows $o b j 1$ to define more attributes than $o b j 2$ , but they must agree on their common attributes.

Question: There has been controversy over whether $s p e c i a l i z a t i o n O f$ is transitive and/oranti-symmetric:

Transitivity: If $s p e c i a l i z a t i o n O f (a, b)$ and $s p e c i a l i z a t i o n O f (b, c)$ hold then $s p e c i a l i z a t i o n O f (a, c)$ hold. This holds for the above definition.
Antisymmetry: If $s p e c i a l i z a t i o n O f (a, b)$ and $s p e c i a l i z a t i o n O f (b, a)$ hold then $a = b$ . 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 $a l t e r n a t e O f$ relation indicates when two entity records "provide different characterizations of the same thing".

$W,I \models alternateOf(a,b)$ if and only if:

[WF] Both $a$ and $b$ are entity identifiers, denoting $o b j 1 = I (a)$ and $o b j 2 = I (b)$ .
The lifetime of $o b j 1$ overlaps that of $o b j 2$ . That is, $lifetime(obj_1) \cap lifetime(obj_2) \neq \emptyset$ .
The two objects refer to the same underlying Thing: $t h i n g O f (o b j 1) = t h i n g O f (o b j 2)$
For every attribute $a t t r$ common to both $o b j 1$ and $o b j 2$ , we have $v a l u e (o b j 1, a t t r) = v a l u e (o b j 2, a t t r)$ .

Question: There has been controversy whether $a l t e r n a t e O f$ is symmetric and transitive:

Symmetry: If $a l t e r n a t e O f (a, b)$ holds then $a l t e r n a t e O f (b, a)$ holds.
Transitivity: If $a l t e r n a t e O f (a, b)$ and $a l t e r n a t e O f (b, c)$ hold then $a l t e r n a t e O f (a, c)$ hold. This does not hold of the above definition because we require the intervals to overlap ( $a$ and $c$ do not necessarily have overlapping lifetimes.)

We also consider the following properties which have been suggested:

$s p e c i a l i z a t i o n O f (e 1, e 2)$ implies $a l t e r n a t e O f (e 1, e 2)$ ? (This holds at the moment.)
$a l t e r n a t e O f (a, b)$ if and only if there exists c such that $s p e c i a l i z a t i o n O f (a, c)$ and $s p e c i a l i z a t i o n O f (b, c)$ ? (This does not necessarily hold without further assumptions about the Entities).

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

$l i f e t i m e (o b j 1) = [1,2]$
$l i f e t i m e (o b j 2) = [2,3]$
$l i f e t i m e (o b j 3) = [3,4]$

and suppose $a l t e r n a t e O f (o b j 1, o b j 2)$ and $a l t e r n a t e O f (o b j 2, o b j 3)$ hold. Then $a l t e r n a t e O f (o b j 1, o b j 3)$ cannot hold since the intervals of $o b j 1, o b j 3$ do not overlap.

Annotation records

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

Axiomatization

Definitions

The definitions are essentially used to map the compact notation and implicit placeholder notation used n PROV-N with the abstract syntax of PROV-DM used in the rest of this semantics. We can formalize the definitional expansion rules as follows:

Definition 1 (optional-identifiers)

For each $r \in \{ used, wasGeneratedBy, wasInvalidatedBy, wasInfluencedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasDerivedFrom, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf\}$ the following axioms hold:

$r(a_1,...,a_n) \iff \exists id.~ r(id; a_1,...,a_n)$
$r(-; a_1,...,a_n) \iff \exists id.~ r(id; a_1,...,a_n)$

Definition 2 (optional-attributes)

For each p in {entity, activity, agent}, if an is not an attribute list parameter then the following definitional rule holds:

p(a1,...,an) IF AND ONLY IF p(a1,...,an,[]).

For each r in { used, wasGeneratedBy, wasInvalidated, wasInfluencedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasDerivedFrom, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf}, if an is not an attribute list parameter then the following definition holds:

r(id; a1,...,an) IF AND ONLY IF r(id; a1,...,an,[]).

Definition 3 (definition-short-forms)

$\forall id,attrs. ~ activity(id,attrs) \iff activity(id,-,-,attrs)$
$\forall id, e, attrs. ~ wasGeneratedBy(id; e,attrs) \iff wasGeneratedBy(id; e,-,-,attrs)$
$\forall id,a,attrs. ~ used(id; a,attrs) \iff used(id; a,-,-,attrs)$
$\forall id,a,attrs. ~ wasStartedBy(id; a,attrs) \iff wasStartedBy(id; a,-,-,-,attrs)$
$\forall id,a,attrs. ~ wasEndedBy(id; a,attrs) \iff wasEndedBy(id; a,-,-,-,attrs)$
$\forall id,e,attrs. ~ wasInvalidatedBy(id; e,attrs) \iff wasInvalidatedBy(id; e,-,-,attrs)$
$\forall id,e1,e2,attrs. ~ wasDerivedFrom(id; e2,e1,attrs) \iff wasDerivedFrom(id; e2,e1,-,-,-,attrs)$
$\forall id,e,attrs. ~ wasAssociatedWith(id; e,attrs) \iff wasAssociatedWith(id; e,-,-,attrs)$
$\forall id,a1,a2,attrs. ~ actedOnBehalfOf(id; a2,a1,attrs) \iff actedOnBehalfOf(id; a2,a1,-,attrs)$

Definition 4 (optional-placeholders)

activity(id,-,t2,attrs) IF AND ONLY IF there exists t1 such that activity(id,t1,t2,attrs). Here, t2 may be a placeholder.
activity(id,t1,-,attrs) IF AND ONLY IF there exists t2 such that activity(id,t1,t2,attrs). Here, t1 must not be a placeholder.
For each r in { used, wasGeneratedBy, wasStartedBy, wasEndedBy, wasInvalidatedBy, wasAssociatedWith, actedOnBehalfOf }, if the ith parameter of r is an expandable parameter of r as specified in Table 3 then the following definition holds:

r(a0;...,ai-1, -, ai+1, ...,an) IF AND ONLY IF there exists a' such that r(a0;...,ai-1,a',ai+1,...,an).

If a is not the placeholder -, and u is any term, then the following definition holds:

wasDerivedFrom(id;e2,e1,a,-,u,attrs) IF AND ONLY IF there exists g such that wasDerivedFrom(id; e2,e1,a,g,u,attrs).

If a is not the placeholder -, and g is any term, then the following definition holds:

wasDerivedFrom(id;e2,e1,a,g,-,attrs) IF AND ONLY IF there exists u such that wasDerivedFrom(id; e2,e1,a,g,u,attrs).

Inferences

Inference 5 (communication-generation-use-inference)

$\forall id, a_2,a_1,attrs. wasInformedBy(id; a_2,a_1,attrs) \Longrightarrow \exists e, gen, t_1, use, t_2. wasGeneratedBy(gen; e,a_1,t_1,[]) \wedge used(use; a_2,e,t_2,[])$

Inference 6 (generation-use-communication-inference)

$\forall gen, a_1, t_1, attrs_1,id_2,a_2,t_2,attrs_2.~wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge used(id_2; a_2,e,t_2,attrs_2) \Longrightarrow \exists id.~wasInformedBy(id; a_2,a_1,[])$

Inference 7 (entity-generation-invalidation-inference)

$\forall gen, e, a_1, t_1, attrs_1, id_2, a_2, t_2, attrs_2. wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge used(id_2; a_2,e,t_2,attrs_2) \Longrightarrow \exists id.~ wasInformedBy(id; a_2,a_1,[])$

Inference 8 (activity-start-end-inference)

$\forall a, t_1, t_2, attrs.~ activity(a,t_1,t_2,attrs) \Longrightarrow \exists start, e_1, a_1, end, a_2, e_2.~ wasStartedBy(start; a,e_1,a_1,t_1,[]) \wedge wasEndedBy(end; a,e_2,a_2,t_2,[])$ </math>

Inference 9 (wasStartedBy-inference)

$\forall id, a, e_1, a_1, t, attrs.~ wasStartedBy(id; a,e_1,a_1,t,attrs), \Longrightarrow \exists gen, t_1.~ wasGeneratedBy(gen; e_1,a_1,t_1,[])$

Inference 10 (wasEndedBy-inference)

$\forall id, a, e_1, a_1, t, attrs.~ wasEndedBy(id; a,e_1,a_1,t,attrs), \Longrightarrow \exists gen, t_1 .~ wasGeneratedBy(gen; e_1,a_1,t_1,[])$

Inference 11 (derivation-generation-use-inference)

In this inference, none of a, gen2 or use1 can be placeholders -.

$\forall id, e_2, e_1, a, gen_2, use_1, attrs.~ wasDerivedFrom(id; e_2,e_1,a,gen_2,use_1,attrs), \Longrightarrow \exists s, t_1,t_2 .~ used(use_1; a,e_1,t_1,[]) \wedge wasGeneratedBy(gen_2; e_2,a,t_2,[])$

Inference 12 (revision-is-alternate-inference)

In this inference, any of a, g or u may be placeholders.

$\forall id, e_1, e_2, a, g,u.~ wasDerivedFrom(id; e_2,e_1,a,g,u,[prov:type='prov:Revision']), \Longrightarrow alternateOf(e_2,e_1)$

Inference 13 (attribution-inference)

$\forall att, e, ag, attrs.~ wasAttributedTo(att; e,ag,attrs) \Longrightarrow \exists a, t, gen, assoc, pl, .~ wasGeneratedBy(gen; e,a,t,[]) \wedge wasAssociatedWith(assoc; a,ag,pl,[])$

Inference 14 (delegation-inference)

$\forall id, ag_1, ag_2, a, attrs.~ actedOnBehalfOf(id; ag_1, ag_2, a, attrs) \Longrightarrow \exists id_1, pl_1, id_2, pl_2 .~ wasAssociatedWith(id_1; a, ag_1, pl_1, []) \wedge wasAssociatedWith(id_2; a, ag_2, pl_2, [])$

Inference 15 (influence-inference)

$\forall id, e, a, t, attrs.~ wasGeneratedBy(id; e,a,t,attrs) \Longrightarrow wasInfluencedBy(id; e, a, attrs)$
$\forall id, a, e, t, attrs.~ used(id; a,e,t,attrs) \Longrightarrow wasInfluencedBy(id; a, e, attrs)$
$\forall id, a_2, a_1, attrs.~ wasInformedBy(id; a_2,a_1,attrs) \Longrightarrow wasInfluencedBy(id; a_2, a_1, attrs)$
$\forall id, a_2, e, a_1, t, attrs.~ wasStartedBy(id; a_2,e,a_1,t,attrs) \Longrightarrow wasInfluencedBy(id; a_2, e, attrs)$
$\forall id, a_2, e, a_1, t, attrs.~ wasEndedBy(id; a_2,e,a_1,t,attrs) \Longrightarrow wasInfluencedBy(id; a_2, e, attrs)$
$\forall id, e, a, t, attrs.~ wasInvalidatedBy(id; e,a,t,attrs) \Longrightarrow wasInfluencedBy(id; e, a, attrs)$
$\forall id, e_2, e_1, a, g, u, attrs.~ wasDerivedFrom(id; e_2, e_1, a, g, u, attrs) \Longrightarrow wasInfluencedBy(id; e_2, e_1, attrs).$ Here, a, g, u may be placeholders -.
$\forall id, e, ag, attrs.~ wasAttributedTo(id; e,ag,attrs) \Longrightarrow wasInfluencedBy(id; e, ag, attrs)$
$\forall id, a, ag, pl, attrs.~ wasAssociatedWith(id; a,ag,pl,attrs) \Longrightarrow wasInfluencedBy(id; a, ag, attrs)$ Here, pl may be a placeholder -.
$\forall id, ag_2, ag_1, a, attrs.~ actedOnBehalfOf(id; ag_2,ag_1,a,attrs) \Longrightarrow wasInfluencedBy(id; ag_2, ag_1, attrs)$

Inference 16 (alternate-reflexive)

$\forall e.~ entity(e) \Longrightarrow alternateOf(e,e)$

Inference 17 (alternate-transitive)

$\forall e_1, e_2, e_3.~ alternateOf(e_1,e_2) \wedge alternateOf(e_2,e_3) \Longrightarrow alternateOf(e_1,e_3)$

Inference 18 (alternate-symmetric)

$\forall e_1, e_2.~ alternateOf(e_1,e_2) \Longrightarrow alternateOf(e_2,e_1)$

Inference 19 (specialization-transitive)

$\forall e_1, e_2, e_3 .~ specializationOf(e_1,e_2) \wedge specializationOf(e_2,e_3) \Longrightarrow specializationOf(e_1,e_3)$

Inference 20 (specialization-alternate-inference)

$\forall e_1, e_2.~ specializationOf(e_1,e_2) \Longrightarrow alternateOf(e_1,e_2)$

Inference 21 (specialization-attributes-inference)

$\forall e_1, attrs, e_2.~ entity(e_1, attrs) \wedge specializationOf(e_2,e_1), \Longrightarrow entity(e_2, attrs)$

Constraints

Constraint 22 (key-object)

The identifier field id is a KEY for the $e n t i t y (i d, a t t r s)$ statement.
The identifier field id is a KEY for the $a c t i v i t y (i d, t 1, t 2, a t t r s)$ statement.
The identifier field id is a KEY for the $a g e n t (i d, a t t r s)$ statement.

Constraint 23 (key-properties)

The identifier field id is a KEY for the $w a s G e n e r a t e d B y (i d; e, a, t, a t t r s)$ statement.
The identifier field id is a KEY for the $u s e d (i d; a, e, t, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s I n f o r m e d B y (i d; a 2, a 1, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s S t a r t e d B y (i d; a 2, e, a 1, t, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s E n d e d B y (i d; a 2, e, a 1, t, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s I n v a l i d a t e d B y (i d; e, a, t, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s D e r i v e d F r o m (i d; e 2, e 1, a, g 2, u 1, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s A t t r i b u t e d T o (i d; e, a g, a t t r)$ statement.
The identifier field id is a KEY for the $w a s A s s o c i a t e d W i t h (i d; a, a g, p l, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s A s s o c i a t e d W i t h (i d; a, a g, - , a t t r s)$ statement.
The identifier field id is a KEY for the $a c t e d O n B e h a l f O f (i d; a g 2, a g 1, a, a t t r s)$ statement.
The identifier field id is a KEY for the $w a s I n f l u e n c e d B y (i d; o 2, o 1, a t t r s)$ statement.

Constraint 24 (unique-generation)

$\forall gen_1,gen_2,e,a,t_1,t_2,attrs_1,attrs_2.~ wasGeneratedBy(gen_1; e,a,t_1,attrs_1) \wedge wasGeneratedBy(gen_2; e,a,t_2,attrs_2), \Longrightarrow gen_1 = gen_2.$

Constraint 25 (unique-invalidation)

$\forall inv_1,inv_2,e,a,t_1,t_2,attrs_1,attrs_2 .~ wasInvalidatedBy(inv_1; e,a,t_1,attrs_1) \wedge wasInvalidatedBy(inv_2; e,a,t_2,attrs_2), \Longrightarrow inv_1 = inv_2.$

Constraint 26 (unique-wasStartedBy)

$\forall start_1,start_2,a,e_1,e_2,a_0,t_1,t_2,attrs_1,attrs_2 .~ wasStartedBy(start_1; a,e_1,a_0,t_1,attrs_1) \wedge wasStartedBy(start_2; a,e_2,a_0,t_2,attrs_2), \Longrightarrow start_1 = start_2.$

Constraint 27 (unique-wasEndedBy)

$\forall end_1,end_2,a,e_1,e_2,a_0,t_1,t_2,attrs_1,attrs_2 .~ wasEndedBy(end_1; a,e_1,a0,t_1,attrs_1) \wedge wasEndedBy(end2; a,e_2,a0,t_2,attrs_2), \Longrightarrow end_1 = end2.$

Constraint 28 (unique-startTime)

$\forall a_1,a_2,t,t_1,t_2,e,attrs,attrs_1 .~ activity(a_2,t_1,t_2,attrs) \wedge wasStartedBy(start; a_2,e,a_1,t,attrs_1) \Longrightarrow t_1=t.$

Constraint 29 (unique-endTime)

$\forall a_1,a_2,t,t_1,t_2,e,attrs,attrs_1.~ activity(a_2,t_1,t_2,attrs) \wedge wasEndedBy(end; a_2,e,a_1,t,attrs_1) \Longrightarrow t_2 = t.$

Constraint 30 (start-precedes-end)

$\forall XYZ .~ wasStartedBy(start; a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end; a,e_2,a_2,t_2,attrs_2) \Longrightarrow start \preceq end.$

Constraint 31 (start-start-ordering)

$\forall XYZ .~ wasStartedBy(start_1; a,e_1,a_1,t_1,attrs_1) \wedge wasStartedBy(start_2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq start_2.$

Constraint 32 (end-end-ordering)

$\forall XYZ .~ wasEndedBy(end_1; a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow end_1 \preceq end2.$

Constraint 33 (usage-within-activity)

$\forall XYZ .~ wasStartedBy(start; a,e_1,a_1,t_1,attrs_1) \wedge used(use; a,e_2,t_2,attrs_2) \Longrightarrow start \preceq use.$
$\forall XYZ .~ used(use; a,e_1,t_1,attrs_1) \wedge wasEndedBy(end; a,e_2,a_2,t_2,attrs_2) \Longrightarrow use \preceq end.$

Constraint 34 (generation-within-activity)

$\forall XYZ .~ wasStartedBy(start; a,e_1,a_1,t_1,attrs_1) \wedge wasGeneratedBy(gen; e_2,a,t_2,attrs_2) \Longrightarrow start \preceq gen.$
$\forall XYZ .~ wasGeneratedBy(gen; e_,a,t_,attrs_) \wedge wasEndedBy(end; a,e_1,a_1,t_1,attrs_1) \Longrightarrow gen \preceq end.$

Constraint 35 (wasInformedBy-ordering)

$\forall XYZ .~ wasInformedBy(id; a_2,a_1,attrs_) \wedge wasStartedBy(start; a_1,e_1,a_1',t_1,attrs_1) \wedge wasEndedBy(end; a_2,e_2,a_2',t_2,attrs_2) \Longrightarrow start \preceq end.$

Constraint 36 (generation-precedes-invalidation)

$\forall XYZ .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq inv.$

Constraint 37 (generation-precedes-usage)

$\forall XYZ .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge used(use; a_2,e,t_2,attrs_2) \Longrightarrow gen \preceq use.$

Constraint 38 (usage-precedes-invalidation)

$\forall XYZ .~ used(use; a_1,e,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow use \preceq inv.$

Constraint 39 (generation-generation-ordering)

$\forall XYZ .~ wasGeneratedBy(gen_1; e,a_1,t_1,attrs_1) \wedge wasGeneratedBy(gen_2; e,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq gen_2.$

Constraint 40 (invalidation-invalidation-ordering)

$\forall XYZ .~ wasInvalidatedBy(inv_1; e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv_2; e,a_2,t_2,attrs_2) \Longrightarrow inv_1 \preceq inv_2.$

Constraint 41 (derivation-usage-generation-ordering)

In this constraint, a_, gen_2, use_1 must not be placeholders.

$\forall XYZ .~ wasDerivedFrom(d; e_2,e_1,a_,gen_2,use_1,attrs_) \Longrightarrow use_1 \preceq gen_2.$

Constraint 42 (derivation-generation-generation-ordering)

In this constraint, any of $a$ , $g$ , $u$ may be placeholders.

$\forall XYZ .~ wasDerivedFrom(d; e_2,e_1,a,g,u,attrs) \wedge wasGeneratedBy(gen_1; e_1,a_1,t_1,attrs_1) \wedge wasGeneratedBy(gen_2; e_2,a_2,t_2,attrs_2) \Longrightarrow gen_1 \prec gen_2.$

Constraint 43 (wasStartedBy-ordering)

$\forall XYZ .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge wasStartedBy(start; a_,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq start.$
$\forall XYZ .~ wasStartedBy(start; a_,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow start \preceq inv.$

Constraint 44 (wasEndedBy-ordering)

$\forall XYZ .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge wasEndedBy(end; a_,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq end.$
$\forall XYZ .~ wasEndedBy(end; a_,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow end \preceq inv.$

Constraint 45 (specialization-generation-ordering)

$\forall XYZ .~ specializationOf(e_2,e_1) \wedge wasGeneratedBy(gen_1; e_1,a_1,t_1,attrs_1) \wedge wasGeneratedBy(gen_2; e_2,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq gen_2.$

Constraint 46 (specialization-invalidation-ordering)

$\forall XYZ .~ specializationOf(e_1,e_2) \wedge wasInvalidatedBy(inv_1; e_1,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv_2; e_2,a_2,t_2,attrs_2) \Longrightarrow inv_1 \preceq inv_2.$

Constraint 47 (wasAssociatedWith-ordering)

In the following inferences, pl may be a placeholder -.

$\forall XYZ .~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasStartedBy(start_1; a,e_1,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv_2; ag,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq inv_2.$
$\forall XYZ .~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasGeneratedBy(gen_1; ag,a_1,t_1,attrs_1) \wedge wasEndedBy(end2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq end2.$
$\forall XYZ .~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasStartedBy(start_1; a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end2; ag,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end2.$
$\forall XYZ .~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasStartedBy(start_1; ag,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end2.$

Constraint 48 (wasAttributedTo-ordering)

$\forall XYZ .~ wasAttributedTo(a_t; e,ag,attrs) \wedge wasGeneratedBy(gen_1; ag,a_1,t_1,attrs_1) \wedge wasGeneratedBy(gen_2; e,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq gen_2.$
$\forall XYZ .~ wasAttributedTo(a_t; e,ag,attrs) \wedge wasStartedBy(start_1; ag,e_1,a_1,t_1,attrs_1) \wedge wasGeneratedBy(gen_2; e,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq gen_2.$

Constraint 49 (actedOnBehalfOf-ordering)

$\forall XYZ .~ actedOnBehalfOf(del; ag_2,ag_1,a_,attrs) \wedge wasGeneratedBy(gen_1; ag_1,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv_2; ag_2,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq inv_2.$
$\forall XYZ .~ actedOnBehalfOf(del; ag_2,ag_1,a_,attrs) \wedge wasStartedBy(start_1; ag_1,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end2; ag_2,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end2.$

Constraint 50 (typing)

$\forall XYZ .~ entity(e,attrs) \Longrightarrow entity \in typeOf(e).$
$\forall XYZ .~ agent(ag,attrs) \Longrightarrow agent \in typeOf(ag).$
$\forall XYZ .~ activity(a,attrs) \Longrightarrow activity \in typeOf(a).$
$\forall XYZ .~ used(u; a,e,t,attrs) \Longrightarrow activity \in typeOf(a) \wedge entity \in typeOf(e).$
$\forall XYZ .~ wasGeneratedBy(gen; e,a,t,attrs) \Longrightarrow entity \in typeOf(e) \wedge activity \in typeOf(a).$
$\forall XYZ .~ wasInformedBy(id; a_2,a_1,attrs) \Longrightarrow activity \in typeOf(a_2) \wedge activity \in typeOf(a_1).$
$\forall XYZ .~ wasStartedBy(id; a_2,e,a_1,t,attrs) \Longrightarrow activity \in typeOf(a_2) \wedge entity \in typeOf(e) \wedge activity \in typeOf(a_1).$
$\forall XYZ .~ wasEndedBy(id; a_2,e,a_1,t,attrs) \Longrightarrow activity \in typeOf(a_2) \wedge entity \in typeOf(e) \wedge activity \in typeOf(a_1).$
$\forall XYZ .~ wasInvalidatedBy(id; e,a,t,attrs) \Longrightarrow entity \in typeOf(e) \wedge activity \in typeOf(a).$
In this constraint, a, g2, and u1 must not be placeholders.

$\forall XYZ .~ wasDerivedFrom(id; e_2, e_1, a, g2, u1, attrs) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1) \wedge activity \in typeOf(a).$

$\forall XYZ .~ wasDerivedFrom(id; e_2, e_1, -, -, -, attrs) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1).$
$\forall XYZ .~ wasAttributedTo(id; e,ag,attr) \Longrightarrow entity \in typeOf(e) \wedge agent \in typeOf(ag).$
In this constraint, pl must not be a placeholder.

$\forall XYZ .~ wasAssociatedWith(id; a,ag,pl,attrs) \Longrightarrow activity \in typeOf(a) \wedge agent \in typeOf(ag) \wedge entity \in typeOf(pl).$

$\forall XYZ .~ wasAssociatedWith(id; a,ag,-,attrs) \Longrightarrow activity \in typeOf(a) \wedge agent \in typeOf(ag).$
$\forall XYZ .~ actedOnBehalfOf(id; ag_2,ag_1,a,attrs) \Longrightarrow agent \in typeOf(ag_2) \wedge agent \in typeOf(ag_1) \wedge activity \in typeOf(a).$
$\forall XYZ .~ alternateOf(e_2, e_1) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1).$
$\forall XYZ .~ specializationOf(e_2, e_1) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1).$
$\forall XYZ .~ mentionOf(e_2,e_1,b) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1) \wedge entity \in typeOf(b).$
$\forall XYZ .~ hadMember(c,e) \Longrightarrow prov:Collection \in typeOf(c) \wedge entity \in typeOf(c) \wedge entity \in typeOf(e).$
$\forall XYZ .~ entity(c,[prov:type=prov:EmptyCollection]) \Longrightarrow entity \in typeOf(c) \wedge prov:Collection \in typeOf(c) \wedge prov:EmptyCollection \in typeOf(c).$

Constraint 51 (impossible-unspecified-derivation-generation-use)

In the following rules, g \wedge u must not be -.

$\forall XYZ .~ wasDerivedFrom(id;e_2,e_1,-,g,-,attrs) \Longrightarrow False$
$\forall XYZ .~ wasDerivedFrom(id;e_2,e_1,-,-,u,attrs) \Longrightarrow False$
$\forall XYZ .~ wasDerivedFrom(id;e_2,e_1,-,g,u,attrs) \Longrightarrow False$

Constraint 52 (impossible-specialization-reflexive)

$\forall XYZ .~ specializationOf(e,e) \Longrightarrow False$

Constraint 53 (impossible-property-overlap)

For each r and s in { used, wasGeneratedBy, wasInvalidatedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf} such that r and s are different relation names, the following constraint holds:

$\forall id,a_1,\ldots,a_m,b_1,\ldots,b_n .~ r(id; a_1,...,am) \wedge s(id; b_1,...,b_n) \Longrightarrow False$

Constraint 54 (impossible-object-property-overlap)

For each $p \in \{entity, activity, agent\}$ and for each $r \in \{ used, wasGeneratedBy, wasInvalidatedBy, wasInfluencedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasDerivedFrom, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf\}$ , the following impossibility constraint holds:

$\forall id,a_1,\ldots,a_m,b_1,\ldots,b_n.~ p(id,a_1,\ldots,a_m) \wedge r(id; b_1,\ldots,b_n) \Longrightarrow False$

Constraint 55 (entity-activity-disjoint)

$\forall id .~ entity \in typeOf(id) \wedge activity \in typeOf(id) \Longrightarrow False$

Constraint 56 (membership-empty-collection)

$\forall c,e .~ hasMember(c,e) \wedge prov:EmptyCollection \in typeOf(c) \Longrightarrow False$

@@ Line 858: / Line 858: @@
 </math>
 ===Constraint 53 (impossible-property-overlap)===
-For each r  \wedge  s in { used, wasGeneratedBy, wasInvalidatedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf} such that r  \wedge  s are different relation names, the following constraint holds:
+For each r  and  s in { used, wasGeneratedBy, wasInvalidatedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf} such that r  and  s are different relation names, the following constraint holds:
 <math>
-\forall XYZ .~ r(id; a_1,...,am)  \wedge  s(id; b1,...,bn) \Longrightarrow False
+\forall id,a_1,\ldots,a_m,b_1,\ldots,b_n .~ r(id; a_1,...,am)  \wedge  s(id; b_1,...,b_n) \Longrightarrow False
 </math>
 ===Constraint 54 (impossible-object-property-overlap)===

FormalSemanticsCR