《第4章关系系统及其查询优化精选文档.ppt》由会员分享，可在线阅读，更多相关《第4章关系系统及其查询优化精选文档.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4章关系系统及其查询优化本讲稿第一页，共二十二页关系模型关系模型n关系模型的组成部分关系模型的组成部分n数据结构（数据结构（Structure，关系），关系）n完整性约束（完整性约束（Integrity）n数据操纵（数据操纵（Manipulation）本讲稿第二页，共二十二页4.1 关系系统关系系统n关系系统与关系模型是密切相关而又不同的两个概念关系系统与关系模型是密切相关而又不同的两个概念n关系系统笼统地定义为支持关系模型的关系系统笼统地定义为支持关系模型的DBMSn由于关系模型的三个组成部分并不是同等重要，实际产品中由于关系模型的三个组成部分并不是同等重要，实际产品中的侧重有所不同的侧重
2、有所不同n思考：什么样的系统可以定义为关系系统？思考：什么样的系统可以定义为关系系统？n支持关系模型的数据库管理系统是关系系统？支持关系模型的数据库管理系统是关系系统？n一个实际的关系系统必须完全支持关系模型？一个实际的关系系统必须完全支持关系模型？n只有完全支持关系模型的系统才能称为关系系统？只有完全支持关系模型的系统才能称为关系系统？本讲稿第三页，共二十二页4.1.1 关系系统的定义关系系统的定义n一个系统可以定义为关系系统，当且仅当它：一个系统可以定义为关系系统，当且仅当它：1、支持关系数据库（关系数据结构）、支持关系数据库（关系数据结构）2、支持、支持选择、投影和（自然）连接运算选择、
3、投影和（自然）连接运算，且对这些运算，且对这些运算不必要求定义任何物理存储路径不必要求定义任何物理存储路径能方便用户的、能方便用户的、最有用的运算，有利最有用的运算，有利于提高性能于提高性能而由系统自动选择，而由系统自动选择，保证物理独立性保证物理独立性这是关系系统的最小要求，许多实际系统都不同程度地超过了这些要求这是关系系统的最小要求，许多实际系统都不同程度地超过了这些要求本讲稿第四页，共二十二页4.1.2 关系系统的分类关系系统的分类n表式关系：表式关系：n仅支持关系数据结构，不支持集合操作，如仅支持关系数据结构，不支持集合操作，如倒排表列倒排表列n最小关系系统：最小关系系统：n仅支持关系
4、数据结构和三种关系操作，如仅支持关系数据结构和三种关系操作，如FoxBASE,FoxPron关系完备的系统关系完备的系统n支持关系数据结构和所有的关系代数操作，支持关系数据结构和所有的关系代数操作，如如DB2,Oracle,Sybase,Informix等等n全关系系统：全关系系统：n完全地支持关系模型的所有特征完全地支持关系模型的所有特征n是一个目标，有一套参考准则是一个目标，有一套参考准则(12条条)用阴影表示支持程度用阴影表示支持程度本讲稿第五页，共二十二页0.基础准则：必须能完全通过其关系能力管理数据库基础准则：必须能完全通过其关系能力管理数据库1.信息准则：所有信息都能用表中的值显式
5、地表示，包括元数据信息准则：所有信息都能用表中的值显式地表示，包括元数据2.保证访问准则：保证数据库中的每个数据项都能被访问到保证访问准则：保证数据库中的每个数据项都能被访问到3.空值的系统化处理：支持空值概念，并能处理空值空值的系统化处理：支持空值概念，并能处理空值4.联机数据字典：授权用户能够查询数据库的描述信息联机数据字典：授权用户能够查询数据库的描述信息5.统一的数据子语言，且具有定义、操纵、授权、事务处理功能统一的数据子语言，且具有定义、操纵、授权、事务处理功能6.视图更新准则：理论上可更新的视图应允许由系统更新视图更新准则：理论上可更新的视图应允许由系统更新7.支持以关系为对象的高
6、级插入、删除和更新操作支持以关系为对象的高级插入、删除和更新操作8.数据物理独立性数据物理独立性9.数据逻辑独立性数据逻辑独立性10.数据完整性的独立性，完整性条件的定义独立于应用程序数据完整性的独立性，完整性条件的定义独立于应用程序11.分布独立性，数据的重新分布独立于应用程序分布独立性，数据的重新分布独立于应用程序12.无破坏准则：关系系统的一个低级语言不能违背完整性准则无破坏准则：关系系统的一个低级语言不能违背完整性准则全关系系统的全关系系统的12条基本准则条基本准则本讲稿第六页，共二十二页4.2 关系系统的查询优化关系系统的查询优化4.2.1关系系统及其查询优化关系系统及其查询优化n说
7、明说明n查询处理是查询处理是RDBMS的核心，而查询优化技术是查询处理的的核心，而查询优化技术是查询处理的关键技术关键技术n用户只需提出用户只需提出“做什么做什么”，不必说明，不必说明“怎么做怎么做”n查询优化的目标查询优化的目标n选择有效的策略，求得给定选择有效的策略，求得给定表达式表达式的值的值n查询优化的优点查询优化的优点n使得用户在表达查询时不必考虑查询效率问题使得用户在表达查询时不必考虑查询效率问题nRDBMS将通过将通过优化器优化器(Optimizer)自动进行查询优化自动进行查询优化SQL、关系代数、关系代数等表达式等表达式优化器可以做什么？优化器可以做什么？本讲稿第七页，共二十
8、二页查询优化的一般步骤查询优化的一般步骤n将查询转换成某种内部表示，如语法树将查询转换成某种内部表示，如语法树n语法树有多种形式，如关系代数语法树。语法树有多种形式，如关系代数语法树。n将语法树转换成标准（优化）形式：将语法树转换成标准（优化）形式：n优化器将应用优化器将应用等价转换规则等价转换规则反复地反复地(通过内部的循环算法通过内部的循环算法)对查询表达对查询表达式进行式进行尝试性转换尝试性转换，将原始的语法树转换成，将原始的语法树转换成“优化优化”的形式。的形式。n选择低层的存取路径：选择低层的存取路径：n根据数据字典中的存取路径、数据的存储分布以及聚簇情况等信息来选根据数据字典中的存
9、取路径、数据的存储分布以及聚簇情况等信息来选择具体的执行算法，进一步改善查询效率。择具体的执行算法，进一步改善查询效率。n生成由一系列内部操作组成的生成由一系列内部操作组成的查询执行方案查询执行方案，选择代价，选择代价最小的。最小的。目前商品化目前商品化RDBMS大都采用基于代价的优化算法大都采用基于代价的优化算法多用户环境下多用户环境下总代价总代价I/O代价代价CPU代价内存代价代价内存代价本讲稿第八页，共二十二页4.2.2 一个实例一个实例例子：求选修了例子：求选修了2号课程的学生姓名号课程的学生姓名假设：学生假设：学生-课程数据库中有课程数据库中有1000个学生记录，个学生记录，1000
10、0个选课记录，其个选课记录，其中选修中选修2号课程的选课记录为号课程的选课记录为50个个SELECT SnameFROM Student,SCWHERE Student.Sno=SC.Sno AND SC.Cno=2;SQL：关系代数：关系代数：本讲稿第九页，共二十二页对于对于Q1，假设读取表的策略为：一个，假设读取表的策略为：一个块块能装能装10个个Student元组或元组或100个个SC元组，元组，在内存中存放在内存中存放5块块Student元组和元组和1块块SC元组，每秒读写元组，每秒读写20块。块。代价分析代价分析1：Q11、计算笛卡尔积：、计算笛卡尔积：n读取所有数据库记录到内存所需
11、时间：读取所有数据库记录到内存所需时间：n需读取总块数为需读取总块数为100+20*100=2100块，块，总计花费总计花费2100/20=105秒秒n从内存写到中间文件读取笛卡儿积所需时间：从内存写到中间文件读取笛卡儿积所需时间：n计算笛卡尔积后生成元组数为计算笛卡尔积后生成元组数为103*104=107个。设每块能装个。设每块能装10个元组，则将个元组，则将积结果块从内存写到中间文件为积结果块从内存写到中间文件为107/10/20=5*104秒秒2、选择操作、选择操作n需要将笛卡尔积结果块从中间文件读入内存，需要的时间同需要将笛卡尔积结果块从中间文件读入内存，需要的时间同样为样为107/1
12、0/20=5*104秒。秒。3、投影：、投影：假设选择操作后得到的结果仅假设选择操作后得到的结果仅50个元组，最后在此基础个元组，最后在此基础上作投影操作，时间可以忽略。上作投影操作，时间可以忽略。因此，忽略内存代价，执行因此，忽略内存代价，执行Q1的总时间约为的总时间约为105+2*5*104秒秒读读Student表表100块块读读SC表表20遍，每遍遍，每遍100块块本讲稿第十页，共二十二页代价分析代价分析2：Q21、计算自然连接、计算自然连接n需要读取的总块数和花费的时间为仍为需要读取的总块数和花费的时间为仍为 2100块和块和105秒秒n自然连接后生成的元组数为自然连接后生成的元组数为
13、104个，设每块能装个，设每块能装10个元组，则计个元组，则计算完自然连接后将这些块从内存写到中间文件时间均为算完自然连接后将这些块从内存写到中间文件时间均为104/10/20=50秒秒。2、选择操作、选择操作n需要将连接后的结果从中间文件读入内存，需要的时间同样为需要将连接后的结果从中间文件读入内存，需要的时间同样为50秒秒。3、投影操作、投影操作：时间可以忽略：时间可以忽略因此，忽略内存代价，执行因此，忽略内存代价，执行Q1的总时间约为的总时间约为105+2*50=205秒秒本讲稿第十一页，共二十二页代价分析代价分析3：Q31、选择运算、选择运算n先对先对SC表作选择运算，只需读一遍表作选
14、择运算，只需读一遍SC表，存取表，存取100块花费时间为块花费时间为100/205秒秒。因为满足条件的元祖仅。因为满足条件的元祖仅50个，不必使用中间文个，不必使用中间文件。件。2、自然连接、自然连接n读取读取Student表，把读入的表，把读入的Student元组和内存中的元组和内存中的SC元组作连元组作连接。也只需读一遍接。也只需读一遍Student表共表共100块花费时间为块花费时间为5秒秒3、投影运算、投影运算：时间可以忽略：时间可以忽略因此，忽略内存代价，执行因此，忽略内存代价，执行Q1的总时间约为的总时间约为5+5=10秒秒可见，同样的查询通过不同的执行过程，其效率相差很大，可见，
15、同样的查询通过不同的执行过程，其效率相差很大，因此有必要进行查询优化。因此有必要进行查询优化。本讲稿第十二页，共二十二页4.2.3 查询优化的一般准则查询优化的一般准则n选择运算应尽可能先做选择运算应尽可能先做n在执行连接前对关系适当预处理（如在连接属性上建索引、对在执行连接前对关系适当预处理（如在连接属性上建索引、对两个关系排序等），减少关系的扫描次数。两个关系排序等），减少关系的扫描次数。n将投影运算和选择运算同时进行将投影运算和选择运算同时进行n将投影同其前或其后的双目运算结合起来，减少扫描关系的将投影同其前或其后的双目运算结合起来，减少扫描关系的次数次数n将某些选择同在它前面要执行的笛
16、卡尔积结合起来成为一将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接运算比笛卡尔积省很多时间个连接运算，连接运算比笛卡尔积省很多时间n找出公共子表达式找出公共子表达式本讲稿第十三页，共二十二页4.2.4 关系代数等价变换规则关系代数等价变换规则n各种关系查询语言都可以等价地转换为关系代数表达式，各种关系查询语言都可以等价地转换为关系代数表达式，因此因此关系代数表达式的优化关系代数表达式的优化是查询优化的基本课题是查询优化的基本课题n研究关系代数表达式的优化从其研究关系代数表达式的优化从其等价变换规则等价变换规则开始开始本讲稿第十四页，共二十二页常用的关系代数等价变换规则常用的
17、关系代数等价变换规则n1）连接、笛卡尔积的交换）连接、笛卡尔积的交换n2）连接、笛卡尔积的结合）连接、笛卡尔积的结合n3）投影的串接）投影的串接n4）选择的串接）选择的串接本讲稿第十五页，共二十二页n5）选择与投影的交换）选择与投影的交换n6）选择与笛卡尔积的交换）选择与笛卡尔积的交换n7）选择与并的交换）选择与并的交换n8）选择与差的交换）选择与差的交换常用的关系代数等价变换规则常用的关系代数等价变换规则(续续)本讲稿第十六页，共二十二页n9）投影与笛卡尔积的交换）投影与笛卡尔积的交换n10）投影与并的交换）投影与并的交换常用的关系代数等价变换规则常用的关系代数等价变换规则(续续)本讲稿第十
18、七页，共二十二页4.2.5 关系代数表达式的优关系代数表达式的优化算法化算法关系代数语法树关系代数语法树(Q1的语法树的语法树)SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.Sno AND SC.Cno=2;Student SCproject(Sname)project(Sname)select(select(SC.Cno=2)join(join(Student.Sno=SC.Sno)SnameSname Student.Sno=SC.Sno Student SC.Cno=2SC SnameSnameStudent SC SC.
19、Cno=2 Student.Sno=SC.Sno 原始语法树原始语法树优化后的语法树优化后的语法树(Q3的语法树的语法树)本讲稿第十八页，共二十二页关系表达式的优化算法关系表达式的优化算法n输入：语法树输入：语法树n输出：计算程序输出：计算程序n方法：方法：n利用规则利用规则4变换变换n对每个对每个选择处理选择处理，利用规则，利用规则4-8尽可能尽可能将其将其移到树叶移到树叶n对每个对每个投影处理投影处理，利用规则，利用规则3.5.9.10尽可能尽可能将其将其移到树叶移到树叶n利用规则利用规则3-5将选择和投影的串接合并成单个选择，单个投影或一将选择和投影的串接合并成单个选择，单个投影或一个选
20、择后跟一个投影，使多个选择或投影能并行个选择后跟一个投影，使多个选择或投影能并行n将以上得到的语法树的内节点分组将以上得到的语法树的内节点分组n生成一个程序，每组节点的计算为一步，各步执行应同步生成一个程序，每组节点的计算为一步，各步执行应同步本讲稿第十九页，共二十二页语法树及其优化实例语法树及其优化实例关系代数语法树一关系代数语法树一SELECT year,MAX(birthdate)FROM MovieStar,StarsInWHERE name=starnameGROUP BY year;StarsIn(title,year,starname)MovieStar(name,address,gender,birthdate)本讲稿第二十页，共二十二页语法树及其优化实例语法树及其优化实例关系代数语法树二关系代数语法树二关系代数语法树三关系代数语法树三本讲稿第二十一页，共二十二页作业作业nP166，4题题本讲稿第二十二页，共二十二页