業(yè)務(wù)過程模型檢索與重構(gòu)

金濤業(yè)務(wù)過程模型檢索與重構(gòu)提綱背景介紹模型檢索精細任務(wù)執(zhí)行關(guān)系計算并行化重構(gòu)總結(jié)與展望業(yè)務(wù)過程管理技術(shù)應(yīng)用廣泛Surveys

over

the

past

five

years

have

shown

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

行為的計算復(fù)雜度高基于行為的檢索精確查詢A->D&&B||C相似檢索Filtering-verificationframework索引用于過濾減少復(fù)雜計算次數(shù)索引元素的選取索引元素的快速提取基于索引的查詢處理使用索引過濾有向圖，唯一的源點和終點，邊不帶標簽，變遷結(jié)點帶標簽（任意長度字符串）Label多，頻繁子圖少需要考慮label的相似性具有行為語義業(yè)務(wù)過程模型特點W(l):l中單詞個數(shù)SCW(l1,l2):l1中單詞能在l2中找到同義詞的個數(shù)可替換為其他基于term的相似性度量Label相似性度量業(yè)務(wù)過程模型樣本特征數(shù)據(jù)集模型數(shù)變遷總數(shù)路由變遷標簽總數(shù)#1.00.60.5DG1141035153819806802747710595464SAP591401316533146306230582786269323662036TC1231595352126212521249118311361009818數(shù)據(jù)集模型數(shù)變遷數(shù)庫所數(shù)弧數(shù)圖密度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è)務(wù)過程模型庫頻繁子圖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è)務(wù)過程模型庫頻繁子圖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è)務(wù)過程模型庫頻繁子圖用戶決定是否考慮label相似性用戶在查詢處理過程決定label相似度閾值Filtering：擴展查詢條件Verfication：結(jié)合label相似性構(gòu)造獨立于其它索引的label索引Label相似性考慮1.1基于結(jié)構(gòu)的精確檢索基于路徑建立索引路徑長度：路徑上的結(jié)點數(shù)目示例查詢處理∩Stage1:filteringStage2:refinementEvaluationImplementinBeehiveZL1PindexL2CPindexExperimentsontwodatasetsSAPR/3(600+)synthesisset(40,000+)1.2基于結(jié)構(gòu)的相似檢索query沒有模型包含查詢對象為子圖如果我們放松約束，pn2和pn4可以作為近似結(jié)果返回基于最大公共邊子圖的相似度計算任務(wù)邊索引任務(wù)邊和模型之間的映射查詢處理Filtering從查詢對象中抽取任務(wù)邊得到候選模型集合Refinement計算候選模型和查詢對象模型之間的相似度值索引和查詢處理FilteringTaskedgemodel<A,B>1,2,3<A,C>1<B,D>1,2<C,D>1Candidateset:pn1pn2100%RefinementResultset:pn1100%1.3基于行為的精確檢索行為的計算基于orderingrelationscausalconflictconcurrency任務(wù)關(guān)系索引行為計算性能比較給定一個模型，如何快速檢索出與之行為相似的模型?1.4基于行為的相似檢索采用TAR相似度HaipingZha,JianminWang,LijieWen,ChaokunWang,JiaguangSun:Aworkflownetsimilaritymeasurebasedontransitionadjacencyrelations.ComputersinIndustry(CII)61(5):463-471(2010)問題計算性能不好基于可達圖，存在狀態(tài)空間爆炸問題新方案使用Unfolding技術(shù)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計算性能比較小結(jié)貢獻在BPM領(lǐng)域最先開始關(guān)注模型檢索的效率使用索引技術(shù)全面支持4種類型的模型檢索未來工作嵌套模型的檢索研究問題二精細任務(wù)執(zhí)行關(guān)系計算問題I和A之間的因果關(guān)系，C和D之間的因果關(guān)系一樣嗎？B和D之間的并行關(guān)系，B和C之間的并行關(guān)系一樣嗎？更細粒度的行為分析，用于：基于行為的檢索業(yè)務(wù)規(guī)則符合性檢測基于模型執(zhí)行實例中一個任務(wù)的出現(xiàn)是否一定伴有另一個任務(wù)的出現(xiàn)充分必要因果關(guān)系t1=>t2

任意一個包含t1的實例中必包含t2滿足t1->t2。任意一個包含t2的實例中必包含t1滿足t1->t2。必要不充分因果關(guān)系t1=>|t2

包含t1的實例中可能包含t2滿足t1->t2。任意一個包含t2的實例中一定包含t1滿足t1->t2。充分不必要因果關(guān)系t1|=>t2

任意一個包含t1的實例中必然包含t2滿足t1->t2。包含t2的實例中可能包含t1滿足t1->t2。既不充分也不必要因果關(guān)系t1|=>|t2

包含t1的實例中可能存在t2滿足t1->t2。包含t2的實例中可能存在t1滿足t1->t2。行為因果關(guān)系的分類基于Mcmillan改進算法基于完全有限前綴遍歷庫所判定前驅(qū)、后繼事件的因果關(guān)系根據(jù)庫所類別區(qū)別對待（截斷庫所、通信庫所、一般庫所）截斷處理不緊鄰事件因果關(guān)系的傳遞共計16個傳遞性規(guī)則判定要點并行關(guān)系的分類遍歷庫所1|=>3,3=>4截斷處理2|=>3因果傳遞1|=>4,2|=>4示例小結(jié)貢獻不同因果關(guān)系細分不同并行關(guān)系細分判定及傳遞規(guī)則針對無環(huán)模型的判定算法未來工作針對有環(huán)模型的處理研究問題三并行化重構(gòu)問題給定一個合理的結(jié)構(gòu)化工作流網(wǎng)模型，盡可能的將其并行化重構(gòu)以提升業(yè)務(wù)流程處理的效率.基于數(shù)據(jù)流分析將不必要順序執(zhí)行的任務(wù)并行化前提假設(shè)給定模型為合理的結(jié)構(gòu)化工作流網(wǎng)模型，并帶有數(shù)據(jù)操作如果兩個任務(wù)之間存在因果關(guān)系或者傳遞因果關(guān)系，則必有數(shù)據(jù)操作依賴直接因果關(guān)系并行關(guān)系間接因果關(guān)系并行關(guān)系間接因果關(guān)系直接因果關(guān)系解決方案ExtracttaskrelationsAnalyzedataoperationdependenceUpdatetaskrelationsRefactormodelRefactormodel有效性最大程度的并行化所有原始數(shù)據(jù)依賴關(guān)系都得到了保持沒有引入新的數(shù)據(jù)依賴關(guān)系隨機生成模型10,000modelsMaximumnumberoftransitionspermodel:50Maximumnumberofdataitemspermodel:nMaximumnumberoftasksoperatingononedataitem:n有效性重構(gòu)前TS=0重構(gòu)后Min(TS)=0Max(TS)=48Avg(TS)=3Stdev(TS)=6.12效率小結(jié)貢獻問題:首次提出了過程模型的并行化重構(gòu)問題方法:首次使用過程挖掘技術(shù)解決重構(gòu)問題工具:BeehiveZ未來工作重構(gòu)后的模型是否合理？總結(jié)貢獻點首先關(guān)注模型檢索效率問題首先開展了基于行為的模型檢索提出了不確定性因果關(guān)系、并行關(guān)系的分類及判定提出了模型的并行化重構(gòu)問題并給出了解決方案BeehiveZ開源系統(tǒng)未來工作嵌套模型的檢索有環(huán)模型的不確定性行為判定重構(gòu)模型的合理性已發(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