2-2. 关系操作的基础算法(2)在线视频

下面我们来介绍一下集合运算在基于排序的实现算法

集合运算，我们说它是指并交叉这样的运算

这种运算它的特点是两个关系，一定是并兼容的

也就是说它必须是同构这样的一种关系

对于这样的一种运算，它是二元运算

那于这种运算，它在基于排序这种算法的实践基础之上

实际上是与归并排序的框架是一致的

也就是说如果R和S要进行这个集合运算的时候

我们首先要将R和S呢，进行排序，生成若干个有序子表

然后接下来再把它们两个的有序子表读入内存缓冲区

在内存里面再进行并交叉的运算

在这个里面呢，算法实现的过程当中大家要注意的是什么呢

就是怎么样对它进行排序，那么因为是两个进行集合运算的关系是并兼容的

所以呢，就说我们在排序的时候，一定要对主码进行排序

也就是说我们基于每个表格的主码，生成若干个有序子表

然后呢，将有序子表读入到内存当中

然后在内存里面呢，来进行这种元组的比较

这两个关系生成有序子表的数量有什么要求呢

有要求，我们对这两个关系生成有序子表的数量

肯定不能超过缓冲区的数量，也就是说当我排完序之后

两个关系的有序子表，要能够都读入到缓冲区里面来

你不能有一个子表读不进来，那就没有办法进行排序

所以这就是集合运算，这样的一种

实际上我说的是一个宏观的这样一种运算过程

具体的时间算法，大家要根据集合运算的一些特点

比如说像并运算，那肯定就是要找重复元组

那对于交运算呢，那就是找相同的元组

差运算呢，就是减去，我们这也给大家举一个例子

比如说是一个并运算的实现，是吧

那么，是两个关系R和S，那么我们仍然假设这个缓冲区呢

仍然只能是有三块用来进行读取数据的

每一个块可能容纳两个元组

在这种情况下我们要对R和S进行并运算

我们首先将它们生成有序子表，生成几个呢，生成三个

这生成这三个有序子表，一般来说我把较小的这张表格

比如说R比较小，就把它生成一个有序子表

S呢，比较大，我们就把它分成两个有序子表

那就R和S生成的有序子表的个数加起来是三，等于缓冲区的个数

然后接下来我们就在对这两个子表进行归并的过程当中

来进行这个并运算，我们把这两个有序子表的第一块分别都读入内存

比如R我们把它的第一块1,2读入内存

S1和S2第一块也分别读入内存，然后我们在内存当中

就开始也是按照最小值，比如说先找最小的1

那么因为是并，所以我们要把重复的元组删掉

不重复的元组再出来，所以这个和那个消除重复元组是非常相似的

所以它这个过程呢，我用动画给大家演示一下，基本上就是这样

我们把重复元组删掉之后，如果内存当中已经有这个缓冲区是空的

接下来把外存的数据读进来，一直重复这个过程

直到所有的数据全部读入内存，最后来执行运算

那么这就是并运算的实现，那么它的代价呢

就是归并的代价和最后我们进行这个读入数据之后

然后进行并运算的这样的一个代价，所以说

它等于归并的代价加两个文件块之和，这是有一个读入写出的过程

那么归并的代价当然就是两个有序子表的归并代价

那么这就是这个集合运算，那么对于差运算和交运算

我们只要在内存里面把运算的算法进行一下改变就可以了

那么下面我们在稍微说明一下自然连接运算

因为自然连接运算在关系运算当中是非常重要的

那么对于自然连接运算，它也是一个二元运算

两个表进行自然连接一定是具有公共属性，是吧

在公共属性上进行等值连接，比如R和S

那么它的运算从宏观上来讲和并运算是完全一样的

我们要把R和S首先呢，进行排序，生成若干个有序子表

然后再把它们的有序子表读入内存里面来

然后我们在内存里面来进行这种元组的匹配

当然如果我们要进行元组的匹配的话，一定也是一样

根据我们排序的顺序来进行的，那么在这个里面呢

我们需要注意的是两个有序子表如何进行排序的问题

这个呢，也一样，就是说它怎样进行排序能支持后续的运算呢

那显然一定是要在公共属性上进行排序

而且生成的有序子表的数量一定也与集合运算一样

要两个有序子表的和要等于缓冲区里面用于读取数据的块数

那么这就是自然连接运算的算法，那么它的这个代价也一样

等于归并的代价加上两个文件块读一次和写一次代价

那么到此为止呢，我们就把基于排序的关系运算的实现算法给大家介绍清楚了

下面我们来给大家介绍一下基于散列的两趟算法

那么散列，前面我们已经给大家介绍了很多

它都是根据搜索码值也好，或者是根据某一个属性

把一个数据文件要映射到不同地址空间上去

那么基于散列算法的框架呢

基本上与基于排序算法的框架是非常一样的

只不过排序是用来生成有序的两列子表

而散列呢，是要分成随机的不同的桶，那么它的框架也是两步

第一步，就是我们用散列函数把关系进行划分，生成Nh个散列桶

然后接下来我们对这些散列桶进行操作

把它读入到缓冲区里面，然后实现指定的操作

所以说一排基于排序的算法呢，是非常相似的

那么散列呢，因为它也要进行划分

所以它也要读入数据和读出数据

只不过中间要用散列函数来进行映射

那么它的代价实际上就是读一次数据和输出一次数据

也就是二倍的数据块的数量，我们用Br来表示这个关系的所占的磁盘块

这就是它的散列的时候的划分代价

我们在ppt上给大家也准备了散列这个一个伪代码的实现过程

有兴趣的同学呢，可以回去按照这个一个伪代码来编写散列的程序

当然，如果一个关系特别大的时候

我们可能一次散列达不到要求

这个时候我们需要对关系进行递归的划分

然后一直划分到每一桶它所占的磁盘块数与缓冲区的块数相一致

否则的话呢，如果我们桶特别大的话，我一次读不到缓冲区里面

后面我们就很难进行操作，所以呢，散列对桶的大小实际上还是有要求的

这个呢，大家要知道，下面我们就还是像基于排序的算法一样

来说一下基于散列算法它在进行关系运算的时候是怎么实现的

我们也先来看一下消除重复元组，那么消除重复元组呢

从宏观上来讲，它和基于排序是非常相似的

比如说我想对R这张表，把它里面所有重复的元组要消除掉的话

那我首先要对它进行散列，用哈希函数把整个R表分成若干个桶

比如说我生成n个桶，然后接下来我再讲这n个桶读入到缓冲区里面

然后在缓冲区里面我来建立合适的储存结构

然后在这个里面，我就可以去对重复的元组进行消除

这就是我们基于散列的消除重复元组的这样一种实现方法

当然，就说我们桶的数量一定与缓冲区的数量是一样的

这种实现方法它的代价就是关系散列的代价和我们最后的一次分区读入

有的人也把它用这个说

如果关系所占的磁盘块数是Br的话

实际上它的代价是三倍的Br，这是一种比较保守的估计

自然连接运算和这个基于排序的自然连接运算也是一样的

比如说两个关系的话，如果要进行自然连接运算

那么我要基于散列的方式，首先也一样

必须将R和S都要进行散列，散列成若干个桶

然后最后我把这些桶读入到数据里面来，读入到缓存里面来

缓存里面进行处理，一般的情况下基本上是这样子的

就说两个实现自然连接的这样的表，总是有一个比较大，一个比较小

那么一般的情况下呢，我们是把比较小的这张表

我们都要把它读入到缓存区里面来

就是把它划分的桶读入到缓存区里面来

然后在缓存里面建立非常适合的内存索引结构

然后对于比较大的这样的一张表

生成一些桶我们采用分区的这样的一种方式

然后会采用基于索引的这样的一种方式来进行实现

比如说拿出一个从这个s这张表生成的一个桶里拿出一个元组来

来到这个我们比较小的关系建立起来的索引结构里面去进行探查

看看符合要求的，我们就在结果之中进行显示

如果不符合要求，那么直接就抛弃掉

那么散列的这个要注意的是什么呢

就是我们一定是在连接属性上进行散列

而且采用的一定是相同的哈希函数进行散列

那么在散列的过程当中一般的来讲

只要比较小的关系经过散列以后，那么它能够符合我们前面说的要求

也就是说，比较小的关系经过散列以后

它每一个桶它所占的磁盘块的数量比这个缓存区的数量要小

或者说在缓冲区里面能够全部容纳下就可以了

那么这个基于散列这个自然连接的代价呢

实际上它和这个前面的这个消除重复元组或者是其他的运算也差不多一样

也就是说它也是指关系划分的代价再加上最后的一个分区读入这样的一个代价

那么这就是基于散列的这种两趟算法的实现

那么其他的运算我们就不在这过多的介绍了

在关系运算的第三类实现算法里呢，就是基于索引的算法

这个地方我不给大家做过多的介绍

因为索引大家都非常清楚，我们建立索引的目的就是为了加快查找

所以我们基于索引的算法实际上也就是利用索引它的这个功能

我们这里稍微说一下比如说我可以利用索引来实现连接运算

比如说一个R和S来进行连接运算的话

那么我R和S它们这种连接我们就可以把它转化成一种嵌套循环结构

那么在这种嵌套循环结构里面有一个关系一定是外层的

比如说R是个外层呢，然后呢

我从外层关系里面拿出来一个之后

我们就可以把这个关系的一个元组

按照它特定的搜索码值去寻找内存这个关系面的哪一个元组跟它进行匹配

那么在这个寻找的过程当中我们就可以使用索引

也就是说外层我拿出一个元组，那么它的搜索码值相当于就是已经确定了

我利用这个搜索码值，到内层关系里面

直接去探查哪个元组在什么地方，直接把它找出来

那么这就是基于索引的这样的一种连接运算

那么基于索引的其他运算实际上也有类似的这样的一种原理

就说，一般的情况下，我们都是在内层的运算当中使用索引

那么这种方法的代价呢，比较难估算

有人给出下面的一种代价描述

也就说，它是R的磁盘块的数量再加上

比如说这个S的一个磁盘块的数量乘以一个这个保守的这样的一个值