《数据库系统原理》25-26节教案(第四章 关系系统及其查.doc

数据库系统原理-56-25、26节 （共11页、第11页）山 东 理 工 大 学 教 案数据库系统原理教案第 13 次课教学课型：理论课 实验课 习题课 实践课 技能课 其它主要教学内容（注明：* 重点 # 难点 ）：第四章 关系系统及其查询优化一、 关系系统的定义和分类二、 关系系统的查询优化的目的三、关系代数等价变换规则（*）四、优化的一般步骤五、优化的标准语法树的画法（实际优化的转化步骤）：（*、#）u 根据题目要求写出SQL查询语句u 根据SQL语句写出关系代数表达式u 画出关系代数表达式的语法树u 采用优化准则和关系代数等价变化规则写出优化关系代数表达式u 根据优化关系代数表达式画出标准（优化）形式语法树教学目的要求：1、理解关系系统的查询优化的目的2、掌握关系代数等价变换规则3、掌握优化的标准语法树的画法教学方法和教学手段：教学方法主要是讲授、示教。教学手段：板书和多媒体相结合。讨论、思考题、作业：作业：习题166167页 4、 5、 6参考资料：王珊，陈红：数据库系统原理教程 清华大学出版社，2000刘方鑫：数据库原理与技术 电子工业出版社，2002丁宝康：数据库原理 经济科学出版社，2000 第四章 关系系统及其查询优化学习目标u 掌握关系系统的定义和分类u 理解关系系统中查询优化的必要性及查询优化的策略、方法和步骤u 关系代数的等价变换规则 u 查询优化的一般步骤u 根据关系代数表达式能画出原始语法树u 能用优化算法对原始的语法树进行优化处理，画出优化后的标准（优化）形式本章难重点u 查询优化的必要性u 计算每种关系代数的代价u 把关系代数查询转换成原始语法树u 在原始语法树的基础上进行优化算法，生成优化后的语法树u 考试类别：P166页：题4本章主要内容：u 关系系统的定义和分类u 关系系统中查询优化的概念u 查询优化的必要性u 查询优化的基本原理和技术41 关系系统n 能够在一定程度上支持关系模型的数据库管理系统是关系系统。n 由于关系模型中并非每一部分都是同等重要的，并不苛求一个实际的关系系统必须完全支持关系模型。 n 关系数据结构：域及域上定义的关系n 关系操作：并、交、差、广义笛卡尔积、选择、投影、连接、除等 n 关系完整性：实体完整性、参照完整性、用户自己定义的完整性411 关系系统的定义一个数据库管理系统可定义为关系系统，当且仅当它至少支持：n 关系数据库（即关系数据结构），从用户观点看，数据库系统中只有表这一种结构。n 支持选择、投影和（自然）连接运算，对这些运算不要求用户定义任何物理存取路径注意：这是对关系系统的最低要求定义说明如下：A、如果一个系统仅支持关系数据库而没有选择、投影和连接运算功能，不能称为关系系统。原因：因为不支持这三种关系运算的系统，使用仍不方便，不能提高的生产率，而提高生产率正是关系系统的主要目标之一。B、一个系统虽然支持这三种运算，但要求定义物理存取路径，例如要求用户先建立索引才能按索引字段检索记录，也不能称为关系系统。原因：因为依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。实际上并不要求关系系统的选择、投影、连接运算和关系代数的相应运算完全一样，而只要求有等价的这三种运算功能。C、要求关系系统支持这三种最主要的运算而不是关系代数的全部运算功能，是因为选择、投影、连接是关系系统中最有用的运算功能，能解决绝大部分的实际问题。总之，要求关系系统即要支持关系数据结构，又支持选择、投影和连接是，这是为了使用方便和数据易用。412 关系系统的分类分类依据：支持关系模型的程度。1、表式系统：仅支持关系(即表)数据结构，不支持关系集合级的操作。例如：倒排表列系统、EXCEL等。2、(最小)关系系统：仅支持关系数据结构，支持选择、投影、连接关系操作。例如：FoxBASE，FoxPro等。3、关系完备的系统：支持关系数据结构、支持所有的关系代数操作，功能与关系代数等价。例如：PB、VFP、VB等。4、全关系系统：支持关系模型的所有特征。特别是数据结构中域的概念、实体完整性和参照完整性。目前，大型关系系统（例如oracle）已不同程度上接近或达到了这个目标。图中的圆表示关系数据模型。每个圆分为三部分，分别表示关系模型的三个组成部分：结构S(Structure)、数据操纵M(Manipulation)、完整性I(Integrity)，图中阴影部分表示各类系统支持模型的程度。小结如下：数据结构数据操作完整性表式系统表(最小)关系系统表选择、投影、连接关系完备的系统表全关系系统表42 关系数据库系统的查询优化 查询优化的必要性：查询优化是影响RDBMS性能的关键因素。查询优化的可能性：关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。421 关系系统的查询优化l 关系系统的查询优化是RDBMS实现的关键技术，又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“做什么”，不必指出“怎么做”。l 由DBMS进行查询优化的好处n 用户不必考虑如何最好地表达查询以获得较好的效率。n 系统可以比用户程序的优化做得更好。(1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划。(2)如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往不太可能。(3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。l 关系数据库查询优化的总目标：选择有效的策略，求得给定关系表达式的值。l 实际系统对查询优化的四个步骤：将查询转换成某种内部表示，通常是语法树。根据一定的等价变换规则把语法树转换成标准(优化)形式。选择低层的操作算法。对于语法树中的每一个操作：n 计算各种执行算法的执行代价n 选择代价小的执行算法生成查询计划。l 查询计划也称查询执行方案，是由一系列内部操作组成的。l 这些内部操作按一定的次序构成查询的一个执行方案。l 通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。常用系统模型的代价计算如下：A、集中式数据库单用户系统 总代价 = I/O代价 + CPU代价多用户系统 总代价 = I/O代价 + CPU代价 + 内存代价B、分布式数据库总代价=I/O代价+CPU代价+ 内存代价+通信代价 4.2.2 查询优化的必要性 例1：对第3章的表求选修了2号课程的学生姓名。用SQL语言表达如下：SELECT ST.Sname FROM ST，SC WHERE ST.Sno=SC.Sno AND SC.Cno=2假设1：ST:1000条，SC:10000条，选修2号课程：50条假设2：一个内存块装元组10个St或100个SC,内存中一次可以存放5块St元组和1块SC元组以及若干块连接结果元组假设3：读写速度20块/秒假设4：连接方法是基于数据块的嵌套循环法n 在内存中尽可能多的装入（如St）的若干块元组，留出一块存放另一个表（SC）的元组，然后把SC中的每个元组和St中的每个元组连接，连接后的元组装满一块后写到中间文件上。n 再从SC中读入一块和内存中的St元组连接，直到SC表处理完，这时再一次读入若干块St元组，读入一块SC元组 ，重复上述过程，直到把St表处理完。系统可以用多种等价的关系代数表达式来完成这一查询查询方式1：Q1=sname(st.sno=o=2(StSc)查询方式2：Q2=sname(o=2(StSc)查询方式3：Q3=sname(So=2(Sc)下面将看到由于查询执行的策略不同，查询时间相差很大。一、查询方式1：Q1=sname(st.sno=o=2(StSc)1计算广义笛卡尔积（StSc）读取总块数= 读St表块数 + 读SC表遍数*每遍块数=1000/10+(1000/(105)(10000/100)=100+20100=2100读数据时间：2100/20=105秒连接后的元组数为1000*10000=107。设每块能装10个元组，共用107/10=106块，写出这些块用106/20=5*104S（秒）本次连接操作所用总时间是：105S+5*104S2作选择操作（stsno=o=2）依次读入连接后的元组，这一步读取中间文件花费的时间(同写中间文件一样)也是5*104S。选择满足条件的元组假设仅50个，均可放在内存，假定选择操作的内存处理时间忽略。3作投影（sname）把第2步的结果在Sname上作投影输出，得到最终结果。u 本次查询总时间是：105S+2*5*104S= 1055000050000秒= 27.8小时u 其中内存处理（选择和投影）时间均忽略不计。二、第二种情况：Q2=sname(o=2(StSc)1计算自然连接(StSc)为了执行自然连接，读取St和SC表的策略不变，总的读取块数为2100块花费105S。但自然连接的结果比第一种情况大大减少为104个元组（学号相等元组），因此写出这些元组时间为1041020=50S(每块能装10个元组, 每秒读/写20块)，仅为第一种情况的千分之一。计算自然连接的总时间是105S+50S2读取中间文件块花费时间也为50S，再执行选择运算。（o=2）3把第2步结果投影输出。（sname）本次查询总时间是：105+50+50=205S=3.4分三、第三种情况：Q3=sname(So=2(Sc)1 先对SC表作选择运算（o=2(Sc) ）。读一遍SC表，读取10000/100=100块花费时间为5S（100/20）。满足条件的元组仅50个，不必写入外存。2读入St表和内存中的SC元组作连接读取St表（St），共1000/10=100块花费时间为5s。把读入的St元组和内存中的SC元组作连接的元组仅50个，不必写入外存。3把连接结果投影输出。（sname ）本次查询总时间是：5+5=10s。查询过程分析如下：假设SC表在Cno上有索引，St在Sno上有索引选择：读SC表索引，读SC表总块数= 50/100连接运算 特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。6找出公共子表达式。如果重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件，以后的操作是在中间文件上操作。例如：多次操作总是ST中某一院系学生的学号、姓名信息，可以先建立只有学号、姓名的视图，再对视图操作。其中的学号、姓名就是公共子表达式。424 关系代数等价变换规则l 各种查询语言都可以转换成关系代数表达式，关系代数表达式可以等价变换。u 关系代数表达式等价n 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。n 两个关系表达式E1和E2是等价的，记为E1E2n 优化策略大部分都涉及到代数表达式的变换。u 常用的关系等价变换规则如下：1连接、笛卡尔积交换律E1E2 E2E1 E1 E2 E2 E1 E1E2E2E1（有条件F的自然连接,相同属性组等值）F F2.连接、笛卡尔积的结合律设E1、E2、E3是关系代数表达式，F1和F2是连接运算的条件，则有：（E1E2）E3E1（E2E3）（E1 E2） E3E1（E2 E3） （E1 E2） E3E1（E2 E3）F1 F2 F1 F2 3投影的串接定律A1,A2,An(B1,B2,.Bm(E) A1,A2,An(E)假设：u E是关系代数表达式。u Ai（i=1，2，3，n）、Bj(j=1,2,3,.m)是属性名，并且A1,A2,An 是 B1,B2,B3,Bm的子集。4选择的串接定律Fl (F2(E) F1F2(E)其中，E是关系代数表达式，F1、F2是选择条件。选择的串接律说明选择条件可以合并。这样一次可检查全部条件。5选择与投影的交换律F(A1,A2,An(E) A1,A2,An(F(E)其中，选择条件F只涉及属性A1，A2，An 。若F中有不属于A1,A2,A3,An的属性B1,B2,Bm,则有更一般的规则：A1,A2,An(F(E)A1,A2,An(F (A1,A2,An,B1,B2,Bm(E) 6选择与笛卡尔积的交换律(1)假设：F中涉及的属性都是E1中的属性则：F(E1E2)F(E1)E2(2)假设：F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出：F(E1E2)F1(E1)F2(E2)(3) 假设：F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则 F(E1E2) F2(F1(E1)E2)它使部分选择在笛卡尔积前先做 7选择与并的交换设E=E1E2 , E1、E2有相同的属性名，则：F(E1E2)F(E1)F(E2)8选择与差运算的交换若E1与E2有相同的属性名，则：F(E1- E2)F(E1)-F(E2)9投影与笛卡尔积的交换设E1和E2是两个关系表达式，A1，A2，An是E1的属性，B1，B2，Bm是E2的属性，则 ：A1,A2,An,B1,B2,Bm(E1E2)A1,A2,An(E1)B1,B2,Bm(E2)10投影与并的交换设E1和E2有相同的属性名，则：A1,A2,An(E1E2) A1,A2,An(E1) A1,A2,An(E2)u 关系代数等价变换规则小结：1、2: 连接、笛卡尔积的交换律、结合律。3：合并或分解投影运算。4：合并或分解选择运算。5-8：选择运算与其他运算交换。5、9、10：投影运算与其他运算交换。425 关系代数表达式的优化算法关系表达式的优化算法：算法：关系表达式的优化。输入：一个关系表达式的语法树。输出：计算该表达式的程序。方法：(1) 分解选择运算：利用规则4把形如F1F2Fn(E)变换为：F1(F2(Fn(E) )(2)通过交换选择运算，将其尽可能移到叶端。对每一个选择，利用规则48尽可能把它移到树的叶端。 (3)通过交换投影运算，将其尽可能移到叶端。对每一个投影利用规则3、5、9、10中的一般形式尽可能把它移到树的叶端。 注意：法则3使一些投影消失，而规则5的更一般形式把一个投影分裂为两个，其中一个有可能被移向树的叶端。(4) 合并串接的选择和投影，以便能同时执行或在一次扫描中完成：l 利用规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。l 使多个选择或投影能同时执行，或在一次扫描中全部完成。l 虽然这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。 (5)对内节点分组：l 把上述得到的语法树的内节点分组。即每一双目运算(、-)和它所有的直接祖先为一组(这些直接祖先是、运算)。l 如果其后代直到叶子全是单目运算，也将它们并入该组。l 当双目运算是笛卡尔积()，而且其后的选择不能与它结合为等值连接时，把这些单目运算单独分为一组。(6) 生成程序：l 生成一个程序，每组结点的计算是程序中的步。l 各步的顺序是任意的，但是要保证任何一组的计算不会在它的后代组之后计算。4.2.6优化的一般步骤例如 求选修了课程Cno=2的学生姓名。优化步骤如下：（1） 把查询转换成某种内部表示（如语法树）。SQL查询语句SELECT St.Sname FROM St, SC WHERE St.Sno=SC.Sno AND SC.Cno=2; SQL语言转换成某种内部表示（如语法树）。转化为关系代数语法树：（2）代数优化：利用优化算法，把关系代数语法树转换成标准(优化)形式：利用等价规则4、6把选择SC.Cno=2移到叶端形成标准(优化)图4.5。（3）物理优化：选择低层的存取路径（系统实现）利用优化器查找数据字典获得当前数据库状态信息l 选择字段上是否有索引。l 连接的两个表是否有序。l 连接字段上是否有索引。根据一定的优化规则选择存取路径。如本例中若SC表上建有Cno的索引，则应该利用这个索引，而不必顺序扫描SC全表。（4）生成查询计划，选择代价最小的（系统实现）在作连接运算时，若两个表(设为R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划：l 对两个表作排序预处理l 对R1在连接属性上建索引l 对R2在连接属性上建索引l 在R1，R2的连接属性上均建索引对不同的查询计划计算代价，选择代价最小的一个。在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理时间在粗略计算时可不考虑。注意：优化的标准语法树的画法（实际优化的转化步骤）：u 根据题目要求写出SQL查询语句u 根据SQL语句写出关系代数表达式u 画出关系代数表达式的语法树u 采用优化准则和关系代数等价变化规则写出优化关系代数表达式u 根据优化关系代数表达式画出标准（优化）形式语法树注意:系统可以用多种等价的关系代数表达式来完成查询,因此可能会画出各种不同的优化树,但是都应遵循查询优化的一般准则。(见P159页实例)补充举例：例1 供应商数据库中有：供应商、零件、项目、供应四个基本表(含义同第2章)。S(Sno，Sname，Status，City)、P(Pno，Pname，Color，Weight)J(Jno，Jname，City)、SPJ(Sno，Pno，Jno，Qty)查询要求：检索使用上海供应商生产的红色零件的工程号。(1) SQL语句 :SELE JNO FROM S,P,SPJ WHERE COLOR=红色 AND CITY=上海 and S.SNO=SPJ.SNO AND SPJ.PNO=P.PNO(2)写出该查询的关系代数表达式:jno(city=上海color=红(spj.pno=p.pno(s.sno=spj.sno(SSPJ)P) 该查询初始的关系代数表达式的语法树如下:(图A)图 A 图B (3)写出查询优化的关系代数表达式:jno(SNO(city=上海(S)Sno,PNO,JNO(SPJ) Pno (Color=红(P)用优化算法，对初始的关系代数表达式的语法树进行优化，优化后的语法树（图B）例2:学生数据库中有两个基本表(关系)：St(Sno，Sname，Age，Sex，Sdept) 、 SC(Sno，Cno，Grade)查询要求：检索选修2号课程的学生姓名及其所在的