第4章关系系统及其查询优化

第四章关系系统及其查询优化关系模型关系模型的组成部分数据结构（Structure，关系）完整性约束（Integrity）数据操纵（Manipulation）ＳＭＩ4.1关系系统关系系统与关系模型是密切相关而又不同的两个概念关系系统笼统地定义为支持关系模型的DBMS由于关系模型的三个组成部分并不是同等重要，实际产品中的侧重有所不同思考：什么样的系统可以定义为关系系统？支持关系模型的数据库管理系统是关系系统？一个实际的关系系统必须完全支持关系模型？只有完全支持关系模型的系统才能称为关系系统？4.1.1关系系统的定义一个系统可以定义为关系系统，当且仅当它：1、支持关系数据库（关系数据结构）2、支持选择、投影和（自然）连接运算，且对这些运算不必要求定义任何物理存储路径能方便用户的、最有用的运算，有利于提高性能而由系统自动选择，保证物理独立性这是关系系统的最小要求，许多实际系统都不同程度地超过了这些要求4.1.2关系系统的分类表式关系：仅支持关系数据结构，不支持集合操作，如倒排表列最小关系系统：仅支持关系数据结构和三种关系操作，如FoxBASE,FoxPro关系完备的系统支持关系数据结构和所有的关系代数操作，如DB2,Oracle,Sybase,Informix等全关系系统：完全地支持关系模型的所有特征是一个目标，有一套参考准则(12条)ＳＩＭＳＭＩＳＩＭＳＭＩ用阴影表示支持程度0.基础准则：必须能完全通过其关系能力管理数据库1.信息准则：所有信息都能用表中的值显式地表示，包括元数据2.保证访问准则：保证数据库中的每个数据项都能被访问到3.空值的系统化处理：支持空值概念，并能处理空值4.联机数据字典：授权用户能够查询数据库的描述信息5.统一的数据子语言，且具有定义、操纵、授权、事务处理功能6.视图更新准则：理论上可更新的视图应允许由系统更新7.支持以关系为对象的高级插入、删除和更新操作8.数据物理独立性9.数据逻辑独立性10.数据完整性的独立性，完整性条件的定义独立于应用程序11.分布独立性，数据的重新分布独立于应用程序12.无破坏准则：关系系统的一个低级语言不能违背完整性准则全关系系统的12条基本准则4.2关系系统的查询优化4.2.1关系系统及其查询优化说明查询处理是RDBMS的核心，而查询优化技术是查询处理的关键技术用户只需提出“做什么”，不必说明“怎么做”查询优化的目标选择有效的策略，求得给定表达式的值查询优化的优点使得用户在表达查询时不必考虑查询效率问题RDBMS将通过优化器(Optimizer)自动进行查询优化SQL、关系代数等表达式优化器可以做什么？查询优化的一般步骤将查询转换成某种内部表示，如语法树语法树有多种形式，如关系代数语法树。将语法树转换成标准（优化）形式：优化器将应用等价转换规则反复地(通过内部的循环算法)对查询表达式进行尝试性转换，将原始的语法树转换成“优化”的形式。选择低层的存取路径：根据数据字典中的存取路径、数据的存储分布以及聚簇情况等信息来选择具体的执行算法，进一步改善查询效率。生成由一系列内部操作组成的查询执行方案，选择代价最小的。目前商品化RDBMS大都采用基于代价的优化算法多用户环境下总代价＝I/O代价＋CPU代价＋内存代价4.2.2一个实例例子：求选修了2号课程的学生姓名假设：学生-课程数据库中有1000个学生记录，10000个选课记录，其中选修2号课程的选课记录为50个SELECTSnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;SQL：关系代数：))((3))((2))((1'2'.'2'.'2'...SCStudentQSCStudentQSCStudentQCnoSCSnameCnoSCSnameCnoSCSnoSCSnoStudentSname或或对于Q1，假设读取表的策略为：一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，每秒读写20块。代价分析1：Q11、计算笛卡尔积：读取所有数据库记录到内存所需时间：需读取总块数为100+20*100=2100块，总计花费2100/20=105秒从内存写到中间文件读取笛卡儿积所需时间：计算笛卡尔积后生成元组数为103*104=107个。设每块能装10个元组，则将积结果块从内存写到中间文件为107/10/20=5*104秒2、选择操作需要将笛卡尔积结果块从中间文件读入内存，需要的时间同样为107/10/20=5*104秒。3、投影：假设选择操作后得到的结果仅50个元组，最后在此基础上作投影操作，时间可以忽略。因此，忽略内存代价，执行Q1的总时间约为105+2*5*104秒读Student表100块读SC表20遍，每遍100块代价分析2：Q21、计算自然连接需要读取的总块数和花费的时间为仍为2100块和105秒自然连接后生成的元组数为104个，设每块能装10个元组，则计算完自然连接后将这些块从内存写到中间文件时间均为104/10/20=50秒。2、选择操作需要将连接后的结果从中间文件读入内存，需要的时间同样为50秒。3、投影操作：时间可以忽略因此，忽略内存代价，执行Q1的总时间约为105+2*50=205秒代价分析3：Q31、选择运算先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为100/20＝5秒。因为满足条件的元祖仅50个，不必使用中间文件。2、自然连接读取Student表，把读入的Student元组和内存中的SC元组作连接。也只需读一遍Student表共100块花费时间为5秒3、投影运算：时间可以忽略因此，忽略内存代价，执行Q1的总时间约为5+5=10秒可见，同样的查询通过不同的执行过程，其效率相差很大，因此有必要进行查询优化。4.2.3查询优化的一般准则选择运算应尽可能先做在执行连接前对关系适当预处理（如在连接属性上建索引、对两个关系排序等），减少关系的扫描次数。将投影运算和选择运算同时进行将投影同其前或其后的双目运算结合起来，减少扫描关系的次数将某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接运算比笛卡尔积省很多时间找出公共子表达式4.2.4关系代数等价变换规则各种关系查询语言都可以等价地转换为关系代数表达式，因此关系代数表达式的优化是查询优化的基本课题研究关系代数表达式的优化从其等价变换规则开始常用的关系代数等价变换规则1）连接、笛卡尔积的交换2）连接、笛卡尔积的结合3）投影的串接4）选择的串接122112211221EEEEEEEEEEEEFF)()()()()()(3221132211321321321321EEEEEEEEEEEEEEEEEEFFFF的子集是其中BmBAnAEEAnAABmBBAnAA,...,1,...,1),())((,...,2,1,...,2,1,...,2,1)())((2121EEFFFF5）选择与投影的交换6）选择与笛卡尔积的交换7）选择与并的交换8）选择与差的交换))(())((,...,2,1,...,2,1EEFAnAAAnAAF)()())(212121EEEEEEFFF有相同的属性名，则和设)()())(,,21212121EEEEEEEEEFFF则有相同的属性名，设)2)(()(212,11)2()()(2211,212)()(11122121121121EEEEEEFEFEEEEEFEFFFFEEEEEFFFFFFFFF则两者的属性，和涉及中的属性只涉及如果则中的属性，只涉及中的属性，只涉及且如果则中的属性，中涉及的属性都是如果常用的关系代数等价变换规则(续)9）投影与笛卡尔积的交换10）投影与并的交换)()())(2,...,2,11,...,2,121,...,2,121EEEEEEAnAAAnAAAnAA有相同的属性名，则和设)()())(,...,1,...,1,212,...,2,11,...,2,121,...,2,1,,...,2,121EEEEEBmBEAnAEEBmBBAnAABmBBAnAA则的属性，是的属性，是且和设两个关系常用的关系代数等价变换规则(续)4.2.5关系代数表达式的优化算法关系代数语法树(Q1的语法树)SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’;StudentSCproject(Sname)select(SC.Cno=‘2’)join(Student.Sno=SC.Sno)SnameStudent.Sno=SC.SnoStudentSC.Cno=‘2’SCSnameStudentSCSC.Cno=‘2’Student.Sno=SC.Sno原始语法树优化后的语法树(Q3的语法树)关系表达式的优化算法输入：语法树输出：计算程序方法：利用规则4变换对每个选择处理，利用规则4-8尽可能将其移到树叶对每个投影处理，利用规则3.5.9.10尽可能将其移到树叶利用规则3-5将选择和投影的串接合并成单个选择，单个投影或一个选择后跟一个投影，使多个选择或投影能并行将以上得到的语法树的内节点分组生成一个程序，每组节点的计算为一步，各步执行应同步语法树及其优化实例MovieStarStarsInstarnamename)(,birthdateMAXyear关系代数语法树一SELECTyear,MAX(birthdate)FROMMovieStar,StarsInWHEREname=starnameGROUPBYyear;StarsIn(title,year,starname)MovieStar(name,address,gender,birthdate)语法树及其优化实例关系代数语法树二关系代数语法树三MovieStarStarsInstarnamenamebirthdateyear,)(,birthdateMAXyearMovieStarStarsInstarnamenamebirthdateyear,)(,birthdateMAXyearbirthdatename,starnameyear,作业P166，4题