（计算机软件与理论专业论文）集成系统中基于约束的xml查询重写方法研究.pdf

摘要 摘要 查询重写作为数据集成中的一项核心技术，在集成或发布系统中有重 要应用。随着i n t e r a c t 技术的发展，x m l 成为异构数据集成中的数据交换 的中间形式，针对x m l 模式作为全局视图的查询重写成为集成系统中研 究重点。本文在对国内外研究现状进行综合分析的基础上，对x m l 查询 重写进行了深入的研究。 本文主要研究了基于中间件结构体系的集成系统中的查询重写，以及 所涉及的技术和方法。 首先，分析了集成系统的体系结构以及所使用的重写技术，介绍了与 查询重写相关的查询语言、映射和视图定义语言，重点分析了算法使用的 映射语言的特点和蕴涵的约束信息。 其次，对采用x m l 作为公共数据模型的查询重写算法进行了深入探 讨，提出利用数据源和目标模式之间的映射关系生成映射规则，对用户查 询进行相应替换，得到针对各数据源的查询。 再次，为避免替换过程中产生不合理的查询，提出一种基于约束合并 的改进算法。将用户查询分解成若干子查询，利用映射规则进行相应替换， 根据约束条件进行有效的合并，得到最大被包含重写，以减少网络传输的 代价。同时可以保证生成的重写尽可能的少，从而减小时间和空间开销， 提高集成系统效率。 最后，结合自己的理论研究，设计了一个基于x m l 的异构集成系统 的原型系统，对其中主要模块使用的技术进行了说明，并通过实验验证了 文中所给算法的正确性和有效性。 关键词查询重写；数据集成；x m l ；中间件；约束 燕山大学工学硕士学位论文 a b s t r a c t q u e r yr e w r i t i n gi sac o r et e c h n o l o g yo fd a t ai n t e g r a t i o n ，a n dp l a y sa n i m p o r t a n tp a r ti ni n t e g r a t i o na n dp u b l i s h i n gs y s t e m s w i t l lt h ed e v e l o p m e n to f i n t e r n e tt e c h n o l o g y , x m lh a sb e c o m et h em e d i a t eo fd a t ae x c h a n g i n gi nt h e h e t e r o g e n e o u sd a t ai n t e g r a t i o n w em a k eac o m p r e h e n s i v ex m ls c h e m aa st h e g l o b a lv i e wo fq u e r yr e w r i t i n g o nt h eb a s i so fa n a l y z i n ga n ds y n t h e s i z i n gt h e a c t u a l i t yi ni n t e r n a la n de x t e m a l ，w er e s e a r c ho nt h ep r o b l e m so ft h ex m l q u e r yr e w r k i n gd e e p l y w em a i n l yi n v e s t i g a t et h eq u e r yw r i t i n gt e c h n o l o g yo fb a s e do nt h e m i d d l e w a r ec o n s t r u c t u r es y s t e m ，s o m et e c h n i q u e sa n dm e t h o d s f i r s t l y , w ea n a l y s et h ec o n s t r u c t u r co f i n t e g r a t i o ns y s t e ma n dt h er e w r i t i n g t e c h n o l o g y , t h e nw ei n t r o d u c eq u e r yl a n g u a g e ，m a p p i n gl a n g u a g ea n dv i e w d e f i n i t i o nl a n g u a g eu s e di nt h er e w r i t i n ga l g o r i t h m ，f u r t h e r m o r ea n a l y z et h e c h a r a c t i c so f t h em a p p i n gl a n g u a g ei nm a n yt y p i c a lq u e r yr e w r i t i n ga l g o r i t h m s s e c o n d l y w ep r o b ei n t ot h eq u e r yr e w r i t i n ga l g o r i t h m st a k i n gx m la st h e p u b l i cd a t am o d e l w ep r e s e n tt h em a p p i n gr u l e sa m o n gt h es o u r s ed a t aa n dt h e t a r g e ts c h e m a ，a n dt h e nw ec a nm a k es o m es u b s t i t u t i o n i nt h ee n d ，w ec a ng e t d i f f e r e n tq u e r yo fd i f f i c e n td a t ar e s o u r c e t h i r d l y , t o a v o i dp r o d u c i n gu n r e a s o n a b l eq u e r yi nt h ec o u t s eo f s u b s t i t u t i o n ，w ep r e s e n t a n i m p r o v e da l g o r i t h m b a s e do nc o n s 仃a i n t d e c o m p o s et h ed a t ar e s o u r c ei n t om a n ys u b q u e r i e sa i m e d a tt h eq u e r yo f t a r g e t s c h e m a i nt h ec o n r s eo fs u b s t i t u t i o no fm a p p i n gr u l e s ，w ec a nu s et h e c o n s 仃a i n tc o n d i t i o na n dm a k ear e s e a n a b l ea m b i n a t i o nt o g e tm a x i m a l l y - c o n t a i n e dr e w r i t i n g s ，p r o d u c ef e w e rq u e r i e st or e d u c et h et i m ea n dt h es p a c e c o s t e da n dt oi m p r o v ee f f i c i e n c yo f t h ei n t e g r a t i o ns y s t e m f i n a l l y , w i t ho b rt h e o r e t i c a lr e s e a r c h , w ed e s i g nap r o t o t y p eo ft h e n a b s t m c t x m l b a s e dh e t e r o g e n e o u sd a t ai n t e g r a t i o ns y s t e m ，a n da sf o re a c hm o d u l e ， d e s c r i b e st h et e c h n i q u e sa n da l g o r i t h m su s e db yt h e s em o d u l e sa tl e n g t h i nt h e e n d ，t h ec o r r e c t i t u d ea n de f f i c i e n c yo ft h ea l g o r i t h m sa r ev a l i d a t e db yo u r e x p e r i m e n t s k e y w o r d sq u e r yr e w r i t i n g ；d a t ai n t e g r a t i o n ；x m l ；m i d d l e w a r e ；c o n s t r a i n t 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文集成系统中基于约束的 ) 。“l 查询重写方法研究，是本人在导师指导下，在燕山大学攻读硕士学 位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部 分外不包含他人己发表或撰写过的研究成果。对本文的研究工作做出重要 贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完 全由本人承担。 作者签字 纠以铲 日期：7 0 0 碑月勿日 燕山大学硕士学位论文使用授权书 集成系统中基于约束的m 。查询重写方法研究系本人在燕山大 学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成 果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关 人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校 保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。 本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以 公布论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密 ( 请在以上相应方框内打“4 ”) 作者签名：二i 房久分 日期：沙p 万年月他日 导师魏d 、ll 诉 日期：弼年p 县。日 第1 章绪论 1 1 研究背景 第1 章绪论 随着计算机技术特别是网络技术的发展，许多行业、单位和部门逐步 实现了业务、信息的计算机管理。但是，由于具体业务和功能归属不同， 它们都只是根据自身需要构建了许多相互独立的信息服务和管理系统，甚 至在一个单位内部所采用的信息化环境不会固守一个平台，而是由不同平 台组成。这样随着时间的推移和技术的进步，这些由不同技术构建的信息 系统就象一个个“信息孤岛”，各自有着不同的处理对象、操作方法和专用 客户端。从应用角度来看，每个部门就是一个数据源，因为他们之间的信 息和组织都不一样，这样每个数据源又都是异构的，因此就构成了一个巨 大而复杂的异构数据环境。而由于部门之间协同合作的需要，在各个环节 之间数据交流以及集成共享的问题也日益严重起来。 当处理存储在不同的地点、不同的模式甚至是不同的类型的数据时， 数据互操作问题成为焦点。数据互操作粗略地分为数据交换和数据集成。 数据交换是把异构的数据从一个或多个数据源类型移动或重构成新的目标 类型，在转换过程中不需要建立公共数据模型，这种方式对于不需要频繁 更新的历史数据是比较有效的，而对于实时更新的数据这种方式的转换和 传输的代价很大，就要用到另一种数据互操作形式数据集成。数据集 成则需要公共模式来进行转换，也就是为用户提供一个异构数据源的统一 接口。只有将这些孤立的数据都集成起来，并且提供给用户一个统一的视 图，才有可能从巨大的数据资源中获取所需的东西。而数据集成中的核心 技术就是查询重写，查询重写技术是数据库研究的一个基本问题，在查询 优化、数据仓库、数据集成、语义缓存等问题有广泛的应用。 随着x m l 成为数据交换和表示的标准，越来越多的系统使用x m l 数 据作为传输和表示的形式。在数据集成系统中，越来越多地采用x m l 作 燕山大学工学硕士学位论文 为全局数据模型来进行查询重写。在某些领域的数据库中，数据分别存储 在各自的数据库中，由集成系统进行信息集成。在其中一个数据库中存放 形态信息，而在其它数据库中存放其性质等信息。在后续研究中又会加入 一些新的相关数据库。而基于视图的数据集成系统的扩充困难川，加入新 的数据库就得重新建立视图和映射。现在利用x m l 作为集成系统的数据 源，并利用映射来建立目标模式，有效地解决了这个难题，使得集成系统 具有模块化结构，扩充容易。同时利用映射也可以灵活方便将新数据源加 入到目标模式中，用户只针对目标模式提出查询，由查询重写模块对查询 进行处理，将其分解为针对各数据源的查询。 1 2 国内外研究现状 查询重写算法的基本思想就是搜索所有可能的重写，然后将合格的重 写加入结果集中。x m l 及半结构查询重写是一个n p 问题1 2 】，在处理过程 中要考虑到完备性。目前研究的方向主要集中在如何高效快速完成重写过 程和如何利用视图尽可能多的回答查询。 m a r s 发布系统 3 1 处理的是x m l 和关系混合模式，在向缓存视图和 索引等冗余存储的发布方案中，对x m l 查询进行重写。文献【4 】和【5 1 提出 根据已生成的视图通过重写半结构查询来优化查询。x p e r a n t o 【6 1 和 s i l k r o u t e 7 1 系统是在x m l 发布s q l 数据过程中实现了对x m l 查询到s q l 查询的重写。 上面介绍的查询重写是等价重写，也就从数据源或视图映射到目标模 式或视图是没有损失的，映射包含的信息表明了x m l 视图中的信息等价 于关系数据存储的信息。而在数据集成系统中数据源的信息不完整，这种 数据源的不完备性导致了查询熏写方法的不同，此时考虑的是最大被包含 重写问题。考虑到数据源和它们的映射提供的是一种不完全、部分的视图， 如何处理这个问题也是设计可伸缩数据集成系统的要求。即源模式中的某 一部分是目标模式的某一部分的子集。在这种情况下要得到带有约束的重 写或如有可能得到最大被包含重写是有一定难度的【引。 2 第1 覃绪论 集成系统中的查询重写主要考虑的是最大被包含重写问题。针对这一 问题，提出了很多信息集成的体系结构和实现方案。这些方法研究的主要 对象是传统的异构数据库。随着w e b 技术的发展，x m l 成为信息传播和 交换的形式。这种基于x m l 的数据集成系统成为新的研究领域。 信息集成系统的方法可以分为数据仓库和w r a p p e r m e d i a t o r 方法【9 】。 其中数据仓库是按需要的全局模式从各数据源中进行抽取转换并放入数据 仓库中。因其更新以及目前数据源数量大且不固定等原因，使得这种方法 在集成系统中使用的不多。而w r a p p e r m e d i a t o r 是典型的处理异构信息的 集成体系结构【l ”。m e d i a t o r 组件包括由各数据源映射成的全局视图或模 式，以及针对这种全局视图或模式的查询处理机制。这部分的作用是将针 对全局视图或模式的查询转换成对各数据源的查询。目前许多集成系统采 用的就是这种方式。 目前，数据集成技术或多或少地存在一些不足f 12 1 ，如下所示。 ( 1 ) 全局模式同各数据源模式的转换工作繁杂； ( 2 ) 对结构化数据的支持较好，而对半结构化和非结构化数据不够重 视，数据源参与集成的程度不高，一般将这些数据转换为结构化数据进行 处理： ( 3 ) 查询处理效率低、数据传输量大，查询子目标过小，频繁进行数据 传输； ( 4 ) 不能解决多平台的异构性、缺少灵活性、不能实现数据的远程操作。 针对以上不足和x m l 数据或关系数据的特点，充分利用生成全局或 目标模式的映射关系，在集成系统中进行查询重写是一种新的方式，这种 方式能有效提高系统的伸缩性，有利于对重叠数据进行合并。映射出的模 式可以独立设计。新增数据源可以很方便加入到目标模式中。为适应x m l 数据集成中大规模数据集成应用需要，有些系统采用映射进行查询重写。 有的使用简单的路径映射方法直接在模式的各元素间建立起对应关系。可 以提高系统的易用性和灵活性。但这种方法由于打破了实体各属性之间固 有的联系，可能会生成一些不合理的子查询。对这种方法的改进是利用启 发式规则来判断当前依赖与p c 环境之间的一致性 1 3 】，对映射能否替换全 燕山大学工学硕士学位论文 局查询中的元素进行判断。这种方法具有一定的灵活性，而用模式结构来 判断属性之间的联系过于严格，有可能得不到相应的查询。在x y l e m e 系 统中以增加重写开销为代价使用q u e r yr e l a x a t i o n 技术来判断属性之间的 联系。 文献 1 4 和 1 5 】提出一种基于本体的x m l 数据集成方案，该方案使用 本体来描述全局模式，用路径到路径的映射将x m l 数据源描述为全局模 式之上的视图，提出了单数据源的最大绑定算法和生成查询计划的算法。 但算法得到的计划既不是最大计划，又不是优化的计划。文献 1 6 对以上 方案进行完善，提出了为用户找到尽量完整的结果集的最大查询执行计划 的生成算法，算法基本思想是对于查询树的每个图的边进行单独处理，即 对每个覆盖该边的数据源执行原子查询析取并构成查询子计划，然后对所 有的边的查询子计划进行连接，构成最后的查询计划。并且提出了基于网 络代价的优化算法。 以上两种方法利用映射将数据源映射成基于本体的模式，将查询根据 生成的模式和映射进行分解。本文采用的方法是用一种新的映射语言将数 据源映射成一目标模式，利用目标模式、映射集和数据源对查询进行重写。 同时提出了基于映射替换的查询重写算法，这个算法首先根据映射产生若 干映射规则，用这些规则进行下一步的替换工作；对用户查询进行替换， 最后生成若干候选查询；然后对这些候选查询进行优化，使其达到最小， 没有冗余。而查询分解算法使用约束条件来对存在重复的多个数据源的相 关信息进行合并，形成统一的视图。算法中人为的映射规则和替换规则较 多。替换过程中会产生大量不合理的查询。 目前，国外一些公司和研究机构己经研究出了若干通用的数据源集成 系统【l m ”。其中比较具代表性的有：m i c r o s o f t 公司研制的o l ed b 、i b m 公司a l m a d e n 研究中研制的g a r l i c 、美国斯坦福大学和i b ma l m a d e n 研究 中心联合开发的的t s i m m i s 、l o r e ( l i g h t w e i g ho b j e c tr e p o s i t o r y ) 以及 o z o n e 等；i n f o r m a t i o nm a n i f o l d 、a d d s ( a m o c od i s t r i b u t e dd a t a - b a s e s y s t e m ) 、d a n 垤l e x ( g e n e r a lm o t o r s ) 、i n o r e s s t a r 、m e r m a i d 等。 国内也有一些单位参与了异构数据源集成工作的研究。主要有：东大 4 第1 章绪论 阿派股份有限公司的r d b m so p e n b a s e ；还有清华大学研制的c i m s 系统 中使用了异构数据库的互操作，但不具有全局数据库模式的概念；东南大 学研制了联邦数据库管理系统，主要实现了o r a c l e 、i n g r e s 、d b a s e 三者之 间的数据接口等；北京理工大学的u u h d b 系统是基于c s 结构的异种数 据库联合使用系统。 这些系统根据系统所使用的数据库类型、所采用的视图以及使用的全 局数据类型不同采用不同的查询重写算法，现对一些典型系统和算法比较 如下。 ( 1 ) a g o r a 系统a g o r a 系统圈中的查询重写采用模块化x m l 视图来处 理关系数据和x m l 数据，而用户的查询采用x q u e r y 表达式。虽然x m l 作为全局数据类型，但x m l 数据却要转化为关系模型，并将x q u e r y 查询 转换成标准的s q l 查询来进行查询分解和查询优化。该系统主要根据关系 模式来进行映射，x m l 转化为关系数据又比较复杂，用户很难理解和定义。 ( 2 ) x y l e m e 系统这是一个基于数据仓库解决方案的x m l 数据集成系 统【l ”。在这个系统中，数据源没有转换成统一的类型，查询是通过不同的 视图进行的，每个视图由一个抽象d t d 产生，抽象d t d 由数据源根据路 径到路径的映射规则产生的。这种映射规则与b ( q ，s ) 算法使用的规则相似， 不同之处是x y l e m e 系统采取的是完全映射，也就是数据源从文件的根开 始映射出的抽象d t d 对应的也是d t d 的根元素。 ( 3 ) m a r s 系统它是基于x m l 的发布系统【3 】，主要处理的是x m l 数 据和关系类型数据。采用l a v 和g a v 混合类型作为中间视图。在算法中 考虑了x m l 和关系数据的集成约束。 除了这些系统外，还有一些典型的算法。 ( 1 ) b u c k e t 算法m a n i f l o d 系统采用此算法【2 3 1 ，系统采用局部视图来进 行查询重写。用关系模式来描述逻辑类层次形式的全局视图，其中数据源 也采用关系视图。根据全局视图和数据源视图重写连接查询。算法独立检 查每个查询的子目标来进行查询重写，由于子目标的独立造成一部分查询 丢失。这个算法的完备性是经过证明的，每个桶保存的是查询子目标到视 图子目标的映射。 燕山大学工学硕士学位论文 ( 2 ) m i n i c o n 算法m i n i c o n 算法从性能的角度研究关系查询重写问 题，其基本思想刚是减少子目标匹配的重复性工作，尽早裁剪不必要的搜 索分支。也就是在查询子目标之间使用输入输出依赖，减少搜索产生所有 可能的重写的空间。这个算法提高了b u c k e t 算法及以前的算法的执行效 率，并具有很好的可伸缩性。文献 2 5 将m i n i c o n 算法的思想应用到半结 构查询重写中，用o e m 表示数据，基于t s l 查询语言，从理论上分析了 算法的效率。并研究了关系查询重写中没有的对象标识符依赖、集合值变 量的映射以及包含映射等方面的问题，并提出了相应的解决方案。 ( 3 ) b ( q ，s ) 算法b ( q ，s ) 算法【2 6 】与m i n i c o n 算法类似，在查询分解时 使用查询变量的父亲孩子依赖关系。将x m l 的树型结构描述成具有更强 概念模式的局部视图。 ( 4 ) 基本查询重写算法基本查询重写算法【2 7 采用基于x m l 模式之间 的映射这种技术，扩展了以前用视图进行查询重写的关系技术，并且可以 处理不同的复杂类型和查询以及关系中没有的层次结构。重写过程中会出 现许多不合理的查询，而且不能处理具有不同值的同名的数据。 1 3 本文研究内容 异构数据集成系统的目的是将来自不同的、异构数据源的数据集成到 一起，为用户提供个统一的查询界面和查询手段，以便于能够透明地对 这些数据进行访问和操纵。其中的关键是如何以一种统一的数据模式描述 各数据源中的数据，屏蔽它们的平台、数据结构等异构性，实现数据的无 缝集成。 w 3 c 制定的x m l 及针对x m l 的x q u e r y 查询标准为解决这个问题提 供了新的契机。x m l 除具有内容的自描述性、跨平台性、内容和显示分离、 可扩展性等特点外，它还具有强大的数据表达能力，不仅可以表达关系模 型和面向对象模型的数据，而且还可以表达不规则的、易变的数据。所有 这些都使x m l 为异构数据间的访问和交换提供了一种新的模式，使统一 描述各种格式的数据成为可能。可以预见，x m l 很可能成为一种新的数据 6 第1 苹绪论 互操作的标准。同时，基于x m l 的各种技术不断涌现，其中x q u e r y 已经 成为x m l 查询语言的事实标准，正获得人们越来越多的认可，使用它可 以对以x m l 表示的任何数据进行查询处理。 本文针对应用领域中的数据集成的方法进行了研究。在已有的目标模 式和映射集的基础上，结合数据源，针对目标模式的查询进行查询重写。 重写算法利用映射中包含的针对数据源的查询和针对目标模式的查询等信 息，产生一些替换规则，对查询进行相应替换，从而得到含有各数据源的 查询。这种方法适用于各数据源间含有重复信息的数据集成，并具有很好 的扩展性，每个数据源映射到全局模式中的一部分，可以适应集成系统的 发展的需求。 提出的利用约束进行子查询合并的算法有效地提高查询重写的效率， 对于查询的每个路径构成子查询进行单独处理，使用x m l 蕴涵的约束信 息以及映射中含有约束信息将子查询合并成最大被包含重写查询，以满足 集成系统的要求。利用全局模式把用户查询分解成独立的子查询，可以处 理用户查询中使用的通配符，并且可以增大用户查询的自由度，而一般系 统中用户的查询有严格的限制。算法可以依据全局模式补全查询路径，并 搜索所有可能路径。 1 4 本文结构 本文共5 章，从第2 章起，内容组织如下。 第2 章分析了典型集成系统的体系结构，介绍查询重写使用到的相关 技术，其中包括x m l 、查询语言x q u e r y 和几种视图定义语言。 第3 章分析查询重写算法所用到的目标模式、映射和查询的特点以及 表示方式。并用规范实例对查询进行应答，重点分析了其中使用的合并技 术。 第4 章根据映射语言的特点提出了基于映射替换的重写方法，利用目 标模式和映射产生替换规则，对查询进行替换：在这个算法的基础上提出 利用映射中的约束条件对算法进行改进，使得产生的候选查询相应减少。 7 燕山大学工学硕士学位论文 并对算法进行了分析。 第5 章对上面的算法进行了实验验证，并分析实验结果，最终得出相 关结论。 最后，对全文进行总结，并对未来进行展望。 第2 章集成系统概述 第2 章集成系统概述 信息系统集成技术已经历了2 0 多年的发展过程，研究者已提出了很多 信息集成的体系结构和实现方案，然而这些方法所研究的主要集成对象是 传统的异构数据库系统，随着e q t e m c t 的飞速发展，网络迅速成为一种重 要的信息传播和交换的手段，尤其是在w e b 上有着丰富的信息资源。如何 获取这些有用数据并加以综合利用，成为一个广泛关注的研究领域构 建w e b 信息集成系统。 信息集成系统中使用的方法可分为数据仓库方法和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 方法，也就是中间件法。这种方 法通过中介模式将各数据源的数据集成起来，而数据仍存储在数据源中， 由中介模式对针对全局视图的查询进行查询重写，分解为针对各数据源的 查询。包装器的作用是将针对数据源的查询转换为基于各局部数据源的模 式查询，由各数据源的查询执行引擎对数据源进行查询，查询结果再返回 包装器转换成相应形式，送回中介器进行结果合并返回给用户。 中介模式基于视图的查询重写根据视图的类型主要有三种形式 2 8 , 2 9 ： g a v ( g i o b a l - a s - v i e w ) 方法，用户查询直接作用于定义在数据源关系上的全 局视图，其特点是全局模式根据数据源模式动态生成，这种方式下的查询 分解简单；l a v ( l o c a l a s v i e w ) 方法要求为每一个数据源的查询给出一个 对全局视图的查询，这种方法利用全局谓词集合描述多个数据源内容视图 和用户查询，当给定某用户查询时，中间件系统通过综合不同的数据源视 9 燕山大学工学硕士学位论文 图决定如何回答查询，这种方法查询分解较复杂；g l a v ( g l o b a l - a n d l o c a l a s e w ) 方法是前两者的综合，一般用于特殊关系数据交换系统中， 有利于说明x m l 模式与用于查询引擎的语句之间的语义。 典型的数据集成系统由全局模式、数据源以及它们之间的映射构成， 全局模式呈现给用户一个虚拟的全局数据库的概念，映射集描述了全局数 据库和数据源之间的联系，是查询重写( 分解) 的重要依据。 2 1 集成系统体系结构 从体系结构实现的角度出发，信息集成技术经历了如下发展阶段 9 1 ： 单个的联邦系统、基于组件的分布式集成系统和基于w e bs e r v i c e s 的信息 集成系统。从体系结构的发展可以看出查询重写技术的发展，下面简单介 绍三种体系结构。 2 1 1联邦系统 联邦数据库系统( f e d r a t e dd a t a b a s es y s t e m ，f d b s ) 是由参与联邦的半 自治的数据库系统组成【3 0 】，目的是实现数据库系统间部分数据的共享。联 邦中的每个数据库的操作是独立于其它数据库和联邦的。之所以叫“半自 治”是因为联邦中的所有数据库都添加了彼此访问的接口。 联邦数据库系统又可分紧耦合f d b s 和松耦合f d b s 两种。 紧耦合f d b s 有一个或几个统一的模式，这些模式可通过模式集成技 术半自动生成，也可通过用户手工构造。要解决逻辑上的异构，就需要领 域专家决定数据库模式间的对应关系。由于模式集成技术不易添加或删除 联邦数据库集成系统中的数据库，所以紧耦合f d b s 通常是静态的，且很 难升级。 松耦合f d b s 没有统一的模式，但它提供了一些查询数据库的统一语 言。这样f d b s 中的数据库更具有自治性，但必须由用户解决所有语义上 的异构。由于松耦合f d b s 没有全局模式，所以，每个数据库都要创建自 己的“联邦模式”。f d b s 中实现互操作“最常用的”方法是将每个数据库 l o 第2 章集成系统檄述 模式分别和其它所有数据库模式进行映射。 如图2 1 所示例子中，这样的联邦数据库中需要建立n x ( n 一1 ) 个模式 映射规则。当参与联邦的数据库很多时，建立映射规则的任务变得不可行 了。所以，联邦数据库集成系统适合于自治数据库的数量比较小的情况， 而且，希望数据库能够保持“独立”，允许用户单独查询，数据库间能够彼 此联合回答查询的情况。对于网络上越来越丰富的数据源，f d b s 显然不 是一个很好的解决方案。 图2 - 1联邦数据厍系统体系结构示例 f i g 2 - 1a ne x a m p l eo f t h ea r c h i t e c t u r eo f f d b s 2 1 2 分布式集成系统 异构分布式数据库系统是一个逻辑上完整而又具有站点自治性，物理 上分散在若干台互相连接着的计算机上的、具有相同或不同数据模型的数 据库系统。在异构分布式数据库系统中，不同节点上的数据库系统具有独 立性、自治性和分布透明性，用户对任何数据库的操作就如同在本地执行， 不必关心其数据模型、物理位置等细节，它屏蔽了各种数据库在物理上和 逻辑上的差异，使用户用自己所熟悉的一种数据操作语言就能够操纵任一 种数据库。 目前，在实现异构分布式数据库系统体系结构口8 l 上可以有以下三种方 法。 第一种是对各种异构型数据库都建立用户交互接口，不进行任何模式 熬山大学工学硕士学位论文 的集成。这种方案简单易行，但用户无法透明地访问数据，并且当增加一 种新的异构数据库时，必须增加用户接口，非常烦琐。 第二种是在各成员数据库之上建立一个全局模式，从而对整个系统实 施统一控制。该全局模式由所有成员数据库模式集成，当这种全局模式建 立好之后，就可以针对不同的数据库进行统一的访问。 第三种是采用联邦数据库系统f d b s ( f e d e r a t e dd a t ab a s es y s t e m ) ，不 采用全局模式，在维持局部成员数据库自治的前提下，对异构的成员数据 库进行部分的集成，提供数据的共享和透明的访问。 一个典型的基于中间件的集成系统如图2 2 所示。 图2 - 2 基于全局模式的集成系统 f i g 2 - 2i n t e g r a t i o ns y s t e mb a s e do nt h eg l o b a ls c h e m a 目前用的最多的是第二种方法，也就是基于中间件的集成系统。除了 用户界面和数据源都可以看成中间件。查询用x q u e r y 形式，用户提出的查 询被转换为系统内部表示形式，再由重写模块处理。将查询分解为针对各 第2 章集成系统概述 个数据源的查询，然后由包装器进行转换，送到各数据源查询引擎进行查 询。由中间件来处理用户查询，屏蔽数据源的异构性，提供给用户一个使 用多种数据源的统一接口。 2 1 3 基于w 曲s e r v i c e s 信息集成系统 i n t e m e t 的迅速普及和广泛应用对计算机技术的发展产生了深刻的影 响，桌面应用正在向网络应用转移，从网上获得的不仅是信息，还包括程 序和交互式应用( 也就是服务) ，操作界面将在浏览器层面上得到统一，兼 容性由网络标准技术实现，使用一组w e bs e r v i c e s 协议，构建信息集成系统。 对每个数据源都为其创建一个w e bs e r v i c e ，然后使用w e b 服务定义语言向 服务中心注册。当要构建一个新的集成应用时，集成端首先向注册中心发 送查找请求，收集并选择合适的数据源，然后通过s o a pf s i m p l eo b j e c t a c c e s sp r o t o c 0 1 ) 协议从这些数据源获取数据。这种方法克服了上述两种方 法的缺陷，具有完好封装、松散耦合、规范协议和高度的集成能力等特性。 因此，基于w e bs e r v i c e s 的信息集成方案是构建w e b 数据集成系统较为理想 的体系结构。 从上面的体系结构中可以看到，要实现一个异构数据集成系统，必须 考虑以下技术问题。 ( 1 ) 公共数据模型公共数据模型就是数据集成系统中包装器对于各数 据源的包装形式。关于公共数据模型，首要的一点就是它应该能够方便地 描述各种数据源的数据，包括半结构化数据。从该意义上说，具有自描述 特征的数据模型比较适合，它的元数据附着在数据上，不仅能够方便地表 示结构化或半结构化数据，而且允许各种异构数据并存，是通用异构数据 源集成系统较为理想的公共数据模型。 ( 2 ) 全局视图定义及全局查询语言全局视图是用公共数据模型定义 的视图。全局查询语言应该包括数据定义语言和数据操纵语言。由于集成 系统采用具有自描述特征的公共数据模型x m l ，各数据源的数据事实上是 以半结构化的形式参与集成，所以全局查询语言以半结构化数据查询语言 为主。 燕山大学工学硕士学位论文 f 3 ) 全局数据字典 全局数据字典为异构数据集成系统提供必不可少 的元数据，并帮助用户构造有意义的查询，同时保证全局查询分解和优化 的顺利进行。 ( 4 ) 查询分解及翻译 用户发出的全局数据查询请求被分解成对各数 据源的子查询，再由相应的包装器完成局部查询。而且由于各数据源的查 询语言与全局查询语言可能有较大的不同，因此分解出的子查询必须翻译 为各数据源的查询语言。 f 5 ) 查询优化查询优化的目的是为了提高查询效率。网上的传输速度 是制约查询效率的关键因素，而各数据源的查询方式、速度的不同又使处 理变得更为复杂。所以对于涉及到多个数据源的连接查询，提高处理效率 显得尤为重要。 ( 6 ) 查询结果处理对于来自各数据源的局部查询结果要进行汇总，并 按一定格式进行存储和显示。 2 _ 2 视图定义语言 传统的数据集成技术一般都建立在模式集成的基础上，主要用于集成 具有模式的数据源。所以以往异构数据源集成系统( 例如联合数据库系统) 通常采用关系或对象的数据模式作为全局模式。然而，事实上许多数据源 是没有显式模式或模式无法预知，例如有些数据源会包含一些非结构化的 和半结构化的数据，像图像文件和h t m l 文件等。由于未能提供一种通用 的数据集成途径，面对不断出现的新数据源，传统的数据集成技术显得无 能为力。针对全局模式和全局数据模型的不同，提出了许多视图定义语言。 2 2 1 树查询语言t s l 在处理半结构化数据时，一般采用o e m ( o b j e c te c h a n g em o d e l ) 数据模 型来表示半结构化数据，作为全局数据类型。用t s l ( t r e es p e c i f i c a t i o n l a l l g l l a g e ) 作为查询语言和视图定义语言【3 l 】，在t s i m m i s 系统中使用的就 是这种语言，利用类似d a t a l o g 规则形式来定义查询。 第2 章集成系统概述 t s l 查询语言采用d a t a l o g 的形式，易于重构。一个查询是一个规 则，分为规则头和规则体，以：一隔开。规则头定义结果图中的结果对象， 其中出现的变量称为头变量，而规则体包含数据源满足的条件，其中的变 量称为体变量。对于头相同的多个t s l 规则可以合并起来，形成新的查询。 规则体中所有集合型值域最多含一个对象模式的t s l 查询称为规范化t s l 查询。如果t s l 查询规范化后仅含一个子目标，则称单路径查询。如果 t s l 查询的头是一个单路径子目标，称该查询为单路径头查询。任意一个 t s l 查询均可分为若干单路径头查询。规则头中所有变量都在规则体中出 现的t s l 查询称为安全t s l 查询。 例1 ：t s l 查询定义 f ( p ) f e m a l e ) ) ： d b 。 上述查询表示在数据源d b 含有以对象标识为p ，标签为p e r s o n ，其值域 为对象模式的集合，对象模式集合中包括以g 为对象标识，g e n d e r 为标签， 以f e m a l e 为值的数据，和包括以x 为对象标识、y 为标签，以z 为值的数据。 查询结果是以f ( p ) 为对象标识、以f e m a l e 为标签、值为对象模式，包括以f ( x ) 为对象标识、y 为标签、以z 为值的数据。 查询重写需要在查询和物化视图中建立映射，映射是查询子目标和视 图子目标建立的关联。由于映射是一一对应的，为方便建立映射，首先对 视图进行规范化操作，规范化的视图是指在视图定义中，如果对象模式的 值域是对象模式集合，则在该集合中，只包含一种对象模式，按照上述定 义，对象模式 d b ，由于值域 ) 中包含两个不同的对象模式，所以根据定义，上述 视图不是一个规范化视图，其视图定义可以转换成为 d ba n d pp e r s o n ) d b ，规范化后的视图和原视图的 表达能力一致，而且上述转换的方法是多项式时间能够完成的。 2 2 2c l i o 映射语言 c l i o 系统是一个数据交换系统口2 1 。为有利于数据交换的进行，在系统 中使用了新的源到目标模式的映射形式。用语法定义一个表达式 燕山大学工学硕士学位论文 e ：= s l x l e 1 ，在这里x 是一个变量，s 是一个模式的根，l 是一个标签，e 1 是记录投影。那么一个映射可以是如下形式。 m ：= f o r e a c hx ii ng l ，x ni ng n w h e r e b l e x i s t sy li ng l ，y mi ng m w h e r e b 2 w i t he l = e la n d a n de i k = e k 在这里每个x i i ng i 或y j i ng j 叫作发生器并且每个g i 或酯是一个带有 类型s e t o f 的t 表达式e ；变量x i 或y j 绑定e 集合的单独元素。如果用于 g i 或鲂的变量由前面发生器在同一子句定义的话，映射是良构。在f o r e a c h 或e x i s t s 子句中任意模式的根必须是一个源模式或目标模式的根。两个 w h e r e 子旬中的b l 和b 2 表明表达式x i ，x n 或y 1 , y m 之间的关系，其中 可以包括等值常量。最后，谢t l l 子句中的等价关系表示源和目标的关系， e i 和e i 必须具有同一原子类型，并且一个是来自目标模式的表达式e i 和一 个数据源表达式e i 。 从这个映射的定义可以看出，f o r e a c h 子句是对源模式的查询，e x i s t s 子句是对目标模式的查询，而w i t h 是它们之间的关系。后面的算法处理思 想也就是基于此。 2 3 全局数据模型 集成系统中还需要一个全局数据模型来描述所有的信息源，对于结构 化、半结构化及无结构的信息的描述所用的数据模型已有许多研究。 2 3 1 数据转换模型o e m o e m ( o b j e c te x c h a n g em o d e l ) 是数据转换的模型【3 1 】，用于文档类型转 换，基本思想是对每个需要交换的对象给定一个标记，标记用于表示这个 信息的含义。这个模型可以看作是一棵带标记的有方向的树，对象对应一 个节点，每个对象都有标识符和标签。这里的对象分为原子对象和集合对 1 6 第2 章集成系统概述 象两类，原子对象的值是原子值，集合对象是该子对象的集合。用 来表示一个o e m 对象。其中o b j e c t - i d 是对象的唯一的 可变长的标识；l a b e l 是个可变长的字符串，描述对象含义；t y p