关系系统及其查询优化精选PPT.ppt
关系系统及其查询优化第1页，此课件共15页哦4.1 关系系统1.定义定义 （1）支持关系数据库（关系数据结构）支持关系数据库（关系数据结构）（2）支持选择、投影和（自然）连接运算，且不要求定义任何物理存取）支持选择、投影和（自然）连接运算，且不要求定义任何物理存取路径。路径。2.分类分类 根据关系模型的三个组成：结构根据关系模型的三个组成：结构S(Structure)、完整性、完整性I(Integrity)、数、数据操纵据操纵M(Manipulation)的实现进行分类。分的实现进行分类。分4类。类。第四章第四章 关系系统及其查询优化关系系统及其查询优化第2页，此课件共15页哦4.1 关系系统3.全关系系统的基本准则（全关系系统的基本准则（12条）条）准则准则0 RDBMS能完全通过它的关系能力管理数据库；能完全通过它的关系能力管理数据库；准则准则1 信息准则；信息准则；用基本表的值显式表示数据。用基本表的值显式表示数据。准则准则2 保证访问准则；保证访问准则；不用选择路径。不用选择路径。准则准则3 空值的系统化处理准则；空值的系统化处理准则；支持空值。支持空值。准则准则4 动态联机数据字典准则；动态联机数据字典准则；准则准则5 统一的数据子语言准则；统一的数据子语言准则；准则准则6 视图更新准则；视图更新准则；允许理论上可更新的视图更新。允许理论上可更新的视图更新。准则准则7 高级的插入、修改和删除操作准则；高级的插入、修改和删除操作准则；允许选择存储路径。允许选择存储路径。准则准则8 数据物理独立性准则；数据物理独立性准则；存储和存储方法改变，应用不变。存储和存储方法改变，应用不变。准则准则9 数据逻辑独立性准则；数据逻辑独立性准则；关系改变，应用不变。关系改变，应用不变。准则准则10 数据完整性的独立性准则；数据完整性的独立性准则；定义在数据字典中。定义在数据字典中。准则准则11 分布独立性准则；分布独立性准则；在引入和重新分布时，应用逻辑不变。在引入和重新分布时，应用逻辑不变。第四章第四章 关系系统及其查询优化关系系统及其查询优化第3页，此课件共15页哦4.2 查询优化1.实例实例 用用SQL语言查询选修了语言查询选修了2号课程的学生姓名：号课程的学生姓名：SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2 假定：数据库有假定：数据库有1000个学生记录、个学生记录、10000个选课记录、选修个选课记录、选修2号课程的选课记录有号课程的选课记录有50个。个。关系代数表达式表示为：关系代数表达式表示为：第四章第四章 关系系统及其查询优化关系系统及其查询优化第4页，此课件共15页哦4.2 查询优化2.分析分析 第四章第四章 关系系统及其查询优化关系系统及其查询优化数据项的数目：数据项的数目：Student1000(5)SC10000(3)=80,000,000选择后选择后(最多最多)：50(5)1(3)=400结果：结果：50 80,000,450数据项的数目：数据项的数目：Student1000(5)SC30(3)=240,000选择后选择后(最多最多)：50(5)1(3)=400结果：结果：50 240,450 3/1000数据项的数目：数据项的数目：Student50(5)SC50(3)=20,000 2/10000 选择后选择后(最多最多)：50(5)1(3)=400结果：结果：50 20,450 8/100第5页，此课件共15页哦4.2 查询优化3.查询的代价查询的代价总代价总代价I/O代价代价+CPU代价代价+内存代价内存代价4.查询优化的必要性查询优化的必要性 关系数据库系统能够取得巨大的成功，关系数据库系统能够取得巨大的成功，SQL语言语言能够得到广泛的应用，关键得益于查询优化技术能够得到广泛的应用，关键得益于查询优化技术的发展。的发展。5.优化的步骤优化的步骤 （）将查询转换为内部表示语法树；（）将查询转换为内部表示语法树；（）根据等价变换规则把语法树优化；（）根据等价变换规则把语法树优化；（）选择底层的操作算法；（）选择底层的操作算法；（）生成查询的执行方案。（）生成查询的执行方案。第四章第四章 关系系统及其查询优化关系系统及其查询优化第6页，此课件共15页哦4.2 查询优化6.查询优化的一般准则查询优化的一般准则 （）选择运算尽可能先做；（）选择运算尽可能先做；（）执行连接前进行排序或索引；（）执行连接前进行排序或索引；（）投影运算和选择运算同时进行；（）投影运算和选择运算同时进行；（）投影与前后的双目运算结合；（）投影与前后的双目运算结合；（）选择与笛卡尔积结合为连接；（）选择与笛卡尔积结合为连接；（）提取公共子表达式。（）提取公共子表达式。第四章第四章 关系系统及其查询优化关系系统及其查询优化第7页，此课件共15页哦4.2 查询优化7.关系代数的等价变换规则关系代数的等价变换规则 （）连接、笛卡尔积的交换律（）连接、笛卡尔积的交换律 E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 F F（）连接、笛卡尔积的结合律（）连接、笛卡尔积的结合律(E1 E2)E3 E1(E2 E3)(E1 E2)E3 E1(E2 E3)(E1 E2)E3 E1(E2 E3)F1 F2 F1 F2第四章第四章 关系系统及其查询优化关系系统及其查询优化第8页，此课件共15页哦4.2 查询优化7.关系代数的等价变换规则关系代数的等价变换规则 （）投影的串接定律（）投影的串接定律A1,A2,An(B1,B2,Bm(E)A1,A2,An(E)（）选择的串接定律（）选择的串接定律F1(F2(E)F1F2(E)（）选择与投影的交换律（）选择与投影的交换律F(A1,A2,An(E)A1,A2,An(F(E)（）选择与并的交换律（）选择与并的交换律F(E1E2)F(E1)F(E2)第四章第四章 关系系统及其查询优化关系系统及其查询优化第9页，此课件共15页哦4.2 查询优化7.关系代数的等价变换规则关系代数的等价变换规则 （）选择与差的交换律（）选择与差的交换律F(E1E2)F(E1)F(E2)（）选择与笛卡尔积的交换律（）选择与笛卡尔积的交换律F(E1E2)F(E1)E2 F(E1E2)E1F(E2)F(E1E2)F1(E1)F2(E2)F(E1E2)F2(F1(E1)E2)第四章第四章 关系系统及其查询优化关系系统及其查询优化第10页，此课件共15页哦4.2 查询优化7.关系代数的等价变换规则关系代数的等价变换规则 （）投影与笛卡尔积的交换律（）投影与笛卡尔积的交换律A1,A2,An,B1,B2,Bm(E1E2)A1,A2,An(E1)B1,B2,Bm(E2)（）投影与并的交换律（）投影与并的交换律A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)第四章第四章 关系系统及其查询优化关系系统及其查询优化第11页，此课件共15页哦4.2 查询优化8.关系代数表达式的优化算法关系代数表达式的优化算法 输入：表示关系代数表达式的语法树输入：表示关系代数表达式的语法树输出：计算该表达式的程序输出：计算该表达式的程序（）分解选择运算规则（）分解选择运算规则F1(F2(E)F1F2(E)（）移到叶端（）移到叶端 F(E1E2)F(E1)E2（）分解投影并移到叶端（）分解投影并移到叶端 A1,A2,An,B1,B2,Bm(E1E2)A1,A2,An(E1)B1,B2,Bm(E2)（）合并投影和选择（）合并投影和选择 F(A1,A2,An(E)A1,A2,An(F(E)（）合并选择和笛卡尔积为连接运算（）合并选择和笛卡尔积为连接运算 F(E1E2)E1 E2 F（）生成优化后的关系代数表达式。（）生成优化后的关系代数表达式。第四章第四章 关系系统及其查询优化关系系统及其查询优化第12页，此课件共15页哦4.2 查询优化9.优化过程优化过程 第四章第四章 关系系统及其查询优化关系系统及其查询优化语法树语法树优化过程优化过程()第13页，此课件共15页哦4.2 查询优化9.优化过程优化过程 第四章第四章 关系系统及其查询优化关系系统及其查询优化优化过程优化过程(2)优化过程优化过程(3)第14页，此课件共15页哦习习 题题1;2;3;41;2;3;4。第四章第四章 关系系统及其查询优化关系系统及其查询优化第15页，此课件共15页哦
