Диссертация (1137084), страница 14
Текст из файла (страница 14)
When decomposing a workflow net, its single source place belongs to exactlyone fragment with the token residing in it. A maximally decomposed net can be easily composedvia fusion of boundary transitions with the same labels.Formally, maximal decomposition has been defined by W. van der Aalst [126].
We adopt thisformal definition for workflow nets as follows.Definition 9 (Maximal Decomposition of a Workflow Net). Let N = (, , , ) ∈ N be alabelled workflow net. The set of sub-nets Dmax (N ) = {(P(x ,y) , T(x ,y) , ⎷(x , y)⌄, l↾T(x ,y) ) ⋃︀ (x ,y) ∈ F }is the maximal decomposition of net , where– for any edge (x , y) ∈ F : ⎜(x , y)⨆︁ ⊆ F is the smallest set such that– (, ) ∈ ⎜(, )⨆︁, and– (′ , ′ ) ∈ ⎜(, )⨆︁ if (′ , ′ ) ∈ and {′ , ′ } ∩ ((⎜(, )⨆︁) ∖ (N )) ≠ ∅;57– for any set of edges ⊆ : = {() ⋃︀ ∈ () ∩ (N )};– for any edge (x , y) ∈ F : ⎷(, )⌄ ⊆ is the smallest set such that– ⎜(, )⨆︁ ⊆ ⎷(, )⌄, and– ⎜(′ , ′ )⨆︁ ⊆ ⎷(, )⌄ if (′ , ′ ) ∈ and (⎜(′ ,′ )⨆︁ ∩ ⎷(,)⌄ ) ⊈ l (Tvu (N )), where l (Tvu (N )) arenames of unique visible process activities;– the sets of places (,) = (⎷(, )⌄) ∩ and transitions (,) = (⎷(, )⌄) ∩ of thesub-net are defined by edges ⎷(, )⌄;– an initial marking of a fragment is distributed using simple projection: = ↾(,)where (,) ∈ .Figure 2.4 shows a maximal decomposition of the process model shown in Figure 2.2.
The netis decomposed into six net fragments: 1 , 2 , 3 , 4 , 5 , and 6 . All transitions in theinitial model are visible and have unique labels. Thus, transitions 1 (a), 2 (b), 3 (c), 4 (d),5 (e), 6 (f), 7 (g), and 8 (h) are borderline nodes. Inner nodes are places , 1 , 2 , 2 ,3 , 4 , and . One may see how the initial marking is split: the single token goes with the place in the sub-net 1 . It is easy to see, that fragments can be composed into the workflownet shown in Figure 2.2 via a fusion of transitions with the same labels.SN5hSN2hSN1sourceaat1t1c1t8SN3cSN4cbbt3t3eet2t2ddt5t5t4t4c2t8c3c4fSN6ft6t6ggt7t7sinkFigure 2.4: Maximal decomposition of the model from Figure 2.2Another example of decomposition is shown in Figure 2.5. The initial model contains fourvisible transitions with unique labels: 1 (a), 3 (b), 4 (c), and 7 (d).
These transitions areused to split the model, and became borderline nodes. Transition 8 (e) is also visible and has aunique label. Therefore, it can be split, but both copies of the transition fall into a single fragmentof decomposition (4 ). That is why the transition is not split. There are three types of innernodes in this decomposition: 10 places (, 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , and ), 2 silenttransitions (2 and 6 ), and 2 transitions with the same label (9 and 10 with label f). The wholedecomposition contains four sub-nets.In the context of this thesis, the most important property of maximal decomposition is thatit is a valid decomposition by construction [126]. Moreover, it can be shown that the maximaldecomposition is a valid decomposition with the minimum possible size of fragments, i.e.
it ismaximal. Note that maximal decomposition is not the only possible decomposition that can beused as a building block. Section 2.6 discussed other existing decomposition algorithms.58casourceτt1t2p1at1t7p6p7p3τp1t2p2ecct4t4bbt3t3fp8t10sinkt8p4SN3SN1at9dτt6t3SN2t1p5bp2sourceft4p3SN4fp5τt6p6p4ddt7t7t9p7efp8t10sinkt8Figure 2.5: Example of a maximal decomposition of the model with silent transitions andidentical transition labelsMaximal Decomposition AlgorithmThis section presents the Algorithm 1 which we developed to construct the maximaldecomposition according to Definition 9.Five functions constitute the algorithm: decompose, handlePlace, handlePlaceRecursively,andtwofunctionshandlePresedingTransitions,handleSubsequentTransitions.Analgorithm entry point is in the main function decompose.The algorithm works as follows. Function decompose starts from an arbitrary place of initialnet.
It calls handlePlace function while there are places to traverse in the net. The handlePlacefunction is needed to begin the recursive procedure handlePlaceRecursively from place selected at the current step. This procedure consequently traverses predecessor and successor nodesof place using functions handlePresedingTransitions and handleSubsequentTransitionscorrespondingly. These functions split the net fragments if find a visible transition. Note thatall visible transitions in the initial net are assumed to have unique labels. There are notwo transitions with the same label like transitions 9 and 10 with label f in Figure 2.5.Function handlePresedingTransitions traverses all incoming arcs of .
If a predecessortransition is visible, it is split. Otherwise, the recursive procedure handlePlaceRecursivelyis started from each place connected to via an incomming arc incoming(N, t). FunctionhandleSubsequentTransitions works in the same way.The algorithm begins traverse from an arbitrary place but always visits each place of the initialmodel. Visited places with their labels are stored in a map in the decomposefunction. Functions handlePresedingTransitions and handleSubsequentTransitions alwaysprocess each incoming and outgoing arc of the processed place, and check a transition at the otherend of the arc if can be made borderline transition.
Thus, this algorithm visits all places and all59Algorithm 1 Maximal decomposition algorithmInput: a Petri net = (, , , , ) with initial and final markings;places and transitions are labelled, a label of is assessable via ().Output: a set of Petri nets is the maximal decomposition of .1:2:3:4:5:6:7:8:9:10:11:12:Function decompose( ) ← ; ← ∅;For all ∈ doIf ∉ ( ) then′ ′ = ( ′ , ′ , ′ , , ′ ); ← ∪ handlePlace( , , ′ );( ′ ) ← ( ); ← ∪ { ′ };EndIfEndForreturn ;EndFunction▷ make new empty fragment13:14:15:16:17:18:Function handlePlace( , , ′ ) , ← ;handlePlaceRecursively( , , ′ , , );return ;EndFunction▷ mapping of nodes from original net to a current fragment19:20:21:22:23:24:25:26:27:Function handlePlaceRecursively( , , ′ , , )If ∈ ( ) thenreturnEndIf (︀⌋︀ ←Ð ( ′ , ());handlePrecedingTransitions( , , ′ , , );handleSubsequentTransitions( , , ′ , , );EndFunction▷ create new place in ′ with label of 28:29:30:31:32:33:34:35:36:37:38:39:40:41:42:43:44:45:Function handle(Preseding/Subsequent)Transitions( , , ′ , , )For all ∈ (⇑)(, ) do′ ←Ð ; ← (⇑)( );If ∈ ( ) then′ ←Ð (︀⌋︀;else′ ←Ð ( ′ , (), ()); (︀⌋︀ ←Ð ′ ;EndIf( ′ , (′ ⇑ (︀⌋︀), ( (︀⌋︀⇑′ ));If ¬(′ ) thenFor ′ ∈ (⇑)(, ) dohandlePlaceRecursively( , (⇑)( ′ ), ′ , , );EndForEndIfEndForEndFunction▷ a transition has already been handled▷ new transitiontransitions, and made no more than (⋃︀ ⋃︀ + ⋃︀ ⋃︀) operations.
Recursive calls reduce the number ofplaces which remain unvisited, and do change the order of operations count.Fragments-to-Repair SelectionUsually, fitness is considered as the main criteria for evaluation of model repair results, and toselect broken model fragments. We also focus on this quality of process models. In this thesis, tocheck fitness alignment-based fitness evaluation function is used.Consider an example. Suppose, the model shown in Figure 2.2 does not correspond exactlyto the current behaviour. In particular, the order of events with labels and is changed in theprocess. In contrast to the behaviour of the model, always precedes if both appear in the trace.60Namely, the normative event log contains traces ∐︀, , , , ̃︀ and ∐︀, , , , ̃︀, and there are notraces in which precedes .Then, for each sub-net is constructed corresponding sub-log using simple projection. Thealignment-based fitness evaluation algorithm is applied to pairs of sub-nets and correspondingsub-logs.
Figure 2.6 shows how it is done. The result is that fragment 3 does not perfectly fitthe log, and should be repaired.〈a, d, b, e, f〉〈a, b, c, e, g〉SN5hSN2hSN1sourceaat1t1〈a, d, b, e, f〉〈a, b, c, e, g〉c1t8SN3cSN4cbbt3t3t2t2ddt4t4〈a, d, b, e, f〉〈a, b, c, e, g〉c2〈a, d, b, e, f〉〈a, b, c, e, g〉t8c3eet5t5〈a, d, b, e, f〉〈a, b, c, e, g〉c4〈a, d, b, e, f〉〈a, b, c, e, g〉fSN6ft6t6ggt7t7sink〈a, d, b, e, f〉〈a, b, c, e, g〉Figure 2.6: Fragments-to-repair selectionThe Selection building block is organized exactly as is made in the considered example.
Eachsub-net after decomposition checked using alignment-based fitness evaluation function. Then, thetechnique does not touch perfectly fitting sub-nets, whereas fragments with fitness below 1 aretransferred to The Repair building block responsible for a construction of repaired fragments.Sub-net Repair AlgorithmsSN3'〈d, b〉〈b, c〉ds-startτts1cbt4s2t2t3s3τs-endts2Figure 2.7: This model is discovered using Inductive minerInductive miner [23] is used to repair the sub-nets.
This algorithm guarantees perfect fitnessof a discovered model when executed with particular settings (inductive miner infrequent withzero noise threshold ). It uses sequential (and recursive) inductive inferences to build the socalled process trees, which can be simply translated into well-structured workflow nets. Anotherdiscovery algorithm, which is also used in this chapter is ILP (Integer Linear Programming)-basedalgorithm [24]. This algorithm guarantees perfect fitness with particular settings like Inductive61miner. Figure 2.7 shows a workflow net 3′ discovered using Inductive miner for the sub-logrelated to the fragment 3 that has been selected previously.Composition, Result, DiscussionThe last step is a composition of repaired model.
The fusion of all untouched sub-netsSN1 , SN2 , SN4 , SN5 , SN6 and the re-discovered sub-net 3′ gives the net shown in Figure 2.8.The replaced part of the model is highlighted.ht8asourcec1τt3bt2s3ts1s-startdect1τft6c3t5gc4sinkt7s-endts2s2t4Figure 2.8: Petri net after transition fusionThis model perfectly fits the event log with traces ∐︀, , , , ̃︀ and ∐︀, , , , ̃︀. The repairedmodel is not a workflow net, since it has additional source (-start) and sink (-end ) places, whichwere created by the discovery algorithm.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
