Skip to topic | Skip to bottom

Provenance Challenge

Challenge
Challenge.OPM1-01Review-TimeConstraints

Start of topic | Skip to actions
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 P1 occurs before a process P2, in general, we cannot infer that P1 caused P2 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.

Time Constraints in the Open Provenance Model
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 t1mt1M, and T2=(t2m,
t2M), with t2mt2M inequality is
defined as follows:

T1 < T2ift1m ≤ t1M < t2m ≤ t2M
T1 ≤ T2ift1m ≤ t1M ≤ t2m ≤ t2M

According to Figure 14, an artifact must exist before it is being used (T1 < T3 and T4 < T6). If an artifact is used by a process, it will actually be used after the start of the process (T2 < T3). A process generates artifacts before its end (T4 < T5), and a process starts precedes its generation of artifacts (T2 < T4) and its end (T2 < T5).

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.

Causation is Time-Monotonic
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

I Attachment sort Action Size Date Who Comment
time.jpg manage 196.9 K 31 Jul 2008 - 01:25 PaulGroth  
fig15.jpg manage 51.0 K 31 Jul 2008 - 03:11 PaulGroth  

You are here: Challenge > OPM > OPM1-01Review > OPM1-01Review-TimeConstraints

to top

Copyright © 1999-2012 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback