论文部分内容阅读
摘要：变化传播在许多软件领域都起着必不可少的重要作用，分析基于某种变化类型的传播范围更是一个难以忽视的问题。文中提出一种基于Petri网的库所系统，依据单向影响关系，分析添加增加类型变迁的变化传播范围的方法。首先，以某打车软件为例，建立打车软件客户端的库所系统，并插入一个增加类型的变化变迁。其次，利用单向影响关系，衡量库所系统原变迁集与所添加的增加类型变迁之间的影响关系。最后，根据增加类型变化传播影响范围公式，得出基于打车软件的库所系统，添加一个增加类型变化的传播影响范围。
关键词：Petri网；库所系统；增加类型；单向影响关系；变化传播
中图分类号：TP391.9 文献标志码：A 文章编号：1009-3044（2018）02-0211-02
Change Propagation Analysis of the Add Type Based on the Place System
PENG Ke
（College of Mathematics and Big Data， Anhui University of Science and Technology， Huainan 232001， China）
Abstract： Change propagation plays an important role in many software fields. It is a difficult problem to analyze the change propagation range of some type of change. This paper presents a method of analyzing the change propagation influence range， which inserting a transition of add type into a place system Based on Petri net on a basis of unidirectional influence relationship. Firstly， take a taxi software as an example， build a place system for car-hailing software， and then insert a change transition of add type into the system. Secondly， the influence relationship between the original change set of the system and the inserted transition of add type， which is measured by the unidirectional influence relationship method. Finally， according to the formula of change propagation influence range of a transition of the above inserted add type， it is concluded that the change propagation influence range of an inserted transition of add type Based on the place system of a car-hailing software.
Key words： Petri net； place system； add type； unidirectional influence relationship； change propagation
1 背景
现今，变化传播分析是业务流程管理中的一个重要方面。而在不断变化的业务环境下，依据变化类型，量化变化传播范围则一直属于比较繁琐又很困难的一类问题。因为变化类型分为好几种，每种不同的变化在流程中生成或添加后，都会由于涟漪效应的多样性而形成各种截然不同的新流程。故从变化传播范围角度分析变化传播是一项刻不容缓的重任。
目前，关于变化类型和变化传播已有许多研究。文献[1]阐述了变化区域和变化传播的概念，并对它们之间的关系进行了简单的介绍。文献[2]从变化分类角度来动态评估变化区域对整个流程系统的影响。文献[3]提出了一种基于流程结构树通用的分散式变化传播方法，它同样也是根据变化种类促使变化传播持续使能发生。文献[4]解决了利益相关者在业务流程中因通过不同视角执行变化而导致的不一致现象。文献[5]则是在Petri网的库所系统中，基于置信度要求变量来分析并巩固变化传播并给出由内部可信赖属性生成的影响范围。
本文的整体结构如下：第一部分介绍文中所涉及的相关基本概念；第二部分为基于库所系统的增加变化类型变化传播范围分析；第三部分則是总结本文的贡献以及未来工作的结束语。
2 基本概念
这一部分主要介绍了与本文密切相关的概念，其他相关定义可参见文献[6]。
定义1[6]（Petri网）满足下列三个条件的三元组[N=（P，T；F）]称作Petri网：
1） [P]是一个有限非空库所集，[T]是一个有限非空变迁集；
2） [P?T≠?]，[P?T=?]；
3） [F=（P×T）?（T×P）]表示流关系。
Petri网三元组包括库所[P]、变迁[T]、流关系[F]。用图形表示Petri网时，以圆圈表示库所，矩形表示变迁。对于任意[x，y∈P×T]，若[x，y∈F]即[x]到[y]有一个流关系，则活动对之间用一个有向线段表示。为计算变化传播范围，下面介绍库所系统。 定义2[7]（库所系统）六元组[Σ=S，T；F，K，W，M]是一个库所系统（Place System），其中
1） [（S，T；F）]是一个网；
2） [W：F→{1，2，3，...}]成为权函数；
3） [K：S→{1，2，3，...}]成为容量函数；
4） [M：S→{1，2，3，...}]是[Σ]的一个标识，满足条件[?s∈S：M（s）≤K（s）]
用一个库所系统[PS]对一个系统建模时，五元组[S，T；F，K，W]描述系统的结构，标识[M]反应系统的状态，此五元组也成为库所系统的基网。
定义3[3]（增加类型变化）
[AddChangePattern：]= [Add（Fragment，pred，succ）]
变化类型共有大概四种，本文分散式计算中将会用到的就是定义3增加类型变化，它是通过在流程前承结点[pred]与后继结点[succ]之间插入一个新的变迁实现的。
3 基于库所系统的增加变化类型变化传播范围分析
当前，越来越多的市民和私家车踏入了某打车软件这一领域，这些打车软件使得闲置的私家车有了一番用武之地，司机也能挣得不少的外快。市民则因其便捷性和快捷性而更青睐于这一与出租车不同的打车方式。本文就以某打车软件和乘客的交互行为为例子，建立库所系统，以库所系统为基础，插入一个增加类型的变化变迁，并通过分析前驱后继变迁集影响关系来计算影响范围。图1即为定义3所描述的增加类型变化，是图2中变迁[t′]的变化类型。
[T={t2：使用此软件；t7：新用户验证；t8：老用户默认登录；t15：所定位位置为初始位置；t16：自选位置；t17：到达位置为目的地；t18：现在叫车；t19：预约叫车；t22：抢单；t23：收到车辆信息；t28：车主电话联系；t31：上车；t34：发送行车路线；t35：发送乘车金额；t38：无优惠券；t39：有优惠券；t40：付款}] 图2中所增加的变化[t′={ 决定不坐车}]
为计算库所系统的变化传播范围，本文将以衡量库所系统原变迁集与所插入的增加类型变迁之间的影响关系为基础。下面将介绍单向影响关系[5][M=（mt（i，j））]，
[mt（i，j）=1，ti与tj之间存在单向影响关系0，ti与tj之间不存在单向影响关系，1≤i，j≤n]
库所系统由此影响关系得到添加一个增加变化后，包含此变化及其前驱变迁的影响关系矩阵[M1]和包含此变化及其后继变化的影响关系矩阵[M2]，矩阵中的元素均由单向影响关系[M=（mt（i，j））]所组成。
增加一个变化[t′]后，包含此变化及其前驱变迁的影响关系矩阵为
增加类型变化传播影响范围的公式[8]为：
[CPIRA=M11M10，1 M21M2（0，1）×100%]，
其中[M1]和[M0，1]分别表示矩阵中的元素1以及元素0、1，而[M]则表示矩阵所包含元素个数。这个公式的意义就是根据计算前驱矩阵[M1]和后继矩阵[M2]中，含1即存在单向影响关系的数量占含0，1总数的比例之和的百分比，来展示增加类型变化在库所网中传播的影响范围。
由上述公式可以得到，本文基于库所系统插入一个增加类型变化的传播影响范围是：
[CPIRA=40961 22144×100%=19.4%]
4 结束语
尽管过去的研究在包括软件领域等企业管理范围内各个方面的变化传播分析都有所涉猎，却很少考虑到从每个变化类型分散式的一一计算这些变化所传播的范围，本文则从增加类型变化弥补了一部分的短板。本文将乘客在使用某打车软件时的交互行为来建立库所系统，同时在其中添加一个增加类型的变化变迁。之后引入单向影响关系，用以衡量库所系统原变迁集与所插入的增加类型变迁之间的影响关系。随之得出由单向影响关系组成的，包含此增加类型变化的前驱矩阵和后继矩阵。最后，再依据增加类型变化传播影响范围的公式计算得到本文基于库所系统插入一个增加类型变化的传播影响范围。在此研究的基础上，未来工作将从两方面展开：试用本文中的方法计算基于其他变化类型的变化传播范围；以运行时间，运行良好程度等方面来检验此法的优劣之处，扬长避短，发挥优势并改正缺陷。
参考文献：
[1] Demuth A， Riel-Ehrenleitner M. Co-evolution of Metamodels and Models through Consistent Change Propagation[J]. The Journal of Systems and Software， 2016， 111： 281-297.
[2] Gupta C， Singh Y， Singh D. A Dynamic Approach to Estimate Change Impact using Type of Change Propagation[J]. Journal of Information Processing Systems， 2010， 4（6）：597-608.
[3] Fdhila W， Indiono C， Rechert M. Dealing with Change in Process Choreographies： Design and Implementation of Propagation Algorithms[J]. Information Systems， 2015， 9（5）：55-106.
[4] Grossmann G， Mafazi S. Change Propagation and Conflict Resolution for the Co-Evolution of Business Processes[J]. International Journal of Cooperative Information Systems， 2015， 12（8）：102-140.
[5] Chen Y， Cheng P， Yin J. Change Propagation Analysis of Trustworthy Requirements Based on Dependency Relations[J]. 2010 IEEE International Conference on Information Management and Engineering， 246-251.
[6] Polyvyanyy A， Armas-Cervantes A， Marlon Dumas. On the expressive power of behavioral profiles[J]. Formal Aspects of Computing， 2016， 5（28）：597-599.
[7] 吳哲辉. Petri网导论[M]. 北京： 机械工业出版社， 2006： 9-15.
[8] Salay R， Gorzny J， Chechik M. Change Propagation due to Uncertainty Change[J]. Springer Verlag Berlin Heidelberg， 2013， 28（21）：21-36.
关键词：Petri网；库所系统；增加类型；单向影响关系；变化传播
中图分类号：TP391.9 文献标志码：A 文章编号：1009-3044（2018）02-0211-02
Change Propagation Analysis of the Add Type Based on the Place System
PENG Ke
（College of Mathematics and Big Data， Anhui University of Science and Technology， Huainan 232001， China）
Abstract： Change propagation plays an important role in many software fields. It is a difficult problem to analyze the change propagation range of some type of change. This paper presents a method of analyzing the change propagation influence range， which inserting a transition of add type into a place system Based on Petri net on a basis of unidirectional influence relationship. Firstly， take a taxi software as an example， build a place system for car-hailing software， and then insert a change transition of add type into the system. Secondly， the influence relationship between the original change set of the system and the inserted transition of add type， which is measured by the unidirectional influence relationship method. Finally， according to the formula of change propagation influence range of a transition of the above inserted add type， it is concluded that the change propagation influence range of an inserted transition of add type Based on the place system of a car-hailing software.
Key words： Petri net； place system； add type； unidirectional influence relationship； change propagation
1 背景
现今，变化传播分析是业务流程管理中的一个重要方面。而在不断变化的业务环境下，依据变化类型，量化变化传播范围则一直属于比较繁琐又很困难的一类问题。因为变化类型分为好几种，每种不同的变化在流程中生成或添加后，都会由于涟漪效应的多样性而形成各种截然不同的新流程。故从变化传播范围角度分析变化传播是一项刻不容缓的重任。
目前，关于变化类型和变化传播已有许多研究。文献[1]阐述了变化区域和变化传播的概念，并对它们之间的关系进行了简单的介绍。文献[2]从变化分类角度来动态评估变化区域对整个流程系统的影响。文献[3]提出了一种基于流程结构树通用的分散式变化传播方法，它同样也是根据变化种类促使变化传播持续使能发生。文献[4]解决了利益相关者在业务流程中因通过不同视角执行变化而导致的不一致现象。文献[5]则是在Petri网的库所系统中，基于置信度要求变量来分析并巩固变化传播并给出由内部可信赖属性生成的影响范围。
本文的整体结构如下：第一部分介绍文中所涉及的相关基本概念；第二部分为基于库所系统的增加变化类型变化传播范围分析；第三部分則是总结本文的贡献以及未来工作的结束语。
2 基本概念
这一部分主要介绍了与本文密切相关的概念，其他相关定义可参见文献[6]。
定义1[6]（Petri网）满足下列三个条件的三元组[N=（P，T；F）]称作Petri网：
1） [P]是一个有限非空库所集，[T]是一个有限非空变迁集；
2） [P?T≠?]，[P?T=?]；
3） [F=（P×T）?（T×P）]表示流关系。
Petri网三元组包括库所[P]、变迁[T]、流关系[F]。用图形表示Petri网时，以圆圈表示库所，矩形表示变迁。对于任意[x，y∈P×T]，若[x，y∈F]即[x]到[y]有一个流关系，则活动对之间用一个有向线段表示。为计算变化传播范围，下面介绍库所系统。 定义2[7]（库所系统）六元组[Σ=S，T；F，K，W，M]是一个库所系统（Place System），其中
1） [（S，T；F）]是一个网；
2） [W：F→{1，2，3，...}]成为权函数；
3） [K：S→{1，2，3，...}]成为容量函数；
4） [M：S→{1，2，3，...}]是[Σ]的一个标识，满足条件[?s∈S：M（s）≤K（s）]
用一个库所系统[PS]对一个系统建模时，五元组[S，T；F，K，W]描述系统的结构，标识[M]反应系统的状态，此五元组也成为库所系统的基网。
定义3[3]（增加类型变化）
[AddChangePattern：]= [Add（Fragment，pred，succ）]
变化类型共有大概四种，本文分散式计算中将会用到的就是定义3增加类型变化，它是通过在流程前承结点[pred]与后继结点[succ]之间插入一个新的变迁实现的。
3 基于库所系统的增加变化类型变化传播范围分析
当前，越来越多的市民和私家车踏入了某打车软件这一领域，这些打车软件使得闲置的私家车有了一番用武之地，司机也能挣得不少的外快。市民则因其便捷性和快捷性而更青睐于这一与出租车不同的打车方式。本文就以某打车软件和乘客的交互行为为例子，建立库所系统，以库所系统为基础，插入一个增加类型的变化变迁，并通过分析前驱后继变迁集影响关系来计算影响范围。图1即为定义3所描述的增加类型变化，是图2中变迁[t′]的变化类型。
[T={t2：使用此软件；t7：新用户验证；t8：老用户默认登录；t15：所定位位置为初始位置；t16：自选位置；t17：到达位置为目的地；t18：现在叫车；t19：预约叫车；t22：抢单；t23：收到车辆信息；t28：车主电话联系；t31：上车；t34：发送行车路线；t35：发送乘车金额；t38：无优惠券；t39：有优惠券；t40：付款}] 图2中所增加的变化[t′={ 决定不坐车}]
为计算库所系统的变化传播范围，本文将以衡量库所系统原变迁集与所插入的增加类型变迁之间的影响关系为基础。下面将介绍单向影响关系[5][M=（mt（i，j））]，
[mt（i，j）=1，ti与tj之间存在单向影响关系0，ti与tj之间不存在单向影响关系，1≤i，j≤n]
库所系统由此影响关系得到添加一个增加变化后，包含此变化及其前驱变迁的影响关系矩阵[M1]和包含此变化及其后继变化的影响关系矩阵[M2]，矩阵中的元素均由单向影响关系[M=（mt（i，j））]所组成。
增加一个变化[t′]后，包含此变化及其前驱变迁的影响关系矩阵为
增加类型变化传播影响范围的公式[8]为：
[CPIRA=M11M10，1 M21M2（0，1）×100%]，
其中[M1]和[M0，1]分别表示矩阵中的元素1以及元素0、1，而[M]则表示矩阵所包含元素个数。这个公式的意义就是根据计算前驱矩阵[M1]和后继矩阵[M2]中，含1即存在单向影响关系的数量占含0，1总数的比例之和的百分比，来展示增加类型变化在库所网中传播的影响范围。
由上述公式可以得到，本文基于库所系统插入一个增加类型变化的传播影响范围是：
[CPIRA=40961 22144×100%=19.4%]
4 结束语
尽管过去的研究在包括软件领域等企业管理范围内各个方面的变化传播分析都有所涉猎，却很少考虑到从每个变化类型分散式的一一计算这些变化所传播的范围，本文则从增加类型变化弥补了一部分的短板。本文将乘客在使用某打车软件时的交互行为来建立库所系统，同时在其中添加一个增加类型的变化变迁。之后引入单向影响关系，用以衡量库所系统原变迁集与所插入的增加类型变迁之间的影响关系。随之得出由单向影响关系组成的，包含此增加类型变化的前驱矩阵和后继矩阵。最后，再依据增加类型变化传播影响范围的公式计算得到本文基于库所系统插入一个增加类型变化的传播影响范围。在此研究的基础上，未来工作将从两方面展开：试用本文中的方法计算基于其他变化类型的变化传播范围；以运行时间，运行良好程度等方面来检验此法的优劣之处，扬长避短，发挥优势并改正缺陷。
参考文献：
[1] Demuth A， Riel-Ehrenleitner M. Co-evolution of Metamodels and Models through Consistent Change Propagation[J]. The Journal of Systems and Software， 2016， 111： 281-297.
[2] Gupta C， Singh Y， Singh D. A Dynamic Approach to Estimate Change Impact using Type of Change Propagation[J]. Journal of Information Processing Systems， 2010， 4（6）：597-608.
[3] Fdhila W， Indiono C， Rechert M. Dealing with Change in Process Choreographies： Design and Implementation of Propagation Algorithms[J]. Information Systems， 2015， 9（5）：55-106.
[4] Grossmann G， Mafazi S. Change Propagation and Conflict Resolution for the Co-Evolution of Business Processes[J]. International Journal of Cooperative Information Systems， 2015， 12（8）：102-140.
[5] Chen Y， Cheng P， Yin J. Change Propagation Analysis of Trustworthy Requirements Based on Dependency Relations[J]. 2010 IEEE International Conference on Information Management and Engineering， 246-251.
[6] Polyvyanyy A， Armas-Cervantes A， Marlon Dumas. On the expressive power of behavioral profiles[J]. Formal Aspects of Computing， 2016， 5（28）：597-599.
[7] 吳哲辉. Petri网导论[M]. 北京： 机械工业出版社， 2006： 9-15.
[8] Salay R， Gorzny J， Chechik M. Change Propagation due to Uncertainty Change[J]. Springer Verlag Berlin Heidelberg， 2013， 28（21）：21-36.