（本科）第2.5查询优化ppt课件.pptx
课程主讲人：第2.5查询优化 2.5 查询优化 数据管理经历了三个发展阶段：人工管理阶段；文件系统阶段数据库系统阶段。 3用户输入查询查询的内部表示执行查询步骤向用户报告查询结果查询语句的句法分析查询优化处理查询 1 1、响响应应用用户户查查询询的的一一般般过过程程 2.4 查询优化查询优化 4例：查询学号为091502的学生选修的课程名称。E1=课程名(课程.学号=学习.学号学习.学号=091502(课程学习)E2=课程名(课程.学号=学习.学号(课程 学号=091502(学习)E3=课程名(课程 学号=091502(学习)查询效率：E3E2E12.4.1 查询优化的必要性查询优化的必要性 5关系代数表达式的等价变换规则1）连接、笛卡尔积交换律 E1E2E2 E1 E1 E2 E2 E1 E1 E2 E2 E1FF2）连接、笛卡尔积结合律 (E1E2) E3 E1(E2E3 ) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3)F1F2F1F22.4.1 查询优化的必要性查询优化的必要性 63、投影的串接定律(注意条件)A1,A2,An(B1,B2,Bm(E) A1,A2,An(E)4、选择的串接定律F1(F2(E) F1F2(E)5、选择与投影的交换律（注意条件）F(A1,A2,An(E) A1,A2,An (F(E)（F只涉及A1,A2,An ）A1,A2,An (F(E) A1,A2,An F(A1,An,B1,Bm(E)6、选择与笛卡尔积的交换律F (E1E2) F (E1 ) E2F (E1E2) F1 (E1 ) F2(E2) F (E1E2) F 2(F 1(E1 ) E2) 77、选择与并的交换F (E1E2) F (E1 ) F (E2)8、选择与差的交换F (E1-E2) F (E1 ) -F (E2)9、投影与笛卡尔积的交换律A1,A2,An,B1,B2,Bm (E1E2) A1,A2,An (E1) B1,B2,Bm ( E2)10、投影与并的交换A1,A2,An(E1E2)A1,A2,An (E1) A1,A2,An(E2)2.4.1 查询优化的必要性查询优化的必要性 85、关系代数表达式的优化算法输入：一个关系表达式的语法树输出：计算该表达式的程序方法：1)把F1F2 .Fn(E)变换为 F1 (F2(Fn( E) 2)对每一个选择尽可能把它移到树的叶端。 3)对每一个投影尽可能把它移到树的叶端。4)合并选择和投影或一个选择后跟一个投影。5)将得到的语法树的内节点分组。(每一双目运算和它所有的直接祖先为一组。6)生成一个程序，每组节点的计算是程序中的一步。求值顺序为先子孙，后祖先。规则4规则3,5,9,10规则4-8规则3-5 9 1、尽可能早地执行选择操作（减少中间运算结果） 2、合并笛卡尔积和其后的选择操作，使之称为一个连接运算 3、合并连续的选择和投影操作，以免分开运算造成多次扫描文件，从而节省了操作时间 4、找出表达式里的公共子表达式。 5、适当地对关系文件做预处理2.4.2 查询优化的策略和算法查询优化的策略和算法 10例：求001001号学生所选修的课程名及成绩 CN,G （SC.S#=001001SC.C#=C.C# （SC C）CN,GSC.S#=001001SC.C#=C.C#SCC2.4.2 查询优化的策略和算法查询优化的策略和算法 11CN,GCN,GSC.C#=C.C#SC.C#=C.C#SCSCC C SC.S#=SC.S#=001001001001CN,GCN,GSC.C#=C.C#SC.C#=C.C#SCSCC C SC.S#=SC.S#=001001001001选择的串接定律选择与笛卡尔积的交换 12 CN,GCN,GSC.C#=C.C#SC.C#=C.C#SCSCC CSC.S#=SC.S#=001001001001CN,G,SC.C#,C.C#CN,G,SC.C#,C.C#5、选择与投影的交换律F(A1,A2,An(E) A1,A2,An (F(E)（F只涉及A1,A2,An ）A1,A2,An (F(E) A1,A2,An F(A1,An,B1,Bm(E) 13CN,GSC.C#=C.C#SCCSC.S#=001001C#,CNG,C# 投影与笛卡尔积的交换律 14CN,G （ C#，G（ SC.S#=001001（SC） CN，C#（C）优化后的表达式 15例：查询选修了数据库原理的学生姓名和成绩 姓名,成绩 （课程名=数据库原理 学生.学号=学习.学号学习.课程号=课程.课程号（学生 学习 课程）姓名,成绩 （课程名=数据库原理 （学生 学习 课程） 16姓名,成绩课程名=数据库原理学生.学号=学习.学号学习.课程号=课程.课程号课程学生学习 17姓名,成绩学习.课程号=课程.课程号课程学生学习 课程名=数据库原理学生.学号=学习.学号规则 4 、6选择的串接选择和笛卡尔积交换 18姓名,成绩学习.课程号=课程.课程号课程学生学习 课程名=数据库原理学生.学号=学习.学号姓名,成绩,学习.课程号,课程.课程号规则 5选择和投影交换 19姓名,成绩学习.课程号=课程.课程号课程学生学习 课程名=数据库原理学生.学号=学习.学号姓名,课程号，成绩课程号规则 9投影和笛卡尔积交换 20规则 5选择和投影交换姓名,成绩学习.课程号=课程.课程号课程学生学习 课程名=数据库原理学生.学号=学习.学号课程号姓名,学生.学号,学习.学号,课程号，成绩姓名,课程号，成绩 21规则 9投影和笛卡尔积交换姓名,成绩学习.课程号=课程.课程号课程学生学习 课程名=数据库原理学生.学号=学习.学号课程号姓名,学号课程号,学号,成绩姓名,课程号，成绩 22姓名,成绩学习.课程号=课程.课程号课程学生学习 课程名=数据库原理学生.学号=学习.学号课程号姓名,学号姓名,课程号，成绩 23优化后的表达式姓名,成绩 （ 课程号，成绩，姓名（学号，姓名（学生） 学习 ） 课程号（ 课程名=数据库原理（课程） 24关系系统：关系系统的定义关系系统的分类2.5 关系系统关系系统 25关系系统（关系数据库系统）：支持关系模型的数据库管理系统。1 1关系系统的定义关系系统的定义一个系统可定义为关系系统，当且仅当它支持：（1）关系数据结构。（2）支持选择、投影和（自然）连接运算。对这些运算不必要求定义任何物理存取路径。2.5.1 关系系统定义关系系统定义 261） 表式系统：仅支持数据结构，不能算关系系统。2） (最小)关系系统：数据结构+三种关系操作。3）关系完备的系统:数据结构+所有关系代数操作。4）全关系系统：支持关系模型的所有特征。 S: 数据结构 M: 数据操作 I: 完整性约束 SMIMIS SIM SIM2.5.2 关系系统分类关系系统分类 27准则准则0 0：一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。 一个关系型DBMS的关系能力包括属性指定、元组选择、插入和删除、关系合并以及数据完整性和并发控制等，准则0指出，一个RDBMS必须能完全通过这些关系能力来管理数据库，而不需要用户介入。*2.5.3 全关系系统的全关系系统的12条基本准则条基本准则 28 准则准则1 1：信息准则。 准则准则2 2：保证访问准则。 准则准则3 3：空值的系统化处理。 准则准则4 4：基于关系模型的动态的联机数据字典。 准则1-4 保证数据库完整性 *2.5.3 全关系系统的全关系系统的12条基本准则条基本准则 29 准则准则5 5：统一的数据子语言。 准则准则6 6：视图更新准则。 准则准则7 7：高级的插入、修改和删除操作。 准则5-7 保证数据库操作*2.5.3 全关系系统的全关系系统的12条基本准则条基本准则 30 准则准则8 8：数据物理独立性。 准则准则9 9：数据逻辑独立性。 准则准则1010：数据完整性的独立性。 准则准则1111：分布独立性。 准则准则1212：无破坏准则。准则8-11 保证数据库独立性 *2.5.3 全关系系统的全关系系统的12条基本准则条基本准则
