关系代数实现算法.pptVIP

* 第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， 则笛卡儿乘积R?S的元组的字节数是IR＋IS， 元组数目是TRTS，空间字节数是TRTS(IR＋IS)， 占用磁盘块数是BR?S=TRTS(IR＋IS)/b， 其中b是磁盘块的容量。 因此，笛卡儿乘积是一个非常耗时的操作。 以下介绍笛卡儿乘积的四种实现算法。