（计算机软件与理论专业论文）全局模式和局部模式之间的模式匹配技术研究.pdf

河海大学硕士学位论文 摘要 摘要 随着网络技术的发展，未来的信息处理环境将是由大量的、异构的、自治的 和分布的网络环境组成。由于数据的多样性带来信息存取的方法和手段的多样 性，这给信息共享带来了诸多困难。因此必须研究一种对大量的、异构的和自治 的数据源的统一的、集成的存取手段和方式，多数据源集成就是研究这一问题。 而模式匹配是数据集成领域中一个基本的问题，它主要考虑全局模式和局部模式 之间的匹配。在模式匹配的过程中涉及到数据模式复杂的语义和结构冲突，现在 虽然已经做了很多模式匹配方法的研究，但是都没有很好地解决这些冲突。本文 提出一种解决模式匹配问题中语义和结构冲突的方法，并将它们集成至0 一个统一 的模式。总结起来，主要工作如下： ( 1 ) 分析了模式匹配过程和匹配策略，总结了各种模式匹配方法。 ( 2 ) 设计了一个基于语义的模式匹配方法，研究了模式匹配过程中模式之间 的语义冲突问题，对异构模式间可能存在的语义冲突问题进行了分类，阐述了解 决这些语义冲突的策略和实现方法。 ( 3 ) 研究了模式匹配中结构冲突问题，对异构模式问可能存在的结构冲突问 题进行了分类，阐述了解决这些结构冲突的策略和实现方法，最后实现结构冲突 相互之间的转化，将它们集成到一个统一的结构。 关键词：数据集成、模式匹配、语义冲突、结构冲突 河海大学顾十学位论文 摘要 a b s t r a c t w i t ht h e d e v e l o p m e n to fn e t w o r kt e c h n o l o g y , t h ee n v i r o n m e n to fi n f o r m a t i o n p r o c e s s i n gw i l lc o n s i s to fv a s tn e t w o r k so fl a r g es c a l e ，h e t e r o g e n e o u s ，a u t o n o m o u s a n dd i s t r i b u t e dc o m p u t i n gr e s o u r c ei nt h ef u t u r e v a r i o u sd a t ar e s u l ti nv a r i o u s m e t h o d sf o ra c c e s s i n gi t ，w h i c hm a k e si td i f f i c u l tf o ri n f o r m a t i o ns h a r i n g s oi ti s n e c e s s a r y t os t u d yau n i t ya c c e s s i n gm e t h o da n df o r mf o rv a s tn e t w o r k so fl a r g es c a l e ， h e t e r o g e n e o u sa n dd i s t r i b u t e dc o m p u t i n g r e s o u r c ew h i c hi sd a t ai n t e g r a t i o n sw o r k s c h e m a m a t c h i n g i sab a s i cp r o b l e mi nt h ef i e l do fd a t ai n t e g r a t i o n ，t h em a i n a s p e c to f i tc o n c e r n sam a t c hb e t w e e n g l o b a l s c h e m aa n dl o c a ls c h e m a i tm u s tf a c e c o m p l i c a t e ds e m a n t i ca n ds t r u c t u r e c o n f l i c t si nt h ep r o c e s so fs c h e m am a t c h i n g t h o u - g hm a n y r e s e a r c h e sh a v eb e e nd o n eo nt h em e t h o d so fs c h e m am a t c h i n g ，t h e y c a n ts o l v et h e s ep r o b l e m sv e r yw e l l i nt h i sp a p e rw e p r o p o s e s o l u t i o n st os o l v et h e s e c o n f l i c t sa n di n t e g r a t et h es c h e m a si n t o au n i f i e do n e i n s u m m a r y , t h em a i n c o n t r i b u t i o no ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) a n a l y z et h ep r o c e s so fs c h e m am a t c h i n ga n dm a t c hs t r a t e g y , s u m m a r i z et h e m e t h o d so fs c h e m am a t c h i n g ( 2 ) d e s i g n as c h e m am a t c h i n gm e t h o db a s e do n s e m a n t i c ，i n v e s t i g a t et h ep r o b l e m o fs e m a n t i cc o n f l i c ti ns c h e m am a t c h i n g w ec l a s s i f yt h ep o s s i b l es e m a n t i cc o n f l i c t s b e t w e e n h e t e r o g e n e o u ss c h e m a s a n di n t r o d u c et h es o l u t i o nm e t h o d s r e s p e c t i v e l y 0 ) i n v e s t i g a t et h ep r o b l e m o fs t r u c t u r ec o n f l i c t si ns c h e m am a t c h i n g w ec l a s s i f y t h ep o s s i b l es t r u c t u r ec o n f l i c t sb e t w e e nh e t e r o g e n e o u ss c h e m a sa n di n t r o d u c et h e s o l u t i o nm e t h o d s i nt h ee n d ，w ea c c o m p l i s ht h et r a n s f o r m a t i o nf o rt h e s et y p e so f s t r u c t u r a lc o n f l i c ta n d f i n a l l yi n t e g r a t et h e m i n t oau n i f i e do n e k e y w o r d s ：d a t ai n t e g r a t i o n ，s c h e m am a t c h i n g ，s e m a n t i cc o n f l i c t ，s t r u c t u r e c o n f l i c t 河海大学硕士学位论文 全局模式和局部模式之问的模式匹配技术研究 第一章引言昂一早ji 百 1 1 模式匹配提出的研究背景 计算机网络和数据库系统的迅速发展，企业竞争与兼并的加剧，使得信息资 源的异构性在企业的信息系统中无处不在，越来越多的应用需要访问各种异构数 据源。任何企业应用首先需要解决的，就是如何对企业中的异构数据源进行集成 和一致化处理，形成标准、统一和可靠的数据源，来做为应用系统的基础。而为 了达到异构数据源的共享，必须首先解决数据集成问题。 异构数据集成为异构数据源提供一个完整的数据源模式和一致的访问接口， 使用户不必考虑数据模型的异构性、数据抽取、数据合成等问题，用户只需指定 他们想要的数据，而不必描述怎样得到数据 8 , 1 2 , 3 5 】。这样就减轻了用户寻找相关 数据源、和每个数据源交互然后合并返回结果的负担，也就是消除异构，实现分 布透明。目前，开发异构数据源集成系统通常采用数据仓库法和虚拟法。相比而 言，虚拟法适合数据源数目多，数据更新频繁，而且无法预知用户的查询种类的 情况，是当前异构集成研究的热点。 采用虚拟法的异构数据源集成系统提供给用户个全局模式( 即中介模式) ， 数据仍保存在局部数据源中，通过各数据源的包装器( w r a p p e r ) 将数据虚拟成 全局模式，这里的数据源可以是数据库、遗产系统、w e b 数据源等等。用户的查 询是针对该全局模式的，所以用户不必知道数据源的位置、模式及访问方法。 对于采用虚拟法的异构数据源集成系统，它的主要部分是中介器和针对每个 数据源的包装器。这里中介器的功能是接收针对全局模式生成的查询，根据数据 源描述信息及映射规则将接收的查询分解成每个数据源的子查询，再根据数据源 描述信息优化查询计划，最后将子查询发送到每个数据源的包装器。包装器将这 些子查询翻译成符合每个数据源模型和模式的查询，并把查询结果返回给中介 器。中介器将接收的所有数据源的结果合并成一个结果返回给用户。 虚拟法集成结构中为用户提供数据源的统一访问存在以下困难。首先，用户 的查询基于全局模式，而查询引擎需要与封装器交互，将针对全局模式的查询转 换为基于各数据源局部模式的查询，即确定与查询相关的数据源。因此，为了回 答用户查询，必须建立局部模式和中介模式之间的匹配【3 “。 河海大学硕士学位论文 全局模式和局部模式之间的模式匹配技术研究 图1 1 异构数据源集成系统结构图 这里匹配是一个对模式进行操纵的操作，它将两个模式作为输入，然后返回 这两个模式中相对应元素的一个映射1 4 ”。匹配既可以是两个输入模式之间的匹 配，也指将输入模式匹配到一个全局模式【1 5 】。 数据模型是用来描述数据的一组概念和定义。一般来说，数据的描述包括两 个方面【4 4 j ：( 1 ) 数据的静态特性包括数据的基本结构、数据间的联系和数据的 约束。( 2 ) 数据的动态特性指定义在数据上的操作。而数据模式是用给定数据模 型对具体数据的描述，即对某一类数据的结构、联系和约束的描述。本文中的模 式是指数据源中数据的逻辑组织形式，比如在关系数据库中一个表的定义就是一 个模式，它描述了这个表中的属性名、属性的排列顺序、属性的域、主键和外键 等信息：在面向对象数据库中，模式描述了数据库中定义的类及类所具有的属性、 方法等信息。可以看出模式由一组元素组成，元素可以是表、列、属性等，因此 模式匹配研究问题就是：对于一个模式s l ( l b 如全局模式1 和一个模式s 2 ( 比如 局部模式) ，在这两个模式的相应元素之间找出某些语义上相同或相似的关系， 由此产生s 1 和s 2 的匹配关系 2 1 2 5 】。模式匹配系统的形式化描述【5 l 就是这样的元 组( t s i ) ， m i ) ) ，t 是一个全局模式， s j ) 是n 个源模式即局部模式的集合， m i ) 是n 个局部模式到全局模式集合，因此对于每一个局部模式s i ，都有一个从s i 到t 的一个匹配m i ，1 i n 。 河海火学硕士学位论文 全局模式和局部模式之闯麓模式匹配技术研究 1 2 研究现状及存在的问题 1 2 1 模式匹配研究现状 过去模式匹配一般是通过手工执行的，通过一个图形用户接口来支持。很明 显，手工表明模式匹配是个冗长、费时、容易出错，因而代价也很高的过程。 这对于迅速发展的w e b 数据源来说是一个越来越明显的过程。而且，当系统开 始能够处理更复杂的数据库，模式也更大，更加增加了要匹配的数量。因而需要 一个更快的、劳动强度相对小的匹配方法，这就需要模式匹配的自动支持。 在过去的十几年中做了很多自动模式匹配的工作。这些工作大部分基本上关 注于一个特定应用程序域的上下文然后被应用到一个特定的模式格式【1 8 , 1 9 , 3 7 l 。例 如，m i c r o s o f t 研究的c u p i d 方法【2 】，w a s h i n g t o n 大学研究的g l u e 和l s d 1 0 ，2 7 ，3 3 】 方法，l e i p z i g 大学研究的c o m a 方法p “，s t a n f o r d 大学研究的s i m i l a r t yf l o o d i n g 方法p w 以及i b m a l m a d e n 研究的c l i o 方法m 1 等。 m i c r o s o f t 研究的c u p i d 方法主要应用于x m l 和关系模式上，它是一种基于 元素级匹配和结构级匹配的混合方法。其思想是，如果两个元素的子元素是相似 的，那么这两个元素就趋向于相似；如果两个元素具有相似的祖先，那么它们也 趋向于相似。为了处理同义词、缩略语、首字母缩写，它用到了辅助的信息，如 词典等。为了解决共享元素的问题，它在模式树中加入辅助节点以反映共享节点 和父节点之间的多重关系。 整个算法分成三步，第一步做语言学上的元素级匹配，并通过名称、数据类 型和领域进行分类。这个过程中，复合名词被分解成单个词，按照数据类型，语 义内容归入不同的类别，然后在每个类别内计算模式元素对之间的语言相似性系 数，计算中用到了子串匹配和辅助信息源。第二步，把原来的模式转化为一颗模 式树，做自底向上的结构匹配。两元素之间的相似性取决于它们的语言相似性以 及它们的叶子集的相似性。如果算出的相似系数超过了阀值，那么就增加叶子集 的相似系数。之所以关注叶子集是基于这样的假设，时节点包含了更多的信息。 这一步计算出匹配概念对之间的语言相似系数和结构相似系数的加权平均值。第 三步，用这些加权平均值来选出匹配结果。 s i m i l a r i t yf l o o d i n g ( s f ) 的思想是基于相邻模式元素之间的相似传递性，也 就是说如果两个模式元素的邻近元素是相似的，那么它们就趋向于相似。s f 也 是一种综合使用了名称匹配和结构匹配的混合方法。首先，它将模式信息转化成 有向图，然后通过简单的名称匹配得出各个节点之间的初始化相似系数。这时的 结果是相当粗略的，不能反映节点之间的语义关系。接着，它用s f 方法对初始 系数进行迭代计算，直到得到收敛值，也就是各个节点对之间最终的相似系数。 河海大学硕士学位论文 全局模式和局部模式之间的模式匹酣技术研究 最后，它用一些过滤方法从数值最高的几个候选节点中找出最合适的一个。与其 它模式匹配方法不同的是，它并没有使用词典，没有利用术语之间语言学上的语 法关系。 g l u e 系统用机器学习的方法来完成不同模式之间的匹配任务，其思想是多 策略学习。它代表了一种自动合并不同匹配器( 1 e a r n e r ) 匹配结果的组合方法， 产生的是原子级的1 ：1 的映射关系。除了名称匹配器之外，它还用到了几个在预 处理阶段经过训练的实例级匹配器。在预处理阶段，用户先给出一些映射实例， 然后用这些实例训练l e a r n e r ，发现其中特有的实例模式和匹配规则。用这些模式 和规则去匹配整个模式，得到候选值的列表。 一个全局的匹配器用同样的机器学习方法融合这些由不同l e a r n e r 得出的匹 配候选值列表，得到一个综合的列表。在预处理过程中，它也经过了训练，以决 定每个l e a r n e r 的权值。由于是组合式的匹配方法，加入新的l e a r n e r 也很方便。 虽然此方法是面向实例的，但它也能利用模式信息。此外它还能加以扩展， 利用用户提供的领域约束信息以提供匹配准确性。 c o m a 系统采用的是复合方法，可以灵活的组合不同的匹配算法及其结果。 它所应用的匹配器主要利用模式信息，如元素和结构属性。与其他系统不同的是 它可以重用以前的匹配结果，这可显著的提高匹配效率。在匹配过程的不同阶段 c o m a 应用了不同的组合策略，如匹配结果的聚合一起匹配候选值的选择。在 匹配过程中，它把模式转化成带有根节点的有向无环图，所有算法都基于这个内 部表示结构来工作。算法产生的相似值矩阵保存在基于d b m s 的知识库中。每 个模式元素都以从根节点出发的完整的路径名称来唯一标识。 c o m a 中应用的匹配算法包括两种元素级的混合匹配算法，n a m e 和 t y p e n a m e ，以及三种结构级的混合匹配算法，n a m e p a t h ，c h i l d r e n 和l e a v e s 。 其中，c h i l d r e n 和l e a v e s 在比较元素相似性时都用到了t y p e n a m e 算法。 1 2 2 模式匹配存在的问题 由于数据集成工作在一个多源、异构的环境下，存在着互不相同的数据库模 式。因此，采用这些互不相同的模式描述实体对象时便存在许多不同的方式，这 些数据表达方面的不一致就是冲突。对于开发者来说，希望以一种统一的方式来 描述实体对象，这样就可以提高系统的开放性，易于推广使用；而对于一个数据 集成的用户来说，希望利用现有的数据库资源，方便信息流动，以一种统一的方 式应用系统。因此，数据冲突的解决对模式匹配来说是一个重要的问题。另外， 它也是分布式数据库系统提供分布透明性、一致性的关键。模式匹配存在的冲突 问题包括2 2 】： 4 河海大学硕上学位论文 全局模式和局部模式之间的摸式妲配技术研究 ( 1 ) 命名冲突：由于各用户数据库遵循不同的实体命名习惯，因而存在命名 冲突，命名冲突包括同物异名和同名异物。 ( 2 ) 结构冲突：由于对实体对象的使用方式不同，各用户数据库对同一数据 对象的描述结构可能存在差异。 ( 3 ) 语义冲突：由于参加集成的各局部数据库可能处于一个分布的环境中， 可能使用不同的硬件和软件环境，运行在不同的数据库管理系统之上，因此可能 发生各种各样的语义上的区别。这些语义上的不同可能引起各种矛盾，从简单的 名字语义冲突( 不同的名字代表相同的概念) ，到复杂的结构语义冲突( 不同的 模型表达同样的信息) 。语义冲突会带来模式匹配结果的冗余，干扰数据处理、 发布和交换1 1 , 2 8 , 4 3 】。 以上是常见的三种冲突，也就是说模式匹配面临着数据源在语法( 数据表示 方法) ，结构( 数据结构) 和语义( 数据含义) 等上的异构问题【“。当然在模式 匹配过程中可能还存在着其他类型的冲突，值得注意的是数据库集成系统中可能 存在语义上相互矛盾的冲突。例如，同样一个人，在一个局部数据库中是2 6 岁， 而在另一个局部数据库中是3 4 岁。另外，更新不一致和记录错误也可能导致 些人为的冲突问题，在个数据集成系统中对这些冲突都必须采取措施进行处 理。 当前虽然在自动化模式匹配方面做了大量的研究，但是各种模式匹配方法旨 在将主要目标放在怎样根据模式信息来提高匹配的准确性，也就是说它们并没有 将注意力放在怎样来解决模式匹配过程中的这些语义和结构冲突问题，而这些语 义和结构冲突问题阻碍了自动化模式匹配的进一步研究。同时目前大部分文献对 语义和结构的分析仅限于对模式元素名称、缩写词等简单命名冲突、模式元素类 型等方面进行考虑，而并没有对存在在模式元素里的高层次语义冲突问题进行研 究， 1 3 论文主要工作 本文研究和分祈了数据集成领域中各种模式匹配方法，针对模式匹配过程中 存在的语义和结构冲突进行分类，并提出了相应的解决策略。主要工作归结为以 下几点： ( 1 1 总结了模式之间存在的冲突问题，分析全局模式和局部模式之间的模式 匹配过程和匹配策略，总结各种模式匹配方法。 ( 2 ) 研究了全局模式和局部模式之间的匹配过程中存在的语义冲突问题，对 异构模式间可能存在的语义冲突问题进行了分类，阐述了解决这些语义冲突的策 略和实现方法，同时对语义匹配过程进行了探讨，利用相关的技术来提高模式匹 河海大学硕士学位论文 全局模式和局部摸式之间的模式匹配技术研究 配的自动化水平。 ( 3 ) 分析了全局模式和局部模式的匹配过程中存在的结构冲突，并提出了相 应的解决办法。这里对三种类型的结构冲突迸行了形式化定义，通过转化将拥有 结构冲突模式( 包括属性名和关系名) 根据结构冲突类型转换成一个统一的模式。 1 4 论文组织 在这篇论文里我们研究了在模式匹配过程中语义和结构冲突的解决方法。首 先给出了过去模式匹配解决方法的一个分类，展示了可用的模式匹配技术的广阔 范围。然后我们在第三章研究怎样来解决语义冲突，对语义匹配过程进行了探讨， 接着在第四章研究了模式匹配过程中结构冲突的解决方法。 第二章主要分析了模式之间存在的冲突，设计了一个实现全局模式和局部模 式之间的模式匹配的过程和匹配策略，并且提供了一个自动执行模式匹配的不同 方法的一个分类。 第三章对基于语义的模式匹配过程进行了探讨，研究了全局模式和局部模式 之间模式匹配过程中存在的语义冲突及其相应的解决策略。 第四章研究了全局模式和局部模式匹配过程中结构冲突的形式化定义及其 相应的结构冲突解决方法。 第五章总结论文，提出关于全局模式和局部模式匹配研究的进一步工作。 河海大学硕士学位论文 会局模式和局部模式之间的摸式匹配技术i i j 究 第二章模式匹配技术研究 在集成异构数据源的过程中，模式匹配是关键的步骤，它主要考虑如何根据 数据源模式统一到一个一致的全局模式。这里全局模式定义了系统中的数据内容 和数据的逻辑组织形式，用户的查询语句针对全局模式生成。由于全局模式中的 数据并不真正存在，它是对数据源模式即局部模式进行更高级别的统一抽象，因 此又可以把全局模式称为数据源的虚拟视图，把这种系统中的查询处理方式看作 “利用视图回答查询”。 2 1 模式匹配问题 在数据集成领域中，由于数据源系统多是独立开发，数据源是相当自治的， 所以描述数据的数据模型或存储结构经常会出现不同的情况，这也使得不同数据 源模式的匹配变得困难。以关系数据库为例，我们很难分辨出在两个不同的数据 库中两个模式描述的是相同的数据，即使它们采用的是相同的数据模型。每个数 据源系统有自己的对象视图，集成这些视图就像集成两种人类的知识一样困难。 所以，有许多因素会导致数据模式存在差异【4 0 j ： 数据源的用户不同，他们要看到的视图不同。 数据源开发者可以用不同的数据模型描述数据。例如，一个数据库用关 系模型实现，而另一个用面向对象模型实现。 模型的构成之间存在等价现象，用户可以在一个模式中用属性描述，而 在另一模式中用实体描述同样的信息。 开发者对一些公共的概念也会采用不同的描述，这些描述之问的关系可 能是相同的、等价的、兼容的或不兼容的。 数据源的自治性和数据源模式匹配的复杂性加大了模式匹配的难度。之所以 说数据源模式匹配是复杂的是因为模式匹配是知识集中的任务。我们可以想像在 一些大的系统中，不曾有一个人能理解所有匹配的数据源的模式 9 1 。 上述问题也是模式匹配的焦点问题。它们形式上的性质使得人们想到要用模 式匹配去解决逻辑、语义和知识的描述问题。 对于描述模式匹配中的冲突问题有许多种分类。下面介绍几种有代表性的分 类。 1 、第一种分类例 异类( h e t e r o g e n e i t y ) 冲突：在不同模式中采用不同的数据模型描述问 题，就产生异类冲突。例如：一个源模式即局部模式用面向对象数据库描 河海大学硕士学位论文 全局模式和局部模式之间的模式匹配技术研究 述，而全局模式采用关系数据库描述。 命名( n a m i n g ) 冲突：不同的模式中可能用相同的术语描述不同的概念， 这是所谓的同形异义( h o m o n y m s ) ，或者用两个不同的术语描述相同的概 念，这即同义词( s y n o n y m s ) 。 语义( s e m a n t i c ) 冲突：在不同的模式中，用不同的抽象层( 1 e v e l so f a b s t r a c t i o n ) 去模型化相同的实体。例如：在一个数据库中可能是区分“c a r s ” 和“t r u c k s ”信息的，而在同一集成系统中的另一个模式却可能只简单地模 型化“a u t o m o b i l e s ”，不存储c a r s 和t r u c k s 的区分信息。 结构( s t r u c t u r a l ) 冲突：不同的模式中用不同的方法描述相同的信息。 例如：一个c a l 所有权模式可能用一个表存储c a r 和o w n e r 的信息，而另 一模式可能把同样的信息分成“c a r ”和“o w n e r 两张表存储。 2 、第二种分类 a l 该分类主要是对第一类异类冲突概念的一个细致的改进，但和其它分类仍有 细微的不同。第二种分类把异类冲突看作是语义不一致的一类( 如，语义冲突) 。 但是该分类把命名冲突作为语义不一致的原因，而第一种分类把命名冲突和语义 不一致区分开来。 命名( n a m i n g ) 冲突：同第一种分类中的命名冲突 域( d o m a i n ) 冲突：在不同的模式中用不同的简单值去描述数据。例如： 一个模式中把c a r 的价格描述成整形，而另一模式中可能描述成文本类型 元数据( m e t a d a t a ) 冲突：个概念在一个数据源中的描述是带有模式的， 而在另一数据源中没有模式。例如：一个数据源中将c a r s 和t r u c k s 分开存 储，那么就要维护两个表，c a r s 表和t r u c k s 表。一条记录出现在哪张表， 那么该记录就指定了该交通工具是汽车还是货车。而另一个数据源中用一 张表存储c a r s 和t r u c k s 的信息，但是表中有一列用于指示表中每条记录描 述的是汽车还是货车。 结构( s t r u c t u r a l ) 冲突：同第一种分类中的结构冲突 属性丢失( m i s s i n ga t t r i b u t e s ) ：一个模式描述的信息可能是另一模式描 述信息的超集( s u p e r s e t ) 。例如：两个描述汽车销售的模式，一个模式中 包括汽车最近汽油改变的属性，而另一模式可能没有提供该信息。这个问 题在某种意义上同【3 】中的语义冲突，两者都处理了存储在两个模式中的 相同实体细节层的差异。 硬件，软件不同( d i f f e r e n th a r d w a r e s o f t w a r e ) ：该冲突描述的现象是两个 被集成的信息系统有不同的硬件、操作系统、通信协议等。这些不同在集 成两个系统时会引起问题。这种分类观点是，软硬件不同不是语义不一致 的原因，它是一个比较具体、底层的问题，和信息系统的语义几乎没有关 河海大学硕+ 学位论文 全局模式和局部模式之间的模式匹配技术研究 系。 模式匹配是一项复杂而繁重的任务，而且随着网络的普及，集成系统所能集 成的数据源越来越多，上述冲突情况也会越来越普遍，想解决所有的模式冲突是 不现实的。在本论文里，主要解决关系数据模式之间的语义和结构冲突。 2 2 模式匹配过程 对于一个采用虚拟法的异构数据源集成系统，提供给用户一个全局模式( 即 中介模式) ，数据仍保存在局部数据源中，通过各数据源的包装器( w r a p p e r ) 将 数据虚拟成全局模式。 图2 1 是一个自底向上的模式匹配过程，首先在预集成阶段，把数据源模式 翻译成一个采用公共数据模型的输出模式，这样消除用不同数据模型描述数据源 模式带来的问题。 在比较阶段，对要匹配的数据源集进行分析，寻找不同模式元素间的关系和 冲突。关于冲突类型在上一小节中有分析。这可在两个层面上来做：模式比较和 数据源中实际数据的比较，在产生全局模式的过程中主要需要对模式的比较，得 到语义、结构上的冲突描述信息，这一过程需要集成人员的参与。 在得到模式元素之间语义、结构上的冲突描述信息之后。利用这些冲突信息， 对输出模式进行统一。对实际数据的比较用于生成映射规则，映射规则就是定义 冲突处理的规则。模式统一阶段解决模式比较阶段发现的冲突问题，改变输出模 式，使其适合输出模式的彼此集成。消解冲突过程是解决冲突问题，通过比较阶 段指定冲突类型，针对不同冲突采取不同的解决方法。在匹配模式的过程中主要 消除模式的语义和结构冲突。 在模式合并和重构阶段，将消除冲突的输出模式合并，重写组合成符合要求 的全局模式。为得到理想的全局模式，这一过程可能要重复几遍，而且在整个过 程中需要集成人员的参与，由于冲突的复杂性，目前还没有方法实现匹配过程的 完全自动化。 河海大学硕士学位论文 全局模式和局部模式之问的模式匹配技术研究 模式合并与重构 簇乍除冲突的 模式统一 描述信窟出模式 比较 l 输出模式 预集成 式 局部模式局部模式 图2 1 模式匹配过程 该方法之所以加入输出模式这个中间层。把解决模型异构和模式冲突分开 来，相同模型间的模式差异问题容易统一，方便匹配的同时，提高了匹配的正确 性，为数据集成系统的查询分解、优化及执行提供了快捷、正确的保障。 这里可以看到，在建立全局模式和局部模式之间的模式匹配时将要利用的输 入信息包括【1 7 j ： ( 1 ) 要执行匹配的模式语言类型，例如关系模式、x m l 模式等，不同的模式 语言可以展现可以被模式匹配方法所利用的不同方面。但是，依赖于特定语言的 方面会使算法限制到特定的模式类型上。 ( 2 ) 模式和匹配任务的数量 ( 3 ) 模式信息：如要决定的候选匹配的模式元素的数量，输入模式越大，候 选匹配的搜索空间就越大，匹配性能就越低。 ( 4 ) 使用的辅助信息：例如数据字典和应用到特定领域的约束( 例如，每个 源模式必须匹配至少一个全局模式) 。这些信息的使用会极大的改善匹配结果性 能。 在得到输入信息之后，利用这些信息执行模式匹配方法 2 3 1 ，输出模式的元 素相互之间的一个映射，即匹配。 1 0 南 河海大学硕士学位论文 全局模式年几局部模式之问的模式匹配技术研究 图2 2 显示了采用虚拟法的异构数据集成系统的模式结构图，展示了匹配过 程中模式自底向上的变换过程，这里输出模式可以认为是我们在建立全局模式和 局部模式之间的匹配过程中的一个中间模式。 2 , 3 模式匹配策略 图2 2 模式结构图 模式匹配策略解决如何选取模式进行比较的问题。模式匹配策略主要分为： 二元匹配策略和多元匹配策略两种类型【1 1 4 1 】。二元匹配策略一次只能允许匹配两 个模式。当每次用一个新的局部模式与现有的中间模式进行匹配时，这种匹配策 略称为二元爬梯策略。而在开始时将参加匹配的局部模式配对，并以对称的方式 进行集成时就称为二元平衡策略。多元匹配策略分为两种：多源一次匹配策略和 多元逐次匹配策略。多源次匹配策略是指在全局模式的集成过程中将要参加匹 配的数据库模式一次集成为一个全局模式。多源逐次匹配策略是分多次集成来生 成最后的全局模式，每次匹配多于两个的局部模式或中间结果模式。对于各种匹 配策略可以看示意图2 3 ： 河海大学硕士学位论文 全局模式和局部模式之间的模式匹配技术研究 2 4 模式匹配方法 2 4 1 方法分类 图2 3 匹配策略类型 匹配是一个模式操纵，它将两个模式作为输入然后返回在这两个模式中相应 元素的一个映射。模式匹配在许多应用程序中是一个重要的步骤：在电子商务里， 帮助在不同的x m l 模式之间的映射信息；在数据仓库里，将数据源映射成仓库 模式：在中介器里，辨别异构数据库之间的集成点，全局模式也可以是事先给定 的。 一个模式由一组元素组成，元素可以是表、列、类、属性等。模式匹配问题 是；对于一个模式s 1 ( 比如全局模式) 和一个模式s 2 ( 比如数据源模式) ，在这两个 模式的相应元素之间找出某些语义上相同或相似的关系，由此产生s 1 与s 2 的匹 配关系【1 4 1 。当前，解决这些异构性问题的模式匹配一般是手工执行的。这个手 工过程是冗长的、费时的、容易出错，因而代价很高。这就需要一个劳动强度相 对较小的方法。这样一个方法应该对辨别关系提供自动支持，并且能够在源模式 和全局模式之间生成映射。现存的方法的分类总结在图2 4 中。 河海大学硕一l ! 学位论文 全局模式和局部模式之问的模式匹配技术硼究 语 眵匹配枣法 独立匹配方法 罗 基于模式的方式基于实例的方法混合匹配 复合匹配 元7 瑚合 翥篓嚣糕藿 类型相似性 图匹配1 r 方法辅助信息 图2 4 现存的模式匹配方法的分类 自动组合 模式匹配时可能会用到多种匹配方法( 匹配器) 1 3 4 l 。我们可以根据具体的 应用要求灵活的选用不同的方法及其组合。在具体实施时有一个组合使用它们的 问题。我们可以在匹配过程中先后使用多个匹配标准，这是混合匹配法。我们也 可以分别执行各个匹配算法，然后再将结果合并，这是复合匹配法_ j 。 对于单独的匹配方法，我们可以考虑以下互不相关的分类标准。 模式级与实例级：前者只考虑模式信息，而不考虑实例数据。模式信息包括 名称，描述，关系，约束，等等。后者利用了这两方面的信息。 模式级匹配方法只考虑模式信息，不考虑实例数据，可用的信息包括模式元 素的一般属性，如名称，描述，数据类型，关系类型( p a r t o f , i s a 等) ，约束和 模式结构等等。一般的，一个匹配算法会找到多个候选结果，每个候选结果都有 一个介于0 到1 的数值表示它的相似程度。 实例级方法由于利用了数据实例的信息，因而和模式级方法互为补充。它即 可以和模式级方法一起使用，互相验证，也可以单独使用。从实例数据中抽取出 模式元素特征的方法，如规则，神经网络，机器学习等。一般的实例级方法寻找 的是模式元素之间的匹配关系，要找到模式元素组合或结构的匹配就需要比较这 些元素组合的数据实例。显然，这样做遇到的主要问题是模式元素的可能组合空 间是及其巨大的。如果不加限制，这样的任务是根本不可能完成的。 法方 的、 柬lf 呦、 基法 勃日il 语， 法方 河海大学颂士学位论文 全局模式和局部模式之问的模式匹配技术研究 元素级与结构级：它们是相区分的两个主要的匹配粒度。前者只考虑模式中 独立的模式元素，后者还要考虑这些模式元素的组合。 元素级匹配考虑的是模式中的单个概念、属性或关系，而不考虑这些逻辑模 式之间的联系。也就是说它在匹配父模式时，并不会去考虑其子模式或与其他模 式之间的关系。 与之相反，结构级匹配不光要考察单独的对象，还要考虑它们之间的联系。 结构匹配可能是完全匹配，也可以是部分匹配，这取决于匹配所要求的完整性和 准确性。理想情况下，两个模式中相应结构的所有组成元素都能一一对应，即完 全匹配。但实际上，一个模式中的某些元素在另一个模式中找不到对应部分，这 时就只能达到部分匹配。针对复杂的情形，为了提高效率，我们可以在数据库中 存储己知的等价模式，然后在匹配过程中直接参考这些模式。 基于语言与基于约束：前者基于语言( 如名称和描述文本) ，后者基于基本 的约束信息。基于语言的方法中最常用的信息是元素名称。度量名称相似的标准 有很多，如等价关系，同义关系，上义关系( h y p e m y m ，若y 属于x ，则x 是 y 的上义词，如“出版物”是“论文”的上义词) ，以及编辑距离( e d i td i s t a n c e ) ，甚 至词语的发音等。为了发现这些关系，通常都要用到词典。在这方面，自然语言 词典是很有帮助的。在具体应用领域中，领域相关的词典由于含有领域知识( 常 用的专业词汇，简写等) 因而具有特别重要的价值。但是，当前可利用的领域词 典较少，需要研究者付出更多的努力。 自然语言中的一词多义现象极大的干扰名称匹配的过程。为了减少由此产生 的误配情况，需要由人或词典提供失配信息。这样的方法很类似于基于结构的方 法，这也使得两种方法之间的分别变得模糊。 模式中包含的约束信息，有数据类型、取值范围、唯一性、可选性、关系类 型和可选值等。如果要比较的双方都有这样的约束信息，就可以它为根据来决定 模式元素的相似性。 如果仅使用约束信息进行匹配，得到的往往是n ：m 的匹配结果。具有相同约 束条件的元素可能有好几个，例如，有好几个元素都是s t r i n g 类型。为了进一步 区分这些元素，可以和其他的匹配方法( 如名称匹配) 结合起来使用。 一些结构信息也可以认为是约束信息，如整体与部分的关系( p a r t o f ) 。这 些信息告诉我们哪些元素属于同一个更高级别的元素，这个过程可以在多级结构 上传递的进行。当然，这些约束信息也可以看作是结构信息，用结构匹配方法来 判定相似性。这样的匹配既考虑了拓扑结构，也考虑了不同的元素类型和可能的 不同类型的结构连接。 匹配基数：整个的匹配结果可以将一个模式中的一个或多个元素映射到另一 个模式中的一个或多个模式【川，因而产生了四种情况：1 ：1 ，1 ：n 1 ，n ：l ，n ：m 。匹配基 1 4 河海大学硕士学位论文 全局模式和局部模式之问的模式匹配技术研究 数又分为局部的和全局的。如果只在一条映射规则中考虑，则是局部的，如果在 不同的映射规则中考虑，那就是全局的。例如，在两条映射规则中，模式t 1 分 别和t 1 ，t 2 相似，则其局部基数是1 ：1 ，全局基数是1 ：n 。 现有的匹配方法大多把一个模式中的每一个元素与另一个模式中具有最高 相似性的元素匹配。这样产生的结果在局部是1 ：1 的匹配，在全局则是1 ：1 或1 ：n 的映射关系。现有的大多数方法都不能产生局部和全局1 ：1 和n ：m 的映射关系， 要产生这些映射关系需要在匹配算法中采用更复杂的标准。 辅助信息大多数匹配方法不仅仅依赖所输入的模式信息，还会用到一些辅 助信息，例如字典，以前的匹配结果，还有用户的反馈等等。 2 4 2 不同方法的结合 每种匹配方法利用了不同的信息，对于一个给定的匹配任务，各有不同的适 应性和价值。因而，组合使用几种方法比单单采用一种方法会产生更好的结果。 组合的方式有两种：混合方式集成了多种标准，复合方式则合并各个独立执行的 匹配方法的结果。组合多种匹配方法也为同时进行评估提供了可能。 混合匹配方法在整个过程中采用了多个标准。和多个匹配方法的单独执行比 较起来，它可以提供更好的候选结果和更好的性能。由于仅符合一种标准的候选 结果可以在早期被排除，以及在匹配过程中要综合考虑多种标准，混合匹配方法 效率更高。结构级匹配也能从与其他方法如名称匹配联系使用中得到好处。一种 组合结构级和元素级匹配的方法是先用一种方法产生部分映射，然后再用另一种 方法完成映射。 混合匹配方法可以提供更好的性能，因为它可以减少遍历整个模式结构的次 数。例如，元素级匹配的混合方法可以在每个模式元素上同时测试多个标准，然 后再测试下一个模式元素。 另一方面，复合匹配方法则把几个独立执行的匹配方法的结果合并起来，这 些方法中也可以包括混合方法。这种合并多个匹配方法的能力使它比混合方法具 有更大的灵活性。混合方法通常用硬连接的方法组合同时执行或以固定次序执行 多个匹配方法。与之对比，复合方法允许我们以模块化的方法选择所需的方法。 例如，我们可以用机器学习的方法组合独立的匹配方法。而且，复合方法在执行 顺序上没有特别地要求，我们可以让它们同时执行，也可以让它l r j l 顷序执行。在 后一种情况下，前面执行的匹配方法的结果可以被后面执行的方法利用，以取得 更好的结果。 匹配方法的选择、执行次序的决定和独立运行结果的合并，这些既可以由匹 配方法本身自动决定，也可以由人来决定。自动化的方法可以减少人的参与，但 河海人学硕= l 学位论文 全局模式和局部模式之间的模式匹配技术研究 是很难获得一个适合于不同应用领域的通用的解决办法( 虽然可以通过调整参数 来进行控制) 。作为可选的方案，可以由人来直接选择匹配方法，决定执行次序， 和如何合并结果。这样更容易实旌，以给了用户更多控制的余地。在任何情况下， 用户的参与都是必不可少，因为匹配方法本身只是提供一些候选结果，最终需要 用户来决定是接收，拒绝，还是改变结果。 为了处理复杂的匹配任务，还需要在匹配过程中支持多个用户的迭代开发。 在复合方法中，各个匹配算法可以按照一定的顺序执行，用户提供的匹配结果也 可以作为其中一种独立的匹配算法。对于用户提供的匹配输入，复合匹配方法必 须意识到它的权威性，不会去改动它，而把精力放在解决不匹配部分上。 我们在前面介绍的各种模式匹配原型都是按照上面的分类标准，基于不同的 匹配准则的基础上来执行模式匹配。例如c u p i d 是一种基于元素级和结构级匹配 的混合方法。s f 也是一种综合使用了名称匹配和结构匹配的混合方法。g l u e ( l s d ) 和c o m a 系统采用的都是复合方法。 2 5 本章小结 本章综述分析了模式之间存在的冲突问题，描述了一个实现数据集成领域中 全局模式和局部模式之间的模式匹配过程和匹配策略，并且提供了一个自动执行 模式匹配的不同方法的一个分类。从这里我们可以看到全局模式和局邦模式之间 的模式匹配利用各种匹配方法构造相应的匹配器，找出模式元素间的映射关系。 匹配器可以是单个匹配器，即基于一个单独的匹配规则计算出最终的匹配映射关 系；也可以是单个匹配器的混合，即在一个杂交的匹配器中运用多种匹配规则进 行匹配：或是应用复合的匹配器对不同匹配器计算出的多种匹配结果进行合并。 单匹配器可以是基于模式或基于实例的。单匹配器也可按照元素粒度或结构 粒度进行划分。匹配器可用基于语言的方法或基于约束条件的方法。匹配结果将 一个模式中的一个或多个元素和另一个模式中的一个或多个元素相联系。另外， 每一个匹配映射中的元素可和两个模式中的一个或多个元素间存在内在联系，在 基于实例的匹配中可能存在着不同匹配基数。 构建匹配器时，往往不只用到输入的两个模式