数据库系统概论课件--第九章.ppt

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

1、数据库系统概论AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化AnIntroductiontoDatabaseSystem第九章关系系统及其查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小结AnIntroductiontoDatabaseSystem关系系统及其查询优化（续）本章目的：RDBMS的查询处理步骤查询优化的概念基本方法和技术查询优化分类：代数优化物理优化AnIntroductiontoDatabase

2、System9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例AnIntroductiontoDatabaseSystem9.1.1查询处理步骤RDBMS查询处理阶段：1.查询分析2.查询检查3.查询优化4.查询执行AnIntroductiontoDatabaseSystem查询处理步骤（续）查询处理步骤AnIntroductiontoDatabaseSystem1.查询分析对查询语句进行扫描、词法分析和语法分析从查询语句中识别出语言符号进行语法检查和语法分析AnIntro

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

4、查询优化方法选择的依据：基于规则(rulebased)基于代价(costbased)基于语义(semanticbased)AnIntroductiontoDatabaseSystem4.查询执行依据优化器得到的执行策略生成查询计划代码生成器(codegenerator)生成执行查询计划的代码AnIntroductiontoDatabaseSystem9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例AnIntroductiontoDatabaseSystem9.1.2实现查

5、询操作的算法示例一、选择操作的实现二、连接操作的实现AnIntroductiontoDatabaseSystem一、选择操作的实现［例1］Select*fromstudentwhere<条件表达式>；考虑<条件表达式>的几种情况：C1：无条件；C2：Sno＝'200215121'；C3：Sage>20；C4：Sdept＝'CS'ANDSage>20；AnIntroductiontoDatabaseSystem选择操作的实现（续）选择操作典型实现方法：1.简单的全表扫描方法对查询的基本表顺序扫描，逐一检查每个

6、元组是否满足选择条件，把满足条件的元组作为结果输出适合小表，不适合大表2.索引(或散列)扫描方法适合选择条件中的属性上有索引(例如B+树索引或Hash索引)通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组AnIntroductiontoDatabaseSystem选择操作的实现（续）［例1-C2］以C2为例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码)使用索引(或散列)得到Sno为‘200215121’元组的指针通过元组指针在student表中

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

8、>20的另一组元组指针求这2组指针的交集到student表中检索得到计算机系年龄大于20的学生算法二：找到Sdept＝‘CS’的一组元组指针，通过这些元组指针到student表中检索对得到的元组检查另一些选择条件(如Sage>20)是否满足把满足条件的元组作为结果输出。AnIntroductiontoDatabaseSystem二、连接操作的实现连接操作是查询处理中最耗时的操作之一本节只讨论等值连接(或自然连接)