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

分布式数据库的查询优化算法研究 摘要 本文首先介绍了分布式数据库系统的基本概念， 如分布式数据库 系统的模式结构及体系结构、 数据分片的原则及分类、 数据分布的策 略等; 然后简要描述了分布式查询的处理过程: 接着本文重点研究了 分布式查询的一些常用优化算法， 如基于关系代数等价变换规则的优 化算法、基于连接的优化算法、基于半连接的优化算法、s d d 1算 法， 基于查询图的贪婪算法。 本文在对分布式查询的一些常用优化算法研究的基础上，设计了 一个新的算法， 本文称之为基于多关系半连接查询优化算法， 以适用 于以分布式数据库系统的缓冲区作为查询的中间结果的最后装配站 点这种情况。 实验证明基于多关系半连接的查询优化算法明显地减少 了中间结果数据量，有效地降低了网络通信总代价。 关键字:分布式数据库，查询优化，s d d 1 ，多关系半连接 r e s e a r c h o n q u e r y o p t i m i z a t i o n a l g o r i t h m o f di s t r i b u t e d da t a ba s e ab s t r a c t t h i s p a p e r i n t r o d u c e s t h e b a s i c c o n c e p t o f d i s t r i b u t e d d a t a b a s e s y s t e m, s u c h a s t h e m o d e a r c h i t e c t u r e a n d s y s t e m a r c h i t e c t u r e o f d d b s , t h e p r i n c i p l e a n d c l a s s if i c a t i o n o f d a t a f r a g m e n t a t i o n , t h e s t r a t e g y o f d a t a d i s t r i b u t i o n . t h i s p a p e r d e s c r i b e s t h e m a n a g e m e n t p r o c e s s i n g o f d i s t r i b u t e d q u e r y . t h i s p a p e r g i v e e m p h a s i s t o t h e r e s e a r c h o n t h e r e g u l a r o p t i m i z a t i o n a l g o r i t h m s o f d i s t r i b u t e d q u e r y , s u c h a s t h e o p t i m i z a t i o n a l g o r it h m b a s e d o n t h e r e g u l a t io n o f r e l a t i o n a l g e b r a e q u i v a l e n c e t r a n s f o r m a t i o n , t h e o p t i m i z a t i o n a l g o r it h m b a s e d o n j o i n , t h e o p t i m i z a t i o n a l g o r i t h m b a s e d o n s e m i j o in , s d d _ 1 a l g o r i t h m, t h e g r e e d y a l g o r i t h m b a s e d o n q u e r y g r a p h . o n t h e b a s i s o f t h e r e s e a r c h o n t h e s d d _ 1 a l g o r i t h m a n d t h e g r e e d y a l g o r i t h m b a s e d o n q u e r y g r a p h ，t h i s p a p e r d e s i g n a n e w a l g o r i t h m n a m e d t h e q u e r y o p t i m i z a t i o n a l g o r i t h m b a s e d o n m u l t i p l e r e l a t i o n s s e m i j o i n , w h i c h i n t e g r a t e t h e c h a r a c t e r i s t i c s o f s d d _ 1 a lg o r i t h m a n d t h e g r e e d y a l g o r i th m b a s e d o n q u e r y g r a p h , t h i s n e w a l g o r i t h m c a n b e a p p l i e d t o t h e c i r c u m s t a n c e i n w h i c h t h e c a c h e o f d d b s i s t h e f i n a l a s s e m b l y s i t e o f t e m p o r a r y q u e r y r e s u l t .t h e a l g o r i t h m r e d u c e t h e t e m p o r a r y r e s u l t d a t a n u m e r d is t i n c t l y a n d r e d u c e t h e n e t w o r k c o m m u n i c a t i o n t o t a l c o s t e ff i c i e n t l y t h r o u g h e x p e r i m e n t . k e y w o r d s : d i s t r ib u t e d d a t a b a s e , q u e r y o p t i m i z a t i o n , s d d _ l , m u l t i p l e r e l a t i o n ss e mi l o in 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 h 在- -p 己! - 1 - 只 7 -fj . 】 1 . 1论文背景 分布式数据库系统是计算机网络技术与数据库技术互相渗透和有机结合的 产物。 具有数据独立性、 集中与自 制相结合的控制机制、 适当增加数据冗余、 事 务管理的分布性等特点。 在分布式数据库系统中，数据独立性除了数据的逻辑独立性与物理独立性 外， 还有数据分布独立性亦称分布透明性。 分布透明性指用户不必关心数据的逻 辑分片， 不必关心数据物理位置分布的细节， 也不必关心重复副本的一致性问 题， 同时也不必关心局部场地上数据库支持哪种数据模型。 有了分布透明性， 用户的 查询程序书写起来就如同数据没有分布一样，使系统使用起来更简单、 有效。 在集中式数据库系统中， 为减少空间的浪费和保证数据的一致性， 要尽量减 少数据的冗余。 而分布式数据库系统却希望增加数据的冗余来提高系统的可靠性、 可用性和 改善系统性能。 但是由 于数据的分布和冗余， 使得分布式数据库系统查询处理增 加了许多新的内容和复杂性，因此分布式查询处理的优化显得更为重要。 无论是在集中式数据库系统中还是在分布式数据库系统中， 一个查询策略的 选择都是以执行查询的预期代价为依据的， 不同的只是构成一个查询代价的主要 因素在这两类系统中不完全一样。 在集中式数据库系统中，一个查询的预期代价 ( q c )是以查询处理的c p u 代价和1 / o代价来衡量的，即 q c = c p u代价+ u o代价p l c p u的处理时间 是ps级， 帕 的处理时间是m s 级， 因此集中式数据库系统 中， 提高查 询效率主 要 从减少i / 。次 数来 进行f l l 在分布式数据库系统中， 一个查询的预期代价， 除了像集中式数据库系统一 样考虑c p u代价和1 / 0代价之外，还需要考虑数据通过网络传输的代价，即 q c =c p u代价+ v 0代价+ 通信代价fl 通信网络与磁盘相比， 可以看作是一个非常慢的外围设备， 因而通信系统有 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 h 在- -p 己! - 1 - 只 7 -fj . 】 1 . 1论文背景 分布式数据库系统是计算机网络技术与数据库技术互相渗透和有机结合的 产物。 具有数据独立性、 集中与自 制相结合的控制机制、 适当增加数据冗余、 事 务管理的分布性等特点。 在分布式数据库系统中，数据独立性除了数据的逻辑独立性与物理独立性 外， 还有数据分布独立性亦称分布透明性。 分布透明性指用户不必关心数据的逻 辑分片， 不必关心数据物理位置分布的细节， 也不必关心重复副本的一致性问 题， 同时也不必关心局部场地上数据库支持哪种数据模型。 有了分布透明性， 用户的 查询程序书写起来就如同数据没有分布一样，使系统使用起来更简单、 有效。 在集中式数据库系统中， 为减少空间的浪费和保证数据的一致性， 要尽量减 少数据的冗余。 而分布式数据库系统却希望增加数据的冗余来提高系统的可靠性、 可用性和 改善系统性能。 但是由 于数据的分布和冗余， 使得分布式数据库系统查询处理增 加了许多新的内容和复杂性，因此分布式查询处理的优化显得更为重要。 无论是在集中式数据库系统中还是在分布式数据库系统中， 一个查询策略的 选择都是以执行查询的预期代价为依据的， 不同的只是构成一个查询代价的主要 因素在这两类系统中不完全一样。 在集中式数据库系统中，一个查询的预期代价 ( q c )是以查询处理的c p u 代价和1 / o代价来衡量的，即 q c = c p u代价+ u o代价p l c p u的处理时间 是ps级， 帕 的处理时间是m s 级， 因此集中式数据库系统 中， 提高查 询效率主 要 从减少i / 。次 数来 进行f l l 在分布式数据库系统中， 一个查询的预期代价， 除了像集中式数据库系统一 样考虑c p u代价和1 / 0代价之外，还需要考虑数据通过网络传输的代价，即 q c =c p u代价+ v 0代价+ 通信代价fl 通信网络与磁盘相比， 可以看作是一个非常慢的外围设备， 因而通信系统有 上海师范大学硕士学位论文分布式数 据库的查 询优化算法研究 较高的存取延迟时间。另外，在 c p u上处理通信的代价很高。例如，在网络中 发一个消息和处理对方接收消息的回音， 一般要花费5 0 0 0 1 0 0 0 0 条操作系统的 指令。通信代价可用下列式子粗略估算: ( 一 次 传 输 的 ) 通 信 代 价 = c o + c ,x i 其中x是数据传输量，通常以b i t 为单位计算。马和c ， 是依赖于系统的常 数， c id 是两场地间启动一个传输的固定费用， c : 是网 络范围内的单位传输费 用。 在分布式数据库系统中查询优化的首要目 标是使该查询在执行时其通信代 价为最小，而要使通信代价最小，就必须使数据传输量最小。 分布式数据库系统中涉及的数据可能分布在几个场地， 引起数据在网络中来 回传输。 应采用较优的处理方法， 使网络中数据传输量最小。 而导致数据传输量 大的主要原因是数据间的连接操作。 目 前， 对于分布式数据库系统的查询处理有许多优化算法， 如基于关系代数 等价变换的优化算法、 基于半连接操作的优化算法、 基于直接连接操作的优化算 法。 由 美国计算机公司1 9 7 8 年研制的s d d 1 是分布式数据库管理系统的第一个 样机， 该系统 采用的 分 布式查询方法是多关系半 连 接算法， s d d _ 1查询 优化算 法大致思想是通过反复的获得有益半连接运算， 减少每个站点上用于连接运算的 数据， 然后将所有站点的数据汇集到数据量最大的站点做最后装配。 选择优化后 存储数据量最大的站点为查询的中间结果的组装站点， 这样可以使整个网络上的 传输量保持最小。 s d d _ 1查 询优化算 法是指定 局部数据库中经 过半连 接优化操作后数据量最 大的站点作为查询的中间结果的最后装配的站点。在分布式查询的实际应用中， 有时并不是指定局部数据库中的某一站点作为查询的中间结果最后装配的站点， 而是指定分布式数据库系统的缓冲区作为查询的中间结果的最后装配的站点， 对 于这种情况， s d d _ 1查 询优化算法显然不再适用， 寻找怎样的分布式查询优化 算法或技术成为了学术界及企业界的一个研究热点。 1 . 2本课题解决的问 题 本文在对现有的分布式查询优化算法研究的基础上， 对分布式数据库的多关 上海师范大学硕士学位论文分布式数 据库的查 询优化算法研究 较高的存取延迟时间。另外，在 c p u上处理通信的代价很高。例如，在网络中 发一个消息和处理对方接收消息的回音， 一般要花费5 0 0 0 1 0 0 0 0 条操作系统的 指令。通信代价可用下列式子粗略估算: ( 一 次 传 输 的 ) 通 信 代 价 = c o + c ,x i 其中x是数据传输量，通常以b i t 为单位计算。马和c ， 是依赖于系统的常 数， c id 是两场地间启动一个传输的固定费用， c : 是网 络范围内的单位传输费 用。 在分布式数据库系统中查询优化的首要目 标是使该查询在执行时其通信代 价为最小，而要使通信代价最小，就必须使数据传输量最小。 分布式数据库系统中涉及的数据可能分布在几个场地， 引起数据在网络中来 回传输。 应采用较优的处理方法， 使网络中数据传输量最小。 而导致数据传输量 大的主要原因是数据间的连接操作。 目 前， 对于分布式数据库系统的查询处理有许多优化算法， 如基于关系代数 等价变换的优化算法、 基于半连接操作的优化算法、 基于直接连接操作的优化算 法。 由 美国计算机公司1 9 7 8 年研制的s d d 1 是分布式数据库管理系统的第一个 样机， 该系统 采用的 分 布式查询方法是多关系半 连 接算法， s d d _ 1查询 优化算 法大致思想是通过反复的获得有益半连接运算， 减少每个站点上用于连接运算的 数据， 然后将所有站点的数据汇集到数据量最大的站点做最后装配。 选择优化后 存储数据量最大的站点为查询的中间结果的组装站点， 这样可以使整个网络上的 传输量保持最小。 s d d _ 1查 询优化算 法是指定 局部数据库中经 过半连 接优化操作后数据量最 大的站点作为查询的中间结果的最后装配的站点。在分布式查询的实际应用中， 有时并不是指定局部数据库中的某一站点作为查询的中间结果最后装配的站点， 而是指定分布式数据库系统的缓冲区作为查询的中间结果的最后装配的站点， 对 于这种情况， s d d _ 1查 询优化算法显然不再适用， 寻找怎样的分布式查询优化 算法或技术成为了学术界及企业界的一个研究热点。 1 . 2本课题解决的问 题 本文在对现有的分布式查询优化算法研究的基础上， 对分布式数据库的多关 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 系半连接算法进行了 研究。本文的主要工作包括以 下几点: ( 1 ) 介绍了分布式数据库系统的基本概念，如分布式数据库系统的模式结构 及体系结构、数据分片的原则及分类、数据分布的策略等: ( 2 ) 简要描述了分布式查询的处理过程; ( 3 ) 研究了 分布式查询的一些常用算法，如基于关系代数等价变换规则的 优 化算法、基于连接的 优化算法、 基于半连接的优化算法、 s d d 1算法， 基于查 询图的贪婪算法; t 4 ) 在分布式查询的一些常用算法进行研究的基础上， 设计了一个新的算法， 本文称之为多关系半连接查询优化算法， 以适用于以 分布式数据库系统的缓冲区 作为查询的中间结果的最后装配的站点这种情况。 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 第二章 分布式数据库系统概述 2 . 1分布式数据库系统的定义及特点 2 . 1 . 1分布式数据库系统的定义 分布式 数据库系 统 ( d i s t r i b u t e d d a t a b a s e s y s t e m , d d b s ) 是 物理上分布而逻 辑上集中的数据库系统. 物理上分布是指分布式数据库系统中的数据分布在由网 络连接起来的、 地理位置分散的不同站点上: 逻辑上集中是指各数据库站点之间 在逻辑上是一个整体， 并由统一的数据库管理系统进行管理， 同时各站点又具有 管理本地数据的能力。 分布式数据库系统可看成是计算机网络与数据库系统的有 机结合。 分布式数 据库系统有两个重要的 组成部分: 分布式数据库 但i s t r i b u t e d d a t a b a s e , d d b ) 和分 布 式数 据 库 管 理系 统 ( d i s t ri b u te d d a ta b a s e m a n a g e m e n t s y s t e m , d d b ms ) o 分布式数据库是计算机网 络中各站点上数据库的逻辑集合。 也就是分布式数 据库是一组结构化的数据集合， 在逻辑上属于同一个系统， 在物理上分布在计算 机网络的不同站点上，是集中与分布的统一。 这个定义强调了分布式数据库的两种特性: ( 1 ) 数据分布性: 即这些数据库是分布在不同站点上的。 这把分布式数据库与单一的集中式数 据库区别开来。 ( 2 ) 逻辑关联性: 即这些数据库具有某些把它们联系在一起的性质。 这把分布式数据库与驻留 在计算机网络不同站点上的一组本地数据库区别开来。 分布式数据库管理系统是分布式数据库中的一组软件， 负责管理分布环境下 逻辑集成数据的存取、 一致性和完备性。同时，由于数据的分布性， 在管理机制 上还必须具有计算机网络通信协议的分布管理特性。 土海师范大学硕士学位论文分布式数据库的查询优化算法研究 2 . 1 . 2分布式数据库系统的特点 根据分布式数据库系统的定义， 可以知道分布式数据库系统具有如下四个基 本特点: ( 1 ) 物理分布性: 数据不是存在一个站点上，而是存储在计算机网络的多个站点上。 ( z ) 逻辑整体性: 数据物理分布在各个场地， 但逻辑上是一个整体， 它们被分布式数据库系统 的所有全局用户共享， 并由 一个分布式数据库管理系统统一管理。 这是分布式数 据库系统的逻辑整体性特点， 也是与分散式数据库系统的最大区别。 区别一个数 据库系统是分布式还是分散式，只要判断该系统是否支持全局应用。 ( 3 ) 站点自 治性: 各站点上的数据由本地的分布式数据库管理系统管理，具有自 治处理能力， 完成本场地的应用 ( 局部应用) 。 ( 4 ) 站点间协作性: 各站点虽然具有高度的自治性， 但是又相互合作构成一个整体。 对全局用户 来说， 使用分布式数据库系统如同集中式数据库系统一样， 用户可以在任何一个 站点执行全局应用。 由上述四个基本特点，可以推出分布式数据库系统的其他特点，包括: .数据独立性: 数据独立性是数据库方法追求的主要目 标之一。 分布式数据库系统的数据独 立性除了数据的逻辑独立性与数据的物理独立性之外，还包括数据分布透明性。 分布透明性是指用户或应用程序不必关心数据的逻辑分片， 不必关系数据物理位 置分配的细节， 也不必关心各个站点上数据库的数据模型是哪种类型， 可以像集 中式数据库一样来操作物理上分布的数据库。 .集中与自治相结合的控制机制: 在分布式数据库系统中， 同一站点上的局部用户共享本站点上的数据， 并由 本地数据库管理系统进行管理: 而在全局范围内， 全局用户共享系统中各个站点 上的数据，这种共享由集中的控制机制统一管理。 .适当增加数据冗余度: l 海师范大学硕士学位论文分布式数据库的查询优化算法研究 在集中 式数据库系统中， 尽量减少冗余是系统目 标之一。 其原因是冗余数据 不仅浪费空间， 而且容易引起的 数据的不一致性。 而在分布式数据库系统中， 确 希望通过冗余数据来提高系统的可靠性、 可用性和改善系统性能。 通过在多个站 点上存储数据的副本，使得当某一站点上的数据破坏时，系统仍可以正常运行; 另外， 系统可以 选择用户最近的数据副本进行操作， 以 减少通信代价， 改善整个 系统的性能。 .事务管理的分布性: 数据的分布性必然造成事务执行和管理的分布性。 即一个全局事务的执行可 分解为在若干站点上子事务 ( 局部事务)的执行。 事务的原子性、 一致性、 隔离 性持久性以及事务的恢复也都应该具有分布性特点。 2 . 1 . 3分布式数据库系统的分类 按局部数据库管理系统的模型可以将分布式数据库系统分为以 下三类: ( 1 )同构同质型d d b s : 各个站点都采用同一类型的数据模型 ( 例如，都是关系型) ，并且是同一型 号的d b m s ，如都是o r a c l e 类型。 ( 2 )同构异质型 d d b s : 各个站点采用同一类型的数据模型 ( 例如 号不同，如d b 2 , o r a c l e , s y b a s e , s q l s e r v e r 都是关系型) ， 但是d b ms的型 等。 ( 3 ) 异构型d d b s : 各个站点的数据模型的型号不同， 甚至类型也不同。 随着计算机网络技术的 发展， 例如， 有关系型的、 有面向对象类型的。 异种机联网问题已 经得到较好的 解决，此时依靠异构型d d m s 就能存取全网种各种异构局部库中的数据。 按分布式数据库系统的全局控制系统的类型可以将分布式数据库系统分为 以下三类: ( 1 ) 集中型 d d b s : d d b s 中的全局信息位于一个中心站点上。 ( 2 ) 分散型 d d b s : 每一个站点上包含全局控制信息的副本。 l 海师范大学硕士学位论文分布式数据库的查询优化算法研究 在集中 式数据库系统中， 尽量减少冗余是系统目 标之一。 其原因是冗余数据 不仅浪费空间， 而且容易引起的 数据的不一致性。 而在分布式数据库系统中， 确 希望通过冗余数据来提高系统的可靠性、 可用性和改善系统性能。 通过在多个站 点上存储数据的副本，使得当某一站点上的数据破坏时，系统仍可以正常运行; 另外， 系统可以 选择用户最近的数据副本进行操作， 以 减少通信代价， 改善整个 系统的性能。 .事务管理的分布性: 数据的分布性必然造成事务执行和管理的分布性。 即一个全局事务的执行可 分解为在若干站点上子事务 ( 局部事务)的执行。 事务的原子性、 一致性、 隔离 性持久性以及事务的恢复也都应该具有分布性特点。 2 . 1 . 3分布式数据库系统的分类 按局部数据库管理系统的模型可以将分布式数据库系统分为以 下三类: ( 1 )同构同质型d d b s : 各个站点都采用同一类型的数据模型 ( 例如，都是关系型) ，并且是同一型 号的d b m s ，如都是o r a c l e 类型。 ( 2 )同构异质型 d d b s : 各个站点采用同一类型的数据模型 ( 例如 号不同，如d b 2 , o r a c l e , s y b a s e , s q l s e r v e r 都是关系型) ， 但是d b ms的型 等。 ( 3 ) 异构型d d b s : 各个站点的数据模型的型号不同， 甚至类型也不同。 随着计算机网络技术的 发展， 例如， 有关系型的、 有面向对象类型的。 异种机联网问题已 经得到较好的 解决，此时依靠异构型d d m s 就能存取全网种各种异构局部库中的数据。 按分布式数据库系统的全局控制系统的类型可以将分布式数据库系统分为 以下三类: ( 1 ) 集中型 d d b s : d d b s 中的全局信息位于一个中心站点上。 ( 2 ) 分散型 d d b s : 每一个站点上包含全局控制信息的副本。 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 ( 3 ) 可变型 d d b s : 所有站点分为两组: 一组站点包含全局控制信息副本， 称为主站点;另一组 站点不包含全局控制信息的副本，称为副站点。 2 . 2数据分片与数据分布 数据分片与数据分布是分布式数据库中的两个重要概念， 分布式数据库大部 分问 题都与数据分片及数据分布有关， 对整个系统的可用性、 可靠性及效率都有 极大的影响， 同时也与分布式数据库系统的其他方面密切相关， 尤其是分布式查 询处理问题。 2 . 2 . 1关系分类 对于分布式数据库来说，全局关系模式将按照一定的条件划分成子关系模 式， 并按一定的分布原则将子关系对应的模式分布到适当的站点上。 因此， 可将 分布式数据库中的关系分为以 下三类: ( 1 ) 全局关系: 一个全局关系是指在分布式数据库系统中对用户是可见的，但是虚拟的。 ( 2 ) 逻辑片段; 是指实际存在的关系， 是全局关系在某个站点上的子关系的逻辑成分， 全局 关 系与逻辑关系间 有一 定 的映 射， 用分片模式定义， 映 射性质为1 : n ( n = 1 ) a ( 3 ) 物理片段: 一个关系称为物理片段， 指这个关系是在某一站点上的逻辑片段， 即是在某 一站点上的基本关系。 物理片段由 分布模式定义， 由于副本的存在， 一个逻辑片 段可对应一个或多个物理片段。 这三个关系之间的联系是: 一个全局关系由分片操作 ( 分片模式定义) 分解 成多个逻辑关系: 一个逻辑关系在几个站点上存放副本 ( 分布模式定义) 就产生 几个物理关系。这些分片信息和分布信息就构成了全局关系的分布结构。 2 . 2 . 2数据分片 数据分片( d a t a f r a g m e n t a t i o n ) 从逻辑上将全局概念模式， 即全局关系模式 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 ( 3 ) 可变型 d d b s : 所有站点分为两组: 一组站点包含全局控制信息副本， 称为主站点;另一组 站点不包含全局控制信息的副本，称为副站点。 2 . 2数据分片与数据分布 数据分片与数据分布是分布式数据库中的两个重要概念， 分布式数据库大部 分问 题都与数据分片及数据分布有关， 对整个系统的可用性、 可靠性及效率都有 极大的影响， 同时也与分布式数据库系统的其他方面密切相关， 尤其是分布式查 询处理问题。 2 . 2 . 1关系分类 对于分布式数据库来说，全局关系模式将按照一定的条件划分成子关系模 式， 并按一定的分布原则将子关系对应的模式分布到适当的站点上。 因此， 可将 分布式数据库中的关系分为以 下三类: ( 1 ) 全局关系: 一个全局关系是指在分布式数据库系统中对用户是可见的，但是虚拟的。 ( 2 ) 逻辑片段; 是指实际存在的关系， 是全局关系在某个站点上的子关系的逻辑成分， 全局 关 系与逻辑关系间 有一 定 的映 射， 用分片模式定义， 映 射性质为1 : n ( n = 1 ) a ( 3 ) 物理片段: 一个关系称为物理片段， 指这个关系是在某一站点上的逻辑片段， 即是在某 一站点上的基本关系。 物理片段由 分布模式定义， 由于副本的存在， 一个逻辑片 段可对应一个或多个物理片段。 这三个关系之间的联系是: 一个全局关系由分片操作 ( 分片模式定义) 分解 成多个逻辑关系: 一个逻辑关系在几个站点上存放副本 ( 分布模式定义) 就产生 几个物理关系。这些分片信息和分布信息就构成了全局关系的分布结构。 2 . 2 . 2数据分片 数据分片( d a t a f r a g m e n t a t i o n ) 从逻辑上将全局概念模式， 即全局关系模式 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 ( 3 ) 可变型 d d b s : 所有站点分为两组: 一组站点包含全局控制信息副本， 称为主站点;另一组 站点不包含全局控制信息的副本，称为副站点。 2 . 2数据分片与数据分布 数据分片与数据分布是分布式数据库中的两个重要概念， 分布式数据库大部 分问 题都与数据分片及数据分布有关， 对整个系统的可用性、 可靠性及效率都有 极大的影响， 同时也与分布式数据库系统的其他方面密切相关， 尤其是分布式查 询处理问题。 2 . 2 . 1关系分类 对于分布式数据库来说，全局关系模式将按照一定的条件划分成子关系模 式， 并按一定的分布原则将子关系对应的模式分布到适当的站点上。 因此， 可将 分布式数据库中的关系分为以 下三类: ( 1 ) 全局关系: 一个全局关系是指在分布式数据库系统中对用户是可见的，但是虚拟的。 ( 2 ) 逻辑片段; 是指实际存在的关系， 是全局关系在某个站点上的子关系的逻辑成分， 全局 关 系与逻辑关系间 有一 定 的映 射， 用分片模式定义， 映 射性质为1 : n ( n = 1 ) a ( 3 ) 物理片段: 一个关系称为物理片段， 指这个关系是在某一站点上的逻辑片段， 即是在某 一站点上的基本关系。 物理片段由 分布模式定义， 由于副本的存在， 一个逻辑片 段可对应一个或多个物理片段。 这三个关系之间的联系是: 一个全局关系由分片操作 ( 分片模式定义) 分解 成多个逻辑关系: 一个逻辑关系在几个站点上存放副本 ( 分布模式定义) 就产生 几个物理关系。这些分片信息和分布信息就构成了全局关系的分布结构。 2 . 2 . 2数据分片 数据分片( d a t a f r a g m e n t a t i o n ) 从逻辑上将全局概念模式， 即全局关系模式 土海师范大学硕士学位论文分布式数据库的查询优化算法研究 划分成若千个逻辑片段。分隔后的各逻辑关系之间遵循下列原则: ( 1 ) 完整性原则: 全局关系的所有数据项必须包括在任何一个片段中， 不允许出现某个数据项 属于全局关系，却不属于任何一个片段。 ( 2 ) 重构性原则: 通过对所有水平划分的片段执行并操作， 对所有垂直划分的片段执行连接操 作，可以重构成全局关系。 ( 3 ) 不相交原则: 一个全局关系的任何两个片段的交集为空 ( 垂直分片的主键属性除外) 。不 相交的原则不是必须的， 但有这个原则可使分隔不致太复杂。 分隔时不相交， 则 分布式的冗余可以得到控制。 根据上述原则，常用的分片方法有以下几种: ( 1 ) 水平分片: 按一定的条件将关系r按行分为 若干互不相交的子集r i , r 2 . . .r， 每一个子 集为关系的一个片段，各片段的并集构成原来的关系，即满足: r i u r 2 u . 二u r = r r ; n 药= 水 平 分片 实际 上 关 系的 选 择 操 作。 图2 . 1 伪 ) 是关 系r 的 水平 分 片的 例 子。 ( 2 ) 垂直分片: 将关系按列分为若干子集r i , r 2 . . 凡，垂直分片的自 然连接必须是原关系， 即满足: r i o r 2 0 . . o r , = r 垂直分片是对关系进行投影操作。图2 . 1 ( c ) 是关系r的垂直分片的 例子。 ( 3 ) 混合分片: 水平分片和垂直分片混合使用。图2 . 1 ( d ) 是关系r的混合分片的 例子， 在对数据分片时要注意分片程度， 片段过大过小都会影响系统效率， 因为片 段过大不利于数据分布及并发控制，片段过小会使查询操作经常涉及多个片段， 从而系统经常做额外的连接操作。 上海师范大学硕士学位论文 分布式数据库的查询优化算法研究 abcde l al bl cl dl e 2 a2 b2 c2 d2 e 3 a3 b3 c 3 d3 e 4 a 4 b4 c 4 d4 e ( a ) 关系r abcde 1 拓 islo1c1u1e 2 a 2 b2 c2 d2 e abcde 3 a3 b3 c3 d3 e 伪 ) 水平分片 acd 1，i 户1 d 么azeo 3 a3 c3 d abe l al bl e 2 a2 b2 e 3 a 3 b 3 e 4 a 4 b 4 e ( c ) 垂直分片 ab cd l al bl c l d 2 a 2 b2 c2 d abc 1 al bl c abe 2 a 2 b2 e ( d ) 混合分片 图2 . 1数据分片示例 上 海师范大学硕士学位论文分布式数据库的查询优化算法研究 2 . 2 . 3数据分布 数据分布 ( d a t a d i s t r i b u t i o n ) 是指在计算机网络各站点上的分布策略。 分布 式数据库系统中， 数据存储是先数据分片， 再数据分布。 也就是先将逻辑数据库 中的全局关系分成若干逻辑片段， 再按分布策略将这些片段分散存储在各个站点 上。数据分布的策略有以下四种: ( 1 ) 集中式: 所有数据片段都安排在同一个站点上。 这种分布策略使系统中所有活动都集 中 在单个站点上， 比较容易控制。 但所有检索和更新必须通过该站点， 使这个站 点负担过重， 容易形成瓶颈。 一旦这个站点出现故障， 将会使整个系统崩溃， 因 而系统的可靠性较差。 ( 2 ) 分隔式: 所有数据只有一份， 被分隔成若干逻辑片段， 每个逻辑片段被指派在一个特 定的站点上。 这种分布策略可以充分利用各站点上的存储设备， 数据的存储量大， 检索和更新本地数据有局部自 治性， 系统有可能发挥并发操作的潜力， 系统的可 靠性有所提高，当部分站点出现故障后， 系统仍可能继续运行。 对于全局性的查 询， 所需要的存取时间超过集中式分布方式， 因为数据在不同站点需要进行通信。 ( 3 ) 复制式: 数据在每个站点上重复存储，也就是每个站点上都有一个完整的数据副本。 这种分布策略的可靠性最高， 响应速度快， 数据库的恢复也容易实现， 可以从任 一站点得到数据副本。但是要保持各站点上数据库的同步则比较复杂且代价高。 另外，整个系统的数据冗余很大，系统的数据容量只是一个站点的数据容量。 ( 4 ) 混合式: 这是一种介于分隔式和复制式之间的分布方式。 数据库分成若干可相交的子 集， 每一子集安置在一个或多个站点上， 但是每一站点未必保存全部数据。 混合 式兼顾了分隔式和全复制式两个方式， 获得了两者的优点， 但是也带来了两者各 自 的复杂性。 这种分布策略的灵活性大， 对各种情况可分别对待， 以 提高整个系 统的效率。 例如， 对不重要的数据仅有一个副本， 而重要的数据可以安排多个物 理副本。 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 2 . 3分布式数据库系统的结构 2 . 3 . 1分布式数据库系统的模式结构 集中式数据库系统由 三级模式结构组成。即内模式、 概念模式、 外模式。 而 分布式数据库系统的模式结构为: 局部数据模式1 局部数据模式 2 +全局数据模式 局部数据模式 n 如图2 .2 所示， 局部数据模式是各站点上局部数据库系统的模式结构， 具有 集中式数据库系统的三级模式结构; 全局数据模式是用来协调各局部数据模式使 之成为一个整体的模式结构。 全局外模式全局外模式全局外模式 全局外模式2 全周被念模式映象 全局概念摸式 全局数据模式 全局概念摸式/ 分片模式映象 分片模式 分片模式/ 分段模式映象 分布模式 分布模式/ 局部概念模式映象 臀嘿fa a嘿馨 局部外模武/ 局部概念模式映象 局部外模式/ 局部概念摸式映象 局部数据模式 局部概念模式 局部概念模式 局部概念模刘/ 局部内模式映象 局部概念模式a 局部内摸式映 局部内模式局部内模式 局部数据库 局部数据库 图2 . 2分布式数据库系统的模式结构o l 上海师范大学硕士学位论文分布式数据库的查询优化算法研究 2 . 3分布式数据库系统的结构 2 . 3 . 1分布式数据库系统的模式结构 集中式数据库系统由 三级模式结构组成。即内模式、 概念模式、 外模式。 而 分布式数据库系统的模式结构为: 局部数据模式1 局部数据模式 2 +全局数据模式 局部数据模式 n 如图2 .2 所示， 局部数据模式是各站点上局部数据库系统的模式结构， 具有 集中式数据库系统的三级模式结构; 全局数据模式是用来协调各局部数据模式使 之成为一个整体的模式结构。 全局外模式全局外模式全局外模式 全局外模式2 全周被念模式映象 全局概念摸式 全局数据模式 全局概念摸式/ 分片模式映象 分片模式 分片模式/ 分段模式映象 分布模式 分布模式/ 局部概念模式映象 臀嘿fa a嘿馨 局部外模武/ 局部概念模式映象 局部外模式/ 局部概念摸式映象 局部数据模式 局部概念模式 局部概念模式 局部概念模刘/ 局部内模式映象 局部概念模式a 局部内摸式映 局部内模式局部内模式 局部数据库 局部数据库 图2 . 2分布式数据库系统的模式结构o l 上 海师范大学硕士学位论文分布式数据库的查询优化算法研究 全局数据模式具有四个层次: 全局外模式、 全局概念模式、 分片模式、 分布 模式。 ( i ) 全局外模式 ( g l o b a l e x t e rn a l s c h e m a ) : 全局外模式是全局应用的用户视图，是全局概念模式的逻辑子集。 ( 2 ) 全局概念模式( g l o b a l c o n c e p t u a l s c h e m a ) : 全局概念模式定义分布式数据库的全局数据的逻辑结构。 ( 3 ) 分 片 模式 ( f r a g m e n t a ti o n s c h e m a ) : 分片模式将全局关系分解为若干个不相交的部分， 即数据分片。 分片模式定 义片段以 及定义全局关系与片段之间的映象， 这种映象是一对多的， 即每个片段 来自 一个全局关系，而一个全局关系可分成若干片段。 ( ) 分 布 模式 ( a ll o c a t io n s c h e m a ) : 由数据分片得到的片段仍然是分布式数据库的全局数据， 是全局关系的逻辑 部分，每一个片段在物理上可定位 ( 分配) 于网络的一个或多个站点上。 分布模 式根据选定的数据分配策略， 定义各片段的物理存放站点。 在分布模式中， 定义 的映象类型确定了分布式数据库的数据分配是否冗余， 若映象是一对多的， 即一 个片段分配到多个站点重复存放，则数据分配是冗余的，否则是不冗余的。 分布式数据库系统的局部数据模式由局部概念模式与局部内模式组成。 ( 1 ) 局部概念模式( l o c a l c o n c e p t u a l s c h e m a ) : 一个全局关系经逻辑划分成一个或多个逻辑片段， 每个逻辑片段被分配在一 个或多个站点上， 称为该逻辑片段在某站点上的物理映象或物理片段。 分配在同 一站点上的同一个全局概念模式的若干片段 ( 物理片段) 构成了该全局概念在该 站点上的一个物理映象。 ( 2 ) 局部内 模式 ( l o c a l i n t e rn a l s c h e m a ) : 局部内 模式是分布式数据库中关于物理数据库的描述， 类似于集中式数据库 中的内模式。 2 . 3 . 2分布式数据库系统的体系结构 分布式数据库系统由分布式数据库管理系统和分布式数据库构成。 分布式数 据库管理系统是对数据进行管理和维护的一组软件， 是分布式数据系统的重要组 上 海师范大学硕士学位论文分布式数据库的查询优化算法研究 全局数据模式具有四个层次: 全局外模式、 全局概念模式、 分片模式、 分布 模式。 ( i ) 全局外模式 ( g l o b a l e x t e rn a l s c h e m a ) : 全局外模式是全局应用的用户视图，是全局概念模式的逻辑子集。 ( 2 )