第四章关系系统及其查询优化优秀课件.ppt

《第四章关系系统及其查询优化优秀课件.ppt》由会员分享，可在线阅读，更多相关《第四章关系系统及其查询优化优秀课件.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章关系系统及其查询优化第1页，本讲稿共21页4.1 关系系统n关系系统与关系模型的关系？n支持关系模型的数据库管理系统是关系系统？n一个实际的关系系统必须完全支持关系模型？n只有完全支持关系模型的系统才能称为关系系统？n什么样的系统可以定义为关系系统？第2页，本讲稿共21页4.1.1 关系系统的定义n一个系统可以定义为关系系统，当且仅当它：(1)支持关系数据库(关系数据结构)：表 (2)支持选择、投影和(自然)连接运算，且对这些运算不必要求任何物理存储路径方便用户使用的重要运算而由关系系统自动选择进一步理解：方便用户，提高性能，物理独立性，最有用进一步理解：方便用户，提高性能，物理独立性，

2、最有用第3页，本讲稿共21页4.1.2 关系系统的分类n关系模型的组成部分n数据结构(关系)S，完整性约束I，数据操纵M用阴影表示支持程度第4页，本讲稿共21页4.1.2 关系系统的分类n表式关系：n仅支持关系数据结构，如倒排表列n最小关系系统：n仅支持关系数据结构和三种关系操作，如FoxBASE,FoxPron关系完备的系统n支持关系数据结构和所有的关系代数操作，如Oracle,Sybasen全关系系统：n完全地支持关系模型的所有特征n是一个目标，有一套参考准则(12条)自学全关系系统的12条基本准则第5页，本讲稿共21页4.2 关系系统的查询优化4.2.1关系系统及其查询优化n说明n查询处

3、理是RDBMS的核心，而查询优化技术是查询处理的关键技术n查询优化的目标n选择有效的策略，求得给定表达式的值n查询优化的优点n使得用户在表达查询时不必考虑查询效率问题nRDBMS将通过优化器(Optimizer)自动进行查询优化SQL、关系代数等表达式优化器可以做什么？第6页，本讲稿共21页查询优化的一般步骤n将查询转换成某种内部表示，如语法树n语法树有多种形式，如关系代数语法树。n将语法树转换成标准(优化)形式：n优化器将应用等价转换规则反复地(通过内部的循环算法)对查询表达式进行尝试性转换，将原始的语法树转换成“优化”的形式。n选择低层的存取路径：n根据数据字典中的存取路径、数据的存储分布

4、以及聚簇情况等信息来选择具体的执行算法，进一步改善查询效率。n生成由一系列内部操作组成的查询执行方案，选择代价最小的。目前商品化RDBMS大都采用基于代价的优化算法多用户环境下总代价多用户环境下总代价I/O代价代价CPU代价内存代价代价内存代价第7页，本讲稿共21页4.2.2 一个实例例子：求选修了2号课程的学生姓名假设：学生-课程数据库中有1000个学生记录，10000个选课记录，其中选修2号课程的选课记录为50个SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.Sno AND SC.Cno=2;SQL：关系代数：第8页，本讲稿共

5、21页对于Q1，假设读取表的策略为：一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，每秒读写20块。代价分析1：Q11、计算笛卡尔积：n读取所有数据库记录到内存所需时间：n需读取总块数为1000/10+1000/(10*5)*10000/100=100+20*100=2100块，总计花费2100/20=105秒n从内存写到中间文件读取笛卡儿积所需时间：n计算笛卡尔积后生成元组数为103*104=107个。设每块能装10个元组，则将积结果块从内存写到中间文件为107/10/20=5*104秒2、选择操作n需要将笛卡尔积结果块从中间文件读入内

6、存，需要的时间同样为107/10/20=5*104秒。3、投影：假设选择操作后得到的结果仅50个元组，最后在此基础上作投影操作，时间可以忽略。因此，忽略内存代价，执行Q1的总时间约为105+2*5*104秒读Student表100块读SC表20遍，每遍100块第9页，本讲稿共21页代价分析2：Q21、计算自然连接n需要读取的总块数和花费的时间为仍为 2100块和105秒n自然连接后生成的元组数为104个，设每块能装10个元组，则计算完自然连接后将这些块从内存写到中间文件时间均为104/10/20=50秒。2、选择操作n需要将连接后的结果从中间文件读入内存，需要的时间同样为50秒。3、投影操作：

7、时间可以忽略因此，忽略内存代价，执行Q1的总时间约为105+2*50=205秒第10页，本讲稿共21页代价分析3：Q31、选择运算n先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为100/205秒。因为满足条件的元祖仅50个，不必使用中间文件。2、自然连接n读取Student表，把读入的Student元组和内存中的SC元组作连接。也只需读一遍Student表共100块花费时间为5秒3、投影运算：时间可以忽略因此，忽略内存代价，执行Q1的总时间约为5+5=10秒可见，同样的查询通过不同的执行过程，其效率相差很大，因此有必要进行查询优化。第11页，本讲稿共21页4.2.3 查询优化的

8、一般准则n选择运算应尽可能先做n在执行连接前对关系适当地预处理（建立索引，排序）n将投影运算和选择运算同时进行n将投影同其前或其后的双目运算结合起来，减少扫描关系的次数n将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接运算比笛卡尔积省很多时间n找出公共子表达式第12页，本讲稿共21页4.2.4 关系代数等价变换规则n各种关系查询语言都可以等价地转换为关系代数表达式，因此关系代数表达式的优化是查询优化的基本课题n研究关系代数表达式的优化最后从其等价变换规则开始第13页，本讲稿共21页常用的关系代数等价变换规则n1）连接、笛卡尔积的交换n2）连接、笛卡尔积的结合n3）投影的串接n

9、4）选择的串接第14页，本讲稿共21页n5）选择与投影的交换n6）选择与笛卡尔积的交换n7）选择与并的交换n8）选择与差的交换常用的关系代数等价变换规则(续)第15页，本讲稿共21页n9）投影与笛卡尔积的交换n10）投影与并的交换常用的关系代数等价变换规则(续)第16页，本讲稿共21页4.2.5 关系代数表达式的优化算法关系代数语法树(Q1的语法树)SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.Sno AND SC.Cno=2;Student SCproject(Sname)select(SC.Cno=2)join(Studen

10、t.Sno=SC.Sno)Sname Student.Sno=SC.Sno Student SC.Cno=2SCStudent SCSname SC.Cno=2 Student.Sno=SC.Sno 原始语法树优化后的语法树(Q3的语法树)第17页，本讲稿共21页关系表达式的优化算法n输入：语法树n输出：计算程序n方法：n利用规则4变换n对每个选择处理，利用规则4-8尽可能将其移到树的叶端n对每个投影处理，利用规则3.5.9.10尽可能将其移到树的叶端n利用规则3-5将选择和投影的串接合并成单个选择，单个投影或一个选择后跟一个投影，使多个选择或投影能并行n将以上得到的语法树的内节点分组n生成一个程序，每一节点为一步第18页，本讲稿共21页语法树及其优化实例关系代数语法树一SELECT year,MAX(birthdate)FROM MovieStar,StarsInWHERE name=starnameGROUP BY year;StarsIn(title,year,starname)MovieStar(name,address,gender,birthdate)第19页，本讲稿共21页语法树及其优化实例关系代数语法树二关系代数语法树三第20页，本讲稿共21页作业nP166，4题第21页，本讲稿共21页