（计算机软件与理论专业论文）数据库模式间语义映射系统的研究.pdf

摘要 摘要 随着信息化时代的不断发展，异构模式间的语义映射成为了人们关注 的焦点问题。目前，模式间语义映射的两大关键组成部分多作为两个独立 的单元分别进行研究，然而，随着s e m a n t i cw e b 概念的提出，迫切的需要 将模式匹配与模式映射结合起来，从而实现异构模式间完整的语义映射。 本文以全局和局部两种角度对语义映射系统进行了研究。 首先，通过对目前最先进的i m a p 模式匹配系统进行研究，发现其在 匹配处理过程中还存在着一定的不足，通过对抽取的i m a p 系统框架进行 扩展，在其前期处理中加入一个预处理模块，并进一步对域知识进行扩充， 针对预处理模块加入相应的域约束条件“类型a 的属性集合中任何属性都 不能与类型b 的属性集合中的任何属性进行组合，构造出与目标模式属性 相匹配的候选匹配”，从而构建出基于i m a p 系统框架的语义映射系统模式 匹配模块，并从理论和实验上证明了其可行性。 其次，通过进一步对c l i o 模式映射系统处理过程的研究，将其模式映 射思想与模式匹配模块相整合，构建出语义映射系统的模式映射模块，实 现了模式匹配后的数据传输或交换，形成一个完整的异构模式间的语义映 射系统。 再次，在整合的语义映射系统的模式映射模块中，根据模式匹配模块 中所得到的候选匹配相似度，提出一个候选映射最大相似度和算法，对模 式映射模块中的候选映射集合进行自动化处理，提取出可信度最高的候选 映射。 最后，在整个模式映射模块的处理过程中，提供一个图形用户接口 ( g u i ) ，以便于系统在处理过程中与数据库管理员( d b a ) 进行交互，使得 d b a 能够指导整个映射的处理过程，及时纠正错误的候选映射。 关键词语义映射；模式匹配；模式映射；候选匹配；相似度；候选映射 燕山大学工学硕士学位论文 a b s t r a c t w i t ht 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 ，s e m a n t i cm a p p i n gb e t w e e n d i f f e r e n ts c h e m a sh a sb e e naf o c u si s s u ea l lo v e rt h ew o r l d ，a tp r e s e n t ，i t st w o c o m p o n e n t sa r em o s t l ys t u d i e da st w oi n d e p e n d e n tp a r t s b u tt h en o t i o no f s e m a n t i cw e bu r g e n t l yn e e d st oc o m b i n es c h e m am a t c h i n gw i t hs c h e m a m a p p i n gt o g e t h e li no r d e rt or e a l i z et h ei n t e g r a t i v es e m a n t i cm a p p i n g b e t w e e n d i f f e r e n ts c h e m a s ，w es t u d yi ns e m a n t i cm a p p i n gs y s t e mb yt w op o i n t so f v i e w ： g l o b a l - v i e wa n d l o c a l - v i e w f i r s t l y , s t u d y i n gt h em o s ta d v a n c e di m a ps c h e m am a t c h i n gs y s t e m , w e f i n dt h a ti ts t i l lh a ss o m es h o r t a g e si nt h ep r o c e s s ，a n dm o d i f yt h ef r a m e w o r ko f i m a p , b ya d d i n gap r e p r o c e s sm o d u l et ot h ep r o p h a s eo fp r o c e s sa n de x t e n d t h ed o m a i nk n o w l e d g ew i t had o m a i nr e s t r i c t i o nr e l a t e dw i t hp r e p r o c e s s o r s u c ha s a n ya t t r i b u t ei nt h ea t t r i b u t es e to f t y p ea c a nn o tc o m b i n ew i t ht h a to f t y p eb t oc o n s t r u c tam a t c hc a n d i d a t e ”c o n s e q u e n t l yw ec o n s t r u c tas c h e m a m a t c h i n gm o d u l ei ns e m a n t i cm a p p i n gs y s t e mb a s e do n 心搬a n dp r o v ei t s f e a s i b i l i t yb ym a t h e m a t i c sa n de x p e r i m e n t s e c o n d l y , s t u d y i n gt h es c h e m am a p p i n gs y s t e mc l i o ，w ei n t e g r a t ei t s s c h e m am a p p i n gi d e aw i t ht h ei m p r o v e ds c h e m am a t c h i n gm o d u l ei ns e m a n t i c s y s t e mt or e a l i z et h et r a n s m i s s i o na n d m o d i f i c a t i o na r e rs c h e m am a t c h i n g ，a n d f o r ma ni n t e g r a t i v es e m a n t i cm a p p i n gs y s t e mb e t w e e nd i f f e r e n td a t a b a s e s c h e m a s t h i r d l y ，i nt h es c h e m am a p p i n gm o d u l e o ft h ei n t e g r a t i v es e m a n t i c m a p p i n gs y s t e m ，a c c o r d i n gt ot h es i m i l a r i t yv a l u ei ns c h e m am a t c h i n gm o d u l e ， w ep r o p o s eam a xc a n d i d a t em a p p i n gs i m i l a r i t ya l g o r i t h mt oa u t o m a t i c a l l y e x e c u t et h ep r o c e s so fs c h e m am a p p i n g ，a n dd i s t i l lt h ec a n d i d a t em a p w i t ht h e h i g h e s tr e l i a b i l i t y a b s t r a c t f i n a l l y , w ep r o v i d eag r a p h u s e ri n t e r f a c e ( g u i ) t oh e l pd b ai n t e r a c tw i t h t h es y s t e m p u t t i n gc a n d i d a t em a p p h a gr i g h ti nt i m e ，a n dd i r e c t i n gt o w a r d st h e r i g h tw a y , i ti sc o n v e n i e n tf o rg u i d i n gt h ep r o c e s s k e y w o r d ss e m a n t i cm a p p i n g ；s c h e m am a t c h i n g ；s c h e m am a p p i n g c a n d i d a t em a t c h ；s i m i l a r i t y ；c a n d i d a t em a p p i n g m 第1 章绪论 1 1 研究背景 第1 章绪论 s e m a n t i cw e b 是互联网缔造者t i mb e r n 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 理论模型的提出，对异构模式问的语义映射系 统的需求也就日益迫切。异构模式间的语义映射主要由两个基本步骤组成， 它们分别是模式匹配和模式映射。 目前，这两个组成部分大多作为独立的单元进行研究。模式匹配概念 的提出要追溯到8 0 年代的模式集成理念，而随着模式匹配不断的发展变 化，匹配后的数据需要迸一步的传输和修改，因此，模式映射概念于9 0 年代也应运而生了。现在，由于需求的不断扩大，需要我们把这两个独立 单元结合起来，从而构建出完整的异构模式语义映射系统。 1 2 语义映射研究现状 由于语义映射是用来详细说明存储在不同数据源中的数据之间的关 系，因此它是任何数据共享结构框架的核心。同时它可以是一个集成系统、 数据仓库、对等数据管理系统或基于w 曲s e r v i c e 的关键组成部分。数据共 享系统在很多应用领域都是至关重要的，例如：企业数据集成、科学协作、 在w w w 上的数据管理以及政府机关之间的协作等等。 目前，语义映射多是通过图像用户界面人工创建的，并且此类工作实 际上是非常乏味和容易出错的，因此，迫切的需要实现语义映射的自动化。 燕山大学工学硕士学位论文 目前，半自动的创建映射问题已经在数据库和人工智能中得到了重视。然 而，相关的研究只是针对语义映射的两个关键组成部分分开进行研究的。 下面就对这两个关键组成部分的研究现状分别进行简要的介绍。 1 3 模式匹配研究现状 对模式匹配的研究早在上个世纪8 0 年代就已经开始了。早期的模式匹 配工作是为模式集成服务的。进入九十年代，随着模式集成问题的发展变 化，模式匹配开始应用于将数据源集成到数据仓库的过程中。在最近的二 十年，电子商务的出现进一步推动了模式匹配的研究。由于交易伙伴经常 交换描述商务交易的信息，而通常情况下，每一个交易伙伴使用他自己的 信息格式，因此不同的消息模式间的转换也需要模式匹配操作。 由于需求的不同，模式匹配工作大部分仍以人工( 域专家或数据库管理 员) 定义方式为主，费时费力且容易出错。而这个问题也随着w e b 数据源 的快速增加与电子商务的一体化而目趋严重。同时，随着系统处理数据库 模式的日益复杂，数据库中数据规模的不断扩大，需要完成更多的匹配， 手工工作量与需要完成的匹配数目成正比。因此，需要找出一种通用的、 自动化程度高的、可以应用于不同数据模型和应用领域的综合的模式匹配 方法。 近些年来，模式匹配作为数据管理应用中的基础性问题受到了全球的 普遍关注。 在我国，目前对于模式匹配的研究还处于起步阶段，只有国防科技大 对此领域有较深入的研究，并且将模式匹配技术应用于军事领域，同时还 得到了国家科研项目的支持。 而在国外，目前已经开发出了很多半自动的发掘模式匹配【l 叫的系统和 方法，例如；a u t o p l e x 、a u t o m a t c h 、c o m a 、c u p i d 、d e l t a 、d i k e 、e j x 、 g l u e 、l s d 、m o m i s 、a r t e m i s 、s e m i m 、s k a t 、s f 和t r a n s c m 等等。 然而，它们中的大部分是由于特殊的应用需求而开发出来的。其中仅有很 少的几个，如：c o m a 、c u p i d 和s f 是以一种通用化的方式来解决模式匹 2 第1 章绪论 配问题，这种通用化的方式能够适用于不同的应用需求和模式语言。关于 模式匹配的研究大部分把重点放在发掘模式元素之间的1 ：1 匹配，例如： 一个1 ：1 一致性会详细的说明在源模式中的元素l o c a t i o n 与目标模式中的 a r e a 元素相匹配，或是a g e n t n a m e 与n a m e 相匹配。 然而，1 ：1 匹配是很普通的，在现实世界模式之间的关系还包括很多 的复杂匹配。一个复杂匹配指明了一个模式与另一个模式中相一致的属性 的组合。例如：它可以具体指明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 = - - c o n c a t ( c i t y , s t a t e ) 。实际上，我们所考虑的异构模式中，复杂的匹配占全部 匹配的一半左右。因此，半自动的发掘复杂匹配技术的发展对于任何实际 的映射来说都是非常重要的。 2 0 0 4 年s i g m o d 会议上r o b i nd h a m a n k a r ，y o o n k y o n gl e e ，a n h a i d o a n ，a l o nh a l e v y 和p e d r od o m i n g o s 提出的i m a p t s 模式匹配系统就很好 的解决了此类问题，此系统不仅能够半自动的发掘模式间的1 ：1 匹配，而 且能够较准确的发掘出复杂匹配。但是，此系统在一定程度上还存在着不 足。 1 4 模式映射研究现状 构建模式映射的过程是一个搜索基于一致性属性、模式属性和隐藏于 数据当中的模式或结构线索的映射过程。异构模式间进行匹配后，必然需 要对匹配项进行进一步的数据传输和交换。这就涉及到语义映射的第二个 关键组成部分：模式映射。目前，很多应用，如：数据仓库、全局信息系 统和电子商务都需要从源模式中提取数据，然后把这些数据重新应用到目 标模式当中。 模式映射概念是在模式匹配概念提出后，于9 0 年代提出并发展起来 的。在这方面，早期只是在理论上进行研究，加拿大多伦多大学的r e n e e j m i l l e r 教授就是其中最杰出的专家之一。随着模式匹配和模式映射的发展 成熟，m i l l e r 在2 0 0 0 年与5 位i b m 软件工程师一起开发了c l i o 系统1 9 】。 该系统集模式匹配和模式映射于一身，实现了异构模式间完整的语义映射。 燕山大学工学硕士学位论文 然而，该系统的匹配模块过于简单，数据一致性主要依靠数据库管理员进 行人为的指定。而系统中关于模式映射模块的设计则是最早的模式映射原 型，也是目前为止最成熟的映射原型。但是，在国内，研究的重点集中在 信息查询上，主要是查询优化等方面，而对此领域的研究还很少。 1 5 论文结构 本文通过对i m a p 系统进行改进，增加一个预处理单元，并对域知识 进行扩充，加入与预处理单元相对应的域约束，构造出一个基于i l v i a p 系 统基本框架的模式匹配模块，大大的提高了模式匹配的效率和精确度。同 时，通过对c l i o 系统模式映射思想的研究，把该思想与改进的模式匹配模 块相结合，整合出一个完整的异构模式语义映射系统。并且针对映射思想 中数据一致性与模式匹配中候选匹配两者的关系，构造相应的处理单元实 现两者的转化。同时，将模式匹配系统框架中候选匹配相似度与模式映射 思想中的核心算法相结合，提出一个新的映射算法。 第2 章作为后续内容的铺垫，简单介绍相关的基础理论。主要介绍了 模式匹配的技术分类，并对模式匹配和模式映射中的基础概念进行了概括 性的描述。 第3 章重点阐述模式匹配基本框架，对基本框架的各个组成部分进行 了详细的描述，并通过分析，指出基本框架存在的问题。 第4 章描述了模式映射发掘算法的思想，并对算法的实现进行了详细 的说明。 第5 章详细阐述课题的研究方案，根据模式匹配基本框架存在的问题， 构建出基于基本框架的模式匹配模块，并通过对模式映射思想的研究，将 两者整合成一个综合的语义映射系统，对系统的框架结构进行了详细的说 明，并通过实验数据说明了该原型系统的可行性。 最后，对全文进行总结，并提出下一步的设想。 4 第2 章基础理论 第2 章基础理论 2 1 模式匹配技术分类 模式匹配定义为在作为输入的模式中有对应语义关系的元素间产生一 个映射。由于不同的背景环境而造成的数据源( 关系数据库、面向对象数据 库、x m l 、h t m l 等) 异构问题已经成为信息集成的主要障碍。实现异构 数据源无缝集成的首要问题是定义异构数据源模式元素之间的数据一致性 关系，即异构模式间的模式匹配。 根据不同的应用需求，模式匹配有多种分类标准，图2 1 描述了模式 匹配的整体分类【1 0 】。 s c h e m a m a t c h i n g a p p r o a c h e s h l d i v i 洲鼍“h e r7 一一一b m b i 岫m 蚰e n 邺”4 螋。 瓮嘶 i n s t a l l c e , o o n t 、e n t s b a s m h 地y b r i d nc m 皿”c i i p o e s i l c e ，者f 、。叩栅- 嗉太艋f ：l 。 4 。；、砷。上nm 厶函一咿m “ 。一 o _ b e db a s e d 1 1 ，j n s i m i a m l a r e 时卿t y p i e l 嘶 。g r m a p c l i h d e s c r i p t i o n k e yp r o p e i i l g s i m i l a r 时 s 蚰l l 明t y 一“ ；。 v s i m i l a r i t y 图2 - 1 模式匹配技术分类 f i g 2 - 1t h ec 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 从图中可看出，匹配技术分为单一匹配技术和合成匹配技术，对于单 一模式匹配技术，又有如下分类标准： ( 1 ) 基于模式的匹配技术基于模式的匹配技术仅考虑模式信息，而不 考虑实例数据。可获得的模式信息包括模式元素的一些属性，如元素名、 燕山大学工学硕士学位论文 描述、元素实例的数据类型、关系类型、约束和模式结构。通常情况下， 基于模式的匹配技术可以发掘出多个候选匹配，每一个候选匹配都有一个 在 0 ，1 范围内的数字化的匹配相似度值，通过比较这些数字化的相似度值 可以得出最优的候选匹配。 ( 2 ) 基于实例的匹配技术基于实例的匹配技术考虑的是实例级的数 据，通过这些实例级数据我们可以认识到模式元素所表示的内容和意义。 在可用的模式信息非常有限的情况下( 尤其是对于半结构化数据) ，它们是 非常有意义的。特别是在没有给定任何模式信息的非常情况下，可以通过 实例数据手工的或自动的构造出模式。而且，在应用基于模式的匹配技术 发掘出来的候选匹配具有相同的相似度的情况下，应用基于实例的匹配技 术可以选择出正确的候选匹配。 ( 3 ) 基于元素的匹配技术基于元素的匹配技术是对单个模式元素进 行匹配。对于第一个输入模式的每个元素，基于元素的匹配在第二个输入 模式中确定匹配元素。在最简单的情况下，仅考虑粒度的最底层元素，即： 原子层。例如：x m l 模式中的属性或关系模式中的列。但其也不仅限于原 子层，也可应用于高层( 非原子层) 元素。高层粒度包括文件记录、实体、 类、关系表和x m l 元素。基于元素的匹配可以通过与关系连接处理相似 的算法实现。 ( 4 1 基于结构的匹配技术基于结构的匹配技术发掘在结构中共同出 现元素的匹配组合。在理想的情况下，两个模式中所有结构的组成都可以 匹配。另一种情况就是仅仅有部分组成需要匹配。而在更复杂的情况下， 基于结构匹配的有效性可通过考虑保存在知识库中的己知等价模式来提 高。 ( 5 ) 基于语言学的匹配技术基于语言学的匹配应用名字和文本( 如单 词或句子) 来挖掘语义上相似的模式元素。主要技术有基于名字的匹配和描 述匹配。基于名字的匹配是通过等价或相似的名字来匹配模式元素的。而 描述匹配是通过对模式在语言上的描述来确定模式元素间的相似度。 f 6 ) 基于约束的匹配技术对于定义数据类型、数据值的取值范围、唯 一性、可选性、关系类型等通常都会有一些模式约束。如果两个输入模式 6 第2 章基础理论 中都包含有这样的约束信息，那么匹配器就可以应用这个约束信息来确定 模式元素的相似度。基于约束的匹配技术有助于限制候选匹配的数量，并 且可以和其他类型的匹配器结合使用。 ( 7 ) 基于匹配基数的匹配技术通过一个联系集，映射基数指明实体集 中的一个实体同另一个实体集相关联的实体数目。所有的匹配结果总结出 来有四种情况：1 = 1 、1 ：n 和m ：n 。 ( 8 ) 基于辅助信息的匹配技术大多的匹配器不仅依赖于输入模式，还 依赖于辅助信息，比如数据字典、已知的匹配结果和用户的建议等。 以上介绍了多种匹配技术。对于某一匹配任务，每一种技术都应用不 同的信息并且有不同的应用领域。同时，应用一种技术的匹配器不像结合 了多种技术的匹配器那样能够高效的发掘出更加准确的匹配。正是由于单 一匹配技术( 无论是基于模式的还是基于实例的) 在进行模式匹配时具有此 种局限性，因此，结合的匹配技术应运而生了。结合不同的匹配技术有两 种方式：一种是混合的匹配器( h y b r i dm a t c h e r s ) ，它基于多个标准和信息源， 综合了多种匹配技术来确定候选匹配。另一种是合成的匹配器( c o m p o s i t e m a t c h e r s ) ，它是把多个单一匹配器独立运行时产生的结果进行合并。下面 我们就介绍几种已经开发出来的模式匹配技术，从它们的实现方法、优缺 点等来对这些技术进行概括性的介绍。 2 2 模式匹配技术应用举例 2 2 1s e m i n t s e m i n t 】是由n o r t h w e s t e mu n i v e r s i t y 开发的一个应用混合匹配技术 的模式匹配系统，它主要应用神经网络技术去确定候选匹配，并在两个模 式的单属性间建立一个映射，即它的匹配基数是l ：l 。它应用了高达1 5 个 基于约束的和5 个基于内容的匹配标准。基于模式的约束从关系数据库管 理系统的目录中应用可供利用的信息。同时，实例数据还通过提供数据值 的分配、数据的平均个数来增强此类信息。对于每一个标准，系统应用一 燕山大学工学硕士学位论文 个函数把每个可能的候选匹配相似度映射n o ，1 1 区间上。应用这些函数， 对n 个匹配标准，s e m i n t 为每一个由在 o ，l 】区间上的值所组成的属性确 定一个匹配签名( 或全部或是支持标准的一个己选择的子集) 。由于签名对 应于n 维空间的一个点，那么签名间的欧几里德距离就可作为相似度的评 价标准来使用，从而确定一系列的匹配候选。由于系统可以同时选择多个 匹配标准并对确定的候选匹配进行估价，因此，s e m i n t 是一个应用强大的、 灵活的混合匹配技术的模式匹配系统。 但是，s e m i m 不支持基于名字的匹配或图形匹配，而且s e m i n t 方法 需要用户手工操作，如选择最优的匹配标准，从属性聚类中选择匹配属性， 在这一方面，其自动化程度太低。 2 2 2 c u p i d c u p i d 1 2 】应用的是一种通用化的混合匹配方法，它把一个名字匹配器 与一个结构化匹配算法相结合，根据这个结构化算法可以推导出元素的相 似度，而元素的相似度是根据元素组件( 主要是元素名字和元素的数据类型) 的相似性得出的。 在c u p i d 系统中，为了解决元素的共享问题，将模式图转换成树的形 式，在树中通过增加附加的节点来解决共享节点和它的父亲节点之间的多 重关系。但是，c u p i d 也只是对模式匹配问题做了更进一步的工作，并没 有完全解决这个问题，仍需要加入其他的技术( 如：应用于实例的机器学习， 通用化语言技术，可重用已知匹配的匹配模型等) 来使c u p i d 更加全面。 2 2 3c o m a c o m a t l 3 】应用的是一种合成的模式匹配方法，它提供一个承载了多个 不同匹配器的外部知识库，并且支持多种结合匹配结果的方法。目前，匹 配器利用的是模式信息，如元素和结构属性( 也就是说应用的是基于模式的 匹配技术1 。另外，还提供了一个特殊的匹配器来对以上匹配器产生的结果 进行筛选过滤。其中的结合策略应用于匹配处理过程的各个不同组成部分， 例如，对各个匹配器产生结果的聚合和对候选匹配的选择。它把输入模式 第2 苹基础理论 转换成具有根节点的有向无环图，在图上应用所有的匹配算法对图进行操 作。每一个模式元素都是通过从模式图的根节点到相关节点的完全路径唯 一标识的。 输入模式sj 、s 2 后，在匹配过程中的一次或多次交互过程中，候选 匹配的确定是自动化和交互式完成的。每一次的匹配迭代都e h _ - - - 个步骤组 成：可选择的用户反馈阶段、不同匹配器的执行阶段和匹配结果的合并阶 段。在交互模型中，每一次迭代时，用户都可以与c o m a 相交互，指定匹 配策略( 匹配器的选择、合并匹配结果的策略选择) ，定义正确或错误匹配 的关系，接受或拒绝以前迭代中建议的候选匹配。交互式的技术有利于对 特殊模式测试和比较不同的匹配策略，并有利于不断的精炼和提高匹配结 果。在自动化的处理过程中，匹配过程仅进行一次匹配迭代，应用个默 认的策略或通过输入参数指定的策略，这种模型适用于已知自身最适合的 匹配策略或已完成自身用户交互接口的应用领域。但是，c o m a 只解决了 l ：1 匹配，而在实际应用中1 ：1 匹配只是所有匹配当中的一部分，因此需要 应用c o m a 匹配思想来开发新算法，从而提高匹配的精确度，并进一步实 现对复杂匹配的挖掘。 2 2 4s m d d s m d d 1 4 】模式匹配技术是n d b c 2 0 0 5 上提出的一种基于数据实例分 析特征的模式匹配方法。它通过分析模式元素所包含数据的分布特征，利 用神经网络的模式识别功能找出具有相似数据分布规律的元素集合，并进 一步计算模式元素之间的相似度，最后将推荐的候选匹配返回给用户。它 与s e r n i n t 的主要区别在于其所考虑的是数据内容。下面简单介绍一下 s m d d 方法的模式匹配过程。 ( 1 ) 提取数据分布特征向量s m d d 利用特征提取器提取目标模式中 模式元素所包含的部分数据实例，分析其分布规律，生成数据分布特征向 量。 ( 2 ) 分布特征向量聚类s m d d 利用聚类算法将输入的数据分布特征 向量动态地分为m 类，并计算聚类中心。分类数m 由凝聚层次聚类算法 燕山大学工学硕士学位论文 根据相似度域值动态确定，不要求用户预先设定。 ( 3 ) ；j l l 练神经网络s m d d 生成三层前馈神经网络，将聚类中一o 作为训 练样本，利用b p 学习算法反复迭代计算，调整突触权重以适应输入模式 的激励，最终识别类c j 。 ( 4 ) 计算元素相似度利用特征提取器提取源模式中的模式元素的数 据分布特征向量，将其输入经过训练的神经网络，计算输入向量与目标模 式元素中各分类的相似度。 ( 5 ) 匹配选择选择相似度较高的匹配对作为候选匹配返回给用户。 s m d d 通过挖掘数据内容信息，根据元素的数据分布特征计算模式元 素之间的相似度。但s m d d 的匹配质量很大程度上依赖于数据源中数据的 规律性分布。在数据分布较为规律的情况下，s m i ) d 的匹配质量较好，反 之，计算效果不理想。 2 3 问题定义 在这里，我们是对关系模式下的模式匹配进行讨论的，但是，所提供 的思想可以贯彻到其他的数据表示当中。通过一个实例来考虑两个关系模 式s 和t ，如图2 2 所示。两个数据库存储的都是房屋列表清单，并且由 两个不同的财团进行管理。 s c b e m ass e h c m at h a u s r s ocationpric。(s)ia g c n t o l d l i s t i n g s 图2 - 2 关于房屋清单的两个关系数据库模式间的语义映射 f i g 2 - 2s e m a n t i cm a p p i n gb e t w e e nt w os c h e m a so f r e l a t i o n a ld a t a b a s eo nh o u s el i s t i n g 1 0 第2 章基础理论 假设两个财团决定要进行合并。为了减少开销，他们通过把s 中的所 有房屋列表传送到t 中，从而删去数据库s 。在不知道关系数据库模式之 间的语义映射的情况下，这种传送是不可能的。下面，我们通过使用s q l 表示法，描述了t 中单一属性的一些映射。同时详细说明了把s 中数据传 送到t 中所创建的元组。实际上，要说明语义映射，可以使用的方法有很 多种，如：s q l 、x q u e r y 、g a v 、l a v 、g l a v t ”1 。下面的例子通过使用 s q l 来表示上面的公司合并实例： a r e a = s e l e c tl o c a t i o nf r o mh o u s e s a g e n t - a d d r e s s = s e l e c tc o n c a t ( c i t y , s t a t e ) f r o ma g e n t s l i s t p r i c e 2s e l e c tp r i c e + ( 1 + f e e r a t e ) f r o mh o u s e s ，a g e n t s w h e r e a g e n t i d 2 i d 通常情况下，创建语义映射的过程分为两步。第一步，模式匹配，可 以发两个模式元素之间的语义一致性。第二步，我们通过创建映射表达式 来详细阐述匹配，并通过这些表达式对数据进行自动的传输或交换。需要 注意的是，语义映射的这两步可能都需要与设计者进行交互。 实际上，一个语义映射系统的目标就是提供一个环境，在这个环境中 用户可以快速的创建两个模式之间的映射。并且，在创建映射的过程中， 用户可以对系统提供的假设建议进行思考，然后把反馈返回给系统，从而 来指导系统找出最优的映射，并最终实现用户需求的数据传输与交换。 2 4 本章小结 本章通过介绍模式匹配技术的基本分类，举例说明了几个常用模式匹 配系统的工作原理，对模式匹配的一些相关概念进行了概括性的介绍，并 且通过问题定义当中财团合并的实例说明了语义映射系统的目的和意义。 燕山大学工学硕士学位论文 第3 章模式匹配基本框架 3 1 体系结构 本文所应用的模式匹配基本框架是一个半自动发掘数据库模式之间的 l ：1 匹配和复杂匹配的框架。虽然目前该框架考虑的只是关系模式之间的 匹配，但是，它所归纳的思想可以应用到其它的数据表示当中。 同时，它还是一个运用了多种模式匹配技术的综合系统框架。它不仅 应用了已有的模式匹配技术，还应用了一些新的方法： ( 1 ) 产生匹配为了阐述对无穷数目候选匹配的检验问题，基本框架通 过在可能匹配空间上的搜索来考虑复杂匹配的产生过程。为了对匹配空间 进行高效的搜索，应用了一个搜索单元的集合，即：s e a r c h e r s 。其中，每 个s e a r c h e r 都对所有可能的候选匹配进行检索，并得出一个与属性组合的 特殊类型相一致的候选匹配空间子集合。再对这个特殊的匹配空间应用基 于数据实例的匹配技术对候选匹配进行初步估价。 f 2 ) 开发利用域知识 目前很多研究已经注意到了应用域知识来进行 模式匹配的好处。尤其在候选匹配的过滤方面，域知识是非常有用的。而 对于复杂匹配，应用域知识将带来更大的益处。基本框架不仅能够利用域 知识来对一个目标匹配的精确度进行估价，同时还能够在搜索候选匹配阶 段应用域知识来修剪候选匹配，除了在集成约束和已有匹配的知识获取方 面应用域知识，基本框架应用了两种类型的域知识：首先，如果需要匹配 的数据库共享一些元组，那么它可以利用这些共享数据来发掘复杂匹配。 其次，它还利用了在域范围内的外部数据对候选匹配进行修剪。 ( 3 ) 解释匹配预测 由于模式匹配基本框架应用了多种高级匹配技术， 它们所需要做出的预测就会变得越来越复杂，同时，对于复杂匹配的决策 来说也就更加困难，这是因为对复杂匹配进行决策需要依赖于其它简单匹 配所做出的预测。因此，基本框架引入了一个新的特性，这个特性能够帮 第3 章模式匹配基本框架 助设计者与系统进行交互。此特性能够通过基本框架为用户提供个预测 匹配的解释单元，同时，用户还可以通过对一些基础解释进行判断，从而 得出最优匹配，并进行进步的反馈处理。 基本框架的体系结构如图3 - 1 所示。它由三个主要的处理单元组成： 匹配产生器、相似度估价器和匹配选择器。 】t l 和j 擎匹配 源模式s 和目标模式t 图3 - 1模式匹配基本框架的体系结构刚 f i g 3 - lt h eb a s i ca r c h i t e c t u r eo f s c h e m am a t c h i n g i 8 】 其处理过程概述如下：首先，匹配产生器把两个模式s 和t 作为输入。 对于t 中的每个属性t ，基本框架产生一个候选匹配的集合，其中包括1 ：1 匹配和复杂匹配。匹配检索器由一个检索器集合s e a r c h e r s 组成，每个检索 器都是对特殊类型或特殊域空间的候选匹配进行初步过滤和估价。检索器 产生出相对变小的候选匹配空间并进行初步估价后，相似度估价器再对候 选匹配进行进一步的估价，这个估价值显示了候选匹配对目标属性t 的相 一一 垄竺盔堂三堂堡主兰篁笙茎 似度。因此，这个单元的输出是一个矩阵，其中存储了 对的相似度估价值。最后，匹配选择器对相似度矩阵进行检验，并 输出最优匹配。 在整个匹配过程中，这三个单元还应用了域知识和外部数据来提高匹 配的精确度，并且与个解释单元进行交互来为匹配做出解释。 3 2 匹配产生器 匹配产生器最基本的思想是：在可能的候选匹配空间上反复执行候选 匹配发掘过程。匹配产生器利用一个特殊的检索器集合，每个检索器都是 根据特殊的组合操作符和属性类的知识，对搜索空间的一个特殊部分进行 搜索。 下面通过t e x ts e a r c h e r 和n u m e r i cs e a r c h e r ，对检索器进行简单的介绍。 t e x ts e a r c h e r 检索源模式中所有文本属性和并置属性的匹配空间，从而 来寻找与目标模式属性相匹配的匹配集合。并且，t e x ts e a r c h e r 应用试探法 集合来判断个属性是否是文本的。其中，试探法通过检查数字和非数字 字符之间的比率，和每个数据值的平均字词数目来判断一个属性是否是文 本的。 n u m e r i cs e a r c h e r 则利用数字属性值来检索匹配，而这些匹配往往是源 模式属性的一个代数表达式。 基本框架使用多个检索器的两大好处： ( 1 ) 每一个检索器都可以考虑候选匹配空间的一个更小的，更有意义的 部分。 ( 2 ) 可以很容易的对附加的检索器进行扩展。 3 2 1 检索器举例 下面对目前在基本框架中应用的检索器进行举例说明，如表3 - 1 所示。 这些检索器覆盖了各种不同类型的复杂匹配，如：文本、数字、范畴，等 等。并应用了各种不同的技术来对候选匹配进行估价，同时还应用了各种 1 4 第3 章模式匹配基本框架 类型的域知识，如：域约束和重叠数据等，实现对候选匹配的过滤。 表3 - 1 基本框架中的检索器 t a b 3 - 1t h es e a r c h e r so f t h eb a s i ca r c h i t e c t u r e s e a r c h e r s p a c eo f c a n d i d a t e se x a m p l e s e v a l u a t i o n t e x ta t t r i b u t e s 址t h e n a i v e b a y s t e x t n a m e = c o n ( f i r 甜- n a m e ，l a s t - n a m e ) s o u r c cs c h e m aa n db e a ms e a r e l l u s e rs u p p l i e dm a t c h e s b i n n i n g a n d n u m e r i c l i s t - p r i c e = p r i c e + ( 1 + t a x - r a t e ) o rp a s tc o m p l e xm a t c h e s k l d i v e r g e n c e a t t r i b u t e sw i t hl e s s c a t e g o r yp r o d u c t - c a t e g o r i e s2p r o d u c t - t y p e s k ld i v e r g e n c e t h a ntd i s t i n c tv a l u e s s c h e m as o u r c ea t t r i b u t e f i r e p l a c e = 1i fh o u s e - d e s c h a s k ld i v e r g e n c e m i s m a t c h c o n t a i n i n gt a r g e ti n f o“f i r e p l a c e u n i t p h y s i c a lq u a n t i t y p r o p e r t i e s o f w e i g h t - k g - - 2 2 + n e t - w e i g h t - p o u n d s a t t r i b u t e st h ed i s t r i b u t i o n s c o l u m n sr e c o g n i z e da s m a p p i n gi n t o d a t eb i r t h - d a t e2b - d a y b - m o n t h b - y e a r o n t o l o g yn o d e s a no n t o l o g y o v e r l a ps p e c i f i e db yac o n t e x t e q u a t i o n i n t e r e s t e a r n e d = b a l a n c e * i n t e r e s t - r a t e f l e eg r a m m a r o v e r l a pv e r s i o no f t h et e x t ，c a t e g o r y , s c h e m am i s m a t c ha n du n i tc o n v e r s i o ns e a r c h e r s 下面对这些检索器进行概括性的阐述： ( 1 ) n u m e r i cs e a r c h e r 此检索器中，计算数值分配相似度的评分值所使 用的方法是：k u l l b a c k l e i b l e rd i v e r g e n c em e a s u r e 【1 6 ，1 7 】。同时，检索器在检 验匹配类型时，考虑的不是任意的匹配空间，而是一个受限制的匹配空间， 例如，那些对源模式数字属性进行加、减、乘、除操作的组合属性。 f 2 ) c a t e g o r ys e a r c h e r 此检索器发掘范畴列属性间的转换映射。例如： w a t e r f r o n t = f ( n e a r - w a t e r ) ，其中f ( “y e s ”) = 1 ，并且f c “n o ”) = 0 。在给定一个目 标属性t 的情况下，检索器通过计算t 属性不同数据值的个数来决定t 是否 是一个范畴属性，其中不同数据值的个数必须在一个阈值范围内，目前这 燕山大学工学硕士学位论文 个阈值设为1 0 ，然后，检索器应用相同的技术，在源模式中搜索范畴列属 性，对源模式此类范畴列属性应用k u l l b a c k l e i b l e rd i v e r g e n c em e a s t t r e ，计 算出与目标模式属性t 的相似度，并选取相似度较高的作为候选匹配。 ( 3 ) s c h e m am i s m a t c hs e a r c h e r 此检索器所针对的模式丢失匹配指的 是：一个模式中列属性的数据值与另一个模式当中的属性名相匹配。例如： 如果源模式中的属性h