（计算机应用技术专业论文）分布式异构数据互操作的若干关键技术研究.pdf

摘要 随着网络技术的发展，越来越多的用户希望能够访问和处理来自分布于不同 的数据源的信息，实现数据在多个系统与不同数据源之间的集成与共享。在现有 的分布式异构的环境中，将信息技术的应用从传统的事务处理推向i n t e m e t 环境 下的数据集成、共享与互操作的任务越来越紧追。本文对分布式异构数据互操作 进行了深入的分析和探讨，围绕其中的公共互操作模型的构造，根据获得局部数 据源信息的特点如何进行有效的查询优化等关键技术进行了研究。 论文首先详细介绍了联邦数据库系统f b d s 和m e d i a t o 们珩a p p e r 系统两种的 数据互操作模型。论文将两种传统的数据互操作方式的主要特点与广域分布式环 境相结合设计了一个分布式异构数据互操作h i m 模型。该模型兼顾了两者的优点， 比单独使用一种集成方案更适合广域分布式环境。论文在给出了分布式异构信息 互操作系统中查询处理的基本概念和结构之后，根据获得的局部源信息的特点将 全局查询优化分为基于静态源信息和基于动态源信息的查询优化。并对分布式异 构数据源互操作全局查询优化进行改进。首先将带冗余条件表达式的查询图、边 界点和查询块等概念引入k r t l s k a l 算法。分割带冗余条件表达式查询图、查询块 优化、重构查询图等步骤构成改进后算法m q b k 。然后在m q b k 算法的基础之 上，结合场地间运算代价在不同情况下需要用不同的权函数表示这一特点，将优 化算法迸一步改进为基于静态源信息的多权值优化算法。最后将局部源信息动态 产生的特点融入改进算法，将基于静态源信息的多权值优化算法与基于动态源信 息的查询优化相结合设计了一个混合优化算法d s h o 算法。 实验表明m q b k 算法性能优于k m s k a l 算法；混合优化d s h 0 算法的平均 执行时间最短，性能最优，基于动态源信息的查询优化次之，基于静态源信息的 多权值优化算法性能略差一点。 关键词：分布式异构数据；互操作模型；查询优化；权函数；查询图；源信息 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rn e t w o f k ，m o r ea n dm o r eu s e r sb e g i nt oh a v e t h er e q u i r e m e n tt oa c c e s sa n dp r o c e s si n f o m a t i o nd i s t f i b u t e da m o n gd i f f e r e n td a t a s o u r c e s ，w h i c hr e a l i z e st h ei n t e g r a t i o na n ds h a r i n go fv a r i o u ss y s t e m s i tb e c o m e s m o r ec r i t i c a lt h a tm o v et h e 印p “c a t i o no fi n f o n n a t i o nt e c h n o l o g yf r o mt r a n s a c t i o n p r o c e s s i n g t od a t a i n t e r o p e r a t i o n u n d e rt h ei n t e m e t t h i s p a p e r f b c u s e so n d i s t r i b u t e dh e t e r o g e n e o u sd a t a i n t e r o p e r a t i o n ， i nw h i c hs u c ht e c h n o l o g i e sa s c o n s t m c t i o no fi n t e r o p e r a t i o nm o d e l ，q u e r yo p t i m i z a t i o nb a s e do nc h 盯a c t e r i s t i c so f o b t a i n i n gl o c a li n f b m a t i o na r es t u d i e dc a r e f u l l y t h et r a d i t i o n a ld a t a i n t e r o p e r a t i o nm o d e l s ， f c d e r a t e dd a t a b a s es y s t e m柚d m e d i a t o r w r a p p e rs y s t e m ，a r es u m m a r i z e di nt h i sp a p e rf i r s t h o w e v e r ，i ff e d e r a t e d d a t a b a s es y s t e mi st a l 【e na st h eo n l y 印p r o a c ho nd 砒ai n t e g f a t i o n ，t h ea b i l i t yo fd a t a s h a r i n ga n de 伍c i e n c yo fi m e r o p e r a t i o nc 孤n o tb eg u a r 锄t e e d ，a n da u t o n o m o u sa b i l i t y c 锄n o tb es a t i s f i e di fw et a k em e d i a t o r w r 印p e rs y s t e ma st h eo n l ya p p r o a c h t h i s p a p e fp r e s e n t sad i s t r i b u t e dh e t e r o g e n e o u sd a t ai n t e r o p e r a t i o nm o d e lh i mw h i c h c o m b i n e st h ea d v a n t a g eo ft w ot r a d i t i o n a lm o d e la n dc a nf u l f i ut h er e a lw o r l d a p p l i c a t i o nr e q u i r e m e m sm u c hb e n e r t h i sp 印e rt h e na n a l y s e sm eo r g a n i z a t i o na n dc o n c e p t i o no fq u e r yp r o c e s s i n gi n d i s t r i b u t e dh e t e r o g e n e o u sd a t a ( d h d ) i n t e r o p e r a t i o n a c c o r d i n gt ot h ec h a f a c t e r i s t i c s o fh o wt oo b t a i nl o c a ls o u r c ei n f o 珊a t i o n ，g l o b a lo p t i m i z a t i o ni sc l 解s i f i e da sq u e r y o p t i m i z a t i o ns c h e m e sb a s e do ns t a t i cl o c a li n f o 姗a t i o na n dd y n a m i cl o c a li n f o 珊a t i o n g l o b a lq u e r yo p t i m i z a t i o ni si m p r o v e da st h ef o l l o w i n g f i r s t l y t h ec o n c e p t sa sq u e r y g r a p hw i t hr e d 肋d a n tc l a u s e ，b o u n d a r yp o i n t 卸dq u e r yb l o c ka r ei n t r o d u c e d i n t f a d i t i o n a lk n l s k a la l g o r i t h ma n dt h ei m p m v e da l g o r i t h mm q b km a i n l yc o n s i s t so f q u e 哆g r 印hd i v i d i n g ，q u e r yb l o c ko p t i m i z i n ga n dq u e r yg r 印hr e c o n s t m c t i n g s e c o n d l y ，b a s e do nm q b k ，t h ea l g o r i t h mi sf h n h e ri m p r o v e dt h r o u g hd e f i n i n g d i f 弛r e mw e 培h t si nq u e r yo p t i m i z a t i o ns c h e m e so ns t a t i cl o c a li n f o 咖a t i o na n dt h e m u l t i p l e w e i g h t ss t a t i cq u e r ya l g o r i t h m si so b t a i n e d f i n a l l y ，c o m b i n i n go p t i m i z a t i o n s c h e m e sb a s e do nd y n a m i c1 0 c a l i n f o m a t i o n ，ah y b r i da l g o r i t h md s - h oi sd e s i g n e d a tt h ee n do ft h i sp a p e r ，t h ea l g o r i t h mi sf e a l i z e db ye x p e r i m e n t t h es i m u l a t i o n s 蛐de x p 耐m e n t a lr e s u l t ss h o wt h a tt h ep e r f o m a n c eo fm q b ki sb e t t e rt h 她k m s k a l 粕dt h eh y b r i do p t i m i z a t i o ns c h e m ed s - h oi sm u c hb e t t e rt h a nq u e r yo p t i m i z a t i o n s c h e m e sb a s e do ns t a t i cl o c a l i n f o m a t i o na n do nd y n a m i cl o c a li n f b m a “o n k e yw o r d 墨：d i s t r i b u t e dh e t e r o g e e o u sd a t a ( d h d ) ；i n t e r o p e r a t i o nm o d e l ；q u e r y o p t i m i z a t i o n ； w e i g h tf h n c t i o n ；q u e r yg r a p h ；l o c a ls o u r c ei n f b r m a t i o n i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：呼遗 慨叼年卑月4 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密晤。 ( 请在以上相应方框内打“”) 作者签名： 邛湛 新签名：砂钞 日期：明年年月茄日 日期：。7 年午月2 名日 第1 章概论 1 1 论文的研究的背景和选题意义 2 0 世纪7 0 年代以来，由于计算机硬件环境，特别是计算机网络通讯技术的快 速发展，越来越多的用户希望能够透明地获取和处理各种各样的遍布在信息世界 的每一个角落的计算资源，实现多个软硬件系统以及不同信息源之间的互操作。 数据库技术的发展已导致了许多种类不同的数据库系统的出现。很多单位和 组织为了存储和管理在发展过程中积累的大量数据，在不同时期开发了不同的数 据库管理系统。由于构建系统时难以做到统一规划，这些系统常常是自治的，异 构的。正是由于实施数据管理系统的阶段性、技术性以及其他经济和人为因素的 影响，导致了大量的异构数据库的存在。致使这些系统之间很难进行信息交换， 实现互操作。 而随着互联网应用的不断深入，已经有更多的不同种类的数据资源可供用户 共享，这些资源不仅包括传统的数据库系统中的数据，如关系型数据库和面向对 象数据库，它们都有良好的数据模型，而且还包括许多半结构化和无结构的数据， 如h t m l 、x m l 文档和文本数据。目前，几乎所有的大型商业应用，如电子商 务、虚拟企业等，都是基于w e b 的数据管理系统，采用浏览器，应用服务器数 据库服务器三层应用架构模式，系统中重要的业务数据保存在数据库中。由于安 全控制方面的考虑，这些系统通常不直接向w 曲开放其后台数据库，而是将这 些数据信息经过处理之后再发布到网页上，形成h t m l 或x m l 数据。遍布于 i n t e m e t 网络中的w 曲服务器将这些数据链接在一起，形成一个全球性的信息 共享环境。 可见这些信息源物理上可能分布在异构环境的多个自治域中，有着不同的数 据格式、存储方式、访问控制策略，逻辑上则可能在数据模型、操纵语言和数据 语义等方面存在着很大差异l l 】。同时，这些信息源的可共享性、共享方式，共享 内容等也可能随时发生变化。计算机技术的飞速发展为实现这些分布式异构数据 源之问的实现互操作可能，但由于存在着上述的差异和困难，要将它变成现实并 非易事。因此，实现分布式异构数据源之间的互操作便成为一个很有研究价值的 课题。在对分布式数据源互操作问题的研究中，互操作框架的构建对互操作系统 的实现起着重要的作用，它决定了内部各组件的基本组织方式和系统的体系结 构。查询处理也是分布式异构数据源集成系统的一项关键任务。查询处理的效率 不仅影响分布式数据源集成系统性能，还对整个应用系统数据的可用性、可扩展 性、提高集成系统的使用效率起着不可估量的作用。因此，对分布式异构数据源 互操作以及所涉及到的一些关键问题的研究具有一定的实用价值和学术意义。 1 2 国内外研究现状综述 1 2 1 研究现状 目前国内外对于分布式异构数据互操作技术以及集成系统查询优化方法的 研究很多。如以微电子和计算机技术协会( m c c ) 开发的信息集成系统i n f o s l e u t h 【2 l 为例，i n f o s l e u t h 是结合a g e n t 技术和本体技术开发一个m e d i a t o r w r a p p e r 信息 集成系统，如图1 1 所示。系统粗略的划分成三层：数据源层，集成层和应用层。 i n f o s l e u t h 采用了分布式方法来实现中间层，中间层由一组协作信息a g e n t 组成， 例如查询a g e n t ，任务执行规划a g e n t 等等。多个a g e n t 之间利用通讯语言k q m l 进行通讯和协作，以用户的请求和查询任务。通过将己存在的数据源包装，构建 、a p p e r ，形成一个简单的信息a g e n t 。w r a p p e r 对外提供统一的访问界面，对同 一类型的数据源只需构建一个w r a p p e r 。 图1 1i n f o s l e u t h 系统结构 美国i b m 公司a l m a d e n 研究中心数据库组的开发项目g a r l i c 1 1 ，该项目组 的研究把传统的和多媒体数据存储在不同的数据仓库中，支持新的数据仓库的添 加，并通过一个“中间件”查询处理器提高查询效率，为多种异构遗留数据源提 供集成视图，这些数据源包括数据库系统如d b 2 ，o r a c l e 、可检索的w 曲数据， 文本搜索引擎以及一些专业数据的数据库。它通过建立包装器( w r a p p e r ) 的方 法来集成这些数据嘲。w r a p p e r 技术是将遗留系统( l e g a c y s y s t e m ) 集成到大型 集成框架中有效而且代价较小的方法。遗留系统经过w r a p p e r 包装后就变成了 可以复用的软组件，它可以在新的构架下被调用，从而扩展了遗留系统的生命周 期；美国s t a n d f o r d 大学设计的一个专门用于管理半结构化信息的数据库管理信 息系统l o r e 嗍，它可以对半结构化数据o e m 和x m l 数据进行存储和管理；美 国密歇根迪尔伯恩大学( u n i v o f m i c h i g a n d e a r b o m ) 的q i a n gz h u 和加拿大沃 特卢大学( u n i v o f w a t e r l o o ) 的p e 卜a k el a r s o n 等以及i b m 多伦多实验室和几所 北美大学的研究者们合作开发的c o r d s 项目中对多数据库的查询处理特别是 查询优化做了较多的研究工作i ，1 ，他们提出了查询采样、查询探测、模糊查询【l l 等技术对全局查询进行优化，还提出了衰减代价评估模型1 9 l 以实现对全局查询的 2 优化。此外，他们还对动态多数据库环境中的代价模型进行了一些定性分析1 1 0 l l 。 但是c o r d s 采用的是关系模型，任何加入c o r d s 的数据源在与其他数据源进 行数据之间的交互时，必须转换成表格式数据，这有较大的局限性：美国南加州 大学( u n i v e r s i t yo fs o u t h e mc a l i f o r n i a ) 的n a v e e na s h i s h 和c r a i g k n o b l o c k 利 用对半结构化数据进行包装办法来实现对w w w 上的数据类似数据库的查询 操作i 倒l 。法国i n r i a 研究院的c a r a v e l 项目致力于解决自治、异构信息源的 网络中信息集成的般问题】f l ”。信息源包括数据源和程序源，数据源可能是结 构化或半结构化的。c a t a v e l 的目标是通过集成视图提供对信息源的统一访问， 放松对一致性数据仓库的管理，并提出适应不同用户的信息浏览方法，在信息集 成、查询优化、半结构数据访问、数据仓库、x m l 查询、w e b 数据管理等方面 都取得了很多成果。加拿大阿尔伯特大学( u n i v e r s i t y o f a l b e r t a ) 的l - l y a n ，t o z s u 等在d l o m 项目中提出了一个基于中介器( m e d i a t o r ) 的互操作管理体系 结构的具体实现l 。其查询处理部分由查询接口管理器、动态查询路由、动态查 询执行计划器、动态查询结果聚合器构成。其用户接口是基于w w w 的，用户 提交一个基于w w w 的表单查询，查询接口管理器将表单查询转换成用i d l 表示的查询。查询路由主要负责定位和选取对查询结果有帮助的相关信息源，查 询执行计划器主要负责将用户查询分解为针对各信息源的子查询，并产生一个经 过优化的查询执行调度计划。子查询经过翻译后在相应的信息源上执行，查询结 果聚合器将各子查询的结果打包给d i o m 对象，并根据客户的源查询语句组装 结果。其语义关联操作和客户查询描述是解决查询结果的语义异构的主要技术。 国内由华中科技大学计算机科学与技术学院研制的基于c o r b x m l 的多 数据库原型系统p a n o r a m a m h l 8 】可以有效集成o r a c l e ，s y b a s e 和d m 2 等数据库， 提出了一种多模式的映射方案f 1 9 】【2 0 l ，对系统中全局查询转换的方法进行了详细的 研究【2 i l 。由东南大学开发的一个基于c o i m a 的可扩展的异构数据源集成系统原 型v e r s a t i l e 【2 2 】，该模型在i o n a 公司的o r b i x 产品上，对s o ls e r v e r ，v e r s a n t ， 文件系统、超文本数据进行包装和集成。该系统不仅能集成上述数据源，而且能 集成随时插入的新数据源中的数据。南开大学的袁小洁等研究人员提出了一个基 于m e d i a t i o n 的异构数据集成解决方案】，并针对该方案设计实现了一个异构数 据集成系统h d i s ，其结构如图1 2 所示。系统在异构数据集成系统中引入了虚 拟表，用户查询基于虚拟表，采用了查询任务预分配算法来提高查询效率，提出 用语义表达式文法解决异构数据集成中的冲突问题。东北大学的于戈、王国仁等 针对x m l 数据查询语言中路径表达式本身的优化进行了研究彤，提出了两种 针对路径表达式的优化策略：路径缩短策略和补路径策略，提高了x m l 路径 查询的效率；复旦大学的施伯乐、陈彤兵等提出了基于元数据描述和数据源能力 的分布式自治数据源的联合查询方法】。基于元数据描述，在语义正确的前提下， 根据不同查询条件和不同数据源能力，自动构造查询计划来解决分布式异构数据 源的集成和综合查询问题，并给出了根据实际需要快速构造查询计划的直观算法 和尽可能全面构造所有可能查询计划的闭包算法； 图1 2 h d l s 系统结构 中国人民大学的孟小峰和中科院的王静等提出了一种基于区域划分的结构 连接算法，该算法基于任务分解的思想，利用区域编码的特点对输入集合进行 划分，解决x m l 查询处理中在输入数据无序或没有索引情况下的排序合并问 题。东南大学的钱钢、董逸生等给出了基于路径映射的x m l 数据集成方法和 基于映射依赖的查询重写算法【2 7 】，以解决全局模式与局部数据源之间的查询转换 问题。 1 2 2 主要研究内容 根据对分布式异构数据源互操作研究现状的分析，国内外对该领域的研究主 要涉及以下多个方面： 第一是解决地域的分布性。各数据源分布在不同的地域，属于分布式系统， 因此，需要用到许多分布式系统的处理技术，如分布式数据库系统、分布式对象 技术等【2 。1 。 第二是处理数据源的异构性。数据源的异构问题分为三个层次：平台层、数 据模型层和语义层脚】。平台层异构是指数据源所处的硬件环境、操作系统、网络 协议不同；数据模型层异构是指各数据管理系统所使用的数据模型和数据语言的 不同，语义层异构是指由于各数据源设计上的独立性导致的语义冲突。 第三是保留数据源的自治性。被集成的每个数据源都有自己的管理系统，运 行着各自已有的应用程序。这些系统是预先已经存在的，称为遗留系统( l e g a c y s y s t e m ) 1 3 0 l 。这就要求这些数据源在被集成之后仍然保持一定程度的独立性。 第四是实现对用户的透明性。对于集成系统的全局用户，集成的复杂性应该 是不可见的，用户应能选择最适合的用户接口和查询语言，不需知道数据究竟是 来自于哪个局部子系统。 第五是有效的查询处理的实现。集成系统用户所需的数据物理上分散存储于 4 各局部数据源中，用户只是根据集成系统的全局逻辑视图进行查询，因此查询处 理的关键是查询计划的确定及优化处理，即如何将全局查询分解成不同数据源的 子查询，并分发到各数据源，产生的予查询结果最后重新组成一个回答提交给用 户川旧。 第六是模型化问题。在异构信息集成系统中，同一个概念可能按不同的方式 模型化，相似的应用也可能选择不同的模型化技术。在多种模型化技术中，采用 公共数据模型( c d m ) 表达的全局集成模式是一种较理想的方法印l 。这也提出 了另外一个问题，即如何在公共数据模型与局部数据模型之间进行转换。 第七是数据抽取、整合和统一。目前，i n t e r n e t i n t r a n e t 上已经积累了庞大 的数据资源，这些数据的构成方式各不相同。一种极端是来自传统的数据库数据， 它们具有严谨的结构；另一极端是来自于一些文件系统中的无结构数据，如图像、 声音和未加工的纯文本。介于两种极端中间的是所谓的半结构化数据，如 h t m l ，x m l 。由于没有预设的模式结构，集成系统必须从中抽取出关键的、用 户感兴趣的数据，然后加以整合，再与其它数据源的数据一起集成】。 近2 0 年来，针对该领域上述七个主要的问题，国内外学者从各个不同层面、 采用不同的方法和技术分别对其进行了研究，并得出了不少有益的结论，也建立 了一些原型系统驴钉。但是一方面由于各数据源的分布性、自治性和异构性等特 点带来的困难，另一方面也由于技术条件的限制，目前对异构数据源的集成及其 查询处理技术的研究还处于个案处理的初步阶段，目前并不存在一个“通用”的 解决方案，现有的互操作系统也都处在研究阶段，离实用的商业化水平还相距甚 远。而传统的数据集成与查询处理技术对于分布异构信息集成的查询优化的研究 具有许多可借鉴的经验。 因此，本论文通过对传统的分布式数据互操作与查询处理的优化技术进行拓 展，针对该领域七个主要研究方向中的第五点( 有效查询处理的实现) 和第六点 ( 模型化问题) 进行更深入的分析，研究在广域环境下实现分布式异构多数据源 的互操作和查询优化的相关理论和实现技术。 1 3 论文的主要工作 人们在充分利用分布于世界各地的不同种类的信息所带来的诸多优点的同 时，也发现正是因为“分布式”和“异构”，又产生了一系列较集中式数据源更 复杂、难度更大的技术问题。例如，分布式异构数据源的互操作、针对分布式数 据源的查询处理与优化、分布式数据的更新处理以及分布式事务的并发控制等 等，这些都是亟待解决的问题。 论文在分析分布式异构信息源互操作问题中信息自身特点和信息共享特点 的基础上，针对如下方面进行了研究： ( 1 ) 分布式异构信息源互操作模型的研究和建立 互操作的方式是异构信息源集成方法中的一种。由于现有的各局部数据源的 数据模式是由不同的用户，在不同的时间和地点，基于不同的数据模型独立地设 计的，它们之间存在着各种各样的差异和冲突。为了实现用户对分布式异构数据 源的透明访问，建立一个适合广域分布式环境的分布式异构信息源互操作模型十 分必要。论文就目前国内外对异构数据源的互操作方法进行更深入的研究和比 较。通过结合多个传统的数据互操作模型的优点，设计一种改进的模型以更适合 分布式异构数据源之间的互操作。 ( 2 ) 查询处理的研究和分析 查询处理是异构信息集成系统的关键技术之一。在分布式异构数据互操作系 统中，查询处理除了要解决传统数据查询需要解决的问题，还需解决分布式和异 构带来的特殊问题。查询优化又是查询处理中非常重要而又十分复杂的问题。论 文对分布式异构数据互操作中的查询处理进行分析，对全局优化策略进行较深入 的研究，尤其针对由于局部数据源的自治性而产生的不同种类的查询优化策路进 行探讨。分析了每种优化策略的特点，针对其中的可改进之处给出一定的改进方 案。 ( 3 ) 查询优化方案的设计 根据论文所提出的改进方案，对基于静态信息源的查询优化方案，以一个直 连接算法的改进为基础，对该方案进行详细的设计；在对基于动态信息源的查询 优化方案的设计中，对其关键参数进行研究，最终将两种不同类型的优化策略进 行结合，设计一个全局查询方案，以期减少查询代价，提高优化整体性能。 1 。4 论文的组织结构 论文按如下方式组织： 第一章介绍论文的研究背景和选题意义，针对国内外对分布式异构数据互操 作的研究现状和研究的主要内容详细作了分析，在此基础上提出了本论文的主要 研究工作。 第二章在仔细研究两种传统的数据互操作技术联邦数据库系统f b d s 和 m e d i a 幻r w h p p e r 系统的基础上，结合两者特点设计了一个分布式异构数据互操 作h i m 模型，并且将w e b 服务的基本架构引入到h i m 模型。该模型较单独使 用一种集成方式更适合广域分布式环境，且兼顾了局域范围内的信息集成和处理 的效率。 第三章首先简单介绍了查询处理和查询优化的基本原理。对两类全局查询优 化策略一基于静态局部源信息的查询优化和基于动态局部源信息的查询优化， 进行了详细的研究。提出了解决在带权图中找到最小代价生成树问题的k r u s k a l 算法存在的问题和可改进之处；分析了采用基于静态局部源信息的查询优化方案 时，使用不同权函数在不同实际运行环境中反映了不同场地间运算的代价情况， 提出了基于k r u s k a l 算法的静态局部源信息查询优化的改迸方案：最后结合基于 动态局部源信息的查询优化提出了将两种优化策略相结合的方案。 6 第四章首先改进了传统k 邝s k a l 算法，将带冗余条件表达式的查询图、边 界点和查询块等概念引入传统算法，设计了一个运用于含冗余条件查询图且基于 多查询块的m q b k 算法。在此基础之上，结合静态优化算法的多种权函数，将 m q b k 算法进一步改进为基于静态源信息的多权值优化算法。之后再将基于静 态源信息的多权值优化算法与基于动态源信息的查询优化相结合设计了一个用 于全局优化的混合优化d s h o 算法。 第五章对传统的k r u s k a l 算法和m q b k 算法的连接代价性能，以及基于静 态源信息的多权值优化算法、基于动态源信息的查询优化和混合优化d s 。h o 算 法的时间性能进行了实验验证和结果分析。最后对论文进行了总结，并对今后的 研究做出了展望。 7 第2 章d h d 互操作模型的研究与建立 2 1 问题的概述 重构( r e c o n s t r u c t i o n ) 和互操作( i n t e r o p e r a t i o n ) 是分布式异构数据 ( d i s t r i b u t e dh e t e r 0 2 e n e o u sd a t a ，d h d ) 集成的两种主要方式m l 。重构，需要 把旧系统中的应用逻辑、数据定义和数据都转移到新系统中。这种方式便于新系 统的维护和集成，但原有系统越多，其过程也越复杂，且费用越昂贵。互操作则 是通过在已有信息系统的基础上设置新的标准界面，来建立一个互操作平台，实 现不同系统之间的互操作。这种方式既保持了已有系统中的数据和应用程序，还 允许新的系统加入互操作平台中，实现计算资源的共享，为用户提供一种统一的、 规范化的、跨越不同领域的、独立于数据源的互操作手段。因此，受到更广泛的 关注。但是，计算环境的分布性、异构性以及各已有系统的自治性，使得多种不 同数据源之闯的互操作实现起来非常困难。 互操作性是指不同计算机系统、网络、操作系统和应用程序一起工作并共享 信息的能力，它强调将具有不同数据结构和数据格式的软件系统集成在一起协同 工作m 】。一个理想的互操作系统需要系统能够在分布且异构的环境中，使不同的 系统能彼此更加安全地获取和处理对方的信息；用户能比较方便地搜索和查询所 需的信息，并能相对便捷地使用各种不同类型或者格式的数据；信息管理者能很 好地对数据进行管理，为用户保障服务，并将资源充分地提供给用户使用p 9 j 。根 据互操作所涉及的不同侧重点，它可以被分为软件互操作、数据互操作、语义互 操作等。 2 2 传统d h d 互操作模型存在的问题 数据互操作( d a t a i n t e r o p e r a b i l i t y ) 是指在分布式异构环境中实现不同数据 格式和数据结构的数据的共享与相互访问，包括不同文件系统中的相互访问、不 同数据库中数据的访问以及w e b 文档的访问等。是信息集成中需要解决的主要 问题。 d h d 互操作己经有很多研究人员提出了多种结构，其中有最常用的进行数 据集成，实现互操作的方式一般有三种：联邦数据库系统f e d e r a t e dd a t a b a s e s y s t e m ( f e d e r a t e dd a t a b a s es y s t e m ，f d b s ) 、m e d i a t o r w r a p p e r 系统以及数据仓 库( d a t aw a r e h o u s e ) 。下面就两种d h d 互操作模型联邦数据库系统f b d s 和 m e d i a t o r w r a p p e r 系统的主要特点和存在的问题进行分析。 2 2 1 联邦数据库系统f d b s 该技术主要在8 0 年代采用，联邦数据库系统f d b s 是一个相互合作但是又 各自保持其自治性的组件数据库系统( c d b s ) 的集合。用于管理联邦数据库的 系统软件称为联邦d b m s ，即f d b m s ，图2 1 给出了联邦数据库系统的一种体 系结构。 图2 1 联邦数据库系统 多个由在不同结点上松散藕合分布的自治异构的c d b s 构成了f b d s 。同时 实现c b d s 之间的数据共享与互操作【4 0 】。联邦数据库中不存在全局的中央控制中 心，这样能保证数据源的自治性，提高数据的私有和安全特性。组件数据库c d b s 可自由地加入或退出联邦，单个组件结点有权拒绝或允许其它组件结点对它的访 问。在大多数情况下，f d b s 是异构的，各成员数据库系统可能有不同的数据模 型、查询语言、并发控制、事务处理机制、安全策略等，另外，联邦数据库可能 有自己的联邦数据模型，联邦数据库不能直接操作成员数据库。成员本身也可以 是联邦数据库，一个数据库可以是多个联邦数据库系统的成员数据库。图2 1 中 共包括两个联邦数据库：f d b s l 和f d b s 2 ，其中f d b s l 包含成员c d b s l 一和 c d b s 2 ，f d b s 2 包含成员c d b s 2 和c d b s 3 ，同时c d b s 3 又是由成员数据库 c d b s 4 和c d b s 5 组成的联邦数据库。 f d b s 没有全局模式，为了使用联邦数据库系统实现不同数据源的集成，s e t h 和l a r s o n 提出了五级调用模式结构来描述联邦数据库系统j ，这五级模式包 括：局部模式( l o c a ls c h e m a ) 、成员模式( c o m p o n e n ts c h e m a ) 、输出模式( e x p o n s c h e m a ) 、联邦模式( f e d e r a t e ds c h e m a ) 和外模式。 联邦数据库模式结构中的局部模式就是成员数据库的概念模式，它必须转换 成联邦的通用数据模型，以便所有成员数据库管理系统以通用语言提供模式定 9 义。转换处理器( t r a n s f o r m i n gp r o c e s s o r ) 将局部模式中的对象映射到成员模式， 同时，还将针对成员模式的查询翻译到局部模式。成员模式中的数据并不全部抽 取到联邦系统，只有有用的数据才被送到输出模式。过滤处理器( f i l t e “n g p r o c e s s o r ) 负责完成成员模式向输出模式的过滤和转换，此外还负责联邦主体在 联邦与成员数据库之间的访问控制，将针对输出模式的操作翻译到成员模式，并 确保语法的正确性和语义的有效性( 保证上述操作被执行时，成员系统的完整性 不受到影响) 。联邦模式是多个输出模式的集合，构造处理器( c o n s t r u c t i n g p r o c e s s o r ) 负责将多个输出模式集成到联邦模式，同时还将针对联邦模式的操作 分解为针对输出模式的操作。为了处理不同的应用以及安全控制的需要，对联邦 模式进行不同的归类，形成针对不同用户群的外模式，这一归类工作同样由过滤 处理器来负责完成。 输出模式及其相应的过滤处理器，隔离了联邦的数据访问和联邦用户的操作 请求，从而保证了成员数据库的自治特性。其次，可以通过定义不同的输出模式， 满足不同联邦的需要，从而可以实现一个成员数据库可以包含在多个联邦系统 中。另外，联邦系统可以通过引用它的成员数据库系统所提供的输出模式，为预 先定义的其他联邦类提供输出模式，这样可以加快联邦层次结构的形成。联邦数 据库系统的五级模式结构主要是考虑了为实现数据的互操作而进行的模式的逻 辑定义、自底向上的翻译和白顶向下的操作转换。 联邦数据库系统f d b s 作为一种d h d 互操作的方式，其主要弊端是由于各 成员数据库系统间的松散耦合产生的，使得真正实用的联邦数据库管理系统在实 现上更加困难。在某些情况下，只能实现包含简单查询语句、实现领导决策辅助 等功能。 2 2 2m e dia 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 信息集成的方法是在w i e d e r h 0 1 d 提出了m q s ( m e d i a t o r q u e r ys y s t e m ) 体系结构【4 2 】的基础上加入对异构信息源封装形成的。它通过在中介 ( m e d i a t o r ) 和包装器( ，r a p p e r s ) 之间分割任务，提高查询处理的并发性，减少响应 时间。它是在不影响其局部自治性的基础上，构造用户所需要的某种透明性的分 布式管理系统，以支持对物理上分布的多个数据库的全局访问和数据库之间的互 操作。采用m e d i a t o r w r a p p e r 系统实现分布式数据源互操作的结构如图2 2 所示。 从图中可以看出，一个使用m e d i a t o r w r a p p e r 的异构信息集成系统主要由4 个部分组成； 顶层是用户和应用程序，用户输入特定的查询语句，应用程序对查询语句进 行语法和语义检查，如果没有错误的话，将查询语句传给中介，再从中介得到返 回的数据，显示给系统用户。 1 0 图2 2m 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 是局部数据源和中介的接口，一个包装器对应一种类型的数 据源，比如一个异构数据库查询系统中有s q l s e r v e r 、o r a c l e 、s y b a s e 等类型的 数据源，并且每种类型的数据库可能不止一个，那么系统中只需要为每种类型的 数据源分别定义一个包装器就可以了，每个包装器对应一种类型的数据库，而不 必关心某种类型的数据源的数量是多少。包装器负责接收全局代理发送过来的 子查询，将其转换为本地数据源能够处理的语言，交付给局部数据源去执行，并 将返回的结果翻译为公共数据模型表达，传回给全局代理】。包装器主要功能一 是在全局代理和成员系统之间建立通信机制，并以局部成员系统用户的身份担任 查询代理，完成不同数据模型的查询语言之间的查询转换；二是负责维护局部系 统的输出模式，实现数据模型映射，即在不同的数据模型之间进行翻译；三是担 任全局事务在局部系统中的事务代理。与全局代理合作，保证全局可串行化。提 供事务并发和恢复控制。为实现全局事务处理的正确性标准，局部事务之间有必 要进行协调：四是控制语义完整性，由于成员系统的局部更新会影响全局数据的 完整性，因此局部代理必须及时感应和监控局部操作，并且及时回馈给全局代理。 m e d i a t o r w r a p p e r 模型提供了一种从系统和规模上来解决d h d 互操作的方 法。它能够接受和容纳多个分布异构数据库系统，对外呈现出一种集成结构和统 视图，具有全局的统一管理，而对内又允许各个异构数据库的“自治性”。 2 2 3f b m s 和m e d ia t o r w r a p p e r 系统存在的问题 可以看出，m e d i a t o f 、v r 印p e r 系统和f b d s 在组成结构和实现方法上主要的 差别在于f d b s 没有全局模式和一个统一中央控制中心，使得各成员数据库系统 问的耦合更加松散，所以真