This paper addresses the problem of discovering a sound Workflow net (WFN) from sample event traces representing the behavior of a process. A current challenging problem deals with discovering a suitable model from incomplete logs since it is not possible to ensure that a log contains all executions of a process. A method that allows building WFN from logs including a reduced number of traces is presented. It is based on the concept of invariant occurrence between activities, which yields sets of activities named conjoint occurrence classes, which are used to infer the causal and concurrent behavior not exhibited in the log. Procedures derived from the method have been implemented in the ProM framework. Experimental results show that the algorithm can discover models form logs including less traces compared to other standing discovery algorithms.
The automated synthesis of formal models from the observation of a process
execution in the form of event sequences is called process discovery [
One significant problem in process discovery techniques is the fact that the log could not contain enough information to discover a process model, i.e. the log might be incomplete. This might cause that the obtained model excludes actual behavior or represents some behavior that is not in the real process. Many things can cause the incompleteness of the log; one of the most common is the presence of parallelism, due to the high number of possible parallel activities whose interleaving cannot be sampled in the traces.
The obtained model through a discovery technique must be easy to
understand by representing clearly, the causal and parallel relationships between the
activities. Furthermore, such a model must represent all the observed behavior
(provided as input data) and the lowest amount as possible of non-observed
behavior. Several metrics called quality dimensions [
A procedure used to test whether or not a technique is able to discover models that have the same language as the real-life process by which a log was produced is called rediscoverability, which compares the obtained model directly with the real-life process. This procedure is summarized in Figure 1.
The method proposed in this paper pursues to obtain a suitable Petri net model that reveals some behavior hidden in the log, namely some causal and/or concurrent relationships. A method that allows building sound WFN from logs including a reduced number of traces is presented. The discovery technique is based on the concept of invariant occurrence between activities, which leads to obtain sets of events named conjoint occurrence classes; such classes help to infer the causal and concurrent behavior not exhibited in the log.
The paper is organized as follows. In Section 2 the related work is overviewed, In Section 3, the basic notions of PN and WFN are recalled. Section 4 states the first notions of invariance of occurrence and defines the occurrence classes. In Section 5 the synthesis of PN model from the conjoint occurrence classes is presented. Section 6 demonstrates the performance of the proposal through experiments and the results are compared with other approaches. Section 7 concludes the paper. 2
Pioneer works on the matter, named language learning techniques, have been
proposed in the field of computer sciences. The aim was to build fine
representations (finite automata, grammars) of languages from samples of accepted words
[
In the field of Discrete Event Systems (DES), where the problem is named
identification, several approaches have been proposed for building models
representing the observed behavior of automated processes. The incremental approach
proposed in [
In both fields, the aim in general is to discover processes models from observed behavior. However, the nature of processes leads to problem statements somehow different in terms of input data. 3
This section presents the basic concepts and notations used in this paper.
sented by the 4-tuple G = (P, T, I, O) where: P = {p1, p2, ..., p|P |} and T = {t1, t2, ..., t|T |} are finite sets of vertices named places and transitions respectively; I : P × T → {0, 1} (O : T × P → {0, 1}) is a function representing the arcs going from places to transitions (from transitions to places).
A marking function M : P → N represents the number of tokens residing inside each place; it is usually expressed as an |P |-entry vector.
A Petri Net system or Petri Net (P N ) is the pair N = (G, M0), where G is a P N structure and M0 is an initial marking. In a PN system, a transition tj is enabled at marking Mk if ∀pi ∈ P, Mk(pi) ≥ I(pi, tj ); an enabled transition tj can be fired reaching a new marking Mk+1. The reachability set of a PN is the set of all possible reachable markings from M0 firing only enabled transitions; this set is denoted by R(G, M0). For any tj ∈ T , •tj = {pi|I(pi, tj ) = 1}, and tj • = {pi|O(tj , pi) = 1}, similarly for any pi ∈ P , •pi = {tj |O(tj , pi) = 1}, and pi• = {tj |I(pi, tj ) = 1}.
A PN system is 1-bounded or safe iff, for any Mi ∈ R(G, M0) and any p ∈ P, Mi(p) ≤ 1. A PN system is live iff, for every reachable marking M i ∈ R(G, M0) and t ∈ T there is a reachable marking Mk ∈ R(G, M0) such that t is enabled in Mk.
lowing properties [
A consecutive activities sequence: x, d, e, a, b, y of a process executions that brings the system from initial state into the final state, corresponds to a trace; a workflow log is a multiset of traces. The set of traces that can be produced by a model N , is the language of N , is denoted by L(N ). An example workflow net is shown in Fig.2
marking Mi ∈ R(N, M0), o ∈ Mi → Mi = [o], N not contains dead transitions.
a, b ∈ T :
- a →λ b, iff there is a trace σ = t1, t2, ...tn >∈ λ and 1 ≤ i < n − 1, such that ti = a, ti+1 = b, - a||λb iif a →λ b and b →λ a. - f irst(σ) = t1, last(σ) = tn, if n ≥ 1
The ordering relations has been used in [
flow log of N . λ is a complete workflow log of N iff (1) for any workflow log λ of N : →λ ⊆→λ, (2) each activity of N is present in λ. 4
This section introduces the notion of invariance of occurrence and presents a technique for deriving a partial order relationship between activities. 4.1
A trace is a sequence of ordered activities, such that the immediately preceding activity of a referent activity in the sequence, is associated with a position that is less by exactly one from the position of the reference activity. i.e. < a, b, c > is a trace where the activity a is associated with position 1 the activity b is associated with the positions 2 and the activity c is associated with the position 3, we denote xi to refer the ith activity in the trace. First, useful operators for expressing the relative positions of activities in a trace and activity precedence/subsequence relationships are introduced.
Definition 6. (Trace handling operators). Let λ be a workflow log over T , let a ∈ T ; if there is a trace σk = x1, x2, ..., xn such that σk ∈ λ and a ∈ σk, • τ (xi, σk) provides the activity name of element xi in σk • P os(a, σk) = {p, q, r . . . , s} such that τ (xp, σk) = a, ..., τ (xs, σk) = a • P red(xi, σk) = τ (xi−1, σk) , i ∈ {2, 3, . . . , n} • Succ(xi, σk) = τ (xi+1, σk) , i ∈ {1, 2, . . . , n − 1}
, if 1 ∈ P os(a, σk) ⎧⎪ ∅ • P redset(a, σk) = ⎨⎪⎪
⎧⎪ ∅ • Succset(a, σk) = ⎨⎪⎪ ⎪⎩⎪⎪ ⎪⎩⎪⎪ ip=2 P red(xi, σk) ∩ · · · ∩ ir=q+2 P red(xi, σk)
s ∩ i=r+2 P red(xi, σk), if P os(a, σk) = {p, . . . , q, r, s}, p <, . . . , < r < s , if
n ∈ P os(a, σk) q−2 i=p Succ(xi, σk) ∩ ∩ in=−s1 Succ(xi, σk),
ir=−q2 Succ(xi, σk) ∩ . . .
if P os(a, σk) = {p, q, r, . . . , s}, p < q <, . . . , < s
The function P os(a, σk) provides a set of indices in which the symbol a appears in the trace σk, while the functions P red and Succ provide, respectively, the predecessor and successor activity of xi in the trace. The P redset is build from the activities sets appearing between the occurrence of the activity symbol, together with the beginning of the trace and the first occurrence of the activity symbol; the operator yields common symbols among these activities sets. The Succset is defined similarly. Example 1. Consider a log λ with three traces σ1 = x, a, b, d, e, c, a, b, y , σ2 = x, d, e, a, b, y , σ3 = x, a, b, d, c, a, e, b, y , which has been produced using the workflow net N in Fig. 2. Note that is not a complete with respect to N , since b →N c, e →N y hold in N but not in λ. Furthermore, the only knowledge about the parallel behavior generated between the cycle (a, b, c) and the sequence (d, e) is a||λe; all the other parallel relations are not in λ. The relations found in λ are the following: x →λ (a, d), a →λ (b, e), b →λ (d, y), c →λ a, d →λ (c, e), e →λ (b, a).
If we apply the P redset and Succset functions over the activity symbol a and the traces in λ we get: P redset(a, σ1) = {x} ∩ {b, d, e, c} = ∅, P redset(a, σ2) = {x, d, e}, P redset(a, σ3) = {x} ∩ {b, d, c} = ∅; Succset(a, σ1) = {b, d, e, c} ∩ {b, y} = {b}, P redset(a, σ2) = {b, y}, P redset(a, σ3) = {b, d, c} ∩ {e, b, y} = {b}. 4.2
Now, we are going to introduce several notions useful to determine the sets of activities that occur together in all traces of λ.
the set of activities that always precede a in every trace σk it appears, i.e. InvP red(a, λ) = σk P redset(a, σk). Similarly the Invariable subsequent set is InvSucc(a, λ) = σk Succset(a, σk).
set of activities that always occur when a occurs, that is, Oi(a) = InvP red(a, λ)∪ InvSucc(a, λ) ∪ {a}. Definition 9. Let R be a binary relation over T defined as R = {(a, b)|b ∈ Oi(a), ∀a, b ∈ T }. Let R be the coarsest equivalence relation such that R ⊆ R. R is called the Conjoint Occurrence Relation (COr) and the equivalence classes are called Conjoint Occurrence Classes (COci).
The Conjoint Occurrence Classes of the log above are COc1 = {a, b}, COc2 = {c}, COc3 = {x, d, e, y}; the Fig. 3 shows the matrix representation of the relation R in which the doted rectangles represent the COci.
currence Class induced by R , and a ∈ COck; when σi ∈ λ is executed, such that a ∈ σi all activities in COck are also executed in σi.
Proof. By definition, Oi(a) provides all the activities that invariably occurs when a occurs. Consider ∀a, b, c ∈ COck, a ∈ Oi(a), if a ∈ Oi(b) then b ∈ Oi(a) and if a ∈ Oi(b) ∧ b ∈ Oi(c) then a ∈ Oi(c), there is no activity unrelated among the rest of activities; then the set is invariable in all the traces of λ.
Class induced by R . All the activities in COck occur in the same order in all the σi ∈ λ.
Proof. Assume that there are two activities a, b ∈ COck, in a parallel relation (a||b); then when the operators Predset and Succset are applied to one activity, the other one will not appear in its Oi(), consequently they are not in the same COck. Similarly, suppose that there are two traces in which a and b appear in a different order; then the same reasoning is applied to conclude that such activities cannot belong to the same COck.
If we take activities a, b ∈ T of Example 1, we can observe that a ∈ COc1 and the activity a is present in σ1, σ2, σ3; consequently, b is also in σ1, σ2, σ3, as shown in the traces. σ1 = x, a, b, d, e, c, a, b, y , σ2 = x, d, e, a, b, y , σ3 = x, a, b, d, c, a, e, b, y ; furthermore, they occur in the same order.
Besides the Invariance and Order information provided by the Conjoint Occurrence classes, they provide much more information about the final model. Given the way in which this classes are computed and the partition of the alphabet T ; it is possible to obtain hidden relations between the elements of a COci; below we present some propositions that help to find this hidden relations. 5.1
structure (transition-place-transition) according to their Order, in which each couple of consecutive activities are causally related.
Proof. (by contraposition). Suppose that the elements in COck do not have a PN sequential substructure according to their Order. Let a, b be any activities in COck such that a < b (a before b); given that there is not a PN sequential substructure, at least one of the places pi that connect a to b is missing causing that b could appear before a in some execution; therefore by proof of Proposition 2, these sets of elements cannot be in the same COck.
Definition 10. Each sequential Petri Net sub-structure can be disassembled in three parts: the start and the end activities according to the order and rest of the sequential substructure, which is called the body.
denoted (a ⇒ b), iff they are consecutive in the order of the COci
by a COc, •pi = 1 and pi• = 1; additionally their input and output activities must belong to the COc.
Proof. Following the same reasoning as in the proof of Proposition 3, given that place pi exists but there is an activity k ∈ pi• such that k ∈/ COci, it could provoke an execution in which the activity a appears without the future appearance of b; therefore a, b are not in COc. In case that k ∈ •pi, this allows an execution in which the activity a appears without the previous appearance of b. 5.2
The incompleteness of the log is mostly caused by the high level of parallel behavior of activities in the real process, this is a common issue in several discovery techniques based on Log ordering relations. The COc classes provide a way to deal with this problem. Since the members of a COc are causally related, given a property of one of its elements, this may be transmitted to the other members in the class, i.e. it is possible to deduce parallel behavior between a couple of activities, even if they are not directly consecutive in both directions.
Most of the workflow systems offers standard building blocks such as
ORsplit, OR-joint, AND-split, AND-joint [
such that at least an activity a ∈ COci is parallel to an activity b ∈ COcj i.e. (a||b) then.
either COci or COcj , such that COci ∪ COcj ⊆ Oi(x) ∩ Oi(y), then x, y are
(COci||COcj ), with the exception of activities corresponding to And-split or And-join.
Proof. (1) Given that Oi(a) contains the activities that occur whenever the a occurs and the And-split structure puts a token in two or more places enabling different threads, the only way in which an activity a has an And-split structure is that his Oi(a) contains all the activities involved in all the parallel threads. The reasoning is similar for the AND-joint case.
(2) Given that both COci and COcj define sequential substructures in which each place has one input and output, then the only way to see the presence of an activity a ∈ COcj during the sequential execution of COci, is that the activities in both sequential substructures are enabled by a previous And-split, consequently the activities in COci have a parallel behavior with the elements of COcj
The COc gives a partitioned view of the process. Next function helps to join this partitions in order to complete the model.
Definition 12. Let X ⊆ T be a set of activities and σi ∈ λ; the function φX (σi) filters the trace by applying the natural projection of σi over T \X.
The previous function makes a filtering over the log traces, by removing all the occurrences of any activity a ∈ X. The traces preserve the order of reminder activities.
Once the parallel behavior between all the COc have been detected, it is possible to use the φX function as a strategy to find missing parallel behavior or links (causal relations) between sequential substructures, by assigning to X the parallel activities of a COci w.r.t a COcj and vice versa.
In order to illustrate how the function φX operates, it is applied on the COc and previous log. Since e||a, then COc1||COc3. Giving X the parallel activities in COc1 the result is: φ{a,b}(σ1) = x, d, e, c, y , φ{a,b}(σ2) = x, d, e, y and φ{a,b}(σ3) = x, d, c, e, y , then by computing the Relations between activities for the filtered log, a new parallel behavior is discovered: c||e, therefore COc2||COc3.
Now being X the parallel activities in COc3, the result is, φ{d,e}(σ1) = x, a, b, c, a, b, y , φ{d,e}(σ2) = x, a, b, y and φ{d,e}(σ3) = x, a, b, c, a, b, y , then the new consecutive relation b →λ c is discovered.
Notice that x, y are not part of the parallel behavior because they are the start and end in COc3; furthermore, COc1 ∪ COc3 ⊆ Oi(x) ∩ Oi(y), thus x, y corresponds to an AND-split and AND-joint respectively. The application of this procedure to the new parallel relation (COc2||COc3) does not create new →λ relations. This log filtering is performed iteratively over all the classes that have a parallel relation in addition to the new ones which result of a previous filter. The computation ends when no new consecutive relations are found. 5.3
Once a hidden behavior in the log is found, it is used to connect all the sequential substructures into the final model by creating new places. Table 2 shows the Relations between activities of the log λ in Example 1, after adding the found relations by filtering the log.
The rest of (a →λ b) relations after removing all the parallel behavior (||λ) determine the existence of a place between activities a and b; some of these are already considered by the places which conform a sequential Petri Net substructure, such is the case of the strong causal relations (a ⇒ b) in COc1 and (x ⇒ d), (d ⇒ e), (e ⇒ y) in COc3 for Example 1. For the rest of relations, the addition of places is quite intuitive, it is defined as follows. Definition 13. (Merging activities in →λ relation). When the left activity in two →λ relations are the same (a →λ b, a →λ c) two possible substructures can be created.
a) The places of →λ relations are merged into a single one iff (b λ c ∨ c λ b) This is denoted as [a, b + c].
b) The places of →λ relations are not merged iff (b →λ c ∨ c →λ b) This is denoted as [a, b||c].
Similarly, for →λ relations when the right activity is common, (b →λ a, c →λ a), the substructure created will be either [b||c , a] or [b + c , a] accordingly. In general, a set of →λ relations in the form (a →λ b, a →λ c, . . . , a →λ d) may produce either [a, b + c + d] or [a, b||c||d]. Consequently, the merging can be applied to composed relations, i.e. [b + c , a] and [b + c , d] leads [b + c , a + d].
For the activities in f irst(σ) or last(σ) we add two more places corresponding to the i and o places in the final workflow model i.e. a ∈ i • |∃σi, a ∈ f irst(σi) and a ∈ •o|∃σi, a ∈ last(σi)
A similar way to infer the merging of places is presented in [
The Fig. 5 shows the Petri Net model after connecting the sequential substructures with the new relations.
All the definitions previously described can be summarized in the following algorithm that we called the Conjoint Occurrence Miner (CoM ). 6
We implement the CoM algorithm as a plunging in the ProM Framework [
The aim of these experiments is to show first, how the CoM algorithm deals with small logs, and then, to present how others process discovery algorithms work with the same incomplete logs.
We used the Workflow net N presented in Figure 2 to generate a complete workflow log λ according to the → relation, then we construct 4 smaller sublogs of λ by removing traces from λ , which have 0.90, 0.80, 0.75 and 0.60 of the average ratio of →-pairs compared to the model N , named λ0.90, λ0.85, λ0.75 and λ0.60 respectively. In this case, λ0.60 corresponds to λ presented in Example 1.
For this experiment, we consider the following discovery algorithms: Integer
Linear Programing miner (ILP )[
(1) L(N ) = L(ILP (λ0.85)), L(N ) = L(α(λ0.90)), L(N ) = L(IM (λ0.90)), L(N ) = L(IM in(λ0.60)) and L(N ) = L(CoM (λ0.60)). (2) ILP , α and IM require the full → relations for rediscover the original model N , whereas IM in and CoM rediscover N with λ0.90, λ0.60 respectively.
The one that needs less information for rediscover the model is the CoM algorithm. Figure 6 shows fragments of the resulting models applying the others algorithms to λ.60.
In this experiment, thirty logs are used to tests the proposed method and other discovery techniques. Such logs have been obtained in the same way than in Experiment 1, from six diverse sound WFN involving form six to ten activities; the nets are shown in Figure 7.
Results. Table 3 shows the results of Experiment 2. Column 2: gives the percentage of logs for which the discovery technique returns a language equivalent model. Column 3: gives the percentage of logs for which the technique is able to rediscover the original model. Although the method shows good results for dealing with incompleteness, there are particular behaviors that cannot be discovered using this technique; such is the case of short loops structures as shown in N1 and N2 of Figure 8. This is because it is not easy to infer the conjoint occurrence classes COc from traces in which an activity can be observed directly after itself.
In this work a novel discovery technique is presented. It is based on a new relation between activities called Conjoint Occurrence Relation, which leads to a partition of the activities alphabet into classes. Such classes are used to infer causal and parallel relations missing in the incomplete log, and consequently, Petri net substructures. Furthermore, the experimental results show that the performance algorithm is acceptable with respect to other relevant discovery techniques. Although the technique is presented as a discovery one, which can deal with logs including reduced number of traces, the proposed notions and algorithms seem to be a promising approach for dealing with the problem of rediscoverability. Current research addresses study the class of models and the minimum behavior exhibited in the log for ensure this property.