分布式数据库设计.pdf

分布式数据库设计 分布式数据库设计 DDB设计的两个问题 1）分段 – 分割关系成"段" ；逻辑上 2）分配 – 将段置放到站点 ；物理存储上 ⽬标 – 优化响应时间/吞吐量/费⽤/… 分段元则 假若有全局关系R 被分段为⼦关系(⽚段)集合， – 完整性，分⽚之后，不能丢失元素 – 不相交性，每⼀个元素只能分配到唯⼀的⼀个分段 – 重构性，存在函数 g 使得 R = g(F1 , F2 , …, Fn ）。 也就是通过分⽚，能够还原出原来的数据总体 ⽔平分段 把不同性质的元组，分割为不同的分段 基本⽔平分段 以关系E⾃⾝的属性性质为基础，执⾏"选择"操作，将关系分割成若⼲个不相交的⽚段 例如： 对于学⽣表，根据班级编号这⼀性质，将学⽣元组分割多个⽚段。 如何选择⼩项谓词 什么⼩项谓词？ ⼩项谓词就是划分条件的各种可能的组合，⽐如： 但是上⾯的⼩项谓词，相当⼤⼀部分都是不符合语义的，因为没有实际的数据对应这些⼩项谓词。 还是回到刚才的那个问题：如何选择⼩项谓词集作为分段的依据呢？ 仍然是以例⼦来说话： 应⽤a访问Loc = Sa 的元组；应⽤b则访问Loc = Sb的元组。 （1）不分段 （2）按照{Loc = sa,loc = sb}来分段，分两段 （3）按照{loc = sa,loc = sb,sal < 10}来分段，分4端； 只有⼀个分段的话，对⼀个特定的应⽤，分组内的元组选择概率不相等，因此不好。⽐如：对于应⽤a，它只会选择loc = sa的元组，⽽不选择loc = sb的元组。元组选择的概率不等，因此不好。 对于分成四个分段的⽅案，由于对于同⼀个应⽤，两个分段选择的概率是相等的，这样也不好。 所以最理想的情形是：对每个特定的应⽤，最好能把它所要访问的所有元组集中在⼀个分段，⽽且只是⼀个分段（⼩项性） 导出分段 从另⼀个关系的属性性质或⽔平分段推导出来。 ⽐如有选课表和学⽣表， SC(S#, C#, GRADE) S ( S#, SNAME. AGE, SEX) 按照学⽣表中的性别属性，将SC表拆分成两个分段，SC1，SC2，分别存储的是男⽣和⼥⽣的选课信息。 ⼀般如何来实现导出分段呢？半连接操作 也就是在连接操作的基础上，进⾏投影操作，筛选出R的属性。它的意义在于在R中筛选出能够与S进⾏连接的元组⽽过滤出⽆⽤的元组。 以学⽣-选课表为例，先将学⽣表根据性别划分成两个分段S1，S2，再让SC分别与S1和S2进⾏半连接操作即可。 注意：导出分段的完整性和不相交性不能得到保证，除⾮（学⽣表是导出表，选课表是被导出表）： 1）导出属性在导出表中是主键； 2）满⾜引⽤约束（属性如果存在于被导出表，则必须也存在于导出表）； 垂直分段 通过"投影"操作把⼀个全局关系的属性分成若⼲组 。垂直分段的基本⽬标是将使⽤频繁的属性聚集在⼀起。 垂直分段，保证重构性的⽅式就是在每个分段中都保留主关键字。这样，通过⾃然连接操作可重构出原来的数据整体。 如何来进⾏垂直分段？ 通过属性的亲和矩阵 就是找出所有这样的应⽤：它既访问了判断A1⼜访问了⽚段A2，把他们的频率之和相加。 要通过⾏列调整寻找分割点 混合分段 先⽔平分段，再垂直分段； 先垂直分段，再⽔平分段。 分配 在满⾜⽤户需求的前提下, 把设计好的数 据⽚段分配到相应的站点上存储 分配的有关问题 查询来源 通讯费⽤? 结果⼤⼩, 关系,… 存储容量, 存储费⽤? 分段⼤⼩? 站点处理能⼒? 查询处理策略? – 连接操作算法 – 查询结果收集站点 简化模型如下： 读的代价为： 写代价： 存储代价如下： 最后得⽬标函数： 要计算出这个⽬标函数的值，是⼀个NP难问题。 所以采⽤⼀个简单的法则：尽可能将⽚段分配在被局部访问位置，即尽量做到本地化的访问。 最佳适应⽅法 充分考虑到了应⽤的访问次数，哪个站点的B最⼤，就把⽚段分配到哪个站点。