（计算机软件与理论专业论文）基于模式映射的异构数据集成模型研究.pdf

。_ _ _ 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 ll，1111 一o ， 原创性声明和关于论文使用授权的说明y 1 7 91 i i l l l l 1 u l111 1 1 1 1 1i i 81ii1 1i1 9 i i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：盘：鱼茔 日 期： 垄：垒：耋 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：煮鱼錾导师签名： e f - j 山东大学硕士学位论文 鲁i； i i i ii iini i ；i 皇曼皇曼! 曼曼曼曼皇曼曼曼曼曼毫曼! 曼曼曼曼量曼皇曼曼! 曼曼曼曼曼曼曼邑曼皇皇! 曼曼曼曼曼曼曼曼曼皇 目录 摘要i a b s t r a c t i i i 第一章绪论l 1 1 研究背景1 1 2 研究现状5 1 3 主要工作7 第二章r c m 模型介绍9 2 1 映射方法9 2 1 1g a v 9 2 1 2l a v 1 1 2 1 3g l a v 1 3 2 1 4r c m 映射方法1 4 2 2 映射描述一1 4 2 2 1 传统描述方法1 4 2 2 2 板映射文档1 6 2 3r c m 映射文档一1 7 2 3 1r c m 数据源描述1 8 2 3 2r c m 本体转化2 2 2 4r c m 冲突描述一2 3 2 4 1 冲突分类2 3 2 4 2 冲突初步描述2 5 第三章r c m 冲突发现与消除2 7 3 1 基于板映射模型的算法2 7 3 1 1 算法描述2 7 3 1 2 算法分析2 8 3 2r c m 中的冲突发现算法一2 8 3 2 1d e t e c t i o i l 算法2 8 3 2 2 算法分析3 0 3 3r c m 中的冲突消除算法一3 l 3 3 1 关系查询重写算法3 1 3 3 2 半结构查询重写算法。3 1 山东大学硕士学位论文 3 3 3s o l u t i o n 算法3 3 3 3 4 算法分析3 3 3 4 实验分析一3 4 第四章r c m 框架实现3 6 4 1 基本结构一3 6 4 2 主要模块j 3 7 4 3 数据源注册与发布3 8 4 3 1 数据源注册3 8 4 3 2 数据源发布3 8 4 4 数据源描述一3 8 4 4 1 数据源本体编辑3 8 4 4 2 数据源本体操作3 9 第五章总结与展望4 1 参考文献4 2 致谢4 7 攻读学位期间发表的学术论文目录4 8 一 ， _ 一 一 山东大学硕士学位论文 ii l l t a b l eo fc o n te n t s a b s t r a c ti nc h i n e s e i a b s t r a c t c h a p t e r1i n t m d u a i o n 1 1 1r e s e a r c hb a c k g r o u n d 1 1 2r e l a t i v er e s e a r c h 5 1 3m a i nw o r k 7 c h a p t e r2r c m d e s c r i p t i o n 9 2 1m a p p 吨m e t h o d 9 2 1 1g a v 9 2 1 2l a v 1 1 2 1 3g l a v 1 3 2 1 4m a p p i n gm e t h o do f r c m 1 4 2 2m a p p i n gd e s c r i p t i o n 1 4 2 2 1t r a d i t i o n a lm e t h o d 1 4 2 2 2m a p p i n gd o c u m e n t 1 6 2 3m a p p i n gd o c u m e n to f r e i n 1 7 2 3 id a t ad e s c r i p t i o n 1 8 2 3 2o n t o l o g yt r a n s f o r m a t i o n 2 2 2 4c o n f l i c td e s c r i p t i o n 2 3 2 4 1c o n f l i c tc l a s s i f i c a t i o n 2 3 2 4 2i n i t i a ld e s c r i p t i o n 2 5 c h a p t e r3c o n f l i c tf o u n d a n ds o l v e d 2 7 3 1 t r a d i t i o n a la l g o r i t h m 2 7 3 1 1a l g o r i t h md e s c r i p t i o n 2 7 3 1 2a l g o r i t h ma n a j y s i s 2 8 3 2c o n f l i c t f o u n da l g o r i t h m 2 8 3 2 1a l g o r i t h md e t e c t i o n 2 8 3 2 2a l g o r i t h ma n a l y s i s 3 0 3 3c o n f l i c t - s o l v e da l g o r i t h m 3 1 3 3 1a l g o r i t h mf o rr e l a t i o n a ld a t a 3 1 3 3 2a l g o r i t h mf o rs e m i - s t r u c t u r e dd a t a 3 1 3 3 3a l g o r i t h ms o l u t i o n 3 3 3 3 4a l g o r i t h ma n a l y s i s 一j j 3 4e 冲e r i m e n ta n a l y s i s 一3 4 c h a p t e r4f r a m e w o r ki m p l e m e n t a t i o n 3 6 4 1 f r 锄e w o r k ：3 6 42m 撕nc o m p o n e n t s 3 7 4 3r e 西s t e r dr e l e a s e 3 8 4 3 1d a t as o u r c er e g i s t e r 3 8 4 3 2d a t as o u r c er e l e a s e 3 8 4 4d a t es o u r c ed e s c r i p t i o n 3 8 4 4 1o n t o l o g ym o d i f i c a t i o n 3 8 4 4 2o n t o l o g yo p e r a t i o n 3 9 c h a p t e r5c o n c l u s i o n “4 1 i 沁f e r e n c e 4 2 a c k n o w l e d g e m e n t 4 7 硼始t h e s i sp u b l i s h e df o rt h em a s t e r sd e g r e e ：4 8 - - 山东大学硕士学位论文 摘要 随着各种企业级系统的快速发展和异构框架的不断丰富，将各种异构系统进 行的集成就成为当前数据库领域的一个热点问题。要实现系统集成就首先进行数 据集成，而基于本体的数据集成在各种数据集成方法中脱颖而出，成为目前数据 集成领域中的重要研究点。一般情况下，由于数据源的异构性和多样性，数据集 成中会存在各种各样的冲突，比如常见的命名冲突，单位冲突，顺序冲突等等， 所以必须首先发现冲突，然后按照人工的或者自动的冲突消除规则对冲突进行处 理。 鉴于上述考虑，本文利用本体的语义性，提出了一个基于模式映射的数据集 成模型，该模型构建于映射规则( r u l e - b a s e d ) ，并且能够自动发现和消除特定 的冲突( c o n f l i c t s o l v e d ) ，所以将其命名为r c g 。 本文首先对r c m 进行建模，该模型包含了局部概念集、全局概念集、映射集、 冲突集和约束集，其中后三者是该模型的核心。我们用映射文档的形式来对后三 者进行描述，然后在此基础上提出了一个冲突发现和消除的算法，最后阐述了r 嘣 框架的实现。 在数据源描述方面，每个局部数据源由它自己的本体来描述语义。但是为了 使每个源本体之间能够相互比较，在最上层建了一个共享的词汇集，共享的词汇 集包含了领域内基本的术语，即构建了一个代表全局数据源的本体，这样就涵盖 了r c m 模型中的局部概念集和全局概念集。在此基础上，用o w l 自定义的映射文档 对局部数据源与全局数据源之间的映射关系进行描述，从而将l i c m 中的映射集、 冲突集和约束集的信息记录到映射文档中。 本文研究了基于板映射模型的冲突消除算法和常用的查询重写算法，分析了 它们的部分不足之处，提出了适合在r c m 上进行冲突发现和消除的算法。在映射 文档中自动发现冲突并判断冲突发生的子数据源及对应的属性，并同时在映射文 档中进行修改。在查询重写的过程中，将借助该映射文档来消除以单位冲突和格 式冲突为代表的数据冲突和以命名冲突为代表的语义冲突，从而保证查询结果的 正确性。 本文最后介绍了由r c m 延伸出来的框架，具体包括用户接口、查询处理、 山东大学硕士学位论文 文档处理和结果提取四大部分，结合g l a v 、本体等技术的各自优势，提出了各 部分可行的实现方式。 关键字：数据集成；冲突消除；本体；模式映射 i 山东大学硕士学位论文 a b st r a c t w i t ht h er a p i dd e v e l o p m e n to fv a r i o u se n t e r p r i s es y s t e m sa n de n o r m o u s i m p r o v e m e n to fh e t e r o g e n e o u sf r a m e w o r k s ，h o wt oi n t e g r a t et h e s e sh e t e r o g e n e o u s a p p l i c a t i o n sb e c o m e s t h eh o t t e s ti s s u ei nt h ec u r r e n td a t a b a s ed o m a i n d a t a i n t e g r a t i o ns h o u l db ed o n eb e f o r et h ei m p l e m e n t a t i o no fa p p l i c a t i o ni n t e g r a t i o n t h e n t h eo n t o l o g y b a s e dd a t ai n t e g r a t i o ns t a n d so u tf r o mal a r g eq u a n t i t yo fi n t e g r a t i o n m e t h o d s a n dt u r n si n t oa ni m p o r t a n tr e s e a r c hp o i n ti nt h es p h e r eo fd a t ai n t e g r a t i o n i nt h eo r d i n a r yc o u r s eo fe v e n t s ，b e c a u s eo ft h eh e t e r o g e n e i t ya n dd i v e r s i t yo fd a t a s o u r c e s ，t h e r ea r ev a r i e t yo fc o n f l i c t si nt h ep r o c e s so fd a t ai n t e g r a t i o n , s u c ha s n a m i n gc o n f l i c t ，u n i tc o n f l i c ta n do r d e rc o n f l i c t c o n f l i c t ss h o u l db ef o u n df i r s t ，a n d w o u l db es o l v e dm a n u a l l yo ra u t o m a t i c a l l ya c c o r d i n gt os o m ep o l i c i e so rr u l e s i no r d e rt os o l v et h e s ep r o b l e m s ，w i t ht h eh e l po fs e m a n t i c so fo n t o l o g y , t h i s p a p e rp r o p o s e sas c h e m am a p p i n g b a s e dm o d e lf o rd a t ai n t e g r a t i o n t h i sm o d e li s c o n s t r u c t e df r o mm a p p i n gr u l e s ，a n dc a na u t o m a t i c a l l yd i s c o v e ra n ds o l v es o m et y p e s o fc o n f l i c t s ，s ow en a m e di tr c m , s h o r tf o rm a p p i n gr u l e - b a s e dc o n f l i c t s o l v e dm o d e l f o rd a t ai n t e g r a t i o n t h i sp a p e rf i r s tc o n s t r u c t sr c m , w h i c hc o n t a i n sl o c a lc o n c e p ts e t ，g l o b a l c o n c e p ts e t ，m a p p i n gr u l es e t ，c o n f l i c ts e ta n dc o n s t r a i n ts e t t h el a s tt h r e ei st h ec o r e o ft h em o d e la n dd e s c r i b e di nt h ef o r mo fm a p p i n gd o c u m e n t t h e n 锄e x t e n d e d a l g o r i t h mi sp r o p o s e dt od i s c o v e ra n ds o l v ec o n f l i c t s l a s ti ti l l u s t r a t e sh o wt o i m p l e m e n tt h er c m f r a m e w o r k i na s p e c to fd a t as o u r c ed e s c r i f ) t i o n , e a c hl o c a ld a t as o u r c ei sd e s c r i b e db yt h e s e p a r a t e do m o l o g yt os h o wi t ss e m a n t i c s i no r d e rt oc o m p a r et h ed i f f e r e n c e so f o n t o l o g i e s ，ac o m m o nv a c a b u l a r yi sm a d e ，w h i c hc o n t a i n sa l m o s ta l lt e r m si nt h i s d o m a i n i ti sb u i l ta st h eo n t o l o g yo ft h eg l o b a ls o u r c ea n dc o v e r st h el o c a lc o n c e p ts e t a n dg l o b a lc o n c e p ts e to fr c m t h e nm a p p i n gd o c u m e n t sa r ef o r m e dw i t ho w la n d u s e dt od e s c r i b et h em a p p i n gr e l a t i o n sb e t w e e ng l o b a la n dl o c a ls o u r c e s ，w h i c hc o v e r m a p p i n gs e t ，c o n f l i c ts e ta n dc o n s t r a i n ts e to fr c m i 山东大学硕士学位论文 t h i s p a p e rr e s e a r c h e st r a d i t i o n a lc o n f l i c t s o l v e da l g o r i t h m sa n dc o m m o n q u e r y r e w r i t i n ga l g o r i t h m s ，a n a l y s e st h e i rs h o r t c o m i n g sa n dp r o p o s e san e w a l g o r i t h mf o rd i s c o v e r i n ga n ds o l v i n gc o n f l i c t s i ts c a n st h em a p p i n gd o c u m e n t sa n d c o u l da u t o m a t i c a l l yd i s c o v e rc o n f l i c t sa n df i n dd a t as o u r c e sa n dc o n c e p t sw h i c hc a u s e c o n f l i c t s ，a n dt h e nm o d i f i e st h ei n f o r m a t i o no fc o n f l i c t si nm a p p i n gd o c u m e n t s i nt h e p r o c e s so fr e w r i t i n gq u e r i e s ，t h em o d i f i e dd o c u m e n t sw o u l db eu s e dt os o l v et h ed a t a l e v e la n ds e m a n t i cl e v e lc o n f l i c t sa n dg u r a n t e et h a tt h ef i n a lr e s u l ti sr i g h t ，s u c ha st h e u n i tc o n f l i c t ，r e p r e s e n t a t i o nc o n f l i c ta n d n a m i n gc o n f l i c t a tl a s t ，t h ef r a m e w o r ke x e n t e df r o mr c mi si n t r o d u c e d , w h i c hc o n s i s t so fu s e r i n t e r f a c e ，q u e r yp r o c e s s i n g ，m a p p i n gd o c u m e n tp r o c e s s i n ga n dr e s u l te x t r a c t i o n i t m e r g e st h ea d v a n t a g e so fg l a v , o n t o l o g ya n ds oo na n dg i v e sa na v a i l a b l e i m p l e m e n t i o no f e a c hc o m p o n e n t k e y w o r d s ：d a t ai n t e g r a t i o n ；c o n f l i c t ss o l u t i o n ；o n t o l o g y ；s c h e m am a p p i n g i 山东大学硕士学位论文 第一章绪论 1 1 研究背景 随着计算机科学技术的迅猛发展，计算机数据处理速度的不断提高和存储容 量的不断增大，企业或者组织所累积的数据也快速增加。数据的采集、存储、交 换和转发变得日益频繁而复杂，在这种情况下企业或者组织只有尽可能的实现资 源或者信息共享，才能更有效的为正确决策提供精准分析的数据支撑，籍此实现 业务的快速响应，进而推动业务价值的提升。由此可见数据共享对现阶段企业应 用的重要意义，也促使数据集成技术成为业内的关注热点。 7 图1 1 数据集成示意图 为了更有效地利用企业或者组织中所有的数据信息，需要从多个分布、异构 和自治的数据源中集成数据，同时还必须保持数据各自的完整性和一致性，然而 要达到上述目标并不是一件容易的事。首先，这些服务于各个应用系统的信息往 往呈现出不同层次的异构性1 。异构性按照层次来分可以有如下几种： 1 ) 系统级异构是指主机、操作系统或网络制式体系结构的不同； 黑国 裔蟛一 国一 山东大学硕士学位论文 2 ) 语法级异构是指数据类型、格式的差异； 3 ) 结构级异构是指数据结构、接口和模式上的不同； 4 ) 语义级异构是指在一定领域内专用的词汇意义的共享和交流时所表达 含义的不同，比如不同的信息源使用多种词汇表示同一概念；同一概念 在不同的信息源中表达不同的含义：各信息源使用不同的结构来表示相 同或相似的信息；各信息源中的概念之间存在着各种联系，但因为各信 息源的分布自治性，这种隐含的联系不能体现出来。 从数据的语义来说，异构性又可进行以下分类。数据模型异构1 4 8 1 是指数据 库管理系统本身的不同。例如数据交换系统可以是同为关系数据库系统的 o r a c l e ，s q ls e v e r 等作为数据模型，也可以是不同数据模型的数据库，例如关系、 层次、网络、面向对象或函数型数据库等。而逻辑异构【4 8 】贝u 包括命名异构、值 异构、语义异构和模式异构等。例如语义的异构具体表现在相同的数据形式表示 不同的语义，或者同一语义由不同形式的数据表示等。 同时这些数据或者信息往往存储在多个不同的数据源之中，经常出现一套应 用系统对应好几个数据源或者几套引用系统对应一个数据源，应用与数据之间对 应关系的复杂化也使数据的共享或利用的难度增大。 另外，从用户的视角来看，上述种种差异性都必须是透明的，所以要求集成 系统能提供给用户一个统一的数据访问接口。 由此就可以明确我们的研究目标，即在于确立一个操作性强的、可消除多种 冲突的分布异构数据源集成模型。下面本文将以具体的应用场景来阐述数据集成 中的种种困难以及要解决的问题。 以通讯运营商为例，集团规模庞大，业务地点分散，信息种类繁杂，就拿常 见的监理业务来说，就存在基站监理系统、核心网监理系统、传输网监理系统、 防火保温分项工程系统、工程资金结算系统、桩基土建系统和施工工艺检查系统 等。由于这些系统历史上可能并不是同时引进使用的，各种信息系统之间相互隔 离，所谓的“信息孤岛”现象普遍存在，各种资源信息不能共享，即使在同类的 系统中也可能存在大量的数据异构性，比如数据因为历史或者开发厂商的原因出 现了无法兼容或共享的现象。在这种背景下，监理业务工作的现状已不能适应信 息化的发展趋势，如何依据通讯运营监理企业信息系统数据特点，设计数据集成 2 山东大学硕士学位论文 的最优模式，通过数据集成来加强内控降低成本已经成为通讯运营行业提升管理 水平的迫切需要。 比如在基站监理业务中，存在以下2 个异构数据源s 1 和s 2 ，两者的数据模 式如图1 2 所示，只列出我们关注的属性。 数据源s l - - - ， o n s ： 数据源s 2 图1 2 异构数据源s l 和s 2 简略的数据模式 在上图中，数据源s 1 的b a s e s t a t i o n 代表基站，f l o w t r a f f i c 代表流量负 载( 以m 为单位) ，d a t e 代表监理日期( 格式为y y y y - m m d d ) ，i s k e y s t a t i o n 代 表是否是核心基站，而k e y s t a t i o n s 代表一个所有核心基站的视图，因为这组数 山东大学硕士学位论文 据在查询过程中经常用到，用视图定义出来可以减少查询过程的复杂性和查询语 句的复杂度。数据源s 2 的b a s e s t a ti o n s 代表基站组，b a s e s t a ti o n 代表某一个 具体基站，f l o w t r a f f i c 代表流量负载( 以g 为单位) ，d a t e 代表监理日期( 格 式为y y y y 砌 d d ) ，c o r e s t a t i o n 代表所有的核心基站。由于历史和监理厂商的 原因，s 1 采用关系数据库，s 2 采用x m l 数据库，所以两者描述数据的模式上有 着层次的不同。另外s l 和s 2 中的f l o w t r a f f i c 都代表流量负载，但是单位不同， 这种情形叫做单位冲突；d a t e 都是代表监理日期，但是所采用的格式不同，这 种情形叫做格式冲突；s 1 中的k e y s t a t i o n s 和s 2 中的c o r e s t a t i o n s 都是代表 核心基站，但是所采用的名称不一样，这叫做同义异名冲突。 当对这两个数据源进行联合查询的时候，由于数据库异构和数据模式异构的 存在，如果不解决上述异构性带来的冲突，就无法得到正确的结果。根据现实问 题的需要，本文将提出了一个基于映射规则和本体的数据集成框架，亟待解决如 下问题： 1 ) 使用哪种映射方法来保证使用以及维护局部数据源与全局数据源映射 关系的代价最小? 现存的映射方法有g a y 、l a y 、g l a v 和b a v 等等嵋1 ，该 采用或者扩展哪一种映射方式来构建r c m 才能在实现功能的同时保持最 小的代价? 2 ) 在采用基于本体的集成模型的情况下，如何选用合适的本体集成方法才 最适合上述场景? 目前的本体集成方式包括单本体方法、多本体方法和 混合本体方法等等m 。正确描述上述本体以及映射规则，是r 嘣模型的 基础目标。 3 ) 如何发现和消除上述冲突来保证查询重写算法的正确性? 如何定义冲 突并且在查询执行的过程中发现和消除冲突是保证最终结果正确的重 要条件。目前的查询重写算法有两大类，关系查询重写算法和半结构查 询重写算法钔，分别针对关系数据和半结构数据进行查询重写。如何扩 充查询重写算法来发现和消除局部数据源中存在的各种冲突? 4 ) 当查询执行的具体流程该如何安排? 当数据库采用不同的数据库的时 候，我们需要一个统一的访问接口来屏蔽数据库的异构性，这个接口与 数据库的层次关系该如何定义? 4 山东大学硕士学位论文 为了解决上述问题本文在g l a v 三元组( g ，s ，r ) 的基础上进行扩展成为由 本体描述的五元组( o c ，o i ，r m , r c ，r l ) ，具体来说，就是在传统的映射规则描 述中增加了描述冲突和约束的元素，既基于映射规则( r u l e - b a s e d ) ，又能够发 现与消除冲突( c o n f l i c t s 0 1 v e d ) ，因此我们将该模型称为r u l e - b a s e da n d c o n f l i c t s o l v e dm o d e lf o ri n t e g r a t i o no fh e t e r o g e n e o u sd a t as o u r c e s ， 简称r c m 。 1 2 研究现状 自从“异构数据集成”这个词被首次提出以来，涌现出多种数据集成方式， 按照时间顺序排依次是联邦数据库、数据仓库、中介模式以及新兴的a g e n t 模式 和p 2 p 整合机制，其中基于本体描述的中介模式是目前研究的焦点。 中介模式【1 6 1 ，即m e d i a t o r w r a p p e r 整合机制，如下图所示，是一种虚拟整合 方式，在基于这种模式的整合系统中，并不真正存储需要整合的数据资源，而是 通过m e d i a t o r 和w r a p p e r 来实现整合。m e d i a t o r 和w r a p p e r 均为中间件，位于用 户和数据源之间，m e d i a t o r 负责相应用户请求和整合查询结果，w r a p p e r 则负责 连接信息源的执行具体查询。同时，使用这种机制的整合系统能够有效地保持各 个异构信息源的自治性，满足局部应用的各自要求，并且能够充分发挥m e d i a t o r 的作用，满足集成系统的全局性要求。与以数据仓库为代表的物理整合机制相比， 中介模式不需要在本地储存大量的数据信息，因而能够适应松散耦合的网络环境 下信息源高度自治、分布广泛、更新周期短等特点，而且在m e d i a t o r 中引入 o n t o l o g y 等语义相关技术后，能够有效解决概念整合、冲突消除等问题。因而， m e d i a t o r w r a p p e r 整合机制成为目前实现数据集成的主流方式。 l ， 山东大学硕士学位论文 图1 3 中介模式结构图 局模式 g l o b a l ) 信息源模式 ( l o c a l ) 在中介模式中，数据集成可以看做由三个部分构成：全局模式、数据源以及 它们之间的映射关系。如果用i 表示一个数据集成系统，则i 可以形式化描述为一 个三元组( g ，s ，r ) 1 2 1 ，其中： g 是一全局模式，使用语言k 描述。l 。使用符号表凡；符号表凡中每个符号对 应g 中一个元素( 如果g 是关系型的，则其中每个元素就是个关系；如果是面向对 象的，每个元素就是一个类) ；s 是源模式，使用语言l s 描述。l s 使用符号表a s ； 符号表a s 中每个符号对应s 中一个元素；r 是g 和s 之间的映射关系，包含一组如下 形式的对应关系： q s - q 6 q g - - q s 其中，q s 和q g 分别是基于源模式s 和全局模式g 提出的查询。查询q s 使用 符号表魅上的语言l m , s ，查询q g 使用符号表a g 上的语言l m ，g 。直觉上来看， 一个映射q s - q g 含义就是源模式上的查询q s 对应全局模式上的查询q g 。反之， 即一个映射q g - q s 含义就是全局模式上的查询q g 对应源模式上的查询q s 。 6 山东大学硕士学位论文 随后在中介模式的基础上，出现了板映射模型【6 】，该模型能利用自定义的词 汇表和映射文档记录数据源之间的映射规则和冲突信息。“在基于本体的x m l 集成系统中，每个局部数据源都有一组映射规则，每一条映射规则描述了本体中 的概念到该数据源每个元素的映射信息，为全局模式到局部数据源的查询分解算 法提供了必要的查询转换信息。但是，由于此类映射规则并不记录各局部数据源 间的冲突，因此当局部数据源间存在冲突时，系统在处理局部数据源数据的连接 操作或者返回结果数据整合时，将导致连接失败或者整合结果错误。为了解决这 个问题，在传统的映射规则基础上进行扩展，使得每一条映射规则不仅描述本体 中的概念到该数据源每个元素的映射信息，还描述在这个概念上该数据源与其他 数据源的冲突信息。这种文档就被称为板映射文档。 在板映射模型中提出了一个简单的冲突消除算法【6 】，该算法描述如下：首先 任意选择一个子查询作为标准查询，得到它的互操作概念集：然后对每一个概念， 查找该子查询所在数据源的映射规则文档，如果这个概念对应的规则包含冲突属 性，则遍历每个冲突属性，找出冲突的数据源和转换函数，修改子查询。直到概 念集中的所有概念都处理完，算法结束。 该算法数据结构简单，实现起来比较容易，而且时间复杂度低，是一种比较 通用的冲突消除算法。但是缺点也比较明显，板映射文档中的冲突需要人工标注， 无法根据映射关系来自动发现冲突；解决的冲突类型比较少，而且均为数据冲突； 冲突描述不够灵活，不方便扩充。 另外，目前的查询重写算法有两大类，包括关系查询重写算法和半结构查询 重写算法n 副，分别针对关系数据和半结构数据进行查询重写。本文将基于板映射 模型的冲突消除算法与扩展的查询重写进行结合，提出了新的算法，能够自动的 发现和消除数据集成中的数据冲突和语义冲突。 1 3 主要工作 本文将从第2 章开始详细介绍r c m 模型的构成、所采用的冲突消除与发现算法 以及具体的框架实现。 第2 章将在中介模式的基础上，介绍r c i v l 的映射方法，所采用的数据源描述方 法，目前常见的冲突及其分类，并给出了在r c l v l 的映射文档中这些冲突该如何描 7 山东大学硕士学位论文 述。 第3 章首先介绍了基于板映射模型的冲突算法以及常见的查询重写算法，并 在此基础上借鉴r e w r i t e 算法n 朝的思想，提出了适用于r c m 的冲突自动发现与消 除算法。该算法可以适用于多种数据冲突与语义冲突的，并且通过实验证明其正 确性与可用性。 第4 章介绍r c m 框架的具体实现，其中包括4 大模块，包括用户接口、查 询处理、映射文档处理和结果析取，并且分别介绍了各部分的主要功能。 第5 章介绍对r c m 的总结和展望。 山东大学硕士学位论文 第二章r o m 模型介绍 本章首先介绍一下什么是r c m 及其映射方法，阐述了r c m 所采用的数据源描述 方法和目前常见的冲突及其分类，并给出了在r c l v l 的映射文档中这些冲突该如何 描述。 2 1 映射方法 r c m 在g l a v 三元组( g ，s ，r ) 的基础上进行扩展，所以可以将r c m 看做是由 本体描述的五元组( o c ，0 i ，r m ，r c ，r l ) 。具体来说，就是在传统的映射规则描 述中增加了描述冲突和约束的元素，既是基于规则映射( r u l e - b a s e d ) ，又能够 发现与消除冲突( c o n f l i c t s 0 1 v e d ) ，因此我们将该模型称为r u l e - b a s e da n d c o n f l i c t s o l v e dm o d e lf o ri n t e g r a t i o no fh e t e r o g e n e o u sd a t as o u r c e s ， 简称为r c m 。 2 1 1g a v g a v 方法是将各本地数据源的局部视图映射到全局视图，即全局模式被描 述为源模式上的一组视图。用户查询直接作用于定义在数据源模式上的全局视 图。在一个g a v 数据集成系统i ( qs ，r ) 中，映射r 将全局模式g 中每个元素g 关联到一个l 上的查询q s 。这样，一个g a v 映射是一组对应关系，其中每个映 射对应于g 中的一个元素一1 2 】： g q s 下面我们将通过一