数据库系统概论chp09

《数据库系统概论chp09》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据库系统概论第九章关系查询处理和查询优化第九章关系系统及其查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小结关系系统及其查询优化（续）本章目的：RDBMS的查询处理步骤查询优化的概念基本方法和技术查询优化分类：代数优化物理优化9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1.1查询处理步骤RDBMS查询处理阶段：1.查询分析2.查询检查3.查询优化4.查询执行查询处理步骤（续）查询处理步骤1.查询分析对查询语句进行扫描、词法分

2、析和语法分析从查询语句中识别出语言符号进行语法检查和语法分析2.查询检查根据数据字典对合法的查询语句进行语义检查根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查检查通过后把SQL查询语句转换成等价的关系代数表达式RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式把数据库对象的外部名称转换为内部表示3.查询优化查询优化：选择一个高效执行的查询处理策略查询优化分类：代数优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择查询优化方法选择的依据：基于规则(rulebased)基于代价(

3、costbased)基于语义(semanticbased)4.查询执行依据优化器得到的执行策略生成查询计划代码生成器(codegenerator)生成执行查询计划的代码9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.1.2实现查询操作的算法示例一、选择操作的实现二、连接操作的实现一、选择操作的实现［例1］Select*fromstudentwhere<条件表达式>；考虑<条件表达式>的几种情况：C1：无条件；C2：Sno＝'200215121'；C3：Sage>20；C4：Sdept＝

4、'CS'ANDSage>20；选择操作的实现（续）选择操作典型实现方法：1.简单的全表扫描方法对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出适合小表，不适合大表2.索引(或散列)扫描方法适合选择条件中的属性上有索引(例如B+树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组选择操作的实现（续）［例1-C2］以C2为例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码)使用索引(或散列)得到Sno为‘20021

5、5121’元组的指针通过元组指针在student表中检索到该学生［例1-C3］以C3为例，Sage>20，并且Sage上有B+树索引使用B+树索引找到Sage＝20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生。选择操作的实现（续）［例1-C4]以C4为例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引：算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage>20的另一组元组指针求这

6、2组指针的交集到student表中检索得到计算机系年龄大于20的学生算法二：找到Sdept＝‘CS’的一组元组指针通过这些元组指针到student表中检索对得到的元组检查另一些选择条件(如Sage>20)是否满足把满足条件的元组作为结果输出。二、连接操作的实现连接操作是查询处理中最耗时的操作之一本节只讨论等值连接(或自然连接)最常用的实现算法［例2]SELECT*FROMStudent，SCWHEREStudent.Sno=SC.Sno；连接操作的实现（续）1.嵌套循环方法(nestedloop)2.排序-合并方法(sort

7、-mergejoin或mergejoin)3.索引连接(indexjoin)方法4.HashJoin方法连接操作的实现（续）嵌套循环方法(nestedloop)对外层循环(Student)的每一个元组(s)，检索内层循环(SC)中的每一个元组(sc)检查这两个元组在连接属性(sno)上是否相等如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止连接操作的实现（续）2.排序-合并方法(sort-mergejoin或mergejoin)适合连接的诸表已经排好序的情况排序－合并连接方法的步骤：如果连接的表没有排

8、好序，先对Student表和SC表按连接属性Sno排序取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组连接操作的实现（续）200215121200215122200215123200215124...2002151211922002151212852002151213