业务过程模型检索与重构

金涛业务过程模型检索与重构提纲背景介绍模型检索精细任务执行关系计算并行化重构总结与展望业务过程管理技术应用广泛Surveys

over

the

past

five

years

have

shown

processmanagementtobethenumberoneconcernofseniorexecutives[Gartner,2010]GartnerPrediction:“By2014,40%ofbusinessmanagersandknowledgeworkersinGlobal2000enterpriseswillusecomprehensivebusinessprocessmodelstosupporttheirdailywork,upfrom6%in2009.”业务过程模型数据日益增多SAP参考模型600+Haier3,000+SunCorp6,000+中国移动8,000+如何管理？将业务过程模型视为一种非结构化数据EPC、BPMN、BPEL、YAWL、Petrinet、JPDL、XPDL、……假设1——模型基于图(存在基于规则的模型)假设2——所有模型均由或者转化为workflownet表示业务过程模型格式多种多样研究问题一模型检索关注性能模型复用提高建模效率避免重复存储业务整合相似业务过程的检索北车集团20多个子公司合并，业务流程整合中国移动30多个分公司的业务集中化SOA服务的查找与组合基于BPEL模型检索分类基于结构的精确查询基于行为的精确查询基于结构的相似检索基于行为的相似检索问题子图匹配算法为NPC问题基于最大公共子图的相似度计算为NPC问题基于结构的检索精确查询相似检索问题

行为的计算复杂度高基于行为的检索精确查询A->D&&B||C相似检索Filtering-verificationframework索引用于过滤减少复杂计算次数索引元素的选取索引元素的快速提取基于索引的查询处理使用索引过滤有向图，唯一的源点和终点，边不带标签，变迁结点带标签（任意长度字符串）Label多，频繁子图少需要考虑label的相似性具有行为语义业务过程模型特点W(l):l中单词个数SCW(l1,l2):l1中单词能在l2中找到同义词的个数可替换为其他基于term的相似性度量Label相似性度量业务过程模型样本特征数据集模型数变迁总数路由变迁标签总数#1.00.60.5DG1141035153819806802747710595464SAP591401316533146306230582786269323662036TC1231595352126212521249118311361009818数据集模型数变迁数库所数弧数图密度AvgMaxAvgMaxAvgMaxAvgMaxDG1149349.73319.3700.10.5SAP5916.85310.66517.71420.20.5TC123133911.53226.3800.10.2DG(114)#1.00.60.52/11460478

(33)60481

(35)60481

(35)61084

(47)61073

(46)179607(50)70567

(67)4/114416

(7)416

(7)416

(7)419

(11)437

(13)434

(10)440

(17)7/11459

(7)59

(7)59

(7)102

(7)122

(9)122

(9)122

(8)##8/1148/1148/1148/1149/1149/1149/114业务过程模型库频繁子图SAP(591)#1.00.60.54/5911747

(141)1922

(154)1922

(154)2298

(178)2303

(192)3862

(237)2554

(329)6/591199

(84)203

(97)203

(97)216

(122)219

(125)270

(188)322

(270)10/5918

(10)8

(10)8

(10)9

(20)9

(20)18

(69)34

(190)##11/59111/59111/59111/59111/59133/59144/591业务过程模型库频繁子图TC(123)#1.00.60.53/1232

(15)4

(17)4

(17)10

(23)13

(26)27

(42)81

(73)7/1232

(15)2

(17)2

(17)2

(17)2

(17)2

(17)2

(17)10/1231

(10)2

(17)2

(17)2

(17)2

(17)2

(17)2

(17)##11/12311/12311/12311/12311/12311/12311/123业务过程模型库频繁子图用户决定是否考虑label相似性用户在查询处理过程决定label相似度阈值Filtering：扩展查询条件Verfication：结合label相似性构造独立于其它索引的label索引Label相似性考虑1.1基于结构的精确检索基于路径建立索引路径长度：路径上的结点数目示例查询处理∩Stage1:filteringStage2:refinementEvaluationImplementinBeehiveZL1PindexL2CPindexExperimentsontwodatasetsSAPR/3(600+)synthesisset(40,000+)1.2基于结构的相似检索query没有模型包含查询对象为子图如果我们放松约束，pn2和pn4可以作为近似结果返回基于最大公共边子图的相似度计算任务边索引任务边和模型之间的映射查询处理Filtering从查询对象中抽取任务边得到候选模型集合Refinement计算候选模型和查询对象模型之间的相似度值索引和查询处理FilteringTaskedgemodel<A,B>1,2,3<A,C>1<B,D>1,2<C,D>1Candidateset:pn1pn2100%RefinementResultset:pn1100%1.3基于行为的精确检索行为的计算基于orderingrelationscausalconflictconcurrency任务关系索引行为计算性能比较给定一个模型，如何快速检索出与之行为相似的模型?1.4基于行为的相似检索采用TAR相似度HaipingZha,JianminWang,LijieWen,ChaokunWang,JiaguangSun:Aworkflownetsimilaritymeasurebasedontransitionadjacencyrelations.ComputersinIndustry(CII)61(5):463-471(2010)问题计算性能不好基于可达图，存在状态空间爆炸问题新方案使用Unfolding技术JavierEsparza,StefanRömer,WalterVogler:AnImprovementofMcMillan'sUnfoldingAlgorithm.FormalMethodsinSystemDesign(FMSD)20(3):285-310(2002)行为相似度TAR计算TARsI->AA->BA->CB->CC->BB->DC->DD->ED->FF->AI->GF->G查询处理m1TARIndexInvertedForward“A,B”->m1m1->(“A,B”,”A,C”,“B,C”,“C,B”,“B,D”,“C,D”)“A,C”->m1“B,C”->m1“C,B”->m1“B,D”->m1“C,D”->m1query计算TARs“A,B”,“A,C”,“B,C”,“C,B”,“B,D”,“C,D”Filteringmodelsbasedoninvertedindexm1ComputingTARsimilaritywiththehelpofforwardindex1.0ReturnthemodelsthatsatisfythesimilaritythresholdrequirementImplementedSystemTAR计算性能比较小结贡献在BPM领域最先开始关注模型检索的效率使用索引技术全面支持4种类型的模型检索未来工作嵌套模型的检索研究问题二精细任务执行关系计算问题I和A之间的因果关系，C和D之间的因果关系一样吗？B和D之间的并行关系，B和C之间的并行关系一样吗？更细粒度的行为分析，用于：基于行为的检索业务规则符合性检测基于模型执行实例中一个任务的出现是否一定伴有另一个任务的出现充分必要因果关系t1=>t2

任意一个包含t1的实例中必包含t2满足t1->t2。任意一个包含t2的实例中必包含t1满足t1->t2。必要不充分因果关系t1=>|t2

包含t1的实例中可能包含t2满足t1->t2。任意一个包含t2的实例中一定包含t1满足t1->t2。充分不必要因果关系t1|=>t2

任意一个包含t1的实例中必然包含t2满足t1->t2。包含t2的实例中可能包含t1满足t1->t2。既不充分也不必要因果关系t1|=>|t2

包含t1的实例中可能存在t2满足t1->t2。包含t2的实例中可能存在t1满足t1->t2。行为因果关系的分类基于Mcmillan改进算法基于完全有限前缀遍历库所判定前驱、后继事件的因果关系根据库所类别区别对待（截断库所、通信库所、一般库所）截断处理不紧邻事件因果关系的传递共计16个传递性规则判定要点并行关系的分类遍历库所1|=>3,3=>4截断处理2|=>3因果传递1|=>4,2|=>4示例小结贡献不同因果关系细分不同并行关系细分判定及传递规则针对无环模型的判定算法未来工作针对有环模型的处理研究问题三并行化重构问题给定一个合理的结构化工作流网模型，尽可能的将其并行化重构以提升业务流程处理的效率.基于数据流分析将不必要顺序执行的任务并行化前提假设给定模型为合理的结构化工作流网模型，并带有数据操作如果两个任务之间存在因果关系或者传递因果关系，则必有数据操作依赖直接因果关系并行关系间接因果关系并行关系间接因果关系直接因果关系解决方案ExtracttaskrelationsAnalyzedataoperationdependenceUpdatetaskrelationsRefactormodelRefactormodel有效性最大程度的并行化所有原始数据依赖关系都得到了保持没有引入新的数据依赖关系随机生成模型10,000modelsMaximumnumberoftransitionspermodel:50Maximumnumberofdataitemspermodel:nMaximumnumberoftasksoperatingononedataitem:n有效性重构前TS=0重构后Min(TS)=0Max(TS)=48Avg(TS)=3Stdev(TS)=6.12效率小结贡献问题:首次提出了过程模型的并行化重构问题方法:首次使用过程挖掘技术解决重构问题工具:BeehiveZ未来工作重构后的模型是否合理？总结贡献点首先关注模型检索效率问题首先开展了基于行为的模型检索提出了不确定性因果关系、并行关系的分类及判定提出了模型的并行化重构问题并给出了解决方案BeehiveZ开源系统未来工作嵌套模型的检索有环模型的不确定性行为判定重构模型的合理性已发表论文TaoJin,JianminWang,LijieWen:EfficientRetrievalofSimilarWorkflowModelsBasedonBehavior.APWeb2012:677-684TaoJin,JianminWang,LijieWen:EfficientlyQueryingBusinessProcessModelswithBeehiveZ.BPM(Demos)2011TaoJin,JianminWang,LijieWen:QueryingBusinessProcessModelsBasedonSemantics.DASFAA2011:164-178TaoJin,JianminWang,LijieWen:EfficientRetrievalofSimilarBusinessProcessModelsBasedonStructure.OTMConferences2011:56-63TaoJin,JianminWang,NianhuaWu,MarcelloLaRosa,ArthurH.M.terHofstede:EfficientandAccurateRetrievalofBusinessProcessModelsthroughIndexing.OTMConferences2010:402-409TaoJin,LijieWen,JianminWang;ClassificationandDeterminationofCausalRelationBetweenTasks;ChineseConferenceonPetriNet,2011TaoJin,LijieWen;Indexingtechnologyforbusinessprocessmodels;ChineseConferenceonBusinessProcessManagement,2011NianhuaWu,TaoJin,HaipingZha,TengfeiHe,LijieWen,JianminWang;BeehiveZ:AnOpenFrameworkforBusinessProcessModelManagement;NationalDatabaseConferenceofChina,2010LinMia