工作流模型验证与数据访问冲突分析方法研究.pdf

《工作流模型验证与数据访问冲突分析方法研究.pdf》由会员分享，可在线阅读，更多相关《工作流模型验证与数据访问冲突分析方法研究.pdf（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类号U D C：工!j!密缎：垒匠学号：Q 2 9 8 2 1I Y 7 q 0 4 6 1-y i 9 0 S 0 0隶南大譬硕士学位论文工作流模型验证与数据访问冲突分析方法研究研究生姓名旦生!垩导师姓名(职称)一王茜(熬援!蝗昱2申请学位类别工堂亟专业名称进篡拯鏖墨挂苤论文提交R 期2 Q Q 5 生2 旦论文答辩日期2 Q Q 至3 县3 Q 目学位授予单位壅直太堂一学位授予日期一一廿答辩委员会丰席评阅人蔓锄二O O 五年三月工作流模型验证与数据访问冲突分析方法研究摘要工作流技术是重要的协同应用支撑技术之一，它通过对业务过程进行建模、执行和管理来完成业务目标。工作流模型建立起来之后，模

2、型正确性验证和工作流执行时的并发控制成为需要解决的问题。本文的模型验证由语法分析和结构验证组成，采用了一种基于有向图的归约法的工作流模型结构冲突分析方法，结合数据流分析方法，探讨了工作流模型的正确性验证问题，并且开发了一个工作流模型验证工具。此外，当多个工作流实例并发执行时，这些实例之间的某些任务可能通过共享数据对象而存在约束关系，这将引发严重的数据访问不一致问题。本文扩展了结构化工作流定义语言S W D L，在此基础上，采用集合约束系统对工作流内部以及实例之间所有可能引起冲突的任务进行分析，生成数据资源的任务冲突集，在此基础上划分出任务调度具有互斥眭质的关联任务子集，并且引入动态任务约束，以

3、保证各实例中可能引发数据冲突的任务子集运行时的临时事务性。本文提出的调度算法在保证工作流实例运行正确性的同时，提供了一种多实例间灵活的、尽可能多的任务并发调度方法，实验验证了本文调度算法的有效性，性能分析表明，该算法提高了工作流的执行性能。关键 司：工作流，模型验证，集合约束，工作流并发，数据访问冲突R e s e a r c ho nW o r k f l o w M o d e lv e r i f i c a t i o na n dD a t aA c c e s sC o n f l i c tA n a l y z eA b s t r a c tW o r k f l o wi

4、so n eo ft h ei m p o r t a n ts u p p o r t i n gt e c h n i q u e si nC S C W I tf a c i l i t a t e sp e o p l e sc o o p e r a t i o nb ym o d e l i n g，e x e c u t i n ga n dm a n a g i n gp r o c e s s e st oa c h i e v et h e i rb u s i n e s sg o a l sA f t e raw o r k f i o wm o d e li sb u

5、 i l t t h eq u e s t i o no fm o d e lv e r i f i c a t i o na n dw o r k f l o wc o n c u r r e n c yi st ob es o l v e d T ov e r i 白t h es e m a n t i ca n ds t r u c t u r a Ic o r r e c t n e s s，ag r a p hr e d u c t i o nm e t h o di si n t r o d u c e di nt h i sp a p e r,c o m b i n e dw i

6、 t hd a t af l o wa n a l y z em e t h o d，w ec o m p l e t eam o d e lv e r i f i c a t i o nt 0 0 1 W h e nm u l t i p l ew o r k f l o wj n s t a n e e se x e c u t ei np a r a l l e l t h e ym i g h th a v es o m ec o n s t r a i n tr e l m i o n s h i p sb e c a u s es o m et a s k so ft h ei n

7、 s t a n c e sm i g h ts h a r et h es a m ed a mo b j e c t s T h i sw i l lC a L I s es e r i o u sp r o b l e m so fi n c o n s i s t e n c yi nd a t aa C C e S S T h i sp a p e re x t e n d st h eS t r u c t u r e dW o r k f l o wD e f n i t i o nL a n g u a g e(S W D L)B yu s i n gs e tc o n s

8、t r a i n ts y s t e m s，a l lp o s s i b l ec o n f l i c t c a u s i n gt a s k si nt h ew o r k f l o wa n da m o n gt h ei n s t a n c e sa r ea n a l y z e da n dt h ec o n f l i c t e dt a s ks e to ft h ed a t as o u r c e si sg e n e r a t e d B a s e do nt h a t t h es u b s e to ft h er e

9、l a t e dt a s k sa n dt h ed y n a m i ct a s kc o n s t r a i n t sa r eg e n e r a t e d，e n s u r i n gt h et e m p o r a r yt r a n s a c t i o na m o n gt h ei n s t a n c e so ft h et a s ks u b s e tw h i c hm i g h tl e a dt od a t ac o n f l i c tw h e ne x e c u t i n g T h l sp a p e rp

10、r o v i d e saf l e x i b l ea l g o r i t h mf o ra sm a n ya sp o s s i b l ei n s t a n c e so ft a s k st or u nc o n c u r r e n t l yw h i l ee n s u r i n gt h ec o i T e c t n e s so f t h ew e r k f l o wi n s t a n c e ss ot h a tt h ep e r f o r m a n c eo f t h ew o r k f l o ws y s t e

11、mi si m p r o v e dA ne x p e r i m e n tp r o v e st h ev a l i d i t yo f t h i sa l g o r i t h mi sd i s c u s s e dK e yW o r d s：W o r k f l o w,M o d e lV e r i f i c a t i o n，S e tC o n s t r a i n t，W o r k f l o wC o n c u r r e n c y,D a t aA c c e s sC o n f l i c t东南大学学位论文独创性声明本人声明所呈交的

12、学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他入己经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。研究生签名：0 雌日期：盟)东南大学学位论文使用授权声明东南扶学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件电子芏档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论E 的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅可以公布(包括刊羔)论文的全部

13、或部分内容。论文的公布(包括刊登)授权东南大学研究生院办理。研究生签名期斗摊各日期查塑查兰堕主兰些堡苎三垡鎏堡型墅至兰墼塑堕塑苎窭竺堑查婆塑窒第一章绪论1。1 工作流技术的发展及应用现状工作流的概念起源于生产制造业与办公自动化领域。根据工作流管理联盟(W F M C)对工作流的定义，工作流是一类能够完全或者部分自动执行的经营过程，它根据一系列过程规则、文档、信息或任务能够在不同的执行者之间进行传递与执行。工作流管理系统是利用软件来定义、创建和管理工作流执行的计算机系统，该系统运行在一个或多个能理解流程定义并与流程参与人相互协作的工作流引擎之上I l】。8。年代中期，F n e N e t 和v

14、 i e w S t a r t 等公司率先开拓了工作流产品市场，成为最早的一批工作流产品供应商。他们把图像扫描、复合文档、结构化路由、实例跟踪、关键字索引以及光盘存储等功能结合在一起，形成种全面支持某些业务流程的集成化的软件。比较典型的有F i l e N e t 于1 9 8 4 年推出的W o r k F i o w 商用系统，v L e 瞒t a r c 于1 9 8 8 年推出的v i e 瞒t a r，I B M于1 9 8 8 年推出的I m a g e P l u s。进入9 0 年代，随着计算机的普及，计算机网络技术的迅速发展，企业的信息化程度提高，企业信息资源越来越表现出异

15、构、松散耦台的特点。I n t e m e t 的发展和普及为电子商务提供了技术可能，而电子商务的重要功能就是商务流程的管理和监控，如企业供应链管理系统S C M(S u p p l yC h a i nM a n a g e m e n t)和企业客户关系管理C R M(C u s t o m e rR e l a t i o n s h i pM a n a g e m e n t)。在这种技术背景下，工作流管理系统也由最初的无纸化办公环境，转而成为集成企业复杂业务流程，实现业务流程自动执行的工具，工作流技术进入了一个崭新的发展阶段，1 9 9 3 年工作流管理联盟W F M C(W o

16、r k f i o wM a n a g e m e n tC o a l i t i o n)成立，工作流相关的概念和术语得到了人们的认可。目前，在全球范围内，对工作流技术的研究及相关产品的开发进入了更为繁荣的阶段，更多更新的技术被集成进来，文件管理系统、数据库、电子邮件、移动式计算、W e b 服务等已被容纳于工作流管理系统之中。工作流产品市场每年以两位数字的速度迅猛增长。随着计算机技术的发展，新的技术不断地融入工作流系统中，使得工作流产品得到不断完善。作为支持企业经营过程重组(B u s i n e s sp r o c e s sr e e n g i n e e r i n g，B

17、P R)、经营过程自动化(B u s i n e s sp r o c e s sa u t o m a t i o n，B P A)的一种手段，工作流技术的研究和应用日益受到学术界与企业界的重视，国内外许多大学和研究机构也致力于工作流技术的研究和开发项目，其中比较有影响力的。i：作流研究中心主要有t B M 的A L M A D E N 研究中t：,T nw I D E 工作流研究组等。工作流定义了W h a t(流程的基本描述、流程各组成活动及活动描述)，H o w(流程各间的时序及选择约束关系、活动阊信息流、活动任务完成内容)，W h o(流程活动的角色，包括参与人、管理人等)，W h

18、e n(流程启动时间、任务完成的时间约束)，W h e r e(任务完成地点的分布)，相对于一般的流程，丁=作流主要具有如下的一些特点：(计算机管理：工作流管理是由计算机管理的企业业务流程，而不是手工管理的流程，也不是部分步骤由计算机来完成的计算机应用：(2)(3)自动流程：流程实现任务及任务信息在流程参与人之间自动流转：流程具有计算机可以理解的定义：流程具有显式或者隐式的计算机定义，它将实际的经营过烈转化为计算机可处理的形式化定义，通常称这种定义为工作流模型：东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究1。2 工作流模型验证与数据访问冲突分析的必要性 二怍流模型是对工作流的抽

19、象表示它将实际的经营过程转化为计算机可处理的形式化定义。为了使计算机能够支持业务过程处理，就要对业务过程进行分析，抽象出业务过程的本质特征，并使用某种计算机可处理的方式来表示。在W f M S 中对业务过程描述的目的是便于工作流管理系统的控制执行，因此，过程模型的正确陛是业务目标实现的基本保证。工作流模型的正确性验证是工作流建模环境的一个核心功能，其目的是对已建立的工作流模型按照菜种正确性原则进行验证。工作流模型的正确性主要包含两方面的含义：(1)过程模型的结构正确性，即过程模型是结构无冲突的在没有错误发生的情况下，工作流能够正常终止。(2)过程模型的语义正确性，也就是说工作流在正常终止时应该

20、达到所期望的业务目标。由于工作流模型的复杂性，目前还没有有效的算法可以对工作流模型的正确性进行完备的分析。由于P e t r i 网严格的数学基础和图形化的规范语义。许多研究人员采用P e t r i 网对工作流进行建模和分析，文献”3 提出了一种基于P e t r i 网的验证方法，S a d i q 等在有向无环图(d i r e c t e da c y c l i cg r a p h，D A G)的基础上，通过定义一些归约规则【6J，如果一个工作流模型可以通过使用这些归约规则归约为空，则认为该工作流模型是正确的，否U 判定该模型存在某些结构冲突，但是，S a d i q 的验证方法不

21、允许工作流模型中存在循环结构，这与实际应用中的工作流模型不符合，此外，S a d i q 方法对嵌套重叠结构(O v e r l a p p e dS t r u c t u r e)的处理存在着错误”。为了实现预期的业务目标，就需要上E 确地定义过程模型，这就要求在工作流执行之前对其模型进行分析。对j：作流模型的分析主要包含3 个方面 3 1：(1)有效性分析(v a l i d a t i o na n a l y s i s)：测试工作流的执行是否能实现预期的业务目标。(2)正确性证明(c o r r e c t n e s sv e r i f i c a t i o n)：验证工作流

22、模型的正确性。(3)性能分析(p e r f o r m a n c ea n a l y s i s)：评价下作流的某些性能参数，例如1=作流的平均执行时间、活动执行的平均等待时间，吞吐率、资源占用率等。其中对工作流模型的有效性分析和性能分析可以通过谊真来进行，可惜目前有效的工作流仿真技术近乎空白，模型验证也往往是通过运行一些_ l 作流实例由有经验的专业人员来检查1 1 作流的执行是否符合设计要求，这通常需要比较氏的时间周期。我们认为在一作流执行之兹妞果采燃一些验证1：具对所建立的 j 作流模型进行验汪，将有助于及早发现模型中存在的一些例如结构冲突等错误，提高建模效率。因此，探讨工作流模型

23、验证方法，并为工作流管理系统提供模型验证工具成为需要研究的问题。1：作流模型验证通常从语法验证和结构验证方面着手一般是对单个l：作流模型进行分析验证。然而，在工作流实例的执行过程中，如果多个在逻辑上可以同时执行的活动共享同一数据，则有可能造成数据访问冲突，这种数据访问冲突可能来自于一个工作流实例内部的并行活动之间，也可能来自T 不同工作流实例的活动之间，甚至可能是同-T I 作流的不同实例之间。这种数据访问冲突将导致严重的数据不一致现象。因此，必须在：作流模酗定义阶段进行数据访问冲突分析，并寻求j 1：作流数据访问止确性保证方法。2东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究1

24、 3 论文的主要内容与章节安排论文以工作流模型验证和数据访问正确性保证为研究目标，内容安排如下：在第二章主要基于工作流有向图模型，采用数据流分析方法和图形归约方法进行模型验证。第三章实现了一个图形化的工作流建模和模型验证工具，并给出一个复杂工作流模型的验证实例。接下来的第四章分析了工作流系统中的并发问题，通过采用集合约束系统，文章对工作流多实例间数据访问冲突进行了分析，并生成数据访问冲突集。在此基础上，第五章采用任务调度具有互斥性质的任务子集及任务约束概念，给出了工作流多实例数据访问正确性保证方法，并且设计丁实验进行性能分析和验证。文章最后总结了全文，归纳了论文的创新点，并阐述进一步研究的方向

25、。2 1 研究现状第二章工作流模型分析目前，用来描述业务过程的方法主要包括有向图J、P e t r i 网u】、形式逻辑【4 l、事件一条件一动作规则E C A A ，1 等，其中有向图的使用虽为普遍，它采用图形符号来表示活动之间的约束关系，简单直观。而P e 订i 网由于严密的形式语言结构，适合对工作流动态性质进行分析，但这种方法使用不直观，不易使用。形式逻辑使用符号来表示活动之间的逻辑关系，该方法不易描述活动之间的复杂关系和活动数量很多的业务过程。E C A A 方法则是从事件的角度来描述业务过程，但是它对业务过程的描述缺乏严密性。在对业务过程描述的基础上，为了检验所建立的业务过程模型的正

26、确性，必须进行模型分析和验证。目前，_ 作流模型分析大多停留在理论层次上，带有工作流模型验证工具的成熟工作流产品不多。在模型分析方法中，比较有代表性的是S a d i q 的有向无环图的归约法【6 1和A a l s t 的j 作流网(W F N e t)方法 7 1。S a d i q 认为，通过反复使用预先定义的一些归约规则。如果能将一个工作流图归约为空，则认为该工作流模型是结构正确的。然而，这种方法存在以下缺陷：(1)由于归约的前提是有向无环圈(D A G 图)。因此不允许所分析的工作流图具有任何形式的循环结构，这与实际的业务过程相悖。(2)对某些正确的嵌套重叠结构，S a d i q

27、归约法无法把正确的工作流图归约为空。(3)由于没有对数据流进行分析该分析方法无法检验出模型中的无效活动节点。文献【1”对S a d i q 的错误之处进行了证明，并定义了一套转换规则，试图解决重叠结构的归约问题。A a l s t 使用W F-N e t 来描述和分析业务过撑，其中W F N e t 是从基本P e t r i 网派生而来的，A a l s t 方法通过分析W F-N e t 的性质来证明业务过程模型的正确性，但是，W F N e t 方法不易在实际工作流产品中实现。本章引入数据流分析方法，对无效活动节点和循环结构进行判定，改进了S a d i q 归约规则，简化了具有重叠结构

28、的上作流模型的验证过程。东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究2 2 工作流模型2 2 1 工作流元模型元模型(m e t a m o d e l)是用来定义语义模型的构造(c o n s t r u c t)和规则(r u l e)的，通常称为定义表达模型的语言的模型1，工作流元模型是用于描述工作流内部的各个元素，元素之间关系以及元素属性的。工作流元模型通常涉及相互关联的3 个子元模型，即：(1)过程定义元模型：用于定义描述业务过程的模型元素，控制工作流的执行；(2)相关数据元模型：工作流执行所处理的数据以及它们之间的流动关系；(3)组织机构元模型：描述单位，部门，人员

29、的组织关系以及所担当的角色：工作流元模型的核心是过程定义元模型，工作流管理联盟为过程定义开发了一个基本的元模型。工作流元模型归约出元素类型的一个基本集合，这些元素类型适台于相对简单的过程定义，工作流开发人员可以根据需要对该元模型进行适当的扩展。工作流管理联盟的过程定义元模型中元素的定义和重要属性如F：活动(A c t i v i t y)：完成工作流的一个逻辑步骤，重要属性包括活动名称活动类型，前后活动条件，其他调度约束等。转移条件(t r a n s i t i o nc o n d i t i o n s)：从当前活动到下一活动流转或状态转移的规则，主要参数包括过程条件，执行条件，通知条件

30、等。工作流相关数据(w o r k f l o wr e l e v a n td a t a)：被工作流管理系统用作决定个工作流实例状态转移的数据。重要属性包括数据名称或路径，数据类型等。角色(r o l e)：把参与者与一系列活动相联系的机制，重要属性包括名称，组织实体等。被调应用(i n v o k e da p p l i c a t i o n)：应用主要描述用于完成业务过程所采用的工具蒴l手段，重要属性包括类型或名称，执行参数，位置或存取路径等。圈2-I 是W f M C 给出的过程定义元模型”：图2-1W f M C 的过槲定义元模型4东南大学硕士学位论文工作流模型验证与数据访问

31、冲突分析方法研究2 2 2 过程描述语言在描述业务过程时往往使用某种语言符号来表示过程模型中的各种元素，在有向图中，基本符号分为两类：节点和弧，节点包括活动节点和控制节点，活动节点包括开始活动、原子活动、子过程、结束节点，而控制节点则包括与节点(A N D n o d e)、或节点(O R n o d e)，如图2 2 所示：图2 2 过程描述语言的基本符号起始活动表示一个工作流过程的开始，终止活动表示一个工作流过程的结束。原子活动是可以直接由工作流管理系统执行的基本实体。由于过程模型中的活动也可能是具有复杂结构的过程模型，因此引入子过程的概念，子过程本身可以是一个工作流模型，它与主流程组成一

32、个层次化的工作流模型。控制节点和弧表示业务处理规则和约束关系，或节点表示工作流执行的路径选择和合并，与节点表示工作流执行的分叉和同步，弧通过连接两个节点表示控制流和数据流的流动方向。如果弧带有条件表达式，则表示在工作流执行时计算表达式的值，结果为真时触发相应的变迁发生。工作流管理联盟W f M C 定义了工作流执行的6 种基本控制结构，它们分别是：顺序(S e q u e n t e)、循环(I t e r a t i o n)、与分支(A N D s p l i t)、与合并(A N D j o i n)、或分支(O R s p l i t)、或合并(O R j o i n)，这些控制结构用

33、有向图表示为：图2-31 二作流执行的基本控制结构顺序(S e q u e n c e)表示一个活动执行结束后另一个活动可以开始执彳丁=循环(i t e r a t i o n)表示若干个活动反复被执行直到满足某个条,f l：；5查堕查兰堡主堂些笙壅三丝迹堡型壁堑量塑塑堕塑壁窭坌塑变鲨竺窒与分支(A N D s p l t)异j 来触发后续多个活动的执行，需要注意的是，后续的多条路径可以以任意的次序执行。与合并(A n d-j o i n)用来N 步输入进来的多条路径，表示著行执行的路径在该节点上同步。或分支(O R s p l i t)工作流引擎计算所有的布尔表达式，选择其中的一条正确的执行

34、路径。或合并(O R-j o i n)只要其输入路径中有一条执行完毕，就触发执行后续活动。图2 4 是一个用以上控制结构构成的简单工作流模型，包含闭合结构，循环结构等基本控制结构。2 3 模型验证图2 4 普通的工作流模型示例对于面向过程的工作流系统而言，过程定义是业务过程自动流转的基础，然而，过程定义比较容易出错，仅凭流程设计者的经验或者操作者的反复实验来发现差错的方法效率低F。因此，在工作流执行前之前，需要采用验证方法，对业务过程中的各项特性进行检测，以保证工作流模型的正确性。这里的正确性主要包括三方面的含义：一是指工作流模型的语法正确陛，即所建立的工作流模型符合基本的语法要求：二是指工作

35、流模型的结构正确性，也就是说工作流模型姓无结构冲突的，在没有错误发生情况下工作流可以正常终J t；三是指工作流模型的语义正确性，也就是说工作流在正常终止时应该达到所期望的业务目标。下面将集中对语法正确性和结构正确性进行分析，语义正确洼留待第四章进行分析2，3。t 语法检查为便于分析，我们定义工作流图G=犯q 毋，其中：(1)N=s t a r t N o d e，n I，”2 n。，e n d N o d e 为节点集，其中s t a r t N o d e 为开始节点n i f 原子活动节点，子过程节点、控制节点)，e n d N o d e 为结柬节点。2)E N x N，是连接弧的集合，

36、-(n E N，n j N)J j 连接两个_ 节点的弧。对于任意结点n N，我WJ 定义n 的入度I n D e g r e e(n)：C o u n t(e)IV e，e(m，n )，即所有终点为n 的边的总数；对于任意结点n N，我仃J 定义n 的出度I n D e g r e e(n)：C o u n t(e)IV e，e ，即所有始点为n 的边的总数；一个语法正确的：作流图G 必须满足以F 性质：图G 有唯一的s t a r t N o d e 和结束节点，流程起始于s t a r t N o d e1，点，终f 丁e n d N o d e6查塑查兰堡主兰些鲨壅三堡亟堡型堕堑兰塑塑

37、堕塑壁窒坌堑查鲨竺塞节点；任一原子活动节点和子过程有且仅有一个出度和入度a开始节点s t a r t N o d e 的入度为0，出度为1；结束节点e n d N o d e 的出度为0，入度为1；或分支、与分支节点的入度为1，出度大于1：或合并、与合并节点的出度为1，入度大于1：其中性质规定原子活动节点和子过程节点有且只有一个出度和入度，不符合该性质的工作流模型将不能通过语法检查，语法验证可以识别工作流图的简单语法错误，对于复杂工作流图的结构冲突，我们采用有向图归约法对其进行验证。原型系统实现见第三章。2 3 2 过程模型的结构冲突过程模型的结构冲突主要分为三类州”l：死锁、同步丢失、无效活

38、动。(1)死锁在一个结构正确的工作流模型中，一个与分支(A N D s p l i t)需要和一个与合并(A N D-j o i n)对应，如果将一个或分支(O R s p l i t)和与合并(A N D-j o i n)对应，将导致与合并节点的输入弧至少有一条不能触发，从而引发死锁，流程无法进入正常结束。死锁的另一种情况是无限循环循环出口条件始终无法成立。(图2-5(a)、(d)、(f)所示)(2)同步丢失同样。一个或分支(O R s p l i t)也需要一个或合并(O R-j o i n)对应。如果一个与分支和一个或合并对应将导致与分支的多个输出弧在汇聚时未能相互等待以达到同步，从而只

39、有一个分支上的活动有效。(图2 5(b)、(e)所示)(3)无效活动工作流模型中某些活动在所有的实例中永远不能无法执行，这种清况通常发生在或分支的某个分支条件永远为假或者死锁结构冲突引起的后续活动无效。(图2-5(c)、(g)所示)口(a)死锁(b)同步丢失(c)无效活动口辱孔驴 矗(d)E 锁、无效活动7(e)同步丢父东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究口(f)死锁图2-5 常见的工作流结构冲突(g)无效活动需要注意的事，结构冲突并不是过程模型中仅有的错误，其他如活动之间的数据依赖也可能引发工作流的错误执行。然而工作流模型中其他错误的存在并不会增加或消除结构冲突，因而

40、工作流模型中结构冲突的识别可以独立于其他类型的验证分析而进行。2 3 3 模型归约法则S a d i q 等在文献【6 1 中对有向无环图定义了4 种归约规则：顺序归约、邻接归约、闭合归约、重叠归约。对一个工作流图反复使用归约规则，删去所有已被确认为正确的结构，保留冲突结构，若能将一个工作流图归约化简为仅由一个起始节点和一个结束节点组成的有向圈，则认为该工作流图无结构冲突，否则认为该图存在结构冲突。本章首先对文献【6 1 中的归约进行了介绍，然后对其进行了扩展，增加了循环归约和终结符归约，并且引入数据流分析方法，讨论了循环结构和无效活动节点的判定，并简化了重叠结构的验证过程。顺溽；野约詹，1

41、6 1：两个顺序执行的活动节点可以合并成为一个活动节点。图2 7 循环归约为一个活动节点。专瑚一曲=卜争=h 刘查塑查兰堡主兰堡堡苎三堡鎏堡型壁堡童墼塑堕塑壁窒坌堑立璧塑塞在进行循环归约之前，验证程序必须首先识别出循环结构，我们采用数据流分析的方法进行循环检测。我们知道，在工作流图中，从开始节点出发可以到达工作流图中的任何节点。定义l：在一个工作流图中，从开始节点触发到达某节点n j 的各条通路都必须经过节点n。，则称n i 为n 的必经节点，记做n，d o mn J。n j 的全部必经节点的集台记为D(n j)，称作n j的必经节点集。图2-8 循环结构图2-8 各个节点的必经节点集有：D(

42、)：D()=，)D()=，)D()=，D()=，)定义2：设e=是工作流图中的一条边，若bd o r aa，则称e=为工作流图中的一条回边。图2-8 中有一条回边，即。性质：每条回边构成一个循环，殴 是一条回边，则该回边构成的循环包括下列节点：a、b、不经过b 能够到达a 的所有节点。根据这个性质，回边 构成的循环=，)，从而识别出上图中的循环结构。留台妇缈置，7：两个并行执行的活动节点可以归约为一个活动节点、两个选择执行的活动节点可以归约为一个活动节点。日亭日争日口口口日口1 IV0彩蜜i 廊约见刚：在工作流图中可能出现两个控制型节点直接相连的情况，此时可采用邻接归约，邻接归约通常有两种情况

43、：若当前节点为分支型节点(与分支、或分支)，且当前节点的逻辑类型与其前驱节点相同(均为与分支或者均为或分支)，可以把当前节点的输出弧转移到其前驱节点上，同时删除当前节点。9查堕查兰堡主兰垡堡塞三堡堕堡型墅壁量墼塑堕塑翌窒坌堑塑鲨堕翌图2-1 0 邻接归约一若当前节点为合并型节点(与合并、或合并)，且当前节点的逻辑类型与其后继节点相同(均为与合并或者均为或合并)，则可以把当前节点输入弧转移到其后继节点上，同时删除当前节点。+士+图2-l l 邻接归约磐秽妇约R s：为了简化工作流模型的验证过程，在归约的过程中往往把活动节点去掉，一个正确的工作流模型经过归约化简后将只存在一个起始节点和结束节点，以

44、及由起始节点指向结束节点的有向弧。终端归约示例如下：2 4 无效活动的判定图2，1 2 终端归约S q d i q 规则忽略了过程模型语义相关的属性和弧上的条件表达式可以看作仅仅是对l作流模型的控制结构进行验证。而事实上，过程模型中弧上表达式的语义可能会造成条件的永远无法满足，例如图2-5(c)、(g)就是条件表达式永远无法满足转移条件的例子，造成了无效活动。另外，死锁结构也可能造成某些活动成为无效活动，如图2-5(d)所示。通过对死锁结构的判定能够识另0 由死锁结构引起的无效活动，因此，下面主要讨论通过检查相关弧上的条件表达式而完成对无效活动的判定。具体判定过程为：搜索模型中“或分支”节点：

45、依次取“或分支”节点的输出弧上的条件表达式，如果该弧上的条什表达式永远为假，则删除该弧：遍历1 i 作流模型，如果存在除起始点以外的入度为0 的活动仙点，则标，占该活动O，0专东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究节点为无效节点，并且删除其出边，循环；如对图2 1 3 的所示一个工作流模型，经过上述判定算法可以划分出两个无效活动节点(图中红色节点所示)。国2 1 3 无教活动的判定对于或分支节点，一般情况下其输出弧中应该有条e l s e 路径，系统实现以保持一条不设定守卫条件的选择边来充当该条e l s e 路径，以防止存在选择路径都不满足条件而流程无法继续执行下去和无

46、效活动的情况。2 5 重叠结构的化简S e N t 6 1 中提出种特殊的归约方法即重叠结构归约，但是，这种归约方法并不完备，清华大学的李红臣在文献【1 0 1 证明了其无法验证某些复杂的重叠嵌套结构针对这种情况，文献 t O l 对重叠结构进行了定义，他认为重叠结构是这样的一种结构：输入层为与：带点，输出层为或节点，两层间存在交叉全连接的结构(图2-1 4)；重叠结构可以按照图2 1 4 的方法进行归约，为了避免归约所带来的语法错误问题，文献作了如下定义：规则一：假如控制节点只有一条输入弧和一条输出弧，则可以移去控制肯点，将其输入弧与输出弧合并。文献l I 的重叠结构归约方法如下：嚣一X事实

47、上，我”J 可以推论，重叠结构的的输入层一定为或分支节点，即倒2-1 5 所示东南大学硕士学位论文工作流模型验证与数据访问冲突分析方法研究 第一层 第二层 第三层图2 1 5 重叠结构的输入层必为或分支证明，采用r J-7 宝内 去，假设重叠结构的输入层为并分支节点，即图中第一层为并分支，则流程启动后，由于第二层并分支的同时触发将引发第三层或合并节点的同步丢失问题故重叠结构的输入层必为或分支节点。同理，重叠结构的输出层一定为与合并节点，即图所示：第一层一 第二层一 第三层一 第四层图2-1 6 重叠结构的输出层必为与台并证明，采用归纳法，假设重叠结构的输出层为或合并节点，即图中第四层为或合并则

48、流程启动后，由于数据流皆到达第三层的所有或合并肖点，将引发第四层或合并节点的同步丢失问题，故重叠结构的输出层必为与合并节点。基于以上分析，结合圈2-1 4 和规则一，我们认为，典型重叠结构的归约如幽2，1 7：闭合归约匕=l规则一图2 1 7 重叠结构的归约需要注意的是，由于各人的建模习惯不同，可以派生出众多的类似重蹙结构的复杂l：作流结构，而且这些结构在逻辑上可能是正确的此时往往需要对流程进行修改，例如图2 18是一个信用矗消费流穰图，流程描述如下：首先并行执行信用度奇淘利卡余额贲询酮个任务如果信用良好并且余额充足，则进行信川 消费：若余额不足或者信川度判定为差，则不进1 2。9令东南大学硕

49、士学位论文工作流模型验证与数据访问冲突分析方法研究行信崩卡消费，流程结束。信用卡消费图2-1 8 信用卡消费流程图把上述图中的活动节点去掉，只留下控制节点和弧，将得到如下的一个结构图2 1 9 信用卡消费流程重叠结构根据定义，它并不属于重叠结构，事实上，该结构应该避免，因为它可以通过变更余额查询和信用查询为串行结构，使得模型更加简便而直观。重叠结构是工作流图中的一种特殊结构，它比较少出现，在结构验证中，对识别出来的重叠结构，可以依照上述规则将其化简归约为一个空结构。至堕查兰堡主兰堡堕塞三堡堕堡型墅堡兰塑塑堕塑壁窭坌堑立壁堕塞第三章工作流模型验证工具及其实现3 1 带有模型验证工具的W f M

50、S 体系结构本节的工作流模型验证工具集成在我们所开发的工作流管理系统中，可以对所建立的工作流模型进行语法和结构验证。系统体系结构如图3-1 所示：图3-1 集成模型验证工具的工作流管理系统3 2 图形化工作流过程定义工具医习l1，J工作流模型是工作流执行的基础，它为业务过程描述提供了一种直观的方法。建模工具的主要功能如F：提供工作流模型定义所需的基本元素，如起始结点、任务结点、子过程、连接弧、终止结点等i对工作流程的集中式管理、定义、修改及监视：流程定义在服务器端由管理员身份用户集中建模，并且进行角色定义，任务描述，系统设置：提供模型的导入导山接I Z l，所建立的工作流模型可以方便存储和读写