Petri网动态切片的最小变化域分析方法*

赵　芳，方贤文，方　欢

安徽理工大学理学院信息与计算科学系，安徽淮南232001

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

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



Petri网动态切片的最小变化域分析方法*

赵芳+，方贤文，方欢

安徽理工大学理学院信息与计算科学系，安徽淮南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网络优先出版: 2015-08-13, http://www.cnki.net/kcms/detail/11.5602.TP.20150813.1107.001.html

摘要：在业务流程管理中，确定流程模型的最小变化域是一项重要的问题。已有的方法主要是从整个模型book=517,ebook=71的角度去分析考察它的最小变化域，计算量比较复杂，具有一定的局限性。为了尽快查找到目标模型中的最小变化域，提出了Petri网动态切片的方法。首先通过对比分析源模型和目标模型的结构图得出目标模型的可疑区域，接着依据行为轮廓的思想在目标模型可疑区域中搜索出变化域，然后通过Petri网动态切片的方法得到目标模型的最小变化域。最后通过具体的电子购物实例，验证了该方法的有效性。

关键词：最小变化域；Petri网；动态切片；可疑区域；行为轮廓；变化域

1　引言

随着计算机技术的日益发展，业务流程已经得到了广泛的应用。从流程的制定到流程的实施，基于不同的目的产生了大量的模型，但在建模的过程中也会出现一些问题（变化域）。因此寻找模型的这种变化域有一定的意义，解决变化域的问题也成为业务流程管理的核心问题。

目前，国内外有很多人从事变化域的研究工作。例如，2007年Weber等人对过程模型中的变化域进行了分类，提供了一系列的变化域模式，增强了系统性功能[1]；之后Li等人用数学的思想测量出两个过程模型间的距离以及相似度，并且提出基于高水平变化域的操作方式能够保证模型的转换结果是一个合理的过程模型[2]；Llorens及Rakow等研究人员在2008年引出了Petri网的动态切片技术，提出了用程序切片来隔离包含故障的区域，使得系统的故障能更容易被发现[3-4]；2009年和2012年间，Weidlich和Mending等人给出了流程模型的变化域传播，通过给定源模型中的变化域，基于边界变迁的减少和内部边界变迁的减少确定了目标模型的变化域[5-6]；Wang等人之后又提出了一种新的基于网络的方法去识别重要的模块，并且全面探讨了变化域的分布和传播的相关性[7]；再后来，Goknil等人根据行为语义学形成的需求关系，提出了变化域的传播方法，并且对有变动需求的模型进行了一致性的检验[8]。

基于以上背景，本文首先根据源模型和目标模型变迁对间的关系，将源模型、目标模型的结构图进行了对比分析，得到了目标模型的可疑区域；然后根据行为轮廓这方面的理论构造出算法，得出了目标模型在可疑区域中的变化域；最后通过Petri网动态切片技术以及相应的算法进一步确定了目标模型的最小变化域。

本文组织结构如下：第2章介绍了一些基本定义；第3章提出了用行为轮廓的理论以及动态切片的方法去分析模型的变化域和最小变化域；第4章用具体的实例分析了所给方法的有效性；第5章总结全文。

2　基本定义

定义1[9-11]（流程模型的Petri网）一个流程模型的Petri网是一个四元组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}是网N的结构类型。

在流程模型的Petri网N中存在一种薄弱的序关系，即：T×T包含所有的变迁(x,y)，存在一个发生序列ρ=t1t2…tn，当i∈{1,2,…,n-1}时，i

依据这种薄弱的序关系，定义了行为轮廓。

定义2[12-13]（行为轮廓）设N=(P,T,F,C)为一个流程模型的Petri网，(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种关系构成了网N的行为轮廓，通过严格序关系，得到了严格逆序的关系，即⇒-1(ti,tj)，若(tj,ti)∈{≻}且(ti,tj)∉{≻}。

严格序关系说明两个变迁的发生有先后顺序；排他序关系说明两个变迁是不可能同时发生的；交叉序关系说明两个变迁能够以任何的顺序发生。分别如图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。

本文将不满足以上定义的那些变迁所构成的区域称作可疑区域，在此基础上定义了目标模型的变化域，Petri网的动态切片方法及合成网、模型间的交互以及目标模型的最小变化域。

定义4（目标模型N2的变化域）已知源模型Petri网为N1=(P1,T1,F1,C1)，目标模型Petri网为N2= (P2,T2,F2,C2)，∀tj,tj+1∈T2对应于ti,ti+1∈T1，在可疑区域内，将目标模型中不满足源模型相应变迁间行为轮廓关系的变迁构成的集合{tj,tj+1,…}称为目标模型N2的变化域，记为W。

定义6（模型间的交互）设Nμ=(Pμ,Tμ,Fμ,Cμ)为目标模型的变化域构成的网，对于其中的任意变迁x∈Tμ,IN(x)={(y,x)∈Fμ|y∈●x}称为变迁x的输入集合，OUT(x)={(x,y)∈Fμ|y∈x●}称为变迁x的输出集合。其中|IN(x)|表示x的输入集合库所个数，|OUT(x)|表示x的输出集合库所个数，模型间的交互需要满足|IN(x)|+|OUT(x)|≥3。

定义7（目标模型的最小变化域）已知Petri网动态切片的合成网为S′=S1⋂S2，模型间的交互区域之间形成的网为S3，将S=S′⋂S3形成的网称为目标模型的最小变化域。

3　基于Petri网的动态切片技术分析目标模型的最小变化域

动态切片技术[16-18]主要指的是通过寻找业务流程模型内部相关属性，达到分解整个业务流程的目的，并且对分解所得到的业务流程的切片进行分析研究，进而能够对整个业务流程进行理解和认识。

本文提出的Petri网动态切片技术主要是指在某个给定的条件下，对变化域中的变迁对进行前推和后推，产生一个交集，通过对这个交集进行分析，能够缩小整个目标模型变化域的范围，并且分析出整个目标模型出问题的关键点。具体步骤为：首先通过分析源模型结构图和目标模型结构图，找出目标模型的可疑区域；然后用行为轮廓的方法找出目标模型可疑区域中的变化域；最后基于动态切片的方法确定目标模型中的最小变化域。下面给出具体的算法来验证本文方法的有效性。

算法1寻找目标模型的变化域

Begin（算法开始）

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

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

Output：W，目标模型的变化域。

1.将N1、N2转化为Petri网结构图。

2.观察N1、N2，由定义3得到N2的可疑区域D0，依次标出节点d1d2…dn-1dn，对应N1中的可疑区域为D1，相应的节点为e1e2…em-1em，接着执行步骤3。

3.依据D1内变迁对之间的行为关系，观察D0内相应变迁对之间的行为关系：

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，接着执行步骤4；

End（算法结束）

依据算法1，可以得出目标模型N2的变化域，在此基础上，对N2做进一步的分析，依据动态切片方法，找出目标模型N2的最小变化域。

算法2基于动态切片方法寻找目标模型N2的最小变化域

Begin（算法开始）

Input：W，目标模型N2的变化域。

Output：Wmin，目标模型N2的最小变化域。

1.由算法1，可得N2的变化域是W=●D2⋃D2⋃D●2，令N3=(P3,T3,F3)为目标模型N2中变化域W构成的Petri网。

2.令σi(1≤i≤k)为N3中的执行序列段，在σi中不重复地选定库所节点和变迁节点，由定义5可知：

2.1If●pi≠∅，●pj≠∅，●ti≠∅，●tj≠∅Then S1=●pi⋃●ti⋃●pj⋃●tj⋃…，依次向前推出使能的活动变迁以及引起活动变迁发生的条件库所，直到结束；

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

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

3.由定义5，得知Petri网动态切片的合成网为S′=S1⋂S2。

4.由定义6，在W中找出模型的交互区域，将其构成的网记为S3。

6.重复步骤3、步骤4和步骤5，可得到每条执行序列段下的最小变化域的集合，取它们的并集。

7.输出目标模型N2的最小变化域为：

End（算法结束）

已有的算法[2-3]主要是在行为轮廓的基础上基于边界变迁的减少和内部边界变迁的减少来寻找目标模型的变化域，而且是从整个模型的角度去分析考察的，过程比较复杂。而通过本文所给的定义3和算法1，将源模型和目标模型进行对比分析找出一个可疑区域，并在可疑区域内寻找出目标模型N2的变化域，降低了寻找目标模型变化域的时间复杂度；通过算法2，能够进一步地以动态的方式缩小目标模型N2变化域的范围，更具有一定的优越性。

4　实例分析

本文给出一个电子购物实例，通过阐述实例来分析所给方法的有效性。图2和图3分别给出源模型Petri网N1和目标模型Petri网N2的结构图，依据定义3将N1和N2进行对比分析，可以得出N2的可疑区域，如图3中的虚线区域所示，对应着N1中的虚线区域（图2）。本文提出的方法重点解决如下两个问题：（1）基于行为轮廓的思想在可疑区域中查找变化域；（2）基于动态切片的方法将所查找到的变化域进一步缩小。

图2给出了源模型Petri网结构图。其中p1代表顾客；p4代表商店；p12代表支付中心；t2代表顾客进入商店；t5代表商店验证顾客身份；t8代表顾客进入支付中心；t11代表支付中心验证顾客身份；t13代表不同顾客所享受到的待遇；t15代表顾客付款到支付中心；t18代表支付中心要求顾客输入支付密码；t21代表顾客输入支付密码到支付中心；t24代表支付中心核对钱款；t26代表钱款正确；t28代表钱款错误；t29代表支付中心向商店发送支付成功；t31代表商店向顾客发送交易成功。

Fig.2 Petri nets of source model N1图2　源模型Petri网N1

Fig.3 Petri nets of target model N2图3　目标模型Petri网N2

根据目标模型的最小变化域中的变迁节点所代表的信息，可以得出在目标模型中，支付中心VIP在购物付款时可能会出现钱款不足，而支付中心也未核对其钱款信息，导致支付中心会受到一定的损失。而通过本文所给的方法可以找出产生这种问题的根源，即最小变化域。

Fig.4 Change region of target model N2图4　目标模型N2的变化域

5　结束语

本文在已有研究的基础上，对源模型和目标模型进行了对比分析，基于Petri网及其行为轮廓，通过研究源模型结构图和目标模型结构图，得出了目标模型的变化域，并提出了一种新的方法，即Petri网动态切片技术，确定了目标模型中的最小变化域。

本文方法也有一定的局限性，忽略了可疑区域之外的某些变迁也会对模型产生影响，虽然这种情况很少发生，但这也会降低最终结果的可信度。

未来关于模型的变化域还有许多问题去研究。例如在没有源模型的情况下如何查找目标模型的变化域，如何对查找出的变化域进行改进，如何调整模型使得模型没有变化域等。

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网理论[M].北京:机械工业出版社, 2006: 6-22.

[11]蒋昌俊. Petri网的行为理论及其应用[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网。

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年于同济大学获得博士学位，现为安徽理工大学教授，主要研究领域为Petri网，可信软件，服务计算。主持国家级项目3项，省部级项目近10项，已发表学术论文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年于合肥工业大学获得博士学位，现为安徽理工大学副教授，主要研究领域为Petri网，智能信息系统。

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