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

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

over

the

past

five

years

have

shown

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

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

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

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

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

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