第十章

1．试述查询优化在关系数据库系统中的重要性和可能性。

重要性:

关系系统的查询优化既是 RDBMS 实现的关键技术,又是关系系统的优点所在，它减轻了用户选择存取路径的负担,用户只要提出“于什么”不必指出“怎么干”。

查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率 ,而且在于系统可以比用户程序的“优化"做得更好。

可能性:

优化器可以从数据字典中获取许多统计信息 ,例如各个关系中的元组数,关系中每个属性值的分布情况 ,这些属性上是否有索引、`是什么索引(B+树索引、Hash 索引、唯一索引，还是组合索引) ,等等。优化器可以根据这些信息选择有效的执行计划 ,而用户程序则难以获得这些信息。

如果数据库的物理统计信息改变了,系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序,而重写程序在实际应用中往往是不太可能的。

优化器可以考虑数十甚至数百种不同的执行计划,从中选出较优的一个,而程序员一般只能考虑有限的几种可能性。

2．假设关系 R(,B)和S(,C,D)的情况如下:R有 20 000 个元组,S有 1 200 个元组 ,一个块能装 40 个 尺的元组 ,能装 30 个的 S 元组 ,估算下列操作需要多少次磁盘块读。

对R全盘扫描,块数=20000/40=500

对R进行索引扫描 块数=3+1=4,3块B+树索引,1块数据块

如果R和S在B属性排好序,块数 500+40=540,没有排序,则还要加上排序代价 结果为540+2-500*(log2 500 +1)+2*40*(log2 40 +1)

3．对学生-课程数据库 ,查询信息系学生选修了的所有课程名称。

SELECT Cname
FROM Student,Coures,SC
WHERE Student,Sno=SC.Sno AND SC.Cno=Course.Cno AND Student.Smajor='信息管理与信息系统'

4．对于数据库模式

Teacher( Tno,Tname,Tage,Tsex) ;

Department( Dno,Dname,Tno) ;

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

1.对 teacher 进行全表扫描,查看元组是否满足性别为女。

2.如果满足 dno < 301 的元组数目较少,可以通过索引找到 dno= 301 的索引项,然后顺着 B+树的顺序集得到 dne < 301 的索引项,通过这些指针找到 department 中的元组;如果dno < 301 的元组数目较多 ,可以采用对 department 的全表扫描方式处理。

3.对 work 进行全表扫描,查看元组是否满足 year <> 200

4.通过 year 的索引找到满足 year > 2000 的元组 ,检查元组是否满足 salary < 5000。

5.对 work 进行全表扫描,查看元组是否满足 year < 2000 或 salary < 5000。

5．对于题 4 中的数据库模式 ,存在如下的查询

SELECT tname
FROM teacher,department,work
WHERE teacher.tno=work.tno AND department.dno= work.dno AND
department.dname= "计算机系" AND salary > 5000

画出语法树以及用关系代数表示的语法树 ,并对关系代数语法树进行优化,画出优化后的语法树。

6．试述关系数据库管理系统查询优化的一般准则。

1. 选择运算应尽可能先做。

2. 把投影运算和选择运算同时进行。

3. 把投影同其前或其后的双目运算结合起来执行。

4. 把某些选择同在它前面要拓行的笛卡儿积结合起来成为三余连接运算。

5. 找出公共子表达式。

6. 选取合适的连接算法。

7．试述关系数据库管理系统查询优化的一般步骤。

1. 把查询转换成某种内部玫示器通常用的内部玫示兹语法树。

2. 把语法树转换成标准(优化)形式,即利用优化算法把原始的语法树转换成优化的形式。

3. 选择低层的存取路径。

4. 生成查询计划;选择所需代价最小的计划加以执行。