Petri网建立在通用图论(general graph)之上,具备坚实的数学基础,并且能够直观、形式化地反映异步系统的执行语义,因而在实际工业生产和科学研究的过程中,被广泛应用于对业务过程模型的描述、表示和研究^[8,9]。Petri网描述的是包含动态信息的复杂系统,直接研究其行为空间非常困难。为了解决这个问题,Neilson^[10]和Engelfriet^[11]等人在Petri网的基础上提出了展开(unfolding)的概念,通过展开,可以将一个Petri网转化为一个从初始条件出发的简单、无环的数据结构。但是展开技术依然无法克服语义交织现象所导致的行为空间无限增长的问题。1995年, McMillan^[7]发现展开中实际包含了过多重复的结构和信息,通过截取展开中从初始条件出发到某些结点为止的“有限部分”,就可以去除这些重复的结构和信息,从而极大地压缩展开的大小。McMillan用“完全有限前缀”命名了这种“有限部分”,并且还证明完全有限前缀技术在压缩空间的同时不会造成原模型可达状态的丢失。完全有限前缀技术在模型检测领域有广泛影响和重大意义。Clark^[12]也提到过完全有限前缀技术。后来, Esparza^[13]等人对完全有限前缀技术进行了改进,使其在最坏的情况下,依然能够产生一个有限的前缀。与完全有限前缀相关的概念主要包括配置(configuration)、 切(cut)、 充足关系(adequate order)、 局部配置(local configuration)和切除事件(cut-off event)等。

定义1 展开 N=( B, E, F)的一个配置 C是由有限多个事件组成的集合,即 C⊆ E, 同时满足:

1) C是一个因果后向闭包,即 e∈ C∧ e'≤ e⇒ e'∈ C;

2) C中没有任何两个事件之间存在冲突关系,即∀ e, e'∈ C: ¬( e#e')。

C所代表的本质就是从网系统的初始条件出发,按照Petri网触发规则而形成的一个任务发生序列。Mark( C)代表该配置发生完后对应的标识。

定义2 设Σ是一个Petri网系统, ρ=( N, h)是 Σ的展开, ρ的每一个配置 C对应一个条件的集合,这个条件的集合就被称为一个切,即Cut _c=(Min( N) ÈC•) /• C。其中, C•和• C分别代表 C的所有后继结点和所有前驱节点。

由此可见,一个切唯一地确定 Σ的一个可达状态,即Mark( C) =h(Cut _c)。若一个展开中存在2个配置 C₁和 C₂, 且 Cutc1 = Cutc2, 则代表 C₁和 C₂之后的结构完全相同,这些相同的结构就是前面提到的在展开中重复的、需要被去除的信息。McMillan正是通过这种思想将无限的展开转化为有限的前缀。

当有2个不同的配置对应1个相同的切,完全有限前缀技术按照充足关系来决定舍弃哪一个配置之后的部分。

定义3 假设 Σ=( P, T, F, M₀)是一个Petri网系统,并且≺是定义在其分支进程中的有限配置上的一个偏序关系,那么≺是一个充足关系的条件是:

1) 对于任何配置 C₁和 C₂, 有 C₁⊂ C₂⇒ C₁≺ C₂;

2) 满足“保存性”,即对于有限扩展而言, ≺依然是成立的。

定义4 设 N=( B, E, F)是一个展开,一个事件 e∈ E的局部配置是一个事件的集合{ e'|e'∈ E∧ e'≤ e}, 记作[ e]。事实上,事件 e的局部配置[ e]就是包含 e的最小配置。

完全有限前缀的压缩标准就是基于局部配置的比较: 依据确定的充足关系,选取最小的局部配置,保留其后的部分,而对于其他的局部配置,则舍去其后续的部分,最后所得的结果就是完全有限前缀。

定义5 设 Σ是一个Petri网系统, ρ=( N', h)是 Σ的展开。若≺是一个定义在 N'上的充足关系,同时当且仅当 N'包含一个局部配置[ e']满足Mark([ e]) =Mark([ e'])并且[ e']≺[ e], 则事件 e是 N'的一个切除事件。

为了充分利用CFP技术既能高效压缩过程状态空间且不丢失任何可达状态信息的特点,同时克服其可能丢失部分任务间时序关系的缺陷,本文提出了“时序保存的完全有限前缀”的概念,即通过在切除事件及其对应的线索结点之间引入链接(link)来指示损失的时序信息。

在介绍时序保存的完全有限前缀之前,需要引入相关概念作为基础。

定义6 设 Σ=( N, M₀)是一个Petri网系统,其中 N=( P, T, F), 同时假设有 ρ=( N', h)为 Σ对应的展开,其中 N'=( B', E', F'), 于是存在:

1) 对 N的任意一个可达状态 M, 有Eq( M, ρ) ={ e∈ E'|Mark([ e]) =M}。在不导致理解混乱的前提下,本文都省略 ρ, 将Eq( M, ρ)简记为Eq( M)。

2) continuation( M)代表 ρ中的一个线索结点。对于每一个可达状态 M, continuation( M)定义为: 存在一个唯一的 e'∈Eq( M), 对于其他所有的 e∈Eq( M), 如果有 e≠ e'且[ e']≺[ e], 那么 e'就是continuation( M), 对于某一切除事件 e, 若Mark(Cut( e)) =M,那么

continuation( e) =continuation( M), 并称该点为切除事件 e的线索结点。

3) Off( M) =Eq( M) \continuation( M)表示对应于可达状态 M的所有切除事件。

接下来,可以通过引入从切除事件到其线索结点之间的链接来实现保持所有任务间时序关系的目的。

定义7 一个Petri网系统 Σ=( N, M₀)的时序保存的完全有限前缀是一个二元组( ρ, L), 记作 Γ_Σ, 其中:

1) ρ=( B, E, G)是 Σ的CFP;

2) L是一个链接的集合, L⊆ E×E。如果有( e, e')∈ L, 那么存在一个 Σ的可达状态 M使得 e'=continuation( M)并且 e∈Off( M)。

时序保存的完全有限前缀的生成过程如图1所示。其中,一个TPCFP的数据结构包括一个CFP和一个链接的集合,分别记作 FinΣtp .N和 FinΣtp .L。该算法的基本原理如下: 在完成TPCFP的初始化后,根据函数PE( N', h)(函数名是Possible Extension的缩写,表示依据触发规则从当前状态出发可能触发的变迁)的计算结果,逐步添加相应的结点和边到 FinΣtp .N中去。函数minimal( pe,≺)生成一个事件 e, e满足以下条件: e∈ pe并且就≺关系而言[ e]最小。函数expansion_required代表 e∩ cut_off=∅。函数

cut_off_event( e, FinΣtp .N, c)返回一个布尔型的值,判定 e是否是 FinΣtp .N中的一个切除事件。若是,则将与 e对应的线索结点存储到局部变量 c中,这样在添加链接的时候就不需要再做重复的比较和判定。最后,构造从切点到其对应线索结点之间的链接,添加到 FinΣtp .N中去。 XÈ: =Y代表运算 X=XÈY。

图1

	Figure Option ViewDownloadNew WindowDownload As Powerpoint Slide
	图1 TPCFP的生成算法

定义8 对于一个由工作流网表示的业务过程 Σ, 其中库所 i与库所 o分别是 Σ的源库所和结束库所,若存在一个变迁发生序列TS, 使得 M M', 并且 M( i)≥1∧ M'( o)≥1, 则该变迁发生序列为 Σ的一个过程实例。

定义9 过程实例表示图是一个四元组ρ'=(B',E',F',L'), 由时序保存的完全有限前缀ρ=(B,E,F,L)分解而得,其中:

1) ∃ i, o∈ B', 并且 ∙i<1∧ o∙<1;

2) B'⊆ B, E'⊆ E, F'⊆ F, L'⊆ L。

引理1 若一个时序保存的完全有限前缀有叶子结点 x₁和 x₂, 且 x₁ co x₂, 则 x₁和 x₂属于同一个过程实例,其中co代表两个节点之间为并发关系。

由引理1可知,对于一个时序保存的完全有限前缀而言,两个叶子结点 x₁和 x₂同属于一个co-set,是 x₁和 x₂属于同一个过程实例的充分条件,而非必要条件。之所以非必要条件,是由于循环中的选择结点(即输出大于1的条件结点)造成的。在一个时序保存的完全有限前缀 ρ中,若对于分属不同co-set的2个叶子结点 x和 y存在1个公共祖先条件结点 z, 同时存在链接 l( e, e')∈ ρ.L且 e≺ z≺ e', 则 x和 y依然可能属于同一个过程实例。因此,当时序保存的完全有限前缀 ρ中不包含循环结构或者循环结构中不包含分支条件结点的时候,过程实例表示图是从TPCFP的叶子结点集合中每个co-set出发,逆向追溯直到初始结点后,再添加相应的结束结点而得到的结果。在逆向追溯的过程中,如果出现某个分支条件结点 c, 并且 c包含在一个由链接 l构成的循环中,则需要从该分支结点后所有的co-set出发作逆向追溯,再向得到的结果添加相应的结束事件结点后,才能得到对应的过程实例表示图。

就产生TPCFP而言,算法1仅仅添加从切除事件到线索事件的链接,因此可以认为产生TPCFP的时间复杂度与产生CFP的时间复杂度是相同的,即都是关于Petri网中有向弧的数量的指数复杂度。而从一个TPCFP产生一组执行实例表示图的时间复杂度是一个关于该TPCFP的大小的线性关系,因为这是一个从该TPCFP的叶子结点作逆向遍历的过程。

为了评估本文提出的技术,基于BeehiveZ3.0系统(http://code.google.com/p/beehivez/downloads/list)开发了专门的测试模块用于产生过程实例表示图: 先将业务过程模型转换为对应的TPCFP, 再将这些TPCFP分解为一系列过程实例表示图。本文选择SAP公司定义的604个业务过程模型作为测试数据集。这组用EPC表示的业务过程模型是SAP公司用于指导其开发人员和技术顾问的标准参考模型集合,具备广泛的代表性和实用性。在实际测试的过程中,首先使用ProM(http://www.processmining.org/)将这604个EPC格式的模型全部转换为由Petri网表示的模型。转换的结果得到591个Petri网模型(有13个EPC模型不能被ProM转化,因此在实验中将它们忽略)。该集合的基本统计信息如表1所示。

实验平台的具体配置为: Intel Core i7-2600处理器; 8 GB内存; Windows 7 Ultimate操作系统; JDK的版本为7; JVM的Heap Memory设置为2 GB。

表1

表1

表1 SAP业务过程模型集合统计特征 指标 数量 模型数量 591 变迁数量 4 439 标签数量 1 494 平均变迁数量 7.5 平均库所数量 12.7 平均有向边数量 19.7

表1 SAP业务过程模型集合统计特征

经过BeehiveZ的运算, 591个业务过程模型被转化为3 134个过程实例表示图,平均每个业务过程模型对应5.1个过程实例表示图。这些过程实例表示图的基本统计特征如表2所示。每个过程实例表示图代表该业务过程模型一个或一组可能的过程实例。在代表一组过程实例的情况下,这组过程实例必定是由包含在循环结构中的分支条件结点引起的,相当于在一个循环结构的内部存在选择关系,因此这组过程实例的数量可能是无穷的。然而在实际工程和科学研究的过程中,对它们使用一个过程实例表示图来代表,会起到很大的简化作用。

表2

表2

表2 过程实例表示图集合统计特征 指标 数量 过程实例表示图数量 3 134 变迁数量 16 924 平均变迁数量 5.4 平均库所数量 9.6 平均有向边数量 11.8

表2 过程实例表示图集合统计特征

在实验中,产生TPCFP并对其进行分解的总时间消耗是507 s, 即平均0.85 s就可以分解出一个业务过程模型的所有过程实例表示图。就空间复杂度而言,在本文的实验中,存储这组SAP模型集合所对应的TPCFP所占用的空间是23.9 MB,由于业务过程模型管理技术的应用主体通常都是企业级的用户,对于拥有成千上万个业务过程模型的机构来讲,这样的存储空间代价是完全能够承受甚至是微不足道的。

本文介绍了分解过程实例表示图,用以代表业务过程模型所有过程实例的相关技术。该技术基于改进的完全有限前缀实现,通过引入切除事件与线索事件之间的链接,从而保留所有的任务间时序关系; 然后从TPCFP的叶子结点集合中的每一个co-set出发,逆向追溯整个TPCFP直到初始状态,可以得到该业务过程模型所有过程实例表示图。过程实例表示图在基于行为语义的模型查询、一致性检验和相似性匹配等方面都有广泛的用途。下一步将实现一个图形化的业务过程查询语言,从而实现更加有效的应用。