（计算机应用技术专业论文）分布式数据库多连接查询优化算法的研究.pdf

曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“) 本人郑重声明：此处所提交的博士口硕士囤论文分布式数据库多连 接查询优化算法的研究，是本人在导师指导下，在曲阜师范大学攻读博士 口硕士囵学位期间独立进行研究工作所取得的成果。论文中除注明部分外 不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中己明确的方式注明。本声明的法律结果将完全由本 人承担。 作者签名：刊婷嫡日期：2 0 j o 4 2 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“”) 分布式数据库多连接查询优化算法的研究系本人在曲阜师范大学攻读博 士口硕士团学位期间，在导师指导下完成的博士口硕士回学位论文。本 论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的 名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同 意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和 借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可 以公开发表论文的全部或部分内容。 作者签名：荆婶婷日期：2 0 1 0 6 2 聊繇伽缸矽 吼脚厂歹 分布式数据库多连接杏洵优化算法的研究 摘要 随着计算机网络技术和数字通信技术的蓬勃发展，传统的集中式数据库在处理大量数 据的查询效率和存储速度上具有了很大的局限性，从而不能满足人们的需求，因此具有数 据分布存储和分布处理特性的分布式数据库系统就迎刃而来。 由于数据具有分布的特点以及分布式数据库本身的复杂因素，因此查询问题就成为分 布式数据库中的关键问题，而影响查询技术的关键因素又是查询优化问题，查询优化的好 坏决定了查询效率的高低。与传统集中式数据库查询优化不同的是，分布式查询优化不仅 要考虑本地处理的代价，而且还要考虑远程的通信代价。在分布式数据库查询中，多关系 连接操作是最常用的操作，也是花费通信代价最大的操作，因此多关系连接查询优化就成 为人们研究的热点和问题。虽然很多研究者在这方面做了很多的工作，但分布式数据库查 询优化在很多地方还存在着不足，例如：对于多个关系采用半连接操作时，如何选择一个 最有益的半连接执行顺序，以及如何选择最有益的半连接，如何利用分布式数据库的特性 提高算法的并行执行能力等。 本文首先介绍了分布式数据库系统的一些基本理论，例如：分布式数据库系统的发展 历程、定义、分类、组成、模式结构及功能；然后介绍了分布式查询优化技术以及常用的 连接策略；最后以传输代价最小为目的，针对多关系在采用半连接策略连接时存在的问题， 在以往算法的基础上提出了一种基于有向无循环图的查询优化算法。该算法通过代价估算 来选择最有益的半连接策略，并通过设置节点的入度数和动态参数表不断地更新有向无循 环图来选择最优节点，从而获得最优的半连接执行顺序，并对每个关系进行了充分地缩减， 而且该算法隐含并行操作。最后以一个小型的教学管理系统为实验平台，通过实验验证了 有向无循环图算法的性能。 关键词：分布式数据库：查询优化；多关系连接；半连接策略 分布式数据库多连接布询优化算法的研究 a b s t r a c t w i t ht h e d e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g ya n dd i g i t a lc o m m u n i c a t i o n t e c h n o l o g y , t h et r a d i t i o n a lc e n t r a l i z e dd a t a b a s eb e c o m e sm o r ed i f f i c u l ti nd e a l i n gw i t ht h eq u e r y e f f i c i e n c ya n ds t o r a g es p e e d a st h et r a d i t i o n a lc e n t r a l i z e dd a t a b a s ec a nn o tm e e tp e o p l e sn e e d s ， s ot h ed i s t r i b u t e dd a t a b a s es y s t e mc o m e so n i nd i s t r i b u t e dd a t a b a s es y s t e m ，d a t ai ss t o r e da n d h a n d l e di nd i s t r i b u t e df o r m t h eq u e r yi s s u ei st h ek e yi s s u ei n t h ed i s t r i b u t e dd a t a b a s e b e c a u s et h ed a t ai nt h e d i s t r i b u t e dd a t a b a s ei ss t o r e di nd i s t r i b u t e df o r ma n dt h ed a t a b a s es t r u c t u r ei sv e r yc o m p l i c a t e d t h ek e yf a c t o rw h i c ha f f e c t s q u e r yt e c h n o l o g yi sq u e r yo p t i m i z a t i o np r o b l e m ，b e c a u s et h e e f f i c i e n c y o fq u e r y o p t i m i z a t i o nd e t e r m i n e st h eq u e r ye f f i c i e n c y t h ed i s t r i b u t e dq u e r y o p t i m i z a t i o ni sd i f f e r e n tf r o mt h eq u e r yo p t i m i z a t i o no ft h et r a d i t i o n a lc e n t r a l i z e dd a t a b a s ei nt h e o b j e c t i v eo fq u e r yo p t i m i z a t i o n i tn o to n l yt a k e si n t oa c c o u n tl o c a lp r o c e s s i n gc o s t ，b u ta l s o c o n s i d e r st h ec o s to fl o n g - r a n g ec o m m u n i c a t i o n a st h em u l t i r e l a t i o n sc o n n e c t i o no p e r a t i o ni s t h em o s tc o m m o n l yu s e di nd i s t r i b u t e dd a t a b a s e q u e r y a n di ta l s oc o s t st h e l a r g e s t c o m m u n i c a t i o nc o s t ，t h e r e f o r ei tb e c o m e st h em o s ti m p o r t a n tp r o b l e mi nq u e r yo p t i m i z a t i o n a l t h o u g hm a n yr e s e a r c h e r sh a v ed o n e al o to fw o r ki nt h i sa r e a , t h ed i s t r i b u t e d q u e r y o p t i m i z a t i o ni ss t i l ln o te n o u g hi ns o m ep l a c e s ，f o re x a m p l e ，h o wt os e l e c tt h em o s tb e n e f i c i a l s e m i - j o i ne x e c u t i o ns e q u e n c e ，h o wt os e l e c tt h em o s tb e n e f i c i a ls e m i - c o n n e c t i o na m o n gm a n y s e m i c o n n e c t i o n s ，a n dh o wt ou s et h ec h a r a c t e ro ft h e d i s t r i b u t e dd a t a b a s et oi m p r o v et h e p a r a l l e le x e c u t i o nc a p a b i l i t i e so fa l g o r i t h m i nt h i sp a p e r ，t h eb a s i ct h e o r i e so ft h ed i s t r i b u t e dd a t a b a s es y s t e ma r ef i r s t l yi n t r o d u c e d ， s u c ha st h ed e v e l o p m e n tp r o c e s s ，t h ed e f i n i t i o n ，t h ec l a s s i f i c a t i o n ，t h ec o m p o s i t i o n ，t h em o d e s t r u c t u r ea n dt h ef u n c t i o no ft h ed i s t r i b u t e dd a t a b a s e s e c o n d l y , t h et e c h n i q u eo ft h ed i s t r i b u t e d q u e r yo p t i m i z a t i o na n dt h em o s t l yu s e dc o n n e c t i o ns t r a t e g ya r ei n t r o d u c e d t h e na na l g o r i t h m b a s e do nad i r e c t e dn o n - c y c l i c g r a p hi sp r o p o s e d i nt h ea l g o r i t h m ，a no p t i m a ls e m i - j o i n e x e c u t i o ns e q u e n c ei so b m i n e db ys e t t i n gt h en o d ed e g r e e ，e s t i m a t i n gt h ec o s t ，u p d a t i n gt h e g r a p ha n dt h ed y n a m i cp a r a m e t e rt a b l ec o n s t a n t l y a tt h es a l t l et i m e ，t h ea l g o r i t h mi m p l i e s p a r a l l e lo p e r a t i o n s i nt h ee n d ，as m a l lt e a c h i n gm a n a g e m e n ts y s t e mi si n t r o d u c e di no r d e rt o v e r i f yt h ep e r f o r m a n c eo ft h ea l g o r i t h m k e y w 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 ；m u l t i p l er e l a t i o n sj o i n ； s e m i - j o i ns t r a t e g y 分布式数据库多连接商询优化算法的研究 目录 第一章绪论1 1 1 研究背景1 1 2 研究现状1 1 3 论文组织结构3 第二章分布式数据库系统5 2 1 分布式数据库系统的发展历程5 2 2 分布式数据库系统的定义6 2 3 分布式数据库系统的组成7 2 4 分布式数据库系统的分类7 2 4 1 按d d b s 的控制方式分类8 2 4 2 按节点结构分类9 2 5 分布式数据库管理系统的功能9 2 6 分布式数据库系统的模式结构1 0 2 7 本章小结1 0 第三章分布式数据库查询优化技术1 2 3 1 分和式数据库查询处理的过程1 2 3 2 分布式数据库查询优化概述1 2 3 2 1 查询空间13 3 2 2 查询策略15 3 2 3 查询代价模型1 5 3 3 分布式数据库多连接查询优化策略1 6 3 3 1 基于直接连接的策略1 6 3 3 2 基于半连接的策略1 6 3 3 3s d d l 算法18 3 4 本章小结1 9 第四章基于有向无循环图的多连接查询优化算法2 0 4 1 算法理论基础2 0 4 2 算法思想2 3 4 3 算法描述2 3 4 4 算法实例分析2 5 4 5 算法理论分析2 9 4 6 本章小结3 1 分布式数据库多连接奄询优化算法的研究 第五章实验的设计和算法性能的分析3 2 5 1 实验设计3 2 5 2 实验结果和性能分析3 2 5 2 1 教学管理系统概述3 2 5 2 2 教学管理系统平台下算法性能测试和分析3 4 5 3 本章小结3 5 第六章结论与展望3 6 6 1 结论3 6 6 2 展望3 6 参考文献 3 8 在校期间发表的学术论文4 0 致 谢4l i v 分布式数据库多连接奄询优化算法的研究 1 1 研究背景 第一章绪论 近年来，随着计算机网络技术和数据库技术的发展，以及人们对数据库的迫切需要， 分布式数据库技术成为人们关注的焦点，很多研究者对它进行了大量的研究，而其中最关 注的是分布式数据库查询优化问题j 。 在传统的数据库中数据是集中存放在一个数据库中的，数据独立性【2 3 】只具有物理独立 性和逻辑独立性，而在分布式数据库中数据除了具有物理独立性、逻辑独立性外还具有分 布独立性【4 j 。分布式数据库查询过程中，数据的分布与冗余，不仅使查询要考虑站点间的 通信代价，而且还要提高查询的并行执行能力、提高执行速度，缩短局部响应时间。因此， 分布式数据库查询优化的目标1 4 1 也与传统的数据库优化目标不同，它不仅要考虑c p u ，i o 等局部代价，同时还要考虑数据在网络中传输的通信代价。可见，分布式查询优化技术是 一个非常复杂的问题，它存在很多问题有待人们去研究与探讨f 5 d 们。 多关系进行连接操作是分布式数据库中最难以解决的问题，由于连接操作具有对称 性，因此对于多关系连接可以存在很多种连接方法，而且每种连接方法产生的代价开销也 是不同的，因此如何寻找一种使查询开销最小的连接方法，是分布式查询优化中要考虑的 问题，对于关系的连接顺序也形成了很多的研究算法，但是这些算法只是考虑了关系的连 接顺序，而没有考虑到如何对每个关系进行缩减，而使连接时产生的代价更小。连接操作 一般分为直接连接操作和半连接操作，直接连接操作注重局部处理，而半连接操作注重传 输代价的减少。查询优化可以分为静态优化和动态优化j ，静态优化是在查询执行前进行 优化：动态优化是根据查询过程中中问结果的大小边连接边优化，但动态优化需要事先估 计中间结果的大小，需要进行统计与估计。本文针对多关系进行连接操作，采用动态优化 和半连接策略来减少传输代价，从而使查询总代价达到最小、提高数据库查询效率，因此 本课题具有一定的研究价值。 1 2 研究现状 在分御式数据库系统中查询优化问题影响了整个系统的查询效率，继而影响了整个系 统的整体性能。所以伴随着分布式数据库系统的出现，查询优化问题也成了国内外研究者 关注的问题。 分和式查询优化的目标就是降低查询时产生的总代价，包括通信费用和局部处理费 用。在实施查询优化过程中最关键的是局部的优化以及查询执行策略的优化【1 2 】。所谓局部 分布式数据库多连接布洵优化算法的研究 优化就是对局部数据库进行优化，以达到缩短响应时间；查询执行策略的优化就是在多种 执行方案中选择一个最优的方案，以使传输费用达到最小。数据的传输量是一个关键因素， 它影响传输费用和传输时间的歼销，因此查询策略优化算法就集中到如何实现减少数据传 输量。而影响数据传输量最关键的因素是数据的连接操作，因此国内外学者一直在进行这 方面的研究，也形成了很多不同的算法【乃。19 1 。连接查询策略一般分为两种：一种是基于半 连接策略的算法，另一种是基于直接连接策略的算法。 a p e r s ，h e v n e r 和y a o 提出了半连接方法。它的思想是在连接操作中传输的不是整个关 系，而只是其中的一部分，因此它可以减少中问结果的大小和数据量的大小。但半连接技 术也存在着不足之处，它可能会增加通信次数和延长局部处理时间，因此半连接技术只适 合用于优化传输代价，而不是局部处理代价的情况。由于半连接技术可以减少传输的数据 量，因此很多研究算法都是基于这种方法。 1 9 7 8 年由美国研制的s d d 1 是第一个分布式数据库原型系统。s d d 1 算法【2 0 】采用的 是多关系半连接方法，它是在爬山算法【l2 】上提出的。它的基本思想是采用半连接技术来进 行连接操作，并且每个关系在各个站点上没有副本，而且不进行分片。算法通过估算半连 接的连接费用，并采用动态穷尽的搜索方法寻找最优的半连接顺序。此算法的优点是能够 优化总代价和总时间，缺点是当节点很多时，这种搜索方法就会增加时间的开销。 另一种就是没有使用半连接策略的直接连接算法，它在传输过程中传输的是整个关 系，它主要适用于局部处理代价为主要考虑因素的情况。直接连接优化算法一般可以分为 以下几种 2 1 , 2 2 】： 第一个是基于站点依赖信息的算法。事先查询所需要的关系在各个不同的站点上先进 行分片，如果连接操作的各个关系满足站点依赖，则对每个站点上的片段进行连接操作， 最后拼装连接结果。 第二个是基于数据分片和数据复制的算法。这种算法的思想是先把其中的一个关系分 成多个片段，然后把这些片段分布到指定的站点上，最后把查询中所用的其它关系复制到 这些站点上去进行连接操作。 第三个是基于哈希划分的算法。哈希划分就是建立关系元组的存储位置与它每一个属 性的函数关系，并且将具有相同函数值的元组存放到一个地方。这样，每个关系经过哈希 划分就被水平分片到不同的站点上进行存储，具体存储到哪些不同的站点上则是由哈希函 数值决定的。不同的关系在进行连接时的条件是相同的哈希函数值，这样各个关系则保持 了站点依赖。但哈希划分存在一个情况，就是等值连接条件中并非所有的属性都与原哈希 划分时的属性一致，这时候就不满足站点依赖，我们就需要对关系元组在该属性上再重新 做一次哈希划分。可见，如果多次进行重哈希划分会增加通信代价，针对这种情况，我们 解决的方法是在执行前调整好关系的连接顺序，使那些连接属性能够保持站点依赖的关系 先进行连接。 针对多关系进行连接顺序的优化，很多研究者将启发式算法运用到查询优化中去，主 2 分布式数据库多连接布询优化算法的研究 要有最小生成树算法【2 3 1 。它的主要思想是先将所有的关系节点初始化为一个无向连通图， 图中的每个节点都是一个根节点，然后从连接查询图中选择一条代价最小的边，如果将此 边加入到无向连通图中，不会形成回路，则将这条边加入，否则舍弃这条边，继续选择下 条边，直到所有的关系节点都在同一个连通分量上。最小生成树属于一种贪心算法，使用 这种方法操作比较简单，而且如果贪心策略选择的好，也能得到最优的解，只是它比较适 用于关系数目比较少的情况。 为了解决查询优化过程中关系数目比较多的问题，不少研究者也将遗传算法【2 4 - 2 8 】、粒 子群算、法【2 9 1 、蚁群算法【3 0 】运用到分布式查询优化中去，其中遗传算法是应用最广的算法。 它是由美国的j h o l l a n d 提出来的，它属于一种随机化的搜索方法。遗传算法一般包括以 下几个步骤：随机产生一个初始状态；对每一个解评估它的适应度值：繁殖后代；下一代 的处理。遗传算法具有三个特点：全局优化能力、隐含并行操作和适用于大量关系的搜索。 遗传算法在查询优化中将是最理想的算法，如果把它成功的运用到查询中，将会改变传统 算法中查询效率低，全局优化不足的问题。现在对于遗传算法也有不少的研究，并获得了 初步成功，也形成了各种算法，但还有很多问题有待解决，例如编码技术、如何构造一个 好的适应度函数、如何设计各种参数算子以及条件终止的选择。此外它只适合连接查询图 不带环的情况。虽然遗传算法有很多局限性，但它在解决复杂的优化问题有很大的潜力， 它的研究空间也会越来越大，在分布式数据库查询优化中具有很大的研究价值。 对于分布式查询优化技术及其算法，各有其优缺点，在不同的应用情况下都可以发挥 其优势，因而不能说谁是最好的，我们所要寻找的优化不一定是最优的，但却是最适合应 用环境的需要。随着网络的迅速发展和计算机性能的提高，查询策略也会越来越复杂，查 询优化也会越来越优化。 1 3 论文组织结构 本文是在对现有的分布式查询优化算法进行分析与总结的基础上，针对分布式数据库 多关系进行半连接进行了研究。论文组织结构如下： 第一章主要阐述了课题的研究背景和选题意义、研究现状。 第二章对分布式数据库系统的一些基本理论知识进行了详细的阐述，包括分布式数 据库系统的发展历程、定义、组成、分类、功能、模式结构。 第三章对分布式数据库查询优化技术进行了详细的介绍，包括分布式查询处理的过 程、查询优化的过程，并讨论了常用的多关系连接查询优化策略。 第四章针对多关系连接操作采用半连接策略时存在的不足进行了改进，提出了一种 基于有向无循环图的多关系连接查询优化算法。 第五章以一个小型的教学管理系统为实验平台，通过对比实验，验证了算法的性能。 第六章总结了课题已经完成的工作，并指出了需要进一步完善的地方，以及下一步 分布式数据库多连接布洵优化算法的研究 更深入的研究方向。 4 分布式数据库多连接杏询优化算法的研究 第二章分布式数据库系统 - 2 1 分布式数据库系统的发展历程 随着网络技术和数字通信技术的迅速发展，人们对数据库技术有了更高的要求，期盼 一种新的数据库系统的出现，这种系统不仅具有传统数据库的特点，而且还能够弥补传统 数据库的不足，能够处理那些分布在不同区域的数据，因此分布式数据库就应运而生，成 了近年来研究的热点，成为计算机技术最活跃的研究领域之一。分布式数据库是计算机网 络和数据库技术相结合才产生的，它是建立在传统的数据库基础上的。 从2 0 世纪7 0 年代中期开始，分布式数据库系统( 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 ) 就成为人们研究的对象，它的发展历程经历了3 0 多年，其中也取得了很多的研究成果和 技术方法，一些基本的问题已经被提出并得到了解决。 分布式数据库系统的产生主要来源于两个方面：一个是商业需求，一个是应用环境的 需求。其中商业需求主要因素有以下几条【3 i 】： ( 1 ) 现代企业需要这种分布式的管理模式 对于一些大型的企业或公司、集团、行业来说，它们有些部门是分布在全国各个地方， 虽然这些部门分布在不同的地方但它们之间的关系却很紧密。它们之间的管理，不仅要有 对自己内部的局部管理方式，而且还要有全局的协同管理方式。传统的数据库在这种企业 管理方式中就会表现出局限性，因此迫切需要一种新的能够实现局部处理和全局处理协调 工作的分布式数据库系统。 ( 2 ) 分布式数据库系统具有较高的性能价格比 在现代企业管理中，由于应用需求的不断增大，企业规模也逐渐的增大，而处理的数 据也随着应用的需求而逐渐增大，如果采用传统的集中式数据库系统来处理这些数据时， 则对主机的性能要求非常高，有些原有的机器或许被淘汰。如果采用分布式数据库系统， 充分利用这些分布的已有设备，使他们联合工作，可以获得更高的性能价格比。 其次，分布式数据库系统有一定的应用环境的需求： ( 1 ) 硬件的发展 电子元器件的集成度和性能大幅度提高、价格不断下降以及微机的迅速发展，不论是 在数量上还是应用上，都为分布式数据库系统提供了物质基础。 ( 2 ) 计算机网络技术的普及 随着网络技术的发展和通信技术的进步， ( 3 ) 数据库应用系统的普及 特别是关系数据库系统成为主流产品后， 领域。 人们看到了分布式数据库系统的应用前景。 分布式数据库系统的研究成为迅速崛起的新 分布式数据库多连接杏询优化算法的研究 分布式数据库系统无论在军事上还是民用上，都有着广泛的应用需求，各国也都越来 越关注对分布式数据库系统的研究。例如： ( 1 ) 第一个分布式数据库实验系统s d d 1 ，于1 9 7 6 年1 9 7 9 年由美国的c c a 公司在 d e c - 1 0 机上进行了实现。 ( 2 ) p o r e l ，由德国的斯图加特大学经历1 1 年研制成。 ( 3 ) s y s t e mr 和r ，由i b m 公司研制成。 ( 4 ) s i r i u s ，由法国的i n r i a 研制成。 ( 5 ) i n g e r s ，由美国的加州大学b e r k e l e y 分校研制成，其后荷兰阿姆斯特丹大学研制 成扩展n g e r s 。 ( 6 ) s i t i u s - d e l t a 由法国的i n t i a 研制成，m i c r o b e 由i m a g 研制成。 从2 0 世纪8 0 年代初期开始，我国也逐步开始了对分布式数据库系统的研究。在一些 国内研究者的研究成果下，我国也建立和实现了几个各具特色的分布式数据库系统，在推 动分布式数据库技术发展的过程中起了巨大的作用。例如： ( 1 ) c p o r e l ，由中国科学院数学研究所和上海科技大学及华东师范大学合作实现。 ( 2 ) l s z ，由南京大学设计的异构型分布式数据库管理系统。 ( 3 ) s u n d d b ，由东南大学设计和实现。 2 2 分布式数据库系统的定义 分布式数据库系统是计算机网络技术与数据库技术的有机结合，它通过使用计算机网 络将物理上分散而管理和控制又需要不同程度集中的多个逻辑单位连接起来，共同组成一 个统一的数据库系统。物理上分散是指此网络中的各个结点可能分布在一个很大的区域， 也可能分布在一个较小的区域，计算机范围可以从微型计算机到大规模计算机，甚至到巨 型计算机。逻辑上集中是指各个结点之间在逻辑上是一个整体，对全局事务的处理是在统 一逻辑框架上进行的。 分布式数据库系统由分布式数据库( d i s t r i b u t e dd a t a b a s e ，d d b ) 和分布式数据库管理系 统( d d b m s ) 两部分组成。其中分布式数据库可以看作一个物理上分散而逻辑上统一的数据 共享集合；分布式数据库管理系统则是管理分御式数据库系统的软件。 从以上分布式数据库系统的定义，可知分布式数据库系统具有如下4 个特点： ( 1 ) 数据在物理位置上具有分布性 分布式数据库的数据不像是集中式数据库一样全部存储在一个站点上，而是分散存储 在多个站点上，并且这些站点通过计算机网络组合在一起。 ( 2 ) 数据在逻辑上具有关联性 分布式数据库的数据虽然是分布在不同的站点上，但它们在逻辑上是一个整体，并由 高级的数据库管理系统( 分布式数据库管理系统，d d b m s ) 进行统一控制。 6 分布式数据库多连接杏询优化算法的研究 ( 3 ) 场地自治性 采用本地自治，每个站点都有能力控制本地数据、管理安全性、记录事务同志、当本 地发生故障时加以恢复、并在任何中心站点或协调站点不能操作时为本地用户提供对本地 数据的完全访问。 ( 4 ) 各个场地间具有相互协作的联系 虽然各个场地具有自治性，但它们又可以相互协作构成一个整体，用户可以在任何一 个场地进行全局应用。 2 3 分布式数据库系统的组成 分布式数据库系统是一种特定的计算机应用系统，它通过数据的集中与分散的统一， 完成企业的分层管理。一个分布式数据库系统的组成部分包括硬件、软件、数据和相关的 人员f 3 i 】。 ( 1 ) 硬件 分布式数据库系统所依赖的硬件环境是分布的，因此各个站点上所选择的c p u 、内存 和外存的性能必须要考虑满足本地和全局的应用，同时还要考虑选择合适的通信设备，以 满足各个站点之间的通信。 ( 2 ) 数据 分布式数据库中的数据分为局部数据和全局数据。局部数据是指只提供本站点的局部 应用所需要的数据，以局部数据库( l d b ) 的形式存放在站点中：全局数据是以全局数据库 ( g d b ) 形式分散存放在各站点中，可以被多个站点访问。 ( 3 ) 软件 各个站点为了实现本站点的自治性，必须选择一个适合的操作系统和本地d b m s ，同 时还必须配备高层的d d b m s ，来完成全局事务的处理。 ( 4 ) 人员 全局用户、局部用户、全局数据库管理员( g d b a ) 、局部数据库管理员( l d b a ) 、系统 分析员、应用程序员。 2 4 分布式数据库系统的分类 一般分布式数据库系统的分类有两种，一种是按d d b s 的控制方式分类；另一种是按 照节点的结构进行分类。 7 分布式数据库多连接奄洵优化算法的研究 2 4 1 按d d b s 的控制方式分类 ( 1 ) 紧耦合式d d b s 紧耦合式d d b s 把全局控制信息全部放在一个站点上，这个站点称为中心站点。其它 站点如果要访问远程站点上的数据，需要先访问中心站点，以来确定所需要访问远程数据 的位置，并且由这个中心站点负责完成全局事务的协调和局部数据库转换等控制功能。这 种控制方式最大的优点是容易实现数据的一致性和完整性。缺点是容易产生访问瓶颈，一 旦中心站点受损，整个系统就会崩溃，系统效率不高，可靠性差。系统结构图如下图2 1 所示。 g i o b a lu s e r 图2 - l紧耦合式d d b s ( 2 ) 分散式d d b s 在这种系统中，每个站点都包含全局控制信息的一个副本，每个站点都能完成全局事 务的协调和局部数据库转换，每个站点既是全局事务的参与者又是协调者。任何对远程数 据的请求，都可以通过广播式等方式传播到其它节点。这种系统具有较好的可靠性和可用 性，并行性好。缺点是保持数据的一致性很难，而且实现难度大，需要有复杂的设施。系 统结构图如下图2 2 所示。 8 分布式数据库多连接有询优化算法的研究 g i o b a iu s e rl o c a iu s e r g i o b a iu s e rl o c a lu s e r 分布式数据库管理系统 局部数据年管理系统 上 局部数据库 分布式数据库管理系统i 局部数据库管理系统 i 1l 局部数据库 图2 - 2 分散式d d b s ( 3 ) 主从型d d b s 在这种类型的d d b s 中，将d d b s 系统中的站点分成两类，一类具有全局控制信息， 称为主站点，可以接受全局访问：一类没有全局控制信息，称为从站点，只能为主站点提 供数据服务。当主站点的个数等于1 时为紧耦合式d d b s ，当d d b s 中全部站点都是主站 点时为分散式d d b s 。这种系统在层次控制结构中具有灵活性，但它的设计非常复杂，必 须通过对用户进行充分的应用调查之后，才能使设计的系统满足用户的应用需要。 2 4 2 按节点结构分类 分布式数据库系统如果按照各节点的结构来划分的话，可以分为同构型和异构型。 其中同构型可以分为以下两种： ( 1 ) 同构同质型：每个站点的数据模型和型号都是相同的： ( 2 ) 同构异质型：每个站点的数据模型相同，但是型号不同； 其中异构体现在以下几个方面： ( 1 ) 硬件的异构：不同站点的c p u 或硬件体系结构不同； ( 2 ) 网络的异构：不同网段的结构有所差异等； ( 3 ) 软件的异构：不同站点的操作系统、数据模型和型号不同。 2 5 分布式数据库管理系统的功能 分布式数据库管理系统( d d b m s ) 是支撑分布式数据库的建立、维护和使用以及站点通 信等的管理软件。通常d d b m s 具有如下功能【3 1 】： ( 1 ) 分御式数据库定义功能 9 分布式数据库多连接商洵优化算法的研究 d d b m s 必须提供定义数据库结构及其数据分布等功能。 ( 2 ) 分布式查询处理功能 由于分布式数据库系统中的数据分布在不同的站点上，数据的查询处理会很复杂，数 据在网络上传输也要花费很高的代价，如何减少查询处理的代价是查询处理的任务。此外 在进行查询处理之前还要进行查询分析，即弄清该查询所需要的数据以及这些数据存储在 哪些站点上，若这些数据有多个副本，应该选择哪个副本可以使查询处理的代价最小。 ( 3 ) 分布式数据库维护功能 由于分布式数据库系统中的数据都有大量的副本存在，因此d d b m s 必须维护数据的 完整性和数据的一致性。 ( 4 ) 调度处理功能 只有与各站点进行通信，才能获得相关状态信息，以完成必要的数据传输。 2 6 分布式数据库系统的模式结构 分布式数据库的模式结构可以分为以下五种：全局应用模式、全局表示模式、节点外 模式、节点模式、节点内模式。 ( 1 ) 全局应用模式 全局应用模式也称为全局外模式，它是面向某个特定应用用户的全局数据库数据视 图，也称为全局视图。全局应用模式是全局表示模式的逻辑子集。 ( 2 ) 全局表示模式 全局表示模式也称为全局模式，是对全局数据库的逻辑描述。 ( 3 ) 节点外模式 是面向本节点特定应用用户的局部数据库数据视图。它是对本地局部数据库的部分数 据的描述。 ( 4 ) 节点模式 主要是对本地局部数据库的逻辑描述，如果本节点包含局部数据库以外的数据，还要 对这些外部数据和全局数据库的关联进行描述。 ( 5 ) 节点内模式 主要是对本地局部数据库的存储描述，如果本节点包含局部数据库以外的数据，还要 对这些外部数据的存储进行描述。 2 7 本章小结 本章从六个方面对分布式数据库系统进行了详细的阐述，包括它的发展历程、定义、 分类、组成，以及分布式数据库管理系统的功能、模式结构。通过本章，我们对分布式数 1 0 分布式数据库多连接布洵优化算法的研究 据库系统有了更清晰的认识。 分布式数据库多连接布询优化算法的研究 第三章分布式数据库查询优化技术 分布式查询处理是用户和分布式数据库的接口，是分布式数据库系统的主要问题之 一。由于分布式数据库中数据具有分布存储的特性，也使得查询优化问题比较复杂。查询 策略的不同，也会产生不同的通信代价、响应时问和并行执行能力。分布式查询处理主要 是通过分析查询处理的过程，为查询优化寻找一个好的策略，最后把这个策略转换成对一 些基本关系的操作。主要问题就是如何找到一个最好的策略，使查询的总代价最小，而影 响优化的关键问题是：数据的分布、通信代价、以及局部处理的代价问题。 3 1 分布式数据库查询处理的过程 查询处理就是把给定的查询语句转换成对最底层数据进行操作的过程，查询处理主要 有四个过型3 2 l ：查询分解，数据分配，全局优化，局部优化。 ( 1 ) 查询分解 查询分解就是把查询请求用关系代数的形式表示出来，在这个过程中，查询语句要经 过语义分析，尽可能删去不正确的查询语句，并简化正确的查询语句。 ( 2 ) 数据分配 查询对象一开始是全局的各个关系，而不是它们在站点上的分片，而数据分配这一过 程就是把全局关系分成各个片段。关系分片可以分为水平分片和垂直分片，其中水平分片 可以通过选择操作来进行，而垂直分片可以通过投影操作来进行。 ( 3 ) 全局优化 在分布式环境中，全局优化涉及的是多个站点上的关系的操作，而局部优化只是对单 个站点上查询的优化。全局优化是指对关系片段的查询，查询优化的目标是寻找一个对查 询来说接近最优的策略，也就是如何寻找一个各个片段查询执行的顺序，使得查询代价最 小。 ( 4 ) 局部优化 这种优化类似于集中式数据库的查询优化技术。 3 2 分布式数据库查询优化概述 所谓查询优化，是指产生一个查询执行计划的过程，这个执行计划代表了一个查询策 略的执行，并能够使查询的总代价达到最小。一个查询优化器从软件模型上来看，可以分 为三个组成部分：查询空间、代价模型和查询策略。查询- 空f b j 作为查询的输入条件，它 是由一些执行计划组成的集合，可以通过关系数据库中的一些转化规则得到查询空间。成 1 2 分布式数据库多连接布洵优化算法的研究 本代价模型可以预测某一个执行计划的成本。为了使成本代价模型更加精确，我们必须熟 悉分布式执行的环境。通过分析成本代价模型，查询优化器可以确定最好的查询策略。查 询优化的过程如下图3 1 所示。 3 2 1 查询空间 图3 1 查询优化过程 可以用一棵算符树来形象的描述查询执行计划，通过这棵算符树我们可以得到操作执 行的顺序。对于某一个查询，可以用转换规则来产生查询的算符树，并用算符树来表示它 的查询空间。由于连接操作是查询过程中最复杂的操作，它对查询的性能影响也很大，因 此我们主要研究的是连接算符树，即操作符是连接符号。 例如下面的查询语句： s e l e c te n a m e ，r e s p f r o me m p ，a s g ，p r o j w h e r e e m p e n o = a s g e n o a n da s g p n o = p r o j 。p n o 可以用三棵算符树来表示上面的查询，如下图3 2 所示。 ( a ) 分布式数据库多连接商询优化算法的研究 图3 - 2 算符树 从图3 2 中，我们可以看出对于一个查询语句可以用不同的算符树来表示它，而且每 种算符树的代价也是不同的，例如图( c ) 的代价要大于其它的算符树。 对于一个复杂的查询，产生算符树的代价也是非常大的。比如对于n 个关系进行连接， 使用交换律和结合律规则产生的算符树的代价为o ( n ! ) 。有时，搜索一个大的执行计划的 空间也许比查询本身的代价还要高。因此，查询优化器必须对查询的搜索空间加一些约束 条件。第一个条件是运用启发式规则。最常用的启发式规则是把选择和投影运算尽可能往 下推移，另一个启发式规则是避免查询中产生不需要的笛卡尔积。例如，在图3 2 中图( c ) 就是一个可以不需要考虑的算符树。 另一个条件是连接树的形状。连接树的形状可以分为两种：一种是线性连接树，一种 是浓密连接树。在线性连接树中每个操作符的两个操作数至少有一个是连接关系，而在浓 密连接树，则没有这个要求。虽然使用线性连接树，查询的搜索空间的大小可以降至0 ( 2 n ) ， 然而在分布式数据库中，可以用浓密连接树来实现各个处理机的并行执行能力。连接树形 状如下图3 3 所示。 ( a ) 线性连接树 1 4 分布式数据库多连接布询优化算法的研究 3 2 2 查询策略 ( b ) 浓密连接树 图3 3 两种类型的连接树 最常用的查询策略