趙　芳，方賢文，方　歡

安徽理工大學理學院信息與計算科學系，安徽淮南232001

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0516-08

?

Petri網(wǎng)動態(tài)切片的最小變化域分析方法*

趙芳+，方賢文，方歡

安徽理工大學理學院信息與計算科學系，安徽淮南232001

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0516-08

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61272153, 61402011 (國家自然科學基金); the Natural Science Foundation of Anhui Province under Grant No. 1508085MF111 (安徽省自然科學基金); the Natural Science Foundation of Educational Government of Anhui Province under Grant No. KJ2014A607 (安徽省高校自然科學基金重點項目).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡優(yōu)先出版: 2015-08-13, http://www.cnki.net/kcms/detail/11.5602.TP.20150813.1107.001.html

摘要：在業(yè)務流程管理中，確定流程模型的最小變化域是一項重要的問題。已有的方法主要是從整個模型book=517,ebook=71的角度去分析考察它的最小變化域，計算量比較復雜，具有一定的局限性。為了盡快查找到目標模型中的最小變化域，提出了Petri網(wǎng)動態(tài)切片的方法。首先通過對比分析源模型和目標模型的結構圖得出目標模型的可疑區(qū)域，接著依據(jù)行為輪廓的思想在目標模型可疑區(qū)域中搜索出變化域，然后通過Petri網(wǎng)動態(tài)切片的方法得到目標模型的最小變化域。最后通過具體的電子購物實例，驗證了該方法的有效性。

關鍵詞：最小變化域；Petri網(wǎng)；動態(tài)切片；可疑區(qū)域；行為輪廓；變化域

1　引言

隨著計算機技術的日益發(fā)展，業(yè)務流程已經(jīng)得到了廣泛的應用。從流程的制定到流程的實施，基于不同的目的產(chǎn)生了大量的模型，但在建模的過程中也會出現(xiàn)一些問題（變化域）。因此尋找模型的這種變化域有一定的意義，解決變化域的問題也成為業(yè)務流程管理的核心問題。

目前，國內(nèi)外有很多人從事變化域的研究工作。例如，2007年Weber等人對過程模型中的變化域進行了分類，提供了一系列的變化域模式，增強了系統(tǒng)性功能[1]；之后Li等人用數(shù)學的思想測量出兩個過程模型間的距離以及相似度，并且提出基于高水平變化域的操作方式能夠保證模型的轉換結果是一個合理的過程模型[2]；Llorens及Rakow等研究人員在2008年引出了Petri網(wǎng)的動態(tài)切片技術，提出了用程序切片來隔離包含故障的區(qū)域，使得系統(tǒng)的故障能更容易被發(fā)現(xiàn)[3-4]；2009年和2012年間，Weidlich和Mending等人給出了流程模型的變化域傳播，通過給定源模型中的變化域，基于邊界變遷的減少和內(nèi)部邊界變遷的減少確定了目標模型的變化域[5-6]；Wang等人之后又提出了一種新的基于網(wǎng)絡的方法去識別重要的模塊，并且全面探討了變化域的分布和傳播的相關性[7]；再后來，Goknil等人根據(jù)行為語義學形成的需求關系，提出了變化域的傳播方法，并且對有變動需求的模型進行了一致性的檢驗[8]。

基于以上背景，本文首先根據(jù)源模型和目標模型變遷對間的關系，將源模型、目標模型的結構圖進行了對比分析，得到了目標模型的可疑區(qū)域；然后根據(jù)行為輪廓這方面的理論構造出算法，得出了目標模型在可疑區(qū)域中的變化域；最后通過Petri網(wǎng)動態(tài)切片技術以及相應的算法進一步確定了目標模型的最小變化域。

本文組織結構如下：第2章介紹了一些基本定義；第3章提出了用行為輪廓的理論以及動態(tài)切片的方法去分析模型的變化域和最小變化域；第4章用具體的實例分析了所給方法的有效性；第5章總結全文。

2　基本定義

定義1[9-11]（流程模型的Petri網(wǎng)）一個流程模型的Petri網(wǎng)是一個四元組N=(P,T,F,C)。需要滿足如下的幾個條件：

（1）P為有限非空庫所的集合，T為有限非空變遷的集合，P?T=?。

（2）F?(P×T)?(T×P)為N中的流關系并且(P?T,F)是強連通圖。

（3）●x={y|(y∈P?T)?((y,x)∈F)}稱為x的前集，x●={y|(y∈P?T)?((y,x)∈F)}稱為x的后集。

（4）若x為P的初始庫所，則●x=?；若x為P的終止庫所，則x●=?。

（5）dom(F)?cod(F)=P?T，其中：

dom(F)={x∈P?T|?y∈P?T,(x,y)∈F}

cod(F)={x∈P?T|?y∈P?T,(y,x)∈F}

（6）C={and,xor}是網(wǎng)N的結構類型。

在流程模型的Petri網(wǎng)N中存在一種薄弱的序關系，即：T×T包含所有的變遷(x,y)，存在一個發(fā)生序列ρ=t1t2…tn，當i∈{1,2,…,n-1}時，i

依據(jù)這種薄弱的序關系，定義了行為輪廓。

定義2[12-13]（行為輪廓）設N=(P,T,F,C)為一個流程模型的Petri網(wǎng)，(ti,tj)∈T×T,其中1≤i≤n-1，2≤j≤n，至少滿足以下關系中的一種：

（1）嚴格序關系

?(ti,tj)，若(ti,tj)∈{?}且(tj,ti)?{?}。

（2）排他序關系

?(ti,tj)，若(ti,tj)?{?}且(tj,ti)?{?}。

（3）交叉序關系

?(ti,tj)，若(ti,tj)∈{?}且(tj,ti)∈{?}。

以上3種關系構成了網(wǎng)N的行為輪廓，通過嚴格序關系，得到了嚴格逆序的關系，即?-1(ti,tj)，若(tj,ti)∈{?}且(ti,tj)?{?}。

嚴格序關系說明兩個變遷的發(fā)生有先后順序；排他序關系說明兩個變遷是不可能同時發(fā)生的；交叉序關系說明兩個變遷能夠以任何的順序發(fā)生。分別如圖1所示。

Fig.1　Relations of transitions圖1　變遷關系圖

（1）若ta=tb，那么對?tx∈T2,ta≈tx，有taR1ta?txR2tx。

（2）若ta≠tb，那么對?tx, ty∈T2，tx≠ty，有下列兩種情況中的一種成立：

①ta≈tx，tb≈ty，有taR1tb?txR2ty。

②ta≈ty，tb≈tx，有taR1tb?tyR2tx。

本文將不滿足以上定義的那些變遷所構成的區(qū)域稱作可疑區(qū)域，在此基礎上定義了目標模型的變化域，Petri網(wǎng)的動態(tài)切片方法及合成網(wǎng)、模型間的交互以及目標模型的最小變化域。

定義4（目標模型N2的變化域）已知源模型Petri網(wǎng)為N1=(P1,T1,F1,C1)，目標模型Petri網(wǎng)為N2= (P2,T2,F2,C2)，?tj,tj+1∈T2對應于ti,ti+1∈T1，在可疑區(qū)域內(nèi)，將目標模型中不滿足源模型相應變遷間行為輪廓關系的變遷構成的集合{tj,tj+1,…}稱為目標模型N2的變化域，記為W。

定義6（模型間的交互）設Nμ=(Pμ,Tμ,Fμ,Cμ)為目標模型的變化域構成的網(wǎng)，對于其中的任意變遷x∈Tμ,IN(x)={(y,x)∈Fμ|y∈●x}稱為變遷x的輸入集合，OUT(x)={(x,y)∈Fμ|y∈x●}稱為變遷x的輸出集合。其中|IN(x)|表示x的輸入集合庫所個數(shù)，|OUT(x)|表示x的輸出集合庫所個數(shù)，模型間的交互需要滿足|IN(x)|+|OUT(x)|≥3。

定義7（目標模型的最小變化域）已知Petri網(wǎng)動態(tài)切片的合成網(wǎng)為S′=S1?S2，模型間的交互區(qū)域之間形成的網(wǎng)為S3，將S=S′?S3形成的網(wǎng)稱為目標模型的最小變化域。

3　基于Petri網(wǎng)的動態(tài)切片技術分析目標模型的最小變化域

動態(tài)切片技術[16-18]主要指的是通過尋找業(yè)務流程模型內(nèi)部相關屬性，達到分解整個業(yè)務流程的目的，并且對分解所得到的業(yè)務流程的切片進行分析研究，進而能夠對整個業(yè)務流程進行理解和認識。

本文提出的Petri網(wǎng)動態(tài)切片技術主要是指在某個給定的條件下，對變化域中的變遷對進行前推和后推，產(chǎn)生一個交集，通過對這個交集進行分析，能夠縮小整個目標模型變化域的范圍，并且分析出整個目標模型出問題的關鍵點。具體步驟為：首先通過分析源模型結構圖和目標模型結構圖，找出目標模型的可疑區(qū)域；然后用行為輪廓的方法找出目標模型可疑區(qū)域中的變化域；最后基于動態(tài)切片的方法確定目標模型中的最小變化域。下面給出具體的算法來驗證本文方法的有效性。

算法1尋找目標模型的變化域

Begin（算法開始）

Input：N1=(P1,T1,F1,C1)，源模型。

N2=(P2,T2,F2,C2)，目標模型。

Output：W，目標模型的變化域。

1.將N1、N2轉化為Petri網(wǎng)結構圖。

2.觀察N1、N2，由定義3得到N2的可疑區(qū)域D0，依次標出節(jié)點d1d2…dn-1dn，對應N1中的可疑區(qū)域為D1，相應的節(jié)點為e1e2…em-1em，接著執(zhí)行步驟3。

3.依據(jù)D1內(nèi)變遷對之間的行為關系，觀察D0內(nèi)相應變遷對之間的行為關系：

If D1中的變遷對?(ei,ej)，?-1(ei,ej)，?(ei,ej)或?(ei,ej) Then觀察D0中相應的變遷對dk、dl是否也滿足相同的對應關系

If不滿足Then dk、dl即為疑似點；

Else N2的疑似點集合為D2=D1-{dk,dl}，其中1≤i,j≤m，1≤k,l≤n，接著執(zhí)行步驟4；

End（算法結束）

依據(jù)算法1，可以得出目標模型N2的變化域，在此基礎上，對N2做進一步的分析，依據(jù)動態(tài)切片方法，找出目標模型N2的最小變化域。

算法2基于動態(tài)切片方法尋找目標模型N2的最小變化域

Begin（算法開始）

Input：W，目標模型N2的變化域。

Output：Wmin，目標模型N2的最小變化域。

1.由算法1，可得N2的變化域是W=●D2?D2?D●2，令N3=(P3,T3,F3)為目標模型N2中變化域W構成的Petri網(wǎng)。

2.令σi(1≤i≤k)為N3中的執(zhí)行序列段，在σi中不重復地選定庫所節(jié)點和變遷節(jié)點，由定義5可知：

2.1If●pi≠?，●pj≠?，●ti≠?，●tj≠?Then S1=●pi?●ti?●pj?●tj?…，依次向前推出使能的活動變遷以及引起活動變遷發(fā)生的條件庫所，直到結束；

Else推出S1=σi，1≤i≤k，1≤j≤k。

Else推出S2=σi，1≤i≤k，1≤j≤k。

3.由定義5，得知Petri網(wǎng)動態(tài)切片的合成網(wǎng)為S′=S1?S2。

4.由定義6，在W中找出模型的交互區(qū)域，將其構成的網(wǎng)記為S3。

6.重復步驟3、步驟4和步驟5，可得到每條執(zhí)行序列段下的最小變化域的集合，取它們的并集。

7.輸出目標模型N2的最小變化域為：

End（算法結束）

已有的算法[2-3]主要是在行為輪廓的基礎上基于邊界變遷的減少和內(nèi)部邊界變遷的減少來尋找目標模型的變化域，而且是從整個模型的角度去分析考察的，過程比較復雜。而通過本文所給的定義3和算法1，將源模型和目標模型進行對比分析找出一個可疑區(qū)域，并在可疑區(qū)域內(nèi)尋找出目標模型N2的變化域，降低了尋找目標模型變化域的時間復雜度；通過算法2，能夠進一步地以動態(tài)的方式縮小目標模型N2變化域的范圍，更具有一定的優(yōu)越性。

4　實例分析

本文給出一個電子購物實例，通過闡述實例來分析所給方法的有效性。圖2和圖3分別給出源模型Petri網(wǎng)N1和目標模型Petri網(wǎng)N2的結構圖，依據(jù)定義3將N1和N2進行對比分析，可以得出N2的可疑區(qū)域，如圖3中的虛線區(qū)域所示，對應著N1中的虛線區(qū)域（圖2）。本文提出的方法重點解決如下兩個問題：（1）基于行為輪廓的思想在可疑區(qū)域中查找變化域；（2）基于動態(tài)切片的方法將所查找到的變化域進一步縮小。

圖2給出了源模型Petri網(wǎng)結構圖。其中p1代表顧客；p4代表商店；p12代表支付中心；t2代表顧客進入商店；t5代表商店驗證顧客身份；t8代表顧客進入支付中心；t11代表支付中心驗證顧客身份；t13代表不同顧客所享受到的待遇；t15代表顧客付款到支付中心；t18代表支付中心要求顧客輸入支付密碼；t21代表顧客輸入支付密碼到支付中心；t24代表支付中心核對錢款；t26代表錢款正確；t28代表錢款錯誤；t29代表支付中心向商店發(fā)送支付成功；t31代表商店向顧客發(fā)送交易成功。

Fig.2 Petri nets of source model N1圖2　源模型Petri網(wǎng)N1

Fig.3 Petri nets of target model N2圖3　目標模型Petri網(wǎng)N2

根據(jù)目標模型的最小變化域中的變遷節(jié)點所代表的信息，可以得出在目標模型中，支付中心VIP在購物付款時可能會出現(xiàn)錢款不足，而支付中心也未核對其錢款信息，導致支付中心會受到一定的損失。而通過本文所給的方法可以找出產(chǎn)生這種問題的根源，即最小變化域。

Fig.4 Change region of target model N2圖4　目標模型N2的變化域

5　結束語

本文在已有研究的基礎上，對源模型和目標模型進行了對比分析，基于Petri網(wǎng)及其行為輪廓，通過研究源模型結構圖和目標模型結構圖，得出了目標模型的變化域，并提出了一種新的方法，即Petri網(wǎng)動態(tài)切片技術，確定了目標模型中的最小變化域。

本文方法也有一定的局限性，忽略了可疑區(qū)域之外的某些變遷也會對模型產(chǎn)生影響，雖然這種情況很少發(fā)生，但這也會降低最終結果的可信度。

未來關于模型的變化域還有許多問題去研究。例如在沒有源模型的情況下如何查找目標模型的變化域，如何對查找出的變化域進行改進，如何調整模型使得模型沒有變化域等。

References:

[1] Weber B, Rinderle S, Reichert M. Change patterns and change support features in process-aware information systems[C]//LNCS 4495: Proceedings of the 19th International Conference on Advanced Information Systems Engineering, Trondheim, Norway, Jun 11-15, 2007. Berlin, Heidelberg: Springer, 2007: 574-588.

[2] Li Chen, Reichert M, Wombacher A. On measuring process model similarity based on high-level change operations[C]// LNCS 5231: Proceedings of the 27th International Conference on Conceptual Modeling, Barcelona, Spain, Oct 20-24, 2008. Berlin, Heidelberg: Springer, 2008: 248-264.

[3] Llorens M, Oliver J, Silva J, et al. Dynamic slicing techniques for Petri nets[J]. Electronic Notes in Theoretical Computer Science, 2008, 223: 153-165.

[4] Rakow A. Slicing Petri nets with an application to workflow verification[C]//LNCS 4910: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, Novy Smokovec, Slovakia, Jan 19-25, 2008. Berlin, Heidelberg: Springer, 2008: 436-447.

[5] Weidlich M, Weske M, Mendling J. Change propagation in process models using behavioral profiles[C]//Proceedings of the 2009 IEEE International Conference on Services Computing, Bangalore, India, Sep 21-25, 2009. Piscataway, USA: IEEE, 2009: 33-40.

[6] Weidlich M, Mendling J, Weske M. Propagating changes between aligned process models[J]. The Journal of Systems and Software, 2012, 85(8): 1885-1898.

[7] Wang Rongcun, Huang Rubing, Qu Binbin. Network-based analysis of software change propagation[J]. The Scientific World, 2014, 1155(10): 237-243.

[8] Goknil A, Kurtev I, Berg K, et al. Change impact analysis for requirements: a meta- modeling approach[J]. Information and Software Technology, 2014, 56(8): 950-972.

[9] Smirnov S, Weidlich M, Mendling J. Business process model abstraction based on behavioral profiles[C]//LNCS 6470: Proceedings of the 8th International Conference on Service-Oriented Computing, San Francisco, USA, Dec 7-10, 2010. Berlin, Heidelberg: Springer, 2010: 1-16.

[10] Wu Zhehui. Petri nets theory[M]. Beijing: Mechanical Industry Press, 2006: 6-22.

[11] Jiang Changjun. The behavioral theory of the Petri net and its application[M]. Beijing: Higher Education Press, 2003: 19-28.

[12] Weidlich M, Mendling J, Weske M. Efficient consistency measurement based on behavioral profiles of process models[J]. IEEE Transactions on Software Engineer, 2011, 37 (3): 410-429.

[13] Weidlich M, Polyvyanyy A, Desai N, et al. Process compliance measurement based on behavioral profiles[C]//LNCS 6051: Proceedings of the 22nd International Conference on Advanced Information Systems Engineering, Hammamet, Tunisia, Jun 7-9, 2010. Berlin, Heidelberg: Springer, 2010: 499-514.

[14] Dijkman R, Dumas M, van Dongen B, et al. Similarity of business process models: metrics and evaluation[J]. Information System, 2011, 36(2): 498-516.

[15] Hujsa T, Delosme J, Kordon A. On the reversibility of wellbehaved weighted choice-free systems[C]//LNCS 8489: Proceedings of the 35th International Conference on Application and Theory of Petri Nets and Concurrency, Tunis, Tunisia, Jun 23-27, 2014. Switzerland: Springer International Publishing, 2014: 334-353.

[16] Chen Zhenqiang. Program slicing technology research based on dependency analysis[D]. Nanjing: Southeast University, 2003.

[17] Rakow A. Safety slicing Petri nets[C]//LNCS 7347: Proceedings of the 33rd International Conference on Application and Theory of Petri Nets, Hamburg, Germany, Jun 25-29, 2012. Berlin, Heidelberg: Springer, 2012: 268-287.

[18] Rinderle S, Reichert M, Dadam P. Correctness criteria for dynamic changes in workflow systems—a survey[J]. Data & Knowledge Engineering, 2004, 50(1): 9-34.

附中文參考文獻：

[10]吳哲輝.Petri網(wǎng)理論[M].北京:機械工業(yè)出版社, 2006: 6-22.

[11]蔣昌俊. Petri網(wǎng)的行為理論及其應用[M].北京:高等教育出版社, 2003: 19-28.

[16]陳振強.基于依賴性分析的程序切片技術研究[D].南京:東南大學, 2003.

ZHAO Fang was born in 1989. She is an M.S. candidate at Anhui University of Science and Technology. Her research interest is Petri nets.

趙芳（1989—），女，安徽馬鞍山人，安徽理工大學碩士研究生，主要研究領域為Petri網(wǎng)。

FANG Xianwen was born in 1975. He received the Ph.D. degree from Tongji University in 2011. Now he is a professor at Anhui University of Science and Technology. His research interests include Petri nets, trustworthy software and Web services. He has presided over 3 national projects and nearly 10 provincial projects. He has published more than 90 papers in domestic and international academic journals and conference proceedings. These papers are embodied about 50 times by SCI and EI.

方賢文（1975—），男，河南信陽人，2011年于同濟大學獲得博士學位，現(xiàn)為安徽理工大學教授，主要研究領域為Petri網(wǎng)，可信軟件，服務計算。主持國家級項目3項，省部級項目近10項，已發(fā)表學術論文90余篇，其中SCI/ EI檢索50余次。

FANG Huan was born in 1982. She received the Ph.D. degree from Hefei University of Technology in 2013. Now she is an associate professor at Anhui University of Science and Technology. Her research interests include Petri nets and intelligent information systems.

方歡（1982—），女，安徽淮南人，2013年于合肥工業(yè)大學獲得博士學位，現(xiàn)為安徽理工大學副教授，主要研究領域為Petri網(wǎng)，智能信息系統(tǒng)。

Analysis Method of the Smallest Change Region with Dynamic Slice of Petri Nets?

ZHAO Fang+, FANG Xianwen, FANG Huan
Department of Information and Computing Science, School of Science,Anhui University of Science and Technology, Huainan,Anhui 232001, China

Z+ Corresponding author: E-mail: 1012377428@qq.com

ZHAO Fang, FANG Xianwen, FANG Huan. Analysis method of the smallest change region with dynamic slice of Petri nets. Journal of Frontiers of Computer Science and Technology, 2016, 10(4)：516-523.

Abstract:In the business process modeling, determining the smallest change domain of the process modeling is becoming a key problem. The developed method to consider the smallest change region is mainly from the angle of the whole model, and its calculation is very complex, so it has some limitations. In order to find out the smallest change region of a target model quickly, this paper puts forward a method named dynamic slice of Petri nets. Through the comparative analysis of the structure figures of source model and target model, the suspicious areas of the target model can be achieved. Then the thought of behavioral profiles is used to derive the change region of the suspicious areas in the target model. And the method named dynamic slice of Petri nets is used to obtain the smallest change region of the target model. Finally, the electronic shopping is used as an example to analyze the effectiveness of the method.

Keywords:thesmallestchangeregion;Petrinets;dynamicslice;suspiciousareas;behavioralprofiles;changeregion

文獻標志碼：A

中圖分類號：TP391.9

doi:10.3778/j.issn.1673-9418.1506077