




已阅读5页,还剩77页未读, 继续免费阅读
(计算机应用技术专业论文)数据库模式匹配系统研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 摘要 随着信息化时代的不断发展,对发掘异构模式之间语义一致性的要求 日益迫切。模式匹配作为模式操作的第一步,在数据集成、数据转换、模 型管理等领域都起到了非常关键的作用。本文对国内外关于模式匹配的研 究现状进行了综合分析,从一个全新的角度对复杂的模式匹配方法进行了 研究。 首先,介绍了现有的两种复杂模式匹配方法。通过全面分析这两种方 法中各处理单元的功能及应用的相关技术,指出了两种方法各自的优点和 存在的不足。 其次,基于以上的研究成果和现有的解决方案,提出了扩展的复杂模 式匹配系统c s m 。它可通过预处理和聚类处理分别从数据类型和数据值上 过滤掉部分不合理的侯选匹配,并在匹配产生器中利用多个具有专门目的 的检索程序对候选匹配空间的特殊部分进行检索,发掘1 :1 和复杂匹配; 应用相似度估价器对候选匹配进行估价并由匹配选择器选择出最优的候选 匹配;针对被匹配模式中存在不透明列的情况,还可迸一步应用补充匹配 器发掘不透明列间的匹配关系。从而发掘出全面、合理的匹配对。 再次,根据全集进行模式匹配的思想,提出新的模式匹配方法基 于全集的复杂模式匹配。针对被匹配模式中缺乏匹配信息的问题,应用已 知模式和模式间映射的全集为被匹配模式增添信息,提高匹配的查全率和 查准率。 最后,应用实例分析了上述两种模式匹配方法的匹配过程,并分别从 理论和实验上证明了两种方法的可行性及有效性。 关键词模式匹配:复杂匹配;聚类;相似度;交互信息:全集 燕山大学工学硕士学位论文 a b s t r a c t w i t l lt h ed e v e l o p m e n to fi n f o r m a t i o na g e t h ed e m a n do fd i s c o v e r i n g s e m a n t i c c o n s i s t e n c y b e t w e e nd i f f e r e n ts c h e m a sh a sb e e ni m m i n e n c e i n c r e a s i n g l y s c h e m am a t c h i n ga st h ef i r s ts t e po fs c h e m ao p e r a t i o n , i th a sa c r u c i a le f f e c ti nm a n yf i e l d s ,s u c ha sd a t ai n t e g r a t i o n ,d a t at r a n s l a t i o na n d m o d e lm a n a g e m e n t t h i sp a p e ra n a l y z e st h ec u r r e n ts i t u a t i o no ft h ed o m e s t i c a n di n t e r n a t i o n a ls c h e m am a t c h i n gp r o b l e m ,a n dr e s e a r c h e sf o rt h ep r o b l e mo f c o m p l e xs c h e m am a t c h i n gf r o mac o m p l e t e l yn e wp e r s p e c t i v e a tf i r s t , t h et w ok i n d so fe x i s t i n gc o m p l e xs c h e m am a t c h i n gm e t h o d sa r e i n t r o d u c e d t h i sp a p e rp o i n t so u tt h em e r i t sa n dd e m e r i t si ne a c hm e t h o d t h r o u g ha n a l y z i n gt h ef u n c t i o no fe a c hp r o c e s sm o d u l ea n dt h ei n t e r r e l a t e d t e c h n o l o g i e si nt h et w om e t h o d si na na l l - r o u n dw a y , s e c o n d l y , o nt h eb a s i so ft h ea b o v er e s e a r c ha n de x i s t e n ts o l u t i o n s ,t h e e x t e n d e dc o m p l e xs c h e m am a t c h i n gs y s t e mc s mi sp r o p o s e d i tf i l t e r ss o m e u n r e a s o n a b l em a t c h e so nd a t at y p e sa n dv a l u e sb yp r e p r o c e s sa n dc l u s t e r i n g p r o c e s s ,a n de m p l o y sas e to fs p e c i a l - p u r p o s es e a r c hp r o c e d u r e si nm a t c h g e n e r a t o rt oe x p l o r eas p e c i a l i z e dp o r t i o no f t h es e a r c hs p a c ea n dd i s c o v e r s1 :l a n dc o m p l e xm a t c h e s ;i te s t i m a t e sc a n d i d a t em a t c h e sa n ds e l e c t s o p t i m a l c a n d i d a t em a t c h e sb yu s i n gs i m i l a r i t ye s t i m a t o ra n dm a t c hs e l e c t o rr e s p e c t i v e l y ; a c c o r d i n gt ot h ep r o b l e mt h a tt h e r ea r eo p a q u ec o l u m n si nt h es c h e m a sb e i n g m a t c h e d ,i tc a na p p l yc o m p l e m e n t a r ym a t c h e rt of i n dm a t c h i n gr e l a t i o n s b e t w e e no p a q u ec o l u m n sf u r t h e rm o r e t h e r e b yi tc a nd i s c o v e rm o r eg e n e r a l , r e a s o n a b l em a t c h i n gp a i r s m o r e o v e r , d e p e n d i n go nt h ei d e ao fu s i n gac o r p u st oa c c o m p l i s hs c h e m a m a t c h i n g ,an e ws c h e m am a t c h i n gm e t h o dn a m e dc o r p u s - b a s e dc o m p l e x s c h e m am a t c h i n gi s p r o p o s e d a c c o r d i n gt o t h ep r o b l e mo ft h el a c ko f a b s t r a c t s u f f i c i e n te v i d e n c ei nt h es c h e m a s b e i n gm a t c h e d ,i tc a l lu s eak n o w nc o r p u so f s c h e m a sa n dm a p p i n g sb e t w e e ns c h e m a st oa u g m e n tt h ee v i d e n c ea b o u tt h e s c h e m a sb e i n gm a t c h e d ,t h e r e b yi m p r o v e st h em a t c h i n gr e c a l la n dp r e c i s i o n f i n a l l y , w ea n a l y z et h em a t c h i n gp r o c e s so ft h et w os c h e m am a t c h i n g m e t h o d sa sa b o v eu s i n gi n s t a n c e s a n dp r o v et h e i rf e a s i b i l i t ya n dv a l i d i t yb y t h e o r ya n de x p e r i m e n t k e y w o r d ss c h e m am a t c h i n g ;c o m p l e xm a t c h i n g ;c l u s t e r i n g ;s i m i l a r i t y ; m u t u a li a f o r m a t i o n ;c o r p u s 燕山大学硕士学位论文原创性声明 本人郑重声明:此处所提交的硕士学位论文数据库模式匹配系统研 究,是本人在导师指导下。在燕山大学攻读硕士学位期间独立进行研究工 作所取得的成果。据本人所知,论文中除已注明部分外不包含他人己发表 或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体,均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字 械颍 1 日期:d 弼年帕月如日 燕山大学硕士学位论文使用授权书 数据库模式匹配系统研究系本人在燕山大学攻读硕士学位期间在 导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有,本 人如需发表将署名燕山大学为第一完成单位及相关入员。本人完全了解燕 山大学关于保存、使用学位论文的规定,同意学校保留并向有关部门送交 论文的复印件和电子版本,允许论文被查阅和借阅。本人授权燕山大学, 可以采用影印、缩印或其他复制手段保存论文,可以公布论文的全部或部 分内容。 保密口,在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名: 辆瓶 日期:蚴5 年月如日 导师繇c ;、l 确 吼衫年护的日 第1 章绪论 1 1 研究背景 第1 章绪论 s e m a n t i cw e b 是互联网缔造者t i mb e m e r s l e e 规划的下一代w w w , s e m a n t i cw e b 预想w e b 的内容不再是杂乱的,而是机器都可以识别和处理 的内容。它针对的是互联网信息组织,在互联网网页中加入了机器识别的 数据,根据这些数据,机器可以实现推断和精确搜索,从而把全球互联网 数据组成一个大的知识库。但这只是对未来结构的预想,是一个理论模型。 正是由于s e m a n t i cw e b 理论模型的提出,对发掘异构模式之间语义一 致性的要求也就日益追切。模式匹配作为模式操作的第一步i l 】,起到了非 常重要的作用。 模式匹配概念的提出要追溯到八十年代的模式集成理念,早期的模式 匹配工作是为模式集成服务的。模式集成【2 l 是从给定的一组独立开发的模 式中构造一个全局视图的过程。由于模式是单独开发的,因此不同的模式 使用不同的结构和术语。当要集成的模式来自不同领域时,各模式所使用 的结构和术语显然是不同的;而当要集成的模式来自相同领域时,由于模 式是由不同人员开发的,各模式使用的结构和术语也不尽相同。因此,模 式集成的第一步就是确认这些模式间的关系,这就需要模式匹配操作。当 这些关系被确认后,匹配的元素就可以统一的出现在集成模式中。 进入九十年代,随着模式集成问题的发展变化,模式匹配开始应用于 将数据源集成到数据仓库的过程中。数据仓库1 3 】是支持决策的数据库,是 从一组数据源中提取出来的。这个提取过程需要将数据从数据源的数据格 式转换到数据仓库的数据格式。在设计转换方法时,匹配操作是十分必要 的。给定一个数据源,创建一种合理的转换方法首先要找到同时出现在这 个数据源和数据仓库中的那些元素。这是一个模式匹配过程。创建了最初 的映射后,数据仓库设计者需要检查每一个元素的详细语义,并创建转换 燕山大学工学硕士学位论文 方法使这些语义和数据仓库中的目标语义一致,最终完成数据源到数据仓 库的集成工作。 在最近的二十年,电子商务【4 】的出现进一步推动了模式匹配的研究。 模式匹配进一步应用到电子商务的信息转换过程中。在电子商务过程中, 交易双方要频繁交换描述商务交易的信息。任何一个交易方都使用自己的 信息格式,这些信息格式通常是不同的。交易双方使用的信息模式也不尽 相同,不同的信息模式可能使用不同的名称,不同的数据类型,允许值的 范围也不同。信息转换问题实际上是不同消息模式转换的问题,而不同消 息模式转换问题实际上是一个模式匹配问题。目前主要是人为的指定不同 信息格式闻的相关性,而通过模式匹配操作在两个不同的信息模式间生成 一个直观的映射,就可以很容易的找到信息格式间的相关性,很大程度上 减少了人工干预,提高了电子商务交易过程中信息交换的效率。 但是,随着w e b 数据源的快速增加与电子商务逐渐一体化,系统处理 数据库的模式日益复杂,数据规模也不断扩大。需要完成更多的匹配。而 由于诸多原因,模式匹配又是困难的( 例如:对于同一概念下的模式同样也 可能有结构上的差异和命名的差异,它们可能会表示成不同数据模型,也 可能使用相同单词来表示不同的意义) 。因此,作为各种应用的关键,模式 匹配应该作为一个独立的组成部分而建立,并且尽量使之通用化、自动化。 1 2 研究现状 目前,模式匹配工作大部分仍以人工( 领域专家或数据库管理员) 定义 方式为主,费时、费力、容易出错【5 】。并且随着数据源数量的增多和规模 的不断增大,模式匹配已经成为数据集成系统、数据共享系统、对等管理 系统【6 】等领域的主要瓶颈。因此需要找出一种通用的、自动化程度高的、 可以应用于不同数据模型和应用领域的综合的模式匹配方法。 近些年来,模式匹配作为数据管理应用中的基础性问题受到了全球的 普遍关注。 在我国,目前对于模式匹配的研究还处于起步阶段。2 0 0 5 年国防科技 2 第1 章绪论 大学李由等人提出了一种基于数据实例分析特征的模式匹配方法【7 湛j 。它通 过分析模式元素所包含数据的分布特征。利用神经网络的模式识别功能找 出具有相似数据分布规律的元素集合,并进一步计算模式元素之间的相似 度,最后将推荐的候选匹配返回给用户。 在国外,目前已开发出很多半自动的发掘模式匹配的系统和方法【9 叫引, 例如:a u t o p l e x 、a u t o m a t c h 、c o m a 、c o m a + + 、c u p i d 、d e l t a 、d i k e 、 e j ) 【、g l u e 、l s d 、p s m 、a r t e m i s 、s e m i n t 、s k a t 、s f 、t r a n s o m 、 基于全集和基于副本的模式匹配方法,等等。其中,s e m i n t 是一种混合的 匹配方法,它主要应用神经网络技术去确定匹配候选,在两个模式的单属 性间建立一个映射:c o m a 系统使用的是一种合成的匹配方法,它提供一 个承载了不同匹配器的外部知识库,并且支持各种结合匹配结果的方法; c u p i d 是一种典型的混合匹配方法,它把一个名字匹配器和结构化的匹配 算法相结合,从而导出元素的相似度;s f 方法是依据数据库模式中的列名 和数据类型进行定点计算得到匹配结果:基于副本的匹配方法是通过发现 被匹配模式间的共享数据,来确定属性间的映射关系;p s m 方法应用多个 可利用的平行模式( 平行模式可由比较两个单个的模式并删除共同的属性 得到) 发掘属性间匹配。然而,目前大多数的模式匹配方法都是由于特殊的 应用需求而开发出来的,其中仅有很少的几个,例如:c o m a 、c u p i d 和 s f 是以一种通用化的方式来解决模式匹配问题,这种通用化的方式能够适 用于不同的应用需求和模式语言。 在已有的模式匹配方法中,大都着重发掘模式元素之间的1 :1 匹配, 例如:一个1 :1 一致性会详细说明源模式中的元素l o c a t i o n 与目标模式中 的元素a r e a 相匹配,或是a g e n t n a r u c 与n a m e 相匹配。然而,i :1 匹配是 很普通的,在现实世界模式之间的关系还包括很多的复杂匹配。一个复杂 匹配指明了一个模式与另一个模式中相一致的属性的组合 1 9 - 2 4 。例如:它 可以具体指明l i s t - p r i c e = p r i c e * d i s c o u n t - r a t e 或a d d r e s s = e o n c a t ( c i t y , s t a t e ) 。实 际上,我们所考虑的异构模式中,复杂匹配占全部匹配一半左右。因此, 半自动发掘复杂匹配技术的发展对于任何实际映射来说都是非常重要的。 文献 2 5 2 7 1 中提出的i m a p 和c m 模式匹配系统都能很好的解决了此 型堕笪兰塑生兰! 竺坠 类问题,这两个系统不仅能够半自动的发掘模式间的1 :l 匹配,而且能够 较准确的发掘出复杂匹配。但是,这两个系统在定程度上还存在着不足。 1 3 研究内容 在对现有的复杂模式匹配方法进行分析的基础上,针对现有方法的不 足进行了补充,主要分为以下三个方面。 ( 1 ) 聚类处理由于l :1 的候选匹配是有限的,而所有可能的复杂匹配 是无限多的。本文提出通过聚类处理,过滤掉部分不合理的候选匹配,缩 小候选匹配空问,提高模式匹配系统的效率和精确度。 ( 2 ) 补充匹配针对现有的复杂匹配发掘方法无法找到共享确定的、相 同的静态特征的列间的匹配关系,增加补充匹配模块,使改进后的系统在 发现1 :l 和复杂匹配的同时,还可以进一步发现不透明列间的匹配关系, 提高匹配系统的查全率和查准率。 ( 3 ) 应用全集现有的复杂模式匹配系统只可应用被匹配模式中存在 的信息发掘匹配,而当被匹配模式中缺乏匹配信息时,就不能很好的找到 模式间的匹配关系。提出一种基于全集的复杂模式匹配方法,它可应用己 知模式和模式间映射的全集为被匹配模式增添信息,提高匹配的查全率和 查准率。 最后,提出了扩展的数据库复杂模式匹配系统c s m 和基于全集的复 杂模式匹配方法,给出了两种方法的整体算法及算法分析,并通过在三个 现实世界领域中的应用对算法进行了验证,对相同领域及数据下的现有复 杂模式匹配方法产生的匹配结果和匹配的效率进行了比较和分析。 1 4 研究意义 模式匹配已成为许多应用领域的核心问题。例如;面向w e b 的数据集 成、电子商务、模式集成、应用演变、数据仓库、w e b 站点的创建和管理 以及基于组建的开发等等,因此模式匹配具有重要的研究意义。为了更好 4 第l 章绪论 地分析和说明本课题的研究意义,下面来考虑这样两个实际的例子。 实例l :公司吞并问题。公司的吞并问题是一个经典的模式匹配问题。 为了实现两个公司的合并,必须把两个公司的数据库结合起来,所以必须 要考虑的问题就是如何确定其中一个公司表中的属性是否和另一个公司表 中的属性相匹配,是否能够形成映射关系,然后才能够根据匹配和映射实 现数据库的合并。 实例2 :数据集成问题。文献 2 8 1 中引用了美国通用电话与电子设备公 司( g t e ) 的数据库集成项目,该公司需要集成的4 0 多个数据库中包含大约 2 70 0 0 个元素( 即关系表中的属性) ,该项目的规划者估计,假如没有数据 库开发人员的参与,定义元素之间的语义映射关系需要1 2 个人年以上。 从上述两个实例不难看出,模式匹配在现实生活中是很常见的问题, 因此,模式匹配对于解决数据库领域内的类似问题是一种非常重要的方法。 本文的研究成果指出了现有的复杂模式匹配方法的不足之处,分别提 出了扩展的数据库模式复杂匹配系统c s m 和基于全集的复杂模式匹配方 法。其中,所提出的扩展的模式匹配系统c s m 克服了现有复杂模式匹配 方法的不足,进一步提高了匹配查全率、查准率及自动化程度;提出的基 于全集的匹配方法针对被匹配模式中缺乏匹配信息的情况,可更好的发掘 匹配。将这两种方法应用到数据集成等领域,可以更全面更快速的完成数 据库的集成工作,因此有着很好的应用前景。同时,对于复杂模式匹配方 法的研究还处于起步阶段,两种数据库复杂模式匹配方法的提出必将为后 续复杂模式匹配的研究工作奠定坚实的基础。 1 5 本文组织结构 本文总体上分为5 章,从第2 章开始具体布局如下。 第2 章作为后续内容的铺垫,主要介绍了模式匹配的相关基础理论。 对模式匹配的基础性概念进行了概括性的描述,并主要介绍了模式匹配的 技术分类及几种典型的模式匹配方法。 第3 章重点阐述模式匹配基本框架,对基本框架的各个组成部分进行 5 燕山大学工学硕士学位论文 了详细的描述,并通过分析,指出基本框架存在的问题。 第4 章研究了扩展的复杂模式匹配系统。针对模式匹配基本框架存在 的不足,本章提出了可弥补现有匹配系统候选匹配搜索空间过大、无法发 掘不透明列间匹配关系等缺陷的扩展的复杂模式匹配系统c s m ,应用实例 对该系统的匹配过程进行了具体的分析,并通过实验数据说明了该原型系 统的可行性。 第5 章研究了基于全集的复杂模式匹配方法。针对被匹配模式中缺乏 匹配信息的问题,应用已知模式和模式间映射的全集为被匹配模式增添信 息,从而更好的发掘1 :l 和复杂匹配,并通过实验验证了该方法的有效性。 最后,对全文进行总结,并提出下一步的设想。 6 第2 章基础理论 第2 章基础理论 2 1模式匹配的定义 模式匹配1 2 9 是在作为输入的模式中有对应语义关系的元素间产生一 个映射。由于不同的背景环境而造成的数据源( 关系数据库、面向对象数据 库、x m l ,h t m l 等) 异构问题已经成为信息集成的主要障碍,实现异构 数据源无缝集成的首要问题是定义异构数据源模式元素之间的数据一致性 关系,即异构模式间的模式匹配。 模式匹配的最终目标就是寻找两个或多个模式元素之间的语义上的对 应关系。 关于模式匹配的定义从不同的角度有着不同的描述【2 9 ,3 们,下面从四个 角度分别对模式匹配的定义进行描述。 定义2 1 :解释和非解释的匹配。令m i = m a t c h ( r ( r l ,r 2 ,r n ) f m ( s 。) ) , 其中m i 是一个匹配结果,m a t c h 是一个模式匹配算法,r 是大小为1 1 的一 个元模式,s 是一个大小为m 的目标模式,是任意一个一对一的函数, 应用于目标模式中i 列的值。我们称给定的匹配算法m a t c h 是一个非解释 的匹配,当且仅当在不考虑函数f ;时两个匹配的结果m 】和m 2 是相同的。 相反,如果两个结果是不同的,就称为解释的匹配。 定义2 2 :元素和结构匹配。结构匹配算法利用表中列之间的关系, 而元素匹配算法仅考虑单一列的特性。 定义2 3 :1 :1 的模式匹配。s 和t 是给定的两个模式,其中, s = s l ,s 2 ,s 。 ,t = t l ,t 2 ,t 。) ,对于模式s 中的任一元素s i ,利用所有 有用信息,寻找模式t 中与之语义相似度最高的元素t 。 定义2 4 :复杂匹配。给定s 和t 两个模式,o = o l ,0 2 ,o k ) 是一组 在一定的规则集r 的约束下可应用到模式t 上的操作集合,对模式s 中的 每一个元素s ,寻找出与之相似度最高的元素t ,t 可以是模式t 中的一个 7 燕山大学工学硕士学位论文 元素,也可以是由t 中的元素在规则r 约束下构造的一个规则。 定义2 4 中所定义的复杂匹配包括l :n 匹配、n :l 匹配和l l ;m 匹配,其 中n 和m 均大于l 。 2 2 模式匹配技术的分类 根据不同的应用需求,模式匹配有多种分类标准,图2 1 描述了模式 匹配的整体分类【3 l 】。 一般的模式匹配技术 单一的模式匹配技术合成的模式匹配技术 愕篓怜篡ii = f f = l 1 垂蒌蓁li 兰兰圣li 垂蒌蓁ll 主茎三:竺ii 主霎三耋竺i l 誉l i 誉l l 黧| i 器i l 誉l 进一步的匹配标准: 爪爪爪爪瓜 匹配基数 辅助信息 图2 - 1 模式匹配技术分类 f i g 2 - 1c l a s s i f i c a t i o no f s c h e m am a t c h i n gt e c h n o l o g y 8 第2 苹基础理论 从图2 1 中可看出,模式匹配技术分为单一的匹配技术和合成的匹配 技术,对于单一的模式匹配技术,我们考虑如下分类标准。 ( 1 ) 基于模式的匹配技术基于模式的匹配技术仅考虑模式信息,而不 考虑实例数据。可获得的模式信息包括模式元素的一些属性,例如:元素 名、描述、元素实例的数据类型、关系类型、约束和模式结构。通常情况 下,基于模式的匹配技术可以发掘出多个候选匹配,每一个候选匹配都有 一个在 0 ,1 】范围内的数字化的匹配相似度值,通过比较这些数字化的相似 度值可以得出最优的候选匹配。 ( 2 ) 基于实例的匹配技术基于实例的匹配技术考虑的是实例级的数 据,通过这些实例级数据我们可以认识到模式元素所表示的内容和意义。 在可用的模式信息非常有限的情况下( 尤其是对于半结构化数据) ,它们是 非常有意义的。特别是在没有给定任何模式信息的非常情况下,可以通过 实例数据手工的或自动的构造出模式。而且,在应用基于模式的匹配技术 发掘出来的候选匹配具有相同的相似度的情况下,应用基于实例的匹配技 术可以选择出正确的候选匹配。 ( 3 ) 基于元素的匹配技术基于元素的匹配技术是对单个模式元素进 行匹配。对于第一个输入模式的每个元素,基于元素的匹配在第二个输入 模式中确定匹配元素。在最简单的情况下,仅考虑粒度的最底层元素,即: 原子层。例如:x m l 模式中的属性或关系模式中的列。但其也不只限于原 子层,也可应用于高层( 非原子层) 元素。高层粒度包括文件记录、实体、 类、关系表和x m l 元素。基于元素的匹配可以通过与关系连接处理相似 的算法实现。 ( 4 ) 基于结构的匹配技术基于结构的匹配技术能够发掘在结构中共 同出现元素的匹配组合。在理想的情况下,两个模式中所有结构的组合都 可以进行匹配。在通常情况下,两个模式中所有结构的组合中可能仅有部 分能够匹配。对于更加复杂的情况,基于结构匹配技术的有效性可通过保 存在知识库中的已知的等价模式来提高。 ( 5 ) 基于语言学的匹配技术基于语言学的匹配技术是应用名字和文 本( 如单词或句子) 来挖掘语义上相似的模式元素。主要技术有基于名字的 9 燕山大学工学硕士学位论文 匹配和描述匹配。基于名字的匹配是通过等价或相似的名字来匹配模式元 素的,而描述匹配是通过对模式在语言上的描述来确定模式元素间的相似 度来实现匹配的。 ( 6 ) 基于约束的匹配技术对于定义数据类型、数据值的取值范围、唯 一性、可选性、关系类型等通常都会有一些模式约束。如果两个输入模式 中都包含有这样的约束信息,那么匹配器就可以应用这个约束信息来确定 模式元素的相似度。基于约束的匹配技术有助于限制候选匹配的数量,并 且可以和其它类型的匹配器结合使用。 ( 7 ) 基于匹配基数的匹配技术匹配基数是指实体集中的一个实体通 过一个联系集能够与另一个实体集相关联的实体数目。根据匹配基数可以 将模式匹配分为:l :l 匹配、1 1 1 匹配、n :1 匹配和n , m 匹配四种。这四种 匹配的定义见本章2 1 节。 ( 8 ) 基于辅助信息的匹配技术大多的匹配器不仅依赖于输入模式s j 和s 2 ,还依赖于辅助信息,比如数据字典、已知的匹配结果和使用者的建 议等。 以上介绍了多种匹配技术。对于某一匹配任务,每一种技术都应用不 同的信息并且有不同的应用领域。但是,应用一种技术的匹配器不像结合 了多种技术的匹配器那样能够高效的发掘出更加准确的匹配。正是由于单 一匹配技术( 无论是基于模式的还是基于实例的) 在进行模式匹配时具有此 种局限性,因此,结合的匹配技术应运而生了。结合不同的匹配技术有两 种方式:一种是混合的匹配器( h y b r i dm a t c h e r ) ,另一种是合成的匹配器 ( c o m p o s i t em a t c h e r ) 。 混合的匹配器是基于多个标准和信息源,综合了多种匹配技术来确定 候选匹配。和单独执行多个模式匹配技术所得到的匹配结果和完成匹配的 效率相比,这种混合的匹配器提供的匹配结果更为准确,完成匹配的效率 也更高。 合成的匹配器是把多个单一匹配技术独立运行时产生的结果进行合 并,这些单独执行的模式匹配技术也可以包括混合匹配器。在选择匹配技 术、确定各种匹配技术使用的次序以及联结多个匹配结果的时候可以由用 l o 第2 章基础理论 户手动完成,也可以由合成后的模式匹配技术自动完成。自动的完成方式 减少了用户交互的次数,但这种合成的模式匹配技术很难适应不同领域的 应用:而手动的完成方式允许用户选择完成匹配的技术,各种匹配技术执 行的次序以及最终匹配结果的结合方式,这种方式较容易实现并为用户提 供了足够的控制权限,但降低了匹配过程中的自动化程度。和混合的匹配 器相比较,合成的匹配器结合匹配技术的方式更为灵活。 2 3 模式匹配技术应用举例 下面我们就介绍几种已经开发出来的模式匹配技术,从它们的实现方 法、优缺点等来对这些技术进行概括性的介绍。 2 3 1s e m i n t 2 0 0 0 年n o r t h w e s t e mu n i v e r s i t y 开发的s e m i n t i ”j 是一个应用混合匹配 技术的模式匹配系统,它主要应用神经网络技术去确定匹配候选,并在两 个模式的单属性间建立一个映射,即它的匹配基数是1 :l 。它应用了高达 1 5 个基于约束和5 个基于内容的匹配标准。基于模式的约束从关系数据库 管理系统的目录中应用可供利用的信息。同时,实例数据还通过提供数据 值的分配、数据的平均个数来增强此类信息。对于每一个标准,系统应用 一个函数把每个可能的候选匹配相似度映射n 0 ,l 】区间上的。应用这些函 数,对n 个匹配标准,s e m i n t 为每一个由在 0 ,1 】区间上的值所组成的属性 确定一个匹配签名( 或全部或是支持标准的一个已选择的子集1 。由于签名 对应于n 维空间的一个点,那么签名间的欧几里德距离就可作为相似度的 评价标准来使用,从而确定一系列的匹配候选。由于系统可以同时选择多 个匹配标准并对确定的候选匹配进行估价,因此,s e m i n t 是一个应用强大 的、灵活的混合匹配技术的模式匹配系统。 但是,s e m i n t 不支持基于名字的匹配或图形匹配,它难于确定一个有 效的匹配n o ,1 】区间。而且s e m i n t 方法需要用户手工操作,如选择最优的 匹配标准,从属性聚类中选择匹配属性,在这一方面。其自动化程度太低。 燕山大学工学硕士学位论文 s e m i n t 只能发掘1 :l 的匹配,无法找到复杂匹配。 2 3 2 c u p i d 2 0 0 1 年v l d b ( v e r yl a r g ed a t ab a s e s ) 会议上提出的c u p i d 3 3 1 是一种通 用化的混合匹配方法,它把一个名字匹配器与一个结构化匹配算法相结合, 根据这个结构化算法可以推导出元素的相似度,而元素的相似度是根据元 素组件( 主要是元素名字和元素的数据类型) 的相似性得出的。 在c u p i d 系统中,为了解决元素的共享问题,将模式图转换成树的形 式,在树中通过增加附加的节点来解决共享节点和它的父亲节点之间的多 重关系。但是,c u p i d 方法也只是对模式匹配问题做了更进一步的工作, 并没有完全解决这个问题,仍然需要加入其它的技术( 例如:应用于实例的 机器学习,通用化语言技术,可重用已知匹配的匹配模型等) 来使c u p i d 更 加全面。 2 3 3c o m a 2 0 0 2 年v l d b 会议上提出的c o m a 3 4 】是一种合成的模式匹配方法, 它提供一个承载了多个不同匹配器的外部知识库,并且支持多种结合匹配 结果的方法。目前,匹配器利用的是模式信息,如元素和结构属性( 也就是 说应用的是基于模式的匹配技术) 。另外,还提供了一个特殊的匹配器来对 以上匹配器产生的结果进行筛选过滤。其中的结合策略应用于匹配处理过 程的各个不同组成部分,例如:对各个匹配器产生结果的聚合和对候选匹 配的选择。它把输入模式转换成具有根节点的有向无环图,在图上应用所 有的匹配算法对图进行操作。每一个模式元素都是通过从模式图的根节点 到相关节点的完全路径唯一标识的。 c o m a 进行模式匹配的过程如图2 2 所示。输入模式s 1 、s 2 后,在匹 配过程中的一个交互过程或多次交互过程中,候选匹配的确定是自动化和 交互式完成的。每一次的匹配迭代都由三个步骤组成:可选择的用户反馈 阶段、不同匹配器的执行阶段和匹配结果的合并阶段。在交互模型中,每 一次迭代时,用户都可以与c o m a 相交互,指定匹配策略( 匹配器的选择、 第2 章基础理论 合并匹配结果的策略选择) ,定义正确或错误匹配的关系,接受或拒绝以前 迭代中建议的候选匹配。交互式的技术有利于对特殊模式测试和比较不同 的匹配策略,并有利于不断的精练和提高匹配结果。在自动化的处理过程 中,匹配过程仅进行一次匹配迭代,应用一个默认的策略或通过输入参数 指定的策略,这种模型适用于已知自身最适合的匹配策略或已完成自身用 户交互接口的应用领域。但是,c o m a 只是解决了1 :l 的匹配,而在实际 应用中1 :l 的匹配只是所有匹配当中的一部分,因此需要应用c o m a 匹配 思想来开发新算法,从而提高匹配的精确度,并进一步实现对复杂匹配的 挖掘。 匹配交互 2 3 4s f ( 匹配器库) 图2 2c o m a 模式匹配过程 f i g 2 - 2m a t c h i n gp r o c e s si nc o m a 2 0 0 2 年i c d e ( i n t e m a t i o n a lc o n f e r e n c eo nd a t ae n g i n e e r i n g ) 会议上提出 的s f 1 1 】是一种基于模式结构相似度的匹配方法。它的主要思想是依据数据 库模式中的列属性和数据类型进行定点计算得到匹配结果。首先将模式转 换成有向标记图,通过定点计算对图中的这些节点进行多步迭代后,返回 一个图中节点和另一个图中节点的稳定相似度。再对这个绝对的相似度产 生出来的相对相似度运用选择策略建议出最优的1 :1 匹配,最后人为的确 定这些匹配。 但是s f 在某些情况下进行匹配操作时会出现一些问题,不能很好的 得出匹配结果。当列名不同,数据类型都相同时,会产生很多对不确定的 候选匹配,该方法不能自动的选择,只能人为干预;当列名不同,数据类 燕山大学工学硕士学位论文 型也不同时,不会得到逻辑上应该匹配的候选匹配。这样不仅降低了匹配 的精确度,而且还降低了匹配方法的自动化程度,并且s f 只能发掘1 :1 的匹配。 2 3 5i 【a p 2 0 0 4 年s i g m o d ( s p e c i a li n t e r e s tg r o u p o l lm a n a g e m e n to fd a t a ) 会议上 提出的i m a p t 2 5 1 是一种基于模式信息和实例信息的混合的匹配方法。它由 三个主要的单元组成:匹配产生器,相似度估价器和匹配选择器。 匹配产生器由一个检索程序集合组成,每个检索程序都是根据特殊的 组合操作符和属性类的知识,对搜索空间的一个特殊部分进行开发。首先, 对于输入的两个模式s 和t ,匹配产生器为t 中的每一个属性t 产生一个 候选匹配的集合,其中包括1 :l 匹配和复杂匹配;然后,相似度估价器对 每一个候选匹配赋予一个评分值,这个评分值显示了候选匹配对目标属性 t 的相似度。因此这个单元的输出是一个矩阵,其中存储了 对的相似度评分值:最后,匹配选择器对相似度矩阵进行检验, 然后输出t 属性的最优匹配。在整个匹配过程中,这三个单元还应用了域 知识和数据来提高匹配的精确度,并且与一个解释单元进行交互来为匹配 作出解释。 i m a p 系统可以很好的发掘1 :1 和复杂匹配,但也有其自身的缺点。由 于每个检索程序都要对所有的候选匹配进行检索,而且所有可能的候选匹 配是无限多的( 其中包括了许多不合理的匹配) ,这就导致需要检索的候选 匹配规模太大,影响系统效率。另外,由于i m a p 是一种解释的匹配,需 要模式中信息的解释说明,无法发掘不透明列( 共享确定的、相同静态特征 的列) 间的匹配关系,当被匹配模式中包括不透明列时,不能得到全面的匹 配关系。 2 3 6 基于副本的模式匹配方法 2 0 0 5 年i c d e 会议上提出的基于副本的模式匹配方法【2 1 1 主要利用被匹 配模式的数据集中存在的重叠数据来指明模式间的匹配关系,是一种基于 1 4 第2 章基础理论 实例的模式匹配技术。它的基本思想是:将被匹配模式中的每个元组看作 一个串,应用串比较方法比较两个元组并确定元组问的相似度,选择出k 个具有最高相似度的元组对,那么在这些元组对中一定或很可能存在共享 的数据。然后计算k 个相似元组对中每个字段值间的相似度,根据字段相 似度可推导出模式元素的相似度。 基于副本的模式匹配方法应用模式实例信息,可很好的解决具有不透 明列名的模式元素之间的匹配问题。但其只应用了单一的模式信息,可通 过加入其它的技术( 例如:基于名字的估价器和贝叶斯估价器等) ,使其可 应用更丰富的信息,提高匹配的精确度。该方法只能发掘1 :1 的匹配。 2 3 7s m d d 2 0 0 5 年n d b c ( n a t i o n a ld a t ab a s ec o n f e r e n c e ) 会议上提出的s m d d l 7 , 8 j ( s c h e m am a p p i n gm e t h o db a s e do nd a t ad i s t r i b u t i o n ) 是一种基于数据实例 分析特征的模式匹配方法。它通过分析模式元素所包含数据的分布特征, 利用神经网络的模式识别功能找出具有相似数据分布规律的元素集合,并 进一步计算模式元素之间的相似度,最后将推荐的候选匹配返回给用户。 它与s e m i n t 的主要区别在于:首先,s m d d 所考虑的是数据内容,即基 于实例的匹配技术;其次,s m d d 实现了匹配的自动化。s m d d 方法的模 式匹配过程如图2 3 所示。 图2 3s m d d 模式匹配过程 f i g 2 - 3m a t c h i n gp r o c e s si ns m d d ( 1 ) 提取数据分布特征向量s m d d 利用特征提取器提取出目标模式 中模式元素所包含的部分数据实例,分析其分布规律,生成数据分布特征 燕山大学工学硕士学位论文 向量。 ( 2 ) 分布特征向量聚类s m d d 利用聚类算法将输入的数据分布特征 向量动态分为m 类,并计算聚类中心。分类数m 由凝聚层次聚类算法根 据相似度域值动态确定,不要求用户预先设定。 ( 3 ) 训练神经网络s m d d 生成三层前馈神经网络,将聚类中心作为训 练样本,利用b p 学习算法反复迭代计算,调整各突触权重以适应输入模 式的激励,最终识别类c ;。 ( 4 ) 计算元素相似度利用特征提取器提取源模式中的模式元素的数 据分布特征向量,将其输入经过训练的神经网络,计算输入向量与目标模 式元素中各分类的相似度。 ( 5 ) 返回匹配选择相似度较高的匹配对作为候选匹配返回给用户。 s m d d 通过挖掘数据内容信息,根据元素的数据分布特征计算模式元 素之间的相似度。但s m d d 的匹配质量很大程度上依赖于数据源中数据的 规律性分布。在数据分布较为规律的情况下,s m d d 的匹配质量较好,反 之,计算效果不理想,且只能发掘l :1 的匹配。 2 4 问题定义 在这里,我们是对关系模式下的模式匹配进行讨论的,但是,所提供 的思想可以贯彻到其它的数据表示当中( 例如:x m l d t d 和o n t o l o g y ) 。作 为一个实例,我们来考虑两个关系模式s 和t ,如图2 4 所示。两个数据 库存储的都是房屋列表清单,并且由两个不同的财团进行管理。数据库模 式t 有一个表l i s t i n g s ,数据库模式s 把它的数据存储在两个表h o u s e s 和a g e n t s 中。 假设两个财团决定要进行合并。为了减少开销,他们通过把s 中的所 有房屋列表传送到t 中,从而删去数据库s 。在不知道关系数据库模式之 间的语义映射的情况下,这种传送是不可能的。下面,我们通过使用s q l 表示法,描述t 中单一属性的一些映射。实际上,要说明语义映射,可以 使用的方法有很多种,例如:s q l 、x q u e r y 、g a v 、l a v 、g l a v
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年东营市“英才进广饶”(医疗卫生类)事业单位引进人才招聘(16人)考前自测高频考点模拟试题及答案详解参考
- 2025北京市海淀区锦秋学校招聘模拟试卷附答案详解
- 2025广西来宾市政协办公室招聘所属事业单位后勤服务控制数人员1人考前自测高频考点模拟试题及参考答案详解一套
- 2025杭州市临安区城市发展投资集团下属子公司招聘3人(第二批)考前自测高频考点模拟试题带答案详解
- 2025河北唐山幼儿师范高等专科学校选聘工作人员35人模拟试卷及一套答案详解
- 铁氧体材料烧成工年度考核试卷及答案
- 2025航天科工天隼实验室招聘4人考前自测高频考点模拟试题及一套完整答案详解
- 2025广西崇左市龙州县供销资产经营管理有限公司招聘基层供销社人员4人模拟试卷含答案详解
- Pevonedistat-Standard-生命科学试剂-MCE
- 2025年供用水合同解除通知协议(GF-1999-0501)
- 发育生物学实验教案
- 低压电工试题库-含答案
- 【幼儿自主游戏中科学探究活动实践研究文献综述1900字】
- 肝脓肿的诊断和治疗
- YY 9706.102-2021医用电气设备第1-2部分:基本安全和基本性能的通用要求并列标准:电磁兼容要求和试验
- GB 7691-2003涂装作业安全规程安全管理通则
- 危险化学品双重预防机制培训课件
- 跌倒坠床原因分析预防措施
- 湖南人民出版社乘槎笔记(斌椿)
- Q∕SY 1452.1-2012 石油装备产品包装规范 第1部分:钻机和修井机
- 妇产科产前诊断技术服务临床医师考核题(附答案)
评论
0/150
提交评论