分布式数据库设计

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最⼤，就把⽚段分配到哪个站点。