第七章 关系系统及其优化优秀PPT.ppt

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

1、第七章第七章 关系系统及其优化关系系统及其优化现在学习的是第1页，共33页关系系统的定义q关系系统:支持关系数据模型的数据库管理系统(粗略)q关系系统(确切定义):一个系统可以定义为一个关系系统,当且仅当它:支持关系数据库支持选择、投影和连接运算(自然连接),对这些运算不要求定义任何物理存取路径现在学习的是第2页，共33页关系系统的分类:q许多关系系统的产品q按E.F.Codd的思想将关系系统分为:表式系统(a)最小关系系统(b)关系完备的系统(c)全关系系统(d)SMISMISMISMIabcd现在学习的是第3页，共33页关系系统的查询处理:q查询处理的步骤:queryParser&tran

2、slatorRelational algebra expressionOptimizerExecution planEvaluationengineQuery outputdataStatisticsabout dataDBMS现在学习的是第4页，共33页关系系统的查询优化:q为什么需要查询优化q关系系统的查询优化由系统完成,而不是由用户完成优化器可以数据字典获取许多统计信息如果数据库的物理统计信息改变了,优化器可以对查询进行重新优化以选择适应的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术q优化目标:寻求最优的执行计划,使查询执行开销尽量小现在学习的是第5页，共33页关

3、系系统的查询优化:q查询优化的一般步骤将查询转化成内部表示-语法树根据等价变化规则,将语法树转化成优化形式选择低层操作算法生成查询计划q查询执行开销主要包括:总代价=I/O代价+CPU代价q多用户数据库执行开销:总代价=I/O代价+CPU代价+内存代价现在学习的是第6页，共33页关系系统的查询优化:q一个查询实例:求选修2号课程的学生姓名SQL表示:select Snamefrom Students,SCwhere Students.Sno=SC.Sno and Cno=2;关系代数表示:Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)Q2=

4、sname(Cno=2(Students SC)Q3=sname(Students Cno=2(SC)现在学习的是第7页，共33页q代价计算 Q1代价计算(仅考虑I/O代价)计算广义笛卡尔积代价假定:在内存中,存放5块Students元组和一块SC元组,一块可以装10个Students元组或100个SC元组.假定:Students有1000个元组,SC有10000个元组,其中选2号课程的有50个元组数据只有读到内存才能进行连接Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)现在学习的是第8页，共33页通过读取块数计算I/O代价 读取块数计算方

5、法:Students 1000个元组 SC 10000个元组读取总块数:若每秒读写20块,则花费:10100SCStudents5块块Q1=sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)现在学习的是第9页，共33页连接后的元组个数为:103 104=107连接后的中间结果内存放不下,需暂时写到外存若每块可装10个元组,则写出这些元组需:(107/10)/20=5 104s选择操作:读回需5 104s,选择后剩50个元组,假定均可放在内存投影操作:查询共花费:105+2 5 104 105 sQ1=sname(Students.Sno=SC.Sno

6、 and Cno=2(StudentsSC)现在学习的是第10页，共33页Q2=sname(Cno=2(Students SC)Q2代价计算(仅考虑I/O代价)计算自然连接代价也要把数据读到内存进行连接,但连接结果比笛卡尔积要小得多读取块数依然为:花费为2100/20105s连接结果大小为104个元组,写到外存需:(104/10)/20=50s现在学习的是第11页，共33页 Q2=sname(Cno=2(Students SC)Q3=sname(Students Cno=2(SC)读取自然连接结果,执行选择运算,需50s,选择结果均可放在内存投影运算:总花费为:105+50+50=205sQ3

7、代价计算(仅考虑I/O代价)计算对SC做选择运算的代价需读SC到内存进行选择运算读SC块数为:10000/100=100花费为:100/20=5s选择结果为50个SC元组,均可放在内存现在学习的是第12页，共33页Q3=sname(Students Cno=2(SC)计算和Students自然连接的 代价需读Students到内存进行连 接运算读Students块数为:1000/10=100花费为:100/20=5s连接结果为50个元组,均可放在内存投影运算:总花费:5+5=10s1050SCStudents5块块现在学习的是第13页，共33页关系系统的查询优化:q查询优化的一般准则:下面的优

8、化策略一般能提高查询效率,但不一定是最优的选择运算尽可能先做,降低中间结果大小在连接前,对关系适当的进行预处理:对关系排序(排序合并连接方法)或在连接属性上建索引(索引连接方法)9500495002.95003.95001.Students95003 1 95003 2 95004 2.95004 3.95001 1.SC循环嵌套连接循环嵌套连接(不不做任何预处理做任何预处理):.现在学习的是第14页，共33页关系系统的查询优化:9500195002.95003.95004.Students95001 1 95003 1 95003 2 95004 2.95004 3.SC排序合并连接排序合并

9、连接(连连接的关系分别排序接的关系分别排序):.索引连接索引连接(在在SC的的连接列连接列Sno上建立上建立索引索引):Students95001 9500395003 95004 95004.SC索引索引.9500495002.95003.95001.95003 1 95003 2 95004 2.95004 3.95001 1.SC现在学习的是第15页，共33页关系系统的查询优化:把投影运算和选择运算同时进行 sno(cno=2(SC)把投影和其前或后的双目运算结合起来 Cname(Course SC)把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 Students.Sno=

10、SC.Sno and Cno=2(Students SC)找出公共子表达式现在学习的是第16页，共33页关系系统的查询优化:q关系代数等价变换规则:给定sname(Students.Sno=SC.Sno and Cno=2(StudentsSC)如何将上述提到的运算先做,即得到:sname(Students Cno=2(SC)规则1:连接、笛卡尔积的交换律 E1 E2 E2 E1 E1 E2=E2 E1 E1 E2=E2 E1 E:关系代数表达式 F:连接条件规则2:连接、笛卡尔积的结合律 (E1 E2)E3=E1(E2 E3)(E1 E2)E3 E1 (E2 E3)(E1 E2)E3 E1

11、(E2 E3)F1FFF2F1F2现在学习的是第17页，共33页关系系统的查询优化:规则3:投影的串接定律 A1,A2,.,An(B1,B2,.,Bn(E)A1,A2,.,An(E)规则4:选择的串接定律 F1(F2(E)F1F2(E)规则5:选择和投影的交换律 F(A1,A2,.,An(E)A1,A2,.,An(F(E)特殊情况 A1,A2,.,An(F(E)A1,A2,.,An(F(A1,A2,.,An,B1,B2,.,Bm(E)规则6:选择与笛卡尔积的交换律 F(E1 E2)F(E1)E2 F仅和E1有关 F(E1 E2)F1(E1)F2(E2)F=F1F2 F(E1 E2)F2(F1(

12、E1)E2)F1-E1 F2-E1E22021现在学习的是第18页，共33页关系系统的查询优化:规则7:选择与并的交换 F(E1 E2)F(E1)F(E2)规则8:选择与差的交换 F(E1-E2)F(E1)-F(E2)规则9:投影与笛卡尔积的交换 A1,A2,.,An,B1,B2,.,Bm(E1 E2)A1,A2,.,An(E1)B1,B2,.,Bm(E2)规则10:投影与并的交换 A1,A2,.,An(E1 E2)A1,A2,.,An(E1)A1,A2,.,An(E2)20现在学习的是第19页，共33页关系系统的查询优化:q关系代数表达式的优化算法:应用关系代数等价变换规则来优化关系代数表达

13、式,使优化后的表达式能遵循查询优化的一般准则,在语法树上进行优化关系代数表达式的优化算法输入:语法树 1 利用规则4把形如F1F2Fn(E)变换成 F1(F2(Fn(E).)2 对每一个选择,利用规则48尽可能移到树的叶端 3 对于每个投影,利用规则3,9,10,5尽可能移到树 的叶端20页页现在学习的是第20页，共33页关系系统的查询优化:4 利用规则35把选择和投影的串接合并成单个选择,单个投影,或一个选择后跟一个投影 5 把处理后的语法树内节点分组:l每一双目运算(,)和它的所有直接祖先(,)为一组,后代直到叶子全是单目运算也并入该组;l若双目运算为,且其后的选择不能与它结合为等值连接时

14、,这些单目运算单独为一组.6 生成一个程序,每组节点的计算是程序中的一步输出:计算关系代数表达式的程序21页页现在学习的是第21页，共33页关系系统的查询优化:SSPP不能结不能结合成等合成等值连接值连接 S.Sno=SC.SnoSCS能结合能结合成等值成等值连接连接22页页现在学习的是第22页，共33页关系系统的查询优化:q优化的一般步骤:因DBMS不同把查询转换成某种内部表示(例如关系代数语法树)把语法树转化成标准(优化)形式选择底层的存取路径生成查询计划,选择代价最小的q例子:设有供应商S,零件P和供应关系SP三个关系,其关系模式:S(Snum,Sname,City)P(Pnum,Pna

15、me,Weight,Size)SP(Snum,Pnum,Dept,Quan)23页页现在学习的是第23页，共33页关系系统的查询优化:select Sname from S,SP,P where S.Snum=SP.Snum and SP.Snum=P.Snum and S.City=NANJING and P.Pname=Bolt and SP.Quan1000;原始语法树:select-投影 from-笛卡尔积 where-选择24页页现在学习的是第24页，共33页关系系统的查询优化:Sname cSSPPC=S.Snum=SP.Snum and SP.Snum=P.Snum and S.

16、City=NANJING and P.Pname=Bolt and SP.Quan1000Sname cSSPPSname cSSPP s sp pSname cSSPP s sp pSnameSSPP s sp p s p sp c c优化优化:25页页现在学习的是第25页，共33页练习练习1查询要求查询要求:l查询信息系学生选修的所有的课程的课程名称查询信息系学生选修的所有的课程的课程名称l写出关系代数及其原始语法树写出关系代数及其原始语法树,并进行优化处并进行优化处理理,画出优化后的语法树画出优化后的语法树.SELECT Cname FROM Students,Course,SCWHER

17、E Students.sno=SC.sno and Co=SC.cno and Sdept=IS;26页页现在学习的是第26页，共33页练习练习1:Cname(Sdept=IS(Students SC Course)Cname c StudentsSCCourse 原始语法树原始语法树:27页页 Cname c1StudentsSCCourse C:Students.sno=Sc.sno SC.cno=Co Sdept=ISC:SC.cno=Co,C1:Sdept=IS Cname c1 StudentsSCCourse c现在学习的是第27页，共33页练习练习2查询要求查询要求:l一图书管理

18、数据库，其关系如下：一图书管理数据库，其关系如下：BOOKS(Title,Author,Pname,LC_No)PUBLISHERS(Pname,Paddr,Pcity)BORROWERS(Name,Addr,City,Card_No)LOANS(Card_No,LC_No,Date)要求：要求：1.列出列出2003年年1月月1日前借出的所有书名和借书人姓名日前借出的所有书名和借书人姓名2.写出关系代数及其原始语法树写出关系代数及其原始语法树,并进行优化处理并进行优化处理,画出优化后画出优化后的语法树的语法树.SELECT Title,Name from BOOKS,BORROWERS,LOA

19、NSWHERE BOOKS.LC_No=LOANS.LC_No AND BORROWERS.Card_No=LOANS.Card_No ANDDate01/01/200326页页图书编号图书编号图书证号图书证号现在学习的是第28页，共33页练习练习2:Title,Name(Date01/01/2003(BOOKS BORROWERS LOANS)Title,Name Date01/01/2003 BOOKSBORROWERSLOANS 原始语法树原始语法树:27页页 BOOKS.LC_No=LOANS.LC_No AND BORROWERS.Card_No=LOANS.Card_No Titl

20、e,Author,Pname,LC_No,Name,Addr,City,Card_No,Date现在学习的是第29页，共33页练习练习2:Title,Name(Date01/01/2003(BOOKS BORROWERS LOANS)28页页sDate01/01/2003(BOOKS BORROWERS LOANS)=BOOKS Date01/01/2003(BORROWERS LOANS)=BOOKS BORROWERS Date01/01/2003(LOANS)Title,Name Date01/01/2003 BOOKSBORROWERSLOANS BOOKS.LC_No=LOANS.L

21、C_No BORROWERS.Card_No=LOANS.Card_No 现在学习的是第30页，共33页练习练习2:Title,Name(Date01/01/2003(BOOKS BORROWERS LOANS)29页页增加两个投影：增加两个投影：Title，BOOKS.LC_No Name，LOANS.LC_No Title,Name Date01/01/2003 BOOKSBORROWERSLOANS BOOKS.LC_No=LOANS.LC_No BORROWERS.Card_No=LOANS.Card_No Title，BOOKS.LC_No Name，LOANS.LC_No现在学习的

22、是第31页，共33页练习练习2:Title,Name(Date01/01/2003(BOOKS BORROWERS LOANS)30页页 Title,Name Date01/01/2003 BOOKSBORROWERSLOANS BOOKS.LC_No=LOANS.LC_No BORROWERS.Card_No=LOANS.Card_No Title，BOOKS.LC_No Name，LOANS.LC_No Name，BORROWERS.CARD_No LOANS.LC_No,LOANS.Card_No现在学习的是第32页，共33页练习练习2:Title,Name(Date01/01/2003(BOOKS BORROWERS LOANS)31页页 Title,Name Date01/01/2003 BOOKSBORROWERSLOANS Title，BOOKS.LC_No Name，LOANS.LC_No Name，BORROWERS.CARD_No LOANS.LC_No,LOANS.Card_No 最后语法树：最后语法树：现在学习的是第33页，共33页