Page 148 -

130 5 Process Discovery: An Introduction

Table 5.1 Footprint of L 1 :
a b c d e
c,
a # L 1 a, a → L 1 b, a → L 1
etc.
a # L 1 → L 1 → L 1 # L 1 → L 1
b ← L 1 # L 1 L 1 → L 1 # L 1
c ← L 1 L 1 # L 1 → L 1 # L 1
d # L 1 ← L 1 ← L 1 # L 1 ← L 1
e ← L 1 # L 1 # L 1 → L 1 # L 1

Definition 5.3 (Log-based ordering relations) Let L be an event log over A , i.e.,
∗
L ∈ B(A ).Let a,b ∈ A :
• a> L b if and only if there is a trace σ = t 1 ,t 2 ,t 3 ,...,t n and i ∈{1,...,n − 1}
such that σ ∈ L and t i = a and t i+1 = b
• a → L b if and only if a> L b and b
> L a
• a # L b if and only if a
> L b and b
> L a
• a L b if and only if a> L b and b> L a

2
3
Consider for instance L 1 =[ a,b,c,d , a,c,b,d , a,e,d ] again. For this
event log, the following log-based ordering relations can be found

= (a,b),(a,c),(a,e),(b,c),(c,b),(b,d),(c,d),(e,d)
> L 1

= (a,b),(a,c),(a,e),(b,d),(c,d),(e,d)
→ L 1

= (a,a),(a,d),(b,b),(b,e),(c,c),(c,e),(d,a),(d,d),(e,b),(e,c),(e,e)
# L 1

= (b,c),(c,b)
L 1
d
Relation > L 1 contains all pairs of activities in a “directly follows” relation. c> L 1
c because c never
because d directly follows c in trace a,b,c,d . However, d
> L 1
contains all pairs of activities in
directly follows d in any trace in the log. → L 1
d because sometimes d directly follows c and
a “causality” relation, e.g., c → L 1
c and
never the other way around (c> L 1 d and d
> L 1 c). b L 1 c because b> L 1
e
c> L 1 b, i.e., sometimes c follows b and sometimes the other way around. b # L 1
b.
because b
> L 1 e and e
> L 1
For any log L over A and x,y ∈ A : x → L y, y → L x, x # L y,or x L y,
i.e., precisely one of these relations holds for any pair of activities. Therefore, the
footprint of a log can be captured in a matrix as shown in Table 5.1.
The footprint of event log L 2 is showninTable 5.2. The subscripts have been
removed to not clutter the table. When comparing the footprints of L 1 and L 2 , one
can see that only the e and f columns and rows differ.
The log-based ordering relations can be used to discover patterns in the corre-
sponding process model as is illustrated in Fig. 5.4.If a and b are in sequence, the
log will show a → L b.Ifafter a there is a choice between b and c, the log will show
a → L b, a → L c, and b # L c because a can be followed by b and c,but b will not
be followed by c and vice versa. The logical counterpart of this so-called XOR-split