1、第四章 关系系统及其查询优化1、掌握关系系统的有关概念、掌握关系系统的有关概念2、了解全关系系统的十二条基本准则、了解全关系系统的十二条基本准则3、掌握查询优化的一般策略、掌握查询优化的一般策略4、掌握关系代数的等价变换规则、掌握关系代数的等价变换规则5、掌握关系代数表达式的优化算法和优化的一般步骤、掌握关系代数表达式的优化算法和优化的一般步骤本章要求：本章要求：本章内容：本章内容：请选择内容请选择内容返回返回1 关系系统关系系统2 关系系统的查询优化关系系统的查询优化.1第四章 关系系统及其查询优化一、关系系统的定义一、关系系统的定义1、关系模型：、关系模型：数据结构：数据结构：关系（二维表
2、）关系（二维表）数据操纵：数据操纵：关系代数（或关系演算）关系代数（或关系演算）完整性约束：实体完整性、参照完整性、用户定义的完整性完整性约束：实体完整性、参照完整性、用户定义的完整性2、关系系统的定义、关系系统的定义 关系系统是关系数据库系统的简称关系系统是关系数据库系统的简称 从概念上讲，支持关系模型的系统称为关系系统。从概念上讲，支持关系模型的系统称为关系系统。一个系统称为关系系统，当且仅当一个系统称为关系系统，当且仅当（1）支持关系数据结构；）支持关系数据结构；（2）支持选择、投影和连接运算。）支持选择、投影和连接运算。对运算不要求定义任何物对运算不要求定义任何物理存取路径。理存取路径
3、。1 1 关系系统关系系统要求过于严格要求过于严格 按最小要求定义关系系统：按最小要求定义关系系统：.2第四章 关系系统及其查询优化二、关系系统的分类二、关系系统的分类 按对按对关系模型关系模型的支持程度来分的支持程度来分SMI数据操纵数据操纵完整性完整性结构结构1、表式系统、表式系统 仅支持关系结构，仅支持关系结构，不支持集合级操作不支持集合级操作SMIS如：倒排表如：倒排表.3第四章 关系系统及其查询优化SMIS2、（最小）关系系统、（最小）关系系统 支持关系结构，支持关系结构，支持选择、投影和连接运算支持选择、投影和连接运算M3、关系上完备的系统、关系上完备的系统 支持关系结构，支持关系
4、结构，支持所有的关系代数操作支持所有的关系代数操作SMISMM如：如：SYBASE、ORACLE、DB2如：如：FoxBASE、FoxPro.4第四章 关系系统及其查询优化4、全关系系统、全关系系统 支持关系模型的所有特征支持关系模型的所有特征 SYBASE、ORACLE、DB2等系统已接近这个目标等系统已接近这个目标SMISMSI三、全关系系统的十二条基本准则三、全关系系统的十二条基本准则基础（准则基础（准则 0 0）：）：关系型关系型DBMS必须能完全通过它的关系能必须能完全通过它的关系能 力来管理数据库力来管理数据库在关系一级上支持数据的插入、删除、修改，在关系一级上支持数据的插入、删除
5、、修改，没有任何操作必须通过非关系的能力才能实现没有任何操作必须通过非关系的能力才能实现.5第四章 关系系统及其查询优化准则准则1 1：信息准则：信息准则。逻辑上可用一种方法（表中的值）来表示。逻辑上可用一种方法（表中的值）来表示 所有信息。所有信息。用户数据、元数据、索引、应用元数据统一用表格来表示用户数据、元数据、索引、应用元数据统一用表格来表示好处：好处：提高用户生产率提高用户生产率 便于便于DBA维护数据库维护数据库 便于与其它软件接口便于与其它软件接口准则准则2 2：保证访问准则：保证访问准则。依靠表名、主键、列名的组合，保证。依靠表名、主键、列名的组合，保证 能以逻辑方式（而不是物
6、理方式）访能以逻辑方式（而不是物理方式）访 问到每一个数据项。问到每一个数据项。准则准则3 3：空值的系统化处理：空值的系统化处理。好处：好处：完善完整性约束完善完整性约束 对库函数计算的准确性极为重要对库函数计算的准确性极为重要.6第四章 关系系统及其查询优化准则准则5 5：统一的数据子语言准则：统一的数据子语言准则。一种语言全面支持以下功能：一种语言全面支持以下功能：数据定义、视图定义数据定义、视图定义 数据操作数据操作 完整性约束完整性约束 授权授权 事务处理功能事务处理功能准则准则4 4：基于关系模型的动态的联机数据字典：基于关系模型的动态的联机数据字典。数据库自身的描述（元数据）也用
7、关系，且授权用户数据库自身的描述（元数据）也用关系，且授权用户 也可以查询。也可以查询。好处：好处：学习简单学习简单 授权用户可扩充数据字典授权用户可扩充数据字典.7第四章 关系系统及其查询优化准则准则6 6：视图更新准则：视图更新准则。所有理论上可更新的视图也应该允许。所有理论上可更新的视图也应该允许 由系统更新。由系统更新。提高逻辑独立性提高逻辑独立性准则准则7 7：高级的插入、修改、删除操作：高级的插入、修改、删除操作。把一个基本关系或导。把一个基本关系或导 出关系作为单一的操作对象进行处理。出关系作为单一的操作对象进行处理。好处：好处：简化用户操作简化用户操作 便于系统优化便于系统优化
8、 便于分布式处理便于分布式处理准则准则8 8：数据物理独立性：数据物理独立性。准则准则9 9：数据逻辑独立性：数据逻辑独立性。准则准则1010：数据完整性的独立性：数据完整性的独立性。完整性约束条件必须是用数据子语言定义并存储在数完整性约束条件必须是用数据子语言定义并存储在数 据字典中。据字典中。.8第四章 关系系统及其查询优化准则准则1111：分布独立性：分布独立性。数据子语言能使应用程序和终端活动在下列情况下保持数据子语言能使应用程序和终端活动在下列情况下保持 逻辑不变性：逻辑不变性：首次分布数据时；首次分布数据时；数据重新分布时。数据重新分布时。准则准则1212：无破坏准则：无破坏准则。
9、如果一个关系系统具有一个低级（指一次一记录）语言，如果一个关系系统具有一个低级（指一次一记录）语言，则这个低级语言不能违背或绕过完整性准则。则这个低级语言不能违背或绕过完整性准则。E.F.Codd提出的提出的12条准则条准则本节开头本节开头下一节下一节本章开头本章开头.9第四章 关系系统及其查询优化 关系数据语言只需用户指出关系数据语言只需用户指出“干什么干什么”，不必指出，不必指出“怎怎么干么干”，为什么能做到这一点？，为什么能做到这一点？一个重要原因就是一个重要原因就是系统能自动进行查询优化系统能自动进行查询优化。查询优化的总目标：查询优化的总目标：选择有效的策略，求得给定的关系表达式的值
10、。选择有效的策略，求得给定的关系表达式的值。一、为什么要进行查询优化？一、为什么要进行查询优化？例：例：求选修了课程求选修了课程C2的学生姓名的学生姓名SELECT S.SNFROM S,SCWHERE S.S#=SC.S#AND SC.C#=C2;2 2 关系系统的查询优化关系系统的查询优化.10第四章 关系系统及其查询优化也可用也可用SQL语言如下实现语言如下实现:SELECT SNFROM SWHERE S.S#IN (SELECT SC.S#FROM SC WHERE C#=C2);对于一个复杂的查询，不同的用户可能会写出许许多多不对于一个复杂的查询，不同的用户可能会写出许许多多不同的
11、查询方法。这些方法有的简单，有的复杂。它们的执行结同的查询方法。这些方法有的简单，有的复杂。它们的执行结果是一样的，但执行效率可能是不一样的。系统能解决这一问果是一样的，但执行效率可能是不一样的。系统能解决这一问题吗？题吗？.11第四章 关系系统及其查询优化 对这一查询，可以考虑下面几种实现方式：对这一查询，可以考虑下面几种实现方式：1、先求、先求S和和SC的笛卡尔积，然后从中选出两学号字段值相等、的笛卡尔积，然后从中选出两学号字段值相等、课程号为课程号为C2的元组：的元组：Q1=（S SC）SN S.S#=SC.S#SC.C#=C22、先做、先做S和和SC的自然连接，然后从中选出课程号为的自
12、然连接，然后从中选出课程号为C2的元组：的元组：Q2=（S SC）SN SC.C#=C23、先从、先从SC中选出课程号为中选出课程号为C2的元组，然后将该结果与的元组，然后将该结果与S 连接：连接：Q3=（S （SC）SN SC.C#=C2.12第四章 关系系统及其查询优化 分析三种实现策略的执行时间分析三种实现策略的执行时间：设有设有1000学生记录，学生记录，10000选课记录，选修选课记录，选修C2课程的学生有课程的学生有50名。名。1、第一种策略：、第一种策略：Q1=（S SC）SN S.S#=SC.S#SC.C#=C2（1）计算广义笛卡尔积）计算广义笛卡尔积 S SC：执行方式：执行
13、方式：读读S表表读读SC表表S1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 22S6 F CS 19S1 C1 AS1 C2 AS1 C3 A每次读每次读若干块若干块每次读每次读一块一块S SC存于临时文件中存于临时文件中S1 A CS 20 S1 C1 AS1 A CS 20 S1 C2 AS1 A CS 20 S1 C3 AS2 B CS 21 S1 C1 AS2 B CS 21 S1 C2 AS2 B CS 21 S1 C3 A S6 F CS 19 S1 C1 AS6 F CS 19 S1 C2 AS6 F CS 19 S1 C3 A.1
14、3第四章 关系系统及其查询优化读读S表表读读SC表表S1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 22S6 F CS 19S1 C1 AS1 C2 AS1 C3 AS SC存于临时文件中存于临时文件中S1 A CS 20 S1 C1 AS1 A CS 20 S1 C2 AS1 A CS 20 S1 C3 AS2 B CS 21 S1 C1 AS2 B CS 21 S1 C2 AS2 B CS 21 S1 C3 A S6 F CS 19 S1 C1 AS6 F CS 19 S1 C2 AS6 F CS 19 S1 C3 AS1 C5 BS2 C1
15、 BS2 C2 C读下一块读下一块S1 A CS 20 S1 C5 BS1 A CS 20 S2 C1 BS1 A CS 20 S2 C2 C 相当于相当于外循环外循环相当于相当于内循环内循环.14第四章 关系系统及其查询优化 设一块能装设一块能装10个学生记录或个学生记录或100个选课记录，每次在内存中个选课记录，每次在内存中存放存放5块块S的元组、的元组、1块块SC的元组，则的元组，则S表和表和SC表的总块数各为表的总块数各为100。外循环一次，内循环。外循环一次，内循环20次，要读取的总块数为次，要读取的总块数为 100+100 20=2100块块连接后的元组数为连接后的元组数为 100
16、0 10000=1千万，设每块能装千万，设每块能装10个元组，个元组，则则 S SC的总块数为的总块数为1百万块百万块 设每秒能读写设每秒能读写20块，则块，则读的时间：读的时间：2100块块 20块块/秒秒=105秒秒写的时间：写的时间：1000000块块 20块块/秒秒=50000秒秒（2）依次读入）依次读入S SC的元组，然后执行选择：的元组，然后执行选择：读的时间：读的时间：1000000块块 20块块/秒秒=50000秒秒满足条件的元组满足条件的元组50个，设全部放入内存（不再临时存储）个，设全部放入内存（不再临时存储）.15第四章 关系系统及其查询优化（3）在上步基础上执行投影得最
17、终结果（此步时间不计）。）在上步基础上执行投影得最终结果（此步时间不计）。第一种策略的总时间为：第一种策略的总时间为：105+50000+50000 10万秒（近万秒（近28小时）小时）Q2=（S SC）SN SC.C#=C22、第二种策略、第二种策略（1）计算自然连接）计算自然连接 读取读取S表和表和SC表的策略不变，执行时间还是表的策略不变，执行时间还是105秒。秒。因为因为SC表中的每一个学号都在表中的每一个学号都在S表中出现，而表中出现，而S表中无重复表中无重复学号，故连接后的表和学号，故连接后的表和SC表的行数一样，为表的行数一样，为10000行，将它们行，将它们临时存入盘中需临时存
18、入盘中需 （10000 10）块）块 20块块/秒秒=50秒秒计算自然连接需时：计算自然连接需时：105+50=155秒秒.16第四章 关系系统及其查询优化（2）执行选择运算）执行选择运算主要为读取中间文件的时间：为主要为读取中间文件的时间：为50秒秒（3）把上一步结果投影，时间忽略不计）把上一步结果投影，时间忽略不计第二种策略的总时间为：第二种策略的总时间为：155+50=205秒秒Q3=（S （SC）SN SC.C#=C23、第三种策略、第三种策略（1）先对）先对SC表作选择表作选择 只需读一遍只需读一遍SC表，需时表，需时 100块块 20块块/秒秒=5秒秒 中间结果只有中间结果只有50
19、个记录，不需使用中间文件个记录，不需使用中间文件（2）作自然连接）作自然连接 只需读一遍只需读一遍S表，边读边和内存中的中间结果连接，结果表，边读边和内存中的中间结果连接，结果仍为仍为50个元组需时个元组需时 5秒秒.17第四章 关系系统及其查询优化（3）把上一步结果投影，时间忽略不计）把上一步结果投影，时间忽略不计第三种策略的总时间为：第三种策略的总时间为：5+5=10秒秒结论：不同的查询策略其执行时间可能差别很大结论：不同的查询策略其执行时间可能差别很大二、优化的一般策略二、优化的一般策略好处：减少下一步运算的数据量好处：减少下一步运算的数据量1、选择、投影运算应尽可能先做、选择、投影运算
20、应尽可能先做2、把选择和投影运算同时进行、把选择和投影运算同时进行好处：减少扫描关系的次数好处：减少扫描关系的次数 （S）SN SD=CSS1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 22表表S S#SN SD SA.18第四章 关系系统及其查询优化3、在执行连接前对文件适当地预处理、在执行连接前对文件适当地预处理例如：计算例如：计算 S SCSC：S#C#GS4 C3 BS1 C2 AS1 C5 BS6 C4 AS2 C1 BS5 C3 BS2 C2 CS1 C1 AS2 C4 CS3 C2 BS1 C3 AS3 C3 CS4 C5 DS5 C2 CS3 C4
21、BS5 C5 BS6 C5 AS：S#SN SD SAS1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 20S6 F CS 22执行连接时，对执行连接时，对S 表表只需扫描一遍，但若只需扫描一遍，但若S的元组不能整个放入的元组不能整个放入内存，则内存，则S需多少次读需多少次读入内存，对入内存，对SC表就要扫描多少遍表就要扫描多少遍.19第四章 关系系统及其查询优化SC：S#C#GS1 C1 AS1 C2 AS1 C3 AS1 C5 BS2 C1 BS2 C2 CS2 C4 CS3 C2 BS3 C3 CS3 C4 BS4 C3 BS4 C5 DS5
22、 C2 CS5 C3 BS5 C5 BS6 C4 AS6 C5 AS：S#SN SD SAS1 A CS 20S2 B CS 21S3 C MA 19S4 D CI 19S5 E MA 20S6 F CS 22 若对若对S表和表和SC表表按连接字段先排序按连接字段先排序或索引，效果如何？或索引，效果如何？对对S表和表和SC表都表都只需一遍扫描只需一遍扫描.20第四章 关系系统及其查询优化4、把投影同其前或其后的双目运算结合起来、把投影同其前或其后的双目运算结合起来 （S SC）S#，SN，C#，G 如：如：每形成一个连接后的元组，就立即取出投影字段。而不是先每形成一个连接后的元组，就立即取出投
23、影字段。而不是先连接形成一个临时关系，然后在再此临时关系上投影。连接形成一个临时关系，然后在再此临时关系上投影。又如：又如：每取出每取出S的一个元组，先取出投影字段，然后与的一个元组，先取出投影字段，然后与SC进行连接进行连接（S）S#，SN SC5、把某些选择和笛卡尔乘积结合起来成为连接运算、把某些选择和笛卡尔乘积结合起来成为连接运算6、找出公共子表达式、找出公共子表达式.21第四章 关系系统及其查询优化三、关系代数等价变换规则三、关系代数等价变换规则设设E、E1、E2是关系代数表达式。是关系代数表达式。1、关系代数表达式的等价、关系代数表达式的等价 若用相同的关系代替若用相同的关系代替E1
24、、E2中相应的关系变量后所得的中相应的关系变量后所得的结果关系相同，则称结果关系相同，则称E1、E2等价，记作等价，记作 E1 E2。2、一元运算的串接定律（幂等律）、一元运算的串接定律（幂等律）（1）投影的串接定律投影的串接定律 （E）（E）A1,A2,AnA1,A2,AnB1,B2,Bm其中其中A1,A2,An B1,B2,Bm.22第四章 关系系统及其查询优化图示：图示：B1B2B3B4A1A2A3 A1A2A3（2）选择的串接定律选择的串接定律 （E）（E）F1F2F1 F2.23第四章 关系系统及其查询优化3、二元运算的交换律、二元运算的交换律笛卡尔积：笛卡尔积：E1 E2 E2 E
25、1自然连接：自然连接：E1 E2 E2 E1连连 接：接：E1 E2 E2 E1FF4、二元运算的结合律、二元运算的结合律笛卡尔积：笛卡尔积：（E1 E2）E3 E1（E2 E3）自然连接：自然连接：（E1 E2）E3 E1 （E2 E3）自然连接：自然连接：（E1 E2）E3 E1 （E2 E3）F1F2F1F2.24第四章 关系系统及其查询优化5、两个运算间的交换律、两个运算间的交换律（1）选择和投影：）选择和投影：（E）（E）A1,A2,AnA1,A2,AnFFA1A2A3先投影后选择先投影后选择A1A2A3先选择后投影先选择后投影结果相同结果相同其中其中F只涉及只涉及A1,A2,An的
26、属性的属性.25第四章 关系系统及其查询优化若若F中有不属于中有不属于A1,A2,An的属性的属性B1,B2,Bm，则，则 （E）A1,A2,AnF无意义，无意义，但根据但根据投影的串接定律投影的串接定律和上面的和上面的投影与选择的交换律投影与选择的交换律，有：，有：（E）A1,A2,AnF （E）A1,A2,AnA1,A2,An,B1,B2,BmF （E）A1,A2,AnA1,A2,An,B1,B2,BmF（2）选择与笛卡尔积选择与笛卡尔积若若F只涉及到只涉及到E1中的属性，则中的属性，则 （E1 E2）（E1）E2FF.26第四章 关系系统及其查询优化6、一元运算对二元运算的分配律、一元运
27、算对二元运算的分配律（1）选择对笛卡尔积的分配律）选择对笛卡尔积的分配律 若若F=F1 F2，F1只涉及只涉及E1中的属性，中的属性，F2只涉及只涉及E2中的属性，中的属性，则则 （E1 E2）（E1）（E2）FF1F2如：如：（S SC）SD=CS G=A （S）（SC）SD=CSG=A笛卡尔积笛卡尔积S表表S1 A CS 20S2 B MA 21S3 C CS 19SC表表S1 C1 AS1 C2 AS2 C2 AS3 C1 BS3 C3 AS1 A CS 20 S1 C1 AS1 A CS 20 S1 C2 AS1 A CS 20 S2 C2 AS1 A CS 20 S3 C1 BS1
28、A CS 20 S3 C3 AS2 B MA 21 S1 C1 AS2 B MA 21 S1 C2 AS2 B MA 21 S2 C2 AS2 B MA 21 S3 C1 BS2 B MA 21 S3 C3 AS3 C CS 19 S1 C1 AS3 C CS 19 S1 C2 AS3 C CS 19 S2 C2 AS3 C CS 19 S3 C1 BS3 C CS 19 S3 C3 A.27第四章 关系系统及其查询优化（2）投影对笛卡尔积的分配律）投影对笛卡尔积的分配律 （E1 E2）A1,A2,An,B1,B2,Bm其中其中A1,A2,An是是E1的属性的属性,B1,B2,Bm是是E2的属
29、性。的属性。（3）选择对连接的分配律）选择对连接的分配律若若F=F1 F2，F1只涉及只涉及E1的属性，的属性，F2只涉及只涉及E2的属性，则的属性，则 （E1 E2）（E1）（E2）FF1F2F3F3 （E1）（E2）A1,A2,AnB1,B2,Bm （E1）（E2）（E1）（E2）F3F1F1F2F3F2 （E1 E2）（E1 E2）（E1 E2）FFF3F3F3F因为：因为：.28第四章 关系系统及其查询优化 （S）（SC）SN,C#,GS.S#=SC.S#S#,SNS#,C#,G（4）投影对连接的分配律）投影对连接的分配律 （E1 E2）A1,A2,An,B1,B2,BmF （E1）（
30、E2）A1,A2,AnB1,B2,BmF 其中其中F只涉及只涉及 A1,A2,An,B1,B2,Bm中的属性中的属性 若若F涉及涉及A1,A2,An,B1,B2,Bm以外的属性，可如下处理以外的属性，可如下处理 （S SC）SN,C#,GS.S#=SC.S#（S SC）SN,C#,GS.S#=SC.S#S.S#,SN,SC.S#,C#,G此处投影可去掉此处投影可去掉SC）.29第四章 关系系统及其查询优化（6）投影对并的分配律）投影对并的分配律（5）选择对并的分配律）选择对并的分配律 （E1 E2）（E1）（E2）FF F （E1 E2）A1,A2,An （E1）（E2）A1,A2,AnA1,
31、A2,An（7）选择对差的分配律）选择对差的分配律 （E1 E2）（E1）（E2）FF F.30第四章 关系系统及其查询优化四、关系代数表达式的优化四、关系代数表达式的优化1、语法树、语法树 用来表示关系代数表达式的一棵树，其内结点表示一种用来表示关系代数表达式的一棵树，其内结点表示一种运算，叶结点表示一个关系。例：运算，叶结点表示一个关系。例：SELECT S.SNFROM S,SCWHERE S.S#=SC.S#AND SC.C#=C2;可转化为如下关系运算：可转化为如下关系运算：Project(SN)(Restrict(SC.C#=C2)(Join(S.S#=SC.S#)(S，SC)Pr
32、oject(SN)Restrict（SC.C#=C2）Join（S.S#=SC.S#）SSC语法树语法树.31第四章 关系系统及其查询优化 为简化优化算法，可将关系代数运算限制在为简化优化算法，可将关系代数运算限制在“并、差、笛卡并、差、笛卡尔积、投影、选择尔积、投影、选择”五种基本运算上。五种基本运算上。Project(SN)Restrict（SC.C#=C2）Join（S.S#=SC.S#）SSC规范化为规范化为 SN SC.C#=C2 S.S#=SC.S#SSC.32第四章 关系系统及其查询优化2、关系代数表达式的优化算法、关系代数表达式的优化算法输入：一棵关系代数表达式的语法树输入：一
33、棵关系代数表达式的语法树输出：计算该表达式的程序输出：计算该表达式的程序利用选择的串接定律，把形如利用选择的串接定律，把形如 （E）的式子）的式子变换为变换为F1 F2Fn （E）F1 F2Fn 对每一个选择，利用对每一个选择，利用“选择的串接定律、选择和投影的选择的串接定律、选择和投影的交换律、选择对笛卡尔积的分配律、选择对并的分配律、交换律、选择对笛卡尔积的分配律、选择对并的分配律、选择对差的分配律选择对差的分配律”尽可能把它移到树的叶端尽可能把它移到树的叶端（1）分解选择）分解选择（2）选择下移）选择下移.33第四章 关系系统及其查询优化 对每一个投影，利用对每一个投影，利用“投影的串接
34、定律、选择和投影的投影的串接定律、选择和投影的交换律、投影对笛卡尔积的分配律、投影对并的分配律交换律、投影对笛卡尔积的分配律、投影对并的分配律”尽可能把它移到树的叶端尽可能把它移到树的叶端（3）投影下移）投影下移 利用利用“投影的串接定律、选择的串接定律、选择和投影的投影的串接定律、选择的串接定律、选择和投影的交换律交换律”把选择和投影合并成单个选择、单个投影、或选择把选择和投影合并成单个选择、单个投影、或选择后跟投影等三种情况，使多个选择和后跟投影等三种情况，使多个选择和/或投影能同时执行、或或投影能同时执行、或在一次扫描中完成在一次扫描中完成（4）选择、投影合并）选择、投影合并.34第四章
35、 关系系统及其查询优化 把上面得到的语法树分组：把上面得到的语法树分组：每个二元运算和它的每个二元运算和它的 一元直接祖先一元直接祖先 为一组。若它的后代为一组。若它的后代直到叶子全是一元运算，则也将它们并入该组。直到叶子全是一元运算，则也将它们并入该组。按照每组的求值应在其后代组求值之后进行的顺序为每组按照每组的求值应在其后代组求值之后进行的顺序为每组生成一个程序，以产生整个表达式的求值程序。生成一个程序，以产生整个表达式的求值程序。（5）按点分组（每组只有一个二元运算）按点分组（每组只有一个二元运算）（6）生成程序）生成程序不超过别的不超过别的二元运算结点二元运算结点 但对于笛卡尔积，若后
36、面（父结点）是不能与它结合为等但对于笛卡尔积，若后面（父结点）是不能与它结合为等值连接的选择运算时，其一直到叶子的一元运算结点需单独值连接的选择运算时，其一直到叶子的一元运算结点需单独算一组。算一组。.35第四章 关系系统及其查询优化例子：考虑由以下关系组成的图书馆数据库例子：考虑由以下关系组成的图书馆数据库BOOKS（TITLE，AUTHOR，PNAME，LC-NO）BORROWERS（NAME，ADDR，CITY，CARD-NO）LOANS（CARD-NO，LC-NO，DATE）借书证号借书证号图书编号图书编号查询：找出查询：找出2000年年01月月01日前借出书籍的书名和借书人姓名。日前
37、借出书籍的书名和借书人姓名。借出日期借出日期用用SQL 语言可如下表达：语言可如下表达：SELECT TITLE，NAME FROM BOOKS，BORROWERS，LOANS WHERE BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO AND DATE 2000-01-01;.36第四章 关系系统及其查询优化SELECT TITLE，NAMEFROM BOOKS，BORROWERS，LOANSWHERE BOOKS.LC-NO=LOANS.LC-NO AND BORROWERS.CARD-NO=LOANS.CARD-NO
38、 AND DATE 2000-01-01;把上述把上述SQL语句转化为关系代数表达式：语句转化为关系代数表达式：转化为投影转化为投影转化为连接转化为连接转化为选择转化为选择 （TITLE，NAMEDATE2000-01-01（BOOKS （BORROWERS LOANS）.37第四章 关系系统及其查询优化若把连接用笛卡尔积来实现，上式变为：若把连接用笛卡尔积来实现，上式变为：DATE2000-01-01 （BOOKS （BORROWERS LOANS）BOOKS.LC-NO=LOANS.LC-NO ANDBORROWERS.CARD-NO=LOANS.CARD-NO TITLE，AUTHOR，
39、PNAME，LC-NO，（NAME，ADDR，CITY，CARD-NO，DATE （TITLE，NAME.38第四章 关系系统及其查询优化 TITLE，NAMEDATE2000-01-01 上述表达式的语法树上述表达式的语法树 LOANS BOOKS.LC-NO=LOANS.LC-NO ANDBORROWERS.CARD-NO=LOANS.CARD-NO TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATE BOOKS BORROWERS根据算法第根据算法第1步，步，分解该选择分解该选择.39第四章 关系系统及其查询优化 TITLE，NAME
40、DATE2000-01-01 第第1步优化（分解选择）后的语法树步优化（分解选择）后的语法树 LOANS BOOKS.LC-NO=LOANS.LC-NO TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATE BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NO分解之后分解之后选择和投影选择和投影可以交换可以交换.40第四章 关系系统及其查询优化 TITLE，NAMEDATE2000-01-01 选择和投影交换后的语法树选择和投影交换后的语法树 LOANS BOOKS.LC-NO=LOANS.LC-NO
41、 TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATE BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NODATE2000-01-01 TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEDATE2000-01-01 根据算法第根据算法第2步，步，该选择可下移该选择可下移该选择也可下移该选择也可下移.41第四章 关系系统及其查询优化 TITLE，NAME第第2步优化（选择下移）后的语法树步优化（选择下移）后的语法树 LOANS BOOKS.LC-N
42、O=LOANS.LC-NO BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NO TITLE，AUTHOR，PNAME，LC-NO，NAME，ADDR，CITY，CARD-NO，DATEDATE2000-01-01 这两个投这两个投影可以合影可以合并（串接）并（串接）.42第四章 关系系统及其查询优化 TITLE，NAME第第4步优化（合并投影）后的语法树步优化（合并投影）后的语法树 LOANS BOOKS.LC-NO=LOANS.LC-NO BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NODATE2000
43、-01-01 该投影能否下移？该投影能否下移？不能！不能！怎么办？怎么办？.43第四章 关系系统及其查询优化 TITLE，NAME另一种形式的投影与选择交换后的语法树另一种形式的投影与选择交换后的语法树 LOANS BOOKS.LC-NO=LOANS.LC-NO BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NODATE2000-01-01 TITLE，NAME，BOOKS.LC-NO，LOANS.LC-NO该投影可下移该投影可下移.44第四章 关系系统及其查询优化 TITLE，NAME投影对笛卡尔积分配后的语法树投影对笛卡尔积分配后的语法树 LOA
44、NS BOOKS.LC-NO=LOANS.LC-NO BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NODATE2000-01-01 NAME，LOANS.LC-NO TITLE，BOOKS.LC-NO对该投影对该投影可同样可同样处理处理.45第四章 关系系统及其查询优化 TITLE，NAME第第3步优化（投影下移）后的语法树步优化（投影下移）后的语法树 LOANS BOOKS.LC-NO=LOANS.LC-NO BOOKS BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NODATE2000-01-01 NAME，LO
45、ANS.LC-NO NAME，CARD-NO LC-NO，CARD-NO TITLE，BOOKS.LC-NO.46第四章 关系系统及其查询优化 TITLE，NAME对结点分组：对结点分组：LOANS BOOKS.LC-NO=LOANS.LC-NO BORROWERS BORROWERS.CARD-NO=LOANS.CARD-NODATE2000-01-01 NAME，LOANS.LC-NO NAME，CARD-NO LC-NO，CARD-NO共分为二组共分为二组BOOKS TITLE，BOOKS.LC-NO.47第四章 关系系统及其查询优化3、优化的一般步骤、优化的一般步骤（1）把查询转换成某种内部表示）把查询转换成某种内部表示 如语法树如语法树（2）按优化算法对语法树进行优化（标准形）按优化算法对语法树进行优化（标准形）（3）选择低层的存取路径）选择低层的存取路径 充分考虑索引、数据的存储分布，然后选取存储路径充分考虑索引、数据的存储分布，然后选取存储路径（4）生成查询计划，选择代价最小的）生成查询计划，选择代价最小的 如对连接运算，考虑各种实现策略，从中选出代价最小的如对连接运算，考虑各种实现策略，从中选出代价最小的本节开头本节开头本章开头本章开头作业：作业：1、4.48
