FormalSemanticsCR

From Provenance WG Wiki
(Redirected from FormalSemanticsED)
Jump to: navigation, search

Contents

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 valid from invalid provenance records.

The PROV-CONSTRAINTS document contains formal content specifying a notion of validity (approximately, logical consistency) for PROV documents. The formal semantics, PROV-SEM, is planned for release as a W3C Note that will complement the procedural specification in PROV-CONSTRAINTS with a declarative specification formulated in terms of first-order logic. The formal semantics is work in progress. The drafts below are intermediate stages and some of them are out of date.


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. The wiki version of the semantics is in the process of being converted to HTML. The current version can be found here: PROV-SEM.

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. P(x) \Rightarrow Q(x)</math> is satisfied in a mathematical model where the relation <math>P</math> denotes a set of elements that is contained in that denoted by <math>Q</math>. 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 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 Candidate Recommendation of PROV-DM (PROV-DM CR).

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

The rest of the document will discuss the structures and define 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. We write <math>Identifiers</math> for the set of identifiers of interest in a given situation (typically, the set of identifiers present in the PROV instance of interest).

Times and Intervals

We assume a linearly ordered set <math>(Times,\leq)</math> of time instants. For convenience we assume the order is total or linear order, corresponding to a linear timeline; however, PROV does not assume that time is linear and events could be partially ordered and not necessarily reconciled to a single global clock.

We also consider a set <math>Intervals</math> of closed intervals of the form <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

The following atomic formulas correspond to the statements of PROV-DM. We assume that definitions 1-4 of PROV-CONSTRAINTS have been applied in order to expand all optional parameters; thus, we use uniform notation <math>r(id,a_1,\ldots,a_n)</math> instead of the semicolon notation <math>r(id;a_1,\ldots,a_n)</math>.

Each parameter is either an identifier, a constant (e.g. a time or other literal value in an attribute list), or a null symbol "-". Null symbols can only appear in the specified arguments in <math>wasAssociatedWith</math> and <math>wasDerivedFrom</math>, as shown in the grammar below.

<math> \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)\\
         & |&  wasInvalidatedBy(id,e,a,t,attrs)\\
         & |&  wasAssociatedWith(id,ag,act,pl,attrs)\\
         & |&  wasAssociatedWith(id,ag,act,-,attrs)\\
         & |&  wasStartedBy(id,a_2,e,a_1,attrs)\\
         & |&  wasEndedBy(id,a_2,e,a_1,attrs)\\
         & |&  wasAttributedTo(id,e,ag,attrs)\\
         & |&  actedOnBehalfOf(if,ag_2,ag_1,act,attrs)\\
         & |&  wasDerivedFrom(id,e_2,e_1,act,g,u,attrs)\\
         & |&  wasDerivedFrom(id,e_2,e_1,-,-,-,attrs)\\
         & |&  alternateOf(e_1,e_2)\\
         & |&  specializationOf(e_1,e_2)

\end{array} </math>

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 <math>W</math> 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_\bot</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.

The range of the <math>value</math> function us <math>Values_\bot</math>, that is, <math>Values \uplus \{\bot\}</math>, the set of values with an additional element <math>\bot \notin Values</math>. When <math>value(x,a,t) = \bot</math>, we say that attribute <math>a</math> is undefined for <math>x</math> at time <math>t</math>.

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 <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_\bot</math>

Intuitively, <math>lifetime(e)</math> is the time interval during which object <math>e</math> exists. The value <math>value(e,a)</math> is the value of attribute <math>a</math> during the object's lifetime.

As with Things, the range of <math>value</math> includes the special undefined value <math>\bot</math>, making <math>value</math> effectively a partial function. It is also possible to have two different objects that are indistinguishable by their attributes and time intervals. Objects are not things, and the sets of <math>Objects</math> and <math>Things</math> are disjoint; however, certain objects, namely entities, are linked to things.

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 for each attribute <math>a</math> such that <math>value(obj,a) \neq \bot</math>, we have <math>value(obj,a) = value(thingOf(obj),a,t)</math>.
  • <math>lifetime(e) \subseteq lifetime(t)</math>.

Remark: Although both entities and things can have undefined attribute values, their meaning is slightly different: for a thing, <math>value(x,a,t) = \bot</math> means that the attribute <math>a</math> has no value at time <math>t</math>, whereas for an entity, <math>value(x,a) = \bot</math> only means that the entity does not record a fixed value for <math>a</math>. This does not imply that <math>value(thingOf(e),a,t) = \bot</math> when <math>t \in lifetime(e)</math>. In particular, if the <math>value(x,a,t)</math> has multiple values during the lifetime of <math>e</math>, then <math>value(e,a)</math> must be <math>\bot</math>, since assigning a value to <math>value(e,a)</math> would violate condition (3) above.

Plans

We identify a specific subset of the entities called plans, <math>Plans \subseteq Entities</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 Objects</math> of agents.

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>


Interactions

We consider a <math>Interactions \subseteq Objects</math> 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 are disjoint from entities, activities and agents.

  • <math>Interactions = (Events \cup Associations) \cup Derivations \subseteq Objects</math>
  • <math>(Events \cup Associations) \cap Derivations = \emptyset</math>
  • <math>Interactions \cap (Entities \cup Activities \cup Agents) = \emptyset</math>

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 <math>Events \subseteq Interactions</math> of events.
  • A function <math>time : Events \to Times</math> giving the time of each event; i.e. <math>lifetime(evt) = \{time(t)\}</math>.
  • The derived ordering on events given by <math>evt_1 \leq evt_2 \iff time(evt_1) \leq time(evt_2)</math>
  • A function <math>type: Events \to \{start,end,use,generate\}</math> such that Events have types in <math>\{start,end,use,generate\}</math>.

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 <math>Associations \subseteq Interactions</math>, such that every event <math>evt \in Events</math> that is a start or end event is also an association. That is, <math>type(evt) \in \{start,end\}</math> implies <math>evt \in Associations</math>

Associations are used below in the <math>ActsFor</math> and <math>AssociatedWith</math> relations. Add types for association or delegation?

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 <math>Derivations \subseteq Interactions</math>, disjoint from <math>Events \cup Associations</math>.

See below for the associated derivation path and DerivedFrom relation.

Relations

Simple relations

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

  • 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> and <math>type(g) = use</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 if <math>(evt,e)\in Generated</math> then <math>min(lifetime(e)) = time(evt)</math> and <math>type(g) = generation</math> must hold.
  • A relation <math>Invalidated \subseteq Events \times Entities</math> saying when an event invalidated an entity. An event can invalidate at most one entity, and if <math>(evt,e)\in Invalidated</math> then <math>min(lifetime(e)) = time(evt)</math> and <math>type(g) = invalidation</math> must hold.
  • A relation <math>EventActivity \subseteq Events \times Activities</math> associating activities with events, such that <math>(act,evt) \in EventActivity</math> implies <math>time(evt) \in lifetime(act)</math>.
  • A relation <math>AssociatedWith \subseteq Association \times Agents \times Activities \times Plans^?</math> indicating when an agent is associated with an activity, and giving the identity of the association relationship, and an optional plan.
  • A relation <math>ActsFor \subseteq Agents \times Agents \times Activities</math> indicating when one agent acts on behalf of another with respect to a given activity.

Derivation paths and DerivedFrom

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

<math>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</math> where the <math>ent_i</math> are entities, <math>act_i</math> are activities, <math>g_i</math> are generations, and <math>u_i</math> are usages.

Formally, we consider the (regular) language:

  • <math>DerivationPaths = Entities \cdot (Events \cdot Activities \cdot Events \cdot Entities)^+</math> with the constraints that for each derivation path:
  1. for each substring <math>ent\cdot g \cdot act</math> we have <math>(g,ent) \in Generated</math> and <math>(g,act) \in EventActivities</math>, and
  2. for each substring <math>act \cdot u \cdot ent</math> we have <math>(u,ent) \in Used</math> and <math>(u,act) \in EventActivities</math>.

and we use this language to give meaning to derivations:

  • A function <math>derivedFrom : Derivations \to DerivationPaths</math>

Note: The reason why we need paths and not just individual derivation steps is that imprecise wasDerivedFrom formulas can represent multiple derivation steps.

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 <math>W_1.Objects</math>; 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.

TODO: List the components.

Semantics

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

The annotations [WF] refer to well-formedness constraints that correspond to typing constraints.

Interpretations

We need 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 <math>I : Identifiers \to Objects</math> describing which object is the target of each identifier.

Satisfaction

Consider an atomic formula <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.

TODO: Satisfiability of additional formulas to explain constraints/inferences

Attribute matching

We say that an object <math>obj</math> matches attributes <math>[attr_1=val_1,...]</math> in world <math>W</math> provided:

  • for each attribute <math>attr_i</math>, we have <math>W.value(obj,attr_i) = val_i</math>.

This is sometimes abbreviated as: <math>match(W,obj,attrs)</math>

Semantics of Element Records

Entity Records

An entity formula is of the form <math>entity(id,attrs)</math> where <math>id</math> denotes an entity.

Entity assertions <math>entity(id,attrs)</math> can be interpreted as follows:

  • <math>W,I \models entity(id,attrs)</math> if and only if:
  1. [WF] <math>id</math> denotes an entity <math>ent = I(id) \in Entities</math>
  2. the attributes match: <math>match(W,ent, attrs)</math>.

For example, the following formulas both hold if <math>x</math> denotes an entity <math>e</math> such that <math>value(e,a) = 4, value(e,b) = 5, value(e,c) = 6</math> hold:

entity(x,[a=4,b=5])
entity(x,[a=4,b=5,c=6])

Activity Records

An activity record is of the form <math>activity(id,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.

  • We say that <math>W,I \models activity(id,st,et,attrs)</math> if and only if:
  1. [WF] The identifier <math>id</math> maps to an activity <math>act = 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>min(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>max(lifetime(id)) = et</math>
  4. The attributes match: <math>match(W,act,attrs)</math>.

Agent Records

An agent formula is of the form <math>agent(id,attrs)</math> where <math>id</math> denotes the agent and <math>attrs</math> describes additional attributes.

Agent assertions <math>agent(id,attrs)</math> can be interpreted as follows:

  • <math>W,I \models agent(id,attrs)</math> if and only if:
  1. [WF] <math>id</math> denotes an agent <math>ag = I(id) \in Agents</math>
  2. The attributes match: <math>match(W,ag,attrs)</math>.

Semantics of Relations

Entity-Activity

Generation

The generation assertion is of the form <math>wasGeneratedBy(id,e,a,t,attrs)</math> where <math>id</math> is an event identifier, <math>e</math> is an entity 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,t,attrs)</math> if and only if:
  1. [WF] The identifier <math>id</math> denotes an event <math>evt = I(id) \in Events</math>
  2. [WF] The identifier <math>e</math> denotes an entity <math>ent = I(e) \in Entities</math>
  3. [WF] The identifier <math>a</math> denotes an activity <math>act = I(a) \in Activities</math>.
  4. The event <math>evt</math> is involved in <math>act</math>, that is, such that <math>(evt,act) \in EventActivities</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 event <math>evt</math> generated <math>ent</math>, i.e. <math>(evt,ent) \in Generated</math>.
  8. The attribute values match: <math>match(W,evt,attrs)</math>

Use

The use assertion is of the form <math>used(id,a,e,t,attrs)</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,t,attrs)</math> if and only if:
  1. [WF] The identifier <math>id</math> denotes an event <math>evt = I(id) \in Events</math>
  2. [WF] The identifier <math>a</math> denotes an activity <math>act = I(id) \in Activities</math>
  3. [WF] The identifier <math>e</math> denotes an entity <math>ent = I(e) \in Entities</math>
  4. The event <math>evt</math> is part of <math>act</math>, i.e. <math>(evt,act) \in EventActivities</math>.
  5. The type of <math>evt</math> is <math>use</math>, i.e., <math>type(evt) = use</math>.
  6. The event <math>evt</math> occurred at time <math>t</math>, i.e. <math>time(evt) = t</math>
  7. The event <math>evt</math> used <math>obj</math>, i.e. <math>(evt,ent) \in Used</math>.
  8. The attribute values match: <math>match(W,evt,attrs)</math>

Invalidation

The invalidation assertion is of the form <math>wasInvalidatedBy(id,e,a,t,attrs)</math> where <math>id</math> is an event identifier, <math>e</math> is an entity 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 wasInvalidatedBy(id,e,a,t,attrs)</math> if and only if:
  1. [WF] The identifier <math>id</math> denotes an event <math>evt = I(id) \in Events</math>
  2. [WF] The identifier <math>e</math> denotes an entity <math>ent = I(e) \in Entities</math>
  3. [WF] The identifier <math>a</math> denotes an activity <math>act = I(a) \in Activities</math>.
  4. The event <math>evt</math> is involved in <math>act</math>, that is, such that <math>(evt,act) \in EventActivities</math>.
  5. The type of <math>evt</math> is <math>invalidation</math>, i.e. <math>type(evt) = invalidation</math>
  6. The event <math>evt</math> occurred at time <math>t</math>, i.e. <math>time(evt) = t</math>
  7. The event <math>evt</math> invalidated <math>ent</math>, i.e. <math>(evt,ent) \in Invalidated</math>.
  8. The attribute values match: <math>match(W,evt,attrs)</math>

Agent-Activity

Association Records

An association record has the form <math>wasAssociatedWith(id,a,ag,pl,attrs)</math>.

  • <math>W,I \models wasAssociatedWith(id,a,ag,pl,attrs)</math> holds if and only if:
  1. [WF] <math>assoc</math> denotes an association <math>assoc = I(id) \in Associations</math>.
  2. [WF] <math>a</math> denotes an activity <math>act = I(a) \in Activities</math>.
  3. [WF] <math>ag</math> denotes an agent <math>agent = I(ag) \in Agents</math>.
  4. [WF] <math>pl</math> is either the placeholder <math>-</math> or denotes a plan <math>plan=I(pl) \in Plans</math>.
  5. The association associates the agent with the activity and plan, i.e. <math>(assoc,agent,act,plan) \in AssociatedWith</math>.
  6. The attributes match: <math>match(W,assoc,attrs)</math>.

Start Records

A start record <math>wasStartedBy(id,a2,e,a1,attrs)</math> is interpreted as follows:

  • <math>W,I \models wasStartedBy(id,a2,e,a1,attrs)</math> holds if and only if:
  1. [WF] <math>id</math> denotes an event <math>evt = I(id) \in Events</math>
  2. [WF] <math>a2</math> denotes an activity <math>act2 = I(a2)</math>
  3. [WF] <math>e</math> denotes an entity <math>ent = I(e)</math>
  4. [WF] <math>a1</math> denotes an activity <math>act1 = I(a1)</math>
  5. The event <math>evt</math> has type <math>start</math>, i.e. <math>type(evt) = start</math>.
  6. The event happened at the start of <math>act2</math>, that is, <math>(act2,evt) \in ActivitiesEvents</math>, and <math>min(lifetime(act2)) = time(evt)</math>.
  7. The event happened during <math>act1</math>, that is, <math>(act1,evt) \in ActivitiesEvents</math>.
  8. The attributes match: <math>match(W,evt,attrs)</math>.

End Records

An activity end record <math>wasEndedBy(id,a2,e,a1,attrs)</math> is interpreted as follows:

  • <math>W,I \models wasEndedBy(id,a2,e,a1,attrs)</math> holds if and only if:
  1. [WF] <math>id</math> denotes an event <math>evt = I(id) \in Events</math>
  2. [WF] <math>a2</math> denotes an activity <math>act2 = I(a2)</math>
  3. [WF] <math>e</math> denotes an entity <math>ent = I(e)</math>
  4. [WF] <math>a1</math> denotes an activity <math>act1 = I(a1)</math>
  5. The event <math>evt</math> has type <math>end</math>, i.e. <math>type(evt) = end</math>.
  6. The event happened at the end of <math>act2</math>, that is, <math>(act2,evt) \in ActivitiesEvents</math>, and <math>max(lifetime(act2)) = time(evt)</math>.
  7. The event happened during <math>act1</math>, that is, <math>(act1,evt) \in ActivitiesEvents</math>.
  8. The attributes match: <math>match(W,evt,attrs)</math>.

Agent-Entity

Attribution Records

An attribution record <math>wasAttributedTo(id,e,ag,attrs)</math> is interpreted as follows:

  • <math>W,I \models wasAttributedTo(id,e,ag,attrs)</math> holds if and only if:
  1. [WF] <math>id</math> denotes an event <math>evt = I(id)</math> that is also an association <math>evt \in Associations</math>
  2. [WF] <math>e</math> denotes an entity <math>ent = I(e)</math>
  3. [WF] <math>ag</math> denotes an agent <math>agent = I(ag)</math>
  4. The event <math>evt</math> has type <math>attribution</math>, i.e. <math>type(evt) = attribution</math>.
  5. The entity was attributed to the agent, i.e. <math>(id,ent,ag) \in AttributedTo</math>
  6. The attributes match: <math>match(W,evt,attrs)</math>.

Agent-Agent

Responsibility

The <math>actedOnBehalfOf(id,ag2,ag1,act,attrs)</math> relation is interpreted using the <math>ActsFor</math> relation as follows:

  • <math>W,I \models actedOnBehalfOf(id,ag2,ag1,act,attrs)</math> holds if and only if:
  1. [WF] <math>id</math> denotes an association <math>assoc=I(id) \in Associations</math> that is an association interaction, and <math>type(id) = responsibility</math>.
  2. [WF] <math>a</math> denotes an activity <math>act=I(a) \in Activities</math> is an activity.
  3. [WF] <math>ag1,ag2</math> denote agents <math>agent1=I(ag1), agent2=I(ag2) \in Agents</math> are agents.
  4. The agent <math>agent2</math> acts for the agent <math>agent1</math> with respect to the activity <math>act</math>, i.e. <math>(agent2,agent1,act) \in ActsFor</math>.
  5. [Redundant?] The association <math>id</math> associates both agents with the activity, i.e. <math>(assoc,agent1,act),(assoc,agent2,act) \in AssociatedWith</math>.
  6. The attributes match: <math>match(W,assoc,attrs)</math>.

Entity-Entity

Derivation

Precise

A precise derivation record has the form <math>wasDerivedFrom(id,e2,e1,a,g,u,attrs)</math>.

  • <math>W,I \models wasDerivedFrom(id,e2,e1,act,g,u,attrs)</math> if and only if:
  1. [WF] <math>id</math> denotes a derivation <math>deriv = I(id) \in Derivations</math>
  2. [WF] <math>e1,e2</math> denote entities <math>ent1 = I(e1), ent2=I(e2) \in Entities</math>
  3. [WF] <math>a</math> denotes an activity <math>act = I(a) \in Activities</math>
  4. [WF] <math>g</math> denotes a generation event <math>gen = I(g) \in Events</math> and <math>type(I(g)) = generation</math>
  5. [WF] <math>u</math> denotes a use event <math>I(u) \in Events</math> and <math>type(I(u)) = use</math>
  6. The derivation denotes a valid one-step derivation <math>derivedFrom(deriv) = I(e2) \cdot I(g) \cdot I(act) \cdot I(u) \cdot I(e1)</math>
  7. The attribute values match: <math>match(W,deriv,attrs)</math>.


Imprecise

An imprecise derivation record has the form <math>wasDerivedFrom(id,e2,e1,-,-,-,attrs)</math>.

  • <math>W,I \models wasDerivedFrom(id,e2,e1,-,-,-,attrs)</math> if and only if there exists <math>path \in DerivationPaths</math> such that:
  1. [WF] <math>id</math> denotes a derivation <math>deriv = I(id) \in Derivations</math>
  2. [WF] <math>e1,e2</math> denote entities <math>ent1 = I(e1), ent2=I(e2) \in Entities</math>
  3. <math>derivedFrom(deriv)= ent2 \cdot w \cdot ent1</math> for some <math>w</math>
  4. The attribute values match: <math>match(W,deriv,attrs)</math>.


Specialization

The <math>specializationOf(e1,e2)</math> relation indicates when one entity record presents more specific aspects of another.

  • <math>W,I \models specializationOf(e1,e2)</math> if and only if:
  1. [WF] Both <math>e1</math> and <math>e2</math> are entity identifiers, denoting <math>ent_1 = I(e1) \in Entities</math> and <math>ent_2 = I(e2) \in Entities</math>.
  2. The two Entities refer to the same Thing, that is, <math>thingOf(ent_1) = thingOf(ent_2)</math>.
  3. The lifetime of <math>obj_1</math> is contained in that of <math>ent_2</math>,i.e. <math>lifetime(ent_1) \subseteq lifetime(ent_2)</math>.
  4. For each attribute such that <math>value(obj_2,a) \neq \bot</math> we have <math>value(obj_1,attr) = value(obj_2,attr)</math>.

The second criterion says that the two Entities present aspects of the same Thing. 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 have more defined attributes than <math>obj_2</math>, but they must agree on the attributes defined by <math>obj_2</math>.

Remark: There has been discussion 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 present (possibly different) aspects of the same thing. The two entities may or may not overlap in time.

  • <math>W,I \models alternateOf(e1,e2)</math> if and only if:
  1. [WF] Both <math>e1</math> and <math>e2</math> are entity identifiers, denoting <math>ent_1 = I(e1)</math> and <math>ent_2 = I(e2)</math>.
  2. The two objects refer to the same underlying Thing: <math>thingOf(ent_1) = thingOf(ent_2)</math>


Remark: There has been discussion whether <math>alternateOf</math> is symmetric and transitive:

  • Symmetry: If <math>alternateOf(a,b)</math> holds then <math>alternateOf(b,a)</math> holds.
  • Transitivity: If <math>alternateOf(a,b)</math> and <math>alternateOf(b,c)</math> hold then <math>alternateOf(a,c)</math> hold. This holds of the above definition.

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.

Axiomatization

Definitional Rules

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 <math> r \in \{ used, wasGeneratedBy, wasInvalidatedBy, wasInfluencedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasDerivedFrom, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf\}</math> the following axioms hold:

  1. <math>r(a_1,...,a_n) \iff \exists id.~ r(id; a_1,...,a_n)

</math>

  1. <math>r(-; a_1,...,a_n) \iff \exists id.~ r(id; a_1,...,a_n)

</math>

Definition 2 (optional-attributes)

  1. For each p in {entity, activity, agent}, if <math>a_n</math> is not an attribute list parameter then the following definitional rule holds: <math> p(a_1,...,a_n) \iff p(a_1,...,a_n,[])</math>
  2. For each <math> r \in \{ used, wasGeneratedBy, wasInvalidated, wasInfluencedBy, wasStartedBy, wasEndedBy, wasInformedBy, wasDerivedFrom, wasAttributedTo, wasAssociatedWith, actedOnBehalfOf\}</math>, if <math>a_n</math> is not an attribute list parameter then the following definition holds:

<math> r(id; a_1,...,a_n) \iff r(id; a_1,...,a_n,[])</math>

Definition 3 (definition-short-forms)

  1. <math>\forall id,attrs. ~

activity(id,attrs) \iff activity(id,-,-,attrs) </math>

  1. <math>\forall id, e, attrs. ~

wasGeneratedBy(id; e,attrs) \iff wasGeneratedBy(id; e,-,-,attrs) </math>

  1. <math>\forall id,a,attrs. ~

used(id; a,attrs) \iff used(id; a,-,-,attrs) </math>

  1. <math>\forall id,a,attrs. ~

wasStartedBy(id; a,attrs) \iff wasStartedBy(id; a,-,-,-,attrs) </math>

  1. <math>\forall id,a,attrs. ~

wasEndedBy(id; a,attrs) \iff wasEndedBy(id; a,-,-,-,attrs) </math>

  1. <math>\forall id,e,attrs. ~

wasInvalidatedBy(id; e,attrs) \iff wasInvalidatedBy(id; e,-,-,attrs) </math>

  1. <math>\forall id,e1,e2,attrs. ~

wasDerivedFrom(id; e2,e1,attrs) \iff wasDerivedFrom(id; e2,e1,-,-,-,attrs) </math>

  1. <math>\forall id,e,attrs. ~

wasAssociatedWith(id; e,attrs) \iff wasAssociatedWith(id; e,-,-,attrs) </math>

  1. <math>\forall id,a1,a2,attrs. ~

actedOnBehalfOf(id; a2,a1,attrs) \iff actedOnBehalfOf(id; a2,a1,-,attrs) </math>

Definition 4 (optional-placeholders)

  1. <math>activity(id,-,t2,attrs) \iff \exists t1.~ activity(id,t1,t2,attrs)</math>. Here, t2 may be a placeholder.
  2. <math>activity(id,t1,-,attrs) \iff \exists t2.~activity(id,t1,t2,attrs)</math>. Here, t1 must not be a placeholder.
  3. For each <math>r \in \{ used, wasGeneratedBy, wasStartedBy, wasEndedBy, wasInvalidatedBy, wasAssociatedWith, actedOnBehalfOf \}</math>, if the <math>i</math>th parameter of <math>r</math> is an expandable parameter of <math>r</math> as specified in Table 3 of PROV-CONSTRAINTS then the following definition holds:

<math>r(a_0;...,a_{i-1}, -, a_{i+1}, ...,a_n) \iff \exists a'.~ r(a_0;...,a_{i-1},a',a_{i+1},...,a_n)</math>.

  1. <math>a \neq - \Rightarrow (wasDerivedFrom(id;e2,e1,a,-,u,attrs) \iff \exists g.~ wasDerivedFrom(id; e2,e1,a,g,u,attrs))</math>
  2. <math> a \neq - \Rightarrow (wasDerivedFrom(id;e2,e1,a,g,-,attrs) \iff \exists u.~ wasDerivedFrom(id; e2,e1,a,g,u,attrs))</math>.

Inference Rules

Inference 5 (communication-generation-use-inference)

<math> \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,[])

</math>

Inference 6 (generation-use-communication-inference)

<math> \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,[]) </math>


Inference 7 (entity-generation-invalidation-inference)

<math> \forall e,attrs.~entity(e,attrs) \Longrightarrow \exists gen,a_1,t_1,inv,a_2,t_2.~wasGeneratedBy(gen,e,a_1,t_1,[]) \wedge wasInvalidatedBy(inv,e,a_2,t_2,[]) </math>

Inference 8 (activity-start-end-inference)

<math> \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)

<math> \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,[])</math>


Inference 10 (wasEndedBy-inference)

<math> \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,[])</math>

Inference 11 (derivation-generation-use-inference)

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

<math> \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 t_1,t_2 .~ used(use_1; a,e_1,t_1,[]) \wedge wasGeneratedBy(gen_2; e_2,a,t_2,[])</math>

Inference 12 (revision-is-alternate-inference)

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

<math> \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)</math>

Inference 13 (attribution-inference)

<math> \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,[])</math>

Inference 14 (delegation-inference)

<math> \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, [])</math>


Inference 15 (influence-inference)

  1. <math> \forall id, e, a, t, attrs.~ wasGeneratedBy(id; e,a,t,attrs) \Longrightarrow wasInfluencedBy(id; e, a, attrs)</math>
  2. <math> \forall id, a, e, t, attrs.~ used(id; a,e,t,attrs) \Longrightarrow wasInfluencedBy(id; a, e, attrs)</math>
  3. <math> \forall id, a_2, a_1, attrs.~ wasInformedBy(id; a_2,a_1,attrs) \Longrightarrow wasInfluencedBy(id; a_2, a_1, attrs)</math>
  4. <math> \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)</math>
  5. <math> \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)</math>
  6. <math> \forall id, e, a, t, attrs.~ wasInvalidatedBy(id; e,a,t,attrs) \Longrightarrow wasInfluencedBy(id; e, a, attrs)</math>
  7. <math> \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). </math> Here, a, g, u may be placeholders -.
  8. <math> \forall id, e, ag, attrs.~ wasAttributedTo(id; e,ag,attrs) \Longrightarrow wasInfluencedBy(id; e, ag, attrs)</math>
  9. <math> \forall id, a, ag, pl, attrs.~ wasAssociatedWith(id; a,ag,pl,attrs) \Longrightarrow wasInfluencedBy(id; a, ag, attrs)</math> Here, pl may be a placeholder -.
  10. <math> \forall id, ag_2, ag_1, a, attrs.~ actedOnBehalfOf(id; ag_2,ag_1,a,attrs) \Longrightarrow wasInfluencedBy(id; ag_2, ag_1, attrs)</math>

TODO: In 4 and 5, should e be a1? Otherwise these two rules are redundant since the influence of e on a2 can also be derived using other inferences.

Inference 16 (alternate-reflexive)

<math> \forall e.~ entity(e) \Longrightarrow alternateOf(e,e)</math>

Inference 17 (alternate-transitive)

<math> \forall e_1, e_2, e_3.~ alternateOf(e_1,e_2) \wedge alternateOf(e_2,e_3) \Longrightarrow alternateOf(e_1,e_3)</math>

Inference 18 (alternate-symmetric)

<math> \forall e_1, e_2.~ alternateOf(e_1,e_2) \Longrightarrow alternateOf(e_2,e_1)</math>

Inference 19 (specialization-transitive)

<math> \forall e_1, e_2, e_3 .~ specializationOf(e_1,e_2) \wedge specializationOf(e_2,e_3) \Longrightarrow specializationOf(e_1,e_3)</math>

Inference 20 (specialization-alternate-inference)

<math> \forall e_1, e_2.~ specializationOf(e_1,e_2) \Longrightarrow alternateOf(e_1,e_2)</math>

Inference 21 (specialization-attributes-inference)

<math> \forall e_1, attrs, e_2.~ entity(e_1, attrs) \wedge specializationOf(e_2,e_1), \Longrightarrow entity(e_2, attrs)</math>

Constraints

Constraint 22 (key-object)

  1. The identifier field id is a KEY for the <math>entity(id,attrs)</math> statement.
  2. The identifier field id is a KEY for the <math>activity(id,t_1,t_2,attrs) </math> statement.
  3. The identifier field id is a KEY for the <math>agent(id,attrs) </math> statement.

Constraint 23 (key-properties)

  1. The identifier field id is a KEY for the <math>wasGeneratedBy(id; e,a,t,attrs) </math> statement.
  2. The identifier field id is a KEY for the <math>used(id; a,e,t,attrs)</math> statement.
  3. The identifier field id is a KEY for the <math>wasInformedBy(id; a_2,a_1,attrs) </math> statement.
  4. The identifier field id is a KEY for the <math>wasStartedBy(id; a_2,e,a_1,t,attrs) </math> statement.
  5. The identifier field id is a KEY for the <math>wasEndedBy(id; a_2,e,a_1,t,attrs) </math> statement.
  6. The identifier field id is a KEY for the <math>wasInvalidatedBy(id; e,a,t,attrs) </math> statement.
  7. The identifier field id is a KEY for the <math>wasDerivedFrom(id; e_2, e_1, a, g2, u1, attrs) </math> statement.
  8. The identifier field id is a KEY for the <math>wasAttributedTo(id; e,ag,attr) </math> statement.
  9. The identifier field id is a KEY for the <math>wasAssociatedWith(id; a,ag,pl,attrs) </math> statement.
  1. The identifier field id is a KEY for the <math>actedOnBehalfOf(id; ag_2,ag_1,a,attrs) </math> statement.
  2. The identifier field id is a KEY for the <math>wasInfluencedBy(id; o2,o1,attrs) </math> statement.

Constraint 24 (unique-generation)

<math> \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 </math>

Constraint 25 (unique-invalidation)

<math> \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. </math>

Constraint 26 (unique-wasStartedBy)

<math> \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. </math>

Constraint 27 (unique-wasEndedBy)

<math> \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(end_2; a,e_2,a0,t_2,attrs_2), \Longrightarrow end_1 = end_2. </math>

Constraint 28 (unique-startTime)

<math> \forall start,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. </math>

Constraint 29 (unique-endTime)

<math> \forall end,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. </math>

Constraint 30 (start-precedes-end)

<math> \forall start,end,a,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

Constraint 31 (start-start-ordering)

<math> \forall start_1,start_2,a,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

Constraint 32 (end-end-ordering)

<math> \forall end_1,end_2,a,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasEndedBy(end_1; a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow end_1 \preceq end2. </math>

Constraint 33 (usage-within-activity)

  1. <math>

\forall start,use,a,e_1,e_2,a_1,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

  1. <math>

\forall use,end,a,e_1,e_2,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

Constraint 34 (generation-within-activity)

  1. <math>

\forall start,gen,e_1,e_2,a,a_1,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

  1. <math>

\forall gen,end,e,e_1,a,a_1,t,t_1,attrs,attrs_1 .~ wasGeneratedBy(gen; e,a,t,attrs) \wedge wasEndedBy(end; a,e_1,a_1,t_1,attrs_1) \Longrightarrow gen \preceq end. </math>

Constraint 35 (wasInformedBy-ordering)

<math> \forall id,start,end,a_1,a_1',a_2,a_2',e_1,e_2,t_1,t_2,attrs,attrs_1,attrs_2 .~ 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. </math>

Constraint 36 (generation-precedes-invalidation)

<math> \forall gen,inv,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq inv. </math>

Constraint 37 (generation-precedes-usage)

<math> \forall gen,use,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge used(use; a_2,e,t_2,attrs_2) \Longrightarrow gen \preceq use. </math>

Constraint 38 (usage-precedes-invalidation)

<math> \forall use,inv,a_1,a_2,e,t_1,t_2,attrs_1,attrs_2 .~ used(use; a_1,e,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow use \preceq inv. </math>

Constraint 39 (generation-generation-ordering)

<math> \forall gen_1,gen_2,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

Constraint 40 (invalidation-invalidation-ordering)

<math> \forall inv_1,inv_2,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

Constraint 41 (derivation-usage-generation-ordering)

In this constraint, <math>a</math>, <math>gen_2</math>, <math>use_1</math> must not be placeholders.

<math> \forall d,e_1,e_2,a,gen_2,use_1,attrs .~ notNull(a) \wedge notNull(gen_2) \wedge notNull(use_1) \wedge wasDerivedFrom(d; e_2,e_1,a,gen_2,use_1,attrs) \Longrightarrow use_1 \preceq gen_2. </math>

Constraint 42 (derivation-generation-generation-ordering)

In this constraint, any of <math>a</math>, <math>g</math>, <math>u</math> may be placeholders.

<math> \forall d,gen_1,gen_2,e_1,e_2,a,a_1,a_2,g,u,t_1,t_2,attrs,attrs_1,attrs_2 .~ 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. </math>

Constraint 43 (wasStartedBy-ordering)

  1. <math>

\forall gen,start,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge wasStartedBy(start; a,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq start. </math>

  1. <math>

\forall start,inv,e,a,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasStartedBy(start; a,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow start \preceq inv. </math>

Constraint 44 (wasEndedBy-ordering)

  1. <math>

\forall gen,end,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasGeneratedBy(gen; e,a_1,t_1,attrs_1) \wedge wasEndedBy(end; a,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq end. </math>

  1. <math>

\forall end,inv,e,a,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasEndedBy(end; a,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv; e,a_2,t_2,attrs_2) \Longrightarrow end \preceq inv. </math>

Constraint 45 (specialization-generation-ordering)

<math>

\forall gen_1,gen_2,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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.

</math>

Constraint 46 (specialization-invalidation-ordering)

<math> \forall inv_1,inv_2,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

Constraint 47 (wasAssociatedWith-ordering)

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

  1. <math>

\forall assoc,start_1,inv_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ 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. </math>

  1. <math>

\forall assoc,gen_1,end_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasGeneratedBy(gen_1; ag,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq end_2. </math>

  1. <math>

\forall assoc,start_1,end_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasStartedBy(start_1; a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2; ag,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end_2. </math>

  1. <math>

\forall assoc,start_1,end_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2 .~ wasAssociatedWith(assoc; a,ag,pl,attrs) \wedge wasStartedBy(start_1; ag,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2; a,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end_2. </math>

Constraint 48 (wasAttributedTo-ordering)

  1. <math>

\forall att,gen_1,gen_2,e,a_1,a_2,t_1,t_2,ag,attrs,attrs_1,attrs_2 .~ wasAttributedTo(att; 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. </math>

  1. <math>

\forall att,start_1,gen_2,e,e_1,a,a_2,ag,t_1,t_2,attrs,attrs_1,attrs_2 .~ wasAttributedTo(att; 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. </math>

Constraint 49 (actedOnBehalfOf-ordering)

  1. <math>

\forall del,gen_1,inv_2,ag_1,ag_2,a,a_1,a_2,t_1,t_2,attrs,attrs_1,attrs_2 .~ 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. </math>

  1. <math>

\forall del,start_1,end_2, ag_1,ag_2,a,a_1,a_2,e_1,e_2,t_1,t_2,attrs,attrs_1,attrs_2 .~ 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. </math>

Constraint 50 (typing)

  1. <math>

\forall e,attrs .~ entity(e,attrs) \Longrightarrow entity \in typeOf(e). </math>

  1. <math>

\forall ag,attrs .~ agent(ag,attrs) \Longrightarrow agent \in typeOf(ag). </math>

  1. <math>

\forall a,t_1,t_2,attrs .~ activity(a,t_1,t_2,attrs) \Longrightarrow activity \in typeOf(a). </math>

  1. <math>

\forall u,a,e,t,attrs .~ used(u; a,e,t,attrs) \Longrightarrow activity \in typeOf(a) \wedge entity \in typeOf(e). </math>

  1. <math>

\forall gen,e,a,t,attrs .~ wasGeneratedBy(gen; e,a,t,attrs) \Longrightarrow entity \in typeOf(e) \wedge activity \in typeOf(a). </math>

  1. <math>

\forall id,a_1,a_2,attrs .~ wasInformedBy(id; a_2,a_1,attrs) \Longrightarrow activity \in typeOf(a_2) \wedge activity \in typeOf(a_1). </math>

  1. <math>

\forall id,a_1,a_2,e,t,attrs .~ 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). </math>

  1. <math>

\forall id,a_1,a_2,e,t,attrs .~ 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). </math>

  1. <math>

\forall id, e,a,t,attrs .~ wasInvalidatedBy(id; e,a,t,attrs) \Longrightarrow entity \in typeOf(e) \wedge activity \in typeOf(a). </math>

  1. In this constraint, <math>a</math>, <math>g_2</math>, and <math>u_1</math> must not be placeholders.<math>

\forall id, e_2, e_1, a, g2, u1, attrs .~ notNull(a) \wedge notNull(g_2) \wedge notNull(u_1) \wedge 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). </math>

  1. <math>

\forall id,e_1,e_2,attrs .~ wasDerivedFrom(id; e_2, e_1, -, -, -, attrs) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1). </math>

  1. <math>

\forall id, e,ag,attr .~ wasAttributedTo(id; e,ag,attr) \Longrightarrow entity \in typeOf(e) \wedge agent \in typeOf(ag). </math>

  1. In this constraint, <math>pl</math> must not be a placeholder.<math>

\forall id, a,ag,pl,attrs .~ notNull(pl) \wedge wasAssociatedWith(id; a,ag,pl,attrs) \Longrightarrow activity \in typeOf(a) \wedge agent \in typeOf(ag) \wedge entity \in typeOf(pl). </math>

  1. <math>

\forall id, a,ag,attrs .~ wasAssociatedWith(id; a,ag,-,attrs) \Longrightarrow activity \in typeOf(a) \wedge agent \in typeOf(ag). </math>

  1. <math>

\forall id, ag_2,ag_1,a,attrs .~ 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). </math>

  1. <math>

\forall e_2, e_1 .~ alternateOf(e_2, e_1) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1). </math>

  1. <math>

\forall e_2, e_1 .~ specializationOf(e_2, e_1) \Longrightarrow entity \in typeOf(e_2) \wedge entity \in typeOf(e_1). </math>

  1. <math>

\forall c,e .~ hadMember(c,e) \Longrightarrow prov:Collection \in typeOf(c) \wedge entity \in typeOf(c) \wedge entity \in typeOf(e). </math>

  1. <math>

\forall c .~ entity(c,[prov:type=prov:EmptyCollection]) \Longrightarrow entity \in typeOf(c) \wedge prov:Collection \in typeOf(c) \wedge prov:EmptyCollection \in typeOf(c). </math>

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

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

  1. <math>

\forall id,e_1,e_2,g,attrs .~ notNull(g) \wedge wasDerivedFrom(id;e_2,e_1,-,g,-,attrs) \Longrightarrow False </math>

  1. <math>

\forall id,e_1,e_2,u,attrs .~ notNull(u) \wedge wasDerivedFrom(id;e_2,e_1,-,-,u,attrs) \Longrightarrow False </math>

  1. <math>

\forall id,e_1,e_2,g,u,attrs .~ notNull(g) \wedge notNull(u) \wedge wasDerivedFrom(id;e_2,e_1,-,g,u,attrs) \Longrightarrow False </math>

Constraint 52 (impossible-specialization-reflexive)

<math> \forall e .~ specializationOf(e,e) \Longrightarrow False </math>

Constraint 53 (impossible-property-overlap)

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

<math> \forall id,a_1,\ldots,a_m,b_1,\ldots,b_n .~ r(id; a_1,...,a_m) \wedge s(id; b_1,...,b_n) \Longrightarrow False </math>

Constraint 54 (impossible-object-property-overlap)

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

<math> \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 </math>

Constraint 55 (entity-activity-disjoint)

<math> \forall id .~ entity \in typeOf(id) \wedge activity \in typeOf(id) \Longrightarrow False </math>

Constraint 56 (membership-empty-collection)

<math> \forall c,e.~hasMember(c,e) \wedge prov:EmptyCollection \in typeOf(c) \Longrightarrow False </math>


Automatically generated inferences

Inference 5 (communication-generation-use-inference)

<math> \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,[]) </math>

Inference 6 (generation-use-communication-inference)

<math> \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,[]) </math>

Inference 7 (entity-generation-invalidation-inference)

<math> \forall e,attrs.~entity(e,attrs) \Longrightarrow \exists gen,a_1,t_1,inv,a_2,t_2.~wasGeneratedBy(gen,e,a_1,t_1,[]) \wedge wasInvalidatedBy(inv,e,a_2,t_2,[]) </math>

Inference 8 (activity-start-end-inference)

<math> \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)

<math> \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,[]) </math>

Inference 10 (wasEndedBy-inference)

<math> \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,[]) </math>

Inference 11 (derivation-generation-use-inference)

In this inference, none of a, gen2 or use_1 can be placeholders -.<math> \forall id,e_2,e_1,a,gen_2,use_1,attrs.~notNull(a) \wedge notNull(gen_2) \wedge notNull(use_1) \wedge wasDerivedFrom(id,e_2,e_1,a,gen_2,use_1,attrs) \Longrightarrow \exists t_1,t_2.~used(use_1,a,e_1,t_1,[]) \wedge wasGeneratedBy(gen_2,e_2,a,t_2,[]) </math>

Inference 12 (revision-is-alternate-inference)

In this inference, any of a, g or u may be placeholders.<math> \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) </math>

Inference 13 (attribution-inference)

<math> \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,[]) </math>

Inference 14 (delegation-inference)

<math> \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,[]) </math>

Inference 15 (influence-inference)

  1. <math>

\forall id,e,a,t,attrs.~wasGeneratedBy(id,e,a,t,attrs) \Longrightarrow wasInfluencedBy(id,e,a,attrs) </math>

  1. <math>

\forall id,a,e,t,attrs.~used(id,a,e,t,attrs) \Longrightarrow wasInfluencedBy(id,a,e,attrs) </math>

  1. <math>

\forall id,a_2,a_1,attrs.~wasInformedBy(id,a_2,a_1,attrs) \Longrightarrow wasInfluencedBy(id,a_2,a_1,attrs) </math>

  1. <math>

\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) </math>

  1. <math>

\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) </math>

  1. <math>

\forall id,e,a,t,attrs.~wasInvalidatedBy(id,e,a,t,attrs) \Longrightarrow wasInfluencedBy(id,e,a,attrs) </math>

  1. <math>

\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) </math>

  1. In this rule, a, g, u may be placeholders -.<math>

\forall id,e,ag,attrs.~wasAttributedTo(id,e,ag,attrs) \Longrightarrow wasInfluencedBy(id,e,ag,attrs) </math>

  1. In this rule, pl may be a placeholder -.<math>

\forall id,a,ag,pl,attrs.~wasAssociatedWith(id,a,ag,pl,attrs) \Longrightarrow wasInfluencedBy(id,a,ag,attrs) </math>

  1. <math>

\forall id,ag_2,ag_1,a,attrs.~actedOnBehalfOf(id,ag_2,ag_1,a,attrs) \Longrightarrow wasInfluencedBy(id,ag_2,ag_1,attrs) </math>

Inference 16 (alternate-reflexive)

<math> \forall e.~entity(e) \Longrightarrow alternateOf(e,e) </math>

Inference 17 (alternate-transitive)

<math> \forall e_1,e_2,e_3.~alternateOf(e_1,e_2) \wedge alternateOf(e_2,e_3) \Longrightarrow alternateOf(e_1,e_3) </math>

Inference 18 (alternate-symmetric)

<math> \forall e_1,e_2.~alternateOf(e_1,e_2) \Longrightarrow alternateOf(e_2,e_1) </math>

Inference 19 (specialization-transitive)

<math> \forall e_1,e_2,e_3.~specializationOf(e_1,e_2) \wedge specializationOf(e_2,e_3) \Longrightarrow specializationOf(e_1,e_3) </math>

Inference 20 (specialization-alternate-inference)

<math> \forall e_1,e_2.~specializationOf(e_1,e_2) \Longrightarrow alternateOf(e_1,e_2) </math>

Inference 21 (specialization-attributes-inference)

<math> \forall e_1,attrs,e_2.~entity(e_1,attrs) \wedge specializationOf(e_2,e_1) \Longrightarrow entity(e_2,attrs) </math>

Constraint 24 (unique-generation)

<math> \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 </math>

Constraint 25 (unique-invalidation)

<math> \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 </math>

Constraint 26 (unique-wasStartedBy)

<math> \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 </math>

Constraint 27 (unique-wasEndedBy)

<math> \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,a_0,t_1,attrs_1) \wedge wasEndedBy(end_2,a,e_2,a_0,t_2,attrs_2) \Longrightarrow end_1 = end_2 </math>

Constraint 28 (unique-startTime)

<math> \forall start,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 </math>

Constraint 29 (unique-endTime)

<math> \forall end,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 </math>

Constraint 30 (start-precedes-end)

<math> \forall start,end,a,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 31 (start-start-ordering)

<math> \forall start_1,start_2,a,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 32 (end-end-ordering)

<math> \forall end_1,end_2,a,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasEndedBy(end_1,a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2,a,e_2,a_2,t_2,attrs_2) \Longrightarrow end_1 \preceq end2 </math>

Constraint 33 (usage-within-activity)

  1. <math>

\forall start,use,a,e_1,e_2,a_1,t_1,t_2,attrs_1,attrs_2.~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 </math>

  1. <math>

\forall use,end,a,e_1,e_2,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 34 (generation-within-activity)

  1. <math>

\forall start,gen,e_1,e_2,a,a_1,t_1,t_2,attrs_1,attrs_2.~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 </math>

  1. <math>

\forall gen,end,e,e_1,a,a_1,t,t_1,attrs,attrs_1.~wasGeneratedBy(gen,e,a,t,attrs) \wedge wasEndedBy(end,a,e_1,a_1,t_1,attrs_1) \Longrightarrow gen \preceq end </math>

Constraint 35 (wasInformedBy-ordering)

<math> \forall id,start,end,a_1,a_1',a_2,a_2',e_1,e_2,t_1,t_2,attrs,attrs_1,attrs_2.~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 </math>

Constraint 36 (generation-precedes-invalidation)

<math> \forall gen,inv,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasGeneratedBy(gen,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq inv </math>

Constraint 37 (generation-precedes-usage)

<math> \forall gen,use,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasGeneratedBy(gen,e,a_1,t_1,attrs_1) \wedge used(use,a_2,e,t_2,attrs_2) \Longrightarrow gen \preceq use </math>

Constraint 38 (usage-precedes-invalidation)

<math> \forall use,inv,a_1,a_2,e,t_1,t_2,attrs_1,attrs_2.~used(use,a_1,e,t_1,attrs_1) \wedge wasInvalidatedBy(inv,e,a_2,t_2,attrs_2) \Longrightarrow use \preceq inv </math>

Constraint 39 (generation-generation-ordering)

<math> \forall gen_1,gen_2,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 40 (invalidation-invalidation-ordering)

<math> \forall inv_1,inv_2,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 41 (derivation-usage-generation-ordering)

In this constraint, <math>a</math>, <math>gen_2</math>, <math>use_1</math> must not be placeholders.<math> \forall d,e_1,e_2,a,gen_2,use_1,attrs.~notNull(a) \wedge notNull(gen_2) \wedge notNull(use_1) \wedge wasDerivedFrom(d,e_2,e_1,a,gen_2,use_1,attrs) \Longrightarrow use_1 \preceq gen_2 </math>

Constraint 42 (derivation-generation-generation-ordering)

In this constraint, any of <math>a</math>, <math>g</math>, <math>u</math> may be placeholders.<math> \forall d,gen_1,gen_2,e_1,e_2,a,a_1,a_2,g,u,t_1,t_2,attrs,attrs_1,attrs_2.~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 </math>

Constraint 43 (wasStartedBy-ordering)

  1. <math>

\forall gen,start,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasGeneratedBy(gen,e,a_1,t_1,attrs_1) \wedge wasStartedBy(start,a,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq start </math>

  1. <math>

\forall start,inv,e,a,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasStartedBy(start,a,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv,e,a_2,t_2,attrs_2) \Longrightarrow start \preceq inv </math>

Constraint 44 (wasEndedBy-ordering)

  1. <math>

\forall gen,end,e,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasGeneratedBy(gen,e,a_1,t_1,attrs_1) \wedge wasEndedBy(end,a,e,a_2,t_2,attrs_2) \Longrightarrow gen \preceq end </math>

  1. <math>

\forall end,inv,e,a,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasEndedBy(end,a,e,a_1,t_1,attrs_1) \wedge wasInvalidatedBy(inv,e,a_2,t_2,attrs_2) \Longrightarrow end \preceq inv </math>

Constraint 45 (specialization-generation-ordering)

<math> \forall gen_1,gen_2,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 46 (specialization-invalidation-ordering)

<math> \forall inv_1,inv_2,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

Constraint 47 (wasAssociatedWith-ordering)

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

  1. <math>

\forall assoc,start_1,inv_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~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 </math>

  1. <math>

\forall assoc,gen_1,end_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasAssociatedWith(assoc,a,ag,pl,attrs) \wedge wasGeneratedBy(gen_1,ag,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2,a,e_2,a_2,t_2,attrs_2) \Longrightarrow gen_1 \preceq end_2 </math>

  1. <math>

\forall assoc,start_1,end_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasAssociatedWith(assoc,a,ag,pl,attrs) \wedge wasStartedBy(start_1,a,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2,ag,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end_2 </math>

  1. <math>

\forall assoc,start_1,end_2,ag,e_1,e_2,a_1,a_2,t_1,t_2,attrs_1,attrs_2.~wasAssociatedWith(assoc,a,ag,pl,attrs) \wedge wasStartedBy(start_1,ag,e_1,a_1,t_1,attrs_1) \wedge wasEndedBy(end_2,a,e_2,a_2,t_2,attrs_2) \Longrightarrow start_1 \preceq end_2 </math>

Constraint 48 (wasAttributedTo-ordering)

  1. <math>

\forall att,gen_1,gen_2,e,a_1,a_2,t_1,t_2,ag,attrs,attrs_1,attrs_2.~wasAttributedTo(att,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 </math>

  1. <math>

\forall att,start_1,gen_2,e,e_1,a,a_2,ag,t_1,t_2,attrs,attrs_1,attrs_2.~wasAttributedTo(att,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 </math>

Constraint 49 (actedOnBehalfOf-ordering)

  1. <math>

\forall del,gen_1,inv_2,ag_1,ag_2,a,a_1,a_2,t_1,t_2,attrs,attrs_1,attrs_2.~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 </math>

  1. <math>

\forall del,start_1,end_2,ag_1,ag_2,a,a_1,a_2,e_1,e_2,t_1,t_2,attrs,attrs_1,attrs_2.~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 </math>

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

  1. <math>

\forall id,e_1,e_2,g,attrs.~notNull(g) \wedge wasDerivedFrom(id,e_2,e_1,-,g,-,attrs) \Longrightarrow False </math>

  1. <math>

\forall id,e_1,e_2,u,attrs.~notNull(u) \wedge wasDerivedFrom(id,e_2,e_1,-,-,u,attrs) \Longrightarrow False </math>

  1. <math>

\forall id,e_1,e_2,g,u,attrs.~notNull(g) \wedge notNull(u) \wedge wasDerivedFrom(id,e_2,e_1,-,g,u,attrs) \Longrightarrow False </math>

Constraint 52 (impossible-specialization-reflexive)

<math> \forall e.~specializationOf(e,e) \Longrightarrow False </math>

Constraint 55 (entity-activity-disjoint)

<math> \forall id.~entity \in typeOf(id) \wedge activity \in typeOf(id) \Longrightarrow False </math>

Constraint 56 (membership-empty-collection)

<math> \forall c,e.~hasMember(c,e) \wedge prov:EmptyCollection \in typeOf(c) \Longrightarrow False </math>