基于擴展UML圖化簡的過程模型沖突消解

張 婷

（南陽師范學院計算機與信息技術學院，河南南陽473000）

0 引 言

工作流的正確性包括兩個方面的含義:一方面是結構正確性，也就是說業務過程模型是不包含結構沖突的，在沒有錯誤發生時工作流能正常終止；另一方面是語義正確性，即工作流在正常終止時應達到所期望的業務目標［1－2］。其中，結構沖突是導致業務過程模型結構不正確的主要原因。由于業務過程模型中其它錯誤的存在不會增加或減少結構沖突，因而，結構沖突驗證可獨立于其它方面的驗證進行。本文僅對結構沖突進行檢測與消解。

1 結構沖突的特點

結構沖突是指業務過程模型的控制流中出現錯誤，導致工作流在運行時無法正常終止。它是導致過程模型邏輯錯誤的原因，直接影響業務過程的執行是否可以正常終止［3］。常見的結構沖突有:開始/結束節點缺失、死鎖、同步缺失和活鎖［4－5］。分支節點（Split）和結合節點（Join）在組合過程中所具備的特征是過程模型驗證的依據，其具備的特征如下:

（1）若循環結構存在于一個Xor－Split節點和And－Join節點之間，則存在活鎖；

（2）And－Join輸入的前序路徑中，若有來自Xor－Split的輸出，則And－Join處出現死鎖；

（3）Xor－Join輸入的前序路徑中，若有來自And－Split的輸出，則Xor－Join處有同步缺失。

2 擴展的UML活動圖元素

為了使業務建模過程更方便，采用基本的UML活動圖中的圖例描述業務過程［6－7］。為了描述復雜的業務過程，還使用擴展的圖例來建立業務過程模型:

（1）原子活動節點。原子活動節點表示工作流中的一個不可分解的任務。它有且僅有一個輸入路徑和一個輸出路徑。

（2）控制節點。控制節點有4種，分別是多路與分支、多路與結合、多路或分支、多路或結合。多路與分支的輸入被使能時，其所有輸出都會被激活；多路與結合在所有輸入都被使能時，其輸出才會被激活；多路或分支的輸入被使能時，其輸出有且僅有一個被激活；多路或結合的所有輸入中有且僅有一個被使能時，其輸出才能被激活。

（3）活動聚合塊。活動聚合塊Sub是由若干原子活動節點和控制節點組成的聚合結構。

3 基于圖化簡的沖突消解

3.1 沖突消解策略

在一個非結構化的業務過程建模過程中，Split和Join通常沒有嚴格的一對一的關系，從而導致過程模型中的結構錯誤。沖突消解策略是針對結構沖突而制定的。

（1）開始/結束結點缺失:給出提示，用戶可自行添加。

（2）活鎖:活鎖是由于在定義循環結構時，循環的輸出節點為與分支節點而引起的。如圖1（a）中所示，由于B節點是與分支，使得模型的結構中出現活鎖，節點B出錯，則修改方案是將B節點修改為或分支節點，消解的方案如圖1（b）所示。

圖1 活鎖的消解方法

（3）死鎖:如圖2（a）在結構中存在死鎖。這時若修改節點B，將B節點改為或結合節點，修改后的結構如圖2（c）所示；若修改節點A，將A節點改為與分支節點，修改后的結構如圖2（d）所示。由于死鎖的原因是由于一個或分支節點后跟隨一個與結合節點引起的，顯然節點B出錯可能性大，修改節點B的提示會優先。

圖2 死鎖和同步缺失的消解方法

（4）同步缺失:如圖2（b）在結構中存在同步缺失。這時若修改節點B，將B節點改為與結合節點，修改后的結構如圖2（d）所示；若修改節點A，將A節點改為或分支節點，修改后的結構如圖2（c）所示。由于同步缺失一般是由于一個與分支節點后跟隨一個或結合節點引起的，顯然節點B出錯的可能性大，選擇修改節點B的提示會優先。

3.2 沖突消解算法

圖化簡的規則［1，8，9］包含6個類別，分別是:①終端化簡，②順序化簡，③臨近化簡，④閉合化簡，⑤重疊化簡，⑥循環化簡。已知活動圖AD，其基本結構正確。

（1）在AD中應用規則①，去掉活動圖中的開始和終止節點。若化簡結果為空，則AD正確，沖突檢測結束；否則轉步驟（2）。

（2）判斷AD中是否存在循環，若是或分支的循環結構，則按規則⑥進行轉換；若是與分支的循環結構，則存在沖突，沖突檢測結束。

（3）應用規則②將AD中所有活動節點去除。若化簡結果為空，則AD是正確的，沖突檢測結束；否則轉步驟（4）。

（4）在AD中依次應用規則③～規則④，直到AD不能再化簡為止。若化簡結果為空，則AD是正確的，沖突檢測結束；否則轉步驟（5）。

（5）在AD中依次應用規則⑤，直到AD不能再化簡為止。

（6）經過步驟（4）－（5），若活動圖AD未發生變化，則活動圖存在結構沖突，沖突檢測結束，轉入步驟（7）進行沖突消解；否則轉步驟（4）。

（7）根據沖突消解策略進行沖突消解，轉步驟（5）。

4 沖突消解的實現

4.1 結構沖突的描述

結構沖突報告中包含有沖突類型、沖突原因、以及與之有關的節點、業務過程模型部分字段信息；另外也應指出引起沖突的分支或結合節點的詳細信息。表1為結構沖突的描述。其中，錯誤類型有:或分支死鎖（Dead Lock－Source），與結合死鎖（Dead Lock Target），與分支同步缺失（Syn LackSource），或結合同步缺失（Syn Lack Target），活鎖（Lock Target）；節點類型有:分支（Split），結合（Join）；節點邏輯有:與（And），或（Xor）。

表1 結構沖突描述

4.2 沖突消解的實現

圖3為用于業務過程模型結構沖突消解的類圖，圖4為沖突檢測的類圖。

（1）進行數據預處理，讀取活動節點（Act Node）、控制節點（Control Node）、活動塊節點（ActBlock Node），將這些節點保存入一個工作流實例（workflow）中。每個節點類包含兩個屬性:前趨節點集（pre Nodes）和后繼節點集（next Nodes），用來表示節點間弧關系。

（2）對業務過程模型中的各種結構沖突進行檢測。經數據預處理，業務過程模型轉換為workflow的實例。化簡規則的實現都繼承于基類Reduction Rules，在Reduction Rules中定義操作workflow實例的方法。EReduction Rules類只有一個ReductionProcess方法，參數是描述過程模型的文件路徑，返回值是通過屬性FileName來指出保存沖突節點的文件路徑。

（3）業務過程模型類（workflow）的方法handleConflict實現沖突消解的功能。沖突消解是給出UML模型圖的結構沖突及相應的消解方案。沖突消解具體實施時，采用了圖化簡的方式進行沖突檢測，對活動圖邊化簡邊消解。針對某一個沖突，不論選擇哪種消解方案，都會使這個沖突結構滿足化簡規則，可以在圖化簡的過程中被化簡掉。因此，在給出某一個沖突的可選消解方案后，選擇任何一種方案加以實施，其結果是等價的。

4.3 沖突消解算法分析

沖突檢測的限制主要來源于工作流模型復雜度的增長，以及能檢測出的沖突種類。因此，側重于對比可檢的沖突類別、節點個數與參數的變化對檢測時間的影響。在業務過程模型中選取出現結構沖突的實例，作為各結構驗證算法的輸入進行實驗。其中，基于Petri網歸約算法的輸入是轉換為Petri網后的業務過程模型。

（1）分析以下幾種結構驗證算法:基于狀態轉換［3，10］，基于Petri網歸約［11－12］，基于語義推理［13－14］，和基于擴展UML活動圖化簡，結果見表2。可檢測是指對于模型中相應的結構沖突，結構驗證算法能檢測出；可識別是指對于檢測出的沖突，可通過檢測結果分析出沖突的類型。

表2 結構驗證算法的比較

（2）過程模型的節點數目分別為5、10、20、30時，每樣各30個實例，實例中包含死鎖實例、同步缺失實例和活鎖實例各10個。控制節點的入度和出度為小于等于2時，結構驗證算法的運算時間如圖5所示。

圖5 節點數目遞增的沖突檢測平均處理時間

（3）過程模型的節點數為10，控制節點的度為2、3、4時，每樣各有30個實例，實例中包含死鎖實例、同步缺失實例和活鎖實例各10個。結構驗證算法的運算時間如圖6所示。

從表2可以看出，基于語義推理算法只能檢測沖突，不能識別沖突，對于沖突消解不適用。基于狀態轉換算法不能檢測出現循環結構的過程模型，基于語義推理的算法不能檢測出現重疊結構的過程模型，這兩種算法對于復雜的業務過程模型來說是不適用的。

圖6 控制節點度數遞增的沖突檢測平均處理時間

實驗結果表明雖然4種算法的時間復雜度是相同的，但是在節點數目或控制節點度數增加時，UML活動圖化簡的算法的平均處理時間少。基于UML活動圖化簡的算法適用于處理復雜的業務過程模型，在處理過程中采用了化簡的方法降低模型的規模，降低沖突檢測時間。同時它能夠識別出沖突適合于對下一步對沖突進行消解。4種結構驗證算法在時間復雜度相同的情況下，在處理節點數目遞增的業務過程模型時，實際的平均處理時間相差較大。基于狀態轉換算法和基于語義推理算法都沒有使用化簡，不能使模型的規模縮小。基于Petri網歸約的算法雖然使用了化簡，但UML活動圖表示的過程模型轉換為用Petri網表示的過程模型后，實際節點的數目會增加，這弱化了化簡方法的處理能力。在處理節點度數遞增的業務過程模型時，由于基于UML活動圖化簡的算法對控制節點進行了擴展，可以處理度數大于2的控制節點。其它算法對于度數大于2的控制節點只能先轉化為度數不大于2的控制節點后才能運算，增加了節點數目，也使運算時間增長。

5 結束語

為了描述復雜的業務過程模型的邏輯結構，擴展了UML活動圖，定義了業務過程模型中的控制節點，如多路合并和多路分支節點。沖突檢測算法采用圖化簡方法來進行將模型縮減到適當規模，便于進行驗證，并將化簡方法總結為規則集的形式，易于理解和實現。沖突檢測可以對重疊結構和循環結構進行有效地化簡，并能檢測常見的結構沖突。通過分析各種沖突產生的原因，并給出了相應的沖突消解方案。沖突消解方案可以針對各種建模過程中產生的各種結構沖突，給出消解方法，協助操作人員處理沖突。

創新點:擴展UML圖適用于描述大規模復雜應用的業務過程模型，能檢測含有循環和重疊結構的結構沖突，并能指出沖突結構類型，給出相應沖突消解方案，協助處理沖突。

［1］ZHOU Jian－tao，SHI Mei－lin，YE Xin－ming.Formal verification techniques in workflow process modeling［J］.Computer Research and Development，2005，42（1）:1－2（in Chinese）.［周建濤，史美林，葉新銘.工作流過程建模中形式化驗證技術［J］.計算機研究與發展，2005，42（1）:1－2.］

［2］Cai J，Zhao W，Zhang S K，et al.Correctness verification of synchronization based workflow model［C］.Beijing:Proceeding of the IEEE International Conference on e－Bossiness Engineering，2005:527－530.

［3］Fode T，Karim B，Khalid B.An efficient algorithm for workflow graph structural verification［G］.Lecture Notes In Computer Science 5331:On the Move to Meaningful Internet Systems，2008:392－408.

［4］ZHANG Min，GUO Yu－bin.Survey for correctness problem of workflow system［J］.Application Research of Computers，2009，26（5）:1645－1648（in Chinese）.［張民，郭玉彬.工作流正確性問題綜述［J］.計算機應用研究，2009，26（5）:1645－1648.］

［5］CUI Li－zhen，WANG Hai－yang.Verification method for workflow model correctness［J］.System simulations，2008，20（8）:1950－1968（in Chinese）.［崔立真，王海洋.一種工作流模型正確性驗證方法［J］.系統仿真學報，2008，20（8）:1950－1968.］

［6］ZHAO He－ji，ZHANG Li－chun.Workflow modeling method and design based on UML activity diagram［J］.Computer Applications and Software，2004，21（8）:44－45（in Chinese）.［趙合計，張立春.UML活動圖支持下的工作流建模方法與設計［J］.計算機應用與軟件，2004，21（8）:44－45.］

［7］LIU Yi，ZHANG Zi－gang，ZHANG Kan.Overview of workflow models［J］.Computer Engineering and Design，2007，28（2）:449－450（in Chinese）.［劉怡，張子剛，張戡.工作流模型研究述評［J］.計算機工程與設計，2007，28（2）:449－450.］

［8］Li Ye－bai，Mao Fu－qi.Research of the verification in workflow process modeling on the application of Petri nets［C］.International Conference on e－Education，e－Business，e－Management and e－Learning，2010:21－24.

［9］Nazia Leyla，Ahmed Shah Mashiyat，Hao Wang，et al.Towards workflow verification［C］.Proceedings of the Conference of the Center for Advanced Studies on Collaborative Research，2010:255－260.

［10］Zhao Lei，Qian Leqiu，Zhao Wenyun.State－space based verification of workflow model［J］.Computer Engineering and Application，2004，40（10）:220－222.

［11］XU Jing－ming，DU Bao－zhu.Workflow process model structure verification based on Petri net reduction techniques［J］.Computer Technology and Development，2009，19（6）:51－57（in Chinese）.［徐晶明，杜寶珠.基于Petri網化簡技術的工作流過程模型結構驗證［J］.計算機技術與發展，2009，19（6）:51－57.］

［12］Wang Bao－yi，Zhang Shao－min，Xue Qiao－li.The analysis on grid workflow’s deadlock by Petri nets［C］.World Congress on Intelligent Control and Automation，2008:5428－5431.

［13］Ling Hong，Zhao Jiang－bou.Research on workflow process structure verification［C］.IEEE International Conference on e－Business Engineering，2005:160－166.

［14］LING Hong，ZHOU Jiang－bo，XU Zheng－chuan.Semantic deduction－based workflow structure verification method［J］.Computer Integrated Manufacturing Systems，2006，12（6）:893－898（in Chinese）.［凌鴻，周江波，胥正川.基于語義推理的工作流結構驗證方法［J］.計算機集成制造系統，2006，12（6）:893－898.］