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

1386 Journal of Software 软件学报 Vol.32, No.5, May 2021

Abstract: The process tree has both the behavior and the structure of process model, and it is significant on simplifying the complexity
of the process model. Existing methods can only transform the block structured process model into process tree. However, it is difficult to
transform process model with complex structure into process tree. To solve this problem, a generating algorithm for the behavior
equivalent process tree based on complete finite prefix unfolding is proposed. The algorithm is used to transform the process tree in
behavior equivalent's process model into behavior equivalent process tree. This algorithm analyzes the process model based on an
incomplete prefix unfolding technique and extracts the relationships between process model activities. After analyzing the activity relation,
the algorithm reconstructs the process model. The behavior equivalent process tree is constructed through activity relation judgment and
the iterative operation of model reconstruction. The validity and feasibility of the proposed algorithm in the generation of behavioral
equivalent process tree are verified by experiments on the test model.
Key words: process model; complex structure; Petri net; process tree; complete finite prefix unfolding

伴随着“工业 4.0”和“中国制造 2025”而来的产品设计、生产装备、产品研发、感知设备等多个生产环节
都与过程控制技术紧密相关.过程驱动的基本思想在当前工业 4.0 的生产开发中的作用日益凸显,然而在实践
中业务过程模型却呈现海量特征、模型节点过多、行为难以分析等问题.例如,目前 SAP 参考模型大概有 600
[1]
多个;中国北车集团过程模型库中已累积约有 20 多万个;澳洲 Suncorp 银行约有 6 000 多个过程模型 .荷兰一
[2]
家信息通信技术企业的实施软件变更管理系统的日志包含案例数多达 4 万个,其中事件数达到 37 万 .面对如
[3]
此海量的过程模型和活动数,模型往往会呈现出一种“意大利面式”的复杂结构 .针对此类复杂的过程模型,如
何有效地提高复杂模型的可理解性是亟待解决的问题.
目前,降低模型复杂性常用的方法有两种:模型频繁行为模式发现 [4−6] 和精简模型结构 [7−9] .前者强调从模型
执行后的日志中去挖掘模型中的关键路径,去除噪声和非频繁日志所带来的低频次行为依赖,从而减少模型规
模.这种方法能有效保留模型中发生次数较多的行为,但也可能去除掉非频繁的关键行为,理想状态下能够有较
好的结果.后者精简模型结构主要强调从细粒度的过程模型中去发现高层次的粗粒度的模型结构,常用到的技
[9]
术包括模型优化 [7,10] 、模型合并 以及事件聚类 [11] 等.综合上述文献可知,无论是频繁行为模式发现还是对模型
结构进行精简,在一定程度上都会对模型的行为造成损失.这使得一些对模型质量要求较高的领域,无法容忍模
型行为损失的关键过程(比如软件开发版本的重要分支过程),上述两种降低模型复杂性的方法并不适用.
当前过程模型最常用的形式化表达工具是 Petri 网 [12,13] ,虽然其建模优势在于能够描述真并发、具有图形
化描述、具有严格的执行语义等 [14] ,但却时常会由于冗余结构增加了模型的复杂性.为此,本文将聚焦在基于
Petri 网建模的过程模型生成行为等价过程树的表达方法,其中行为等价即π演算中模型间轨迹等价的思想,具
体定义可参见文献[15].通过结构相对清晰的过程树来表达过程模型,同时尽可能保存模型的行为,以此来降低
“意大利面式”复杂结构所引起的模型不易理解问题.
为了在保留行为特征的同时,尽可能降低模型结构所带来的复杂性,我们引入过程树 [16] 来表示过程模型,这
种过程树不仅可以避免这些不合理的构造,还可以兼具过程模型的行为,简化模型的复杂度,有利于直观地对模
型进行分析.过程树是一种包含了过程模型信息的树形结构图,过程树不仅有对应的健全模型表示,也支持基本
的控制流模式 [16] .在过程树中的叶子节点代表活动,分支节点代表活动关系,过程树中任意两个活动(叶子节点)
的关系即它们最近的公共父亲节点.例如图 1 中的模型 P 0 里的活动 t 1 和 t 2 之间是并发关系,因此将其转化为过
程树后,过程树中的叶子节点 t 1 和 t 2 最近的公共父亲节点是并发.将基于 Petri 网描述的过程模型转化为行为等
价过程树的意义在于:
(1) 过程树作为一种树形结构的表示,利用它来描述一个过程模型,结构清晰简单,对模型结构精简工作具
有重要帮助.
(2) 过程树可以使用结构化的形式语言直接表达,它在过程模型的检索与存储的领域具有重要意义.当前
过程模型通常是以图的形式进行存储,不利于直接对模型进行数据库的管理操作,通过结构化的过程树可以快
速地对模型进行查找.
(3) 过程树不仅可以描述过程模型的重要行为特征,更能进一步描述模型的整体行为信息.这有利于理解
模型的整体行为结构.