Page 167 - 《软件学报》2021年第5期

朱锐 等:基于完全有限前缀展开的行为等价过程树生成算法 1391

过程树生成算法的伪代码如算法 1 所示,它首先抽取活动关系,然后判断这些活动关系之间是否冲突,选择
优先级最高的活动关系,将该组活动重构,生成新的过程模型.不停的将过程模型进行重构,当过程模型只剩下
一个活动时,这个活动的名称就是过模型程 p 对应的过程树的前缀表达式.
算法 1. 过程树生成算法.
输入:过程模型 p=(C,A;F,M 0 ).
输出:过程树.
步骤:
processToPTree(p)
1. flag=true //变量 flag 用于判断每次循环时是否抽取出活动关系
2. while flag and p.A.size()>1 then
3. flag=false
4. get a relationship matrix RM with IdentifiesRelation(p) //计算过模型程 p 对应的活动关系矩阵 RM
5. if isConflictRelation(RM) then //判断过模型程 p 活动关系是否冲突,判断方法参考第 3.3 节
6. return ∅
7. end if
8. RL=getRelationList(RM) //获取优先级最高的活动关系,方法参考第 3.3 节
9. for each ◎(a 1 ,a 2 )∈RL then
10. if {a 1 ,a 2 }⊂p.A then
11. p=refactoringOfProcess(p,◎,a 1 ,a 2 ) //重构过模型程 p 中的活动 a 1 ,a 2
12. flag=true
13. end if
14. end
15. end while
16. if p.A.size==1 then
17. return p.A
18. end if
19. return ∅
3.2 活动关系判断

在建立行为等价过程树时,判断过程模型的活动关系非常关键,因此需要对活动关系的判断条件进行准确
定义.本文中使用了顺序(→)、选择(×)、并发(||)、迭代(∝)4 种关系来描述模型行为.为了构建一棵完整的行为
等价过程树,本文抽取出的活动关系需满足两个条件:(1) 该活动关系属于 4 种关系中的一种;(2) 所对应的两个
活动合并后不改变其他任何行为的活动关系.下面给出了满足该条件的这 4 种关系的判断条件.
定义 15(顺序关系判断条件). 对于过程模型 p=(C,A;F,M 0 ),Π=(o,h)为过程模型 p 对应的一个包含截断事件
的分支进程,其中,o=(S,T;F′)是一个出现网,h 是一个映射函数.∀t 1 ,t 2 ∈T,∀a 1 ,a 2 ∈A,h(t 1 )=a 1 ,h(t 2 )=a 2 ,当 t 1 ,t 2 满足下
述条件时,a 1 与 a 2 存在可重构的顺序关系,a 1 先发生,记为→(a 1 ,a 2 ).
(1) [t 1 ]=[t 2 ]−{t 2 },即 t 1 的配置与 t 2 的配置相比只相差 t 2 .
(2) h(t 2 )∉h([t 1 ]),即本地配置[t 1 ]映射到过程模型 p 中的活动集合不包含活动 a 2 .
(3) ∀t∈T 且 t≠t 1 ∧t≠t 2 ,当 h(t)=h(t 2 )时,必有 h(··t)=h(t 1 ),即只有 a 1 发生后 a 2 才可以发生.
(4) ∀t∈T 且 t≠t 1 ∧t≠t 2 ,当 corr(t)=t 1 时,必有 h(t)=h(t 1 )∧[t 2 ]=[t]−{t},即 a 1 与其他活动间不存在迭代关系.
(5) ∀t∈T 且 t≠t 1 ∧t≠t 2 ,必有{t 1 ,t 2 }∩[t]=∅或{t 1 ,t 2 }∩[t]={t 1 ,t 2 }.
定义 16(迭代关系判断条件). 对于过程模型 p=(C,A;F,M 0 ),Π=(o,h)为过程模型 p 对应的一个包含截断事件
的分支进程,其中,o=(S,T;F′)是一个出现网,h 是一个映射函数.∀t 1 ,t 2 ∈T,∀a 1 ,a 2 ∈A,h(t 1 )=a 1 ,h(t 2 )=a 2 ,当 t 1 ,t 2 满足下