第四章关系系统及其查询优化 习题 1．试给出各类关系系统的定义：最小关系系统；关系完备上的系统；全关系型的关系系统。 2．试述全关系型系统应满足的十二条准则，以及十二条基本准则的实际意义和理论意义。 3．试述查询优化在关系数据库中的重要性和可能性。 4．对学生-课程数据库有如下的查询： SELECT Cname FROM Student，Course，SC WHERE Student。Sno=SC。Sno AND SC。Cno=Course。Cno AND Student。Sdept=’IS’； 此查询要求信息系学生选修了的所有课程名称。试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准优化树。 5．试述查询优化的一般准则。 6．试述查询优化的一般步骤。 参考答案 1．答：最小关系系统。 一个系统可定义为最小关系系统，当且仅当它： （1）支持关系数据库（关系数据结构），从用户观点看，关系数据库由表构成，并且只有表这一种结构 （2）支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径。 关系上完备的系统： 这类系统支持关系数据结构和所有的关系代数操作（或者功能上与关系代数等价的操作）。 全关系型的关系系统： 这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整和参照完整性。 2．答：关系模型的奠基人E。F。Codd具体地给出了全关系型的关系系统应遵循的十二条基本准则。从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。从理论意义上看，它是对关系数据模型具体而又深入的论述，是从理论和实际紧密结合的高度对关系型DBMSR 评述。 准则0 一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。 准则1信息准则。关系型DBMS的所有信息都应在逻辑一级上用一种方法即表中的值显式地表示。 准则2保证访问准则。依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项（分量值）。 准则3空值的系统化处理。全关系型的DBMS应支持空值的概念，并用系统化的方式处理空值。 准则4基于关系模型的动态的联机数据字典。数据库的描述在逻辑级应该和普通数据采用同样的方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息。 准则5统一的数据语言准则。 准则6视图更新准则。所有理论上可更新的视图也应该允许由系统更新。 准则7高级的插入、修改和删除操作。 准则8数据物理独立性。无论数据库的数据在存储表示或存取方法上作任何变化，应用程序和终端活动都保持逻辑上的不变性。 准则9数据逻辑独立性。当对基本关系进行理论上信息不受损的任何改变时，应用程序和终端活动都保持逻辑上的不变性。
第9章关系查询处理和查询优化 1．试述查询优化在关系数据库系统中的重要性和可能性。 答：查询优化在关系数据库系统中的重要性： 关系系统的查询优化既是RDBMS实现的关键技术，又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必考虑如何最好地表达查询以获取较好的效率，而且系统可以比用户程序的“优化”做得更好。 查询优化在关系数据库系统中的可能性： （1）优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性的分布情况、这些属性上是否有索引（B＋树索引、HASH索引、唯一索引或组合索引）等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 （2）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 （3）优化器可以考虑数十甚至数百种不同的执行计划，从中选出较优的一个，而程序员一般只能考虑有限的几种可能性。 （4）优化器中包括了很多复杂的技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。 2．对学生-课程数据库有如下的查询：
此查询要求信息系学生选修了的所有课程名称。 试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。 答：学生-课程数据库用关系代数表示的语法树如图9-1所示： 图9-1 关系代数语法树 优化后的标准语法树如图9-2所示：
图9-2 优化后的语法树 3．试述RDBMS查询优化的一般准则。 答：下面的优化策略一般能提高查询效率： （1）选择运算应尽可能先做； （2）投影运算和选择运算同时进行； （3）投影同其前或其后的双目运算结合起来； （4）某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算；（5）找出公共子表达式； （6）选取合适的连接算法。 4．试述RDBMS查询优化的一般步骤。
关系查询处理和查询优化小结 一．关系查询优化的概述 1. 查询优化在关系数据库中的重要性及必要性 关系系统的查询优化既是 RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。查询优化极大地影响RDBMS的性能。用户只要提出“干什么”，不必指出“怎么干”。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化’夕做得更好。 2.查询优化的可能性和优点 1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得 这些信息 2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以 选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的 几种可能性。 4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术；3.查询优化的一般准则 ( l ）选择运算应尽可能先做； ( 2 ）把投影运算和选择运算同时进行； ( 3 ）把投影同其前或其后的双目运算结合起来执行； ( 4 ）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算；( 5 ）找出公共子表达式； ( 6 ）选取合适的连接算法。 4. 查询优化的一般步骤 ( l）把查询转换成某种内部表示，通常用的内部表示是语法树。
( 2）把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。 ( 3）选择低层的存取路径。 ( 4）生成查询计划，选择代价最小的。 5.代价模型 一般DBMS采用基于代价的优化算法： 集中式数据库 单用户系统 总代价 = I/O代价 + CPU代价 多用户系统 总代价 = I/O代价 + CPU代价 + 内存代价 分布式数据库 总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价 二．关系数据库查询优化方法 1.代数优化 关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 1）查询树启发式优化，一般规则有 选择运算应尽可能先做(最重要，最根本) 目的：减小中间关系 投影运算和选择运算同时做 目的：避免重复扫描关系 将投影运算与其前面或后面的双目运算结合 目的：减少扫描关系的遍数 在执行连接操作前对关系适当进行预处理 按连接属性排序 在连接属性上建立索引 某些选择运算＋在其前面执行的笛卡尔积 ===> 连接运算 2）查询树的启发式优化—算法 （1）分解选择运算 （2）通过交换选择运算，将其尽可能移到叶端 （3）通过交换投影运算，将其尽可能移到叶端 （4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成 （5）对内结点分组 （6）生成程序
第 4 章关系系统及其查询优化 1. 试给出各类关系系统的定义：最小关系系统；关系上完备的系统；全关系型的关系系统。 2. 试述全关系型系统应满足的十二条准则，以及十二条基本准则的实际意义和理论意义。 3. 试述查询优化在关系数据库系统中的重要性和可能性。 4. 试述查询优化的一般准则。 5. 试述查询优化的一般步骤。 答案 1．最小关系系统：一个系统可定义为最小关系系统，当且仅当它： （1）支持关系数据库（关系数据结构）。从用户观点看，关系数据库由表构成，并且只有表这一种结构。 （2）支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径。 关系上完备的系统：这类系统支持关系数据结构和所有的关系代数操作（或者功能上与关系代数等价的操作）。 全关系型的关系系统：这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。 2．关系模型的奠基人 E.F.Codd 具体地给出了全关系型的关系系统应遵循的十二条基本准则。从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。从理论意义上看，它是对关系数据模型的具体而又深入的论述，是从理论和实际紧密结合的高度对关系型DBMS 的评述。 准则 0 一个关系型的 DBMS 必须能完全通过它的关系能力来管理数据库。 准则 1 信息准则。关系型 DBMS 的所有信息都应在逻辑一级上用一种方法即表中的值显式地表示。 准则 2 保证访问准则。依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项 ( 分量值 ) 。 准则 3 空值的系统化处理。全关系型的 DBMS 应支持空值的概念，并用系统化的方式处理空值。 准则 4 基于关系模型的动态的联机数据字典。数据库的描述在逻辑级上应该和普通数据采用同样的表示方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息。 准则 5 统一的数据子语言准则。 准则 6 视图更新准则。所有理论上可更新的视图也应该允许由系统更新。 准则 7 高级的插入、修改和删除操作。 准则 8 数据物理独立性。无论数据库的数据在存储表示或存取方法上作任何变化，应用程序和终端活动都保持逻辑上的不变性。 准则 9 数据逻辑独立性。当对基本关系进行理论上信息不受损害的任何改变时，应用程序和终端活动都保持逻辑上的不变性。 准则 l0 数据完整性的独立性。关系数据库的完整性约束条件必须是用数据库语言定义并存储在数据字典中的，而不是在应用程序中加以定义的。 准则 11 分布独立性。关系型 DBMS 具有分布独立性。 准则 12 无破坏准则。如果一个关系系统具有一个低级 ( 指一次一个记录 ) 语言，则这个低级语言不能违背或绕过完整性准则。
第九章关系查询处理和查询优化 内容概述 通过实例讲解关系数据库查询优化的重要性和可能性。讲解RDBMS的查询处理步骤，即查询分析、查询检查、查询优化和查询执行；查询优化的基本概念，查询优化包括代数优化和物理优化；代数优化是指关系代数表达式的优化；物理优化则是指存取路径和底层操作算法的选择，所以先讲解实现查询操作的主要算法，主要是选择操作和连接操作的主要算法思想，然后讲解关系代数表达式等价变换规则，关系代数表达式的优化，物理优化方法（基于启发式规则的存取路径选择优化，操作算法的执行代价估算方法，基于代价的优化方法）。 本章目标 本章并不要求学生掌握RDBMS查询处理和查询优化的内部实现技术，因此没有详细讲解技术细节。 本章的目的是希望学生了解RDBMS查询处理的基本步骤，查询优化的概念、基本方法和技术，为数据库应用开发中利用查询优化技术提高查询效率和系统性能打下基础。 重点和难点 重点：了解关系数据库查询优化的重要性。掌握查询处理各个步骤的主要功能。能够把SQL语句转换成查询树，对查询树进行代数优化，转换成优化的查询树。掌握物理优化的基本方法。 难点：能运用本章学习的查询优化知识，对于比较复杂的查询，尤其是涉及连接和嵌套的查询，写出适合
RDBMS自动优化的SQL语句。对于RDBMS不能优化的查询需要重写查询语句，进行手工调整以优化性能。不要把优化的任务全部放在RDBMS上。 实验内容 实验9 查询优化通过本章实验，了解你安装使用的RDBMS的查询优化方法和查询计划表示，能够利用它分析查询语句的实际执行方案和查询代价，进而通过建立索引或者修改SQL语句来降低查询代价，达到优化系统性能的目标。 具体实验内容： 1. 对单表查询例如以下的查询(可以自己给出查询语句) select * from student where age>20； 2. 连接查询，普通的两表连接查询或多表连接查询 3. 嵌套查询，自己写几个带有子查询的例子，主要考虑带有IN和EXISTS谓词的子查询，包括相关子查询和不相关子查询。也可以使用《数据库系统概论》书上列举的例子。 对以上各种查询，通过建立索引或者删除索引（单表查询语句）、修改连接顺序（连接查询语句）、重写SQL语句即查询重写(嵌套查询)；比较不同查询计划执行的性能差异，达到降低查询代价，优化性能的目标。
一单项选择题 1 设E是关系代数表达式，F1，F2是选取条件表达式，则有______。 A σF1（σF2（E））≡σF1∨F2（E） B σF1（σF2（E））≡σF1∧F2（E） C σF1（σF2（E））≡σF1（E） D σF1（σF2（E））≡σF2（E） 2 设E是关系代数表达式，F是选取条件表达式，并且只涉及A1，…，An属性，则有____。 A σF（πA1，…，An（E））≡πA1，…，An（σF（E）） B σF（πA1，…，An（E））≡πA1，…，An（E） C σF（πA1，…，An（E））≡πA1（σF（E）） D πA1，…，An（σF（E））≡πA1，…，An（σF（πA1，…，An，B1，…Bm（E））） 3 如果条件F形为F1∧F2，F1仅涉及到E1中的属性，F2仅涉及到E2中的属性，则有_____。 A σF（E1×E2）≡σF1（E1）×σF2（E2） B σF（E1×E2）≡σF1（σF1（E1）×σF2（E2）） C σF（E1×E2）≡σF2（σF1（E1）×σF2（E2）） D σF（E1×E2）≡σF1（E2）×σF2（E1） 4 如果一个系统定义为关系系统，则它必须___________。 A 支持关系数据库 B 支持选择、投影和连接运算 C A和B均成立 D A和B都不需要 5 如果一个系统为表式系统，则它支持__________。 A 关系数据结构 B A与选择、投影和连接运算 C A与所有的关系代数操作 D C与实体完整性、参照完整性 6 如果一个系统为关系完备系统，那么它支持___________。 A 关系数据结构 B A与选择、投影和连接运算 C A与所有的关系代数操作 D C与实体完整性、参照完整性 7 如果一个系统为全关系系统，那么它支持___________。 A 关系数据结构 B A与选择、投影和连接运算 C A与所有的关系代数操作 D C与实体完整性、参照完整性 8 关系代数表达式的优化策略中，首先要做的是__________。 A 对文件进行预运算 B 尽早执行选择运算 C 执行笛卡尔积运算 D 投影运算 9 在关系代数运算中，最费时间和空间的是_________________。 A 选择和投影运算 B 除法运算 C 笛卡尔积和连接运算 D 差运算 10 在关系代数表达式的等价优化中，不正确的叙述是____________。 A 尽可能早的执行连接运算 B 尽可能早的执行选择运算 C 尽可能早的执行投影运算 D 把笛卡尔积和随后的选择合并成连接运算 11 根据系统所提供的存取路径，选择合理的存取策略，这种优化方式称为__________。 A 物理优化 B 代数优化 C 规则优化 D 代价估算优化 二填空题 1 关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为用户只要提出_____________，不必指出______________。 2 在关系代数运算中，___________和__________________运算最费时间和空间。究竟应采用什么样的策略才能节省时间和空间，这就是优化的准则。
第四章 关系查询处理和查询优化 1、给出各类关系系统的定义：最小关系的系统；关系完备的系统；全关系型的 关系系统。答：(最小)关系系统：仅支持关系数据结构和三种关系操作。许多 微机关系数据库系统如FoxBASE，FoxPro等就属于这一类。 关系完备的系统： 这类系统支持关系数据结构和所有的关系代数操作(功能 20世纪90年代初的许多关系数据库管理系统属于这一类。 上与关系代数等价)。 全关系系统：这类系统支持关系模型的所有特征。即不仅是关系上完备的 而且支持数据结构中域的概念，支持实体完整性和参照完整性。目前，大多数 关系系统已不同程度上接近或达到了这个目标。 2、试述查询优化在关系数据库系统中的重要性和可能性。 答：查询优化在关系数据库系统中有着非常重要的地位。关系数据库系统和 非过程化的SQL语言能够取得巨大的成功， 关键是得益于查询优化技术的发展。 关系查询优化是影响RDBMS性能的关键因素。 优化对关系系统来说既是挑战又是机遇。所谓挑战是指关系系统为了达到用户 可接受的性能必须进行查询优化。由于关系表达式的语义级别很高，使关系系 统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。这就为 关系系统在性能上接近甚至超过非关系系统提供了机遇。 3．对学生-课程数据库有如下的查询： 查询信息系学生选修的所有课程名称: SELECT Cname FROM St,Course,SC WHERE St.Sno=SC.Sno AND https://www.doczj.com/doc/0619195461.html,o=https://www.doczj.com/doc/0619195461.html,o AND St.Sdept=’IS’ 试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法 树进行优化处理，画出优化后的标准语法树。 答：关系代数表达式如下： πcname(бSt.sdept=’IS’(бst.sno=sc.Sno(бhttps://www.doczj.com/doc/0619195461.html,o=https://www.doczj.com/doc/0619195461.html,o(ST×SC ×COURSE))) 用关系代数表示的语法树如下左图： πcname πcname бSt.sdept=’IS’ бhttps://www.doczj.com/doc/0619195461.html,o=https://www.doczj.com/doc/0619195461.html,o бst.sno=sc.Sno × бsc．Cno=https://www.doczj.com/doc/0619195461.html,o бSt.sno=sc.sno πcno,cname × × Course × Course πsno πsno,cno St Sc St.sdept=’IS’ Sc St 用关系代数表达式优化算法对原关系代数表达式进行优化，优化后的关系
第四章关系系统及其查询优化 4.1 关系系统 关系模型的三个基本要素：关系数据结构、关系的完整性、关系操作。 4.1.1 关系系统的定义 一、定义 满足以下两个条件的系统称为关系系统： ①具有关系数据结构； ②具有选择、投影、自然连接运算，且这些运算不依赖于物理存取路径。 二、解释 ①为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影、连接运算呢？ 因为不支持这三种关系运算的系统，用户使用仍不方便，不能提高用户的生产率，而提高用户生产率正是关系系统主要目标之一。 ②为什么要求这三种运算不能依赖于物理存取路径呢？ 因为依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。不依赖物理存取路径来实现关系运算就要求关系系统自动地选择路径。为此，系统要进行查询优化，以获得较好的性能。这正是关系系统实施的关键技术。 ③为什么要求关系系统支持这三种最主要的运算而不是关系代数的全部运算功能？ 因为它们是最有用的运算功能，能解决绝大部分的实际回题。 4.1.2 关系系统的分类 有了关系系统的定义，我们就可以根据它来区分哪些是真正的关系系统。 4.1.1定义的关系系统是关系系统的最小要求，许多实际系统，如Oracle、SQL Server、DB2、SyBase、Informix系统都不同程度地超过了这些要求。 按照E.F.Codd的思想，可以把关系系统分类如图4.1所示的四类系统。
图 4.1 关系系统的分类 说明： ①图中的圆表示关系数据模型。每个圆分为三部分，分别表示关系模型的三个组成部分：数据结构S(Structure)，完整性I(Integrity)，数据操纵M(Manipulation)。 ②图中阴影部分表示各类系统支持模型的程度。 一、表式系统 仅支持关系（即表）数据结构，不支持关系（即集合）操作。 二、（最小）关系系统 仅支持关系数据结构和三种关系搡作。即4.1.l中定义的关系系统。许多微机关系数据库系统如FoxBASE、FoxPro等就属于这一类。 三、关系完备的系统 这类系统支持关系数据结构和所有的关系代数操作（功能上与关系代数等价）。 四、全关系系统 这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。目前，大多数关系系统已不同程度上接近或达到了这个目标。 4.1.3 全关系系统的十二条基本准则 关系模型的奠基人E.F.Codd博士具体地给出了全关系型的关系系统应遵循的十二条基本准则。从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。从理论意义上看，它是对关系数据模型的具体而又深入的论述，是从理论和实际紧密结合的高度对关系型DBMS的评述。
第9章关系查询处理和查询优化 一、选择题 1．关系代数表达式的优化策略中，首先要做的是（）。 A．对文件进行预处理 B．尽早执行选择运算 C．执行笛卡尔积运算 D．投影运算 【答案】B 2．在关系代数运算中，最费时间和空间的是（）。 A．选择和投影运算 B．除法运算 C．笛卡尔积和连接运算 D．差运算 【答案】C 【解析】在关系代数运算中，最费时间和空间的是笛卡尔积和连接运算，所以尽可能放在后面做。 3．根据系统所提供的存取路径，选择合理的存取策略，这种优化方式称为（）。 A．物理优化
B．代数优化 C．规则优化 D．代价估算优化 【答案】A 【解析】物理优化是根据数据字典中的存取路径、数据的存储分布以及聚簇情况等信息来选择低层的存取路径。 4．在关系代数表达式的等价优化中，不正确的叙述是（）。 A．尽可能早地执行连接 B．尽可能早地执行选择 C．尽可能早地执行投影 D．把笛卡尔积和随后的选择合并成连接运算 【答案】A 【解析】在关系代数表达式中，连接运算的结果常常是一个较大的关系。如果尽可能早地执行连接，则运算得到的中间结果就会很大。 5．设E是关系代数表达式，F是选取条件表达式，并且只涉及A1，…，A n属性，则有（）。 A．бF（πA1，…，An（E））≡πA1，…，An（бF（E）） B．бF（πA1，…，An（E））≡πA1，…，An（E） C．бF（πA1，…，An（E））≡πA1（бF（E）） D．πA1，…，An（бF（E））≡πA1，…，An（бF（πA1，…，An，B1，…，Bm（E）））
【答案】A 6．如果一个系统定义为关系系统，则它必须（）。 A．支持关系数据库 B．支持选择、投影和连接运算 C．A和B均成立 D．A、B都不需要 【答案】C 7．如果一个系统为关系完备系统，那么它支持（）。 A．关系数据结构 B．A与选择、投影和连接 C．A与所有的关系代数操作 D．C与实体完整性、参照完整性 【答案】C 二、填空题 1．关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为，用户只要提出______，不必指出______。 【答案】干什么；怎么干 2．在RDBMS中，通过某种代价模型计算各种查询的执行代价。在集中式数据库中，
第10章查询处理和优化 1. 试述查询优化在关系数据库系统中的重要性和可能性。 解： 重要性：关系系统的查询优化既是RDBMS 实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化’做得更好。 可能性：这是因为：①优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况、这些属性上是否有索引、是什么索引（B ＋树索引还是HASH 索引或惟一索引或组合索引）等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。②如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。③优化器可以考虑数十甚至数百种不同的执行计划，从中选出较优的一个，而程序员一般只能考虑有限的几种可能性。④优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。 2. 试述查询优化的一般准则。 解： 查询优化的一般准则： ①选择运算优先原则 ②投影运算优先原则 ③笛卡尔积合并规则 ④提取公共表达式规则 ⑤必要的预处理 3. 试述查询优化的一般步骤。 解： 各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下：①把查询转换成某种内部表示，通常用的内部表示是语法树。②把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。 ③选择低层的存取路径。④生成查询计划，选择代价最小的。 4. 对学生—课程数据库有如下的查询： SELECT Cname FROM Student, Course, SC WHERE Student.Sno=SC.Sno AND https://www.doczj.com/doc/0619195461.html,o=https://www.doczj.com/doc/0619195461.html,o AND Student.Sdept=’IS’ ; 此查询要求信息系学生选修了的所有课程名称。 试画出用关系代数标识的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。 解： 其关系代数表达式为: 用关系代数表达式优化算法对原关系代数表达式进行优化，优化后的关系代数表达式如下： ，用关系代数表示的语法树如左图所示，优化处理后的标准语法树如右图所示。