【数据库技术】查询处理.pptVIP

第九章 查询处理 9.1 查询处理的过程 9.2 关系代数表达式的转换（重点） 9.3 查询代价的度量 9.4 实现关系运算的算法代价 9.5 表达式的求值方法 9.6 查询优化（重点） 9.1 查询处理的过程 查询处理进程的三个步骤（见教材P159）： (1)语法分析与翻译；(2)查询优化（重点）；(3)查询执行。 优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。 查询优化器 查询优化是影响RDBMS性能的关键因素。主要解决下面3个问题： 问题1：每个查询语句可以翻译成多个等价的关系代数表达式，应该选择哪一个表达式？ 例如有SQL语句： Select student_number from student where student_number“s000003” 等价表达式为： σstudent_number“s000003”(∏ student_number(student)) ∏student_number(σstudent_number“s000003”((student)) 9.2关系代数表达式的转换 引例：“请给出计算机系的教师所讲课程的课程名称和教师姓名”。用如下两个等价的关系代数表达式表达： ∏course_name,teacher_name （σdepartment_name=“计算机系”(teacher∞teaching))，其关系表达式树如下： ∏course_name,teacher_name ∏course_name,teacher_name （（σdepartment_name=“计算机系”(teacher）∞teaching)，其关系表达式树如下： ∏course_name,teacher_name 9.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 ∞ θ2 E2)= E1 ∞ θ1∧ θ2 E2 （5） theta连接（包括自然连接）运算满足交换律： E1 ∞ θ E2 = E2 ∞ θ E1 （6）自然连接运算满足结合律： (E1 ∞ E2) ∞ E3 = E1 ∞（ E2 ∞ E3） （7）选择运算在选定条件下对θ运算的分配律 （8）投影运算对θ运算具有分配律 （9）集合运算并与交运算满足交换律 （10）集合运算并与交运算满足结合律 （11）集合运算对并、交、差运算具有分配律 （12）投影运算对并运算具有分配律 9.2.2 表达式转换举例 若有关系模式： 学生（学号，学生姓名，所在系） 选课（学号，课程名），有关系表达式： 例1：∏学生姓名（σ所在系=“计算机系”(学生∞选课)） 此关系代数表达式的含义？ 下面对此关系作等价变换： 利用规则7（1）可得如下等价表达式： ∏学生姓名（（σ所在系=“计算机系”(学生））∞选课） 例2：∏学生姓名（（σ所在系=“计算机系”∧课程名 like“数据库%“(学生∞选课)） 此关系代数表达式的含义？ 下面对此关系作等价变换： 利用规则7（2）可得如下等价表达式： ∏学生姓名（（σ所在系=“计算机系”（学生）） ∞ （σ课程名 like“数据库%“（选课）)） 关系表达式树分别如下： 9.3 查询代价的度量 9.3.1 查询处理的代价 查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。 在集中式数据库中，查询的执行开销主要包括： 总代价 = I/O代价 + CPU代价 在多用户环境下： 总代价 = I/O代价