流程变体向可配置流程模型的变更传播

刘霖岳,欧阳春,何克清,郭 曦+,冯在文,4,5,沙 瀛,王腾辉

(1.华中农业大学 信息学院,湖北 武汉 430070；
2.昆士兰科技大学 信息系统系，澳大利亚 布里斯班 4000；
3.武汉大学 计算机学院,湖北 武汉 430072；
4.华中农业大学 宏观农业研究院，湖北 武汉 430070；
5.武汉大学 杂交水稻国家重点实验室，湖北 武汉 430072)

近20年，业务流程管理技术发展迅猛，其在工作流系统[1]及服务计算领域[2-4]均有广泛应用。随着各业务部门之间频繁的合并重组，越来越多的企业选择共同发展多个业务流程的变体(通常来自不同公司或部门，彼此之间存在联系但不相同)并最终将其融合为一个可配置业务流程，从而在很大程度上消除冗余，使这些变体协同工作，共同发挥作用。因此，很多企业构建了专门的业务流程分析团队来比较各流程模型，找出其共性和差异，以此为依据对变体进行合并，从而创建可用于推动流程整合工作的集成业务流程模型。多个变体合并后的模型称为可配置业务流程模型(configurable process model)[5]。人工进行流程模型合并是一项繁琐的任务，不但会耗费很多工时，而且在很多环节都容易出错。ROSA等[6]提出一种有效的自动化业务流程合并方法，通过可配置业务流程模型，业务分析师可以清楚地分析各个流程变体(process variant)之间的共同点和差异。然而，在某些情况下，流程变体合并后可能因各种原因而面临修改，修改后的变体与原变体之间会有差异，无法对应之前的可配置业务流程模型，业务分析师希望能够记录发生在流程变体上的修改操作，及其对可配置业务流程模型产生影响的区域，以持续保证流程变体与可配置业务流程模型之间的可追溯性(traceability)，实现业务流程模型家族的协同演化(coevolution)。

已有学者对业务流程模型家族的协同演化方法进行了研究。ROSA等[6]提出一种以可配置业务流程模型为中介的流程家族协同演化方法，并提出支持业务流程家族协同演化的初步变更元语(change primitives)和清洁操作，该方法以可配置业务流程模型为中介，先将流程变体上发生的修改同步到可配置业务流程模型上，再将可配置流程模型上的变更同步到其他流程变体上，从而实现业务流程家族的协同演化，然而所定义的变更元语和清洁操作并不完整，而且是非形式化的。

针对业务流程模型家族变更传播问题中存在的问题，本文提出一种流程变体向可配置业务流程模型传播变更的方法。首先，定义了标准化流程变更元语，以描述流程变体和可配置业务流程模型中发生的一系列变更，在此基础上设计了一系列算法，将流程变体上发生的变更以正确的方式传播到可配置业务流程；
其次，实现了所有变更元语和流程变体到可配置业务流程模型上的变更传播算法，并将变更传播模型集成到国际大规模、开源的高级业务流程仓库APROMORE(advanced process model repository，https://github.com/apromore)[7]中；
最后，通过在SAP公司604个R/3业务流程模型[8]上进行实验，表明本文方法可以在极低的时间耗费下完成95%以上的正确传播。

为了说明变更传播达到业务流程家族协同演化的研究动机和效果，本文研究一个来自SAP公司参考模型的关于Excel数据处理的案例[8]。

1.1 数据处理流程说明

数据处理流程包括两个流程变体，如图1所示。

流程变体1描述对行数据的处理方式，分为人工清算和自动清算，人工清算可以直接结束，而自动清算有未发现数据和发现数据两种情况，若发现数据则同时报告清算完成和数据已清空。

流程变体2描述了一个Excel数据处理系统，其可以同时处理行数据和列数据，数据进入一个清算系统后根据不同情况分为人工清算、自动清算和未发现数据3种。

最后的流程模型是将两者合并后的可配置业务流程模型，可见两个变体表示的流程最终由一个完整的流程图表示，其中为了简化合并模型，在不影响功能的前提下对一些变体的点进行了修改。

1.2 变更传播示例

面对不同需求时，变体上可能产生不同的变化，如图2所示。由于某些原因，行数据可能存在错误信息需要删除，期望在变体1“人工清算”和“自动清算”前的连接器后再追加一个新的事件“数据错误，已清空”，从而使变体1发生改变，如果重新将其与变体2合并，虽然可以将变体1的变更传播到可配置流程模型上，但是重新合并意味着需要再次进行一次计算复杂度较高的流程合并过程。实际上，如果将变体1发生的变化直接传播到可配置业务流程模型，则可避免再次合并引起的大量重复计算。如图2左上流程模型所示，“数据错误，已清空”事件(加粗并划线)已经被追加(append)到最左边的网关之后，旁边的标签表示其为属于变体1的事件。

本文的流程变体向可配置流程模型传播变更的方法主要包括3部分，即对可配置流程模型的修改操作、从变体到可配置业务流程模型的传播操作和完成传播后的流程图清洁操作。

2.1 流程模型的修改操作

首先定义一组针对流程模型的修改操作，包括对流程变体的修改操作和对可配置流程模型的修改操作。

针对流程模型的底层(low-level)修改操作包括添加边操作、删除边操作、修改边注释操作、添加点操作、删除点操作、修改点注释操作6种。在添加边操作中，首先要得到待添加边的起点和终点，并判断添加后是否合法，若合法则可添加；
删除边操作先将边删除，再判断该边的起点和终点是否因该边的消失而变为孤立节点，是则将其删除；
已知添加点和删除点一定伴随着边操作，因此只简单定义了在图的点集中添加、删除点的操作，它们一定会与边操作结合；
最后是更新点、边注释操作，找到对应的点后直接更新即可，更新边注释同理。

完成基本修改操作的定义后，在附录中定义了合并模型的高级(high-level)修改操作，共有9种高级修改操作：

(1)插入边注释 即在一条边的注释上再插入某段注释。

(2)删除边注释 即删除某段边的边注释，如果删除后边的注释为空，则清洁操作会删除这段边。

(3)插入点 即在两个点的边上再插入一个点，需要根据该插入点出边上注释的个数分类讨论。

(4)添加点 即在两个连接器之间增加一条只有一个点的路径。

(5)预/追加点 即在某个点前/后再加上一个点，这两个操作比较相似，将其合并为一个操作。

(6)改变边 即将某条边移动到另一个位置，可以看作“添加边”和“删除边”的组合。

(7)移除点 该操作不会单独出现，一般伴随着删除边操作，即删除某点及其所有边。

(8)添加边 即在两个点之间添加一条边。

(9)删除边 即删除两个点之间的一条边。

以上针对流程模型的高级修改操作是执行变更传播操作的基础，传播时需要调用这些高级操作来修改流程变体和可配置业务流程模型。

2.2 流程变体到可配置流程模型的传播操作

算法1变更传播的判断与实现。

2 begin

3 if(CO=="InsertEdge")then

6 end

7 if(CO=="DeleteEdge")then

9 end

10 if(CO=="UpdateLabel")then

12 if(|α(pv1, v1)|=1|||α(v1,sv1)|=1)then

13 αCG(v1)=αG(v)

14 end

15 else if(|α(pv1, v1)|> 1 && sv1=∅)then

16 m=(c,XOR)

17 InsertNode(pv1,v1,m,CG)

18 AppendNode(m,G.v,CG)

19 αCG(m,v1) αG

20 end

21 else if(|α(pv1,v1)|>1&&|α(v1,sv1)|>1)then

22 m=(c,XOR), n=(c,XOR)

23 InsertNode(pv1,v1,m,CG)

24 InsertNode(v1,sv1,n,CG)

25 AddNode(m,n,G.v,CG)

26 αCG(m,v1) αG

27 αCG(v1,n) αG

28 end

29 end

30 if(CO=="AppendNode")then

32 if(τ(vp)∈{e,f} && |α(pv1,v1)|>1)then

33 m=(c,XOR)

34 InsertNode(pv1,v1,m,CG)

35 AppendNode(m,v2,CG)

36 αCG(m,v2)αG

37 end

38 AppendNode(v1,vs,CG)

39 end

40 if(CO=="AddNode")then

42 AddNode(v1,v2,v,CG)

43 αCG(v1,v)=αCG(v1,v)∪αG

44 αCG(v,v2)=αCG(v,v2)∪αG

45 end

46 if(CO=="InsertNode")then

48 if(|α(v1,v2)|>1)then

49 m=(c, XOR),n=(c,XOR)

50 InsertNode(v1,v2,m,CG)

51 InsertNode(m,v2,n,CG)

52 v1=m,v2=n

53 end

54 InsertNode(v1,v2,v,CG)

55 end

56 end

根据变更操作CO可以判断将执行的传播操作，算法共定义了6种传播操作：

(1)插入边传播操作 传播时在CG的对应点之间插入一条边并添加G的注释即可。

(2)删除边传播操作 传播时清除CG对应边上关于G的注释，若清除后边注释为空，则在清洁操作中删除该边。

(3)更新点注释传播操作 该操作要分多种情况执行：若该点入边或出边上的注释不大于1，则直接更新；
若入边的注释大于1而无出边，则在该点前插入一个连接器并删去边上关于G的注释，然后在连接器后追加G中更新了注释的点；
若出边的注释大于1而无入边，则与上文的操作相反，算法中略去；
若入边和出边的注释均大于1，则在该点前、后各插入一个连接器，然后在两连接器之间新增一条只有G中更新了注释的点的路径，最后删除相关边上的注释。

(4)追加点传播操作 传播时在CG对应点后追加一个节点即可，但要注意，如果该对应点为“事件”或“函数”且其入边的注释大于1，则在其前面插入一个连接器，并在连接器后新增一个该对应点的复制，在复制点的后面追加点。另外，预加点的流程与其基本相似，因此在算法中略去。

(5)添加点传播操作 操作集中对AddNode的判断需要在最开始进行，因为满足AddNode的条件也一定满足AppendNode。传播时要在CG中找到v的父节点和子节点的对应点v1，v2，在两者之间添加一条只有v的路径，然后添加边注释即可。

(6)插入点传播操作 传播时要在CG中找到v的父节点和子节点的对应点v1，v2。若两者之间边的注释大于1，则在两者之间插入两个连接器，在连接器之间的路径上插入新的点v；
若两者之间边的注释不大于1，则直接在路径上插入v。每种情况最后都需要修改边注释。

2.3 流程图清洁操作

在完成流程变体到可配置流程模型变更传播后，可配置流程模型可能因变更传播而产生一些不合法的部分，如冗余连接器、孤立节点、无注释边等，因此定义了清洁操作，删除变更传播后可配置流程模型上不合法的部分。清洁操作如算法2所示。

算法2清洁操作。

1 function CleanGraph(Conf.Graph CG)

2 begin

3 foreach τ(NCG.v)=="c" do

4 if(|pv|>1 && |sv| > 1)then

5 v1=(v.type)

6 InsertEdge(v1,sv,CG)

7 DeleteEdge(v,sv,CG)

8 InsertEdge(v,v1,CG)

9 end

10 if(|pv|<1&&|sv|<1)then

11 InsertEdge(pv,sv,CG)

12 αCG(pv,sv)=αCG(v,sv)

13 DeleteEdge(v, sv,CG)

14 DeleteEdge(pv, v,CG)

15 RemoveNode(v)

16 end

17 end

18 if(α(ECG.e)=∅)then

19 DeleteEdge(e.vp, e.vs, CG)

20 end

21 if(p(NCG.v)=∅&& s(NCG.v)=∅)then

22 RemoveNode(v)

23 end

24 end

该算法的唯一输入是变更传播待清洁的可配置流程模型CG，算法在得到输入CG后会检测可配置业务流程模型中的几种不合法情况并进行改正：

(1)若一个连接器v同时有多个子节点和父节点，则创建一个与其同类型的连接器v1，在v1和v的所有子节点之间插入边，插入边的注释等于v与v子节点之间边的注释，然后删除v与其子节点的所有边，最后建立一条v到v1的边。

(2)若一个连接器的子节点数和父节点数都不大于1，则认为该连接器为冗余连接器，直接删除该连接器及其与父、子节点的边，然后将其父、子节点连接起来。

(3)若一条边的注释为空，则直接删除该边，但要注意删除后可能出现更多不合法的情况，需要重复检查。

(4)一个没有出边也没有入边的点称为孤立节点，应直接删除。

清洁算法完成后，便可将更新后的可配置流程模型返回用户。该合并模型会生成一个新的版本并保留之前的旧版本，分别对应传播前和传播后。同时系统会建立新的模型对应关系，发生变化的变体也会同时创建一个新的版本与总体对应，用户之后的修改将在新版本对应的流程模型上进行。

在完成流程变体向可配置流程模型的变更传播操作和清洁操作后，以传播操作和清洁操为基础，构建业务流程变更传播管理器。该管理器的框架如图3所示，分别由Signavio GUI，Cpf2Graph Service，Graph Comparison Module，Change Propagation Manager，Graph Change Module，Graph2Cpf Service 6个组件组成，每个组件的具体作用以及修改的整体流程如下：

(1)用户通过Signavio GUI修改变体并发出变更传播请求，系统将被修改的变体和原变体一起传入Cpf2Graph Service，得到流程变体对应的有向图。

(2)在Graph Comparison Module的作用下，用户得到变体发生变更的变化操作集；
接着，通过Change Propagation Manager，根据变体的变更集合获得可配置业务流程模型的变更集合。

(3)由Graph Change Module根据变化集修改可配置业务流程模型。

(4)用Graph2Cpf Service将修改后的可配置业务流程模型对应的有向图转化为可配置业务流程模型，并通过Signavio GUI呈现给用户，完成从变体到可配置业务流程模型的变更传播过程。

流程变更传播模块已经集成到业务流程模型管理系统APROMORE(https://apromore.org/)[7]中。

为了证明并评估所提方法的普适性和实用性，采用SAP参考模型的数据集进行实验。该数据集包括604个事件驱动流程链(Event-driven Process Chain, EPC)格式的流程模型，这些SAP EPC参考模型不可配置，因此首先采用一种图的相似度计算方法得到每个图之间的相似度，然后采用凝聚层次聚类(Agglomerative Hierarchical Clustering, AHC)算法，根据其相似度进行聚类，共得到40个流程类簇，经过筛选和处理，舍弃30个EPC模型，并在剩余类簇中选择20对模型作为变体，采用文献[6]的模型合并方法进行两两合并，得到20个可配置业务流程模型及其对应的流程变体构成的业务流程家族，其中每个业务流程家族含有两个变体和一个可配置业务流程模型。下面用这20个业务流程家族进行变更传播实验。

4.1 普适性评估

对每个流程家族进行9项变更传播操作，以验证算法是否对每种流程模型都有效且准确。除之前算法中列出的6项，还有“预加点”“移动边”“移除点”3项，这9项传播操作目前可以涵盖业务流程建模标注(语言)(Business Process Modeling Notation，BPMN)模型变体到总体的几乎所有变更操作，且遵守BPMN规则[9]。另外，传播操作引起的合并模型上的变化并不总是与变体上的变化相同，需要从多种情况讨论传播的实施，以“更新点注释”为例，修改变体时只有一个点的注释发生变化，修改合并模型时需要根据其出边和入边的边注释的数目分为4种情况，有些情况可以直接更改合并模型中点的标签，有些情况则需要插入多个连接器来保证图的正确性。传播操作在合并模型上的操作是复杂多变的，某个复杂的模型经过传播有可能产生错误的合并模型，因此安排一位操作员对传播后的总体进行判断，以确定传播正确与否。表1所示为9项操作在20个模型集上变更传播的正确率。

表1 传播操作在各模型集上的正确率 %

可见，“插入边”“删除边”“移动边”的普适性和正确性很高，原因是这3种传播操作相对简单，不需要考虑连接器和边注释等复杂因素，只要在合并模型中找到变体中变化边的起点和终点所对应的点，对两个对应点之间的边进行操作即可。然而剩下有关点的操作仍存在各种问题，例如当原始的流程图不合法时，所有点操作都将无法进行；
当被添加点的节点的子节点或父节点存在连接器时，传播后的合并模型可能存在错误，原因是对连接器和节点的组合情况考虑不全面；
当插入点和修改点注释的相关点的出边和入边上的注释不唯一时，变更传播也可能会发生错误，原因是未能完整列举出对有多个注释的边进行修改的所有情况；
移除点时最容易发生传播错误，原因是很多模型不存在可以移除的点，如果强行移除则会引起BPMN模型语法错误，导致传播无法进行。

根据表1数据来看，95%以上的传播操作是可以进行的，而且拥有平均90%的正确率，因此认为传播操作是普适且正确的，可以满足绝大多数需要修改变体的情况。当仅进行边修改操作时，几乎可以认为传播完全正确，而进行点操作时，只要操作合法，传播的正确率即可达到90%以上，但还是无法保证完全可靠，需要人为检查传播后的模型正确与否。另外，以上数据中有部分图因为规模和内容问题无法进行全部9项操作实验，所以将其从基数中减去。

4.2 实用性评估

本节评估传播算法的实用性，即用变更传播得到的合并模型比重新合并两个变体得到的合并模型耗时更少。为此统计了在20对模型上9项操作的变更传播时间及重新合并模型的时间，结果如表2所示。需要说明的是，文献[6]中的模型合并方法基于最大公共区域，因此修改变体引起的合并用时的变化可以忽略，即修改后的合并用时等于先前的合并用时。

表2中加粗的“F”表示传播错误，加粗划线的耗时表示该耗时比重新合并模型耗时更多，“/”表示该模型无法测试该传播操作。可知绝大多数情况下传播操作的耗时比重新合并模型的耗时少得多，9项传播操作的平均耗时仅占重新合并耗时的29.6%，证明了传播操作的实用性。有关传播耗时比重新合并模型耗时更多的情况，可能由于图的规模太小，导致传播耗时和合并耗时相差不大，从而被其他细微因素影响。另外，耗时异常的情况常出现在“添加点”这一操作上，可能是算法设计时存在漏洞，还需进一步改进。

综上所述，尽管传播操作目前还存在某些问题，无法保证点操作百分之百正确，而且极少情况的耗时多于重新合并耗时，但是绝大多数情况能满足普适性和实用性需求，未来将继续优化和完善传播算法，进一步提升正确率和效率。

表2 各模型集上的耗时统计 μs

近年来，业务流程模型家族的变更传播问题研究得到了业务流程管理领域的广泛关注,澳大利亚南澳大学GROSSMANN等[10]提出一种作用于公共参考模型(common reference model)和流程视角(process view)之间的变更传播框架，并提出在不同视角之间进行一致性检测的方法，然而该方法并不适用于可配置流程模型和流程变体之间的变更传播。

更多学者针对业务流程仓库(business process repository)中相似流程的变更影响和传播问题进行研究[11-13]。DAM等[11]对业务流程仓库中的流程变更对其他流程产生的级联影响(ripple impact)问题进行了研究，该方法首先对业务流程模型活动的前置条件和效果进行语义标注，通过计算累计效果(cumulative effects)和一种基于依赖的影响分析方法来分析流程与子流程以及流程之间的协同变更影响；
相比文献[11]，本文方法不需要在流程模型之间预先定义跟踪链，但是语义推理的时间开销更高；
FENG等[12]提出一种面向方面的业务流程家族协同演化方法，该方法将协同演化信息封装在插件(plug-in)中，通过面向方面的技术将插件插入业务流程家族，实现了流程家族的协同演化;WEIDLICH等[13]提出一种基于流程行为画像(behavioral profile)的流程模型家族变更传播方法，当流程仓库里某流程变更版本时，该方法抽取流程行为画像的变更，决定流程仓库中相关流程的变更区域，完成整个业务仓库中流程的协同演化。

宋巍等[14]提出一种业务流程变更管理框架，本文方法属于该框架中设计期业务流程家族协同演化的范畴。另外，宋巍等[15]提出一种基于轨迹追踪的数据迁移有效性检查方法，使流程发生动态演化后产生的新版本可以正确执行并产生预期结果[16]，而且可以判断其迁移的有效性，当更改超出业务流程的范围时，还应考虑环境属性等因素，如合作共同编排服务[17]等，这些工作为今后进行可配置模型变更传播的正确性验证提供了思路。

本文提出一种从流程变体到可配置业务流程模型之间的协同演化方法。首先，定义了作用于流程变体和可配置业务流程模型上的7个流程变更元语；
然后，设计了从流程变体到可配置业务流程模型传播方向上的变更传播算法；
接着，提出变更传播算法的模块架构，并将变更传播模块集成到Apromore系统中；
最后，用实验证明了本文方法的正确性和普适性。

未来工作主要包括3部分：

(1)本文所提算法将流程变体上单个变更操作传播到可配置业务流程模型上，然而流程变体的改变可能由一个变更操作序列构成，未来将研究如何将发生在流程变体上的变更操作集合传播到可配置业务流程模型上。

(2)检测并消解变更传播带来的不一致性问题。

(3)将可配置业务流程模型上的变更操作传播到各个流程变体上进行研究。