業(yè)務過程模型檢索與重構

金濤業(yè)務過程模型檢索與重構提綱背景介紹模型檢索精細任務執(zhí)行關系計算并行化重構總結與展望業(yè)務過程管理技術應用廣泛Surveys

over

the

past

five

years

have

shown

processmanagementtobethenumberoneconcernofseniorexecutives[Gartner,2010]GartnerPrediction:“By2014,40%ofbusinessmanagersandknowledgeworkersinGlobal2000enterpriseswillusecomprehensivebusinessprocessmodelstosupporttheirdailywork,upfrom6%in2009.”業(yè)務過程模型數據日益增多SAP參考模型600+Haier3,000+SunCorp6,000+中國移動8,000+如何管理？將業(yè)務過程模型視為一種非結構化數據EPC、BPMN、BPEL、YAWL、Petrinet、JPDL、XPDL、……假設1——模型基于圖(存在基于規(guī)則的模型)假設2——所有模型均由或者轉化為workflownet表示業(yè)務過程模型格式多種多樣研究問題一模型檢索關注性能模型復用提高建模效率避免重復存儲業(yè)務整合相似業(yè)務過程的檢索北車集團20多個子公司合并，業(yè)務流程整合中國移動30多個分公司的業(yè)務集中化SOA服務的查找與組合基于BPEL模型檢索分類基于結構的精確查詢基于行為的精確查詢基于結構的相似檢索基于行為的相似檢索問題子圖匹配算法為NPC問題基于最大公共子圖的相似度計算為NPC問題基于結構的檢索精確查詢相似檢索問題

行為的計算復雜度高基于行為的檢索精確查詢A->D&&B||C相似檢索Filtering-verificationframework索引用于過濾減少復雜計算次數索引元素的選取索引元素的快速提取基于索引的查詢處理使用索引過濾有向圖，唯一的源點和終點，邊不帶標簽，變遷結點帶標簽（任意長度字符串）Label多，頻繁子圖少需要考慮label的相似性具有行為語義業(yè)務過程模型特點W(l):l中單詞個數SCW(l1,l2):l1中單詞能在l2中找到同義詞的個數可替換為其他基于term的相似性度量Label相似性度量業(yè)務過程模型樣本特征數據集模型數變遷總數路由變遷標簽總數#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業(yè)務過程模型庫頻繁子圖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業(yè)務過程模型庫頻繁子圖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業(yè)務過程模型庫頻繁子圖用戶決定是否考慮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)問題計算性能不好基于可達圖，存在狀態(tài)空間爆炸問題新方案使用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種類型的模型檢索未來工作嵌套模型的檢索研究問題二精細任務執(zhí)行關系計算問題I和A之間的因果關系，C和D之間的因果關系一樣嗎？B和D之間的并行關系，B和C之間的并行關系一樣嗎？更細粒度的行為分析，用于：基于行為的檢索業(yè)務規(guī)則符合性檢測基于模型執(zhí)行實例中一個任務的出現(xiàn)是否一定伴有另一個任務的出現(xiàn)充分必要因果關系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改進算法基于完全有限前綴遍歷庫所判定前驅、后繼事件的因果關系根據庫所類別區(qū)別對待（截斷庫所、通信庫所、一般庫所）截斷處理不緊鄰事件因果關系的傳遞共計16個傳遞性規(guī)則判定要點并行關系的分類遍歷庫所1|=>3,3=>4截斷處理2|=>3因果傳遞1|=>4,2|=>4示例小結貢獻不同因果關系細分不同并行關系細分判定及傳遞規(guī)則針對無環(huán)模型的判定算法未來工作針對有環(huán)模型的處理研究問題三并行化重構問題給定一個合理的結構化工作流網模型，盡可能的將其并行化重構以提升業(yè)務流程處理的效率.基于數據流分析將不必要順序執(zhí)行的任務并行化前提假設給定模型為合理的結構化工作流網模型，并帶有數據操作如果兩個任務之間存在因果關系或者傳遞因果關系，則必有數據操作依賴直接因果關系并行關系間接因果關系并行關系間接因果關系直接因果關系解決方案ExtracttaskrelationsAnalyzedataoperationdependenceUpdatetaskrelationsRefactormodelRefactormodel有效性最大程度的并行化所有原始數據依賴關系都得到了保持沒有引入新的數據依賴關系隨機生成模型10,000modelsMaximumnumberoftransitionspermodel:50Maximumnumberofdataitemspermodel:nMaximumnumberoftasksoperatingononedataitem:n有效性重構前TS=0重構后Min(TS)=0Max(TS)=48Avg(TS)=3Stdev(TS)=6.12效率小結貢獻問題:首次提出了過程模型的并行化重構問題方法:首次使用過程挖掘技術解決重構問題工具:BeehiveZ未來工作重構后的模型是否合理？總結貢獻點首先關注模型檢索效率問題首先開展了基于行為的模型檢索提出了不確定性因果關系、并行關系的分類及判定提出了模型的并行化重構問題并給出了解決方案BeehiveZ開源系統(tǒng)未來工作嵌套模型的檢索有環(huán)模型的不確定性行為判定重構模型的合理性已發(fā)表論文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