系统概论王珊_系统概论第五版_系统概论(6)

关系管理系统一般都用查询树，也称为语法分析树来表示扩展的关系代数表达式。 3. 查询优化 查询优化：选择一个高效执行的查询处理策略 查询优化分类 代数优化/逻辑优化：指关系代数表达式的优化 物理优化：指存取路径和底层操作算法的选择 查询优化的选择依据 基于规则 rule based 基于代价 cost based 基于语义 semantic based 4. 查询执行 依据优化器得到的执行策略生成查询执行计划 代码 code generator 生成执行查询计划的代码 两种执行方法 自顶向下 自底向上 9.1 关系系统的查询处理 9.1.1 查询处理步骤 9.1.2 实现查询操作的算法示例 9.1.2 实现查询操作的算法示例 选择操作的实现 连接操作的实现 1.选择操作的实现 选择操作典型实现方法： （1） 全表扫描方法 Table Scan 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出 适合小表，不适合大表 （2）索引扫描方法 Index Scan 适合于选择条件中的属性上有索引 例如B+树索引或Hash索引 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组 选择操作的实现（续） [例9.1] SELECT * FROM Student WHERE 考虑 的几种情况： C1：无条件； C2：Sno＝'座机电话号码1'； C3：Sage 20； ：Sdept＝'CS' AND Sage 20； 选择操作的实现（续） 全表扫描算法 假设可以使用的内存为M块，全表扫描算法思想： 按照物理次序读Student的M块到内存 检查内存的每个元组t，如果满足选择条件，则输出t 如果student还有其他块未被处理，重复①和② 选择操作的实现（续） 索引扫描算法 [例9.1-C2] SELECT * FROM Student WHERE Sno '座机电话号码1' 假设Sno上有索引 或Sno是散列码 算法： 使用索引 或散列 得到Sno为‘座机电话号码1’ 元组的指针 通过元组指针在Student表中检索到该学生 选择操作的实现（续） [例9.1-C3] SELECT * FROM Student WHERE Sage 20 假设Sage 上有B+树索引 算法： 使用B+树索引找到Sage 20的索引项，以此为入口点在B+树的顺序集上得到Sage 20的所有元组指针 通过这些元组指针到student表中检索到所有年龄大于20的学生。

选择操作的实现（续） [例9.1-] SELECT * FROM Student WHERE Sdept 'CS' AND Sage 20; 假设Sdept和Sage上都有索引 算法一：分别用Index Scan找到Sdept＝’CS’的一组元组指针和Sage 20的另一组元组指针 求这两组指针的交集 到Student表中检索 得到计算机系年龄大于20的学生 选择操作的实现（续） 算法二：找到Sdept ’CS’的一组元组指针， 通过这些元组指针到Student表中检索 并对得到的元组检查另一些选择条件 如Sage 20 是否满足 把满足条件的元组作为结果输出。 2.连接操作的实现 连接操作是查询处理中最耗时的操作之一 本节只讨论等值连接 或自然连接 最常用的实现算法 [例9.2] SELECT * FROM Student, SC WHERE Student.Sno SC.Sno; 连接操作的实现（续） （1）嵌套循环算法 nested loop join （2）排序-合并算法 sort-merge join 或merge join （3）索引连接 index join 算法 （4）Hash Join算法 连接操作的实现（续） （1）嵌套循环算法 nested loop join 对外层循环 Student表 的每一个元组 s ，检索内层循环 SC表 中的每一个元组 sc 检查这两个元组在连接属性 Sno 上是否相等 如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25972-6.html