蔡 敏 汪世義 韓俊波

（巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院，安徽 合肥 238000）

1 引言

Aalst將工作流建模理論與Petri網(wǎng)理論相結(jié)合，提出了工作流網(wǎng)模型，同時(shí)還定義了一個(gè)正確的工作流所應(yīng)該滿足的soundness屬性[1]。如今工作流網(wǎng)已成為使用最為廣泛的業(yè)務(wù)流程形式化模型[2]。工作流網(wǎng)中活動之間的序關(guān)系包含了大量的有用的信息，在許多方面有著重要應(yīng)用，如過程挖掘[3]、模型一致性度量[4]、業(yè)務(wù)流程執(zhí)行監(jiān)控[5]等。文獻(xiàn)[4]討論了sound自由選擇工作流系統(tǒng)中序關(guān)系的可獲取性。然而真實(shí)業(yè)務(wù)模型往往表現(xiàn)出非自由選擇特性，要獲取這類系統(tǒng)中的序關(guān)系比較困難。

利用T-不變量對復(fù)雜結(jié)構(gòu)的工作流網(wǎng)進(jìn)行分解，得到一組相對簡單的子結(jié)構(gòu)，再對每個(gè)子結(jié)構(gòu)逐個(gè)進(jìn)行分析，可以達(dá)到分而治之的目的。文獻(xiàn)[6]對sound良構(gòu)工作流網(wǎng)進(jìn)行了分解；文獻(xiàn)[7]利用T-不變量發(fā)現(xiàn)好路徑；文獻(xiàn)[8]將一個(gè)工作流網(wǎng)分解成一組子網(wǎng)，再轉(zhuǎn)化為PERT圖，進(jìn)而分析過程模型的進(jìn)度和工期。本文利用T-不變量分解法將sound自由選擇系統(tǒng)中序關(guān)系可獲取性推廣到一類非自由選擇系統(tǒng)中，指出了文獻(xiàn)[8]中有關(guān)結(jié)論存在的錯(cuò)誤并分析了錯(cuò)誤的原因。

2 基本概念和術(shù)語

本節(jié)給出本文涉及的一些主要概念和表示符號，詳細(xì)信息可參考文獻(xiàn)[1][3][8]。

定義 1 三元組 N＝（P，T；F） 是一個(gè) Petri網(wǎng)，當(dāng)且僅當(dāng)P和T分別是庫所和變遷的有限集合 P∪T≠?，P∩T=?，F(xiàn)?（P × T）∪（T × P），是弧的集合，即流關(guān)系。F+是流關(guān)系的傳遞閉包。

定義 2 Petri網(wǎng) PN=（P，T；F） 是一個(gè)工作流網(wǎng)，當(dāng)且僅當(dāng)：

（1）PN 有且僅有一個(gè)起始庫所 i，即·i=?；

（2）PN 有且僅有一個(gè)終止庫所 o，即 o·=?；

（3）如果在 PN 上增加一個(gè)變遷 t*，使（t*）·=｛i｝，·（t*）=｛o｝所得到的擴(kuò)展網(wǎng)是強(qiáng)連接的。

在工作流網(wǎng)中，一個(gè)變遷可能是一個(gè)活動，也可能僅僅表示AND-split或AND-join結(jié)構(gòu)。庫所對應(yīng)變遷的前件與后件，也可能僅表示OR-split或OR-join結(jié)構(gòu)。一個(gè)工作流系統(tǒng)由一個(gè)工作流網(wǎng)和它的初始標(biāo)識[i]給出，記作 S=（PN，[i]）。

定義3 工作流系統(tǒng)S=（PN，[i]）滿足soundness屬性，當(dāng)且僅當(dāng)：

（1）S是安全的。即對任意可達(dá)標(biāo)識M和庫所 p，都有 M（P）≤1；

（2）從任意可達(dá)標(biāo)識M出發(fā)，都可到達(dá)標(biāo)識[o]；

（3）若存在可達(dá)標(biāo)識，M≥[o]?M=[o]；

（4）無死變遷。

定義 4 PN=（P，T；F）設(shè)是一個(gè)網(wǎng)， C 是 PN的關(guān)聯(lián)矩陣，如果非平凡的非負(fù)整數(shù)向量X滿足CTX=0，則稱X為PN的一個(gè)T-不變量。T-不變量X的支集記作對于一個(gè)T-不變量Jk，如果不存在其它T-不變量Jx?Jk，則稱Jk為最小T-不變量。

定義 5 設(shè) PN1=（P1，T1，F(xiàn)1）與 PN=（P，T；F）是兩個(gè)網(wǎng)，稱PN1是PN的一個(gè)T-組件，當(dāng)且僅當(dāng)滿足條件：

定義5第一個(gè)條件要求是PN1是PN2關(guān)于T1的外延子網(wǎng)，而第二個(gè)條件則要求PN1是個(gè)標(biāo)識圖。

3 sound自由選擇系統(tǒng)中的序關(guān)系

定義6 Petri網(wǎng)是自由選擇的當(dāng)且僅當(dāng)任意兩個(gè)變遷 t1和 t2有：·t1∩·t2≠? 蘊(yùn)含·t1=·t2.

定義7 設(shè)S=（PN，[i]）是一個(gè)工作流系統(tǒng)。并發(fā)關(guān)系包含所有變遷對（x，y），如果x≠y且存在可達(dá)標(biāo)識M≥[x]+[y].

定義 8[4]設(shè) S=（PN，[i]）是一個(gè)工作流系統(tǒng)。 弱序關(guān)系?=T×T 包含所有變遷對（x，y），如果系統(tǒng)存在一個(gè)變遷發(fā)生序列σ=t1，t2…tn，使得ti=x，tk=y，1≤i＜k≤n.

在弱序關(guān)系基礎(chǔ)上，文獻(xiàn)[4]討論sound自由選擇系統(tǒng)中活動之間的幾種關(guān)系：嚴(yán)序關(guān)系、互斥關(guān)系、交錯(cuò)關(guān)系以及逆嚴(yán)序關(guān)系。

定義9[4]設(shè)S=（PN，[i]）是一個(gè)工作流系統(tǒng)。變遷對（x，y）屬于下列關(guān)系之一：

（4） 逆嚴(yán)序關(guān)系：且 y?x.

顯然，這些關(guān)系劃分了T×T。文獻(xiàn)[4]證明了在sound自由選擇系統(tǒng)中，如果兩個(gè)變遷不是并發(fā)的，那么它們的結(jié)構(gòu)關(guān)系與行為關(guān)系是一致的。我們先計(jì)算出并發(fā)關(guān)系，再借助流關(guān)系的傳遞閉包，即可在多項(xiàng)式時(shí)間內(nèi)計(jì)算出上述四種關(guān)系。并發(fā)關(guān)系最終可以歸并到交錯(cuò)關(guān)系中。

4 基于最小T-不變量的結(jié)構(gòu)分解技術(shù)

該分解算法存在的第一個(gè)問題是，T-不變量反映的是Petri網(wǎng)的結(jié)構(gòu)特征，它與初始標(biāo)識無關(guān)。對于sound工作流網(wǎng)，一個(gè)可循環(huán)執(zhí)行的結(jié)構(gòu)的確對應(yīng)了一個(gè)T-不變量，但可能由于托肯不足的原因，一個(gè)T-不變量卻不一定能對應(yīng)系統(tǒng)的一個(gè)合法執(zhí)行序列。圖1給出了這樣一個(gè)反例。在圖1中未涂黑的變遷表示在T-不變量中權(quán)值為1。顯然，該T-不變量不能對應(yīng)一個(gè)合法發(fā)生序列。

圖1 一個(gè)非合法執(zhí)行序列的最小T-不變量

該分解算法存在的第二個(gè)問題是，對于一個(gè)任意的sound工作流網(wǎng)，其最小T-不變量生成的子網(wǎng)未必是T-組件。例如在圖2中所有變遷都在同一個(gè)最小T-不變量中，顯然，這不是一個(gè)T-組件。

圖2 一個(gè)不能生成T-組件的最小T-不變量

由于不能避免上述兩個(gè)問題，文獻(xiàn)[8]中的關(guān)于sound工作流可分解成多個(gè)T-組件子網(wǎng)，每一子網(wǎng)對應(yīng)一個(gè)工作流執(zhí)行分支的結(jié)論是錯(cuò)誤的。此外，該分解算法沒有考慮系統(tǒng)中存在可執(zhí)行環(huán)情況。

然而，對于sound自由選擇系統(tǒng)，有如下結(jié)論：

定理 1[9]設(shè) PN＝（P，T，F(xiàn)，[i]）是活的且有界的自由選擇系統(tǒng)，J是PN的一個(gè)極小T-不變量，則‖J‖生成一個(gè)強(qiáng)連接的T-組件，并且J是可執(zhí)行的。

這一定理保證了對sound自由選擇系統(tǒng)，可以根據(jù)最小T-不變量分解算法，得到可執(zhí)行的T-組件。分解算法如下：

（2）求解方程 CTX＝0，得到所有最小 T-不變量集合，記作它們的支集集合記作注意C是的關(guān)聯(lián)矩陣；

（4）所得子網(wǎng)分成兩個(gè)集合，一個(gè)是不含t*的子網(wǎng)集合另一個(gè)是含t*的子網(wǎng)集合

（6）對合并后的每個(gè)子網(wǎng)，刪除t*及其關(guān)聯(lián)邊。

考慮到T-不變量的物理意義，我們只需求解 X≥0且 X（t*）＝0或 1的 T-不變量。

5 非自由選擇系統(tǒng)中的序關(guān)系

從第3節(jié)討論可知，對sound自由選擇系統(tǒng)，可根據(jù)并發(fā)關(guān)系和流關(guān)系的傳遞閉包來求取序關(guān)系。而對于非自由選擇系統(tǒng)，難以根據(jù)流關(guān)系的傳遞閉包獲取序關(guān)系。如圖2，如果根據(jù)流關(guān)系的傳遞閉包求取序關(guān)系，t1與t2屬于交錯(cuò)關(guān)系。但實(shí)際上t2不可能在t1之前發(fā)生，故這種交錯(cuò)關(guān)系不正確。

如果一個(gè)sound非自由選擇系統(tǒng)可以通過T-不變量分解法分解成sound自由選擇子系統(tǒng)，則其活動的序關(guān)系是可以獲取的。具體步驟如下：

Step 1：基于T-不變量對系統(tǒng)進(jìn)行分解；

Step 2：驗(yàn)證每個(gè)子系統(tǒng)是否為sound自由選擇系統(tǒng)，若存在非sound自由選擇子系統(tǒng)，則結(jié)束；

Step 3：依次求取每個(gè)子系統(tǒng)中的并發(fā)關(guān)系，并結(jié)合子系統(tǒng)中的流關(guān)系的傳遞閉包，獲取嚴(yán)序關(guān)系、交錯(cuò)關(guān)系和互斥關(guān)系。

Step 4：合并第三步的結(jié)果；

Step 5：求取互斥關(guān)系。 變遷對（x，y）屬于互斥關(guān)系，如果所有子系統(tǒng)都不同時(shí)包含x和y.

注意Step 3和Step 5都求取互斥關(guān)系，但不同的是，Step 3求取的是x=y型的互斥關(guān)系，而Step 5則求取x≠y型的互斥關(guān)系。

圖3 一個(gè)sound非自由選擇系統(tǒng)

圖3是一個(gè)sound非自由選擇系統(tǒng)，如果根據(jù)流關(guān)系的傳遞閉包，變遷對（A，E）和（B，D）將屬于嚴(yán)序關(guān)系。然而我們可以看到，該系統(tǒng)只有兩條可能的執(zhí)行路徑：A，C，D 和 B，C，E，故（A，E）和（B，D）是互斥的。如果采用T-不變量分解法，可以得到兩個(gè)sound自由選擇子系統(tǒng)，如圖4所示。 在 Step 3 中可求得 （A，A）、（B，B）、（C，C）、（D，D）、（E，E）是互斥的。 在 Step 5 中，可得（A，E）、（B，D）、（A，B）、（D，E）也是互斥的。

圖4 圖3的兩個(gè)子系統(tǒng)

6 小結(jié)

如何獲取工作流系統(tǒng)中活動之間的序關(guān)系，一直是模型分析人員關(guān)心的問題。本文分析了文獻(xiàn)[8]中的錯(cuò)誤，并給出了反例，對T-不變量分解算法做了修正。最后對sound自由選擇系統(tǒng)獲取活動之間序關(guān)系的方法進(jìn)行推廣，從而可以獲取那些可分解為sound自由選擇子系統(tǒng)的非自由選擇系統(tǒng)中活動的序關(guān)系。如何獲取任意sound工作流網(wǎng)中活動的序關(guān)系，是我們下一步要研究的問題。

[1] W.M.P.van der Aalst.The application of Petri nets to workflow management[J].The Journal of Circuits,Systems,and Computers,1998，8（1）：21-66.

[2] W.M.P.van der Aalst,K.M.van Hee,A.H.M.ter Hofstede,et al.,M.Wynn.Soundness of workflow nets：classification,decidability,and analysis[J].Formal Aspects of Computing,2011，23（3）：333-363.

[3] W.M.P.van der Aalst,T.Weijters,and L.Maruster.Workflow Mining：Discovering Process Models from Event Logs[J].IEEE Transactions on Knowledge and Data Engineering,2004，16（9）：1128-1142.

[4] M.Weidlich,J.Mendling,and M.Weske.Efficient consistency measurement based on behavioural profiles of process models[J].IEEE Transactions on Software Engineering,2011，37（3）：410-429.

[5] M.Weidlich,H.Ziekow,J.Mendling,O.Günther,M.Weske,and N.Desai.Event-Based Monitoring of Process Execution Violations[A].S.Rinderle-Ma,F.Toumani,and K.Wolf,Eds.,Proc.of the 9th International Conference on Business Process Management[C].Springer-Verlag,Berlin Heidelberg,2011：182-198.

[6] S.Pang,C.Lin,M.Zhou and Y.Li.A Workflow Decomposition Algorithm Based on Invariants[J].Chinese Journal of Electronics,2011，20（1）：1-5.

[7] H.M.W.Verbeek,W.M.P.van der Aalst,and A.H.M.terHofstede.Verifying Workflows with Cancellation Regions and OR-joins：An Approach Based on Relaxed Soundness and Invariants[J].The Computer Journal,2007，3（50）：294-314.

[8] 葛季棟，胡昊，呂建.一種基于不變量的從工作流網(wǎng)到PERT圖的轉(zhuǎn)換方法[J].電子學(xué)報(bào)，2008，36（5）：893-898.

[9] E.Best and J.Desel.Partial order behaviour and structure of Petri nets[J].Formal Aspects of Computing，1990，2（1）：123-138.