基于T-不變量分解法獲取工作流中的序關系

蔡 敏 汪世義 韓俊波

（巢湖學院計算機與信息工程學院，安徽 合肥 238000）

1 引言

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

利用T-不變量對復雜結構的工作流網進行分解，得到一組相對簡單的子結構，再對每個子結構逐個進行分析，可以達到分而治之的目的。文獻[6]對sound良構工作流網進行了分解；文獻[7]利用T-不變量發現好路徑；文獻[8]將一個工作流網分解成一組子網，再轉化為PERT圖，進而分析過程模型的進度和工期。本文利用T-不變量分解法將sound自由選擇系統中序關系可獲取性推廣到一類非自由選擇系統中，指出了文獻[8]中有關結論存在的錯誤并分析了錯誤的原因。

2 基本概念和術語

本節給出本文涉及的一些主要概念和表示符號，詳細信息可參考文獻[1][3][8]。

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

定義 2 Petri網 PN=（P，T；F） 是一個工作流網，當且僅當：

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

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

（3）如果在 PN 上增加一個變遷 t*，使（t*）·=｛i｝，·（t*）=｛o｝所得到的擴展網是強連接的。

在工作流網中，一個變遷可能是一個活動，也可能僅僅表示AND-split或AND-join結構。庫所對應變遷的前件與后件，也可能僅表示OR-split或OR-join結構。一個工作流系統由一個工作流網和它的初始標識[i]給出，記作 S=（PN，[i]）。

定義3 工作流系統S=（PN，[i]）滿足soundness屬性，當且僅當：

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

（2）從任意可達標識M出發，都可到達標識[o]；

（3）若存在可達標識，M≥[o]?M=[o]；

（4）無死變遷。

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

定義 5 設 PN1=（P1，T1，F1）與 PN=（P，T；F）是兩個網，稱PN1是PN的一個T-組件，當且僅當滿足條件：

定義5第一個條件要求是PN1是PN2關于T1的外延子網，而第二個條件則要求PN1是個標識圖。

3 sound自由選擇系統中的序關系

定義6 Petri網是自由選擇的當且僅當任意兩個變遷 t1和 t2有：·t1∩·t2≠? 蘊含·t1=·t2.

定義7 設S=（PN，[i]）是一個工作流系統。并發關系包含所有變遷對（x，y），如果x≠y且存在可達標識M≥[x]+[y].

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

在弱序關系基礎上，文獻[4]討論sound自由選擇系統中活動之間的幾種關系：嚴序關系、互斥關系、交錯關系以及逆嚴序關系。

定義9[4]設S=（PN，[i]）是一個工作流系統。變遷對（x，y）屬于下列關系之一：

（4） 逆嚴序關系：且 y?x.

顯然，這些關系劃分了T×T。文獻[4]證明了在sound自由選擇系統中，如果兩個變遷不是并發的，那么它們的結構關系與行為關系是一致的。我們先計算出并發關系，再借助流關系的傳遞閉包，即可在多項式時間內計算出上述四種關系。并發關系最終可以歸并到交錯關系中。

4 基于最小T-不變量的結構分解技術

該分解算法存在的第一個問題是，T-不變量反映的是Petri網的結構特征，它與初始標識無關。對于sound工作流網，一個可循環執行的結構的確對應了一個T-不變量，但可能由于托肯不足的原因，一個T-不變量卻不一定能對應系統的一個合法執行序列。圖1給出了這樣一個反例。在圖1中未涂黑的變遷表示在T-不變量中權值為1。顯然，該T-不變量不能對應一個合法發生序列。

圖1 一個非合法執行序列的最小T-不變量

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

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

由于不能避免上述兩個問題，文獻[8]中的關于sound工作流可分解成多個T-組件子網，每一子網對應一個工作流執行分支的結論是錯誤的。此外，該分解算法沒有考慮系統中存在可執行環情況。

然而，對于sound自由選擇系統，有如下結論：

定理 1[9]設 PN＝（P，T，F，[i]）是活的且有界的自由選擇系統，J是PN的一個極小T-不變量，則‖J‖生成一個強連接的T-組件，并且J是可執行的。

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

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

（4）所得子網分成兩個集合，一個是不含t*的子網集合另一個是含t*的子網集合

（6）對合并后的每個子網，刪除t*及其關聯邊。

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

5 非自由選擇系統中的序關系

從第3節討論可知，對sound自由選擇系統，可根據并發關系和流關系的傳遞閉包來求取序關系。而對于非自由選擇系統，難以根據流關系的傳遞閉包獲取序關系。如圖2，如果根據流關系的傳遞閉包求取序關系，t1與t2屬于交錯關系。但實際上t2不可能在t1之前發生，故這種交錯關系不正確。

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

Step 1：基于T-不變量對系統進行分解；

Step 2：驗證每個子系統是否為sound自由選擇系統，若存在非sound自由選擇子系統，則結束；

Step 3：依次求取每個子系統中的并發關系，并結合子系統中的流關系的傳遞閉包，獲取嚴序關系、交錯關系和互斥關系。

Step 4：合并第三步的結果；

Step 5：求取互斥關系。 變遷對（x，y）屬于互斥關系，如果所有子系統都不同時包含x和y.

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

圖3 一個sound非自由選擇系統

圖3是一個sound非自由選擇系統，如果根據流關系的傳遞閉包，變遷對（A，E）和（B，D）將屬于嚴序關系。然而我們可以看到，該系統只有兩條可能的執行路徑：A，C，D 和 B，C，E，故（A，E）和（B，D）是互斥的。如果采用T-不變量分解法，可以得到兩個sound自由選擇子系統，如圖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的兩個子系統

6 小結

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

[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] 葛季棟，胡昊，呂建.一種基于不變量的從工作流網到PERT圖的轉換方法[J].電子學報，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.