Provenance Challenge

Open Provenance Model Contents

1. Introduction
2. Basics
3. Overlapping and Hierarchichal Descriptions
4. Provenance Graph Definition
5. Timeless Formal Model
6. Inferences
7. Formal Model and Time Annotations
8. Time Constraints and Inferences
9. Support for Collections
10. Example of Representation
11. Conclusion
12. Best Practice on the Use of Agensts
13. References

8 Time Constraints and Inferences

The model of causality in OPM is essential timeless since time precedence does not imply causality: if a process P₁ occurs before a process P₂, in general, we cannot infer that P₁ caused P₂ to happen. However, the converse implication holds assuming time is measured according to a single clock.

We therefore expect time annotations to be consistent with causality. To this end, we extend the definition of legal account view, defined as: an acyclic account view, which contains at most one wasGeneratedBy edge per artifact, and in which causation is time-monotonic, as displayed in Figure 15, and discussed below.

Figure 14: Time Constraints in the Open Provenance Model

We remind the reader that all observed times are pairs of instanteous time values. For T1=(t1m, t1M), with t1m≤ t1M, and T2=(t2m,
t2M), with t2m≤ t2M inequality is
defined as follows:

T1 < T2
if
t1m ≤ t1M < t2m ≤ t2M

T1 ≤ T2
if
t1m ≤ t1M ≤ t2m ≤ t2M

According to Figure 14, an artifact must exist before it is being used (T₁ < T₃ and T₄ < T₆). If an artifact is used by a process, it will actually be used after the start of the process (T₂ < T₃). A process generates artifacts before its end (T₄ < T₅), and a process starts precedes its generation of artifacts (T₂ < T₄) and its end (T₂ < T₅).

Equipped with these definitions, Figure 15 formally states the time constraints illustrated by Figure 14.

Equation (13) states that generation of an artifact precedes its use. Equation (14) requires a process to start before it uses artifacts, but after the artifact that caused it was generated; the use of the artifact taking place before the end of the process.

Equation (15) states that generation of an artifact by a process is preceded by the start of the process and takes place before the end of the process.

Figure 15: Causation is Time-Monotonic

---

Comments

"The model of causality in OPM is essential [sic] timeless since time precedence does not imply causality" is too strong -- OPM is not timeless, since lack of time precedence does imply lack of causality.

-- PatrickPaulson - 18 Aug 2008

to top