第五章分布式数据库设计

1、5 分布式数据库设计本章主要解决分布式数据库模型设计问题，具体指出数据分段与分配的方法，即数据分布问题。这些方法是面向应用开发人员的。5 . 1 分布式数据库设计概述考虑集中式数据库设计的内容:(1) 概念模式的设计(包括应用所需要的全部数据)(2) 物理数据库设计,即将概念模式映射到存储区域,并决定合适的存取方法.分布式也要做这两件事,只不过化为:(1) 全局模式的设计 对应上面（1）(2) 每个站点的本地物理数据库设计 （2）解决的方法与集中式相同，都是用关系数据库规范化理论和文件的物理组织方法。同时在第（1）与第（2）步之间还要做：(1) 分段模式的设计(2) 分配模式的设计这两方面恰好

2、全面表征了数据分布设计的特点，二者互相关联，要综合考虑。在设计数据库之前，必须充分了解需求，严格按照软件工程的方法来设计数据库，做好数据库应用系统中的关键一环。（核心问题）需求应包括：（1）都有哪些应用和哪些用户？应用与用户的对应，每个用户的功能需求（给出用例图，详细描述每个应用所用的数据及处理流程、应用与应用之间的时序关系等）（2）每个应用发出的站点（原发站点）（3）每个应用被使用的频度（4）每个应用对数据对象访问的次数、访问类型、统计分布情况等（5）每个数据对象数据量的大小，值的分布情况。（6）站点间的距离、传输单位信息的费用5.1.1 数据分布设计的目标（1）处理的本地性把数据和使用它们

3、的应用尽量靠近-当然最好是在原发站点（2）可用性和可靠性可用性-对只读应用，可就地使用副本可靠性-在物理上分散的站点分别存放副本，一旦正在使用站点上的数据出了问题（如盘坏了），可使用其它站点上的数据。（3）工作负荷均衡-各尽所能，要考虑每个站点的能力、效率不同等因素，也要与本地性折衷考虑。（4）经济上的考虑-经费开销少（存储、CPU、I/O、通讯等），相比之下，优先考虑通讯。（5）效率方面的考虑-本地性、通讯量少、负荷均等也都会提高效率（互补）。上述几条目标应综合考虑，有些情况是互补的，有些情况又是矛盾的（可靠与同步更新）。特别地要优先考虑大频率的、费时的、实时的应用。5.1.2 自顶向下和自

4、底向上的数据分布设计方法（1）自顶向下的方法（2）自底向上的方法5. 2 数据库分段设计（分段模式设计）数据分布设计包括分段和分配设计，分配的最小的逻辑单位是段。分段是分配的起点，但并不是终点，分配过程中可能还有改变。回顾分段设计的规则：（1）完整性-全局关系中的任意数据必存在于某个段中。（2）可重构性-必须能够由段重新构成全局关系（3）不相交性-主要是指水平分段和导出式水平分段，这2种分段方式必须是全局关系的一个划分，即任意一个元组只能属于一个段，并且用所有段的合并运算重构全局关系；但对于垂直分段，如没重复的数据则没有结合属性，也就无法重构全局关系。对于混合分段，显然是递归进行的，每步或是水

5、平与导出式水平分段、或是垂直分，只要每步都按照上述规则，混合分段的结果也必然满足上述规则。5.2.1 水平分段与导出式水平分段的设计 5.2.1.1 水平分段（初级分段）的设计 根据分段的基本条件，水平分段意味着要确定一组能使分段不相交、且完整的选择谓语，也就是限定语。为了便于讨论，不防令R是一个全局关系，并引入下述定义：（1） 简单谓语： pi ： 属性名属性值 其中， 可以是算术比较、关系、集合等运算符。 （2）最小项谓语设P简单谓语P1，P2，,PN的集合，若Y是P的最小项谓语，则Y就是P中所有简单谓语的合取，其中每个简单谓语或者为自然形式，或者为否定形式，且Y不为永假。 即 Y = p

6、i* piP这里，pi*= pi，或者pi*= NOT pi，且Y永假（3）一个段是一个最小项谓语所包含的所有元组的集合。(4) 简单谓语pi与简单谓语集合P相关的条件是：若P至少有两个最小项谓语（即至少有两个段），且其间的区别仅仅取决于pi两种形式（自然和否定），则至少有一个应用以不同的方法来访问相应的段。/？问题：如何评价分段是比较好的？或称合适的？可以这样回答：p 完整且最小。所谓完整是指：同一个段中任意两个元组被任意应用等概率访问。所谓最小是指：p 中每个pi都p与相关。 水平分段的方法： 5.2.1.2 导出式水平分段的设计 导出式水平分段应充分考虑段与段之间的分布式结合是否得到简化

7、。 （1）充分调查两个全局关系的结合应用（2）最好的方案是形成简单结合图。（3）通常采用半结合或自然半结合进行分段5.2.2 垂直分段的设计 当某些重要应用只涉及全局关系R的某个属性集，而另一些重要应用只涉及全局关系R的另一个属性集，这两类应用又发自不同站点，则应采取垂直分段，这可避免访问较大的关系R时，不同站点间大量的数据传输。例：垂直分段可以是：（1） 垂直分片-除了起结合作用的属性而外，段间再没有重复的属性。（2） 垂直群集 -除了起结合作用的属性而外，段间还有重复的属性。（这在集中式数据库设计时是不提倡的，为什么在分布式数据库设计中要有这种考虑？）5.2.3 混合分段的设计混合分段的最

8、简单方法包括：（1） 把水平分段应用到垂直分段中（2） 把垂直分段应用到水平分段中虽然可以递归地重复这些操作来产生各种复杂的分段树，但多于两级的分段并不切合实际。5 . 3 段的位置分配（分配模式设计） 根据应用，对于每一个全局关系R中的为每一个段Ri，为其分配一个站点集合，这个集合中至少含有一个站点。当只含一个站点时表示不重复分配，否则为重复分配。 5.3.1 段分配的一般准则一般对于一个全局关系R，其中段Ri，段Rj完全可能被分配到同一个站点，这样是否应该将二者再合并成一个段？这样做显然不适合，当初之所以分成二个段，一定是考虑了访问频度的问题，防止大批量数据没有任何意义的进行内外存交换。

9、段分配的一般准则是把几个设计目标综合考虑。 5.3.2 段分配的费用和得益的估量为了便于费用和得益的估量，下面给出一些符号的定义：i 是段的下标名，j 是站点的下标名，K 是应用的下标名fkj 是应用K在站点j上出现的频率rki 、uki 分别是应用K对段i进行检索、更新访问的次数nki = rki+uki 是应用 k 对段i访问的次数5.3.2.1 水平分段（1）采用最佳得益站点法，其基本思想是：对任意一个水平分段Ri ：寻找一个最优的站点j，如果把段Ri放在站点j上，可以使得Ri被本地访问的次数最多。计算公式为： 对于R的每一个段i ,做下面的计算:Bi j =fkj nki K求 MAX

10、（B i j） （对于j =1，2，）由此,我们就为每个段Ri都找到了一个最佳的站点。下面考虑再为每个段Ri寻找合适的所有可以重复存放的站点。（2）采用所有得益站点法，其基本思想是：在（1）的基础上（段Ri已经有一个合适的站点），如果段Ri在某个站点上的检索应用的费用比从所有其它站点上发出对段Ri进行更新应用的费用总和还要高，则将段Ri重复地存放在这个站点上。计算公式为： Bi j =fkj rki c fkj uki K K jj这里，j是给定的（j跑遍除了（1）中选出的每个站点）。引入变量jj，是因为在j站点上更新时还必须考虑j站点上的更新。如果 Bi j 0 就可以把段Ri复地存放在这个

11、站点上。 5.3.2.2 垂直分段 （？）现在假设段Ri在站点r上，需要进一步考虑是否对段Ri垂直分成两段Rs和Rt，并将它们分别分配到站点s和站点t上。可类似地通过得、失两方面加以分析。 Bist =fks nki +fkt nki fkr nki KAs KAt KA1- 2fkr nki - c fkj nki KA2 KA3 jr,s,t 1 存在两组应用As和At，自站点s或t上发出这些应用，且它们分别只使用Rs和Rt的属性。显然，As，At都变为本地应用，分别省了一次异点访问（失益）。2 存在一组应用A1，（请求在r上），以前局限于站点r，只使用Rs或Rt的属性：现在这些应用需要进

12、行一次附加的异点访问（失益）。3 存在一种应用A2，以前局限于站点r（请求在r上发生），使用Rs和Rt这两者的属性，而现在这些应用需要进行两次附加的异点访问（失益）。4 存在一组应用A3，位于不同于r，s或t的站点上，它们要访问Rs和Rt这两者的属性，现在这些应用需要附加一次异点访问（失益）。 5.3.2.3 垂直群集垂直群集：（在已经垂直分段的基础上，考虑两垂直段间重复属性的问题）即设Ri已分配给站点r，先将Ri垂直分成两个段Rs、Rt，且分别分配到站点s和t上，如何考虑二者中重复属性集的得失问题。Bist =fks nki +fkt nki fkr uki KAs KAt KA1- c fkj uki KA2 jr,s,t 1存在应用组As自站点S发出：它们或者读取 R s的任何属性，或者更新Rs中不属于的属性。 2存在应用组At，自站点t发出，读取Rt的任何属性，或者更新Rt中不属于中的属性。（以上两点均为得益） 3存在应用组A1，自站点r发出，它们对的属性进行更新应用，以前只使用Rs