-- PatrickPaulson - 18 Aug 2008

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

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

Comments

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_1 occurs before a process P_2, in general, we cannot infer that P_1 caused P_2 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 \retime:monotonicit, 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 T_1=(t_1^m, t_1^M), with t_1^m\leq t_1^M, and T_2=(t_2^m, t_2^M), with t_2^m\leq t_2^M inequality is defined as follows:

T_1 < T_2 &if& t_1^m \leq t_1^M < t_2^m \leq t_2^M

T_1 \leq T_2 &if& t_1^m \leq t_1^M \leq t_2^m \leq t_2^M %T_1 \leq T_2 &if& t_1^m \leq t_2^m \ and\ t_1^M \leq t_2^M\ \ \ (??????)

According to Figure~\retime:figur, an artifact must exist before it is being used (T_1<T_3 and T_4<T_6). If an artifact is used by a process, it will actually be used after the start of the process (T_2<T_3). A process generates artifacts before its end (T_4<T_5), and a process starts precedes its generation of artifacts (T_2<T_4) and its end (T_2<T_5).

Equipped with these definitions, Figure~\retime:monotonicit formally states the time constraints illustrated by Figure~\retime:figur.

Equation (\reused:generatedby:tim) states that generation of an artifact precedes its use. Equation (\reused:catalyzed:tim) 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 (\regeneratedby:catalyzed:tim) 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

-- PaulGroth - 31 Jul 2008