（计算机软件与理论专业论文）募捐管理系统中分布式查询优化的设计与实现.pdf

at h e s i si nc o m p u t e rs o f t w a r ea n d t h e o r y t h e d e s i g na n di m p l e m e n t a t i o no f d 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 nd o n a t i o na d m i n i s t r a t i o ns y s t e m b yw a n gt i a n b a o s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rw a n gj i a n n o r t h e a s t e r nu n i v e r s i t y m a y2 0 0 8 、j111 ，j1j - j 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ：匕 恧o _哆07， 学位论文作者签名：今织五 一，1 日 期：卜名争7 目目 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年一年口一年半口 两年口 学位论文作者签名多久重 签字日期：仙g 午了日日 导师签名： 签字日期： 碜w ，lr ，0ilij 东北大学硕士学位论文 摘要 募捐管理系统中分布式查询优化的设计与实现 摘要 随着数据库技术的不断发展，分布式数据库的应用变得越来越广泛。由于在分布式 数据库系统中数据的冗余和分布，增加了分布式数据查询的难度和复杂度，如何更加有 效的查询数据是分布式数据库系统面临的一个重要问题，也是本文所要探讨的问题。 国内外数据库方面的专家和学者对分布式条件下查询优化技术做了大量的研究工 作，并取得了重要的成果。经过研究得出了一些经典的分布式查询优化算法：如基于关 系代数等价变换原则的优化算法，基于半连接的优化算法，s d d1 算法，爬山算法，模 拟退火算法，遗传算法等。 本文以中国红十字总会募捐管理软件开发与网络系统集成开发项目为背景。在本文 中，首先介绍了分布式数据库系统的有关概念；然后对分布式查询的处理过程做了阐述， 其中对常见的基于关系代数等价变换原则的优化算法，基于半连接的优化算法，s d d1 算法，遗传算法进行了分析和研究；最后将遗传算法和半连接算法相结合，得出多连接 条件下的半连接遗传算法。该算法根据查询图构造出平衡连接树，并将其作为一个染 色体，然后对平衡连接树做后序遍历得到染色体编码串。然后对由所有生成的染色体构 成的种群运用遗传算法，经过选择、交叉、变异操作后，得到一个执行方案，最后对得 到的方案运用半连接算法进一步对算法进行优化。该算法使执行过程中并行执行的机会 大大增加，从而使得查询的效率得以进一步提高。 关键词：分布式数据库系统；查询优化：遗传算法；半连接算法；半连接遗传算法 f ， 东北大学硕士学位论文a b s t r a c t t h e d e s i g na n di m p l e m e n t a t i o n q u e r yo p t i m i z a t i o ni nd o fd i s t r i b u t e d o n a t i o na d m i n i s t r a t i o n s y s t e m a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t a b a s et e c h n o l o g y , t h ea p p l i c a t i o no fd i s t r i b u t e dd a t a b a s e b e c o m e sm o r ea n dm o r ew i d e t h ed i s t r i b u t e dd a t a q u e r yb e c o m e sm o r ed i m c u l ta n d c o m p l e xb 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 ai nd i s t r i b u t e dd a t a b a s es y s t e m s t h e r e f o r e ，h o wt oq u e r yd a t am o r ee f f e c t i v e l yi sa l li 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 e s y s t e m s ，a n di ti sa l s ot h ep r o b l e mw h i c hw i l lb es t u d i e di nt h i sp a p e r d o m e s t i ca n di n t e m a t i o n a le x p e a sa n ds c h o l a r sh a v ed o n eal o to fr e s e a r c hw o r k so n d i s t r i b u t e dq u e r yo p t i m i z a t i o nt e c h n o l o g y , a n ds o m ei m p o r t a n tr e s u l t sh a v e b e e na c h i e v e d a n u m b e ro fc l a s s i cd i s t r i b u t e dq u e r yo p t i m i z a t i o na l g o r i t h m sh a v eb e e no b t a i n e d ，s u c ha st h e o p t i m i z a t i o na l g o r i t h mb a s e do nr e l a t i o na l g e b r ae q u i v a l e n tt r a n s f o r m a t i o n ，t h eo p t i m i z a t i o n a l g o r i t h mb a s e do nt h es e m i - j o i n t ，s d d _ 1a l g o r i t h m ，m o u n t a i nc l i m b i n ga l g o r i t h m ，s i m u l a t e d a n n e a l i n ga l g o r i t h ma n dg e n e t i ca l g o r i t h m ，e t c t h i sp a p e ri sb a s e do nt h ep r o j e c to fd o n a t i o nm a n a g e m e n ts o f t w a r ed e v e l o p i n ga n d n e t w o r ks y s t e mi n t e g r a t i o no fc h i n e s er e dc r o s s i nt h i s p a p e r w ep r e s e n tt h er e l e v a n t c o n c e p t so fd i s t r i b u t e dd a t a b a s ef i r s t l y ；t h e ng i v ea ni n t r o d u c t i o nt ot h ep r o c e s so fd i s t r i b u t e d q u e r y w eg i v ee m p h a s i st ot h ea n a l y s i sa n dr e s e a r c ho ft h eo p t i m i z a t i o na l g o r i t h mb a s e do n r e l a t i o na l g e b r ae q u i v a l e n tt r a n s f o r m a t i o na n dt h eo n eb a s e do ns e m i - j o i n t ，s d d 1a l g o r i t h m ， g e n e t i ca l g o r i t h m t h e n ，b yc o m b i n i n gt h eg e n e t i ca l g o r i t h ma n ds e m i - j o i n ta l g o r i t h m t o g e t h e r , t h es e m i - j o i n t g e n e t i ca l g o r i t h mu n d e rt h ec o n d i t i o no fm u l t i 1 i n ki sp r o p o s e d t h e p r o p o s e da l g o r i t h mm a yb eu s e dt oc o n s t r u c tb a l a n c ej o i n tt r e eb a s e do nq u e r yf i g u r ew h i c hi s t h o u g h ta sac h r o m o s o m e ，a n dt h ec h r o m o s o m ec h a i ni so b t a i n e db yt r a v e r s i n gt h eb a l a n c e j o i n tt r e ea f t e rt h es e q u e n c e t h e nt h eg e n e t i ca l g o r i t h mi s a p p l i e di n t ot h ep o p u l a t i o n c o n s t r u c t e db ya l l c h r o m o s o m e s ，a n da ne x e c u t i o ns c h e m ei sa c h i e v e da f t e rs e l e c t i o n ， c r o s s o v e ra n dm u t a t i o no p e r a t i o n ，t h e nt h ee x e c u t i o ns c h e m ei so p t i m i z e df u r t h e rb y u s i n gt h e s e m i - jo i n ta l g o r i t h m i nt h ee x e c u t i o np r o c e s so ft h ep r o p o s e da l g o r i t h m ，t h eo p p o r t u n i t yo f p a r a l l e le x e c u t i o ni si n c r e a s e dg r e a t l y , a n dt h eq u e r y e f f i c i e n c yi si m p r o v e df u r t h e r 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 es y s t e m ；q u e r yo p t i m i z a t i o n ；g e n e t i ca l g o r i t h m ；s e m i - j o i n t a l g o r i t h m ；s e m i - jo i n t - g e n e t i ca l g o r i t h m i i i f 一 i ； 东北大学硕士学位论文 目录 目录 独创性声明。l 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 课题的项目背景和理论背景1 1 2 国内外对分布式数据查询研究的现状2 1 2 1 国外研究的现状2 1 2 2 国内研究的现状3 1 3 本文的主要工作。3 1 4 论文组织结构4 第2 章分布式数据库系统概述7 2 1 分布式数据库系统的定义和特点7 2 1 1 分布式数据库系统的定义7 2 1 2 分布式数据库系统的基本特点7 2 1 3 分布式数据库的导出特点8 2 2 分布式数据库系统的分类8 2 2 1 按局部数据库管理系统的数据模型分类8 2 2 2 按全局控制系统分类9 2 3 分布式数据库管理系统的功能和组成l o 2 3 1 分布式数据库管理系统的功能1 0 2 3 2 分布式数据库管理系统的组成1 0 2 4 分布式数据库系统的结构1 1 2 4 1 分布式数据库系统的体系结构1 1 2 4 2 分布式数据库系统的模式结构1 3 2 5 分布式数据库系统中数据分片和数据分布1 4 2 5 1 关系分类1 4 2 5 2 数据分片1 5 2 5 3 数据分布1 9 2 6 本章小结2 0 第3 章募捐管理系统查询优化总体设计2 1 一i v 墨! ! 垄堂堡主兰堡笙文目录 一一 ： 3 1 募捐管理系统的总体架构2 l 3 2 募捐管理系统查询优化2 3 3 2 1 募捐管理系统查询优化所要考虑问题2 3 3 2 2 分布式查询优化的目标和代价估算2 4 3 3 查询统计模块2 5 3 4 分布式查询优化算法分析2 6 3 4 1 基于关系代数等价变换的算法2 6 3 4 2s d d 一1 算法2 7 3 4 3 直接连接操作的优化方法2 8 3 4 4 半连接优化算法n 2 8 3 4 5 基于查询图的贪婪算法分析3 0 3 4 6 遗传算法3 2 3 5 募捐管理系统查询优化总体设计3 3 3 5 1o r a c l e 环境下分布式数据库的实现3 3 3 5 2 半连接遗传算法的基本思想与总体设计3 4 3 6 本章小结3 4 第4 章分布式查询优化的详细设计与实现3 5 4 1o r a c l e 数据库的实现3 5 4 1 1 募捐管理系统表结构及数据分布3 5 4 1 2 链接分布式o r a c l e 数据库3 6 4 2 半连接算法和遗传算法详解3 7 4 2 1 半连接应用分析3 7 4 2 2 遗传算法原理_ 3 8 4 3 半连接遗传算法流程详细设计4 2 4 3 1 连接树的构造4 3 4 3 2 遗传算法优化的设计4 3 4 3 3 半连接优化5 4 4 4 半连接遗传算法的总体实现5 4 4 5 本章小结5 6 第5 章分布式查询优化算法性能分析5 7 5 1 查询实例5 7 5 2 模拟过程5 7 5 2 1 实验场景5 7 5 2 2 实验的步骤和运行参数的选取5 8 一v 一 东北大学硕士学位论文 目录 5 2 3 实验的结果5 8 5 3 性能评价5 8 5 3 1 理论分析5 9 5 3 2 实验结果分析5 9 5 4 本章小结5 9 第6 章结论6 1 6 1 工作总结6 l 6 2 需要解决的问题6 1 参考文献6 3 致谢。6 6 一v i 东北大学硕士学位论文笫1 章绪论 第1 章绪论 1 1 课题的项目背景和理论背景 本文根据东软集团税务事业部中国红十字会募捐管理系统为项目背景。中国红十字 会是从事人道主义工作的社会救助团体，从建会伊始就一直从事救护伤兵、救助难民和 赈济灾民活动，并积极参加人道主义救援活动。 红十字会通过开展社会捐助活动，接受国内外救援捐赠款物并将款物及时发放到灾 民手中或进行必要的救援物资和设备的采购达到赈灾的目的。例如，在这次近几十年不 遇的四川汶川大地震中，全国人民投入到抗震救灾的大军中，中国红十字会同时公布了 几种救灾捐款的途径。捐助者可以通过银行或邮局汇款或直接到当地红十字会捐款，计 算机的普及和网络技术的发展使更多的人选择网上捐款。 中国红十字总会需要对每个捐款的人进行信息管理，捐款者也可在红会网站上查询 有关自己捐助情况的信息。同时，由于中国红十字总会和各地的分会是联系在一起的， 牵涉到数据的分布问题，基于这个应用背景，所以分布式环境下数据的查询成为当前面 临的一个应用课题。 同时，当前世界各国各级政府部门实行电子政务，这也是当前世界政界的一个新的 趋势。在这种形式下，中国红十字会更需要不断完善信息条件下的电子政务的业务，为 本文提供了应用方面的研究背景。 理论方面，随着信息技术的不断发展，人们对信息的使用频率变得更加频繁，信息 处理的重要工具和组成部分是数据库，因此数据库技术在信息技术发展的基础上取得了 飞速的发展。而随着人们对数据库的要求不断提高和网络技术所取得的成果，基于网络 的分布式数据库技术取得了巨大的发展。 2 0 世纪8 0 年代以来，在数据库领域的研究空前的活跃，其中分布式数据库【1 】【2 1 【3 】 ( 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 s ) 的研究与发展也是前所未有。自上世纪7 0 年代中 期开始，在集中式数据库的基础上分布式数据库的研究开始发展起来，分布式数据库应 用数据库技术和计算机网络技术，是二者有机结合的产物，在数据库研究领域产生巨大 的影响。 随着分布式数据库研究的不断深入和技术的不断完善，对分布式数据库的应用越来 越广泛。现代企业项目的应用中，数据量不断增大，数据的查询变得越来越复杂，如何 从成繁琐的记录中选择所要求的数据，如何适应当前高信息处理速度成为分布式数据查 询所面临的重要问题，因此查询优化处理成为分布式数据库系统中的一个关键性问题。 在分布式数据库系统中，一个重要的特征就是数据的分布性和冗余性。诚然，数据 一1 一 东北大学硕士学位论文第1 章绪论 的分布性可以减少数据存储空间，提高数据存取的速度等；数据的冗余性可以使数据变 得更加的安全，亦即，即使因为一个站点被破坏仍然不至于使整个系统瘫痪，造成数据 的丢失。这些优点在当前信息化时代有着非常巨大的优势，这也就是为什么分布式数据 库被广泛应用的原因。 由于数据的分布和冗余，所以有时候要查询的数据需要跨几个节点才能够得到所需 要的结果，使得查询处理中一般都需要站点间的数据传递及通信费用，这也成为查询优 化的主要矛盾；另一方面，数据的分布和冗余也使数据的并行查询成为可能，从而可以 更加有效的利用资源，缩短查询处理的响应时间，提高处理速度。总之，分布式数据查 询在查询的规模和优化的因素方面有着与集中式数据库所不同之处，因此自从分布式数 据库产生伊始就吸引了国际上许多数据库专家致力于研究分布式数据查询优化这一重 要课题，在这方面做了大量的工作，找到了一些规律，并研究出来一些大家公认的比较 经典的算法。 然而由于分布式数据库系统的灵活性，不可能设计出一个算法对各种情况都能够达 到最优查询，我们只能说所设计的某一种优化算法能够更好的解决某一类问题。分布式 数据查询已经被证明了属于n p 完全问题，尽管国内外的数据库专家对此做了大量的工 作，取得重要的进展，但是至今并未得到完全彻底地解决方案，尚有不少问题值得研究 和探讨。 1 2 国内外对分布式数据查询研究的现状 查询时数据库中最常见、最基本的操作，同时也是用户对数据库中的数据进行操作、 维护的唯一途径。数据库系统能够高效、快速的处理查询是数据库性能一个最直接的表 现，查询的效率很大程度上决定了数据库管理系统( d a t a b a s em a n a g e m e n ts y s t e m ，d m s ) 性能，因此，自从分布式数据库系统问世以来，分布式查询优化一直备受关注。 1 2 1 国外研究的现状 1 9 7 8 年，美国计算机公司研制出的s d d 1 ( s y s t e mo f d i s t r i b u t e dd a t a b a s e ) 是分布 式数据库管理系统的第一个样机1 4 1 。由e w o n g 针对s d d1 系统的情况设计出一种启发 式算法；而后，p a b e r n s r e i n 等对e w o n g 的算法做了进一步优化，提出了半连接和缩 减器的概念。 分布的i n g r e s ，是美国加州大学伯克利分校研制的i n g r e s 的分布式后继【5 j 。 e p s t e i n 在分布式i n g r e s 上实现了基于分解的、动态的、解释性的优化算法。 o r a c l e 是世界上第一个商品化的分布式数据库管理系统，它采用完全开放的策略， 能在所有的主流平台上运行，完全支持所有的工业标准【6 】。o r a c l e 查询处理模块由三个 部分组成：解析器( p a r s e r ) ，优化器( o p t i m i z e r ) ，执行器( e x e c u t o r ) 。p a r s e r 对输入 一2 一 东北大学硕士学位论文第1 章绪论 的查询进行语法分析，并检查用户查询所涉及的数据库对象是否存在以及用户是否有对 该数据的操作权限。o p t i m i z e r 利用基于代价的优化或基于规则的优化找出一个执行代 价较低的执行计划，从而大大提高了代价估计的精确度。如果执行计划可能并行，对某 些可能的节点，e x e c u t o r 会启动多个进程来并行执行该节点。 2 0 世纪9 0 年代初，美国的w i s c o n s i n 大学的k r i s t i nb e n n e t t 等人提出了一个分布式 数据库查询优化的算法，它将遗传算法应用到分布式数据库查询优化中去，并且实际了 基于做连接树和浓密连接树的编码方法，给出来交叉、变异算子。在这之后s a i l g k y ur h o 等人提出了一种由4 部分内容组成的遗传算法编码方法，并详细介绍了代价函数的计算 方法，给出了查询优化算法的具体执行步骤。 1 2 2 国内研究的现状 c p o r e l 是有中科院数学研究所设计并有该所与上海科技大学及华东师范大学合 作开发的。主要目标是实用性、先进性和有限的可移植性 7 1 。c p o r e l 是关系系统，支 持关系的水平分片，在代数优化、非代数优化及分布式查询优化方面实现了精致的算法。 在开发了d d b a s e 3 和d d b a s e 3 后南京大学设计实现了异构型分布式数据库管理 系统- i ，s z 异构分布式数据库系统。它支持关系的水平分片，采用m 技术实现了基 于启发式规则的语义优化策略，并进行了多重连接优化。 在基于c o r b a 上有两个学校分别研制出不同的系统。东南大学研制的g a l a x y 是 一个分布式异构数据源集成系统，可以查询数据库、w v c w 数据库等信息源，但是对查 询优化的考虑并不多【引。东北大学研制出多数据库系统s c o p e c i m s ，其中使用对象查询 语言作为全局查询语言，并提出了基于模式集成语义的查询处理规则和路径表达式的查 询处理方法一j 。 国内的科学家在遗传算法方面也做了好多研究，如任美睿等人在k r i s t i nb e n n e t t 的 研究结果之上提出了改善的交叉、变异方法【3 3 1 ；曹阳等人研究了使用遗传算法解决多连 接表达式的并行查询优化方法i u l ；芦金石等人提出了基于树形编码的遗传算法，用这个 算法来解决分布式异构数据库查询优化中的问题【1 2 】。 1 3 本文的主要工作 本文结合数据查询的特点，在对分布式数据库系统进行了大致的介绍，并对执行具 体的过程进行了剖析。分析了分布式数据库查询优化要考虑的问题，描述了分布式数据 库系统查询优化的过程。 在实际的应用中，多连接查询是分布式数据库系统中查询中一个重要的研究方向。 本文在深入研究和分析几种经典的算法后，给出了在中国红十字总会募捐管理软件开发 与网络系统集成开发项目中的分布式查询策略，以得到一个更理想的分布式数据库中查 - - 3 - - - 东北大学硕士学位论文 第1 章绪论 询优化的算法。 在现阶段查询优化的研究过程中，很多成熟的算法，如遗传算法、爬山算法、模拟 退火算法、半连接算法都在一定程度上提高了查询优化的性能。本文将遗传算法和半连 接算法同时应用于募捐管理系统中，提出了半连接遗传算法。 该算法具有以下几个特点： ( 1 ) 该算法分为两步，第一步用遗传算法得到一个查询的优化执行方案，第二步应 用半连接算法对得到的执行方案进行进一步的优化。 ( 2 ) 在以多连接查询为优化对象的例子中，首先改善了遗传算法中染色体编码的方 法，提出了平衡连接树的染色体构建算法。平衡染色体的构建对于提高查询的并行性具 有重要影响。 ( 3 ) 分别对三种遗传算子进行改进。选择算子采用适应度最优的选择方式；通过对 选定的一对连接树上的子树进行交叉，得到新的个体；在变异算子中，根据连接树的特 点，采用子树与叶节点和子树与子树交叉两种变异方式同时存在的方式，弥补了变异算 子新生个体产生不足的问题，增加了种群个体的多样性。 1 4 论文组织结构 本文的主要任务是在实际所做项目基础上提出一种新的查询优化算法一半连接一 遗传算法，并在项目实行过程得以应用。半连接一遗传算法能够应对项目过程中出现的 查询操作，显著的提高查询的效率。 全文的组织结构安排如下： 第1 章，介绍了本课题研究的项目背景和理论背景，介绍了国内外在分布式数据查 询方面的研究现状，简要介绍了本文的主用工作。 第2 章，主要对分布式数据库系统的基础理论和相关概念做了个概要性的叙述。包 括分布式数据和分布式数据库系统的定义、分布式数据库特点、分类的介绍，以及对分 布式数据库管理系统的功能和组成的概述、分布式数据库系统的结构和数据的分片和分 布的详细介绍。本章为后续的研究做了理论方面的工作。 第3 章，本章首先给出募捐管理系统的总体架构，并根据募捐管理系统中的查询问 题分析了要考虑的问题和查询优化的目标和代价。然后重点研究了几种分布式查询优化 算法，对它们各自的优点和存在的不足进行了分析。最后根据上边的分析给出募捐管理 系统查询优化的总体设计，分别对o r a c l e 分布式数据库环境下数据的分布和分片等方 面做了总体设计，接着给出半连接一遗传算法的算法思想和总体设计思路。 第4 章，是本文的核心部分。本章首先给出了分布式条件下o r a c l e 数据库的实现。 对募捐管理系统的表结构进行了分析，根据各个表在实际应用的需求情况采用不同的分 一4 一 东北大学硕士学位论文第1 章绪论 布方式和分片方式。 根据多连接查询的特点，在本章中给出了半连接一遗传算法的详细设计。该算法分 两步，首先在初始种群中运用遗传算法，在搜索空间进行查找，得到最优的执行方案。 在这里我们改进了，初始种群的构造方法，运用构造平衡的连接浓密树然后采用后序遍 历得到染色体编码。通过对两个个体寻找同节点数的子树进行交换使得两个体得以交 叉，交换个体连接树上的不同子树，以达到变异的目的，最后运用适应度最优的方式给 出选择算子。 然后给出半连接优化算法，对连接树运用半连接算法进行优化。最后给出半连接一 遗传算法的总体实现。 第5 章，通过实例对算法的性能进行评价。从理论方面和实验结果对算法进行评判。 第6 章，对该课题研究的总结。指出了本文所做的工作，并提出了需要改进的地方 和对未来的展望。 一5 一 一6 一 东北大学硕士学位论文第2 章分布式数据库系统概论 第2 章分布式数据库系统概论 2 1 分布式数据库系统的定义和特点 2 1 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 ) 是物理上分布而逻辑上集 中的数据库系统【l ，2 捌。物理上的分布是指分布式数据库系统中的数据分布在由网络连接 起来的、地理位置分散的不同站点上；逻辑上集中是指数据库站点之间在逻辑上是一个 整体，并由统一的数据集管理系统进行管理，同时各站点又具有管理本地数据的能力。 因此，分布式数据库系统可以看成是计算机网络与数据库系统的有机结合。 2 1 2 分布式数据库系统的基本特点 根据分布式数据系统的定义，可得出一个分布式数据库系统应该具备如下特点1 1 , 3 1 ： ( 1 ) 数据的物理分布性：分布式数据库系统中的数据不是集中存储在一个站点上， 而是分散存储在有计算机网络连接起来的多个站点上，而且这种分散对用户来说是感觉 不到的。分布式数据库系统的数据具有物理分布性是与集中式数据库系统的最大的区别 之一。 ( 2 ) 数据的逻辑整体性：分布式数据库系统中的数据物理上是分布在网络上不同的 节点上的，但这些分散的数据在逻辑上构成一个整体。这些数据由一个统一的数据库管 理系统( d a t ab a s em a n a g e m e n ts y s t e m ，d b m s ) 统一管理，并可以为分布在不同节点 上的所有用户所共享，这使得“分布”对用户来说是透明的。而这种“逻辑整体性”也是与 分散性数据库的最大区别。区别一个数据库系统是分布式还是分散式，只要判断该系统 是否支持全局应用。 ( 3 ) 站点自治性：系统中的每个站点都具有独立的数据库系统，有自己的数据库、 自己的用户、自己的c p u ，各站点上的数据均由本地的分布式数据库管理系统 ( d i s t r i b u t e dd a t ab a s em a n a g e m e n ts y s t e m 。d d b m s ) 管理，具有高度的自治性。每个 节点都能够运用d d b m s 执行本地的应用请求，同时每个站点又是整个系统中的组成部 分，可以通过网络处理全局的应用请求。 ( 4 ) 站点之间的协作性：虽然各站点具有高度的自治性，但在逻辑上各站点有机组 成一个整体。在任何一个场地的用户都可以像使用一个集中式数据库系统一样，对分布 在其他场地的数据执行全局应用。 一7 一 东北大学硕士学位论文 第2 章分布式数据库系统概论 2 1 3 分布式数据库的导出特点 根据以上的四个基本特点可以推出分布式数据库系统的其他特点【1 5 】： ( 1 ) 数据独立性：除数据的物理独立性和逻辑独立性外，分布式数据库系统的数据 还包括数据分布透明性。分布透明性是指用户或应用程序不必关心数据的逻辑分片，不 必关心数据物理位置分配的细节，也不必关心各站点上数据库的数据模型是哪种类型， 可以像操作集中式数据库一样来操作分布式数据库。 ( 2 ) 集中与自己相结合的控制机制：在分布式数据库系统中，包括全局范围控制和 局部范围控制。全局范围内，有集中的控制机制统一管理数据的共享，分布在各站点上 的数据可由全局用户共享；在局部范围内，由本地数据库管理系统管理本站点数据，该 站点上的用户可以共享本站点上数据。 ( 3 ) 数据的冗余性：在集中式数据库中，数据的冗余不仅浪费存储空间，而且容易 造成数据的不一致性。而在分布式数据库系统中，不同于集中式数据库尽量减少冗余的 目标，却通过数据的冗余来提高系统的可靠性、可用性和改善系统的性能。通过在多个 站点上存储数据的副本，使得当一个站点上数据破坏时，仍能使系统正常运行，保证可 靠性；同时，系统可以选择离用户最近的数据副本进行操作，减少通信代价，改善整个 系统的性能。 ( 4 ) 事务管理分布性：一个全局事务的执行可以分解为若干个站点上的局部事务( 子 事务) 来执行。 2 2 分布式数据库系统的分类 目前对分布式数据库的分类还没有标准的定义，但较为认同的分类方法有两种。一 种是按构成分布式数据库系统的局部数据库管理系统的数据模型来进行分类；另一种是 按分布式数据库系统的全局控制系统类型进行分类。 2 2 1 按局部数据库管理系统的数据模型分类 在分布式数据库系统中，每个站点有各自的数据库系统( 局部数据库系统) 。如果 对局部的数据库系统的数据模型和数据库管理系统进行考察，由他们支持组成的分布式 数据库系统可以分成以下三类： ( 1 ) 同构同质型分布式数据库系统：各站点都采用同一种类型的数据模型( 如关系 模型) ，并且都是同一种类型的数据库管理系统( 如o r a c l e 类型) 。 ( 2 ) 同构异质型分布式数据库系统：各站点均采用同一种类型的数据模型( 如关系 模型) ，但是数据库管理系统的型号不同( 如d b 2 、o r a c l e 、s y b a s e 、s q ls e r v e r 等) 。 ( 3 ) 异构性分布式数据库系统：各站点的数据模型的型号不同，甚至是类型也不同 ( 如有关系型的，有面向对象类型的) 。随着计算机网络技术的发展，异构机联网问题 一8 一 东北大学硕士学位论文第2 章分布式数据库系统概论 已经得到较好的解决，此时依靠异构型分布式数据库管理系统就能存取全局网络中各异 构数据库中的数据。 2 2 2 按全局控制系统分类 按分布式数据库系统的全局控制系统的类型可以将分布式数据库系统分为以下三 类： ( 1 ) 集中型分布式数据库系统：分布式数据库系统的全局控制信息位于一个中心站 点。这种控制方式有利于保持数据的一致性和完整性，但容易产生访问瓶颈，并且如果 一旦中心节点失效，整个系统将崩溃。见图2 1 ： 全局用户 分布式数据库d d b m s 分布式数据d d 局部用户 匕 局部数据库系统 l d b m s l 局部用户 _ 局部数据库系统 l d b m s n 据库 ff 据库 l d b l l d b n 图2 1 集中式控制的d d b m s 结构示意图 f i g 2 1t h es t r u c t u r es c h e m eo fc e n t r a l i z e dc o n t r o l l e dd d b m s ( 2 ) 分散型分布式数据库系统：在每个站点上包含全局控制信息的一个副本。该类 系统可用性好，但保持信息的一致性较困难，需要有复杂的设施，如下图2 2 所示： ( 3 ) 可变型分布式数据库系统：在这种类型的系统中，将站点分成两组，一组包含 全局控制信息副本，称为主站点；另一组不包含全局控制信息副本，称为辅站点。这种 方案的灵活性好，易于实现层次控制结构。但是，设计复杂，必须经过充分用户应用调 查，才能使设计的系统和用户的应用相吻合。 一9 一 东北大学硕士学位论文 第2 章分布式数据库系统概论 局部用户局部用户局部用户局部用户 d d m s ，d d l d b m s l d d m s ，d d l d b m s n 图2 2 分散式控制的d d b s 结构不总图 f i g 2 2t h e s t r u c t u r es c h e m eo fd e c e n t r a l i z e dc o n t r o l l e dd d b m s 2 3 分布式数据库管理系统的功能和组成 分布式数据库管理系统( d i s t r i b u t e dd a t ab a s em a n a g e m e n ts y s t e m ，d d b m s ) 负责 实现分布式数据库的建立、查询、更新、复制、维护等功能，包括提供分布透明性，查 询优化，协调各局部d b m s 共同完成全局应用，保持数据库的一致性，执行并发控制， 实现更新同步和全局回复等。分布式数据库管理系统是整个分布式数据库系统的核心。 2 3 1 分布式数据库管理系统的功能 一个分布式数据库管理系统主要有以下几个功能： ( 1 ) 接受用户请求，并判断送到哪里或访问哪些计算机才能满足该要求。 ( 2 ) 访问网络数据字典，了解如何请求和使用其中的信息。 ( 3 ) 当目标数据分布在系统的多个站点上，必须进行分布式处理。 ( 4 ) 通信接口功能。在用户、局部数据库管理系统和其他站点的数据库管理系统之 间进行协调。 ( 5 ) 在一个一个异构型分布式处理环境中，还需提供数据和进程一直都支持。所谓 异构是指各站点的硬件、软件存在差别。 2 3 2 分布式数据库管理系统的组成 从功能上来说，一个分布式数据库管理系统包括四个基本功能模块： ( 1 ) 查询处理模块：在分布式是数据库系统中，数据分布于整个网络的各个场地中， 当用户请求一个查询时，往往会一起数据的传输，这需要花费相当高的代价。因此，要 尽可能的采用最佳优化方法，以减少传输费用，提高传输效率。查询处理模块由两部分 组成：一是查询分析，对查询语句进行分析、检查，弄清查询请求所需的资源；二是优 化处理，以尽可能小的代价完成一次查询。 一10 一 东北大学硕士学位论文 第2 章分布式数据库系统概论 ( 2 ) 完整性处理模块：该模块主要负责维护数据库的完整性和一致性，检查完整性 规则，处理多副本数据的同步更新等。该模块有以下两个功能：一是确定使用的数据副 本，当查询处理模块分析出要使用的数据后，它根据网络数据目录计算机出使用不同副 本的代价，进一步确定供查询使用的数据副本及该副本所在的场地，并且尽可能使这一 代价极小化；二是维护数据库的完整性，提高并发控制机制。 ( 3 ) 调度处理模块：一旦确定了查询处理的策略，就要进行一些局部处理和数据传 输，这时调度处理模块就负责向有关站点发布命令，是相应站点的数据库管理系统执行 这些局部处理：同时，发布命令在相应站点之间进行必要的数据传输；最后，完成查询 并把结果传送回发出该查询的站点。 ( 4 ) 可靠性处理模块：可靠性高是数据库管理系统的一个主要优点。由于