韓兆剛，鞏 朋，張 莉，呂方興

(1.北京航空航天大學(xué)軟件工程研究所，北京100191;2.菏澤學(xué)院計算機與信息工程系，山東荷澤274015)

過程模型［1］中的反模式是指“導(dǎo)致過程模型錯誤的典型設(shè)計缺陷”［2］，它是評估過程模型正確性的有效手段。過程模型反模式以控制流反模式(控制結(jié)構(gòu)方面的反模式)最為常見［2］。文獻［3］對過程模型進行化簡并根據(jù)化簡結(jié)果判斷過程模型中是否存在死鎖或乏同步，但該方法無法定位反模式。文獻［4］使用編譯技術(shù)中的控制流塊分析技術(shù)［5］分析過程模型并利用啟發(fā)式方法檢測并定位控制流反模式，但該方法只支持一些既定的控制流反模式，擴展性不足。文獻［6］利用 BPMN-Q［7］定義并查詢BPMN模型中的常見控制流反模式，該方法允許用戶自定義反模式，但它的效率較低，而且不支持BPMN以外的建模語言。為了提高過程模型的控制流反模式檢測的實用性和靈活性，筆者提出一種過程模型中控制流反模式的定義和檢測方法。

1 過程模型預(yù)處理

為了支持不同的過程建模語言，提取過程模型的控制流結(jié)構(gòu)，并將其轉(zhuǎn)化為過程建模語言無關(guān)的工作流圖［3］。為了方便，使用 BPMN［8］的建模符號來表示工作流圖中的元素(圖1)，并在下文中使用ANDSplit、ANDJoin、XORSplit和 XORJoin 來表示工作流圖中的并行分支、同步合并、排他選擇和簡單合并。

圖1 工作流圖中的基本元素Fig.1 Basic notations in workflow graph

使用文獻［2］提出的過程結(jié)構(gòu)樹來分析過程模型的控制流結(jié)構(gòu)。過程結(jié)構(gòu)樹由工作流圖中的規(guī)則單入口單出口過程塊和節(jié)點構(gòu)成。通過環(huán)路等價算法［4］對工作流圖進行處理，可以在線性時間得到工作流圖中的規(guī)則單入口單出口過程塊(除非特殊說明，過程塊均為規(guī)則單入口單出口過程塊)。稱該處理過程為工作流圖歸約。

圖2給出了一個示例工作流圖，過程從起始節(jié)點start出發(fā)到達g1，然后并行地執(zhí)行g(shù)1的兩個后繼分支。其中一個分支串行地執(zhí)行a1、a2和a3這幾個活動，另外一個分支則執(zhí)行由g2、a4和g3構(gòu)成的循環(huán)。接下來這兩個分支在g4進行匯合，最后過程到達終止節(jié)點end，該過程結(jié)束。值得注意的是，由于使用并行分支作為循環(huán)出口，過程塊C中的g2和g3構(gòu)成了無窮循環(huán)。圖中的虛線框表示對工作流圖實施規(guī)約后得到的不同過程塊。

圖2 示例工作流圖及其歸約結(jié)果Fig.2 Sample workflow graph and its reduction result

對于給定過程塊F，稱F的母過程塊為包含F(xiàn)的最小過程塊F'，并稱F為F'的子過程塊。把過程塊的子過程塊替換為一個活動節(jié)點不會影響該過程塊的正確性［6］。以圖2為例，過程塊A是過程塊B、C的母過程塊，而過程塊B、C均為A的子過程塊。處理過程塊A時，可以把過程塊B、C作為一個活動節(jié)點來處理，而無需考慮其內(nèi)部結(jié)構(gòu)，這可以顯著地提升處理速度。

文獻［4］證明了規(guī)則單入口單出口過程塊之間只存在嵌套和不相交這兩種關(guān)系，因此工作流圖中的過程塊可以構(gòu)成一個樹形結(jié)構(gòu)，這個樹形結(jié)構(gòu)就是過程結(jié)構(gòu)樹［9］。圖3給出了圖2所對應(yīng)的過程結(jié)構(gòu)樹。

圖3 示例工作流圖對應(yīng)的過程結(jié)構(gòu)樹Fig.3 Corresponding process structure tree of sample workflow graph

過程結(jié)構(gòu)樹中的葉子節(jié)點對應(yīng)于工作流圖的節(jié)點，非葉子節(jié)點對應(yīng)于與工作流圖中的過程塊。以圖2的工作流圖和圖3的過程結(jié)構(gòu)樹之間的關(guān)系為例，圖3中的根節(jié)點A對應(yīng)圖2中的過程塊A，圖3中的葉子節(jié)點g1和g4對應(yīng)于圖2中的節(jié)點g1和g4。工作流圖中的控制流信息則保存在過程結(jié)構(gòu)樹的葉子節(jié)點中。

由于過程結(jié)構(gòu)樹中的節(jié)點和工作流圖中的元素之間存在這種映射，并且工作流圖總可以轉(zhuǎn)換為與之對應(yīng)的過程結(jié)構(gòu)樹［10］，因此可以通過分析過程結(jié)構(gòu)樹來分析過程模型的控制流結(jié)構(gòu)。

2 反模式描述語言CAPDL

為了描述控制流反模式，設(shè)計了控制流反模式描述語言CAPDL。

2.1 CAPDL的設(shè)計思路

控制流反模式是一類導(dǎo)致過程模型異常的特殊控制流結(jié)構(gòu)，描述控制流反模式也就是描述其對應(yīng)的控制流結(jié)構(gòu)。由于控制流結(jié)構(gòu)由活動、分支、合并等模型元素構(gòu)成，因此可以利用模型元素的屬性來描述過程模型中的控制流結(jié)構(gòu)。過程模型中的控制流結(jié)構(gòu)可以分為兩類:簡單控制流結(jié)構(gòu)和復(fù)合控制流結(jié)構(gòu)。簡單控制流結(jié)構(gòu)對應(yīng)于節(jié)點;復(fù)合控制流結(jié)構(gòu)對應(yīng)于過程塊。對于簡單控制流結(jié)構(gòu)，利用模型節(jié)點的屬性就可以對其進行描述;對于復(fù)合控制流結(jié)構(gòu)，則需要利用過程塊內(nèi)部的節(jié)點信息對其進行描述?；谶@個思路，本文設(shè)計了控制流反模式描述語言CAPDL。

2.2 CAPDL的核心概念和元模型

CAPDL的基本概念是謂詞，根據(jù)謂詞的目標(biāo)類型，謂詞可以分為屬性謂詞和節(jié)點謂詞:屬性謂詞應(yīng)用于節(jié)點上的屬性;節(jié)點謂詞應(yīng)用于過程塊中的節(jié)點。表1給出了一些謂詞的使用示例。

表1 CAPDL的謂詞示例Table 1 Examples of predicates in CAPDL

比謂詞高一級的概念是規(guī)則，規(guī)則由一系列謂詞組成。規(guī)則根據(jù)其目標(biāo)類型可以分為節(jié)點規(guī)則和塊規(guī)則:節(jié)點規(guī)則由若干屬性謂詞組成，用于描述過程模型中的模型節(jié)點;塊規(guī)則由若干節(jié)點謂詞組成，用于描述過程模型中的過程塊。規(guī)則的使用示例見表2。

?

比規(guī)則高一級的概念是反模式。由于過程模型中的控制流反模式可能具有多種實現(xiàn)形式［11］，因此一個反模式由一個到多個規(guī)則組成。對于指定的反模式，只要過程塊或模型節(jié)點滿足該反模式規(guī)則集合中的一條規(guī)則，就稱該過程塊或模型節(jié)點滿足該反模式。

為了復(fù)用已有的反模式定義和規(guī)則定義，CAPDL中引入了模塊的概念。模塊可以包含一個到多個規(guī)則或反模式;模塊可以通過導(dǎo)入其他模塊來引用已定義的規(guī)則或反模式。以“錯誤循環(huán)”反模式為例，它由InfiniteLoop規(guī)則和DeadLoop規(guī)則組成，并引用了BasicPatterns模塊中的節(jié)點規(guī)則來定義自己的謂詞。具體如下:

import BasicPatterns\引用BasicPatterns模塊

antipattern Badloop:\定義Badloop反模式

rule InfiniteLoop on block:\定義InfiniteLoop規(guī)則

start with BasicPatterns.XORJoin\引用 BasicPatterns模塊中的節(jié)點規(guī)則

end with BasicPatterns.ANDSplit

rule DeadLoop on block:\定義DeadLoop規(guī)則

start with BasicPatterns.ANDJoin

end with BasicPatterns.XORSplit

通過謂詞、規(guī)則、反模式、模塊等概念，CAPDL提供了一種簡潔的控制流反模式定義方法。圖4給出了CAPDL的元模型。

圖4 CAPDL元模型Fig.4 CAPDL meta-model

3 控制流反模式查詢算法

利用預(yù)處理過程中得到的過程結(jié)構(gòu)樹，以及控制流反模式的CAPDL定義，可以在過程結(jié)構(gòu)樹上查詢滿足目標(biāo)反模式的過程模型節(jié)點和過程塊。

3.1 查詢算法

基于CAPDL的控制流反模式查詢算法步驟如下:

(1)讀取工作流圖對應(yīng)的過程結(jié)構(gòu)樹PST，并初始化PST上每個葉子節(jié)點的謂詞集合。

(2)分析待查詢反模式的CAPDL定義，對其中節(jié)點規(guī)則NodeRule中的屬性謂詞和塊規(guī)則Block-Rule中的塊謂詞進行等價謂詞合并，并將去重后的謂詞保存在屬性謂詞集合和塊謂詞集合中。

(3)遍歷 PST上的葉子節(jié)點 LeafNode，記錄LeafNode所滿足的屬性謂詞并將其添加至節(jié)點的謂詞集合，并根據(jù)該節(jié)點滿足的謂詞判斷其所屬的NodeRule。

(4)遍歷 PST的非葉子節(jié)點 Non-LeafNode，并根據(jù)該節(jié)點滿足的塊謂詞判斷其所屬的BlockRule。

(5)根據(jù)PST節(jié)點所屬的 NodeRule或Block-Rule判斷其所屬的控制流反模式，并記錄其信息。

3.2 反模式查找過程

當(dāng)使用二叉鏈表作為存儲結(jié)構(gòu)時，過程結(jié)構(gòu)樹的后序遍歷可借用二叉樹的先序遍歷和中序遍歷的算法實現(xiàn)，由于二叉樹的遍歷算法的時間復(fù)雜度與節(jié)點數(shù)存在線性關(guān)系，因此過程結(jié)構(gòu)樹上的反模式檢測算法的時間復(fù)雜度也與節(jié)點數(shù)存在線性關(guān)系。

以檢測圖2的示例工作流圖中的錯誤循環(huán)為例，介紹基于CAPDL的控制流反模式查詢過程。圖2的工作流圖可以使用圖3中的過程結(jié)構(gòu)樹表示。

(1)首先讀取圖3中的過程結(jié)構(gòu)樹，并初始化過程結(jié)構(gòu)樹中每個葉子節(jié)點的謂詞集合。以葉子節(jié)點a1、a2、a3、a4為例，它們的謂詞集合均被初始化為:inputedgescount=1;outputedgescount=1。

(2)為了提高查詢效率，本文對CAPDL代碼中重復(fù)的謂詞/規(guī)則進行了合并處理，從而保證同樣的謂詞/規(guī)則不會查詢多次。以“錯誤循環(huán)”反模式的CAPDL定義為例，謂詞inputedgescount=1在規(guī)則Sequential和規(guī)則ANDSplit均有出現(xiàn)(這些規(guī)則定義在模塊BasicPatterns中)。

(3)通過遍歷過程結(jié)構(gòu)樹上的葉子節(jié)點，判斷其滿足的屬性謂詞，可以得到它們所滿足的節(jié)點規(guī)則。以圖3中的葉子節(jié)點g2為例，由于謂詞type=XOR、inputedgescount＞1和 outputedgescount=1在g2上均為真，因此g2滿足規(guī)則XORJoin。同理a1、a2、a3、a4 滿足規(guī)則 Sequential，g3 滿足規(guī)則 ANDSplit。節(jié)點規(guī)則的結(jié)果見圖5，圖中所有葉子節(jié)點滿足的節(jié)點規(guī)則均由節(jié)點規(guī)則查詢得到。

(4)通過遍歷過程結(jié)構(gòu)樹上的非葉子節(jié)點，并利用其子節(jié)點滿足的節(jié)點規(guī)則來判斷其滿足的節(jié)點謂詞，可以得到它們滿足的塊規(guī)則。以過程塊C為例，由于C的起始節(jié)點g2滿足規(guī)則XORJoin，終止節(jié)點g3滿足規(guī)則ANDSplit，因此C滿足規(guī)則InfiniteLoop。塊查詢的結(jié)果見圖5，圖中過程塊C滿足規(guī)則InfiniteLoop這一結(jié)果由塊規(guī)則查詢得到。

(5)根據(jù)過程結(jié)構(gòu)樹中節(jié)點的節(jié)點規(guī)則和塊規(guī)則，得到過程模型的控制流反模式信息:由于滿足“InfiniteLoop”規(guī)則，工作流圖中的過程塊C構(gòu)成了一個錯誤循環(huán)。

圖5 節(jié)點規(guī)則和塊規(guī)則查詢結(jié)果Fig.5 Querying results of node rules ＆ block rules

4 試驗結(jié)果分析

為了驗證本文方法的有效性，對215個實際過程模型進行控制流反模式檢測試驗，試驗以文獻［2］提出的4種常見控制流反模式為檢測目標(biāo)。這4種反模式分別是:異或分支(XORSplit)和同步合并(ANDJoin)的組合(會產(chǎn)生死鎖錯誤)、并行分支(ANDSplit)和簡單合并(XORJoin)的組合(會產(chǎn)生乏同步錯誤)、同步合并(ANDJoin)作為循環(huán)入口(會產(chǎn)生死鎖錯誤)和并行分支(ANDSplit)作為循環(huán)出口(會產(chǎn)生無窮循環(huán)錯誤)。這些控制流反模式的詳細(xì)信息參見文獻［2］。使用CAPDL定義了這些反模式，并基于這些反模式的CAPDL定義，對ILog建模工具(http://www-01.ibm.com/software/integration/visualization/java/)繪制的215個 BPMN過程模型進行了控制流反模式檢測。圖6給出了這些模型的規(guī)模信息。

圖6 模型的規(guī)模信息Fig.6 Model scale information

檢測程序運行在一臺裝有4G內(nèi)存和2.93 GHz的雙核Intel處理器的臺式機上，檢測環(huán)境為Windows 7 SP1。檢測過程分為預(yù)處理過程和反模式檢測過程。圖7給出了檢測過程所耗時間和模型節(jié)點數(shù)的關(guān)系，其中反模式檢測時間和模型節(jié)點數(shù)呈預(yù)期的線性關(guān)系;預(yù)處理時間與模型節(jié)點數(shù)也呈現(xiàn)線性關(guān)系，這印證了文獻［4］中的論斷:通過環(huán)路等價算法對工作流圖進行處理，可以在線性時間得到與之對應(yīng)的過程結(jié)構(gòu)樹。

圖7 檢測時間和模型節(jié)點數(shù)的對應(yīng)關(guān)系Fig.7 Relationship between detection time and model edge number

與文獻［6］提出的利用BPMN-Q檢測控制流反模式的方法相比，本文的檢測方法具有較快的速度。對相近規(guī)模的過程模型檢測同樣的控制流反模式，本文的平均檢測時間為0.33 s，文獻［6］的平均檢測時間為1.9～2.1 s。表3給出了具體的比較數(shù)據(jù)(本文的方法會對四種控制流反模式進行同時檢測，這里計入的是檢測總時間，所以檢測時間相同)。

表3 兩種反模式檢測方法的平均查詢時間比較Table 3 Average querying time comparison of two anti-pattern detection approaches

文獻［6］中的模式查詢方法受系統(tǒng)架構(gòu)限制，每查詢一個控制流模式就需要遍歷一次過程模型，因此在查詢多個控制流模式時需要遍歷過程模型多次，從而造成相當(dāng)?shù)男阅軗p耗。本文方法通過對過程模型進行預(yù)處理，將過程模型轉(zhuǎn)化為過程結(jié)構(gòu)樹，并對控制流反模式的CPDL描述進行等價謂詞合并以減少不必要的查詢判斷。從而在查詢多個控制流反模式時只需一次預(yù)處理和四次過程結(jié)構(gòu)樹遍歷，從而顯著提升了控制流模式查找的效率。

文獻［6］采用圖匹配的方式進行控制流模式查詢。每一次查詢均需要遍歷整個過程模型;本文利用文獻［9］的過程結(jié)構(gòu)樹，把對指定模式的查詢限制在過程模型的子過程塊中，從而減少了查詢時間。

筆者選取了215個過程模型中的100個模型進行人工檢測，然后與檢測結(jié)果進行比較。結(jié)果見表4?？梢钥闯?，出現(xiàn)最多的控制流反模式是XORSplit和ANDJoin的組合(15次)，其次是 XORJoin和ANDSplit的組合和ANDJoin作為循環(huán)入口(各出現(xiàn)6次)，同文獻［6］中的過程模型中常見控制流反模式統(tǒng)計結(jié)果相一致。

表4 反模式檢測結(jié)果Table 4 Anti-pattern detection results

從表4可以看出，檢測過程中存在少數(shù)誤判現(xiàn)象。一般來講，只有基于狀態(tài)空間搜索的正確性驗證方法才能完全避免錯判和漏判。

5 結(jié)束語

為了提高過程模型中控制流反模式檢測的實用性和靈活性，本文提出一種過程模型中控制流反模式的定義和檢測方法。與已有方法相比，該方法既支持不同的過程建模語言，又可以有效地檢測過程模型中用戶自定義的控制流反模式。同時極大地提高了反模式檢測的檢測效率。

［1］ SMITH H，F(xiàn)INGAR P.Business Process Management:The Third Wave［M/OL］.Meghan-Kiffer Press，2003.http://www.bpmi.org/downloads/LIB-2002-08-2.pdf.

［2］ KOEHLER J，VANHATALO J.Process anti-patterns:how to avoid the common traps of business process modeling［J］.IBM WebSphere Developer Technical Journal，2007，10(2):4.

［3］ SADIQ W，ORLOWSKA M E.Analyzing process models using graph reduction techniques［J］.Information Systems，2000，25(2):117-134.

［4］ VANHATALO J，VOLZER H，LEYMANN F.Faster and more focused control-flow analysis for business process models through sese decom-position［M/OL］.Service-O-riented computing-ICSOC 2007， Vienna， Austria.Springer Berlin Heidelberg，2007:43-55.http://link.springer.com/chapter/10.1007/978-3-540-74974-5_4.

［5］ AHO A V，LAM M S，SETHI R，et al.Compilers:principles，techniques，and tools［M/OL］.Pearson/Addison Wesley，2007.http://www.lavoisier.fr/livre/notice.asp?ouvrage=1184227.

［6］ GRUHN V，LAUE R.A heuristic method for detecting problems in business process models［J］.Business Process Management Journal，2010，16(5):806-821.

［7］ AWAD A.BPMN-Q:a language to query business processes［C/OL］//Proceedings of EMISA 2007，Nanjing China.2007:115-128.http://dbis.eprints.uniulm.de/205/1/EMISA-Proceedings-Komplett.pdf#page=117.

［8］ Business Process Modeling Notation(BPMN)Version 2.0［S］.Object Management Group(OMG)，Jun 2010.http://www.omg.org/spec/BPMN/2.0/PDF/.

［9］ VANHATALO J，VOLZER H，KOEHLER J.The refined process structure tree［J］.Data ＆ Knowledge Engineering，2009，68(9):793-818.

［10］ POLYVYANYY A，VANHATALO J，VOLZER H.Simplified computation and generalization of the refined process structure tree［M］//Web Services and Formal Methods.2010，Hoboken，NJ，USA:Springer Berlin Heidelberg，2011:25-41.

［11］ WHITE S A.Process modeling notations and workflow patterns［J］.Workflow Handbook，2004:265-294.

［12］ VAN DER AALST W M P，TER HOFSTEDE A H M.YAWL:yet another workflow language［J］.Information Systems，2005，30(4):245-275.