业务过程模型库索引技术研究 金涛 清华大学

业务过程管理技术应用广泛 Surveys  over  the  past  five  years  have shown  process management to be the number one concern of senior executives [Gartner, 2010] Gartner Prediction: “By 2014, 40% of business managers and knowledge workers in Global 2000 enterprises will use comprehensive business process models to support their daily work, up from 6% in 2009.”

业务过程模型数据日益增多 SAP参考模型 600+ Haier 3,000+ SunCorp 6,000+ 北车集团 200,000+

模型检索 模型重用 业务整合 SOA 提高建模效率 避免重复存储 相似业务过程的检索 服务的查找与组合 基于BPEL 北车集团20多个子公司合并，业务流程整合 SOA 服务的查找与组合 基于BPEL

模型检索分类 基于结构的精确查询 基于行为的精确查询 基于结构的相似检索 基于行为的相似检索

基于结构的检索 精确查询 相似检索 问题 子图匹配算法为NPC问题 图的相似度计算为NPC问题

基于行为的检索 精确查询 A->D && B||C 相似检索 问题 行为的计算复杂度高

使用索引过滤 Filtering-verfication framework 索引用于过滤 索引元素 索引元素的快速提取 基于索引的查询处理

评价指标 有效性（Effectiveness） 效率（Efficiency） 可扩展性（Scalability） Precision: 100% Recall: 100% 效率（Efficiency） 时间（Time efficiency） 查询时间、索引建立（更新）时间 空间（Space efficiency） 索引存储空间大小 可扩展性（Scalability） 效率随规模的变化

相关研究1——图数据库管理 基于结构的精确查询 基于结构的相似检索 基于feature：GraphGrep (PODS2002)、gIndex (SIGMOD2004,TODS2005)、TreePi (ICDE2007)、 Tree+Delta (VLDB2007)、FG-Index (FG*-Index) (SIGMOD2007,TODS2009)、Swift-index (PVLDB2008) 基于closure：Closure-tree (ICDE2006) 基于分解：GDIndex (ICDE2007) 基于编码：summarization graph index (DASFAA2008)、 Gstring (ICDE2007)、Gcoding (EDBT2008) Diskbased benchmark：iGraph (PVLDB2010) 基于结构的相似检索 RASCAL (THE COMPUTER JOURNAL 2002) Grafil (SIGMOD2005,TODS2006)

常用数据库 AIDS Antiviral Screen dataset Chemical molecule Count: 43,905 Avg: 25.4 vertices and 27.3 edges Max: 222 vertices and 251 edges Labels: 62 (vertex) and 3 (edge)

业务过程模型特点 有向图，唯一的源点和终点，边不带标签，变迁结 点带标签（任意长度字符串） Label多，频繁子图少 存在模型嵌套 具有行为语义

相关研究2——业务过程模型查询 BP-QL (VLDB2005,VLDB2006,IS2008) WISE (ICDE2009) VisTrail (SIGMOD2008) BPMN-Q (WWW2010,DASFAA2010) n-gram index (ICWS2006) conf/otm/YanDG10 (CoopIS2010)

我们的工作 Label相似性的考虑 基于结构的精确检索 基于结构的相似检索 基于行为的精确检索 基于行为的相似检索 PathIndex 基于结构的相似检索 TaskEdgeIndex 基于行为的精确检索 TaskRelationIndex 基于行为的相似检索 TARIndex http://code.google.com/p/beehivez/

Label相似性考虑 用户决定是否考虑label相似性 用户在查询处理过程决定label相似性阈值 Filtering：扩展查询条件 Verfication：结合label相似性 构造独立于其它索引的label索引

基于行为的查询 行为计算基于unfolding技术

未完工作——模型嵌套处理 查询样例 借鉴上下文无关文法 FIRST FOLLOW SELECT

未完工作——基于bisimulation的相似性度量 pn1和pn2等价吗？

http://code.google.com/p/beehivez/

Q & A

业务过程模型样本特征 数据集 模型数 变迁数 库所数 弧数 图密度 Avg Max DG 114 9 34 9.7 33 19.3 70 0.1 0.5 SAP 591 6.8 53 10.6 65 17.7 142 0.2 TC 123 13 39 11.5 32 26.3 80 数据集 模型数 变迁总数 路由变迁 标签总数 # 1.0 0.9 0.8 0.7 0.6 0.5 DG 114 1035 153 819 806 802 747 710 595 464 SAP 591 4013 1653 3146 3062 3058 2786 2693 2366 2036 TC 123 1595 352 1262 1252 1249 1183 1136 1009 818

业务过程模型库频繁子图 DG(114) # 1.0 0.9 0.8 0.7 0.6 0.5 2/114 60478 (33) 60481 (35) 61084 (47) 61073 (46) 179607(50) 70567 (67) 4/114 416 (7) 419 (11) 437 (13) 434 (10) 440 (17) 7/114 59 (7) 102 (7) 122 (9) 122 (8) ## 8/114 9/114

业务过程模型库频繁子图 SAP(591) # 1.0 0.9 0.8 0.7 0.6 0.5 4/591 1747 (141) 1922 (154) 2298 (178) 2303 (192) 3862 (237) 2554 (329) 6/591 199 (84) 203 (97) 216 (122) 219 (125) 270 (188) 322 (270) 10/591 8 (10) 9 (20) 18 (69) 34 (190) ## 11/591 33/591 44/591

业务过程模型库频繁子图 TC(123) # 1.0 0.9 0.8 0.7 0.6 0.5 3/123 2 (15) 4 (17) 10 (23) 13 (26) 27 (42) 81 (73) 7/123 2 (17) 10/123 1 (10) ## 11/123

Label相似性度量 W(l): l中单词个数 SCW(l1,l2): l1中单词能在l2中找到同义词的个数 可替换为其他基于的term的相似性度量