Диссертация (1137084), страница 15
Текст из файла (страница 15)
The model contains two tokens in initial marking: one inplace and another one in place -start. In the final marking of this net two places containa token: place and place -end.Note that this model can be easily transformed into an equivalent workflow net by addinginvisible (silent) start and finish transitions and artificial source and sink places.
Figure 2.9 showshow this can be done.hτsourceats3 s-start-1t1c1c3bt2τs-startdt4fet6t5c4gτs-end-1 ts4t7cts1t8t3s2s3τs-endts2Figure 2.9: Workflow net with artificial and placessink62In this model, and places are renamed into -start-1 and -end-1, artificial silenttransitions 3 and 4 are added as well as new and places. This model is a workflownet.Note that places -start and -end significantly restrict the behaviour of the repaired modelin comparison with the initial model (see Figure 2.2). In particular, they form a deadlock, whichprohibits the execution of the loop going through the transition 8 (labelled with h).
Althoughthis does not contradict the event log, based on which the model was repaired, nevertheless, canlower the model value.Therefore, places -start and -end are removed as redundant to recover this problem.Figure 2.10 shows the model after this procedure.hft8asourcet1cbt2c1s3t3ττts1s2t6ec3t5c4gsinkt7ts2dt4Figure 2.10: Petri net without redundant placesSuch a procedure does not change fitness between the model and the event log. Furthermore,this operation does not affect the overall repair scheme.
Firstly, the fitness does not decreasebecause the possible model behaviour is expanded, when places are removed. Secondly, theprocedure does not touch the set of borderline transitions as it deals only with places. Thus,a modular repair technique with this procedure satisfy the perfect fitness repair conditions (seeTheorem 3).Howbeit, this procedure greatly increases the number of possible model runs.
Indeed, nowtransitions 4 and 1 may put tokens to places 2 and 3 at each step of model execution, whereastransition 2 is able to remove a token from place 3 . Thus, a precision of a repaired Petri netmay decrease. In order to cope with this shortcoming of the basic repair technique, we proposethe improved repair algorithm, which is described in the next Section 2.4.2.4Improved Algorithm for Local Process Model RepairThis section presents the improved algorithm for modular repair that makes more preciserepaired models.Consider the construction of a model to replace an unfitting sub-net in detail. Primarily, thetechnique maximally decomposes the model from Figure 2.2.
Figure 2.11 recalls the result, whichconsists of six fragments.63SN5hSN2hSN1sourceaat1t1c1t8SN3cSN4cbbt3t3t2t2c2ddt4t4t8c3eet5t5c4fSN6ft6t6ggt7t7sinkFigure 2.11: Maximal decomposition of the model from Figure 2.2Then the fitness between each sub-net and the corresponding log fragment is calculated. Itturns out that only the fragment 3 does not fit related sub-log. This fragment is replaced bythe model discovered using the inductive algorithm (see Fig. 2.7). Then all fragments are composedinto the repaired model which is shown in Figure 2.8.With close examination of the example in Figure 2.11, it becomes clear that during the repairthe algorithm also works with boundary transitions of repaired fragment (2 , 3 , and 4 ), over whichthe fragments were divided.
As a result, causal relations on boundary transitions were violated,and this led to a less precise final model.EnlargementWe propose to enlarge each fragment-to-repair as a solution to this problem. Such anenlargement should be done according to the certain rule. For each fragment that requires areplacement, it is suggested to attach all adjacent fragments that perfectly fit their sub-logs. Asa result of this operation, it can guaranteed that outer border of an enlarged fragment-to-repairdoes not affected during the discovery of a new sub-net.0−1++1+++Indeed, let → . . .
→ → . . . → ++1 → . . . → be a sequence of transition firingsin a workflow net, going through a large fragment, where transitions , +1 , . . . , +−1 , + belongto the fragment, and + are boundary transitions, and +1 , . . . , +−1 are internal transitions.If we attach all neighbour fragments to the changed one, the transitions and + will belong toone of the neighbour perfectly fitting fragments in the initial decomposition. Therefore, fragments−1+++1of firing sequences .
. . → → . . . and . . . → ++1 → . . . also perfectly fit the event log andthey will not be changed by the repair algorithm.Figure 2.12 demonstrates attaching neighbours to the fragment 3 in the example net. Thissub-net has two neighbours, namely 2 and 4 , to be attached.Definition 10 (Neighbour Sub-nets in Decomposition). Let N ∈ be a fragment (sub-net) insome decomposition of a workflow net .
Neighbour fragments of N are all fragments whichhave common transitions with it (i.e. transitions with the equivalent labels). The set of neighboursof N is defined as follows: (N ) = {N ⋃︀ N ∈ ∧ ∩ ≠ ∅}.We define an enlarged fragment (N ) for N as a fragment obtained by attaching to N allits neighbours, i.e. (N ) = N ∪ (N ).64W(SN3) SN5hSN2hsourceSN3t8SN1aat1t1c1bbt2t2c2cSN4ct3t3ddt4t4t8c3W(SN3)cSN1sourceaat1t1t3bc1t2c2dc3et5t5c4SN6ft6t6ggt7t7sinkSN5hht8t8eet5t5t4efc4fSN6ft6t6ggt7t7sinkFigure 2.12: Neighbours are attached to the sub-netThe procedure of fragment enlargement is applied when there are more than one unfittingfragment in model decomposition, as follows.Definition 11 (Sub-net Enlargement Procedure).
Let = {N 1 , . . . ,N n } be a decomposition of aworkflow net , and = ∪ , where is a set of unfitting net fragments, and is a set ofother fragments. Obviously, ∩ = ∅. The fragment enlargement procedure consists of thefollowing steps:1.
Each fragment from is extended by attaching its neighbours: ∀N ∈ : = (N ), = (N ); = ⋃ is a set of all enlarged fragments, and = ⋃ is a set of allfragments which were affected by the procedure, where = 1, 2, . . . , ; note that fragments canhave common neighbours;2. All affected fragments are removed from the initial decomposition = ∖ ;3. The new decomposition includes enlarged fragments: N= ∪ .It is shown in the remainder, that the result of a fragment enlargement is a valid decomposition.Theorem 4 (Sub-net Enlargement Preserves Decomposition Validity). Let N = {N 1 , . .
. ,N n } ∈(N ) be a valid decomposition of a net . Let Nbe an enlarged decomposition in which twofragments are combined, that is ∃, such that 1 ≤ < ≤ and N= { ∪ } ∪ N ∖ { , }.Then Nis a valid decomposition, i.e.
N∈ (N ).Proof. We need to show, that all five properties of valid decomposition are valid for N={Nw1 , . . . ,Nwn−1 }.(1) All subnets N 1 , . . . ,N n are labeled Petri nets, ∪ is also a labeled Petri net by thedefinition of net union. There is one fragment in a final decomposition, which was constructedby combining two initial fragments, i.e. ∃ such that 1 ≤ ≤ − 1 and Nwk = ∪ . All other65fragments were not changed, i.e. ∀ such that 1 ≤ ≤ − 1 and ≠ : ∃ℎ such that 1 ≤ ℎ ≤ andNwf = ℎ .(2) For all subnets, except the two combined, nothing has changed. When we combine and , we have ( ∪ ∪ ) = ( ) ∪ ( ) by definition, and ∪ () = () if ∈ ( ), or() = () if ∈ ( ) ∖ ( ).
Thus, = ↾ for any 1 ≤ ≤ − 1.(3) Each place remains in its fragment ∩ = ∅ for 1 ≤ < ≤ − 1, since in the initialdecomposition each place belongs to exactly one fragment, and the set of places for the combinedfragments is ∪ , < .(4) Transitions at the fragment boundaries are visible and have unique labels. Indeed, we onlydecrease the set of boundary transitions, when combine the fragments,{ ⋃︀ ∈ ∩ , 1 ≤ < ≤ − 1} ⊂ { ⋃︀ ∈ ℎ ∩ , 1 ≤ ℎ < ≤ } ⊆ (N ).(5) And finally, directly from the definition of the fragment combining we get: N = ⋃1≤ℎ≤ N ℎ =ff⋃1≤ℎ< N ℎ ∪ ⋃<ℎ< N ℎ ∪ ⋃<ℎ≤ N ℎ ∪ N ∪ N = ⋃1≤ < Nw ∪ ⋃< ≤−1 Nw ∪ Nwk .Theorem 4 states that when two fragments are merged, the new decomposition remains valid.Any number of fragments can be merged by sequential merge of pairs of fragments.
At each stepof such a procedure the theorem can be applied. Hence, the decomposition with any number ofenlarged fragments is valid. This result allows us to propose the improved modular repair algorithmdescribed in the remainder.Improved Modular Repair AlgorithmThe basic (naive) repair algorithm can be enhanced by adding one intermediate step. Thetechnique decomposes the initial model, finds unfitting fragments, and enlarges these fragmentsaccording to the procedure described above. A modified decomposition contains larger sub-nets.Then unfitting fragments are replaced using a process discovery algorithm as earlier. We call thisprocedure the improved modular repair algorithm.The improved general scheme of the modular repair technique is shown in Figure 2.13.
One maysee the new Enlargement building block highlighted with red. This block is embedded betweenselection of fragments-to-repair and the repair block itself. The fragment enlargement procedureis considered as an integral part of the modular repair. As it was shown above, this procedurekeeps decomposition valid. Hence, perfect fitness repair conditions (see Theorem 3) are satisfied.Consider an example of applying the improved algorithm. Assume, that we want to repair themodel shown in Figure 2.2 according to the event log which consists of the following traces:∐︀, , , , ̃︀,∐︀, , , , ̃︀,∐︀, , , , ℎ, , , , ̃︀,∐︀, , , , ̃︀.The fragment 3 of the model’s maximal decomposition — which is shown in Figure 2.7 — isneed to be replaced.
Figure 2.12 shows how neighbour fragments 2 and 4 are attached to66EventLogInputInitialWorkflow netDecompositionProjectionSelectionConformingSub-netsSub-netsSub-logsNon-conformingSub-netsSub-logs forNon-conformingSub-netsConformingSub-netsEnlargementCompositionEnlargedSub-netsRepairCorrectedSub-netsEvaluationEvaluationResultOutputCorrectedWorkflow netFigure 2.13: Modular repair with the enlargement stepthis sub-net. Then, we project the event log and obtain the sub-log corresponding to the enlargedfragment (3 )′ , trace of which are as follows:∐︀, , , ̃︀,∐︀, , , ̃︀,∐︀, , , , ℎ, , , ̃︀,∐︀, , , ̃︀.Figure 2.14 shows the model discovered from this sub-log using the inductive discovery algorithm.Figure 2.15 shows the model, obtained by combining all fragments.
It is easy to verify thatthis model perfectly fits the event log used for repair. Moreover, the model reflects the event logmore precisely than the model, which has been discovered without fragment enlargement.Note that places -start and -end, which were added by inductive discovery algorithm, canbe also removed from the model.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
