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

第11章关系代数操作的实现算法有效地处理用高级查询语言编写的用户查询是数据库管理系统的主要任务。对关系数据库系统而言，需要从两个方面讨论查询处理：第一方面是各种关系代数操作的算法及其复杂性分析；第二方面是产生逻辑优化的关系代数表达式或其它形式的查询计划。本章讨论第一个方面的工作；下一章讨论第二个方面的工作。第一节查询的处理过程第二节选择操作的实现算法第三节笛卡儿乘积的实现算法第五节投影操作的实现算法第六节集合的并交差实现算法.K第一节查询的处理过程查询是由高级查询语言(如SQL)表示的对数据库的一系列操作。下边是查询处理的基本流程：扫描与语法分析查询优化查询代码生成查询执行查询查询的内部表示查询的执行计划查询计划的执行代码查询结果1)语法检查；2)语义有效性检查;3)完整性安全性检查；4)产生查询的内部表示(树,图).确定优化的执行策略，产生优化的执行计划组合DBMS提供的各种操作算法，产生计划的执行代码控制执行查询计划，产生查询结果K1层次和网状数据库的查询语言是面向过程的语言，查询优化由用户程序负责.关系数据库的查询语言是非过程性的语言，查询优化应该由DBMS负责，但因最优化需要大量信息和相当耗时，故仅产生效率较高的执行计划。以下假设：每个关系储存在一个文件中。每个文件仅储存一个关系。下边的参数是本章经常使用的：TR关系R的元组数BR磁盘块数IR每个元组的字节数M主存缓冲区的块数b每个磁盘块字节数K11在分析关系代数各种操作的算法时，我们用对磁盘的存取块数来度量一个算法的复杂性。第二节选择操作的实现算法选择操作是在关系R中抽取满足条件C的元组，其SQL表示形式为：K2select*fromRwhereC1andC2orC3式中第一子式(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，则笛卡儿乘积RS的元组的字节数是IR＋IS，元组数目是TRTS，空间字节数是TRTS(IR＋IS)，占用磁盘块数是BRS=TRTS(IR＋IS)/b，其中b是磁盘块的容量。因此，笛卡儿乘积是一个非常耗时的操作。以下介绍笛卡儿乘积的四种实现算法。在选择算法时，要分析各种算法在访问磁盘时的复杂性和对内存缓冲区的要求。1简单算法2主存算法3半主存算法4大关系算法K31笛卡儿乘积的简单算法这种算法仅要求主存提供能容纳两个磁盘块数据的缓冲区。关系R和S各读一块到主存缓冲区，参加笛卡儿乘积运算。通过嵌套循环完成RS。算法定义为：RSK31输出RS对结果关系result初始化;forR每块RBdo读RB入主存;forS每块SBdo读SB入主存;在主存完成RB和SB的元组笛卡儿乘积,产生元组存入result;endfor;endfor;返回result.由于每读R一块，均扫描S一遍，故整个过程中，R读了一遍，而S读了BR遍。从而磁盘存取量为BR+BRBS+BRS，其中，BRS=TRTS(IR+IS)/b是输出结果的写盘块数。动画2笛卡儿乘积的主存算法这种算法假设内存缓冲区有足够的容量，能一次性地把关系R和S都读入主存，完成笛卡儿乘积运算。整个过程，两个关系各读了一遍。这种算法的磁盘存取量为BR+BS+BRS，其中BRS=TRTS(IR+IS)/b是写盘块数。算法的形式定义为：RSRSK32结果关系result初始化;把R和S读入主存;for主存中R的每个元组rdofor主存中S的每个元组sdo产生元组(rs)存入result;endfor;endfor;返回result.动画3笛卡儿乘积的半主存算法这种算法假定内存缓冲区比较大。把关系S一次性读入主存，而R则每次仅读一块到主存参加笛卡儿乘积运算。跟主存算法相同，整个过程，两个关系各读了一遍。磁盘的存取量为BR+BS+BRS，其中BRS=TRTS(IR+IS)/b是写盘块数。算法的形式定义为：RSRSK33result初始化;把S读入主存SB;forR每块RBdo读RB入主存;在主存完成RB和SB的元组笛卡儿乘积,产生元组存入result;endfor;返回result.该算法要求主存缓冲区能容纳BS+1个磁盘块。从磁盘存取量式子看到，R和S是对称的。若把关系R和S的地位对调，磁盘存取量并没有变化，但对主存缓冲区的要求却有所不同。动画4笛卡儿乘积的大关系算法设主存缓冲区的容量是M(即能容纳M个磁盘块的数据)。如果2Mmin(BR,BS)，那么，一方面，由于缓冲区容量的限制，我们无法采用主存算法和半主存算法降低磁盘访问复杂性；另方面，可以发挥M2的资源优势，采用比简单算法效率更高的算法。大关系算法分配给R和S的主存空间分别是1和M-1.算法如下：RSRSK34{把S分为BS/(M-1)个子集Si,每子集有M-1块}对结果关系result初始化；fori=1toBS/(M-1)do把Si读入主存;forj=1toBRdo把R的第j块读入主存；在主存完成RS；产生的元组存入result;endfor;endfor;由于S读了一遍，R读了BS/(M-1)遍，故磁盘存取量为BRBS/(M-1)+BS+BRS，其中BRS=TRTS(IR+IS)/b是写盘块数动画由于两个关系的连接操作实际上是笛卡儿乘积后再按条件选择元组，故连接操作的实现算法可在笛卡儿乘积算法基础上略加修改而成。由于选择操作和两个元组的接驳均在主存进行，故算法的修改并不改变读盘的复杂性，但结果输出量却有不同程度的减少。例如，基于笛卡儿乘积大关系算法的连接操作，读盘的块数仍是BRBS/(M-1)+BS，但连接结果的写盘块数却是BBRS.是等值比较符的连接操作称为等值连接。两个关系同名属性的等值连接称为自然连接。通过修改关系某些属性名，可以把等值连接转化为自然连接。本节仅考虑自然连接。一.连接操作结果的估计二.连接操作实现算法第四节连接操作的实现算法考虑关系R、S关于条件C的连接操作RcS。我们用作为连接操作符。关系R、S连接操作的SQL表示式如右图所示。其中是关系R的属性a和关系S的属性b之间的算术比较符。selectR.*，S.*fromR，SwhereR.aS.bK4本页分析所用符号：关系RS属性ABBC值域DAEDBDC元素数IAJIBIC元组数TRTSCABRS一.连接操作结果的估计与笛卡儿乘积有确定的输出量不同，连接(这里是指自然连接)操作的输出量取决于选择条件。以下是输出量的估计方法。设关系R的属性是A和B，关系S的属性是B和C.连接结果RS的属性是A、B和C.在下边的分析中，使用了右表中的符号。K41设(a,b,c)DADBDC,连接结果RS的元组数目为size(RS)=size(RS)PabcRS=size(RS)PabRPbEPbcS=IAIBIC[TR/(IAJ)][J/IB][TS/(IBIC)]=TRTS/IB连接结果RS块数U的估计为U(TRTS/IB)(IR+IS)/b其中b是每个磁盘块的字节数。(EDB)二.连接操作实现算法下边介绍四种常用的连接操作算法。在讨论中，用t[A1,A2,,AK]表示元组t在属性A1,A2,,AK的值。1.循环嵌套算法2.SORT-MERGE连接算法3.HASH连接算法4.索引连接算法后三种算法都要求对操作关系作某些附加的处理：SORT-MERGE连接算法需对操作关系按连接域作排序预处理。HASH连接算法需预先建立操作关系关于连接域的HASH存储结构。索引连接算法需要预先建立操作关系关于连接域的聚集索引结构。K421.RA=BS的循环嵌套算法类似于笛卡儿乘积的简单算法，该算法扫描操作关系R和S的元组，形成二重循环。所不同的是需要判别连接条件，只有满足连接条件的元组才能输出。设A、B分别是R、S的属性子集。RA=BS的算法是：K42a对result初始化；forrRdoforsSdoifr[A]=s[B]then(rs)写入resultendifendforendfor算法存取量的估计是BR+BRBS+U，其中BR和BS分别是关系R和S的磁盘块数，U是连接结果result的数据块数。为降低存取开销，取较小的关系R作为外循环。RSRSR每读一块S扫描一轮K42b2.RS的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存储结构HSBS/N块BS/N块BS/N块关系R的H存储结构HR形成HASH结构K42c3.RS的HASH连接算法1)按连接属性对R和S建立HASH文件HR和HS2)对桶号循环，用桶指针引导HR和HS连接.以桶数N的简单HASH结构为例，算法是：fori=0toN-1do连接HR和HS的第i桶Endfor;设元组分布均匀，各桶连接采用循环嵌套算法，则第i桶连接的存取块数是cost(BR/N,BS/N)=(BR/N)+(BR/N)(BS/N)(每读R一块，S第i桶的各磁盘块循环一遍)形成HASH结构的访问块数估计是O(BR+BS)4.RA=BS的索引连接算法(连接条件R.A=S.B)设S已对连接域B建立聚集索引文件IS。对R逐块逐元组循环，按连接域值查IS指针，得S记录，再连成大元组，写入结果关系。设S在连接域值域上均匀分布，算法的存取块数为BR+TRBS/I+U，其中，成绩块针900----880----864----822----788----758----788----…..788----…..758----…..成绩证号姓名900----…..880----…..864----…..864----…..822----…..822----…..822----…..788----…..788----…..稀疏索