本章内容提要
支持关系模型的数据库系统是关系系统 。
由于支持关系模型的程度不同,实际的数据库系统可以分为表式系统,（ 最小 ） 关系系统,关系完备的和全关系的四类系统 。
查询处理是数据库管理系统的核心,而查询优化技术又是查询处理的关键技术 。 查询优化一般可分为代数优化和物理优化 。 代数优化是指关系代数表达式的优化,物理优化则是指存取路样和低层操作算法 指示变量 的选择 。
第四章 关系系统及其查询优化本章重点：
关系系统中查询优化的概念,基本原理和技术；
查询优化的一般准则；
查询优化的一般步骤 。
本章难点：
查询优化的一般准则；
查询优化的一般步骤 。
第四章 关系系统及其查询优化
关系模型的三要素：关系数据结构关系操作关系的完整性
关系系统和关系模型是两个密切相关而又不同的概念。支持关系模型的数据库管理系统称为关系系统。但是 关系模型中并非每一部分都是同等重要 的，所以我们不苛求完全支持关系模型的系统才能称为关系系统。因此，
我们给出一个关系系统的最小要求以及分类的定义。
第四章 关系系统及其查询优化
4.1 关系系统
4.1.1 关系系统的定义一个系统可定义为关系系统，当且仅当它：
1.支持关系关系数据库（关系数据结构）；
2.支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径。
系统要进行查询优化，以获得较好的性能。这正是关系系统实施的关键技术。
第四章 关系系统及其查询优化
4.1 关系系统
4.1.2 关系系统的分类
4.1.1定义的关系系统是关系系统的最小要求，许多实际系统都不同程度地超过了这些要求。
按照 E.F.Codd的思想，可以把关系系统分类分为四类：
1,表式系统
2,(最小）关系系统
3,关系完备的系统
4,全关系系统第四章 关系系统及其查询优化 4.1
关系系统
4.1.3 全关系系统的十二条基本准则
准则 0 一个关系型的 DBMS必须能完全通过它的关系能力来管理数据库。 ——准则 0是下面十二条准则的基础。
准则 1 信息准则。
准则 2 保证访问准则。依靠表名、主码和列名的组合，
保证能以逻辑方式访问关系数据库中的每个数据项
(分量值 )。
准则 3 空值的系统化处理。
准则 4 基于关系模型的动态的联机数据字典。
准则 5 统一的数据子语言准则。
第四章 关系系统及其查询优化 4.1
关系系统第四章 关系系统及其查询优化
4.1 关系系统
4.1.3 全关系系统的十二条基本准则
准则 6 视图更新准则。
准则 7 高级的插入、修改和删除操作。
准则 8 数据物理独立性。
准则 9 数据逻辑独立性。
准则 l0 数据完整性的独立性。
准则 11 分布独立性。
准则 12 无破坏准则
4.2.1 关系系统及其查询优化
查询优化在关系数据库中有非常重要的地位。
关系数据库系统和非过程化的 SQL语言能够成功，关键是得益于查询优化的发展。
关系系统的查询优化既是 RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出‘干什么’，不必指出‘怎么干’。
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。
第四章 关系系统及其查询优化 4.2
关系数据库系统的查询优化
关系数据库查询优化的总目标是：选择有效的 策略,
求得给定关系表达式的值。
实际系统对查询优化的具体实现一般可以归纳为四个步骤：
1、将查询转换成某种内部表示，通常是 语法树 。
2、根据一定的 等价变换规则 把语法树转换成标准
（优化）形式。
3、选择低层的操作算法。
4、生成查询计划（ 查询执行方案 ）。
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
查询优化有两种基本策略：基于语法的查询优化（结构优化）
基于代价的查询优化。
基于代价 的优化算法：
在集中式数据库中，查询的执行开销主要包括：
总代价 = I/O代价 + CPU代价在多用户环境下：
总代价 = I/O代价 + CPU代价 + 内存代价
4.2.2 一个实例 （ P159-161）
一个简单的例子,说明为什么要进行查询优化 。
例 求选修了 2号课程的学生姓名 。 用 SQL语言表达：
SELECT Student.Sname
FROM Student,SC
WHERE Student.Sno = SC.Sno AND SC.Cno = '2'；
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
4.2.3 查询优化的一般准则下面的优化策略一般能提高查询效率,但不一定是所有策略中最优的。其实‘优化’一词并不确切，也许‘改进’或‘改善’更恰当些。
l,选择运算应尽可能先做。
2.在执行连接前对关系适当地预处理。
3.把投影运算和选择运算同时进行。
4.把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。
5.杷某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
6.找出公共子表达式。
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
关系代数表达式的优化是查询优化的基本课题。
两个关系表达式的等价
常用的等价变换规则有：
l,连接、笛卡尔积交换律
2.连接、笛卡尔积的结合律
3.投影的串接定律
4.选择的串接定律
5.选择与投影的交换律
6.选择与笛卡尔积的交换律
7.选择与并的交换
8.选择与差运算的交换
9.投影与笛卡尔积的交换
l0.投影与并的交换第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
4.2.5 关系代数表达式的优化算法
可以应用上面的变换法则来优化关系表达式，使优化后的表达式能遵循
4.2.3中的一般原则。
关系表达式的优化算法：关系表达式的优化。
输入：一个关系表达式的语法树。
输出：计算该表达式的程序。
方法：
1,利用规则 (4)把形如 F1∧ F2...∧ Fn(E)变换为 F1( F2(...( Fn(E))...))
2,对每一个选择，利用规则 (4)—（ 8）尽可能把它移到树的叶端。
3,对每一个投影利用规则 (3),(9),(l0),(5)中的一般形式尽可能把它移向树的叶端。
4,利用规则 (3)～ (5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。
5,把上述得到的语法树的内节点分组。
6,生成一个程序，每组结点的计算是程序中的一步。
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
4.2.6 优化的一般步骤
各个关系系统的优化方法不尽相同,大致的步骤可以归纳如下,
l,把查询转换成某种内部表示
2,把语法树转换成标淮 (优化 )形式
3,选择低层的存取路径
4,生成查询计划，选择代价最小的第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化例：查询优化语法树：
Select sname from student,sc
where student.sno =s.sno and cno =‘2’;
第四章 关系系统及其查询优化小结：
关系系统的定义 。
关系模型的分类：可以分为表式系统,（ 最小 ） 关系系统,关系完备的和全关系的四类系统 。
查询处理是数据库管理系统的核心,而查询优化技术又是查询处理的关键技术 。 查询优化有两种基本策略：基于语法的查询优化 （ 结构优化 ） 和基于代价的查询优化 。
支持关系模型的数据库系统是关系系统 。
由于支持关系模型的程度不同,实际的数据库系统可以分为表式系统,（ 最小 ） 关系系统,关系完备的和全关系的四类系统 。
查询处理是数据库管理系统的核心,而查询优化技术又是查询处理的关键技术 。 查询优化一般可分为代数优化和物理优化 。 代数优化是指关系代数表达式的优化,物理优化则是指存取路样和低层操作算法 指示变量 的选择 。
第四章 关系系统及其查询优化本章重点：
关系系统中查询优化的概念,基本原理和技术；
查询优化的一般准则；
查询优化的一般步骤 。
本章难点：
查询优化的一般准则；
查询优化的一般步骤 。
第四章 关系系统及其查询优化
关系模型的三要素：关系数据结构关系操作关系的完整性
关系系统和关系模型是两个密切相关而又不同的概念。支持关系模型的数据库管理系统称为关系系统。但是 关系模型中并非每一部分都是同等重要 的，所以我们不苛求完全支持关系模型的系统才能称为关系系统。因此，
我们给出一个关系系统的最小要求以及分类的定义。
第四章 关系系统及其查询优化
4.1 关系系统
4.1.1 关系系统的定义一个系统可定义为关系系统，当且仅当它：
1.支持关系关系数据库（关系数据结构）；
2.支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径。
系统要进行查询优化，以获得较好的性能。这正是关系系统实施的关键技术。
第四章 关系系统及其查询优化
4.1 关系系统
4.1.2 关系系统的分类
4.1.1定义的关系系统是关系系统的最小要求，许多实际系统都不同程度地超过了这些要求。
按照 E.F.Codd的思想，可以把关系系统分类分为四类：
1,表式系统
2,(最小）关系系统
3,关系完备的系统
4,全关系系统第四章 关系系统及其查询优化 4.1
关系系统
4.1.3 全关系系统的十二条基本准则
准则 0 一个关系型的 DBMS必须能完全通过它的关系能力来管理数据库。 ——准则 0是下面十二条准则的基础。
准则 1 信息准则。
准则 2 保证访问准则。依靠表名、主码和列名的组合，
保证能以逻辑方式访问关系数据库中的每个数据项
(分量值 )。
准则 3 空值的系统化处理。
准则 4 基于关系模型的动态的联机数据字典。
准则 5 统一的数据子语言准则。
第四章 关系系统及其查询优化 4.1
关系系统第四章 关系系统及其查询优化
4.1 关系系统
4.1.3 全关系系统的十二条基本准则
准则 6 视图更新准则。
准则 7 高级的插入、修改和删除操作。
准则 8 数据物理独立性。
准则 9 数据逻辑独立性。
准则 l0 数据完整性的独立性。
准则 11 分布独立性。
准则 12 无破坏准则
4.2.1 关系系统及其查询优化
查询优化在关系数据库中有非常重要的地位。
关系数据库系统和非过程化的 SQL语言能够成功，关键是得益于查询优化的发展。
关系系统的查询优化既是 RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出‘干什么’，不必指出‘怎么干’。
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。
第四章 关系系统及其查询优化 4.2
关系数据库系统的查询优化
关系数据库查询优化的总目标是：选择有效的 策略,
求得给定关系表达式的值。
实际系统对查询优化的具体实现一般可以归纳为四个步骤：
1、将查询转换成某种内部表示，通常是 语法树 。
2、根据一定的 等价变换规则 把语法树转换成标准
（优化）形式。
3、选择低层的操作算法。
4、生成查询计划（ 查询执行方案 ）。
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
查询优化有两种基本策略：基于语法的查询优化（结构优化）
基于代价的查询优化。
基于代价 的优化算法：
在集中式数据库中，查询的执行开销主要包括：
总代价 = I/O代价 + CPU代价在多用户环境下：
总代价 = I/O代价 + CPU代价 + 内存代价
4.2.2 一个实例 （ P159-161）
一个简单的例子,说明为什么要进行查询优化 。
例 求选修了 2号课程的学生姓名 。 用 SQL语言表达：
SELECT Student.Sname
FROM Student,SC
WHERE Student.Sno = SC.Sno AND SC.Cno = '2'；
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
4.2.3 查询优化的一般准则下面的优化策略一般能提高查询效率,但不一定是所有策略中最优的。其实‘优化’一词并不确切，也许‘改进’或‘改善’更恰当些。
l,选择运算应尽可能先做。
2.在执行连接前对关系适当地预处理。
3.把投影运算和选择运算同时进行。
4.把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。
5.杷某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。
6.找出公共子表达式。
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
关系代数表达式的优化是查询优化的基本课题。
两个关系表达式的等价
常用的等价变换规则有：
l,连接、笛卡尔积交换律
2.连接、笛卡尔积的结合律
3.投影的串接定律
4.选择的串接定律
5.选择与投影的交换律
6.选择与笛卡尔积的交换律
7.选择与并的交换
8.选择与差运算的交换
9.投影与笛卡尔积的交换
l0.投影与并的交换第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
4.2.5 关系代数表达式的优化算法
可以应用上面的变换法则来优化关系表达式，使优化后的表达式能遵循
4.2.3中的一般原则。
关系表达式的优化算法：关系表达式的优化。
输入：一个关系表达式的语法树。
输出：计算该表达式的程序。
方法：
1,利用规则 (4)把形如 F1∧ F2...∧ Fn(E)变换为 F1( F2(...( Fn(E))...))
2,对每一个选择，利用规则 (4)—（ 8）尽可能把它移到树的叶端。
3,对每一个投影利用规则 (3),(9),(l0),(5)中的一般形式尽可能把它移向树的叶端。
4,利用规则 (3)～ (5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。
5,把上述得到的语法树的内节点分组。
6,生成一个程序，每组结点的计算是程序中的一步。
第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化
4.2.6 优化的一般步骤
各个关系系统的优化方法不尽相同,大致的步骤可以归纳如下,
l,把查询转换成某种内部表示
2,把语法树转换成标淮 (优化 )形式
3,选择低层的存取路径
4,生成查询计划，选择代价最小的第四章 关系系统及其查询优化
4.2 关系数据库系统的查询优化例：查询优化语法树：
Select sname from student,sc
where student.sno =s.sno and cno =‘2’;
第四章 关系系统及其查询优化小结：
关系系统的定义 。
关系模型的分类：可以分为表式系统,（ 最小 ） 关系系统,关系完备的和全关系的四类系统 。
查询处理是数据库管理系统的核心,而查询优化技术又是查询处理的关键技术 。 查询优化有两种基本策略：基于语法的查询优化 （ 结构优化 ） 和基于代价的查询优化 。
