关系数据库系统而言需要从两个方面讨.ppt

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