文档介绍：第九章查询处理
查询处理的过程
关系代数表达式的转换(重点)
查询代价的度量
实现关系运算的算法代价
表达式的求值方法
查询优化(重点)
查询处理的过程
查询处理进程的三个步骤(见教材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))
问题2:每个关系表达式中的关系运算可以用不同的算法来实现,且可以采用不同的索引,应该选择何种算法或索引?
问题3:对于表达式的求值何种采用计算方法?
以上三个问题的解决的方法形成执行计划。
引例:“请给出计算机系的教师所讲课程的课程名称和教师姓名”。用如下两个等价的关系代数表达式表达:
∏course_name,teacher_name (σdepartment_name=“计算机系”(teacher∞teaching)),其关系表达式树如下:
∏course_name,teacher_name
teacher
teaching
∞
σdepartment_name=“计算机系”
∏course_name,teacher_name ((σdepartment_name=“计算机系”(teacher)∞teaching),其关系表达式树如下:
∏course_name,teacher_name
∞
σdepartment_name=“计算机系“
teaching
teacher
等价规则
约定:用θ表示谓词,用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)投影运算对并运算具有分配律
表达式转换举例
若有关系模式:
学生(学号,学生姓名,所在系)
选课(学号,课程名),有关系表达式:
例1:∏学生姓名(σ所在系=“计算机系”(学生∞选课))
此关系代数表达式的含义?
下面对此关系作等价变换:
利用规则7(1)可得如下等价表达式:
∏学生姓名((σ所在系=“计算机系”(学生))∞选课)