一种基于产生式的流程管理模型分析方法.doc

一种基于产生式的流程管理模型分析方法摘要：在深入分析业务流程模型和合理的抽象业务活动基础上，提出了一种基于产生式的流程模型形式化分析方法，并提供了一种从一般流程描述到该模型的转换方法；在此基础上，推导了一系列行之有效的流程属性验证规则，并通过应用实际例子证明了所提出方法的有效性。 关键词：业务流程模型；分析和验证 业务过程的建模、分析和优化是支持企业业务过程重组的重要基础。行之有效的模型分析方法是成功进行模型分析的关键技术问题。 业务流程重组的实质是企业根据市场需要以企业经营过程为核心重构企业的关键业务流程，并建立与其匹配的运行机制和组织结构，实现对经营过程的有效管理和控制。它一般分为五个阶段，即项目规划、企业经营过程建模、模型分析与优化、基于模型的业务经营过程重组实施和项目评价与监控。在这个过程中模型分析与优化是企业实施业务流程重组中非常重要的一个环节，对业务流程重组成功与否起着至关重要的作用。近几年来，作为支持业务流程重组的重要技术的工作流技术得到了广泛重视。但是由于工作流技术产生于实际应用，缺乏良好的理论基础，应用工作流方法建立的企业经营过程模型缺乏必要且行之有效的模型验证和模型分析方法。研究如何从理论上验证所建立的过程模型结构的合理性，研究如何评价所建立的模型的性能和优化模型的方法就显得尤为重要。 oncepi是中国科学院软件所软件工程中心自主研发的集工作流开发、监控和管理于一身的业务流程管理系统。该系统为企业应用提供了一个构建灵活、高效、自适应流程的平台。oncepi引入面向服务的核心理念，通过将业务流程逻辑与实现各业务的应用相分离、管理流程参与者的相互关系、集成内部和外部资源以及监控和分析流程性能，实现了对业务流程整个生存周期的控制。这样，管理者可以将精力集中于业务自身的优化、组合，从而适应不断变化的商业环境。然而，如果一个业务流程管理系统没有提供一套强有力的流程模型分析工具，流程模型的正确性、有效性和高效性就不能得到有效保证，为系统在现实的企业业务流程运行环境中的应用留下了障碍，特别是对于具有大规模业务流程的企业应用环境中，依靠人工对业务流程模型的维护，难以保证企业业务流程的正确性以及有效、高效的运行。 本文通过分析现有业务流程验证概念和方法，结合oncepi系统在实际应用中面临的流程分析和验证需求，提出了一种基于产生式的流程分析模型以及相应的模型生成方法和验证规则。在此基础上，将这套方法应用于oncepi的流程模型分析和验证之中，开发了一套有力的流程模型分析工具，为oncepi的集成流程设计和开发提供了可靠的保证。 1业务流程验证概念和方法 工作流技术已经被越来越多的业界采用为商业应用和开发的关键技术。其主要特征是自动执行包括人员和自动型应用在内的业务流程。工作流模型是对工作流的抽象表示，也就是对经营过程的抽象表示。由于工作流需要在计算机环境下运行，建立相应的工作流模型是必不可少的。工作流模型应该完整地提出支持工作流定义的概念，为建模用户提供工作流定义所需要的组件或元素。理想的工作流模型能够清楚地定义任意情况下的工作流，能够适应用户在建模过程中所提出的各种要求。 定义和描述工作流模型的方法多种多样，有业务流程语言如xpdl、bpml、bpel等，还有形式化模型如epcm模型、petri网和工作流网等。概括起来可以分为语言描述方法、基于图结构的方法、基于逻辑的方法、代数方法和eca规则方法几类1。由于工作流模型的复杂性，目前还没有有效的算法可以对工作流模型的正确性进行分析。目前已有的大部分工作流产品提供了流程模型的仿真和测试工具，也有一些研究者为流程模型的分析和验证提出了各不相同的概念和方法。 现有的流程模型分析和验证方法大概可以分为三类： （1）基于图形化简的流程验证方法 一般而言，基于图形化简的验证方法适用于基于图结构的流程模型描述方法2，3，通过定义图形结构的化简规则，能够在一定程度上验证流程模型。在文献4中，sadiqw等人对有向无环图(directedacyclicgraph，dag)表示的业务流程证明其结构的正确性。在证明工作图结构正确性的同时使用了如下五种归约规则：终结符规约、顺序规约、邻接规约、闭合归约和重叠归约。如果一个工作流图是正确的，则反复使用这些归约规则可以将工作流图归约为空。但是由于图形结构表达方式的局限性，这种流程模型验证方法只能对部分流程结构中存在的问题进行分析和验证，不能广泛应用在一般的流程模型验证问题中。文献5中列举了一个反例交叉全连接的工作流图，证明了虽然此工作流图是正确的。但是使用重叠归约规则不能消去图中的交叉全连接结构，此流图也无法规约为空。 （2）基于模型的流程分析验证方法 文献6中提出了用petri网进行工作流建模的工作流网，将工作流模型的正确性归纳为工作流网的完整性，并在文献5中提出了一种基于petri网的图形化简方法辅助模型验证。但是其提出的化简步骤由于不具备完备性而不能完全验证工作流模型的正确性。文献1提到的基于模型检查的流程分析方法具有很好的理论基础。这种方法分为两个阶段：首先通过模型映射，将定义的流程模型映射到一种易于分析和验证的有限状态机模型上；在这个模型上使用相应的模型检查器，探索整个状态空间，检查是否每一个系统状态都满足指定的流程属性。由于这种方法只能应用在有限状态机模型上，在流程模型的验证中同样只能部分地验证流程属性。 （3）基于仿真的流程分析方法 文献7中提出了一种基于仿真的模型验证方法，但它缺乏理论上的严格证明，而且当发现系统中确实存在冲突或死锁时，并不能给出错误发生的确切位置（只是给出了一些辅助的检测数据）。基于仿真的流程验证方法，能够结合具体工作流系统，仿真流程模型的执行过程，因而具有很好的实用性。但是其本身没有严格的理论依据，并且依赖于具体的工作流系统，不具有普遍性。oncepi的业务流程分析和验证采用了一种类似于文献1中提到的流程验证框架，即将业务流程的验证划分为两个阶段：首先通过模型映射，将定义的流程模型映射到一种基于产生式的流程分析模型上；然后在这个模型上使用相应的模型化简和变换规则，实现流程属性的分析和验证。这种基于产生式的模型以形式语言理论为基础，能够很好地表达业务流程并体现流程的过程特性。 2基于产生式的流程分析模型 一般而言，工作流是一类能够完全或部分自动执行的业务过程。根据一系列过程规则，文档、信息或任务能在不同的执行者之间传递、执行8。而流程的业务过程模型通过流程模型中的各种实体及其约束关系(包括控制流和数据流)，将业务活动串联起来，从而表达流程的业务过程。几乎所有的流程模型都是基于活动（activity）的，活动是具体执行业务任务的抽象。对于一个面向服务的业务流程管理系统而言，将活动的具体实现绑定到对某个服务的调用。这里的服务是一个抽象概念，可以是webservice或者应用程序甚至是人工活动。这样，可以把业务流程看做是服务的组合过程。下面本文使用“服务”这个概念指代流程模型中具体执行业务任务的实体。 2.1服务的抽象 如上文所述，在本文中服务指代流程模型中具体执行业务任务的实体。那么流程执行过程中，服务是如何完成业务任务的呢？粗略地说，服务请求方通过调用服务，与服务提供方之间发生交互，改变服务提供方和服务请求方的当前状态，从而完成业务任务。因此，本文将服务定义为服务执行上下文状态的一个映射。基于这样的理解，本文可以把服务形式化描述为 service:(context,environment)-(context,environment)(1) 其中，service是流程中的业务活动抽象，即服务；context是流程上下文的一个抽象，它代表服务调用方（流程实例）的上下文状态；environment代表服务提供方（服务实现，如预定义的应用）执行服务的当前状态。这样，服务定义了执行过程中流程实例上下文状态的跃迁及其对服务实现所处环境的作用。在以服务为着眼点时，可以合并服务提供方和调用方的状态，通称为服务执行的context；在以流程为着眼点时，可以忽略服务实现所处的环境状态，而把context直接看做是流程本身的上下文状态，这样服务的形式化表述简化为 service:context-context(2) 从服务的角度重新考查流程的特征，可以定义服务的组合概念。本文把服务复合的逻辑称为服务复合算子。 2.2服务算子及其性质本文使用服务复合算子来描述流程中服务的复合逻辑。 什么是服务的组合呢？一种基本的认识是，多个服务的组合仍然可以被视为服务，即多个服务共同对服务运行环境的作用，可以等效地认为是一个新的服务对其的作用。这个新的服务即是组合的服务，服务组合的结果仍然是服务。 基于这样一个认识，本文定义了服务算子来描述服务的组合。 定义1服务算子定义在服务域，并且其值域也是服务域，用来描述服务的组合 operator:service*-service 其中*指定了算子的元数。 正如21节对流程中服务的组合过程所描述的那样，分析了先前存在的大部分业务流程语言（xpdl、bpel、bpml）和被研究的各种流程模式912。顺序组合和并发组合是两种基本服务组合方式，其他的流程语言结构和流程模式都可以通过这两种服务组合方式配合特定的路由逻辑复合而成。 （1）顺序算子：它表达了服务的顺序组合逻辑和流程中服务之间显式的因果联系。使用“•”符号表示顺序算子。服务的顺序组合可以表示为s=s1•s2 这个表达式代表的语义是s(context)=s2(s1(context)，称之为两个服务的“积”。多个服务的顺序组合使用类似的表达式s=s1•s2•s3。在不会引起误会的场合也可以直接省略“•”符号而直接将顺序组合的服务并置在一起，如s=ab，s=abc。（2）并发算子：它表达了服务的并发组合逻辑，在流程模型中被广泛用来刻画没有因果联系的活动的并发执行。服务的并发组合可以表示为 s=s1+s2 这个表达式代表的语义是s(context)=s2(context)+s1(context)，称之为服务的“和”。如上文所述，context的合并时机和规则取决于流程引擎的具体实现。多个服务的并发组合使用类似的表达式s=s1+s2+s3。 （3）选择算子：它用来表达流程中服务的路由选择逻辑。许多类型的流程模型中存在这样的路由逻辑；服务的选择依赖于运行时具体的流程上下文内容。选择算子被用来刻画这种动态路由逻辑。首先，定义服务的动态选择函数表示为 eval:context-service 其中，context是流程中服务启动时的上下文状态；service是流程实例运行时选择执行的服务分支；eval函数定义了上下文状态到服务分支的映射。在这个基础上，服务选择逻辑可表示为 s=eval?s1|s2 这个表达式代表的语义是s(context)等于s1(context)还是s2(context)取决于eval函数对context映射的结果。多个服务的选择逻辑可以用类似的表达式表达s=eval?s1|s2|s3。在静态表达流程结构时，可以忽略选择函数而把选择表达式简写为 s=s1|s2|s3 从这个定义出发，可以得出选择算子表达的是所谓的xor选择逻辑15。从这个算子可以扩展出一些新的算子，用来表达很常见的一些流程模式，如while循环和dowhile循环模式。本文使用闭包算子“s*”和正闭包算子“s+”来表达。下面进一步分析这三种基本服务复合算子的性质。考虑流程模型中服务的语义，结合上文中对顺序、并发和选择算子的详细讨论，针对算子的运算法则，有如下结论： （1）顺序算子不具备交换律，即一般情况下，s1•s2s2•s1； （2）顺序算子具有结合律，即(s1•s2)•s3=s1•(s2•s3)； （3）并发算子具有交换律，即s1+s2=s2+s1； （4）并发算子具有结合律，即(s1+s2)+s3=s1+(s2+s3)； （5）选择算子具有交换律，即s1|s2=s2|s1； （6）选择算子具有结合律，即(s1|s2)|s3=s1|(s2|s3)； （7）顺序算子与并发算子之间不存在分配律，即s1+s2•s3s1•s2+s1•s3， s1•(s2+s3)s1•s2+s1•s3； （8）顺序算子对选择算子具有分配律，反之不具备，即s1•(s2|s3) =s1•s2|s1•s3，s1|s2•s3(s1|s2)•(s1|s3)； （9）并发算子对选择算子具有分配律，反之不具备，即s1+(s2|s3)=s1|s2+s1|s3，s1|(s2+s3) (s1|s2)+(s1|s3)。 对于以上关于服务复合算子运算法则的结论，需要说明的是，设计到选择算子的结论（5）、（6）、（8）、（9）中，如果将服务选择函数纳入考虑范围之内，均必须重新定义新的选择算子的选择函数。这样才能够保证变换前后的等效性，但是这一要求并不影响流程过程的分析。因此，在使用这些算子作流程过程分析时，仍然可以使用以上的运算法则。对比传统业务流程模型可以看出，这里提到的服务算子实际上替代了所谓“哑元”这一概念。传统的工作流模型把服务（活动）组合与具体的服务混为一体而不加区分，从模型本身就增加了流程分析的难度。本文使用服务复合的概念，可以建立较为清晰的服务复合流程模型。 2.3产生式模型 在服务和服务复合算子概念的基础上，可以开始建立基于产生式的服务复合业务流程模型。在流程的产生式模型中，终结符表示流程的原子服务，非终结符表示流程的复合服务；符号之间通过上文所述的三种基本算子连接构成表达式；非终结符结合对应的表达式构成产生式；一组完备的产生式构成了流程的过程模型。注意其中完备的含义是指产生式中涉及到的非终结符均有对应的表达式，即产生式集中的任何一个非终结符至少有一次出现在产生式的左部。流程的过程模型可以形式化地定义如 下。 定义2流程的过程模型f是一个四元组：（a，c，p，s0） 其中，a是流程的原子服务集合，非空有穷集合，任何sa均是流程中的原子服务；c是流程的复合服务集合，非空有穷集合，任何sc都是流程中的复合服务；p是流程的产生式集合，非空有穷集合，p中的元素均具有s的形式，称为产生式。sc，为服务集合（ac）上的表达式。服务之间的运算符包括顺序算子、并发算子和选择算子，对于产生式集合p，不存在产生式s1，s2，使得s1=s2 。s0是流程的开始符号，s0c。 在产生式模型中，把业务活动抽象为服务，用产生式来表达服务的复合，使用终结符表示原子服务；在流程模型中，它们没有结构，不可细分，用小写字母表达，如a、b、c等。本文使用非终结符表达复合服务；在流程模型中，它们是有结构的服务，可以使用产生式生成更细粒度的服务，用大写字母表达，如a、b、p、q等。结合形式语言理论和上文给出的运算法则，可以对流程模型进行类似的归约或称之为派生，如vaw,wb|c=va(b|c)ab|ac。实际上，在原子服务集合和算子集合•,+上定义了一个服务复合的形式语言，流程的产生式组模型就是这个语言的文法。 使用这种形式语言表示方法，不仅可以使用产生式文法来表达流程的静态结构，而且可以通过产生式的派生，得到流程的派生树，从而表达流程的运行时动态行为。比如，流程p的产生式集合是pa+b,aa|b,bc|d，则流程的派生树有四个：p=a+c,p=a+d,p=b+c,p=b+d。 下面给出一个流程实例来说明如何使用产生式模型表达流程。图1中使用有向图绘制的流程图表达了一个常见的申请处理流程。首先一个申请在“编辑申请”活动中被编辑提交；然后申请被同时递交给活动“预算审核”和“权限审核”，进行申请的预算审核和申请内容权限的校验；审核结果将被校验以确定申请是否通过审核；通过审核则进入“批复申请”活动完成申请的批复，否则申请将被退回申请者编辑修改申请。在这个流程中，使用前面所说的产生式模型，则流程表示如下： 列出组成流程的原子服务。其中a为“编辑申请”，b为“预算审核”，c为“权限审核”，d为“批复申请”。根据图1中表达的流程过程逻辑，流程可以简单地表示为 processp：sldl(t)+taffb+c（3） 对式（3）进行归约，可以得到流程的形式语言表达式： sa•(b+c)+•d（4） 以产生式模型为基础，可以在这个模型上研究流程过程模型的分析和验证方法。下面讨论如何从常见的流程表达形式自动化地转换为基于产生式的形式模型，以及模型上的派生规则和流程属性判定方法。 3模型的生成和验证 使用基于形式化模型的业务流程分析验证方法，首先需要从用户定义的业务流程模型生成对应的流程形式化模型。业务流程的表达方式多种多样，因此，需要为不同的流程表达方式制定不同的自动化翻译规则。oncepi中使用一种基于xpdl10改进的并与其极其类似的语言来表达业务流程。本章以oncepi中的流程表达方式为例，制定了自动化翻译规则，生成流程的形式化模型。 3.1产生式模型的生成在表述一个流程时，一般直接使用一组产生式表示流程的过程逻辑。出现在产生式中的小写字母是终结符，表示流程的原子服务；出现在产生式中的大写字母是非终结符，表示流程的符合服务。为了表示的方便，可以把选择算子的每一个分支使用一个产生式来表示，这样产生式的右部中就可以只有两种算子，即顺序和并发。 使用产生式模型表达流程简单灵活、易于构造。可以根据业务流程中活动的相互依赖关系直接建立流程对应的产生式组，也可以通过一定的规则转换现有的表达方式而得到。针对oncepistudio中基本的工作流模式，定义一组转换规则，简单描述如下： 规则1（1）对流程中每一个应用型活动，赋予一个终结符。（2）对流程模型中每一条跃迁，赋予一个非终结符。 （3）对规则（2）得到的每一个非终结符s，生成一个产生式s。表达式生成方法如下： 如果s对应的跃迁指向的是一个应用型活动s，则=st。其中t是从s出发的跃迁所对应的非终结符。 如果s对应的跃迁指向的是一个流程结束活动，则=e。其中e表示流程的终结。 如果s对应的跃迁指向的是一个并发分支b，则=b1+b2+bn，即b的所有分支跃迁的和。 如果s对应的跃迁指向的是一个排他分支x，则=eval?b1|b2|bn。其中eval是分支x的选择函数。也可以把这个产生式拆分简写为多个产生式：sb1,sb2,sbn。 如果s对应的跃迁指向的是一个排他合并u，则=t。其中t是从u出发的跃迁。 （4）如果若干个跃迁指向的是同一个并发同步节点w，则生成一个表达式s1+s2+snt。其中s1，s2，sn是指向w的所有跃迁，t是从w出发的跃迁。 （5）将从流程的开始活动出发的跃迁对应的非终结符作为产生式组的开始符号。需要额外说明的是，对于基于图结构的流程表达方式，按照类似上述的规则（4），并发分支的同步合并节点会转换成为s1+s2t这种不能严格符合定义的产生式。在这里引入新的化简规则（在3.2节的产生式归约中将应用到这一规则）： r1•s1，r2s2，s1+s2tr1+r2(+)t 从这个例子中可以看出，只需使用简单的规则就可以实现产生式模型到其他流程表达模型的变换。在很多需要变换流程表达方式的场合，可以制定这种简单的规则来实现。下文在作流程分析和验证时，将会用到这种规则，将有向图结构的易于设计者理解的流程模型转换为便于流程分析验证的形式化模型。 3.2产生式归约规则流程的动态分析通过产生式的派生和数据流依赖关系分析来获得流程的控制流行为特征。 使用与规则1类似的规则，可以从传统的图结构流程模型自动化地转换为形式化的产生式模型。下面讨论如何使用产生式模型将一般的流程模型转换为结构良好的流程，并且在这个过程中可以看到，流程的一些特性包括结构上的冲突等会在模型变换过程中被分析出来。 首先给出流程产生式模型归约的规则： 规则2 （1）（合并）合并左部重复的产生式，使其符合产生式左部的唯一性。 （2）（可达符号集）可达符号集定义为：开始符号属于可达符号集；出现在可达符号集中符号的产生式右部的非终结符属于可达符号集。 （3）（连通流程）除非产生式组中所有的非终结符都属于可达符号集；否则，本流程中存在不能被执行的部分，流程中各部分不连通。 （4）（终结消元）对任何产生式s，若s不是开始符号，且中不包含非终结符，则将这个产生式代入其他任何右部包含该产生式左部非终结符的产生式中，消去此非终结符。重复执行此规则直到不存在这样的产生式。将符号e看做终结符号。 （5）（选择表达式）使用算子运算法则中的分配律化简剩余产生式的右部为选择表达式，即表达式中所有的选择算子均在表达式树的第一层，形如s|。（6）（可终结符号集）若非终结符s的产生式右部的所有选择分支中存在一个分支，其中只包含终结符和已经确定为可终结的符号，则s称为可终结的符号。所有可终结的符号构成可终结符号集。 （7）（无限流程）若执行以上步骤后，产生式组中存在非终结符s，属于可达符号集但不属于可终结符号集，则本产生式表达的流程是一个潜在的不能在有限步归约后结束的流程；否则，流程具有有界性。 （8）（简单流程）整理终结消元的结果。如果剩余的非终结符仅有开始符号，则流程中不存在循环、递归等复杂流程结构，称为简单流程。 （9）（非终结消元）如果流程不是简单流程，设剩余非终结符构成集合c，若存在非开始符号的非终结符s属于c且s不出现在s的产生式的右部，将此产生式代入其他产生式中s出现的地方，消去非终结符s；重复执行此规则直到不存在这样的s。 （10