Диссертация (1137084), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Let ∈ ℬ(∗ ) be anevent log with ⊆ and let N ∈ N be a workflow net. For any valid decomposition ={N 1 ,N 2 , . . . ,N } ∈ (N ): is perfectly fitting workflow net N if and only if for all 1 ≤ ≤ :↾ (N ) is perfectly fitting N .Theorem 2 (Discovery Can Be Decomposed [126]). Let ∈ ℬ(∗ ) be an event log with ={ ∈ ⋃︀ ∈ } ⊆ , = {1 , 2 , . . . , } with = ⋃ , and ∈ ℬ(∗ ) → N a discoveryalgorithm.

Let _(,,) = {N 1 ,N 2 , . . . ,N } and N = ⋃1≤≤ N . N ∈ N and ={N 1 ,N 2 , . . . ,N } is a valid decomposition of N , _(,,) ∈ ( ).Consider an example that illustrates an application of these propositions. In particular, recallthe workflow net that has been discussed in Section 1.1.2 (see Figure 1.2). Figure 2.2 showsthis workflow net. Recall, that it represents handling of expenses compensation requests in somecompany. Transition labels are shortened for the readability of figure and have the followingmeaning: Register request =a, Check ticket = b, Examine casually = c, Examine thoroughly = d,Decide = e, Send rejection letter = f, Pay compensation = g, Re-initiate request = h.ht8asourcet1bc1t2c2cft3t6dt4ec3t5c4gsinkt7Figure 2.2: Model of compensation requests handlingThis workflow net, in particular, can be automatically discovered from the following event logconsisting of three traces: = (︀∐︀, , , , ̃︀ ,∐︀, , , , ̃︀ ,∐︀, , , , ℎ, , , , ̃︀⌋︀.Figure 2.3 shows a particular example of how the model from Figure 2.2 may be validlydecomposed.

There are two sub-nets in this decomposition: 1 and 2 . Border transitions are 8(labelled with h), 3 (c), and 4 (d). These transitions are used to split the model. Other transitions54(1 , 2 , 5 , 6 , and 7 ) are inner nodes of sub-nets. Note that sub-nets 1 and 2 can be easilycomposed via fusion of transitions with the same labels (8 with ′8 , 3 with ′3 , and 4 with ′4 ).This can be done because border transitions were selected from the set of visible transitions withunique labels (N ).N1N2asourcet1bc1t2c2hht8t8'ccft3t3't6ddt4t4'ec3t5c4gsinkt7Figure 2.3: Valid decomposition of the model from Figure 2.2An event log can be split into two sub-logs 1 and 2 corresponding to the sub-model 1and 2 using simple projection.

In each sub-log the events remain with names matching withlabels of transitions in the corresponding sub-net. Indeed, there will be two following sub-logs:1 = (︀∐︀, , ̃︀ ,∐︀, , ̃︀ ,∐︀, , , ℎ, , ̃︀⌋︀, and 2 = (︀∐︀, , ̃︀ ,∐︀, , ̃︀ ,∐︀, , ℎ, , , ̃︀⌋︀.Theorem 1 states that if (, ) = 1 then (1 ,1 ) = (2 ,2 ) = 1 and viceversa, if (1 ,1 ) = (2 ,2 ) = 1 then (, ) = 1. One may seen that it istrue in the discussed case.

The same holds for any event log. Moreover, if an event log does notfit the model perfectly, then there is at least one sub-net unfitting to a corresponding sub-log.If the set of process activities can be split = {1 , 2 , . . . , } (where = ⋃ ), then eachof these activity sub-sets can be used to obtain a sub-log containing only activities from thesub-set .

Then, each sub-log can be used to discover a process model . Finally, Theorem 2states that the all these sub-models together = {N 1 ,N 2 , . . . ,N } form a valid decomposition ofthe model that is a union of sub-models N = ⋃1≤≤ N .Based on these two theorems, the sufficient conditions for perfect fitness repair can beformulated. Such a repair guarantees that the repaired model perfectly fits the event log usedfor repair. In particular, this can be defined as follows.Definition 8 (Perfect Fitness Repair for Workflow Nets).

Let ∈ ℬ(∗ ) be an event log with ⊆ , and let N ∈ N be a workflow net such that fitness(, N ) < 1. Let N ′ = ModularRepair (, N ) bea modular repair scheme. ModularRepair (L, N ) is a perfect fitness repair if fitness(, N ′ ) = 1.Next proposition states that the modular repair is perfect fitness repair (i.e. guarantees perfectfitness), if it uses perfect discovery and valid decomposition algorithms. A perfect discoveryalgorithm for any given event log construct a perfectly fitting process model.

A valid decompositiondecomposes both model and its marking, and allows for single-valued composition of sub-modelsbackward into a single model.55Theorem3(PerfectFitnessRepairConditions). ThemodularrepairschemeModularRepair (L, N ) ensures perfect fitness if1. split is a valid decomposition function;2. repair is a perfect discovery function, i.e. for any event log it returns a Petri net, whichperfectly fits this event log;3. compose is a transition fusion function that merges all transitions with the same labels.Proof. This proposition is a direct corollary of the Theorem 1.

Let N be a workflow netwith fitness(, N ) < 1. By applying split is decomposed into a set of fragments ={N 1 , N 2 , . . . ,N }. Each fragment N is then evaluated, let = fitness(↾ (N ) , N ). By Theorem 1∃∶ 1≤≤, fitness(↾ (N ) , N ) < 1, since the decomposition is valid. Fragments with not perfectfitness should be repaired. Then repair function repair is applied to each such fragment.

For each, 1≤≤ let N = repair (↾ (N ) ,N ) if fitness(↾ (N ) , N ) < 1, and N = N if fitness(↾ (N ), N ) = 1. Since we use a perfect discovery function, we get ∀∶ 1≤≤, fitness(↾ (N ) , N ) = 1.Note that the set of activities was not changed. By Theorem 2 the set = {N1 , N2 , . . . ,N } isa valid decomposition of the net N = ( ). Moreover, each fragment perfectly fits thecorresponding event log projection.

Hence, by Theorem 1 we get fitness(, N ) = 1.So far the general scheme of modular repair has been presented. It has been shown, thatmodular repair guarantees perfect fitness of the repaired model, if the repair conditions aresatisfied. The next Section 2.3 presents a concrete instantiation of this general scheme, whichuses a particular set of algorithms as building blocks.2.3Modular Repair using Maximal DecompositionThis section considers the concrete modular repair technique implementing the scheme definedin the previous section. The remainder describes specific algorithms which are used as buildingblocks.In this particular setting, the procedural parameters of the modular repair scheme are asfollows:– an evaluation function eval ∈ (ℬ(∗ ) × N ) → (︀0; 1⌋︀ is the alignment-based fitnesschecking algorithm [22],– a model repair function repair ∈ ℬ(∗ ) × N ) → N is the inductive process discoveryalgorithm [23], or the integer-linear-programming-based discovery algorithm [24],– a decomposition function split ∈ N → (N ) is the maximal decomposition algorithm,– a composition function compose ∈ (N ) → N is the algorithm based on fusion oftransitions with the same labels.56This gives us a concrete decomposed repair algorithm.

Note that this repair algorithmcompletely satisfies the perfect fitness repair (see Theorem 3) conditions (1), (2), and (3). Indeed,as building blocks are used:1. maximal decomposition, which is valid,2. discovery algorithms, which guarantee perfect fitness of the discovered Petri net by definition,and3. simple transition fusion algorithm for sub-nets’ composition.To split the initial workflow net into sub-nets the maximal decomposition is used.

It is basedon partitioning of net arcs and is organized as follows.Each arc of the net resides strictly in a single sub-net (or model fragment). All nodes in eachfragment are divided into boundary (or border, borderline) and internal (or inner ) nodes. Visibletransitions with unique labels are placed on borders of fragments. Note that each such transition issplit. This is why decomposition is called maximal : the number of fragments is maximal, whereasthe size (number pf nodes) of each fragment is minimal. This decomposition is valid, and a netcan not be validly decomposed into finer fragments.A boundary node after decomposition can be connected only with internal nodes of itsfragment. Each visible transition, which has a unique label in the original net, is divided betweentwo or more sub-nets (its copy belongs to each of these fragments).

This supports the causaldependencies between model fragments, and allows for joining sub-nets together via transitionfusion.Places, invisible transitions, and transitions with non-unique labels can be internal nodes only.Within a fragment, each of internal nodes can be connected by an arc either with a boundarynode , or with another internal node.An initial marking is distributed between fragment in a natural way. A place in a fragment ismarked iff it was marked in the original net Recall, that places are not copied but just distributedbetween sub-nets.

Характеристики

Список файлов диссертации