A common problem in process mining is the interpretation of the time stamp of events, e.g., whether it represents the moment of recording, or its occurrence. Often, this interpretation is left implicit. In this paper, we make this interpretation explicit using time intervals: an event occurs somewhere during a time window. The time window may be fine, e.g., a single point in time, or coarse, like a day. As each event is related to an activity within some process, we obtain for each activity a set of intervals in which the activity occurred. Based on these sets of intervals, we define ordering and simultaneousness relations. These relations form the basis of the discovery of a declarative process model describing the behavior in the event log.
Information systems of today collect large amounts of data. For example, banks are
saving information about the granting of mortgages and loans, insurance companies are
saving information concerning the handling of claims, and hospitals are saving the
actions taken to treat patients. Many of the recorded data concern events which have been
performed in the context of a certain business process. For each event, different aspects
are stored, for example, the activity and case for which the event is raised, its type, and
when it has been raised. Process mining [
The information about when the event occurred, for example using the order in which events are recorded, or its recorded timestamp is used to discover, monitor and check the control flow of processes. The implicit assumption many of the process mining algorithms make is that if two events are recorded consecutively, e.g. one is recorded before the other, or the timestamp of the first is before the latter, they occurred consecutively. However, in many cases, this assumption may not hold, as systems implement log recording differently. So, although time information is recorded, it can be interpreted in many different ways.
One interpretation of the timestamp is that it is the time on which the event actually occurred. More likely, many systems implement this as the time on which the event is recorded. Other systems implement logging using a queue system, i.e., the event is placed in the queue, and then written. Thus, if two events occur at the same time, their timestamp may differ as they are written consecutively.
A second problem of timestamps is their scale. On the one hand, a too fine time scale introduces causality that in reality does not exist. For example, consider an information system consisting of many different components each with their own logging mechanism. To construct the process of the information system, the recordings of each component need to be combined in a single event log. As a result, one needs to ensure that all components have the same time. On the other hand, a too coarse time scale may falsely introduce concurrency. For example, if the time scale is in days, the order of activities executed on the same day cannot be discovered.
A third problem lies in the reliability of the time information. For example, the order based on timestamps of events is more reliable if the same timestamp generator is used. Thus, timestamps of events in the same component are more reliable than when the events are recorded by different components. Another source of unreliability is whether time information depends on user input, such as calendars, or if it is generated by the system.
As a result, one should always first check the order in which events occur. One way to resemble this is to use intervals for event occurrences instead of single timestamps. This allows to change the time scale from a very fine scale, such as single points, to very coarse time scales, such as days. For example, an event that occurred on timestamp ‘2013/04/12 12:24:36.3’, can be seen as an interval of a single point, or, if the required time scale under consideration is in days, it can be seen as an event that occurred on April 12, 2013, i.e., in the interval ‘2013/04/12 0:00’ - ‘2013/04/12 23:59:59’.
Process mining focuses on the extraction of process knowledge. Whereas process
knowledge mainly focuses on the level of activities, systems recordings are on an event
level, which is not necessarily the same level, as several events may be raised for the
same activity, for example when the activity started or completed. Thus, to be able to
reason on the level of activities, events should be combined into activities. Aggregration
of events in activities can be done in many ways, such as the life-cycle of activities [
In this paper, we want to make the time intervals in which an activity occurs
explicit. Based on a set of intervals for each activity, we reason about which relations
can be inferred. For example, do two activities occur simultaneously or do they occur
sequentially. As we use intervals instead of single time points, many activities may
occur concurrently. Procedural languages, like Petri nets [
This paper is structured as follows. In Sec. 2 we introduce the basic notions used throughout the paper. Sec. 3 discusses the role of intervals within an event log. These events and their intervals can be mapped onto activities in many different ways, as shown in Sec. 4. Next, in Sec. 5, we define simultaneousness and causality relations on sets of intervals. Sec. 6 presents a method to build a declarative model based on these interval relations. Last, Sec. 7 concludes the paper. 2
Let S be a set. The powerset of S is denoted by P(S ) = {S 0 | S 0 ⊆ S }. We use |S | for the number of elements in S . Two sets U and V are disjoint if U ∩ V = ∅. We denote the cartesian product of two sets S and T by S × T . On a cartesian product we define two projection functions π1 : S × T → S and π2 : S × T → T such that π1((s, t)) = s and π2((s, t)) = t for all (s, t) ∈ S × T . We lift the projection function to sets in the standard way.
A binary relation R from S to T is defined by R ⊆ (S × T ). For (x, y) ∈ R, we also write x R y. For a relation R ⊆ (S × T ), the inverse relation R−1 is defined as R−1 = {(y, x) ∈ (T × S ) | x R y}. A relation R is called a function if x R y and x R z implies y = z for all x ∈ S and y, z ∈ T . It is called a binary relation over S if R ⊆ (S × S ). A binary relation R is reflexive if x R x for all x ∈ S . It is transitive if x R y and y R z implies x R z for all x, y, z ∈ S . It is reflexive if (x, x) ∈ R for all x ∈ S , and irreflexive if (x, x) < R for all x ∈ S . Relation R is symmetric if x R y implies y R x for all x, y ∈ S and asymmetric if x R y implies ¬y R x for all x, y ∈ S . The relation is antisymmetric if x R y and y R x imply x = y for all x, y ∈ S . The transitive closure of a binary relation R is defined as the smallest relationR+ such that x R+ y if either x = y, or x R+ z and z R y for some z ∈ S .
A binary relation R over some set S is an equivalence relation if it is reflexive, symmetric and transitive. A transitive, irreflexive binary relation is called a strict order. It is a preorder, denoted by (S , R), if R is reflexive and transitive. A preorder is a partial order if (S , R) is also antisymmetric. A partial order is called a total order, if in addition also x R y or y R x for all x, y ∈ S .
A sequence over S of length n ∈ N is a function σ : {1, . . . , n} → S . If n > 0 and σ(i) = ai for i ∈ {1, . . . , n}, we write σ = ha1, . . . , ani. The length of a sequence is denoted by |σ|. The sequence of length 0 is called the empty sequence, and is denoted by . The set of all finite sequences over S is denoted by S ∗. Let ν, γ ∈ S ∗ be two sequences. Concatenation, denoted by σ = ν; γ is defined asσ : {1, . . . , |ν| + |γ|} → S , such that for 1 ≤ i ≤ |ν|: σ(i) = ν(i), and for |ν| + 1 ≤ i ≤ |ν| + |γ|: σ(i) = γ(i − |ν|).
Given a set S and a, possibly infinite setT ⊆ R, a function f : S → T × T is called an interval function if π1( f (a)) ≤ π2( f (a)) for all a ∈ S . 2.1
For each user action on the system, an event is raised. An event records its type, for
which activity it has been raised, for which case or business process instance, when
it was raised, by whom, and the data inserted by the user. Such a recording is called
an event log [
Definition 1 (Event log). An event log is a 3-tuple L = (C, E, #) where – C ⊆ C is a set of case identifiersin the event log; – E ⊆ E is a set of event identifiersin the log; – # : A × (C ∪ E) → P(V) is an attribute mapping.
For an attribute n ∈ A we write #n(·) as a shorthand for #(n, ·). The following attributes are always defined: – Each event belongs to exactly one case and each case has at least one event, denoted by the mandatory attribute case ∈ A, i.e., for all events e ∈ E, a case c ∈ C exists with #case(e) = {c}, and for all c ∈ C an event e ∈ E exists with #case(e) = {c}; – Each event belongs to some activity, denoted by the mandatory attribute act ∈ A, i.e., for all events e ∈ E an activity a ∈ A exists such that #act(e) = {a}; – An event may record the time it was recorded using the timestamp attribute time ∈ A, i.e., for all events e ∈ E we have #time(e) = {t} for some timestamp t ∈ T , where T resembles the set of timestamps.
There are many techniques for discovering a process model out of an event log. An
extensive overview of available process discovery techniques can be found in [
The more coarse the chosen time scale (e.g., days, weeks or months), the more
events will occur concurrently. Another consequence of a more coarse time scale is that
events occur in some time window, rather than occurring at a single moment in time.
It is important to note that there are some techniques which do not consider events to
be instantaneous. That is, the authors of [
Consider the events presented in Tbl. 1 showing for each day the events that occurred. For each event, its case and activity are recorded. The time stamps of these events are in days, e.g., event (1, B) occurred on January 1, 2013, as well as event (1, E). Based on this information, we cannot infer any order between B and E, the only fact that can be inferred is that these events occurred simultaneously.
As the time scale is relatively coarse, a first analysis of this event log would be the degree of concurrency. We can build a graph that depicts the intervals on a time scale, as shown in Fig. 1(a). Based on this graph, we derive a concurrency relation I ⊆ E × E, such that a I b if and only if a and b occur within the same time interval. This results in a graph as depicted in Fig. 1(b), where the dashed and solid edges together represent the relation I. For readability, the self loops have been omitted. Note that (A, G) is an edge in the graph, while no case exists in which activities A and G occur simultaneously. Therefore, we can partition the relation I into two relations IS and IG such that a IS b if and only if #case(a) = #case(b), and IG analogously. In Fig. 1(b), the edges of relation IS are solid, the edges of relation IG are dashed. Similarly, the concurrency relation is not transitive with respect to the event log: even though (B, E) and (E, C) are edges in the graph, B, C and E never occur simultaneously in any case.
Whereas in Fig. 1(b) an absolute time window is taken, one could also choose to map each event to a relative interval, e.g. the respective day from the start of the day, as shown in Fig. 1(c). To allow such abstractions, we introduce the notion of an event interval mapping function that maps each event onto a time interval.
Definition 2 (Event interval mapping function). Let L = (C, E, #) be an event log. A function mL : E → T × T is an event interval mapping function for L if it is an interval function. The default interval mapping function DL : E → T × T of L is defined by DL(e) = (#time(e), #time(e)) for all e ∈ E.
Based on the event interval mapping function, two notions of concurrency can be observed: one based on the whole event log, called the concurrency relation, and one based on the individual executions: the simultaneousness relation. Thus, the simultaneousness relation I for an event log L can be defined as the events that occur in the same interval defined by some interval mapping function.
(6,A) (3,G) (4,F) (5,D) (6,F) (4,A) (5,A) (4,G) (5,G) (6,G)
F
A G
C E B D (a) intervals
(b) concurrency graph (5,D) (6,A) (4,F)
(6,F) (5,A) (3,D) (5,G) (4,A) (2,C) (4,G) (3,A) (2,E) (2,A) (1,B) (2,G) (1,A) (1,E) (1,G) (6,G) (c) Relative time, intervals
a corresponding event interval mapping function. Its concurrency relation I¯m ⊆ E × E is defined by a I¯m b iff π1(m(a)) ≤ π2(m(b)) and π1(m(b)) ≤ π2(m(a)) for a, b ∈ E. Its simultaneousness relation Im ⊆ E × E is defined by a I m b iff both a I¯m b and #case(a) = #case(b) for a, b ∈ E.
In the literature, the graph imposed by the concurrency relation is called the interval
graph [
Definition 4 (Interval order). A binary relation R over some set S is an interval order if a R b and c R d imply a R d or c R b for all a, b, c, d ∈ S .
Using intervals in concurrency is not new. For example, Janicki and Koutny [
In [
The interval mapping function on event logs introduced in the previous section induces
an interval order on the events in the event log. In this way, approaches like in [
Different events for the same activity may indicate that the activity has been
executed several times. Or, if an event represents the different stadia of some life cycle of
activities, like a start and complete type, multiple events occur for the same activity.
In [
One way to lift the interval functions from events to activities is by defining a
relation based on the interval order. Similar to the concurrency and simultaneousness
relation, one would obtain two relations R¯and R such that
a R¯b ⇔ ∃e1, e2 ∈ E : #act(e1) = a ∧ #act(e2) = b ∧ e1
e2
a R b ⇔ ∃e1, e2 ∈ E : #case(e1) = #case(e2) ∧ #act(e1) = a ∧ #act(e2) = b ∧ e1
e2
In fact, using the default event interval mapping of an event log, relation R coincides
with the weak order relation of [
Although the above relation R¯is transitive, it abstracts away from the observed sequences in the event log. As activities may have multiple occurrence intervals, it is not an interval function. Therefore, we need to generalize the interval function to sets of intervals.
set T ⊆ R, a function f : S → P(T × T ) is called a generalized interval function if x ≤ y for all (x, y) ∈ f (a) and a ∈ S .
A generalized interval function can define a large set of small intervals, or a small set of large intervals. We call this the granularity of the interval function. Given any generalized interval function, we can define its most fine granular interval function, i.e., each point is its own interval, and the most coarse granular interval function, i.e., the conjunction of all intervals.
generalized interval function. Its finest interval function, denoted by f ↓: S → P(T ×T ), is defined by
f ↓ (s) = {(t, t) | ∃(x, y) ∈ f (s) : x ≤ t ≤ y} The coarsest interval function of f , denoted by f ↑ : S → P(T × T ), is defined by: f ↑ (s) = { ( min{ π1( f (s) ) }, max{ π2( f (s) ) } ) }
Consider as an example the event log shown in Tbl. 2 representing the events of a single case. In this example, the time scale is defined as hours since the start of the execution. Many different ways exists to map these events to a generalized interval function on activities.
Two example mappings are given in Fig. 2. In the first example, the start and complete events of each activity are used to define the different intervals, whereas in the second example the very first start event of the activity defines the begin of the interval, and the very last complete event of the activity the end of the interval. Observe that in Fig. 2(a) activities B and C have no overlap, whereas in Fig. 2(a) these activities do have overlap.
In general, an event log records many different executions. Therefore, we map each execution to its own activity interval function. This results in an activity interval mapping for an event log.
As each event belongs to a single activity, we require that an activity interval mapping defines a unique interval for each event in the event log. On the other hand, as an activity may be represented by multiple occurrences, multiple events may be related to the same activity interval. Definition 7 (Activity interval mapping). Let L = (C, E, #) be an event log with corresponding event interval mapping m, let A be a set of activities of L, and let T ⊆ R be the time scale. The function G : C × A → P(T × T ) is called an activity interval mapping iff – each event has a unique corresponding interval, i.e.,
∀e ∈ E : ( ∃I ∈ G(#case(e), #act(e)) : m(e) ⊆ I ) – each interval has at least one event occurrence, i.e.,
∧ ( ∀I, J ∈ G(#case(e), #act(e)) : (m(e) ⊆ I ∧ m(e) ⊆ J) =⇒ I = J ) ∀a ∈ A, c ∈ C, I ∈ G(c, x) : ∃e ∈ E : #case(e) = c ∧ #act(e) = a ∧ m(e) ⊆ I The default activity interval mapping of an event log L, denoted by L¯: C × A → T × T , is defined by:
L¯(c, a) = {m(e) | ∃e ∈ E : #case(e) = c ∧ #act(e) = a}
Many different interval functions can be defined for an event log. As the next corollary shows, such activity interval mappings are related, as intervals may be combined into larger intervals, or split into several smaller intervals. It is simple to see that given some activity interval mapping, its coarsest interval function is also an activity interval mapping. Further, the finest interval function of the minimal activity interval mapping is contained in the finest interval function of the activity interval mapping. Corollary 8. Given an event log L with corresponding event interval mapping m and activity interval function G. Let A be the set of activities in L. Then (1) G ↑is an activity interval mapping, (2) L¯↓ ⊆ G ↓, and (3) π1(G ↑ (a)) ≤ π1(Lˆ↑ (a)) and π2(G ↑ (a)) ≥ π2(L¯↑ (a)) for all activities a ∈ A. 5
In general, a generalized interval function does not define any interval order.
Consequently, approaches like in [
In an interval order two intervals are unrelated if one does not wholly occur after the other, and vice versa. With sets of intervals, different degrees of simultaneousness can be defined.
The weakest form of simultaneousness is when two elements have some overlapping intervals. For example, in the intervals shown in Fig. 3(a), activities A and B have some intervals that overlap. Note that the relation is not transitive, as shown in the same figure. We say an element s is dependent simultaneous with some other element t if for every interval of s, an overlapping interval of t exists. Thus, everytime s is started, t will be started as well, whereas if t occurs, s does not have to occur. If s always overlaps with t, we say they are strongly dependent. A B C A B
C (a) Weakly simultaneous
(b) Dependent simultaneous A B C
(c) Strongly simultaneous
Consider again Fig. 3. In Fig. 3(a) we have A ↔ B and B ↔ C but not A ↔ C, in Fig. 3(b) we have A ⇒ B as every interval of A overlaps with some interval of B, B ⇒ C as each interval of B overlaps with some interval of C and A ↔ C but not A ⇒ C as not every interval of A overlaps with an interval of C. Last, in Fig. 3(c) we have A B, B C and A ⇒ C but not A C, as every interval of A overlaps some interval of C but not vice versa.
Based on their definitions, it is trivial to see that strong simultaneousness implies dependent simultaneousness which in turn implies weak simultaneousness. Corollary 10. Let f be a generalized interval function over some set S , and let s, t ∈ S . Then (1) s ⇒ t ∧ f (s) , ∅ =⇒ s ↔ t, and (2) and ↔ are symmetric and reflexive.
As shown in Fig. 3, none of these relations is transitive. Consequently, we cannot
obtain equivalence classes based on the intervals. As the relation is symmetric and
reflexive, it can be used as a dependence relation over the set of activities, which allows
us to use Mazurkiewicz trace theory [
Fishburn showed in [
(e) Strictly preceeded by b > a, then a and b are causally ordered, i.e., a is followed by b, but b never followed by a. In terms of intervals, similar relations can be defined. Again, as an activity possibly has multiple intervals, we need to adapt the notion of causality to sets of intervals.
The first causality relation we introduce is if all intervals of some activity t occur after the intervals of s occurred, i.e., s is wholly succeeded by t. An example is depicted in Fig. 4(a), in which A is wholly succeeded by B and B is wholly succeeded by C. If for each interval of s some interval of t can be found that wholly succeeds the interval of s, we say that s is succeeded by t. In Fig. 4(b), A is always succeeded by B, and B is always succeeded by C. Note that this allows intervals of t to occur simultaneously with intervals of s, or even occurring before s, as shown in Fig. 4(b) where B occurs before A. If s is succeeded by t and they have no overlapping intervals, we say that s is strictly succeeded by t. An example is shown in Fig. 4(c), where A is strictly succeeded by B, and B strictly succeeded by C. Note that whereas the succeeded relation is transitive, the strictly succeeded is not, as A and C have overlap.
Symmetrically, if for each interval of t an interval of s can be found that wholly preceeds the interval of t, we say that t is preceeded by s. This allows intervals of s to occur after intervals of t, or even simultaneously, as shown in Fig. 4(d) where B is preceeded by A, and C by B. The relation is called strict, if s and t are not simultaneously. Again, as shown in Fig. 4(e), the strictly preceeded relation is not transitive, as B is strictly preceeded by A, and C by B, but A and C have overlap. This leads to the following notions of causality.
Definition 11 (Causality). Let f be a generalized interval function over some set S . Let s, t ∈ S . Then: – s is wholly succeeded by t, denoted by s t, if all intervals of t are after the intervals of s, i.e., π2( f ↑ (s)) < π1( f ↑ (t)); or c
b holds.
Suppose a Proof. Let a, b, c, d ∈ S such that a (d)) ≤ π2( f ↑ (a)) < π1( f ↑ (b)). Hence, c – s is succeeded by t, denoted by s D t, if each interval of s is followed by an interval – s is strictly succeeded by t, denoted by s of t, i.e., ∀(a, b) ∈ f (s) : ∃(c, d) ∈ f (t) : b < c;
t, if s D t and not s ↔ t; of s, i.e. ∀(c, d) ∈ f (t) : ∃(a, b) ∈ f (s) : b < c; – t is strictly preceeded by s, denoted by s = t, if s w t and not s ↔ t. – t is preceeded by s, denoted by s w t, if each interval of t is preceeded by an interval
It is easy to see that the wholly succeeded relation is a strict order. Similarly, the followed by and preceeded by relations are transitive. However, these relations are not irreflexive in general. Only if the set of intervals for some activity is finite, the relations are irreflexive as well, and thus a strict order. If an activity has an infinite set of intervals, then it is succeeded by itself.
If some activity is wholly succeeded by some other activity, then it is easy to show that the former activity is strictly succeeded by the latter, and the latter is strictly preceeded by the former. x, y ∈ S .
Corollary 12. Let f be a generalized interval function over some set S . Then (1) is a strict order, (2) D, and w are transitive, and (3) x y =⇒ x y ∧ x = y for all
Further, the strictly succeeded by and strictly preceeded by relations are subsets of the succeeded by and preceeded by relations, respectively.
Corollary 13. Let f be a generalized interval function over some set S . Then (1) D, and (2) = ⊆ w
defined on events, the wholly succeeded by relation on activities is an interval order, which follows directly from the definitions. Lemma 14 (Wholly succeeded is an interval order). Let f be a generalized interval function over some set S . Then is an interval order.
b, and c
d. We need to show that either a d does not hold, i.e., π2( f ↑ (a)) ≥ π1( f ↑ (d)). Then π2( f ↑ (c)) < π1( f ↑ (a)) < π1( f ↑ (b)) ≤ π2( f ↑ (c)) < π1( f ↑ (d)). Hence, a
b does not hold, i.e., π2( f ↑ (c)) ≥ π1( f ↑ (b)). Then π2( f ↑ 5.3
The simultaneousness and causality relations form the basic building blocks of any process modelling language. Many other control-flow relations can be defined, depending on the needs within the process modelling notation. For example, one can define anextto relation on activities, defining whether two activities are directly after one another, without any activitiy in between. As for simultaneousness, this can be a weak relation, i.e., for two activities there are intervals next to each other, or a strong relation, i.e., for all intervals. ⊆ d tu Definition 15 (Next-to relation). Let f be a generalized interval function over some set S . Let s, t ∈ S . We say s is next to t, denoted by s ◦ t, if some interval of s is directly followed by an interval of t, without any occurrence of other activities in between, i.e., ∃(k, l) ∈ f (s), (o, p) ∈ f (t) : ( l < o ∧ ¬(∃u ∈ S : (m, n) ∈ f (u) : l < n ∧ m < o) )
Similarly, s is followed by t, denoted by s • t, if all intervals of s are directly followed by an interval of t, without any occurrence of other activities in between, i.e., ∀(k, l) ∈ f (s) : ( ∃(o, p) ∈ f (t) : l < o ∧ ¬(∃u ∈ S : (m, n) ∈ f (u) : l < n ∧ m < o) ) Naturally, if s is followed by t, then s is also succeeded by t.
over some set S , and let s, t ∈ S . Then if s • t then also s D t.
As activities are represented by sets of intervals, an activity can be enclosed by some other activity, i.e., some activity B always occurs between two intervals of A. We call this relation betweenness. Again, this can be a strong notion, requiring this for all intervals of B, or a weak notion, only requiring the existence of such an interval of B. Definition 17 (Betweenness). Let f be a generalized interval function over some set S . Let s, t ∈ S . We say t is weakly in between s, denoted by s # t, if some interval of t is in between two intervals of s, i.e., ∃(m, n) ∈ f (t), (k, l), (o, p) ∈ f (s) : l < m ∧ n < o.
Similarly, we say t is in between s, denoted by s t, if all intervals of t are between two intervals of s, i.e., ∀(m, n) ∈ f (t) : (∃(k, l), (o, p) ∈ f (s) : l < m ∧ n < o).
Altough betweenness seems a natural choice, it can be expressed in terms of the basic causality notions defined in Def. 11.
function over some set S , and let s, t ∈ S . If s t then s w t and t D s. 6
The density of the time scale has a great impact on the level of concurrency in an event log, and hence in the model that describes the allowed behaviour of the executions in the event log. Procedural languages prescribe the order in which activities are supposed to occur. Consequently, concurrency needs to be modelled explicitly in such languages. Instead, we use a declarative approach that has concurrency as a language primitive: activities may occur simultaneous, unless constraints prohibit the execution of the activity. 6.1
In this paper, we use the declarative language Declare [
init A A A A B B B n.m A B B B B B
init response precedence non coexistence
σ(1) = A (A =⇒
B) ((¬B) U A) ∨ ¬B ¬(( A) ∧ ( B)) (n..m) occurrences |{i | σ(i) = A}| ∈ [n..m] ⊆ N basic set of language constructs. Tbl. 3 depicts the language constructs from Declare used in this paper.
The first constraint template, init, states that the first activity of any sequence, represented by σ, should start with A, where A is a placeholder for the actual activity. Similarly, the response template states that every A should eventually be followed by some activity B. The precedence constraint template expresses that some activity B has to be preceeded by some activity A. With the non coexistence template, it is possible to express that two activities should not occur together in any sequence. Last, we allow to limit the number of times an activity can be executed using the n..m occurrences template, where n ≤ m specifies the minimal and maximal number of times some activity A is executed.
The constraints in Declare do not take activity duration into account. Consequently, we need to relate the constructs used in Declare with the simultaneousness and causality relations defined in the previous section.
First, consider the response constraint template. This constraint expresses that activity A is always eventually followed by B. This can be interpreted in many different ways, e.g., “once activity A is started, activity B will eventually start”, or “once activity A is finished , activity B will eventually start”. We choose the latter interpretation, i.e., after activity A finished, eventually activity B will start. A second consideration is whether the response and precedence templates should allow the activities in the constraint to occur simultaneously. As the response template is transitive in the Declare language, we allow the activities to overlap. Thus, we interpret the response template with the succeeded by relation introduced in the previous section. Similarly, we interpret the preceeds template as “before activity B starts, activity A should be finished”, which coincides with the preceeds by relation introduced in the previous section. Therefore, the strictly succeeded by and strictly preceeded by relations are added to the Declare language, as shown in Tbl. 4.
Although in Declare concurrency is a language primitive, each activity in the model is considered to be instantaneous. The language does not provide any constraint that limits concurrency without destroying it. Thus, the weak simultaneousness relation as presented in the previous section is directly supported in the language. The two stronger simultaneousness relations impose an order on the activities: although the activities may overlap, the other activity must be executed simultaneously. This is expressed by the strongly simultaneous template and dependent simultaneous template as depicted in Tbl. 4. 6.3
In the previous section, we introduced several notions of simultaneousness and causality. Up to now, these relations only consider a single execution of the system. An event log contains a set of executions that are executed by, most likely, the same process. Hence, to come to a model that describes each of the executions in the event logs, we need to aggregate the relations over the different executions in the event log.
In what follows, we sketch a declarative discovery algorithm based on time intervals. Here, it is important to mention that the choice of the generalized interval functions for the activities breaks or makes the approach presented in this paper. Events to interval First step in the approach is to map each event to an interval. In many cases the default event interval mapping, i.e., that maps each event to a singlepoint interval, can be used. In some cases, for example if event logs of multiple systems are combined, a reliability interval can be attached to each interval.
Activities to sets of intervals Next step is the construction or discovery of an accurate
activity interval mapping. For example, one can fix the granularity of the time scale,
make it relative or absolute, and then map each event to the corresponding time interval.
Or, one can use the event types to determine the life cycle of an activity, and base the
activity interval mapping on this information. Although at first sight this seems to be
a trivial step, there are many pitfalls [
Strongly simultaneousness
Dependently simultaneousness
Weakly simultaneousness
Wholly succeeded by
Strictly succeeded by
Strictly preceeded by succeeded by
preceeded by (a) Simultaneousness
(b) Causality Derive relations Once the activity interval mapping has been established, we can start to derive the different relations. For example, the (n..m) occurrences template can be easily constructed by analyzing the number of occurrences in each of the sequences in the event log. Similarly, the non-coexistence relation can be calculated by a single walk through the sequences of the event log.
Next step would be to derive the different simultaneousness relations and causality relations. For this, we use the relation hierarchy as depicted in Fig. 5, which follows directly from Cor. 10 and Cor. 12. An arrow from one relation to another relation means that the former is included in the latter. For example, the strongly simultaneousness relation is included in the dependently simultaneousness relation. The algorithm starts with assuming the strongest relation between each of the activities. By going through the different intervals, relations are weakened, until all intervals of all sequences in the event log have been inspected.
The algorithms to derive the simultaneousness and causality relations do not take
transitivity into account, which results in models with many constraints, expressing the
complete transitive closure of the respective relations. Therefore, these relations need
to be reduced, such that the transitive closure of this reduced relations remain the same.
For this, standard algorithms as described in [
Last, we sugar the models using nesting, as has been done in e.g. Dynamic
Condition Response Graphs [
For the example event log of Tbl. 1, the discovery algorithm that has been sketched above results in the model depicted in Fig. 6. For the activities B, C, and E, we briefly illustrate the steps of the algorithm. In the first step, we take a relative time scale for the activity interval mapping. Moreover, a “start” event denotes the start time of an activity and a “complete” event denotes the end time of an activity. Secondly, all three 0. 1 B 0. 1 D activities occur at most once in each of the sequences of the event log resulting into a 0..1 occurrence relation for each of them. Also, activity A and B never occur together in each sequence. In the third step, it is discovered that activities B and C are strongly simultaneous. Also, the tree activities are all preceeded by activity A and succeeded by activity G. Finally, in the last step, activities B, E and C are nested, as these activities are all preceeded by A, do not coexist with D and F, and are all succeeded by G. 7
Timestamps in an event log play an essential role in process mining to determine the order in which events occur. A typical problem in process mining is the impreciseness of these timestamps. In this paper, we overcome this problem by assuming that each event occurs in some time window, i.e., in some interval. As the intervals in an event log are on the level of events, rather than on the level of activities, we have presented an approach based on sets of intervals to represent the occurrences of the activities in the model. On these sets of intervals new notions of simultaneousness and causalities are derived. These notions form the basis to discover declarative models.
The simultaneousness relation forms a natural candidate for the dependency relation in Mazurkiewicz traces. In this way, simultaneousness can be used to test the completeness of event logs, by exploring the Mazurkiewicz equivalent traces.
Although intervals are a natural choice to overcome the impreciseness of timestamps, choosing the right time window is a hard problem. The events and activities can be mapped to intervals in many different ways. The granularity of the time scale, like milliseconds, hours or days, can be used to define the intervals, the time scale can be relative or absolute. Or, if the event log contains a transition life cycle, like a start and complete event, then the first and last event of each execution can be used to determine the intervals in the activity interval mapping. Empirical research is needed to test, validate and compare the different alternatives.
As the proof of the pudding is in the eating, we will implement the presented
approach in ProM [