4. 基于直接连接算法的查询优化在线视频

下面我们来介绍另外一种分布式查询优化算法，基于直接连接算法的查询优化

基于直接连接算法的查询优化有两种方式

一种是利用站点依赖信息来进行查询优化

另外一种是利用分片复制的方式

我们先来看一下利用站点依赖信息的连接

什么叫站点依赖呢？我们来先看一个例子

比如说在这张表里面有两个关系，R1和R2，还有两个站点，S1和S2

这个关系R1它分成两个片段，分别分布在这个S1和S2上，F12和F12

R2也分成两个片段在两个站点上，是F21和F22

如果我们要做两个关系的自然连接运算的话，比如说R1连接R2

那么我们希望是这样，在S1这个站点上F11连接F21

在S2这个站点上F12和F22的自然连接结果

但是如果要让这个结果成立的话，它的条件是什么呢

那么必须应该是这样的

两个片段F11和F12他们之间必须没有交集，也就是说它的交集应该是空

他们的交集是在自然连接属性A上投影的交集一定是空

同理F21和F22他们的交集也要是空，而且F11和F22、F12和F21也不应该有相交的情况

如果满足这种情况，我们前面的连接运算显然就可以成立

这样就是说R和S在分站点上直接执行就可以了

那么就引出来一个站点依赖的概念，它的概念是这样描述的

比如说我有两个关系R和S，他们分别分解成一个片段，比如说R分解成R1和R2

然后我们可以用Ri和Rj来进行表示，S也一样

比如说S1、S2、S3最后我们用Si和Sj

他们如果要进行自然连接就一定要有公共属性A1

所以他们都要包含这个公共属性A1

那么如果说有两个站点i站点和j站点

如果i和j不等的时候，我们有R这个片段和S在这个j站点上的片段在A属性上的取值

他们的交集如果等于空的话，那么我们就说R和S在属性A上站点依赖

它在属性A上这样一些取值，它是分布在不同的站点上的

而且不同站点上的片段他们是没有交集的

我们把这种情况叫做站点依赖

站点依赖有这样一些性质，比如说R和S如果他们的分片要是站点依赖的话

他们两个进行自然连接一定是在若干个站点上各个片段进行自然连接的一个并集

这就是它的性质，根据这个性质我们就可以使用站点依赖的方法来实现这个连接运算

我们把一个大关系的连接运算分成各个站点上片段的连接运算

最后对这个连接运算的结果进行一个并就可以了

这种运算它有很多优点，一个是我不需要进行数据传送

我直接向各个站点的数据发布命令，它直接做运算就行了

如果说运算传送，那只是运算结果的一个传送

再有一个就是这样的运算可以并行执行，各个站点同时可以执行，相互之间没有干扰

最后直接把结果进行搜集就可以了

再有一个就是这样的运算可以利用本地的索引提高效率

站点依赖其实它还有其他的一些性质可以使用

比如说我们在ppt上列出了两条性质

第一个如果R和S在属性A上站点依赖的话

那么对于A的一个超集，A是B的一个子集的话

那么R和S在属性B上也是站点依赖，这个结论是已经被人证明的

感兴趣的同学可以去查阅一些相关的资料

也就是说如果我们要在属性A上进行一个连接运算的话

如果B是A的一个超集，那么我们还可以在B上进行连接运算

如果R和S在属性A上站点依赖的话

而S和T在属性B上站点依赖，那么R、S和T他们直接进行三元连接运算的话

R连接S再连接T，也就等于在各个站点上，比如说Ri和Si进行连接

Si再和Ti进行连接，他们连接的结果的一个并集

这是它的另外一个性质，根据这个性质我们可以实现多个关系的连接运算

因此站点依赖这个算法如果我们在进行数据分配的时候满足这样的一种性质

我们就完全可以使用它进行查询的优化

在查询优化过程中，编译器需要去判断我什么时候可以使用站点依赖算法

这个我在这不做介绍，在我们高级数据库技术这本书的87页有详细的描述

大家可以去看

在直接连接算法之中，第二个是分片和复制算法

分片和复制算法就比较简单了一些

因为刚才我们说站点依赖是某一个关系分布在不同的站点上

属于没有冗余的分配，但实际上我们有些查询是满足不了这样的情况

完全没有数据传输的处理是不太可能的

而且我们在进行数据冗余分配的时候，也不一定能够满足这样的一些要求

所以这个时候我们可以完全采用分布式数据库的一些冗余的分配数据算法方法来解决

如果我们满足不了数据无传输的情况，我们怎么去做一个R和S的连接呢

我们可以这样去做，比如说前面我们讲的仍然是R1和R2

他们在S1和S2两个站点上分别分片

这两个分片如果满足不了这四个分片他们在A属性上没有交集这样一种情况

那么我们怎么去做呢，我们就可以这样去做

我们选择一个站点把查询中的某一个关系

它的所有的片段分布到这个站点上，比如说我选择S1和S2

然后我把查询中一个关系的片段，比如说R1的片段F11和F12分布在这个站点上

然后我再把查询中的其他的关系比如说R2

它这个R2，我们不进行分片了，把它分布在所有的站点上

这样的话我们就可以在站点上分别来计算R1和R2的连接运算，然后来进行合并

这样做的方法虽然说比站点依赖要有一些数据冗余

但实际上它的使用的覆盖面、覆盖的应用是比较广的

因为很多查询并不满足无数据传输

所以很多情况下我们要使用分片、复制算法，才能解决应用的问题

这个算法它也一样，我们可以使得连接运算在各个局部站点上执行

可以并行运算提高效率，另外 一种它也可以利用本地上的一些索引

比如说片段上的索引、我们可以在局部上为每一个关系的副本建立一个索引

来提高它查询的效率，到此为止我们就把分布式数据库查询的基本讨论的这样一些问题

比如它的基本概念、处理过程以及它的代价测量和优化的一些基本策略给大家介绍这么多

在这一章里面同学要重点理解分布式数据库查询优化的策略和它的一些基本步骤

尤其是要掌握半连接算法和直接连接算法它的实现过程