第3篇 系统篇
第9章 关系查询处理和查询优化
1．试述查询优化在关系数据库系统中的重要性和可能性。
答：（1）查询优化在关系数据库系统中的重要性：
关系系统的查询优化既是RDBMS实现的关键技术，又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必考虑如何最好地表达查询以获取较好的效率，而且系统可以比用户程序的“优化”做得更好。
（2）查询优化在关系数据库系统中的可能性：
①优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性的分布情况、这些属性上是否有索引（B＋树索引、HASH索引、唯一索引或组合索引）等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。
②如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
③优化器可以考虑数十甚至数百种不同的执行计划，从中选出较优的一个，而程序员一般只能考虑有限的几种可能性。
④优化器中包括了很多复杂的技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。
2假设关系R（A，B）和S（B，C，D）情况如下：R有20000个元组，S有1200个元组，一个块能装40个R的元组，能装30个S的元组，估算下列操作需要多少次磁盘块读写。
（1）R上没有索引，select*from R；
（2）R中A为主码，A有3层B＋树索引，select*from R where A＝10；
（3）嵌套循环连接R⋈S；
（4）排序合并连接R⋈S，区分R与S在B属性上已经有序和无序两种情况。
答：假设存放连接结果的块因子Mrs＝20，即一个块能装20个连接后的元组。
如果R和S在B属性上已经有序，则需要读写20000/40＋1200/30＋20000/20＝1540块。
如果R和S在B属性上无序，则需要加上排序的代价：2*540＋（2*540*log2540）＝10882块。
3对学生课程数据库，查询信息系学生选修了的所有课程名称。
试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。
答：（1）学生-课程数据库用关系代数表示的语法树如图9-1所示：
图9-1 关系代数语法树
（2）优化后的标准语法树如图9-2所示：
图9-2 优化后的语法树
4对于下面的数据库模式
Teacher（Tno，Tname，Tage，Tsex）；Department（Dno，Dname，Trio）；Work（Tno，Dno，Year，Salary）
假设Teacher的Tno属性、Department的Dno属性以及Work的Year属性上有B＋树索引，说明下列查询语句的一种较优的处理方法。
（1）select * from teacher where Tsex＝‘女’
（2）select * from department where Dno＜301
（3）select * from work where Year＜＞2000
（4）select * from work where year＞2000 and salary＜5000
（5）select * from work where year＜2000 or salary＜5000
答：略。
5对于题4中的数据库模式，有如下的查询：
画出语法树以及用关系代数表示的语法树，并对关系代数语法树进行优化，画出优化后的语法树。
答：初始的关系代数语法树
优化后的关系代数语法树
6试述关系数据库管理系统查询优化的一般准则。
答：下面的优化策略一般能提高查询效率：
（1）选择运算应尽可能先做。
（2）投影运算和选择运算同时进行。
（3）投影同其前或其后的双目运算结合起来。
（4）某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
（5）找出公共子表达式。
（6）选取合适的连接算法。
7试述关系数据库管理系统查询优化的一般步骤。
答：各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下：
（1）把查询转换成某种内部表示，通常用的内部表示是语法树。
（2）把语法树转换成标准（优化）形式，即利用优化算法，把原始的语法树转换成优化的形式。
（3）选择低层的存取路径。
（4）生成查询计划，选择代价最小的。