第九章查询处理 >9.1查询处理的过程 >92关系代数表达式的转换(重点) >93查询代价的度量 >9,4实现关系运算的拿法代价 >9.5表达式的求值方法 >96查询优化(量点) 10n
1 第九章 查询处理 ➢9.1 查询处理的过程 ➢9.2 关系代数表达式的转换（重点） ➢9.3 查询代价的度量 ➢9.4 实现关系运算的算法代价 ➢9.5 表达式的求值方法 ➢9.6 查询优化（重点）
91查询处理的过程 查询处理进程的三个步骤(见教材P159): (1)语法分析与翻译;(2)查询优化(重点);(3)査询执 行。 查询语句 <语法分析与翻译器 关系代数表达式 数据字典 优化器 查询输出 执行引擎 执行计划」数据字典 数据 图91查询处理过程 U∩
2 9.1 查询处理的过程 查询处理进程的三个步骤（见教材P159）： (1)语法分析与翻译；(2)查询优化（重点）；(3)查询执 行。 据 查询语句 语法分析与翻译器 关系代数表达式 执行计划 优化器 查询输出 执行引擎 数据字典 数据字典 数 图9.1 查询处理过程
优化器可以从数据字典中获取许多统计信息,例如 关系中的元组数、关系中每个属性值的分布情况等。 优化器可以根据这些信息选择有效的执行计划,而用 户程序则难以获得这些信息。 如果数据库的物理统计信息改变了,系统可以自动 对查询进行重新优化以选择相适应的执行计划。在非 关系系统中必须重写程序,而重写程序在实际应用中 往往是不太可能的。 >优化器可以考虑数百种不同的执行计划,而程序员 般只能考虑有限的几种可能性。优化器中包括了很 多复杂的优化技术,这些优化技术往往只有最好的程 序员才能掌握。系统的自动优化相当于使得所有人都 拥有这些优化技术。 30八
3 ➢优化器可以从数据字典中获取许多统计信息，例如 关系中的元组数、关系中每个属性值的分布情况等。 优化器可以根据这些信息选择有效的执行计划，而用 户程序则难以获得这些信息。 ➢如果数据库的物理统计信息改变了，系统可以自动 对查询进行重新优化以选择相适应的执行计划。在非 关系系统中必须重写程序，而重写程序在实际应用中 往往是不太可能的。 ➢优化器可以考虑数百种不同的执行计划，而程序员 一般只能考虑有限的几种可能性。优化器中包括了很 多复杂的优化技术，这些优化技术往往只有最好的程 序员才能掌握。系统的自动优化相当于使得所有人都 拥有这些优化技术
◆查询优化器 查询优化是影响RDBS性能的关键因素。主要解决下面3个 问题: 问题1:每个查询语句可以翻译成多个等价的关系代数表达 式,应该选择哪一个表达式? 例如有SQL语句: Select student number from student where student numberO student numberStudent number (o student number< " 000003"((student) 40八
4 ◆查询优化器 查询优化是影响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))
问题2:每个关系表达式中的关系运算可以用不同的算法 来实现,且可以采用不同的索引,应该选择何种算法或 索引? 问题3:对于表达式的求值何种采用计算方法? 以上三个问题的解决的方法形成执行计划。 50八
5 问题2：每个关系表达式中的关系运算可以用不同的算法 来实现，且可以采用不同的索引，应该选择何种算法或 索引？ 问题3：对于表达式的求值何种采用计算方法？ 以上三个问题的解决的方法形成执行计划
92关系代数表达式的转换 引例:“请给出计算机系的教师所讲课程的课程名称和 教师姓名”。用如下两个等价的关系代数表达式表达: ∏ course name, teacher name( o department name=“计算机 系”( teacher∞ teaching),其关系表达式树如下: I course name, teacher_ name o department name=“计算机系” teacher teachin g 6U八
6 9.2关系代数表达式的转换 引例：“请给出计算机系的教师所讲课程的课程名称和 教师姓名”。用如下两个等价的关系代数表达式表达： ➢∏course_name,teacher_name （σdepartment_name=“计算机 系”(teacher∞teaching))，其关系表达式树如下： ∏course_name,teacher_name teacher teaching ∞ σdepartment_name=“计算机系
course_name, teacher name(( o department name=“计算机 系”( teacher)∞ teaching),其关系表达式树如下: course name, teacher name department name=“计算机系“ teaching teacher 70八
7 ➢ ∏course_name,teacher_name （（σdepartment_name=“计算机 系”(teacher）∞teaching)，其关系表达式树如下： ∏course_name,teacher_name ∞ σdepartment_name=“计算机系“ teaching teacher
9.2.1等价规则 约定:用6表示谓词,用L表示属性列表,用E表示关系代数表达式。 (1)0的级联:06102(E=061(o2(E) (2)选择运算满足交换律:o01(062E)=02(o1(E)) (3)的级联 IL1(I12(…(ILn(E))…))=Iu1 (4)选择可与笛卡儿积以及 theta连接相结合: o6(E1×E2)=E1∞E 11062 E2)=E 001∧6212 (5) theta连接(包括自然连接)运算满足交换律: E1∞aE2=E 2 8 U∩
8 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)自然连接运算满足结合律: 3 1 00 (7)选择运算在选定条件下对0运算的分配律 (8)投影运算对θ运算具有分配律 (9)集合运算并与交运算满足交换律 (10)集合运算并与交运算满足结合律 (11)集合运算对并、交、差运算具有分配律 (12)投影运算对并运算具有分配律
9 （6）自然连接运算满足结合律： (E1 ∞ E2) ∞ E3 = E1 ∞（ E2 ∞ E3） （7）选择运算在选定条件下对θ运算的分配律 （8）投影运算对θ运算具有分配律 （9）集合运算并与交运算满足交换律 （10）集合运算并与交运算满足结合律 （11）集合运算对并、交、差运算具有分配律 （12）投影运算对并运算具有分配律
9.2.2表达式转换举例 若有关系模式: 学生(学号,学生姓名,所在系) 选课(学号,课程名),有关系表达式 例1:∏学生姓名(0所在系=“计算机系”(学生∞选课)) 此关系代数表达式的含义? 下面对此关系作等价变换: 利用规则7(1)可得如下等价表达式: ∏学生姓名((0所在系=“计算机系”(学生))∞选课) 0U0
10 9.2.2 表达式转换举例 若有关系模式： 学生（学号，学生姓名，所在系） 选课（学号，课程名），有关系表达式： 例1：∏学生姓名（σ所在系=“计算机系”(学生∞选课)） 此关系代数表达式的含义？ 下面对此关系作等价变换： 利用规则7（1）可得如下等价表达式： ∏学生姓名（（σ所在系=“计算机系”(学生））∞选课）