《deepweb集成服务的不确定模式匹配推广》由会员分享，可在线阅读，更多相关《deepweb集成服务的不确定模式匹配推广（10页珍藏版）》请在金锄头文库上搜索。
1、第31卷 第8期 2008年8月计 算 机 学 报 CHINESE JOURNAL OF COMPU TERSVol. 31No. 8 Aug. 2008收稿日期:2008204213 ;最终修改稿收到日期:2008206230.本课题得到国家自然科学基金(60573091)、 国家 “八六三” 高技术研究发展计划 项目基金(2007AA01Z155)、 国家基础研究与发展 “语义网格” 项目基金(2003CB317000)和新世纪优秀人才支持计划资助.姜芳艽,女,1971年生,博士研究生,主要研究方向为Web数据管理与集成. E2mail : jiangfj .孟小峰,男,1964年生,教授
2、,博士生导师,主要研究领域为Web数据管理、XML数据库、 移动数据管理等.贾琳琳,女,1984年生,硕士研究生,主要研究方向为Web数据管理与集成.Deep Web集成服务的不确定模式匹配姜芳艽1) ,2)孟小峰1)贾琳琳1)1)(中国人民大学信息学院 北京 100872)2)(徐州师范大学 江苏 徐州 221116)摘 要 随着Deep Web的迅猛发展,从高度自治、 异构及动态变化的Web数据库中,为用户提供高质量的数据逐 渐成为当前Deep Web集成服务的一个研究热点.在大部分Web数据库只能通过查询接口为用户提供服务的前提 下,如何建立用户请求与集成查询接口模式之间以及集成查询接口
3、模式与Web数据库查询接口模式之间的匹配 关系,是Deep Web集成服务中进行合理的用户请求转换的关键.之前的相关工作都是寻找最佳的匹配结果,回避 匹配的不确定性,丢弃了可能有价值的其他匹配结果.文中首先剖析了请求转换中模式匹配的不确定性,提出了数 字类型的相似度计算方法,给出了进行数字类型的模式匹配的有效的剪枝方法以及数据类型驱动的模式匹配优化 方法,并在此基础上提出了一种基于相似度计算的不确定性模式匹配方法,最后通过大量的实验证明了该方法的 有效性.关键词 Deep Web;集成服务;相似度;模式匹配;不确定性 中图法分类号TP311Uncertain Schema Matching i
4、n Deep Web Integration ServiceJ IANG Fang2Jiao1) ,2) MENG Xiao2Feng1)J IA Lin2Lin1)1)(School of Inf ormation , Renmin University of China , Beijing 100872)2)( Xuzhou Normal University , Xuzhou, Jiangshu 221116)Abstract With increasing of Deep Web , providing high quality data from autonomous , heter
5、o2 geneous and dynamic Web databases to users is becoming a hot topic in recent research of Deep Web integration service. How to generate the reasonable schema matching between the keywords of the user request and schema of integrated interface as well as between the schema of integrated interface a
6、nd that of Web database interface is essential. The related works about schema matc2 hing are generating the best schema matching which slide over its uncertainty. This paper analy2 zes the uncertainty of schema matching , and then proposes a series of similarity measures. To re2 duce the cost of ex
7、ecution , it proposes the type2based optimization method and schema matching pruning method of numeric data. Based on above analysis , this paper proposes the uncertain sche2 ma matching method. The experiments prove the effectiveness and efficiency of the new method.Keywords Deep Web ; integration
8、service ; similarity ; schema matching ; uncertainty1 引 言近年来,Deep Web1的发展非常迅猛,2004年大约有450000个Deep Web数据源,这些分布自治的资源集合的数据量是Surface Web的500倍以 上,而且目前仍呈指数级的增长趋势.为了使用户快 速地获得高质量的数据,Deep Web集成服务应运而生了. Deep Web集成服务是将Web上通过查询 接口提供Web服务的结构化数据源按领域形成为 统一服务的过程,其基本框架如图1所示.对于用户 而言,集成服务是透明的,即用户无须再面对数百万 个Web服务,不需要关心所
9、需要的数据存储在哪 里,更不需要了解如何获取这些数据.用户只需在类 似于传统的基于关键字搜索引擎的查询接口的用户 层提交用户请求,由集成服务的服务层与资源层交 互,自动完成Web服务的发现与分类,自动进行模 式匹配以完成用户请求的转换,协同各Web服务完 成查询的处理,自动完成对结果数据的合并,最后将 高质量的结果数据返回给用户.而且集成服务能够 适应Web服务自治性和动态性强的特点,具有自适 应和动态演化的能力.图2 用户请求转换中的模式匹配不确定模式匹配的定义如下:源模式S ,目标模 式T , S和T均为关系模式, S到T的不确定模式匹 配为一个三元组(s, t, m) ,其中sS , t
10、T ,并且m 是S到T可能的模式匹配的集合 mi . mi满足传统 的模式匹配的定义,即m :x (j) , Ci与Cj的候选值集合分别为Vi和Vj(均为数字型) ,用户查询包含数字型关键字Key1 和Key2,且Key1和Key2必与Ci与Cj中的一个匹 配.另若A与B匹配,记作 A ,B ,分以下几种情况:(1)无覆盖ViVj=,即概念Ci与概念Cj的候选值之间 不存在任何覆盖的关系,如图3(a) .关键字Key1Key2,且Key1, Key2(Vi或Vj) ,那么根据关键字 的值的大小可以准确判断与概念Ci和Cj的匹配关 系为下面的情况之一:图3 各类匹配关系若Key1Vi,Key2V
11、j,则匹配结果为 Key1, Ci , Key2, Cj ; 若Key1Vj,Key2Vi,则匹配结果为 Key1, Cj , Key2, Ci .(2)松散部分覆盖ViVj,即概念Ci与概念Cj的候选值之 间存在互相覆盖的关系,Vi和Vj之间无约束关系或 者很难捕捉到其约束关系,但是覆盖程度比较小,如 图3(b) .一般地,对于关键字Key1和Key2: 若Key1|(ViVj)且Key2|(ViVj) ,匹 配方法同(1) ;若Key1(ViVj)且Key2(Vj-Vi) ,根 据匹配的互斥性,得到匹配结果 Key1, Ci , Key2,Cj ;反之亦然; 若Key1(ViVj)且Key
12、2(ViVj) ,则不能判断匹配关系,需要进一步计算两者的相似度.(3)松散覆盖ViVj,即概念Ci与概念Cj的候选值之 间存在互相覆盖的关系,Vi和Vj之间无约束关系或 者很难捕捉到其约束关系,而且覆盖程度比较大,如 图3(c) .则不能判断匹配关系,需要进一步计算两 者的相似度.(4)单一约束覆盖ViVj,即概念Ci与概念Cj的候选值之 间存在互相覆盖的关系,且Vi和Vj之间有简单的约 束关系.例如,对于概念Ci与概念Cj的一对取值 Vi,Vj,Vi总是小于Vj,如图3(d) .如果Key1Vj且Key1, Key2Vi,Vj,若Key1,即概念Ci与概念Cj的候选值之 间存在互相覆盖的关
13、系,且Vi和Vj之间有复杂的约 束关系,例如,对于概念Ci与概念Cj的一对取值 Vi,Vj,即Vi与Vj满足的约束关系不是单一的,但Vi与Vj在分段上满足单一约束覆盖(第4种情况) ,即在每一段上满足单一约束覆盖,如图3(e) .我们 可以先分段,再根据对上述第4种方法分段判断关 键字与概念的匹配关系.一般地,概念Ci与概念Cj 的任意一对取值 Vi,Vj: 若 Vi, VjSegment1, ViVj且Key1k) .即不存在某个概念同时对应多个关键字.类似地,对于任意一个概念Cj, ? (A CM(Ai, Cj)(A CM ( Ak, Cj) ) ( ik) .即计 算 机 学 报2008
14、年(9)(b)若候选值为数字型,则二者的相似度为候 选值的重复程度(离散值,如式(10) )或覆盖程度(连 续范围值,如式(11) ) :SimV(Ai, Cj)=|AViCVj| |AViCVj|j)=Sim( Keyi, Cj)(5)其中, Sim是关键字和概念的候选值之间的实例相 似度.41212 相似度计算313节已经分析过,查询转换只在相同数据类型 之间进行,因此模式匹配问题也限定在相同数据类型 的关键字、 概念或属性之间(不同数据类型关键字、 概念或属性之间的相似度为0) .而且对于312节已 经可以判断出的匹配,则不必再计算其相似度(其相 似度为1) .(1)关键字与概念的相似度
15、计算在关键字与集成接口概念的匹配中,主要是计 算关键字与概念的候选值集合之间的匹配关系,通 过计算两者实例的相似度得到. 如果关键字Keyi和概念Cj同属于字符类型,则 将Keyi与概念Cj的候选值集合CVj中的每一个值 相比较,选择相似度值最大的作为关键字Keyi和概 念Cj的相似度,其中隐含了这样一个原则:如果概 念Cj的候选值集合中包含与关键字Keyi类似的字 符串,越类似则Keyi与Cj越相似,相似度计算如 式(6) :Sim ( Keyi, Cj)=max1 -editdistance( Keyi, CVjk) max(|Keyi|,|CVjk|)不存在某个概念同时对应Web数据库查
16、询接口的 多个属性.因为前面我们提到,集成查询接口的概念 是重要的而且是最详细的. 定义10. 可能模式匹配的可信度PSMC(Pos2sible Schema Matching Conviction).它是综合考虑可 能模式匹配KCM ( Key1, C1)A CM ( Key2, C2) A CM( Keyj, Cj)或A CM ( A1, C1)A CM ( A2,C2)A CM(Ak, Ck)中各关键字概念或属性概 念匹配程度后,得到的评价可能模式匹配优劣的 标准. 它与各KCMD或A CMD的值密切相关.直观 地, KCMD或A CMD的值越高,代表匹配越合理, 那么包含这样的KCM或A CM的PSM就可能越 好.考虑到各概念在复杂查询接口上的重要程度的 不同,我们赋予其的权重也有差异.因此可能模式匹 配的可信度是相
