关系代数实现算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第11章 关系代数操作的实现算法,有效地处理用高级查询语言编写的用户查询是数据库管理系,统的主要任务。对关系数据库系统而言，需要从两个方面讨,论查询处理：第一方面是各种关系代数操作的算法及其复杂,性分析；第二方面是产生逻辑优化的关系代数表达式或其它,形式的查询计划。本章讨论第一个方面的工作；下一章讨论,第二个方面的工作。,第一节,查询的处理过程,第二节,选择操作的实现算法,第三节,笛卡儿乘积的实现算法,第五节,投影操作的实现算法,第六节,集合的并交差实现算法.,K,1,第一节 查询的处理过程,查询是由高级查询语言(如SQL)表示的对数据库的,一系列操作。下边是查询处理的基本流程：,扫描与语法分析,查询优化,查询代码生成,查询执行,查询,查询的,内部表示,查询的,执行计划,查询计划的,执行代码,查询结果,1)语法检查；2)语义有效性检查;,3)完整性安全性检查；,4)产生查询的内部表示(树,图).,确定优化的执行策略，,产生优化的执行计划,组合DBMS提供的,各种操作算法，产,生计划的执行代码,控制执行查询计划，,产生查询结果,K1,层次和网状数据库的查询,语言是面向过程的语言，,查询优化由用户程序负责.,关系数据库的查询语言是,非过程性的语言，查询优,化应该由DBMS负责，但,因最优化需要大量信息和,相当耗时，故仅产生效率,较高的执行计划。,2,以下假设：,每个关系储存在一个文件中。,每个文件仅储存一个关系。,下边的参数是本章经常使用的：,T,R,关系R的元组数,B,R,磁盘块数,I,R,每个元组的字节数,M 主存缓冲区的块数,b 每个磁盘块字节数,K1,1,在分析关系代数各种操作的算法时，,我们用对磁盘的存取块数来度量一个算法的复杂性。,3,第二节 选择操作的实现算法,选择操作是在关系R中抽取满足条件C的元组，,其SQL表示形式为：,K2,select *,from R,where C,1,and C,2,or C,3,式中第一子式(select)的含义是返回指定的属性，,第二子式(from)指出参加选择操作的关系。,第三子式(where)指出选择操作的条件。,选择条件可以是简单条件，也可以是复合条件，即把,一组简单条件用逻辑运算符and/or/not连接而成的条件。,如果逻辑运算符仅是and，则复合条件称为合取条件。,一般的DBMS都提供多种选择算法。不同的算法适用于不同,的使用环境。有些算法要求参加运算的关系具有指定的存储,结构或存取方法。下边介绍选择操作的实现算法。,接下页,4,具有简单条件(条件中仅包含关系的一个属性)的选择算法,1.,线性搜索：按原始顺序扫描关系，取出满足条件的元组。,2.二分搜索：要求关系已排序，并且选择条件是排序域上的,等值比较。N元组的关系，其搜索时间复杂性是,O(log,2,N),。,3.主索引或HASH搜索：,要求选择条件是主索引属性或HASH属性上的等值比较。,4.用主索引查找多个元组：,若条件是主属性上的非等值比较，,则用等值比较可找出所有满足非等值比较条件的元组。,5.使用聚集索引按等值比较条件寻找多个元组。,6.,使用,B,+,树索引搜索。,具有合取条件(一组简单条件用and连接而成)的选择算法,7.合取选择算法：先按一个简单条件用前述方法选择，,然后检查是否满足其它条件。,8.复合索引算法：若合取条件都是等值比较，,可考虑使用有关属性上的复合索引。,9.指针交集算法：若合取条件是等值比较，可用各索引域的,辅助索引得到元组指针集合，然后取这些集合的交集。,K2,1,5,第三节 笛卡儿乘积的实现算法,设：关系R和S的元组字节数分别是I,R,和I,S,，,元组数目分别是T,R,和T,S,，,则笛卡儿乘积R,S的元组的字节数是I,R,I,S,，,元组数目是T,R,T,S,，空间字节数是T,R,T,S,(I,R,I,S,)，,占用磁盘块数是B,R,S,=,T,R,T,S,(I,R,I,S,)/b，,其中b是磁盘块的容量。,因此，笛卡儿乘积是一个非常耗时的操作。,以下介绍笛卡儿乘积的四种实现算法。,在选择算法时，,要分析各种算法在访问磁盘时的复杂性和对内存缓冲区的要求。,1 简单算法,2 主存算法,3 半主存算法,4 大关系算法,K3,6,1 笛卡儿乘积的简单算法,这种算法仅要求主存提供能容纳两个磁盘块数据的缓冲区。,关系R和S各读一块到主存缓冲区，参加笛卡儿乘积运算。,通过嵌套循环完成R,S。算法定义为：,R,S,K31,输出,R,S,对结果关系result初始化;,for R每块R,B,do,读R,B,入主存;,for S每块S,B,do,读S,B,入主存;,在主存完成R,B,和S,B,的元组笛卡儿,乘积,产生元组存入result;,endfor ;,endfor;,返回result.,由于每读R一块，均扫描S一遍，故,整个过程中，R读了一,遍，而S读了B,R,遍。从而磁盘存取量为B,R,+B,R,B,S,+B,R,S,，其中，,B,R,S,=T,R,T,S,(I,R,+I,S,)/b是输出结果的写盘块数。,动画,7,2 笛卡儿乘积的主存算法,这种算法假设内存缓冲区有足够的容量，能一次性地把关系,R和S都读入主存，完成笛卡儿乘积运算。整个过程，两个关,系各读了一遍。这种算法的磁盘存取,量为B,R,+B,S,+B,R,S,，,其中,B,R,S,=T,R,T,S,(I,R,+I,S,)/b是写盘块数。算法的形式定义为：,R,S,R,S,K32,结果关系result初始化;,把R和S读入主存;,for 主存中R的每个元组r do,for 主存中S的每个元组s do,产生元组(rs)存入result;,endfor ;,endfor;,返回result.,动画,8,3 笛卡儿乘积的半主存算法,这种算法假定内存缓冲区比较大。把关系S一次性读入主存，而,R则每次仅读一块到主存参加笛卡儿乘积运算。跟主存算法相同，,整个过程，两个关系各读了一遍。磁盘的存取量为B,R,+B,S,+B,R,S,，,其中,B,R,S,=T,R,T,S,(I,R,+I,S,)/b是写盘块数。算法的形式定义为：,R,S,R,S,K33,result初始化;,把S读入主存S,B,;,for R每块R,B,do,读R,B,入主存;,在主存完成R,B,和S,B,的元组笛卡儿,乘积,产生元组存入result;,endfor;,返回result.,该算法要求主存缓冲区能容纳B,S,+1个磁盘块。,从,磁盘存取量式子看到，R和S是对称的。,若把关系R和S的地位对调，磁盘存取量并没有变化，,但对主存缓冲区的要求却有所不同。,动画,9,4 笛卡儿乘积的大关系算法,设主存缓冲区的容量是M(即能容纳M个磁盘块的数据)。,如果 2 M 2的资源优势，采用比简单算法效率,更高的算法。,大关系算法分配给R和S的主存空间分别是1和M-1.算法如下：,R,S,R,S,K34,把S分为B,S,/(M-1)个子集S,i,每子集有M-1块,对结果关系result初始化；,for i=1 to B,S,/(M-1) do,把S,i,读入主存;,for j=1 to B,R,do,把R的第j块读入主存；在主存完成R,S；,产生的元组存入result;,endfor;,endfor;,由于S读了一遍，R读了B,S,/(M-1)遍，故磁盘存取量为,B,R,B,S,/(M-1)+B,S,+B,R,S,，其中,B,R,S,=T,R,T,S,(I,R,+I,S,)/b是写盘块数,动画,10,由于两个关系的连接操作实际上是笛卡儿乘积后再按,条件选择,元组，故,连接操作的实现算法可在笛卡儿乘积算法基础上略加修,改而成。由于选择操作和两个元组的接驳均在主存进行，故算法,的修改并不改变读盘的复杂性，但结果输出量却有不同程度的减,少。例如，基于笛卡儿乘积大关系算法的连接操作，读盘的块数,仍是B,R,B,S,/(M-1)+B,S,，但连接结果的写盘块数却是B,B,RS,.,是等值比较符的连接操作称为等值连接。两个关系同名属,性的等值连接称为自然连接。通过修改关系某些属性名，可以把,等值连接转化为自然连接。本节仅考虑自然连接。,一. 连接操作结果的估计,二. 连接操作实现算法,第四节 连接操作的实现算法,考虑关系R、S关于条件C的连接操作R,c,S。,我们用,作为连接操作符。,关系R、S连接,操作的SQL表示式如右图所示。其中,是关,系R的属性a和关系S的属性b之间的算术比,较符。,select R.*，S.*,from R，S,where R.a, S.b,K4,11,本页分析所用符号：,关系 R S,属性 A B B C,值域 D,A,E,D,B,D,C,元素数 I,A,J,I,B,I,C,元组数 T,R,T,S,C,A,B,R,S,一. 连接操作结果的估计,与笛卡儿乘积有确定的输出量不同，连接,(这里是指自然连接)操作的输出量取决于选择,条件。以下是输出量的估计方法。,设关系R的属性是A和B，关系S的属性是B和C.,连接结果R,S的属性是A、B和C.在下边的分析,中，使用了右表中的符号。,K41,设(a,b,c),D,A,D,B,D,C,连接结果R,S的元组数目为,size(R,S)=size(R,S)P,abc,RS,=size(,R,S)P,ab,R,P,b,E,P,bc,S,=I,A,I,B,I,C,T,R,/(I,A,J)J/I,B, T,S,/(I,B,I,C,),=T,R,T,S,/I,B,连接结果R,S块数U的估计为,U(T,R,T,S,/I,B,)(I,R,+I,S,)/b,其中b是每个磁盘块的字节数。,(E,D,B,),12,二.连接操作实现算法,下边介绍四种常用的连接操作算法。,在讨论中，,用tA,1,A,2,A,K,表示元组t在属性A,1,A,2,A,K,的值。,1.循环嵌套算法,2.,SORT-MERGE连接算法,3. HASH连接算法,4. 索引连接算法,后三种算法都要求对操作关系作某些附加的处理：,SORT-MERGE连接算法需对操作关系按连接域作排序预处理。,HASH连接算法需预先建立操作关系关于,连接域,的HASH存储结构。,索引连接算法需要预先建立操作关系关于,连接域,的聚集索引结构。,K42,13,1. R,A=B,S的循环嵌套算法,类似于笛卡儿乘积的简单算法，该算法扫描操作关系R和,S的元组，形成二重循环。所不同的是需要判别连接条件，,只有满足连接条件的元组才能输出。,设A、B分别是R、S的属性子集。R,A=B,S的算法是：,K42a,对result初始化；,for r,R do,for sS do,if rA=sB,then (rs) 写入result,endif,endfor,endfor,算法存取量的估计是B,R,+B,R,B,S,+U，其中,B,R,和,B,S,分别,是关系R和S的磁盘块数，U是连接结果result的数据,块数。为降低存取开销，取较小的关系R作为外循环。,R,S,R,S,R每读一块,S扫描一轮,14,K42b,R,S,的,SORT-MERGE,连接算法,1),设关系,R,和,S,已按连接域排序，并且连接域至少对一个关,系来说是键属性。按照排序顺序扫描这两个关系的元组，,检验连接条件，把符合条件的元组进行连接。这个算法,的存取块数是,B,R,+B,S,+U,，,其中,U,是连接结果的磁盘块数。,2),一般情况下，先对各关系按连接域排序，然后用上述算,法连接，这就是,SORT-MERGE,连接算法。,排序操作可以由多路合并算法实现，,在主存缓冲区容量为,M,块的情况下，,对关系,R,排序的磁盘存取量是,(,B,R,log,M,B,R,),对关系,S,排序的磁盘存取量是,(,B,S,log,M,B,S,),所以,SORT-MERGE,连接算法的磁盘存取块数是,(,B,R,log,M,B,R,+,B,S,log,M,B,S,)+B,R,+B,S,+U,15,桶号 地址,0 -,1 -,N-1 -,桶号 地址,0 -,1 -,N-1 -,B,R,/N块,B,R,/N块,B,R,/N块,关系R,原始结构,共B,R,块,关系S,原始结构,共B,S,块,关系S的H存储结构H,S,B,S,/N块,B,S,/N块,B,S,/N块,关系R的H存储结构H,R,形成,HASH,结构,K42c,3.R,S,的,HASH连接算法,1)按连接属性对R和S建,立HASH文件H,R,和H,S,2)对桶号循环，用桶,指针引导H,R,和H,S,连接.,以桶数N的简单HASH,结构为例，算法是：,for i=0 to N-1 do,连接H,R,和H,S,的第i桶,Endfor;,设元组分布均匀，各,桶连接采用循环嵌套,算法，则第i桶连接的,存取块数是cost(B,R,/N,B,S,/N)=(B,R,/N)+(B,R,/N)(B,S,/N),(每读R一块，S第i桶的各磁盘块循环一遍),形成HASH结构的访问块数估计是,O(,B,R,+B,S,),16,4. R,A=B,S的,索引连接算法(连接条件R.A=S.B),设S已对连接域B建立聚集索引文件IS。对R逐块逐元组循环，按连,接域值查IS指针，得S记录，再连成大元组，写入结果关系。设S在,连接域值域上均匀分布，算法的存取块数为B,R,+T,R,B,S,/I+U，其中，,成绩 块针,900 -,880 -,864 -,822 -,-,758 -,788 - .,- .,758 - .,成绩 证号 姓名,900 - .,880 - .,864 - .,864 - .,822 - .,822 - .,822 - .,788 - .,788 - .,稀疏索引,非键值索引,数据文件按索引域排序,聚集索引IS,关系S,主存,缓冲区,按分数搜索,I为S连接域值域的大小，即,索引项数。对R的一个元组,扫描S的块数估计值为B,S,/I,K42d,关系R,17,K5,算法：,for R中每元组 do,RA,1,A,K,写入TMP,endfor ;,if A,1,A,K,含键 then,begin T:=TMP;retu;end,else去重复:仅取重复组的首项,begin 排序TMP；,i=1；j=2;,while i=n do,写TMP(i)到T；,while TMP(j)=TMP(i) do j=j+1;endwhile；,i=j；j=j+1;,endwhile,end；,输入：具有n个元组的关系R,输出：R的投影T=,A1,A2,AK,(R),第五节 投影操作,A,R,的实现算法,若投影域含键，仅需对R存取一次，否则结果可能有重复元组。,下边是删除重复的排序算法：,学号 成绩,001 70,002 80,003 80,004 80,005 92,006 92,007 96,008 98,009 98,成绩,70,80,80,80,92,92,96,98,98,除去重复,已排序,1,234,56,7,89,I,j,I,j j j,I,j j,I,j,I,j,T,投映,结果,记录号,TMP,算例执行的示意图,成绩,70 80 92 96 98,18,第六节 集合的并、交、差的实现算法,集合的并、交、差运算要求参加操作的关系具有相,同的属性结构，并且属性的顺序也须相同。为避免,出现重复扫描，可以使用排序的附加操作，也可,以使用HASH结构的方法。下边叙述利用预排序的,算法。首先在相同的键属性上排序操作关系，然后,扫描两个关系完成操作。,1.并操作R,S(对称运算),2.交操作R,S(对称运算),3.差操作R-S(不对称运算),K6,19,1. 并操作R,S,这种操作具有对称性，即R,SS,R.,假设关系R和S分别有n和m个元组，,R的序号为i，S的序号为j.,算法如下： (用R,i,(k)表示R第i元组的键值),K61,算法简例：设R与S都仅,有一个属性(是键)。排,序后分别是：,R：1,4,5,6 (n=4),S：2,4 (m=2),执行过程是：,i=j=1;,比较1和2,输出1,i改为2;,比较4和2,输出2,j改为2;,比较4和4,输出4, i=j=3;,循环停止;,输出R剩余元组5,6.,算法停止.,操作结果：1,2,4,5,6.,关于键k对两关系的元组作升序排列；,i=1；j=1；,while i,n and,j,m,do,比较R,i,(k)与S,j,(k) 较小一方称为小方,若不等，,输出小方元组；小方序号加1；,若相等，,输出元组R,i,； 两序号都加1；,endwhile；,若i,n,， 则输出R的剩余元组；,若j,m,，则输出S的剩余元组.,20,K62,2. 交操作R,S,这种操作具有对称性，即R,SS,R.,假设关系R和S分别有n和m个元组，,R的序号为i，S的序号为j.,算法如下：,算法简例：设R与S都仅,有一个属性(是键)。排,序后分别是：,R：1,4,5,6 (n=4),S：2,4 (m=2),执行过程是：,i=j=1;,比较1和2，i改为2;,比较4和2，j改为2;,比较4和4，i=j=3;,循环停止.,算法停止.,操作结果：4.,关于键k对两关系作升序排列；,i=1；j=1；,while i,n and,j,m,do,比较R,i,(k)与S,j,(k) 较小一方称为小方,若不等，,小方序号加1；,若相等，,输出元组R,i,；两序号都加1；,endwhile.,21,K63,3. 差操作R,S,这种操作不具对称性，即即R,-,S,S,-,R.,假设关系R和S分别有n和m个元组，,R的序号为i，S的序号为j.,算法如下：,算法简例：设R与S都仅,有一个属性(是键)。排,序后分别是：,R：1,4,5,6 (n=4),S：2,4 (m=2),执行过程是：,i=j=1;,比较1和2,输出1,i改为2;,比较4和2, j改为2;,比较4和4, i=j=3；,循环停止;,输出R剩余元组5,6.,算法停止.,操作结果：1,5,6.,关于键k对两关系作升序排列；,i=1；j=1；,while i,n and,j,m,do,比较R,i,(k)与S,j,(k),若R,i,(k)小，则取R,i,；序号i加1；,若S,j,(k)小，则序号j加1；,若相等， 则i和j均加1；,endwhile；,若i,n,， 则输出R的剩余元组.,22,