（计算机科学与技术专业论文）分布式数据库查询优化算法的研究.pdf

摘要 自2 0 世纪7 0 年代中期开始，随着计算机网络技术的迅速发展以及地理位置分散的 公司、团体和各种组织对数据库的广泛需求，分布式数据库系统在集中式数据库系统的 基础上产生并逐渐发展起来。查询操作是数据库中最常用的操作之一，自分布式数据库 诞生到现在的3 0 多年间，对于分布式数据库查询优化的研究就一直在进行着。由于分 布式数据库的数据分布性和冗余性，使得查询的优化较集中式数据库来说要复杂很多， 因此查询优化对于分布式数据库来说一直是一个重要问题。 针对不同的网络环境和查询优化目标，分布式数据库的查询优化算法可分为基于半 连接的优化算法和基于直接连接的优化算法这两大类。本文首先对分布式数据库系统进 行了介绍，并介绍了查询优化的基本知识。然后对上述两类查询优化算法中几种常用的 优化算法进行介绍并进行性能的分析，并且对其中的两种算法进行了改进。 在基于半连接的优化算法中，本文着重分析了传统半连接算法的性能和不足，并进 行改进，减少算法的网络传输代价，提高半连接算法的性能。在基于直接连接的优化算 法中，对p a r t i t i o n 算法进行分析及改进。在实现过程中，提出了针对该算法的查询图划 分方法，将查询图划分为可并行执行的多个子查询图，提高查询执行的并行性。通过在 子查询图执行p a r t i t i o n 算法，充分发挥p a r t i t i o n 算法站点依赖的性能，最终提高整个查 询的执行速度。对于以上两种改进算法，本文都通过实验进行了验证分析，证明它们的 可用性。 在文章的最后，总结了本文的主要工作，分析了论文研究的不足和尚待完善的地方， 同时也提出了下一步的研究目标。 关键词：分布式数据库，查询优化，半连接，直接连接 r e s e a r c ho rd a t aq u e r yo p t i m i z a t i o n i nd i s t r i b u t e dd a t a b a s e z h a n g y a n g ( c o m p u t e ra p p l i c a t i o na n dt e c h n o l o g y ) d i r e c t e db ya s s o c i a t ep r o f w e id o n g p i n g ，a s s o c i a t ep r o f s u nd o n g h a i a b s t r a c t s i n c et h e7 0 t hi n2 0c e n t u r i e sm i d d l e ，w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r k t e c h n o l o g y a n dt h ew i d en e e d so f g e o g r a p h i c a l l yd i s p e r s e dc o m p a n i e s , g r o u p sa n do r g a n i z a t i o n s , d i s t r i b u t e dd a t a b a s e s y s t e mg e n e r a t e da n dh a sb e e nd e v e l o p i n g q u e r yi st h em o s tc o m m o n l yo p e r a t i o nt h a th a sb e e nu s e di n d a t a b a s e s i n c et h eb i r t ho f d i s t r i b u t e dd a t a b a s e ，t h es t u d yo f q u e r yo p t i m i z a t i o ni nd i s t r i b u t e dd a t a b a s eh a s n e v e rb e e ns t o p p e di nm o r et h a n3 0y e a r s b e c a u s eo fd i s t r i b u t i o na n dr e d u n d a n c yo fd a t ad i s t r i b u t e d ，t h e q u e r yo p t i m i z a t i o ni n d i s t r i b u t e dd a t a b a s es y s t e mi sm o r ec o m p l e xt h a nt h a ti nc e n t r a l i z e dd a t a b a s e t h e r e f o r e ，q u e r yo p t i m i z a t i o ni sa ni m p o r t a n tp r o b l e mi nd i s t r i b u t e dd a t a b a s es y s t e m d i s t r i b u t e dd a t a b a s eq u e r yo p t i m i z a t i o na l g o r i t h m sc a nb ed i v i d e di n t os e m i - j o i n - b a s e do p t i m i z a t i o n a l g o r i t h ma n dd i r e c t - j o i n b a s e do p t i m i z a t i o na l g o r i t h mf o rd i f f e r e n tn e t w o r ke n v i r o n m e n t so rq u e r y o p t i m i z a t i o ng o a l s i nt h i sp a p e r , w ef i r s ti n t r o d u c et h ec o n c e p t so fd i s t r i b u t e dd a t a b a s es y s t e ma n db a s i c k n o w l e d g eo fq u e r yo p t i m i z a t i o n s e c o n d l y ，w es t u d i e ds e v e r a lc o m m o n l yu s e do p t i m i z a t i o na l g o r i t h m s a n di m p r o v et h ea b i l i t yo f t w oa l g o r i t h m s i nc o r eo ft h i sp a p e r , f i r s t l yw ed e s c r i b et h ep e r f o r m a n c ea n dd e f a u l to ft r a d i t i o n a ls e m i - j o i n a l g o r i t h ma n dp r o p o s ea ni m p r o v e da l g o r i t h m t h i si m p r o v e da l g o r i t h mc a l lr e d u c et h ec o s to fn e t w o r k t r a n s m i s s i o na n di m p r o v et h ep e r f o r m a n c eo fs e m i - j o i na l g o r i t h m s e c o n d l y ，w ei m p r o v e dp a r t i t i o n a l g o r i t h m i nt h ei m p r o v e da l g o r i t h m ，w ep r o p o s eam e t h o dt od i v i d eq u e r yg r a p h t h i sm e t h o dc a nd i v i d e t h eq u e r yg r a p hi n t om u l t i p l es u b - q u e r yg r a p h s t h r o u g ht h i sm e t h o d ，t h ep a r a l l e l i s mo f q u e r yc 鲫b e i m p r o v e d i nt h es u b - q u e r yg r a p h s , p a r t i t i o na l g o r i t h mc a ne x e c u t ei n d e p e n d e n t l ya n dm a k ef u l lu s eo fi t s a d v a n t a g e s s ot h eo v e r a l lq u e r ye x e c u t i o ns p e e dc a l lb er a i s e d f i n a l l y , w ev e r i f i e dt h ep e r f o r m a n c eo f t h e s et w oi m p r o v e da l g o r i t h mb ye x p e r i m e n t s f i n a l l yw er e v i e we n t i r ew o r k w ep o i n tt h ei n s u f f i c i e n to fo u rw o r ka n di n d i c a t et h eg o a lf o rt h e f u t u r er e s e a r c h k e yw o r d s ：d i s t r i b u t e dd a t a b a s e ，q u e r yo p t i m i z a t i o n ，s e m i - j o i n ，d i r e c t j o i n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：盟 一日期：z o l o 年岁月1 7 e l 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门 ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被 查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用 影印、缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名： 指导教师签名： 嗽枸 日期：工。f o 年s 月2 1e 1 日期：1 ql o 年占月2 7 日 中国以油人学( 华东) 硕j 二学位论文 第一章绪论 1 1 本文研究的背景与意义 随着计算机网络技术的迅速发展，数据库也逐渐网络化，随之产生了分布式数据库。 分布式数据库的数据分散地存储在不同地理位置站点的计算机上，而这些计算机都具有 独立处理数据的能力，可以执行局部应用，它们通过网络连接在了一起。这些分散的数 据从逻辑上来说是属于同一个系统的，是一个逻辑整体，由分布式数据库系统来进行统 一的管理，分布式数据库系统通过网络完成对各计算机上数据的操作，执行全局应用。 计算机网络的普及，使得分布式数据库的应用越来越广泛，而数据库的主要作用是 数据的存储以及数据的查询，因此数据查询的优化一直是分布式数据库的一个关键问题 0 4 1 。在集中式数据库系统中，一个查询优化算法的好坏是以执行查询的预期代价为依 据的，在分布式数据库系统中也同样如此。由于分布式数据库是集中式数据库在网络中 的扩展，因此分布式数据库系统的查询预期代价并不与集中式数据库完全相同。 在集中式数据库系统中，执行查询的预期代价【3 l 可以用处理查询的c p u 代价和计算 机i o 代价来进行衡量，但由于分布式数据库系统是由分散在网络中的多个站点上的计 算机组成，这就使得分布式数据库系统执行查询的预期代价除了要考虑c p u 代价和i o 代价外，还要考虑数据在网络上的通信代价。也正是由于分布式数据库系统的网络分布 性，不同的分布式查询优化算法的查询费用以及并行处理速度也是大不相同。因此，相 对于集中式数据库系统的查询优化，分布式数据库系统的查询优化则更加复杂、更加重 要，也更加具有研究价值。 分布式数据库系统的查询优化不仅直接影响分布式数据库系统的性能，而且还对增 加分布式数据库的效率和可靠性起着重要作用。自从分布式数据库系统形成以来，国内 外的大量学者就一直在对分布式数据库的查询优化进行着研究并提出了许多经典的算 法，但是很多算法都针对某一具体情况，具有很大的局限性，或者由于太过复杂而无法 推广到实际应用中。由于分布式数据库系统的网络复杂性，分布式数据库的查询优化还 有很大的研究空间以及实际意义。 1 2 研究现状 查询操作是数据库中最基本也是最常用的操作，通常用户最关心的问题也是如何高 效、快速的从数据库中查询出需要的数据，因此，对于查询操作的优化直是数据库系 第一章绪论 统的热点问题之，在分布式数据库系统中也不例外。由于分布式数据库系统的分布性 和冗余性，使得分布式数据库的查询优化相比集中式数据库而言更加多样、更加复杂， 也使得对分布式查询优化算法的研究更加受到关注。 无论是在集中式数据库查询还是在分布式数据库查询中，选择、投影和连接都是最 常用的三种操作。对于选择和投影，集中式数据库与分布式数据库对这两种操作的优化 处理并没有太大的区别，但是连接操作则不同。分布式数据库系统的数据是分散存储在 网络中的不同站点上的，而将这些数据进行连接操作必然会涉及到站点问的通信及数据 传输，因此对于连接操作的优化成为了分布式数据库查询优化的重要问题之一。对于连 接操作的优化，国内外的学者一直在进行着研究，也提出了各种各样的算法。尽管算法 多种多样，但却可以将这些算法分为两大类：基于半连接的查询优化算法和基于直接连 接的查询优化算法。 由于半连接操作【6 】可减少连接关系的元组大小，因此可减少网络站点间的数据传输 量。但是，使用半连接也会造成通信次数的增加和局部处理时间的延长，因为半连接操 作在站点问进行了两次关系的传输，而且在每次传输到不同站点后就分别执行一次连接 操作，这就在造成了局部处理时间的延长。假设r 是关系r 经过半连接操作后产生的 中间结果，那么当关系r 的元组数远远大于r ，的元组数时，半连接操作才比较适用。 在分布式数据库发展早期，就出现了以半连接作为查询优化策略的优化算法 s d d l 算法，该算法的出现主要是针对数据传输速率较低的广域网设计的。美国计算机 公司( c c a ) 于1 9 7 6 年到1 9 7 8 年间设计了世界上最早的分布式数据库系统原型s d d l ( s y s t e mo fd i s t r i b u t e dd a t a b a s e ) 【7 1 。该系统具有现在分布式数据库的基本理论，并且 可实现水平分片以及垂直分片。后来e w o n g 针对s d d 1 系统提出了减少通信开销的一 种方法，并设计出一个启发式算法；再后来p a b e m s t e i n 等人对w o n g 的算法作了进一 步优化，提出了半连接和缩减器的概念，这就是最初的s d d 1 算法，同时也成为半连 接优化算法中的个经典算法。s d d 1 算法利用了半连接缩减元组大小、减少数据传输 量的特点，按照一定的顺序将所有参加连接操作的关系进行缩减，最后将缩减后的关系 传输到某一指定站点进行最终的连接，得到查询的结果。由于对关系进行了缩减，所以 使得整个查询过程中的网络传输量大大减少。 另一类分布式数据库查询优化算法则没有使用半连接，而是使用的直接连接策略【8 】。 这主要是因为半连接操作会增加通信次数和局部处理时间，在以传输代价为优化目标的 情况下比较适用，而在高速局域网中，通常是以局部处理时间作为优化目标的，这时选 2 中国石油人学( 华东) 硕 ：学位论义 择直接连接策略会更加合适。 r * | 9 1 算法就是一种基于直接连接操作的查询优化算法。该算法的优化策略就是将所 有的连接全部都列举出来，并将连接操作分配到每个可能的站点，最后根据最优原则从 其中列举的连接操作中选择具有最佳效果的一种作为执行的方案。 早期的基于直接连接的算法还有1 n g r e s 算法，该算法是由e p s t e i n 在分布式 i n g r e s 数据库1 1 0 j 上实现的一种查询优化算法，是一种以分解作为优化策略的算法。 i n g r e s 算法主要有两个重要步骤，第一步称为分解，即将多关系查询分解为多个只含 有单个关系的查询；第二步称为排序，这一步需要执行每一个单关系查询，并使用启发 式方法选择一个初始执行方案，最后根据产生的中间结果的大小将所有查询进行排序， 产生执行所有查询的顺序。 后来又出现了利用站点依赖信息的算法【1 1 , 1 2 】以及基于h a s h 划分的算法【1 3 】。利用站 点依赖的算法首先要将进行连接操作的各个关系在几个不同的站点上进行分片，并且使 分片的片段满足站点依赖，然后分别在每一个站点上进行片段的连接操作，最终将各个 站点的结果进行合并就得到了最终的查询结果。由于该方法的各片段满足站点依赖，因 此在进行连接操作的过程中不需要进行站点间的数据传输。这种基于站点依赖信息的算 法是一种理想化的查询优化算法，而在多数情况下参加连接操作的各关系并不满足站点 依赖，在这种情况下就需要使用其他的方法进行处理，使参加连接的关系满足站点依赖， h a s h 划分就是一种很好的处理方法。h a s h 划分将关系元组的存储位置与它某一属性的 元组值通过h a s h 函数进行关联，通过h a s h 函数将具有相同h a s h 函数值的元组放在同 一站点，这样就将关系的多个片段放到了不同的站点上，而不同关系通过相同的h a s h 划分后，在连接时可保持站点依赖。这样就衍生出许多基于h a s h 划分的算法。p a r t i t i o n 算法 1 3 , 1 4 1 就是其中较为常用的一种。 p a r t i t i o n 算法利用h a s h 划分得到多元连接查询的多种划分方案，从中选择最优的一 种划分方案，将该方案的各关系进行划分并分配到各站点上，同时将其他参加查询的关 系各副本分别放到这些站点上。将各站点上的片段及关系副本进行连接，再将生成的结 果取并集就得到最后的查询结果。p a r t i t i o n 算法利用了分布式数据库分布性的特征，使 得数据库操作可并行进行，从而提高了查询的响应速度。 1 3 本文的工作及章节安排 本文的章节安排如下： 3 第一章绪论 第一章：绪论。介绍了本文的研究背景以及意义，并简单介绍了分布式数据库查询 优化算法的研究现状，同时给出本文的章节安排。 第二章：分布式数据库系统概述。详细介绍了分布式数据库系统的定义、特点以及 体系结构，并简单介绍了分布式数据库系统常用的操作方法。 第三章：分布式数据库的查询处理和优化。介绍了分布式数据库查询查询优化的目 标以及代价模型，并简单介绍了分布式数据库查询查询优化的一般策略。 第四章：基于半连接的查询优化算法研究。详细分析了半连接算法，并对其进行改 进；介绍并分析s d d 1 算法。 第五章：基于直接连接的查询优化算法研究。介绍并分析多种基于直接连接的查询 优化算法，并对p a r t i t i o n 算法进行了改进。 总结：总结本文的主要工作，并提出了下一步可能的研究目标及工作。 4 中固石油人学( 华东) 顾l ：学位论义 第二章分布式数据库系统概述 2 1 分布式数据库系统定义及分类 分布式数据库系统( d i s t r i b u t e dd a t a b a s es y s t e m ，简称d d b s ) 的研究始于2 0 世纪7 0 年代。由于网络技术的发展以及数据库应用需求的扩展，促成了分布式数据库系统的诞 生与发展。 分布式数据库系统是物理上分散而逻辑上集中的数据库系统( i , 2 1 。通过计算机网络， 分布式数据库系统将分散在不同站点上的多个逻辑单位连接起来，构成了一个统一的数 据库系统。更详细的讲，分布式数据库系统的数据并不是存放在一个站点上，而是分布 存储在系统的各个站点上的，而每一个站点都是一个独立的数据库系统，可独立的执行 数据库操作，但这些站点又不是孤立的，它们通过网络连接成一个逻辑整体，并且由分 布式数据库系统进行统一的管理1 1 5 1 。 分布式管理系统( d i s t r i b u t e dd a t a b a s em a n a g e m e n ts y s t e m ，简称d d b m s ) 是建立、 管理和维护分布式数据库的一套软件f 1 5 l ，它由四部分组成，结构如图2 1 所示。 图2 1 分布式数据库管理系统结构 f i 9 2 - 1t h ea r c h i t e c t u r eo fd i s t r i b u t e dd a t a b a s em a n a g e m e n ts y s t e m 5 第一二章分布式数据库系统概述 ( 1 ) l d b m s ( l o c a ld b m s ) ，是各站点上的数据库管理系统，功能就是建立和 管理各站点的局部数据库，实现站点的自治，执行局部应用以及全局查询的子查询。 ( 2 ) g d b m s ( g l o b a ld b m s ) ，称为全局数据库管理系统，主要的功能为协调全 局事务的执行，协调各局部d b m s 来完成全局应用，使数据库保持一致性，执行并发控 制，实现更新的同步，以及进行全局恢复等。 ( 3 ) 全局数据字典( g l o b a ld a t ad i r e c t o r y ，简称g d d ) ，它的功能与集中式数据 库的数据字典相似，除了存放与用户权限有关的定义以及数据完整性约束条件的定义 外，还存放全局概念模式、分片模式、分配模式的定义以及模式间映像的定义，这些模 式会在本章的2 3 中进行详细介绍。 ( 4 ) 通信管理( c o m m u n i c a t i o nm a n a g e m e n t ，简称c m ) ，分布式数据库中的数据 是由分布在网络中的不同站点组成的整体，通信管理的功能就是负责这些站间消息的传 递以及数据的传输，实现通信的功能。 分佰式数据库系统( 下面简称d d b s ) 通常可以按照两种方式进行分类，一种是按 照各站点数据库管理系统( 简称d b m s ) 的数据模型进行分类：另一种是按照分布式数 据库控制系统的类型进行分类。如果按照前者对分布式数据库系统进行分类的话，可分 为以下三种1 37 j ： ( 1 ) 同构同质型d d b s ：各站点的数据库的数据模型都是属于同一类型的( 例如都 属于关系型) ，并且数据库管理系统也都使用同一型号的。 ( 2 ) 同构异质型d d b s ：各站点上的数据库都采用了同一种类型的数据库模型，但 是它们的数据库管理系统的型号却都不相同。 ( 3 ) 异构型d d b s 各站点上数据库的数据模型均不相同，并且这些数据库的管理 系统也可能使用了不同的型号。 如果按照后者来分类，可分为以下三种： ( 1 ) 集中式d d b s ：这种d d b s 的全局控制信息只存放在一个站点上，其他站点均 没有此信息的副本。这种系统可以很容易地实现系统的一致性，相反，系统的稳定性却 比较低。因为一旦全局控制信息所在的站点出现问题，将会导致整个系统的崩溃。 ( 2 ) 分散型d d b s 与集中式d d b s 正好相反，分散型d d b s 在每一个站点上都存 有全局控制信息的一个副本。这种系统则具有很好的稳定性，当一个站点出现故障时， 系统仍然可以正常运行；但是如何保持所有站点上副本的致性却是该系统一大难题， 这通常需要有较复杂的设施来支持。 6 中国石油人学( 学东) 硕i 二学位论文 ( 3 ) 可变型d d b s ：这种d d b s 是上述两种系统的折中。在该系统中，一部分站点 存有全局控制信息的副本，而另一部分站点则不存放。其中，存有全局控制信息副本的 站点叫做主站点，而没有副本的那部分站点叫做辅站点。这种d d b s 具有较好的稳定性， 并且保持副本信息的一致性也不困难。 2 2 分布式数据库系统的特点 分布式数据库系统是在集中式数据库系统技术的基础上发展起来的，但并不是简单 将集中式数据库分散开来就可称为分布式数据库，它是具有自己独特特点的系统【1 5 1 。而 集中式数据库的许多概念以及技术，例如数据独立性、数据共享、冗余度、并发控制、 完整性、安全性以及恢复等，在分布式数据库系统中有了更进一步的拓展。 2 2 1 数据独立性 集中式数据库系统的数据独立性具有数据的逻辑独立性和物理独立性两种含义，作 用就是将用户程序与数据存储分隔开来，使用户在使用数据库时不必关心数据的全局逻 辑结构和存储结构。 分布式数据库系统的数据独立性，除了具有集中式数据库中所包含的数据逻辑独立 性及物理独立性外，还具有分布独立性的含义，通常也称为分布透明性。分布透明性指 用户不必去关心数据的逻辑分片情况、不必去了解数据的具体物理存放位置，也不必去 知道如何保持各副本的一致性，而且也不用去关心各个站点上数据库采用了哪种数据模 型、使用哪种型号的管理系统。 基于分布式数据库分布透明性的特点，用户在写应用程序时感觉就和集中式数据库 一样，感觉不到数据分布在网络中的多个站点上，而且当站点上的数据发生转移或者增 加了某些数据副本时，用户也不必去对应用程序进行任何修改。分布式数据库系统的数 据字典里保存有数据的分布信息，当用户对其他站点的数据进行访问时，系统会根据数 据字典罩所需数据的分布信息进行解释、转换和传送，这一系列过程都无需用户来操作， 对用户而言是完全透明的。 2 2 2 集中与自治相结合的控制结构 数据库中的资源是由多个用户所共享的，在集中式数据库中，为了保证数据库的完 整性及安全性，必须对共享数据库进行集中控制，并且需要有d b a 来专门负责管理监督 以及维护系统的运行。 7 第- 二章分布式数据库系统概述 在分布式数据库系统中，对于数据的共享可分为两种： ( 1 ) 局部共享。即在各站点的数据库中存储该站点上各用户的共享数据，这些数 据都是浚本地站点用户所常用的。 ( 2 ) 全局共享。也就是在各站点上除了存储本地的数据外还要存储来自其他站点 用户的共享数据，以支持系统的全局应用。 这样对于分布式数据库的控制机构也就可分为两个层次，即自治和集中。所谓自治， 就是指各站点的d b m s 可以独立管理本地数据库，而分布式数据库系统通过集中控制机 制来协调各站点d b m s 的工作，执行全局应用。一般来讲，不同的分布式数据库系统所 具有的集中及自治程度也各不相同，有的系统具有很高的自治程度，不设全局d b a ，而 有的系统集中控制程度很高，站点自治能力很弱。 2 2 3 数据冗余 在集中式数据库系统中，数据的冗余通常被视为是存储空间的浪费，而且还可能造 成数据副本的不一致问题，因此，在集中式数据库系统中都极力地减少数据的冗余。而 在分布式数据库系统中却恰恰相反，通常情况下，分布式数据库系统中的各站点都会存 储有同一数据的多个副本，而这么做对分布式数据库而言有以下两个好处： ( 1 ) 增强系统的可靠性和可用性 由于在分布式数据库系统中，多个站点都具有同一数据的多个副本，所以一旦某个 站点发生了故障，系统仍可直接对另一站点上的该数据的副本进行操作，系统也可正常 运行。 ( 2 ) 提高系统性能 在用户进行操作时，系统可从所有的数据副本中选择距离用户最近的副本进行操 作，这样做无疑会降低通信代价，提高整个分布式数据库系统的性能。 不过数据冗余给集中式数据库系统造成的诸多问题也仍然会在分布式数据库系统 中出现，但是随着磁盘容量的增大以及价格的下降，冗余数据所造成的存储空间浪费问 题逐渐得到了解决，但是冗余数据副本不一致的问题仍然是分布式数据库系统尚待解决 的重要问题之一。 总的来说，在分布式数据库系统中，数据的冗余使得检索更加方便并提高了系统的 查询速度，与此同时也增强了系统的稳定性，但由于同一数据在多个站点都存在副本， 这就使得在更新数据时不得不同时更新所有的副本以保证数据的一致性，因此也就相应 8 中国石油人学( 华东) 硕上学位论文 地增加了系统维护的负担。 2 3 分布式数据库系统的体系结构和组成 在分布式数据库系统中，通常可以将其模式结构分为全局外层、全局概念层、局部 概念层和局部内层，共四个层次 2 1 。其中全局外层由全局外模式组成，局部概念层由局 部概念模式组成，局部内层由局部内模式组成，而全局概念层则由全局概念模式、分片 模式和分配模式共三种模式组成。各个模式之间由数据库管理系统提供的多次映像来实 现转换，如图2 2 所示。 图2 - 2 分布式数据库系统模式结构图 。 f i 9 2 - 2d i s t r i b u t e dd a t a b a s es y s t e mm o d e ls t r u c t u r e ( 1 ) 全局外模式( g l o b a le x t e r n a ls c h e m a ) ：全局外模式是分布式数据库全局应用 的用户视图，是全局概念模式的子集。此处的视图与集中式数据库的视图具有相同的概 念，两者不同的是，集中式数据库的视图是从一个具体站点的数据库中得到的，而分布 式数据库的视图是从各站点上的数据库中抽取得到的。但是对于用户来讲，在操作数据 9 第- 二章分布式数据库系统概述 库时与使用集中式数据库是一样的。 ( 2 ) 全局概念模式( g l o b a lc o n c e p t u a ls c h e m a ) ：全局概念模式定义了分布式数 据库中数据的整体逻辑结构以及数据特性，使得数据对用户而言并没有进行分散存储， 仍然是集中在一起的。全局概念模式中所使用的数据模型应该易于向其他模式映射，通 常使用的为关系模型【5 1 。 ( 3 ) 分片模式( f r a g m e n t a t i o ns c h e m a ) ：每一个全局关系均可进行逻辑划分成多 个片段( f r a g m e n t ) ，或者叫作分片。 ( 4 ) 分配模式( a l l o c a t i o ns c h e m a ) ：全局关系被划分成片段后，一个片段在物理 上可以分配到网络的不同站点上【1 5 1 。通过分片模式片段与站点的对应关系可以得知这个 分布式数据库是否是冗余的。如果一个片段被分配到多个站点上进行存放，则称这个分 布式数据库是冗余的，而如果一个片段只分配到一个站点上进行存放，那么就称这个分 布式数据库是非冗余的。 ( 5 ) 局部概念模式( l o c a lc o n c e p t u a ls c h e m a ) ：全局概念模式经过逻辑划分后生 成一个或者多个片段，将这些片段分配到网络中的各个站点上，每一个站点上的片段的 集合就构成了局部概念模式。 ( 6 ) 局部内模式( l o c a li n t e r n a ls c h e m a ) ：局部内模式描述的是分布式数据库中 的物理数据库，与集中式数据库中的内模式很相像，不过在分布式数据库中这个描述并 不仅仅是对站点上本地数据的存储描述，而且还包含有对全局数据在站点的存储描述。 2 4 分布式数据库数据分片与数据分配 2 4 1 数据分片 数据分片，就是将关系划分为多个片段，使数据存放的基本单位不再是关系而是片 段，这不仅有利于按照用户的需求来有效的分配数据，而且还有利于控制数据的冗余度 【l 殂 o 分片有多种方式，包括水平分片、垂直分片、导出分片和混合分片，其中前两者是 分片方式中最基本的两种，而后两者则是较为复杂的两种分片方式。 ( 1 ) 水平分片 水平分片指的是将关系以一定的条件按行分为若干个互不相交的子集，即将关系r 分为若干子集r l 、r 2 、r n ，称每个子集r i ( i _ l ，2 n ) 为一个水平片段，而 关系r 的每个元组必须至少属于一个片段，这样关系r 可看作是所有子集的并集，即 1 0 中国石油人学( 华东) 硕i j 学位论文 r = r lu r 2 u u r n 。 ( 2 ) 垂直分片 垂直分片指的是将关系按列分为若干个子集，即将关系r 按列分为若干属性子集 r i 、r 2 、r n ，称每个子集r i ( i l ，2 n ) 为一个垂直片段。关系r 的重构可通过 连接操作来实现，i i i r = r i o o r 2 0 0 o o r n ，因此为了保证关系r 能够被恢复到原来的关 系，就需要垂直分片的各个片段都包含关系r 的码。 ( 3 ) 导出分片 导出分片指的是导出水平分片，导出分片利用水平分片的方法，但它所采用的水平 分片的条件并不是关系本身属性的条件，而是利用其他关系的属性条件。例如现有学生 选课关系s c ( 姘，甜，g r a d e ) ，那么导出分片的做法并不是按照学号( 蝌) 或者课程号( 蒯) 或者成绩( g r a d e ) 的某些条件进行分片，而是按照学生的年龄，比如年龄( a g e ) 2 0 岁和年龄( a g e ) 心0 岁来进行分片，年龄这个属性a g e 并不在学生选课关系s c 中，这个 属性可能是属于另外一个关系，比如学生信息关系s ( s 舞，n a m e ，a g e ) 。 ( 4 ) 混合分片 混合分片并不是使用单一方法进行分片，而是对上面所说的三种分片方式得到的片 段再继续按照另一种方式进行分片。例如上面所说的学生选课系统，先按照成绩( g r a d e ) 6 0 3 - ) - 和成绩( g r a d e ) t s e m i j o i n 时，通过半连接的方法可大大减少站点间的传输量3 0 l ，而实际 上这种情况是普遍存在的，这样就使得基于半连接查询优化有了应用的价值。 4 2 半连接算法的改进 对于连接操作胁xs = ( r o c s pxs = ( 尢工( s ”0 0 xs ，一般的基于传统半连接的优 化处理是在半连接缩减后直接连接，即将站点2 关系s 的属性x 做投影操作得到7 c x ( s ) ， 将其传输到站点l ，用半连接把关系r 缩减为关系r 0 后，再把l 如传送到站点2 与关系s 连 接得至l j r o oys ，然后将结果传输到查询的发起站点，整个过程如图4 - 1 所示。 中固石油人学( 华东) 硕_ j 二学位论文 站点l 关系r 站点i 关系r 查询发起站点 站点2 关系s x ) c d 站点2 关系s x ) c d 图4 1 半连接处理过程图 f i g4 - 1s e m i - j o i np r o c e s s i n g 通过以上处理虽然可以完成连接操作，但将r o 传送到站点2 的过程也伴随着大量的 数据传输，尤其是在大型数据库中要查询的属性较多、数据量较大的情况下，此过程的 数据传输量会更加大。针对此问题，本文对传统半连接算法进行了改进尝试，并对两种 算法的性能进行比较分析。 在进行算法分析之前，首先介绍选择因子及半连接代价公式的相关概念。 定义l 设r 、s 是两个关系，r 和s 半连接选择因子记为：s f s j ( r o c s ) 训( 兀x ( s ) ) c a r d ( s ) 其中c 砌( 兀x ( s ) ) 是关系s 在关系r 和s 的公共属性x 上投影所包含的不同元组的个 数，c a r d ( s ) 是关系s 的元组个数。 定义2 半连接代价公式记为 2 1 ： c o s t ( r o c s ) = s iz e j ( s ) ) = c a r d ( u x ( s ) ) 宰l e n g t h ( x ) 其中l e n g t h ( x ) 是属性x 定义的长度( 字节数) ； 设任意两个待连接关系r 和s 的连接属性为x ，关系r 和s 分别在站点1 和2 ，两个关系 2 1 第章婊于半连接的询优化算法研究 数据如表4 一l 与表4 2 所示。 表4 1 关系r t h b i e 4 1r e l a t i o n sr 属性a 属性b 属性x a lb lx 4 a 2b 2x 4 a 3b 3x 2 a 4b 3 x 2 a 5b 3 x l a 6b 4 x 5 表牝关系s t a b l e 4 - 2r e i a t i o n ss 属性x属性c属性d x lc ld l x ic 2d l x 2c 3d 2 x 2c 4d 2 x 3c 5d 3 在传统半连接算法中，投影操作冗z ( s ) 是将s 中x 属性筛选出来，不包括重复行，如 表4 3 所示，而在本文改进方法中，在作投影操作时并不去掉重复行，在此处将该操作 记为n 死( s ) ，如表4 - 4 所示。 表伯丌x ( s ) t a b l e 4 - 3 丌( s ) 中国石油人学( 华东) 硕l 学位论义 表n x ( s ) t a b l e 4 - 4n x x ( s ) 对于分别位于站点l 和站点2 的关系r 和s ，进行连接r o o s = ( r o c s ) o o s = ( r o o 兀爿( s ) ) o o s ，本文的改进方法描述如下： ( 1 ) 首先在站点2 上对s 作属性投影操作，得到n 兀x ( s ) ，将n 7 【x ( s ) 传输到站点l ， 根据n 兀，。( s ) 的x 属性的值对站点1 的r 进行缩减，缩减结果为r 0 。 ( 2 ) 接下来对r o 进行属性投影操作，得到n 兀x ( r 0 ) ，然后将n 兀x ( r o ) 传输到站点2 。 ( 3 ) 经过以上两步，r o 和n 兀x ( s ) 位于站点l ，x ( r 0 ) 和s 位于站点2 ，r 0o o n l t x ( s ) 和n 兀( r o ) s 这两个连接操作可在站点l 和站点2 分别进行，结果也不去掉重复行，两 者结果如表4 5 和表4 6 所示。此后的处理完全可以进行并行处理。如果要将结果在站点3 查看，则只需将两个站点的连接结果传送到站点3 作简单的对接就生成了所需要的结果 ( f i g r o o xs 的结果) ，无需再作数据库连接操作，如表4 - 7 所示，对接后的结果与l x s 的结果相同。 表4 - 5r 0 0 0 n ，tr ( s ) t a b l e a - 5r o q o n 2x ( s ) abr xs x a 3b 3x 2x 2 a 3b 3x 2x 2 a 4b 3x 2x 2 第l n j 章赫卡半连接的查询优化算法研究 a 4b 3x 2x 2 a 5b 3x lx l a 5 b 3 x 1x 1 表“n u ( r o ) s t a b l e 4 - 6 n n x ( r o ) s r xs xcd x 2x 2c 3 d 2 x 2x 2c a d 2 x 2 x 2 c 3d 2 x 2x 2 c 4d 2 x lx lc ld l x lx lc 2d l 表4 - 7r n 丌j ( s ) 与n 氕工( r o ) s t a b l e 4 - 7r o o n 万爿( s ) a n dn u j ( r o ) o o s abxcd a 3b 3x 2c 3d 2 a 3b 3 x 2 c 4d 2 a 4b 3 x 2 c 3d 2 a 4b 3x 2c ad 2 a sb 3x lc id l a sb 3x lc 2d l 可以看出，在过程( 2 ) 中并没有将整个r 0 传送到站点2 与s 进行连接操作，而只是将x 属性传送到站点2 ，这样当r 0 的元组数较多且涉及到较多属性时，与传统半连接算法将 r 与7 cy ( s ) 的连接结果r 兀x ( s ) 全部传输到站点2 进行最后连接的做法相比，可大大减少 2 4 中国石油人学( 华东) 硕i ：学位论义 数据的传输量，并且在改进算 法中r o o n x ( s ) 与n 尢( r 0 ) s 的两个连接操作是在两个不 同的站点上分别进行的，这样使整个过程的处理速度得到加快。 4 3 算法性能比较 下面假设要进行连接操作r o o s 。 站点l ：r ( 属性a ，属性b ，属性x ) 站点2 ：s ( 属性x ，属性c ，属性d ) 表4 - 8 关系信息表 t a b l e 4 - 8r e l a t i o n s h i pi n f o r m a t i o n 关系元组数关系大小 r1 5 0 0 9 0 0 0 0 s1 3 0 07 8 0 0 0 表”中间结果信息表 t a b l e 4 - 9i n t e r m e d i a t er e s u l