2015, Vol. 26
2. 东华大学 计算机科学与技术学院, 上海 201620
2. School of Computer Science and Technology, Donghua University, Shanghai 201620, China
以数据为中心(data-centric)是业务流程管理(business process management,简称BPM)发展的新趋势.传统业务流程模型[1, 2]重点是对控制流进行建模,对数据的设计仅处于辅助地位.一些建模方法将数据设计提高到与控制流设计同等重要的位置.其中,以Artifact[3]为中心的BPM是一个典型的代表.近年来,国内外研究学者对以Artifact为中心的业务流程建模[4, 5]、模型分析[6, 7]等展开了深入研究,并取得了显著成果.与传统BPM一样,为确保业务流程建模及运行的正确性,Artifact行为一致性检测是继流程建模、模型分析之后亟待解决的关键问题之一.
一致性检测技术[8, 9]是对已知流程模型及其运行后的事件日志进行映射分析,检测流程模型中是否存在违规操作与不一致现象.目前存在很多一致性检测方法[10-12],这些方法都是基于Petri网原理进行建模和分析,即:给定一个流程的Petri网模型及其执行的事件日志,通过将事件日志还原为Petri网模型,然后对两个Petri网模型进行一致性分析.基于Petri网模型的检测机制存在模型语义过于严格的缺陷,导致很难做出更精确的分析.文献[13]提出一种与模型无关的事件平衡分析方法来避免Petri网模型的局限性,但是由于在流程模型中条件设置的多样性,使得进行事件平衡数的计算比较复杂.Gunther等人[14]通过定义自适应模型(adaptive model)解决了这个问题.基于模糊模型的语义有时会过于松弛,Adriansyah等人[15]提出一种灵活模型(flexible model)进一步解决了模糊模型存在的不足.在行为一致性检测中,确切度(fitness)[15, 16]是对行为一致性进行量化的重要指标,确切度是否精确,直接影响对流程模型的评测结果.Adriansyah等人[16]提出一种基于成本(cost-based)分析技术来度量流程模型和事件日志之间的确切度,然而该技术也只针对流程中任务执行的成本进行了分析.为了保证检测结果的精确度,同时降低计算复杂度,Munoz-Gama等人[17]提出一种层次检测方法.该方法先将复杂模型分解成若干可交互的子模型求解,然后再对子模型进行合并.以Artifact为中心的业务流程中,Artifact之间存在多对多(many-to-many)的交互模式[18];并且,一个Artifact类型[19]是由其数据对象模式和生命周期模式两部分组成.上述检测方法都着重检测流程模型中的任务(服务)是否一致,而忽略了数据操作方面的一致性检测.文献[20]提出一种Data-process Graph(DP-graph)模型,有效地实现了面向业务流程的数据模型异常检测.但是该模型只针对流程模型中的数据进行了静态异常检测,并未能实现对运行后的数据进行一致性检测.
在行为一致性检测过程中,忽略流程模型中数据操作方面会降低检测结果的精确度.例如采购审批业务流程中,采购申请单(purchase request,简称PR)是业务流程中的关键Artifact.图 1给出的是PR完整生命周期的Petri网模型M,图 2是对PR实际运行后的日志进行还原的Petri网模型L.
 | Fig. 1 Complete lifecycle of PR represented by Petri net图 1 PR完整生命周期的Petri网模型 |
 | Fig. 2 Petri net model replayed by process logs图 2 PR执行日志的还原Petri网模型 |
根据已有一致性检测技术分析,M和L所执行的任务是一致的,即:
M.t1«L.t1,M.t2«L.t2,M.t3«L.t3,M.t4«L.t4,M.t5«L.t5,M.t6«L.t6.
然而,当考虑到Artifact数据对象属性赋值时,M和L中PR属性赋值并不完全一致.从图中可以看出:L中任务t1执行后未对属性ApplicantDate进行赋值,而任务t2和t4执行后的属性赋值也与M中不一致.实例表明,仅从模型中任务角度考虑一致性问题是有片面性的.
综上所述,在Artifact行为一致性检测过程中,不仅要考虑业务流程执行过程中服务路径是否一致,同时还要考虑Artifact属性赋值是否正确.为此,首要解决以下几个关键性问题:
(1) 如何形式化描述Artifact的行为及Artifact行为一致性问题?
(2) 如何设计一种验证模型,使其能够同时对服务路径和Artifact属性赋值状态进行检测?
(3) 如何精确计算确切度?
针对以上问题,本文提出了一种基于Artifact快照序列的行为一致性检测方法.该方法的主要思想如下:
· 第一,利用Artifact快照序列描述Artifact行为.现有流程行为描述模型(如fuzzy model、flexible model等)虽然简单明了,但在描述Artifact行为上明显不够完整.一个Artifact快照是在完整生命周期内,某一时刻t,执行某一服务S时Artifact数据属性赋值的状态.Artifact快照序列不仅体现了服务的运行轨迹,也描述出了Artifact数据属性赋值的状态变化;
· 第二,将Artifact行为一致性检测问题转换为语言可判定问题,证明了该问题是一个可判定问题:首先,利用已知模型推导的Artifact快照序列定义语言;然后,构造一台判定该语言的图灵机作为一致性验证模型;最后,将实际执行后的快照序列在该模型上进行模拟,模拟过程中不仅检测了Artifact生命周期中服务路径的一致性,也检测了生命周期中Artifact属性赋值的正确性;
· 第三,利用Artifact的行为模式构造服务-快照关联矩阵.通过服务-快照关联矩阵的等价转换操作计算确切度.服务-快照关联矩阵元素中包含了服务和Artifact属性赋值结果,提高了计算确切度指标的精确度.
1 相关理论以Artifact为中心的业务流程模型[3]主要包含Artifact类型、服务和仓库等基本元素.Artifact[7]是一个可标识、自描述的数据单元实体.一个Artifact类型由Artifact模式(即数据模式)和生命周期模式两部分组成.服务用来操作业务流程中的Artifact,仓库用来存储Artifact生命周期各个阶段的状态.一个服务根据业务规则对Artifact进行属性值的添加、更新和归档等操作.每个服务执行后都产生一个Artifact实例,并将其存储到相应的仓库中.下面给出相关的定义.
定义1(以Artifact为中心的业务流程模型,Artifact-centric busienss process model). 以Artifact为中心的业务流程模型M定义为一个多元组(S,C,Ep,Ea,O,R1,R2,R3,R4,R5,R6;f1,f2,f3,f4,f5;H0),其中,
1) S={s1,…,sns}为服务元素的有穷集;
2) C={c1,…,cnc}为仓库元素的有穷集;
3) Ep={e1,…,enep}为产生事件的有穷集;
4) Ea={e1,…,enea}为接收事件的有穷集;
5) O={o1,…,ono}为外部仓库元素的有穷集;
6) R1ÍSxC:表示服务元素和输出Artifact之间的关系,其中R1¹Æ;
7) R2ÍCxS:表示服务元素和输入Artifact之间的关系;
8) R3ÍEpxS:表示服务元素和调用该服务的事件之间的关系;
9) R4ÍSxEa:表示服务元素和其产生事件之间的关系;
10) R5ÍSxO:表示服务元素和外部Artifact之间的关系;
11) R6ÍSxEa:表示仓库元素和其产生事件之间的关系;
12) f1:R1®D1,其中,D1为前提条件表达式的集合;
13) f2:R2®D2,其中,D2为作用表达式的集合;
14) f3:CÈO®G,G为Artifact类型的集合;
15) f4:EpÈEa®F,F为事件类型集合;
16) f5:R3®K,K为消息类型集合;
17) H0为初始快照.
例如,根据定义,以Artifact为中心的餐馆业务流程模型如图 3所示.在餐馆业务流程中,客户点菜单(guest check,简称GC)是该业务流程的关键Artifact类,整个业务流程将围绕关键Artifact类GC展开工作.
 | Fig. 3 An Artifact-centric business process model of restaurant图 3 以Artifact为中心的餐馆业务流程模型实例 |
定义2(服务[21],service). 服务S定义为一个8元组(n,ET,ES,EP,Ar,Aw,Q,S),其中,
1) n是服务的名称描述;
2) ET代表触发事件类型的有穷集;
3) ES代表挂起事件类型的有穷集;
4) EP代表产生事件类型的有穷集;
5) Ar代表服务读取Artifact的有穷集;
6) Aw代表服务修改或新产生的Artifact有穷集;
7) Q为条件表达式的有穷集,服务读取的Artifact必须满足Q中的条件;
8) S是由以下语句组成的操作序列:create(x),def(x,P),x.P=y.R.其中,(a) x,y是Artifact类型或消息类型的变量;(b) P,R是Artifact类型或消息类型的属性;(c) create(x)表示创建一个新的Artifact;(d) def(x,P)表示定义Artifact变量x的一个属性;(e) x.P=y.R表示将一个Artifact的属性值赋给另一个Artifact的属性.
例如,在餐馆的业务流程模型中的服务有:(1) Create GC,当顾客到达时创建一个新的点菜单GC(guest check);(2) Add Items,当顾客点菜时为GC添加菜品,并创建厨房做菜单KO(kitchen order);(3) Prepare,取当前没有做的KO进行准备;(4) Deliver,将准备好的KO送到顾客餐桌,并读取相应的GC对照;(5) Tender GC,当顾客结账时计算GC的总金额,将现金收取情况写入库CB(cash balance),一个GC最终完成.
定义3(Artifact类型,Artifact class). Artifact类型CA为2元组(A,L),其中,
1) A为Artifact模式,它是一个2元组(U,t),其中:
(a) U是属性的有限集,有一个特殊的属性IÎU称为标识符属性(identifier attribute);
(b) t:U®D是一个完全映射,D是域(domain)的集合,D中至少包含一个标识符域;
2) L为A的生命周期模式,L是2元组(PN,f),其中:
(a) PN=(P,T,F,K,W,M0)是Petri网,其中,P={p1,p2,…,pm}是库所集,对应Artifact类型的属性集合;T={t1,t2,…,tn}是变迁集,T=TUÈTasst,TU对应流程模型中的服务集合,Tasst为辅助变迁集合,不 对A的属性进行赋值操作;FÍ(PxT)È(TxP)是弧集;K是容量函数,规定K(P)º1,即每个库所最多容纳的托肯数为1;W是权函数,规定W(F)º1,即每个变迁发生一次引起相关库所托肯数量的变化为1;M0:P®{0,1}是初始标识;
(b) f:U®P是完全映射,即A中每个属性都映射为Petri网的一个库所,P=PUÈPasst,PU={f(u)|uÎU}是由A的属性映射的库所集合,Passt是辅助库所集合,Passt中的库所与A的属性间没有映射关系.
例如,关键Artifact类GC的生命周期模式和数据对象模式如图 4所示.在生命周期模式中,P1,P2,P3和P4为辅助库所,它们与GC的属性没有映射关系;T1,T2,T3和T4为辅助变迁,它们不对GC的属性进行赋值操作.
 | Fig. 4 Data schema and lifecycle mode of key Artifact GC图 4 关键Artifact类GC的数据模式和生命周期模式 |
定义4(Artifact实例,Aritfact instance). 设A(U,t)是一个Artifact模式,A的实例${a_{\cal A}}$是一个2元组(i,m),
其中,
1) m是一个部分映射,为U中的属性u分配域t(u)中一个的元素;
2) i=m(I),且i¹NULL,称为标识符.
流程执行过程中,Artifact实例是指服务对Artifact类型的数据对象模式具体的赋值操作.例如,关键Artifact类GC完整生命周期中的一个实例见表 1.
|
Table 1 An aritfact instance of Gc in its lifecycle 表 1 关键Artifact类GC的一个实例 |
一个Artifact快照反映了生命周期内某一时刻t,执行某一服务S后生成的Artifact实例,也就是Artifact的属性赋值状态.Artifact的生命周期描述了一类Artifact从创建到完成各操作直至归档的整个过程.因此在完整的生命周期内,Artifact快照序列构成了Artifact行为.下面给出相关定义.
定义5(Artifact快照,snapshot). 设A(U,t)是一个Artifact模式,6元组(i,S,${I_{\cal A}}$,TS,l,z)称为A的一个快照, 其中,
1) i为唯一标识符;
2) ${I_{\cal A}}$是该模式下标识符为i的实例集合;
3) S为操作Artifact模式A的服务集合;
4) TS为服务执行的时间戳集合;
5) l:S®${I_{\cal A}}$为服务集合到实例集合的映射函数;
6) z:S®TS为服务集合到时间戳的映射函数.
根据定义5,关键Artifact类GC在执行服务Create GC时产生一个快照,见表 2.
|
|
Table 2 An aritfact snapshot of GC 表 2 关键Artifact类GC的一个快照 |
定义6(Artifact行为,Artifact behavior). 在Artifact的完整生命周期内,Artifact的行为可以描述为一个满足全序关系的Artifact快照序列({H0,H1,…,Hn-1},p).其中,{H0,H1,…,Hn-1}为Artifact生命周期内的快照集合,H0为初始快照,n-1为服务执行路径中服务的数量,p表示快照集合满足全序关系,由生命周期内服务路径和时间戳决定.
例如,表 3~表 7给出了关键Artifact类GC在完整生命周期中产生的一个快照序列.快照序列{H0,H1,H2,H3, H4}满足全序关系,由服务执行路径“Initial”p“Create GC”p“ADD Items”p“Inform Kitchen”p“Tender GC”和时间戳“2012-04-02,08:30:15”p“2012-04-02, 08:32:17”p“2012-04-02,08:50:50”p“2012-04-02, 09:18:32”p“2012-04-02, 11:51:30”决定.
|
|
Table 3 Initial snapshot H0 of GC 表 3 Artifact类GC的初始快照H0 |
|
|
Table 4 Snapshot H1 of GC 表 4 Artifact类GC的快照H1 |
|
|
Table 5 Snapshot H2 of GC 表 5 Artifact类GC的快照H2 |
|
|
Table 6 Snapshot H3 of GC 表 6 Artifact类GC的快照H3 |
|
|
Table 7 Snapshot H4 of GC 表 7 Artifact类GC的快照H4 |
为简化问题,本文只对Artifact数据属性是否赋值进行一致性检测,并不检测具体属性值的正确性和有效性.为此,下面给出简化Artifact快照的定义.
定义7(简化Artifact快照,simplify snapshot). 设A是一个Artifact模式,H是该模式下完整生命周期内的一个快照序列,对H进行一个简化变换e得到A的简化Artifact快照H*,变化方法是:当H中属性值为空时,将它的值变换为0;否则,将它的值变换为1.
例如,对表 2给出的关键Artifact类GC的一个快照进行简化后,得到表 8的形式.
|
|
Table 8 A simplify snapshot of GC 表 8 关键Artifact类GC的一个简化快照 |
根据简化Artifact快照的定义,下面给出Artifact行为一致性检测问题的形式化描述.
定义8(行为一致性检测). Artifact行为一致性检测形式化定义为6元组(M,L,HSimplify,N1,N2,f(N1,N2)),其中,
1) M为已知流程模型集合;
2) L为流程日志集合;
3) HSimplify为简化Artifact快照集合;
4) N1:M®HSimplify为流程模型M到简化Artifact快照序列的映射;
5) N2:L®HSimplify为流程日志L到简化Artifact快照序列的映射;
6) f(N1,N2)为两个简化Artifact快照序列的确切度,且f(N1,N2)Î[0, 1].
从定义可以得出:Artifact行为一致性检测就是利用已知流程模型推导出的简化Artifact快照序列,与实际运行后产生的简化Artifact快照序列进行映射分析,进而判断流程模型中是否存在违规操作和不一致现象.这里的违规操作和不一致现象主要包括服务执行是否正确、Artifact类型的属性是否赋值.
根据定义,当f(N1,N2)=1时,说明业务流程中不存在违规操作或不一致的现象;当0≤f(N1,N2)<1时,表明业务流程中存在违规操作或不一致的现象.据此,我们将检测到业务流程中具体的违规操作.
3Artifact行为一致性检测方法根据行为一致性检测的定义,本节给出了Artifact行为一致性检测的方法,该方法的执行框架如图 5所示.
 | Fig. 5 Execution framework of the method图 5 检测方法的执行框架 |
在该框架中:首先,根据已知流程模型推导Artifact快照序列;然后,将Artifact行为一致性检测问题转换为语言可判定问题,利用推导出的Artifact序列定义语言,构造图灵机作为一致性验证模型;最后,将实际运行后得到的快照序列放入图灵机中进行模拟来判定是否一致.进一步,利用Artifact快照序列构造服务-快照关联矩阵,通过矩阵等价转换操作计算确切度.
3.1 从已知流程模型中推导Artifact快照序列Artifact快照体现Artifact生命周期的运行轨迹.经过不同的服务,Artifact的属性赋值状态也会产生相应的变化.给定一个业务流程模型M和其Artifact类型的生命周期模型L,可以推导出简化Artifact快照序列.下面给出获取简化Artifact快照序列的算法描述.
算法1. 获取Artifact简化快照序列算法GetArtifactSnapshotSquences(M,L,h0).
输入:流程模型M,Artifact生命周期模型L;简化初始快照h0;
输出:简化Artifact快照序列Q.
GetArtifactSnapshotSquences(M,L,h0)
Begin
(1) 初始化M,L,Q,h,h¢,h0;
(2) 将简化Artifact初始快照h0赋给h;
(3) 验证h的正确性:
(4) 如果h是无效快照,转步骤(1);否则,转步骤(5);
(5) 添加Artifact快照h到集合Q中;
(6) 调用快照推导子算法InferArtifactSnapshot(h);
(7) 如果h可推导出一个新的简化Artifact快照h¢,则h¬h¢,转步骤(5);
(8) 否则,return Q;
End
整个算法中,子算法InferArtifactSnapshot是获取简化Artifact快照序列过程中最核心部分,它的功能是从已知的简化Artifact快照h推导出下一个简化Artifact快照h¢.
算法2. Artifact快照推导子算法InferArtifactSnapshot(h).
输入:简化Artifact快照h;
输出:新的简化Artifact快照h¢.
InferArtifactSnapshot(h)
Begin
(1) 获取简化Artifact快照h的执行服务Sh;
(2) 从流程模型M中获取操作该Artifact的服务路径Path;
(3) 从Path中找到与Sh相对应的服务Smapping;
(4) 如果Smapping是有效的服务,转步骤(5);否则,转步骤(1);
(5) Sh¬Smapping.next;
(6) 从该Artifact生命周期模型L中找到与Sh映射的变迁T;
(7) 根据Sh和T对应的库所集合构造一个简化Artifact快照h¢;
(8) 如果h¢不是有效的简化Artifact快照,则转步骤(1);
(9) 否则,return h¢;
End
例如,根据图 3给定的流程模型和图 4给定的生命周期模型,利用该算法可以得到关键Artifact类GC完整生命周期的简化Artifact快照序列,见表 9.
|
|
Table 9 Deduced Artifact snapshot sequence of GC 表 9 关键Artifact类GC的推导快照序列 |
定理1. GetArtifactSnapshotSquences算法的时间复杂度为O(|n|×|m|×p).
证明:步骤(7)在整个子算法中花费主要时间.在生命周期模型L的Petri网模型中,变迁T对应于流程模型中的服务元素,库所对应于Artifact的属性,库所中的标记(token)表示该属性是否赋值.如果库所中存在一个标记,则表示当前属性已经赋值,用1表示;如果库所中不存在标记,表明当前属性尚未被赋值,用0表示.设变迁T的个数为n(即Artifact生命周期中服务的个数),库所的个数为m(即Artifact的属性个数).p是用来维护不同标记状态的次数.因为完成一次Artifact快照构造只需单遍扫描库所标记的状态,所以需要的最坏时间复杂度为O(|m|×p).要完成整个生命周期内的Artifact快照序列的构造,需要遍历n个变迁对库所标记状态.因此, GetArtifactSnapshotSquences算法的时间复杂度为O(|n|×|m|×p).
定理2. GetArtifactSnapshotSquences算法的空间复杂度为O(|m2|).
证明:在快照推导过程中,算法需要维护每一次生成的Artifact快照属性赋值的状态.设库所的个数为m,一次生成的Artifact快照属性赋值的状态中,属性的个数小于等于m,所以GetArtifactSnapshotSquences算法的空间复杂度为O(|m2|).
3.2 行为一致性检测问题转换为语言可判定问题为了实现同时检测服务路径和Artifact数据属性赋值的一致性,本节通过语言判定原理来解决Artifact行为一致性问题.根据Artifact类型及快照的定义,在进行Artifact行为一致性检测时,一个关键的问题是将Artifact行为一致性检测问题转换为语言判定问题.下面给出问题转换后的形式化定义.
定义9(Artifact行为一致性语言判定问题). Artifact行为一致性语言判定问题的形式化定义为:áM,HñÎB= {áM,Hñ|M推导出H}.其中,
1) M为一个以Artifact为中心的业务流程模型;
2) áM,Hñ表示M实际运行过程中产生的一个Artifact快照序列;
3) B为一个语言,即该流程模型M下可推导出的所有简化Artifact快照序列集合.
判定áM,Hñ是否属于语言B,如果áM,HñÎB,即可判定,表示Artifact的行为一致;如果áM,HñÏB,即不可判定,表示Artifact行为不一致.
根据Artifact行为一致性语言判定问题的形式化定义,可将Artifact行为一致性问题描述成检测语言的成员隶属关系问题.下面的定理将证明语言B是可判定语言.
定理3. B是一个可判定的语言.
证明:证明思路是构造一个判定语言B的图灵机[22]TMA=(H,S,t,d,h0,haccept,hreject),其中,
1) H是该Artifact类型的简化快照序列集合;
2) S为字母表={0,1组成的字符串集合,每个字符串的长度为Artifact快照的属性个数};
3) t为带字母表={S,C};
4) d为转移函数,即流程模型中的服务S;
5) h0ÎH为该Artifact类型的初始快照;
6) hacceptÎH为该Artifact类型的可接受快照;
7) hrejectÎH为该Artifact类型的拒绝快照.
在该验证模型中,首先检测输入áM,Hñ,它表示一个流程模型和其执行的Artifact快照实例.当TMA收到这个输入时,根据Artifact快照的定义,检测该输入是否正确表示流程模型M中Artifact快照:如果是,则先将其转换为简化Artifact快照;如果不是,则拒绝.
然后,TMA执行模拟.运行开始时,TMA的初始状态是Artifact初始快照h0,状态和位置的更新是由转移函数,即流程模型中的服务来操作完成的.当TMA处理完最后一个Artifact快照时,如果TMA处于接受状态,则TMA接受这个输入,表明Artifact行为一致;如果TMA处于拒绝状态,则TMA不接受这个输入,表明Artifact行为不一致.证毕.
3.3 确切度计算确切度是衡量一致性机制的主要性能指标.确切度计算的精确与否,将直接影响一致性检测的评测结果.为此,本节首先利用服务路径与Artifact快照之间的映射关系,构造服务-快照关联矩阵R;然后,根据矩阵等价转换操作计算确切度.
定义10(服务-快照关联矩阵,service-snapshot correlation matrix). 设向量S={S1,S2,…,Sm}为完整Artifact生命周期的服务路径,向量A={A1,A2,…,An}为简化Artifact快照的属性集合.构造一个服务-快照关联矩阵R,它满足l:S®A的映射,表示服务路径S和Artifact快照中属性集合A赋值之间的关系,其中,1≤i≤m,1≤j≤n.
如公式(1)所示,在服务-快照关联矩阵R中,当服务Si对属性Aj进行了赋值操作,矩阵元素aij的值为1;当服务Si未对属性Aj进行赋值操作,矩阵元素aij的值为0.
| $R = \begin{array}{*{20}{c}} {}&{{A_1}}&{{A_2}}&{{A_3}}&{...}&{{A_n}}\\ {\begin{array}{*{20}{c}} {{S_1}}\\ {{S_2}}\\ {{S_3}}\\ {...}\\ {{S_m}} \end{array}}&{\left( {\begin{array}{*{20}{c}} {{a_{11}}}\\ {{a_{21}}}\\ {...}\\ {...}\\ {{a_{m1}}} \end{array}} \right.}&{\begin{array}{*{20}{c}} {{a_{12}}}\\ {{a_{22}}}\\ {...}\\ {...}\\ {{a_{m2}}} \end{array}}&{\begin{array}{*{20}{c}} {{a_{13}}}\\ {{a_{23}}}\\ {...}\\ {...}\\ {{a_{m3}}} \end{array}}&{\begin{array}{*{20}{c}} {...}\\ {...}\\ {...}\\ {...}\\ {...} \end{array}}&{\left. {\begin{array}{*{20}{c}} {{a_{1n}}}\\ {{a_{2n}}}\\ {...}\\ {...}\\ {{a_{mn}}} \end{array}} \right)} \end{array}$ | (1) |
定义11(服务路径确切度,fitness of service path). 设S1为流程模型M推导的服务路径,S2为流程模型M实际执行的服务路径,确切度f(S1,S2)定义如公式(2):
| $f({S_1},{S_2}) = \frac{{Equal(|{S_1}|,|{S_2}|)}}{{\max (|{S_1}|,|{S_2}|)}}$ | (2) |
其中,Equal(|S1|,|S2|)为两个服务路径中对应服务相等的数量,max(|S1|,|S2|)为两个服务路径中服务最大数.
定义12(服务-快照关联矩阵确切度,fitness of service-snapshot correlation matrix). 设R1为流程模型M推导的服务-快照关联矩阵,R2为流程模型M实际执行时产生的服务-快照关联矩阵,确切度f(R1,R2)定义如公式(3):
| $f({R_1},R{}_2) = \frac{{\sum\limits_{i = j = 0}^{m,n} {\sum\limits_{i = j = 0}^{m,n} {Equal(|{a_{ij}}|,|{b_{ij}}|)} } }}{{\max (|{R_1}|,|{R_2}|)}}$ | (3) |
其中,$\sum\limits_{i = j = 0}^{m,n} {\sum\limits_{i = j = 0}^{m,n} {Equal(|{a_{ij}}|,|{b_{ij}}|)} } $代表R1和R2矩阵中对应元素相等的数量,aijÍR1,bijÍR2;max(|R1|,|R2|)代表R1和R2 矩阵元素最大数.
定义13(模型与日志的确切度,fitness of model and its logs). 设f(S1,S2)为两个服务路径之间的确切度, f(R1,R2)为两个服务-快照关联矩阵之间的确切度,流程模型M与实际运行后的日志L之间的确切度f(M,L)定义如公式(4):
| $f\left( {M,L} \right) = {w_1} \times f\left( {{S_1},{S_2}} \right) + {w_2} \times f\left( {{R_1},{R_2}} \right)$ | (4) |
其中,w1和w2是权值,且0<w1<1,0<w2<1,w1+w2=1.
定理4. f(M,L)计算的时间复杂度为O(|R|×|C2|).
证明:矩阵等价转换操作在整个确切度计算过程中占主要的时间代价.在等价转换过程中,算法首先需要遍历矩阵每一行每一个列元素,设服务-快照关联矩阵的行数为|R|,服务-快照关联矩阵的列数为|C|,整个确切度计算的时间复杂度为O(|R|×|C2|).
定理5. f(M,L)计算的空间复杂度为O(|R|×|C|).
证明:该计算过程中,需要维护矩阵每一行列值等价转换的过程.设服务-快照关联矩阵的行数为|R|,服务-快照关联矩阵的列数为|C|,整个确切度计算的空间复杂度为O(|R|×|C|).
4 方法的正确性分析 4.1 理论分析定理6.基于Artifact快照序列的行为一致性检测方法是正确的.
证明:根据Artifact行为一致性问题的形式化定义(定义8),为证明本文提出的行为一致性检测方法是正确的,需要从两个方面进行证明:一方面,要证明利用快照序列构造的图灵机验证模型是正确的;另一方面,要证明利用服务-快照关联矩阵等价转换操作计算确切度是正确的.
关于图灵机验证模型的正确性,定理3已给出了详细的证明过程.
确切度应满足f(M,L)Î[0, 1],它精确地反映了一个流程模型实际执行的结果与预期执行结果之间存在的差异程度.为证明f(M,L)是正确的,首先要证明f(M,L)是一个距离函数.根据距离函数[23]的定义,要证明f(M,L)是度量空间的距离函数,需要证明f(M,L)满足非负性(positiveness)、自反性(reflexivity)、对称性(symmetry)和三角不等式(triangle inequality)这4个特性.根据定义13,f(M,L)是由f(S1,S2)和f(R1,R2)两部分组成.首先,证明f(S1,S2)是一个距离函数.假设S1,S2分别为同一Artifact生命周期内两条不同的服务路径,下面分别证明f(S1,S2)满足非负性、自反性、对称性和三角不等式特性.
(a) 非负性,即,f(S1,S2)≥0.因为S1ÇS2ÍS1ÈS2,所以|S1ÇS2|≤|S1ÈS2|.因此:
(|S1ÇS2|/|S1ÈS2|)≤1,f(S1,S2)=1-(|S1ÇS2|/|S1ÈS2|)≥0.
(b) 自反性,即,f(S1,S2)=0.f(S1,S2)=1-(|S1ÇS2|/|S1ÈS2|)=1-1=0.
(c) 对称性,即,f(S1,S2)=f(S2,S1),因为f(S1,S2)=1-(|S1ÇS2|/|S1ÈS2|)=1-(|S2ÇS1|/|S2ÈS1|)=f(S2,S1).
(d) 三角不等性,即,f(S1,S2)≤f(S1,S3)+f(S3,S2).满足不等式的充要条件是:
(|S1ÇS3|/|S1ÈS3|)+(|S2ÇS3|/|S2ÈS3|)≤1+(|S1ÇS2|/|S1ÈS2|).
任意两个集合S1和S2,都有S1ÇS2ÍS1ÈS2.因此:
(|S1ÇS3|/|S1ÈS3|)+(|S2ÇS3|/|S2ÈS3|)≤(|{S1ÇS3}ÈS2|/|S1ÈS2ÈS3|)+(|{S2ÇS3}ÈS1|/|S1ÈS2ÈS3|)
≤(|S1ÈS2ÈS3|+|S1ÇS2ÇS3|/|S1ÈS2ÈS3|)=1+(|S1ÇS2ÇS3|/|S1ÈS2ÈS3|)
≤1+(|Ss1ÇS2|/|S1ÈS2|).
因此,f(S1,S2)≤f(S1,S3)+f(S3,S2).
因为f(S1,S2)满足非负性、自反性、对称性和三角不等式这4个基本特性,所以f(S1,S2)是一个正确的距离函数.f(R1,R2)的证明过程与f(S1,S2)相似,同理,f(R1,R2)也是一个正确的距离函数.因为f(S1,S2)和f(R1,R2)都是正确的距离函数,且f(M,L)=w1×f(S1,S2)+w2×f(R1,R2),w1和w2是权值,0<w1<1,0<w2<1,w1+w2=1,所以f(M,L)是正确的距离函数.证毕.因此,基于Artifact快照序列的行为一致性检测方法是正确的.
4.2 实例分析以餐馆业务流程为例,假设{S1,S2,S3,S4,S5}为服务集合{Initial,Create GC,ADD Items,Inform Kitchen,Tender GC},关键Artifact类GC完整的生命周期有两条不同的服务路径,分别为P1={S0,S1,S2,S3,S4,S5}和P2={S1,S2,S3,S5, S4}.根据算法1可推导出两个简化Artifact快照序列,见表 10和表 11.表 12和表 13分别为业务流程实际运行后关键Artifact类GC产生的快照实例.
|
|
Table 10 Deduced Artifact snapshot sequence 1 of GC 表 10 关键Artifact类GC推导快照序列1 |
|
|
Table 11 Deduced Artifact snapshot sequence 2 of GC 表 11 关键Artifact类GC推导快照序列2 |
|
|
Table 12 Running Artifact snapshot instance 1 of GC 表 12 关键Artifact类GC实际运行的快照实例1 |
|
|
Table 13 Running Artifact snapshot instance 2 of GC 表 13 关键Artifact类GC实际运行的快照实例2 |
将关键Artifact类GC行为一致性问题转换为语言判定问题.根据定义,语言:
B={(áS1,S2,S3,S4,S5ñ,((1,0,0,0,0,0,0,0,1),(1,1,1,1,0,0,0,0,1),(1,1,1,1,1,0,0,0,1),(1,1,1,1,1,1,0,0,1), (1,1,1,1,1,1,1,1,1));(áS1,S2,S3,S5,S4ñ,((1,0,0,0,0,0,0,0,1),(1,1,1,1,0,0,0,0,1),(1,1,1,1,1,0,0,0,1),(1,1,1,1,1,0,1,1,1),(1,1,1,1,1,1,1,1,1))}.
首先,根据简化Artifact快照的定义,将实际运行的Artifact快照实例进行简化,如果Artifact属性已有具体值,则将其还原为1,代表该属性已被赋值;如果该属性值为NULL,将其还原为0,表示该属性尚未赋值.因此,根据定义,关键Artifact类GC的两个运行实例分别还原为:
· H1={áS1,S2,S3,S4,S5ñ,((1,0,0,0,0,0,0,0,1),(1,1,1,1,0,0,0,0,1),(1,1,1,1,1,0,0,0,1), (1,1,1,1,1,1,0,0,1),(1,1,1,1,1,1,1,1,1))};和 · H2={áS1,S2,S3,S5,S4ñ,((1,0,0,0,0,0,0,0,1),(1,1,1,1,0,0,0,0,1),(1,1,1,1,1,0,0,0,1), (1,1,1,1,1,1,1,0,1),(1,1,1,1,1,1,1,1,1))}.
设计一台识别语言B的图灵机ATM作为Artifact行为一致性验证模型,模型的验证过程如图 6所示,其中,
 | Fig. 6 Verification mode for checkng behavioral conformance of Artifact class Gc图 6 Artifact类GC行为一致性检测的ATM验证模型 |
h0=(1,0,0,0,0,0,0,0,1),h1=(1,1,1,1,0,0,0,0,1),h2=(1,1,1,1,1,0,0,0,1),h3=(1,1,1,1,1,1,0,0,1),
h4=(1,1,1,1,1,0,1,1,1),haccept=(1,1,1,1,1,1,1,1,1),hreject=Øhaccept.
经过ATM验证,Artifact快照实例H1最终可达到接受状态.因此,H1和模型M推导的简化Artifact快照是一致的,而H2最终是拒绝状态.因此,H2和模型M推导的简化Artifact快照是不一致的.
根据定义10,可以得到服务-快照关联矩阵.R1和R2分别为模型M推导的服务-快照关联矩阵,R3和R4分别是运行后的快照实例H1和H2得出的服务-快照关联矩阵.
| ${R_1} = \left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0&1\\ 1&1&1&1&0&0&0&0&1\\ 1&1&1&1&1&0&0&0&1\\ 1&1&1&1&1&1&0&0&1\\ 1&1&1&1&1&1&1&1&1 \end{array}} \right)$ | (5) |
| ${R_2} = \left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0&1\\ 1&1&1&1&0&0&0&0&1\\ 1&1&1&1&1&0&0&0&1\\ 1&1&1&1&1&0&1&1&1\\ 1&1&1&1&1&1&1&1&1 \end{array}} \right)$ | (6) |
| ${R_3} = \left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0&1\\ 1&1&1&1&0&0&0&0&1\\ 1&1&1&1&1&0&0&0&1\\ 1&1&1&1&1&1&0&0&1\\ 1&1&1&1&1&1&1&1&1 \end{array}} \right)$ | (7) |
| ${R_4} = \left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0&1\\ 1&1&1&1&0&0&0&0&1\\ 1&1&1&1&1&0&0&0&1\\ 1&1&1&1&1&1&1&0&1\\ 1&1&1&1&1&1&1&1&1 \end{array}} \right)$ | (8) |
根据定义11~定义13,计算流程模型和执行日志之间的确切度,设权值:
${w_1} = 0.5,{w_2} = 0.5,f(M,{H_1}) = 0.5 \times \frac{5}{5} + 0.5 \times \frac{{45}}{{45}} = 1,f(M,{H_2}) = 0.5 \times \frac{5}{5} + 0.5 \times \frac{{44}}{{45}} \approx 0.99.$
计算结果显示:如果仅从生命周期中执行服务的角度来考虑,流程模型M和快照序列H1,H2完全一致;但是考虑到Artifact数据属性赋值情况时,流程模型M和快照序列H2并非完全一致.实例分析表明,本文提出的检测方法比已有方法的精确度更高.
5 实验分析本实验的案例为某市某铝业公司的业务流程.图 7是该公司铝锭铸造生产的基本业务流程,当公司收到订单时创建一个相应的Artifact Sheet,即流程中的关键Artifact类型.操作Artifact Sheet的服务包括熔铸、热轧、冷轧、精整和包装.熔铸服务通过投入原料和重新利用的废料制造出带有关键属性卷号的铸锭,并将其写入Sheet库.热轧、冷轧、精整服务在读取Artifact Sheet后进行生产,制造出满足要求的铸锭,并将其改变的属性再次写入Sheet库,直至制造出预期的产品包装入库.入库的方式根据客户的需求主要分为两种:一种是热轧后生产出的半成品铝卷进行包装出售;另外一种是依次经过熔铸、热轧、冷轧、精整工艺后制造而成的成品铝卷包装入库.当产品入库后,Artifact Sheet也完成了其生命周期,将归档于完成Artifact Sheet的库中.
 | Fig. 7 Artiflow model of business process图 7 业务流程的ArtiFlow模型 |
图 8中分别给出了Artifact Sheet的数据对象模式和生命周期模式的Petri网表示.
 | Fig. 8 Data schema and lifecycle mode of Artifact Sheet图 8 Artifact Sheet的数据对象模式和生命周期模式 |
实验的硬件环境为CPU:Inter(R) Core(TM) i3-300;内存为1GB;软件环境为Windows XP;数据库为SQL Server 2000;算法实现的运行环境和语言分别为Eclipse 3.4和Java.ArtiFlow管理器是本实验室BPM研究小组开发的一款以Artifact为中心的业务流程建模、运行及检测的原型系统,其中,行为一致性检测器是该系统的一个功能模块.图 9是Artifact行为一致性检测器的运行界面.如图所示,如果服务或Artifact属性赋值存在违规操作,检测器将以红色报警显示具体服务和属性赋值的违规位置.
 | Fig. 9 Running interface of behavioral confrmance checker图 9 Artifact行为一致性检测器的运行界面 |
本实验的内容包括两个方面:(1) 对检测方法的确切度进行评测;(2) 评估检测方法的漏检率和误检率.漏检率和误检率[15]是一致性检测性能的两个关键参数:漏检率是指系统或方法未能检测到的违规操作与实际违规操作数的比值;误检率是指系统或方法将非违规操作检测为违规操作的数量与实际违规操作数的比值.从流程日志库中选取100个流程实例作为实验分析样本.在100个流程实例中,随机修改10个流程实例作为违规流程实例.然后,对本文检测方法和传统基于Petri网映射方法的确切度、漏检率和误检率进行比较.
服务-快照关联矩阵元素中既包含了服务,又包含了Artifact属性赋值结果.因此,利用服务-快照关联矩阵的等价转换操作计算确切度提高了计算确切度指标的精确度.表 14是不同流程实例数中两种方法的确切度计算结果.
|
|
Table 14 Calculation results of fitness about two kinds of method 表 14 两种方法确切度计算结果 |
结果发现:
· 基于传统Petri网映射分析方法得到的确切度值全为1,不符合一致性检测预期的结果;
· 而本文提出的检测方法得到更精确的确切度值,与预期结果完全一致.
Artifact快照序列将业务流程中的数据及服务的执行过程结合在一起,基于Artifact快照序列的行为一致性检测方法同时考虑到了数据属性赋值状态和服务执行状态.而传统基于Petri网映射分析方法仅考虑到服务执行是否一致,忽略了具体属性赋值状态的正确与否.因此,本文提出的检测方法相比传统基于Petri网映射分析方法降低了漏检率和误检率:如图 10所示:本文提出的检测方法平均漏检率为11.2%,而传统基于Petri网映射分析方法的平均漏检率为55.7%;如图 11所示:本文提出的检测方法平均误检率为10.3%,而传统基于Petri网映射分析方法的平均误检率为21.2%.
 | Fig. 10 Comparison of miss rate图 10 漏检率的比较 |
 | Fig. 11 Comparison of error rate图 11 误检率的比较 |
Artifact行为一致性问题是流程建模、模型分析之后重点解决的关键问题.针对现有一致性检测技术忽略数据操作方面检测的问题,本文提出了一种基于Artifact快照序列的行为一致性检测方法.该方法通过对生命周期过程中Artifact快照序列进行映射分析,不仅检测流程模型中服务路径是否正确,同时也验证了Artifact数据属性赋值状态的正确性,进而提高了一致性检测结果的精确度.
实际上,本文在对Artifact数据属性赋值进行检测时,只对Artifact属性是否赋值进行检测,并未检测具体属性值的正确性和有效性.下一步的研究目标就是检测在某一时刻下,Artifact具体属性值的有效性.另一方面,利用服务-快照关联矩阵计算确切度时,随着Artifact快照属性个数增多,矩阵也会变得很大,进而会增大矩阵操作的代价.采用属性划分策略,缩小矩阵的列数来优化矩阵操作的时空复杂度,也是下一步研究的重点.
| [1] | Van der Aalst WMP, ter Hofstede AHM, Kiepuszewski B, Barros AP. Workflow patterns. Distributed and Parallel Databases, 2003, 14(1):5-51 . |
| [2] | Fan YS, Wu C. Research on a workflow modeling method to improve system flexibility. Ruan Jian Xue Bao/Journal of Software, 2002,13(4):833-839 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/833.htm |
| [3] | Nigam A, Caswell NS. Business Artifacts: An approach to operational specification. IBM Systems Journal, 2003,42(3):428-445 . |
| [4] | Bhattacharya K, Caswell NS, Kumaran S, Nigam S, Wu FY. Artifact-Centered operational modeling: Lessons from customer engagements. IBM Systems Journal, 2007,46(4):703-721 . |
| [5] | Liu GH, Liu X, Qin HH, Su JW, Yan ZM, Zhang L. Automated realization of business workflow specification. In: Dan A, Gittler F, Toumani F, eds. Proc. of the 1st Int’l Workshop on SOA, Globalization, People, & Work (SG-PAW 2009). Berlin: Springer-Verlag, 2009. 96-108 . |
| [6] | Bhattacharya K, Gerede C, Hull R, Liu R, Su JW. Towards formal analysis of Artifact-centric business process models. In: Proc. of the Int’l Conf. on BPM 2007. Berlin: Springer-Verlag, 2007. 288-304 . |
| [7] | Gerede CE, Bhattacharya K, Su JW. Static analysis of business Artifact-centric operational models. In: Proc. of the IEEE Int’l Conf. on Service-Oriented Computing and Application (SOCA2007). Piscataway: IEEE Computer Society Press, 2007. 133-140 . |
| [8] | Van der Aalst WMP. Process Mining: Discovery, Conformance and Enhancement of Business Processes. Berlin: Springer-Verlag, 2011. |
| [9] | Leoni MD, Van der Aalst WMP. Data-Aware process mining: Discovering decisions in processes using alignments. In: Shin SY, Maldonado JC, eds. Proc. of the ACM Symp. on Applied Computing (SAC 2013). Portugal: ACM Press, 2013. 1454-1461 . |
| [10] | Goedertier S, Martens D, Vanthienen J, Baesens B. Robust process discovery with artificial negative events. The Journal of Machine Learning Research, 2009,10(2):1305-1340. |
| [11] | Van der Aalst WMP, Adriansyah A, Van Dongen B. Replaying history on process models for conformance checking and performance analysis. WIREs Data Mining and Knowledge Discovery, 2012,2(2):182-192 . |
| [12] | Rozinat A, Van der Aalst WMP. Conformance checking of processes based on monitoring real behavior. Information System, 2008, 33(1):64-95 . |
| [13] | Luo HB, Fan YS, Wu C. Analysis of event balance in the verification of workflow soundness. Ruan Jian Xue Bao/Journal of Software, 2002,13(8):1686-1691 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/1686.htm |
| [14] | Gunther CW, Reichert M, Van der Aalst WMP. Supporting flexible processes with adaptive workflow and case handling. In: Proc. of the 17th Workshop on Enabling Technologies: Infrastructures for Collaborative Enterprises (WETICE 2008). New York: IEEE Computer Society Press, 2008. 229-234 . |
| [15] | Adriansyah A, Van Dongen BF, van der Aalst WMP. Towards robust conformance checking. In: zur Muehlen M, Su J, eds. Proc. of the 6th Workshop on Business Process Intelligence (BPI 2010). Hoboken, 2010. 122-133 . |
| [16] | Adriansyah A, Van Dongen BF, Van der Aalst WMP. Conformance checking using cost-based fitness analysis. In: Chi CH, Johnson P, eds. Proc. of the IEEE Int’l Enterprise Computing Conf. (EDOC 2011). New York: IEEE Computer Society, 2011. 55-64 . |
| [17] | Munoz-Gama J, Carmona J, Van der Aalst WMP. Hierarchical conformance checking of process models based on event logs. In: Colom JM, Desel J, eds. Proc. of the Applications and Theory of Petri Nets 2013. Berlin: Springer-Verlag, 2013. 291-310 . |
| [18] | De Leoni M, Van der Aalst WMP, Van Dongen B. Data- and resource- aware conformance checking of business processes. In: Abramowicz W, Kriksciuniene D, Sakalauskas V, eds. Proc. of the Business Information Systems (BIS 2012). Berlin: Springer- Verlag, 2012. 48-59 . |
| [19] | Hull R, Narendra NC, Nigam A. Facilitating workflow interoperation using Artifact-centric hubs. In: Baresi L, Chi CH, Suzuki J, eds. Proc. of the Int’l Conf. on Service Oriented Computing (ICSOC 2009). Berlin: Springer-Verlag, 2009. 1-18 . |
| [20] | Liu ZQ, Li HY, Wang L, Qu Q. A data model anomalies detection method for business process model. Chinses Journal of Computers, 2010,33(8):1349-1358 (in Chinese with English abstract) . |
| [21] | Liu HB, Liu GH, Huang LM, Song JL. Artifact-Centric business process models and similarity search method. Computer Integrated Manufacturing Systems, 2013,19(8):1810-1821 (in Chinese with English abstract). |
| [22] | Sipser M. Introduction to the Theory of Computation. 3rd ed., Cengage Learning, 2006. 167-170. |
| [23] | Chavez E, Navarro G, Baeza-Yates R, Marroquin JL. Searching in metric spaces. ACM Computing Surveys, 2001,33(3):273-321 . |
| [2] | 范玉顺,吴澄.一种提高系统柔性的工作流建模方法研究.软件学报,2002,13(4):833-839. http://www.jos.org.cn/1000-9825/13/833.htm |
| [13] | 罗海滨,范玉顺,吴澄.工作流合理性验证中的事件平衡分析.软件学报,2002,13(8):1686-1691. http://www.jos.org.cn/1000-9825/13/1686.htm |
| [20] | 刘之强,李红燕,王磊,曲强.面向业务流程的数据模型异常检测方法.计算机学报,2010,33(8):1349-1358 . |
| [21] | 刘海滨,刘国华,黄立明,宋金玲.以业务单据为中心的业务流程模型聚类及相似性查询方法.计算机集成制造系统,2013,19(8): 1810-1821. |