习题9

习题9查询优化的一般步骤1.把查询转换成某种内部表示，通常用的内部表示是语法树。2.把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。3.选择低层的存取路径。4.生成查询计划，选择代价最小的。SQL查询SQL查询处理器编译后的查询查询优化器查询计划代码生成器执行代码运行时处理器查询结果扫描，语法分析，有效性检查查询的内部表示表达式转换，代价估算等优化的查询计划数据字典数据库数据查询优化在关系数据库系统中的重要性•重要性：（1）关系系统的查询优化即是RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。（2）查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好查询优化在关系数据库系统中的可能性•可能性：–(1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息–(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。查询优化在关系数据库系统中的可能性–(3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。–(4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术查询优化的一般准则•下面的优化策略一般能提高查询效率：1.选择运算应尽可能先做；2.把投影运算和选择运算同时进行；3.把投影同其前或其后的双目运算结合起来；4.把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算；5.找出公共子表达式；6.选取合适的连接算法。索引连接，排序合并算法，HASH连接算法。数据库系统工程师真题查询树•对学生-课程数据库有如下查询：SELECTCnameFROMStudent,Course,SCWHEREStudent.Sno=SC.snoandSC.Cno=Course.CnoandStudent.Sdept=‘IS’;查询信息系学生选修了的所有课程的名称。试画出用关系代数表示的语法树，并给出优化后的标准语法树。最初的语法树•结果project(Cname)Select(Student.Sdept=‘IS’)Join(SC.Cno=Course.Cno)Join(Student.Sno=SC.Sno)CourseStudentSC关系代数语法树∏CnameσStudent.Sdept=‘IS’σSC.Cno=Course.Cno×σStudent.Sno=SC.SnoCourse×StudentSC优化后的语法树∏CnameσSC.Cno=Course.Cno×σStudent.Sno=SC.SnoCourse×SCσStudent.Sdept=‘IS’Student填空题•等式∏L(σF(E))=σF(∏L(E))成立的条件是＿＿＿。•等式∏L1(∏L2(E))=∏L1(E)成立的条件是＿＿＿。•等式σF(E1×E2)=E1×σF(E2)成立的条件是＿＿＿。•等式σF(E1E2)=σF(E1)σF(E2)成立的条件是＿＿＿。答案：条件F只涉及到L中的属性L1是L2的子集F只涉及到E2中的属性F只涉及到E1和E2中的公共属性查询树•在教学数据库的三个关系S(S#,Sname,Age,Sex)SC(S#,C#,Grade)C(C#,Cname,Teacher)中，用户有如下查询语句：(1)检索女同学选修课程的课程名和任课教师名.(2)检索不学“数据库”课程的学生姓名与年龄。(3)检索至少学习Wang老师所授一门课程的女学生的学号和姓名。1.试写出该查询的关系代数表达式。2.画出查询表达式的语法树3.使用启发式优化算法，对语法树进行优化，并画出优化后的语法树。（1）关系代数表达式及其语法树∏CNAME,TEACHER(σSEX=‘F’(SSCC)∏CNAME,TEACHERσSEX=‘F’σSC.Cno=C.Cno×σS.Sno=SC.SnoC×SSC（1）优化后的查询树∏CNAME,TEACHERσSC.Cno=C.Cno×σS.Sno=SC.SnoC×σSEX=‘F’SCS（2）关系代数表达式及其语法树πSNAME,AGE(S)-πSNAME,AGE(σCName=‘数据库'(SSCC))-πSNAME,AGEπSNAME,AGESσCName=‘数据库‘σSC.C#=C.C#∧SC.S#=S.S#×S×SCC（2）优化后的查询树-πSNAME,AGEπSNAME,AGESσSC.S#=S.S#×πSC.S#πS.S#,SNAME,AGEσSC.C#=C.C#S×πSC.S#,C#πC,C#SCσCName=‘数据库‘C（3）关系代数表达式及其语法树πS#,SNAME(σSEX=‘F’∧TEACHER=‘Wang’(SSCC))πS.S#,SNAMEσSEX=‘F’∧TEACHER=‘Wang’σC.C#=SC,C#∧SC.S#=S.S#××SCSC（3）优化后的查询树πS.S#,SNAMEσSC.S#=S.S#×πSC.S#,πS.S#,,SnameσC.C#=SC.C#σSEX=‘F’×SπC.C#,πSC.S#,,SC,C#σTEACHER=‘Wang’SCC