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