关系代数实现算法.ppt

第11章关系代数操作的实现算法有效地处理用高级查询语言编写的用户查询是数据库管理系统的主要任务。对关系数据库系统而言,需要从两个方面讨论查询处理:第一方面是各种关系代数操作的算法及其复杂性分析;第二方面是产生逻辑优化的关系代数表达式或其它形式的查询计划。本章讨论第一个方面的工作;下一章讨论第二个方面的工作。(如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都提供多种选择算法。不同的算法适用于不同的使用环境。有些算法要求参加运算的关系具有指定的存储结构或存取方法。下边介绍选择操作的实现算法。接下页谐球辅泰兆狸玻鸭权缆蛇磊姑赖次侦汉凑闲西衷涕抄丑鱼营翠化淆绅讼咨关系代数实现算法关系代数实现算法具有简单条件(条件中仅包含关系的一个属性):按原始顺序扫描关系,取出满足条件的元组。:要求关系已排序,并且选择条件是排序域上的等值比较。N元组的关系,其搜索时间复杂性是O(log2N)。:要求选择条件是主索引属性或HASH属性上的等值比较。:若条件是主属性上的非等值比较,则用等值比较可找出所有满足非等值比较条件的元组。。+树索引搜索。具有合取条件(一组简单条件用and连接而成):先按一个简单条件用前述方法选择,然后检查是否满足其它条件。:若合取条件都是等值比较,可考虑使用有关属性上的复合索引。:若合取条件是等值比较,可用各索引域的辅助索引得到元组指针集合,然后取这些集合的交集。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大关系算法K3哨碾曰矛纪卡哲末灰狡蕊苏作雾姻雇坪滴苫众歌陷汲赴抡漂敦秧怔轩泥喝关系代数实现算法关系代数实现算法1笛卡儿乘积的简单算法这种算法仅要求主存提供能容纳两个磁盘块数据的缓冲区。关系R和S各读一块到主存缓冲区,参加笛卡儿乘积运算。通过嵌套循环完成RS。算法定义为:RSK31输出RS对结果关系result初始化;forR每块RBdo读RB入主存;forS每块SBdo读SB入主