业务过程模型检索与重构

1、金涛业务过程模型检索与重构提纲背景介绍模型检索精细任务执行关系计算并行化重构总结与展望业务过程管理技术应用广泛Surveys over the past five years haveshown process management to be the number one concern of senior executives Gartner, 2010Gartner Prediction: “By 2014, 40% of business managers and knowledge workers in Global 2000 enterprises will use compreh

2、ensive business process models to support their daily work, up from 6% in 2009.” 业务过程模型数据日益增多SAP参考模型 600+Haier 3,000+SunCorp 6,000+中国移动 8,000+如何管理？将业务过程模型视为一种非结构化数据EPC、BPMN、BPEL、YAWL、Petri net、JPDL、XPDL、假设1模型基于图 (存在基于规则的模型)假设2所有模型均由或者转化为workflow net表示业务过程模型格式多种多样研究问题一模型检索关注性能模型复用提高建模效率避免重复存储业务整合相似业务

3、过程的检索北车集团20多个子公司合并，业务流程整合中国移动30多个分公司的业务集中化SOA服务的查找与组合基于BPEL模型检索分类基于结构的精确查询基于行为的精确查询基于结构的相似检索基于行为的相似检索问题子图匹配算法为NPC问题基于最大公共子图的相似度计算为NPC问题基于结构的检索精确查询相似检索问题行为的计算复杂度高基于行为的检索精确查询 A-D & B|C相似检索Filtering-verification framework索引用于过滤减少复杂计算次数索引元素的选取索引元素的快速提取基于索引的查询处理使用索引过滤有向图，唯一的源点和终点，边不带标签，变迁结点带标签（任意长度字符

4、串）Label多，频繁子图少需要考虑label的相似性具有行为语义业务过程模型特点W(l): l中单词个数SCW(l1,l2): l1中单词能在l2中找到同义词的个数可替换为其他基于term的相似性度量Label相似性度量业务过程模型样本特征数据数据集集模型模型数数变迁变迁总数总数路由路由变迁变迁标签总数标签总数#1.00.90.80.70.60.5DG1141035153819806802747710595464SAP591401316533146306230582786269323662036TC1231595352126212521249118311361009818数据数据集集模型模型

5、数数变迁数变迁数库所数库所数弧数弧数图密度图密度AvgMaxAvgMaxAvgMaxAvgMaxDG1149349.73319.3700.10.5SAP5916.85310.66517.71420.20.5TC123133911.53226.3800.10.2DG(114)DG(114)# #1.01.00.90.90.80.80.70.70.60.60.50.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(

6、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)SAP(591)# #1.01.00.90.90.80.80.70.70.60.60.50.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

7、)9(20)18(69)34(190)#11/59111/59111/59111/59111/59133/59144/591业务过程模型库频繁子图TC(123)TC(123)# #1.01.00.90.90.80.80.70.70.60.60.50.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业务过程模型

8、库频繁子图用户决定是否考虑label相似性用户在查询处理过程决定label相似度阈值Filtering：扩展查询条件Verfication：结合label相似性构造独立于其它索引的label索引Label相似性考虑1.1 基于结构的精确检索基于路径建立索引路径长度：路径上的结点数目示例查询处理Stage 1: filteringStage 2: refinementEvaluationImplement in BeehiveZL1P indexL2CP indexExperiments on two datasetsSAP R/3 (600+)synthesis set (40,000+)1.

9、2 基于结构的相似检索queryu没有模型包含查询对象为子图u如果我们放松约束，pn2和pn4可以作为近似结果返回基于最大公共边子图的相似度计算任务边索引任务边和模型之间的映射查询处理Filtering从查询对象中抽取任务边得到候选模型集合Refinement计算候选模型和查询对象模型之间的相似度值索引和查询处理FilteringTask edgeTask edgemodelmodel1,2,311,21Candidate set: Candidate set: pn1pn2100%RefinementResult set: Result set: pn1100%1.3 基于行为的精确检索行为

10、的计算基于ordering relationscausalconflictconcurrency任务关系索引行为计算性能比较给定一个模型，如何快速检索出与之行为相似的模型?1.4 基于行为的相似检索采用TAR相似度Haiping Zha, Jianmin Wang, Lijie Wen, Chaokun Wang, Jiaguang Sun: A workflow net similarity measure based on transition adjacency relations. Computers in Industry (CII) 61(5):463-471 (2010)问题计算

11、性能不好基于可达图，存在状态空间爆炸问题新方案使用Unfolding技术Javier Esparza, Stefan Rmer, Walter Vogler: An Improvement of McMillans Unfolding Algorithm. Formal Methods in System Design (FMSD) 20(3):285-310 (2002)行为相似度TAR计算TARsI-AA-BA-CB-CC-BB-DC-DD-ED-FF-AI-GF-G查询处理m1TARIndexTARIndexInvertedForward“A,B”-m1m1-(“A,B”,”A,C”,

12、“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”Filtering models based on inverted indexm1Computing TAR similarity with the help of forward index1.0Return the models that satisfy the similarity threshold requirementImplemented Sys

13、temTAR计算性能比较小结贡献在BPM领域最先开始关注模型检索的效率使用索引技术全面支持4种类型的模型检索未来工作嵌套模型的检索研究问题二精细任务执行关系计算问题I和A之间的因果关系，C和D之间的因果关系一样吗？B和D之间的并行关系，B和C之间的并行关系一样吗？更细粒度的行为分析，用于：基于行为的检索业务规则符合性检测基于模型执行实例中一个任务的出现是否一定伴有另一个任务的出现1.充分必要因果关系t1=t2任意一个包含t1的实例中必包含t2满足t1-t2。任意一个包含t2的实例中必包含t1满足t1-t2。2.必要不充分因果关系t1=|t2包含t1的实例中可能包含t2满足t1-t2。任意一个包

14、含t2的实例中一定包含t1满足t1-t2。3.充分不必要因果关系t1|=t2任意一个包含t1的实例中必然包含t2满足t1-t2。包含t2的实例中可能包含t1满足t1-t2。4.既不充分也不必要因果关系t1|=|t2包含t1的实例中可能存在t2满足t1-t2。包含t2的实例中可能存在t1满足t1-t2。行为因果关系的分类基于Mcmillan改进算法基于完全有限前缀遍历库所判定前驱、后继事件的因果关系根据库所类别区别对待（截断库所、通信库所、一般库所）截断处理不紧邻事件因果关系的传递共计16个传递性规则判定要点并行关系的分类遍历库所1|=3, 3=4截断处理2|=3因果传递1|=4, 2|=4示例

15、小结贡献不同因果关系细分不同并行关系细分判定及传递规则针对无环模型的判定算法未来工作针对有环模型的处理研究问题三并行化重构问题给定一个合理的结构化工作流网模型，尽可能的将其并行化重构以提升业务流程处理的效率.基于数据流分析将不必要顺序执行的任务并行化前提假设给定模型为合理的结构化工作流网模型，并带有数据操作如果两个任务之间存在因果关系或者传递因果关系，则必有数据操作依赖直接因果关系并行关系间接因果关系并行关系间接因果关系直接因果关系解决方案Extract task relationsAnalyze data operation dependenceUpdate task relationsRe

16、factor modelRefactor model有效性最大程度的并行化所有原始数据依赖关系都得到了保持没有引入新的数据依赖关系随机生成模型10,000 modelsMaximum number of transitions per model: 50Maximum number of data items per model: nMaximum number of tasks operating on one data item: n有效性重构前TS = 0重构后Min(TS) = 0Max(TS) = 48Avg(TS) = 3Stdev(TS) = 6.12效率小结贡献问题: 首次提出

17、了过程模型的并行化重构问题方法: 首次使用过程挖掘技术解决重构问题工具: BeehiveZ未来工作重构后的模型是否合理？总结贡献点首先关注模型检索效率问题首先开展了基于行为的模型检索提出了不确定性因果关系、并行关系的分类及判定提出了模型的并行化重构问题并给出了解决方案BeehiveZ开源系统未来工作嵌套模型的检索有环模型的不确定性行为判定重构模型的合理性已发表论文Tao Jin, Jianmin Wang, Lijie Wen: Efficient Retrieval of Similar Workflow Models Based on Behavior. APWeb 2012:677-68

18、4Tao Jin, Jianmin Wang, Lijie Wen: Efficiently Querying Business Process Models with BeehiveZ. BPM (Demos) 2011Tao Jin, Jianmin Wang, Lijie Wen: Querying Business Process Models Based on Semantics. DASFAA 2011:164-178Tao Jin, Jianmin Wang, Lijie Wen: Efficient Retrieval of Similar Business Process M

19、odels Based on Structure. OTM Conferences 2011:56-63Tao Jin, Jianmin Wang, Nianhua Wu, Marcello La Rosa, Arthur H. M. ter Hofstede: Efficient and Accurate Retrieval of Business Process Models through Indexing. OTM Conferences 2010:402-409Tao Jin, Lijie Wen, Jianmin Wang; Classification and Determina

20、tion of Causal Relation Between Tasks; Chinese Conference on Petri Net, 2011Tao Jin, Lijie Wen; Indexing technology for business process models; Chinese Conference on Business Process Management, 2011Nianhua Wu, Tao Jin, Haiping Zha, Tengfei He, Lijie Wen, Jianmin Wang; BeehiveZ:An Open Framework for Business Process Model Management; National Database Conference of China, 2010Lin Miao, Tao Jin, Jianmin Wang; Transformation Technology from XPDL Model to WWF M