【数据库技术】查询处理

《【数据库技术】查询处理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查询处理9.1查询处理的过程9.2关系代数表达式的转换（重点）9.3查询代价的度量9.4实现关系运算的算法代价9.5表达式的求值方法9.6查询优化（重点）9.1查询处理的过程查询处理进程的三个步骤（见教材P159）：(1)语法分析与翻译；(2)查询优化（重点）；(3)查询执行。据关系代数表达式查询语句语法分析与翻译器执行计划优化器执行引擎查询输出数据字典数据字典数图9.1查询处理过程优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些

2、信息。如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。查询优化器查询优化是影响RDBMS性能的关键因素。主要解决下面3个问题：问题1：每个查询语句可以翻译成多个等价的关系代数表达式，应该选择哪一个表达式？例如有SQL语句：Selectstud

3、ent_numberfromstudentwherestudent_number<“s000003”等价表达式为：σstudent_number<“s000003”(∏student_number(student))∏student_number(σstudent_number<“s000003”((student))问题2：每个关系表达式中的关系运算可以用不同的算法来实现，且可以采用不同的索引，应该选择何种算法或索引？问题3：对于表达式的求值何种采用计算方法？以上三个问题的解决的方法形成执行计划。9.2关系代数表达式的转换引例：“请给出计算

4、机系的教师所讲课程的课程名称和教师姓名”。用如下两个等价的关系代数表达式表达：∏course_name,teacher_name（σdepartment_name=“计算机系”(teacher∞teaching))，其关系表达式树如下：∏course_name,teacher_nameteacherteaching∞σdepartment_name=“计算机系”∏course_name,teacher_name（（σdepartment_name=“计算机系”(teacher）∞teaching)，其关系表达式树如下：∏course_name

5、,teacher_name∞σdepartment_name=“计算机系“teachingteacher9.2.1等价规则约定：用θ表示谓词，用L表示属性列表，用E表示关系代数表达式。（1）σ的级联：σθ1∧θ2(E)=σθ1(σθ2(E))（2）选择运算满足交换律：σθ1(σθ2(E))=σθ2(σθ1(E))（3）∏的级联：∏L1（∏L2（…（∏Ln（E））…））=∏L1(E)（4）选择可与笛卡儿积以及theta连接相结合：σθ(E1×E2)=E1∞θE2σθ1(E1∞θ2E2)=E1∞θ1∧θ2E2（5）theta连接（包括自然连接）运

6、算满足交换律：E1∞θE2=E2∞θE1（6）自然连接运算满足结合律：(E1∞E2)∞E3=E1∞（E2∞E3）（7）选择运算在选定条件下对θ运算的分配律（8）投影运算对θ运算具有分配律（9）集合运算并与交运算满足交换律（10）集合运算并与交运算满足结合律（11）集合运算对并、交、差运算具有分配律（12）投影运算对并运算具有分配律9.2.2表达式转换举例若有关系模式：学生（学号，学生姓名，所在系）选课（学号，课程名），有关系表达式：例1：∏学生姓名（σ所在系=“计算机系”(学生∞选课)）此关系代数表达式的含义？下面对此关系作等价变换：利用规则

7、7（1）可得如下等价表达式：∏学生姓名（（σ所在系=“计算机系”(学生））∞选课）例2：∏学生姓名（（σ所在系=“计算机系”∧课程名like“数据库%“(学生∞选课)）此关系代数表达式的含义？下面对此关系作等价变换：利用规则7（2）可得如下等价表达式：∏学生姓名（（σ所在系=“计算机系”（学生））∞（σ课程名like“数据库%“（选课）)）关系表达式树分别如下：∞学生选课∏学生姓名σ所在系=“计算机系”∧课程名like“数据库%“学生∏学生姓名∞σ所在系=“计算机系”σ所在系=“计算机系”学生选课例2关系代数表达式例1关系代数表达式9.3查询

8、代价的度量9.3.1查询处理的代价查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要