第3章 关系数据库的基本理论 冯万利

本章重要概念 (1) 基本概念 关系数据模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，ER模型到关系模型的转换规则，过程性语言与非过程性语言。 (2 ) 关系代数 五个基本操作，四个组合操作，七个扩充操作。 (3) 关系代数表达式的优化 关系代数表达式的等价及等价转换规则，启化式优化算法。

主要内容 3.1关系数据模型 3.2关系模型的完整性规则 3.3关系代数的基本运算 *3.4关系演算 3.5 查询优化 3.1.1 关系模式 3.1.2 关系操作 3.2关系模型的完整性规则 3.2.1 关系的三类完整性约束 3.2.2 实体完整性 3.2.3 参照完整性 3.2.4 用户自定义完整性 3.3关系代数的基本运算 3.3.1 传统的集合运算 3.3.2 专门的关系运算 3.3.3 关系代数表达式及其应用实例 *3.4关系演算 元组关系演算 域关系演算 3.5 查询优化 3.5.1 查询优化的一般策略 3.5.2 代数表达式的等价变换规则 3.5.3 优化算法

3.1关系数据模型

3.1.1 关系模式 每个关系都有一个模式，称为关系模式(Relation Schema)，由一个关系名及它的所有属性名构成。 在关系模式中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图3.1中： 关系模式名是R 记录称为元组（tuple） 元组的集合称为关系（relation）或实例（instance） 一般用前面的大写英语字母A、B、C、…表示单个属性，用后面的大写字母…、W、X、Y、Z表示属性集，用小写字母表示属性值。

数据库技术的术语 关系模型的术语 A B C D E a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b3 c3 d3 数据库技术的术语 关系模型的术语 数据库技术的术语 关系模型的术语 字段,数据项 属性 记录类型 关系模式 记录1 元组1 记录2 元组2 记录3 元组3 字段值 属性值 文件 关系（或实例） A B C D E a1 b1 c1 d1 e1 a2 b2 c2 d2 e2 a3 b3 c3 d3 e3

关系具有的特点 ⑴ 关系（表）可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。 ⑵ 表中一行称为一个元组，可用来表示实体集中的一个实体。 ⑶ 表中的列称为属性，给每一列起一个名称即属性名，表中的属性名不能相同。 ⑷ 列的取值范围称为域，同列具有相同的域，不同的列可有相同的域。 例如，SEX的取值范围是{M（男），F（女）}，AGE为整数域。 ⑸ 表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为主键。

关系的性质 属性值是原子的，不可分解。 没有重复元组。 没有行序。 理论上没有列序，但一般使用时都有列序。

关键码和表之间的联系 超键：在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。 候选键：如果一个属性集能惟一标识元组，且又不含有多余的属性，那么这个属性集称为关系的候选键。 主键：若一个关系中有多个候选键，则选其中的一个为关系的主键。 外键：若一个关系R中包含有另一个关系S的主键所对应的属性组F，则称F为R的外键。并称关系S为参照关系，关系R为依赖关系。

关系模式举例 例如，学生关系和系部关系分别为： 学生关系的主键是SNO，系部关系的主键为SDNO，在学生关系中，SDNO是它的外键。 学生（SNO，SNAME，SEX，AGE，SDNO） 系部（SDNO，SDNAME，CHAIR） 学生关系的主键是SNO，系部关系的主键为SDNO，在学生关系中，SDNO是它的外键。 更确切地说，SDNO是系部表的主键，将它作为外键放在学生表中，实现两个表之间的联系。 在关系数据库中，表与表之间的联系就是通过公共属性实现的。 我们约定，在主键的属性下面加下划线，在外键的属性下面加波浪线。

关系模式、关系子模式和存储模式 关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的集合。具体的关系称为实例。 例3.1 下图是一个教学模型的实体联系图。实体类型“学生”的属性SNO、SNAME、SEX、AGE、SDEPT分别表示学生的学号、姓名、性别、年龄和学生所在系部；实体类型“课程”的属性CNO、CNAME、CDEPT、TNAME分别表示课程号、课程名、课程所属系和任课教师。学生用S表示，课程用C表示。S和C之间有M:N的联系（一个学生可选多门课程，一门课程可以被多个学生选修），联系类型SC的属性成绩用GRADE表示。右图表示的实体联系图（ER图）。 SNO SNAME AGE SEX SDEPT S C CNO CNAME CDEPTE TNAME SC M N GRADE

关系模式 S1 程晓晴 F 21 CS S2 姜 云 20 IS S3 李小刚 M 该图表示的学生情况的部分转换成相应的关系模式为： S(SNO,SNAME,SEX,AGE,SDPET)关系模式S描述了学生的数据结构，它是下表中学生实体的关系模式。其中SNO，CNO为关系SC的主键，SNO、CNO又分别为关系SC的两个外键。 SNO CNO GRADE S1 C1 87 C2 78 C3 90 S2 67 79 56 S3 80 76 92 学生关系模式 S(SNO，SNAME，SEX，AGE，SDPET) 选修关系模式 SC( SNO，CNO，GRADE) 课程关系模式 C(CNO，CNAME，CDEPT，TNAME) 学生关系实例如下表；选修关系实例如右表。 SNO SNAME SEX AGE SDEPT S1 程晓晴 F 21 CS S2 姜 云 20 IS S3 李小刚 M

关系模式(9) CNO CNAME CDEPT TNAME C1 高等数学 IS 王红卫 C2 数据库原理 CS 李绍丽 C3 数据结构 课程关系实例如下表： CNO CNAME CDEPT TNAME C1 高等数学 IS 王红卫 C2 数据库原理 CS 李绍丽 C3 数据结构 刘 良

关系子模式 用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件的数据构成关系子模式。关系子模式是用户所需数据结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。 例3.2 用户需要用到成绩子模式G(SNO,SNAME,CNO,GRADE)。子模式G对应的数据来源于表S和表SC，构造时应满足它们的SNO值相等。子模式G的构造过程如下图所示。

关系子模式 SNO SNAME CNO GRADE S1 程晓晴 C1 87 S2 姜 云 67 … SNO SNAME SEX AGE 姜 云 67 … SNO SNAME SEX AGE SDEPT S1 程晓晴 F 21 CS S2 姜 云 20 IS … SNO CNO GRADE S1 C1 87 S2 67 … 一 一对应

存储模式 描述关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少（100以内），那么也可以用堆文件方式实现。此外，还可以对任意的属性集建立辅助索引。

3.1.2 关系操作 关系模型中常用的关系操作包括查询（Query）操作和插入（Insert）、删除（Delete）、修改（Update）操作。 查询操作又可以分为：选择（Select）、投影（Project）、连接（Join）、除（Divide）、并（Union）、差（Except）、交（Intersection）、笛卡尔积等。 基本操作：选择、投影、并、差、笛卡尔积。 其他操作：可以用基本操作来定义和导出的。 关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称称为一次一集合（set-at-a-time）的方式。相应地，非关系数据模型的数据操作方式则为一次一纪录（record-at-a-time）的方式。

关系数据语言的分类 关系数据语言分为三类：关系代数、元组关系演算和域关系演算。该三种语言在表达能力上是完全等价的。 关系代数语言 例如 ISBL 元组关系演算语言 例如 APLHA，QUEL 关系数据语言 关系演算语言 域关系演算语言 例如 QBE 具有关系代数和关系演算双重特点的语言 例如 SQL 关系语言是一种高度非过程化的语言，用户不必请求DBA为其建立特殊的存取路径，存取路径的选择由RDBMS的优化机制来完成。

3.2 关系模型的完整性规则

主要内容 3.2.1 关系的三类完整性约束 3.2.2 实体完整性 3.2.3 参照完整性 3.2.4 用户定义完整性

关系模型的完整性规则 关系模型中有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。 实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。 用户定义的完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束。

3.2.1 关系的三类完整性约束 规则3.1 实体完整性（Entity Integrity）规则：若属性（指一个或一组属性）A是基本关系R的主属性。则A不能取空值。 例如: 在关系S(SNO,SNAME,SEX,AGE,SDPET)中，SNO这个属性为主码，则SNO不能取空值。 实体完整性要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标织元组的作用。

对于实体完整性规则几点说明 ⑴ 实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。 ⑵ 现实世界中的实体是可区分的，即它们具有某种唯一性标识。例如每个学生都是独立的个体，是不一样的。 ⑶ 关系模型中以主码作为唯一性标识。 ⑷ 主码中的属性即主属性不能取空值。如果主属性取空值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与第⑵点相矛盾，因此这个规则称为实体完整性。

参照完整性规则 定义2.3 参照完整性规则的形式定义如下： 如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。 这条规则的实质是“不允许引用不存在的实体”。 在上述形式定义中，关系模式R1的关系称为“参照关系”，关系模式R2的关系称为“依赖关系”。 由参照完整性建立了多表之间的对应关系

参照完整性规则举例 例2.1 下面各种情况说明了参照完整性规则在关系中如何实现的。 ① 在关系数据库中有下列两个关系模式： S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） 据规则要求，关系SC中的S# 值应该在关系S中出现。如果关系SC中有一个元组（S7,C4,80），而学号S7却在关系S中找不到，那么我们就认为在关系SC中引用了一个不存在的学生实体，这就违反了参照完整性规则。 另外，在关系SC中S#不仅是外键，也是主键的一部分，因此这里S# 值不允许空。

参照完整性规则举例 ② 设工厂数据库中有两个关系模式： DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D# ) 车间模式DEPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D#不在主键中，因此D# 值允许空。

参照完整性规则举例 ③ 设课程之间有先修、后继联系。模式如下： R(C# ，CNAME，PC# ) 其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。

用户定义的完整性规则 在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在15～30岁之间： CHECK（AGE BETWEEN 15 AND 30）

3.3 关系代数的基本运算

主要内容 传统的集合运算 专门的关系运算 关系代数表达式及其应用实例

传统的集合运算 并（Union） 差（Difference） 设关系R和S具有相同的关系模式，R和S的并是由属于R或属于S的元组构成的集合，记为R∪S。形式定义如下： R∪S≡{t | t∈R ∨ t∈S}，t是元组变量，R和S的元数相同。 差（Difference） 设关系R和S具有相同的关系模式，R和S的差是由属于R但不属于S的元组构成的集合，记为R－S。形式定义如下： R－S≡{ t | t∈R ∧ t∈S}，R和S的元数相同。

举例 关系运算举例

交运算 交（intersection） 关系R和S的交是由属于R又属于S的元组构成的集合，记为R∩S，这里要求R和S定义在相同的关系模式上。形式定义如下： R∩S≡{t︱t∈R ∧ t∈S}，R和S的元数相同。 例 A B C a1 a2 b1 b2 c1 c2 A B C a1 a2 b2 b3 c2 c1 b B C a1 a2 b2 b2 c2 c1 S R ∩S R

笛卡儿积运算 笛卡儿积(Cartesian Product) 设关系R和S的元数分别为r和s,定义R和S的一个(r+s)元的元组集合，每个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组，记为R×S。 R×S ≡{t|t=<tr,ts>∧tr∈R∧ts∈S} 若R有m个元组，S有n个元组，则R×S有m×n个元组。

专门的关系运算 选择（Selection） 选择操作是根据某些条件对关系做水平分割，即选取符合条件的元组。条件可用命题公式（即计算机语言中的条件表达式）F表示。 F中的基本形式为：X1θY1： 其中θ表示比较运算符:＞，≥，＜，≤，＝，＜＞。 X1，Y1等是属性名，常量，或列序号。 关系R关于公式F的选择操作用σF（R）表示，形式定义为：σF（R）＝{ t | t∈R ∧ F（t）= true } σ为选择运算符，σF（R）表示从R中挑选满足公式F为真的元组所构成的关系。 例如，σ2＞ˊ3ˊ（R）表示从R中挑选第2个分量值大于3的 元组所构成的关系。书写时，为了与属性序号区别起见，常量用引号括起来，而属性序号或属性名不要用引号括起来。

投影（Projection) 这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列的顺序。 设关系R是k元关系，R在其分量Ai1，…，Aim（m≤k i1，…，im ，为1到k间的整数）上的投影用πi1,...,im（R）表示，它是一个m元元组集合，形式定义为：πi1，…，im（R）≡{ t | t＝〈ti1，…，tim〉∧〈t1，…，tk〉∈R } 例如，π3，1（R）表示关系R中取第1、3列，组成新的关系，新关系中第1列为R的第3列，新关系的第2列为R的第1列。如果R的每列标上属性名，那么操作符π的下标处也可以用属性名表示。例如，关系R（A，B，C），那么πC，A（R）与π3，1（R）是等价的。

连接（join）运算 连接有两种：θ连接和F连接（这里θ是算术比较符，F是公式）。 ① θ连接 ② F连接 R ⋈ S≡{t︱ t=<tr，ts> ∧ tr∈R ∧ ts∈S ∧ } 表达式 表示元组tr的第i个分量、元组ts的第j个分量满足θ操作。 ② F连接 F连接是从关系R和S的笛卡儿积中选取属性间满足某一公式F的元组, 这里F是形为F1∧F2∧…∧Fn的公式，每个FP是形iθj的式子，而i和j分别为关系R和S的第i、第j个分量的序号。 iθj

连接运算举例 例 θ连接和F连接的例子. 说明: 1. 也可以写成 。 ≡σ2＜4（R×S) 2. 。

自然连接（natural join） 两个关系R和S的自然连接 操作具体计算过程如下： 定义： ②设R和S的公共属性是A1,…,AK，挑选R×S中满足R.A1=S.A1，…，R.AK=S.AK的那些元组； ③去掉S.A1，…，S.AK这些列。 定义： 中i1,…,im为R和S的全部属性，但公共属性只出现一次。 ≡

连接运算举例 B E b1b2b3b3b5 3 7 102 2 A B C a1a1a2a2 b1b2b3b4 5 6 8 12 A R.B 关系S 等值连接 R S R.C<S.B 一般连接 R S C<E B E b1b2b3b3b5 3 7 102 2 A B C a1a1a2a2 b1b2b3b4 5 6 8 12 A R.B C S.B E a1a1a1a1a2 b1 b1 b2 b2 b3 55668 b2 b3 b2 b3 b3 7 10 7 10 10 A R.B C S.B E a1 a2 b1 b2 b3 5 6 8 3 7 10 2 自然连接 R S A B C E a1 a2 b1 b2 b3 5 6 8 3 7 10 2

专门的关系运算 两个关系R和S在做自然连接时，选择两个关系在公共属性上值相等的元组构成新的关系。此时，关系R中某些元组有可能在S中不存在公共属性上值相等的元组，从而造成R中这些元组在操作时被舍弃了，同样，S中某些元组也可能被舍弃。 如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值（Null），那么这种连接就叫做外连接(Outer join)。如果只把左边关系R中要舍弃的元组保留就叫做左外连接（Left outer join或Left join），如果只把右边关系S中要舍弃的元组保留就叫做右外连接（Right outer join或Right join）。

外连接的例子 关系R 关系S 左外连接 右外连接 A B C a1a1a2a2 b1b2b3b4 5 6 8 12 A B C E a1 NULL b1 b2 b3 b5 5 6 8 3 7 10 2 B E b1b2b3b3b5 3 7 102 2 A B C E a1 a2 b1 b2 b3 b4 5 6 8 12 3 7 10 2 NULL 外连接 A B C E a1 a2 NULL b1 b2 b3 b4 b5 5 6 8 12 3 7 10 2

除法（division） 设关系R和S的元数分别为r和s（设r>s>0），那么R÷S是一个（r-s）元的元组的集合。（R÷S）是满足下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组<t，u>必在关系R中。 R÷S≡π1,2,…,r-s（R）- π1,2,…,r-s ((π1,2,…,r-s(R)×S)-R)

除法举例

关系代数运算的应用实例(1) πS#,GRADE(σC#=‘C2’ (SC)) (2) 检索学习课程号为C2的学生的学号与姓名。 在关系代数运算中，把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。 例2.7 设教学数据库中有三个关系： 学生关系 S(S#,SNAME,AGE,SEX) 选课关系 SC(S#,C#,GRADE) 课程关系 C(C#,CNAME,TEACHER) 用关系代数表达式表示查询语句。 (1) 检索学习课程号为C2的学生学号与成绩。 πS#,GRADE(σC#=‘C2’ (SC)) (2) 检索学习课程号为C2的学生的学号与姓名。 πS#,SNAME(σC#=‘C2’ (S ⋈ SC)) (3) 检索选修课程名为MATHS的学生学号与姓名。 πS#,SNAME(σCNAME=‘MATHS’ (S ⋈ SC ⋈ C))

关系代数运算的应用实例(2) πS#,C# (SC) ÷πC# (C) (4) 检索选修课程号为C2或C4的学生学号。 πS#(σC#=‘C2’ ∨C#=‘C4’(SC)) (5) 检索至少选修课程号为C2和C4的学生学号。 π1(σ1=4∧2=‘C2’ ∧5=‘C4’ (SC×SC)) (6)检索不学C2课的学生姓名与年龄。 πSNAME,AGE ( S)-πSNAME,AGE (σC#=‘C2’ (S ⋈ SC)) (7) 检索学习全部课程的学生姓名。 ① 学生选课情况可用操作πS#,C#(SC); ② 全部课程可用操作πC#(C)表示; ③ 学了全部课程的学生学号可用除法操作表示,操作结果是学号S#集; πS#,C# (SC) ÷πC# (C) ④ 从S#求学生姓名SNAME,可以用自然连接和投影操作组合而成: πSNAME(S ⋈ (πS#,C# (SC) ÷πC# (C)) (8)检索所学课程包含学生S3所学课程的学生学号。 ① 学生选课情况可用操作πS#,C# (SC)表示; ② 学生S3所学课程可用操作πC#(σS#=‘S3’(SC))表示; ③ 所学课程包含学生S3所学课程的学生学号,可以用除法操作求得: πS#,C# (SC) ÷ πC#(σS#=‘S3’(SC)) S(S#,SNAME,AGE,SEX) SC(S#,C#,GRADE) C(C#,CNAME,TEACHER)

关系代数运算的应用实例(3) 一般地有下列规律： π(σ(R×S)) 或者π(σ(R S)) (1) 对于只涉及到选择、投影、连接的查询可用下列表达式表示： π(σ(R×S)) 或者π(σ(R S)) (2) 对于否定的操作，一般要用差操作表示，例如“检索不学C2课的学生姓名”。用下列表达式表示： πSNAME(S)-πSNAME(σCNO='C2'(S SC))但不能用下式表示： πSNAME(σCNO≠'C2'(S SC)) ⑶ 对于检索具有“全部”特征的操作，一般要用除法操作表示，例如“检索学习全部课程的学生学号”。用下列表达式表示： 要用πSNO,CNO(SC)÷πCNO(C)表示，而不能写成 πSNO (SC÷πCNO(C))形式。 这是因为一个学生学的课程的成绩可能是不一样的。

3.5 查询优化

主要内容 查询优化的一般策略 代数表达式的等价变换规则 优化算法

查询优化例子 例 设关系R和S都是二元关系，属性名分别为A，B和C，D。 设有一个查询可用关系代数表达式表示： E1=πA（σB=C∧D=‘99’（R×S））） 也可以把选择条件D=‘99’移到笛卡儿积中的关系S前面： E2=πA（σB=C（R×σD=‘99’（S））） 还可以把选择条件B＝C与笛卡儿积结合成等值连接形式： E3=πA（R σD='99'（S）） 这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大部分时间是花在连接操作上的。 可以分析出，在时空性能上，E3最优，其次是E2，最后是E1。此例还可以看出，如何安排选择、投影和连接的顺序是个很重要的问题。

查询优化的一般策略 (1) 在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。 查询优化是实现关系系统的关键技术,它大大减轻了用户选择存取路径的负担,用户使用关系系统时,只要提出“做什么”,不必指出“怎么做”。 在关系代数运算中，笛卡儿积和连接运算是最费时间的。

查询优化的一般策略 (2) 查询优化采用的一般策略是： ⑴ 尽可能早地执行选择运算。在查询中这种变换最为重要，因为它可以以元组为单位减小中间结果，从而使执行时间成数量级地减少。 ⑵ 把先做笛卡儿积，后做选择结合起来。使之成为一个连接运算。连接运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿积R×S的结果再做选择时，并且这个选择是对R和S的属性进行比较，在这样的条件下，这个笛卡儿积和选择运算等价于一个连接。 一般对不含R的属性或不含S的属性的比较，可以移到笛卡儿积运算前去做，这样做比转换到连接更好。 ⑶ 同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文件，从而节省了操作时间。 ⑷ 找出表达式里的公共子表达式。如果公共子表达式的结果不是很大，并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个公共子表达式是有好处的。 子表达式内涉及到连接，但又不能把限定条件向内移入的那类表达式，一般属于这一类。

代数表达式的等价变换规则 (1) 连接和笛卡儿积的交换律 E1 E2≡E2 E1 E1 E2≡ E2 E1 E1×E2 ≡ E1×E2 连接和笛卡儿积的结合律 (E1 E2） E3≡E1 (E2 E3) (E1 E2) E3≡E1 (E2 E3) (E1×E2)×E3 ≡ E1×(E2×E3) 投影的串接 设L1,设L2,…,Ln为属性集，并且 ,那么下式也成立. 选择的串接

代数表达式的等价变换规则 (2) 选择和投影操作的交换 选择对笛卡儿积的分配律 这里要求F只涉及到E1中的属性。 如果F形为F1∧F2，且F1只涉及到E1的属性，F2只涉及到E2的属性，则有 此外，如果F形为F1∧F2，且F1只涉及到E1的属性，F2只涉及到E1和E2的属性，则有：

代数表达式的等价变换规则(3) 选择对并的分配律 E1和E2具有相同的属性名，或者E1和E2表达的关系的属性有对应性，则有： 选择对集合差的分配律 E1和E2的属性有对应性，则有： 选择对自然联接的分配律 F只涉及到表达式E1和E2的公共属性，则有： （E1 E2）≡ （E1） （E2） 投影对笛卡尔的分配律 L1是E1中的属性集，L2是E2中的属性集，则有： 投影对并的分配律 E1和E2的属性有对应性，则有：

代数表达式的等价变换规则 (4) 选择与联接操作的结合 （E1×E2）≡E1 E2 （E1 E2）≡E1 E2 并和交的交换律 并和交的结合律 （E1∪E2）∪E3≡E1∪（E2∪E3） （E1∩E2）∩E3≡E1∩（E2∩E3）

优化算法 (1) 代数优化是利用上面的等价变换规则，对关系表达式进行优化，以减少执行时的开销。虽然不能保证最优，但在多数情况下能使表达式更好些。在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。 优先应用单项的选择和投影； 优先应用一般选择和投影； 对笛卡儿积、并运算、差运算，若它们前面加有选择和投影，则先做选择和投影。

优化算法 (2) 方法： 算法：关系代数表达式的优化。 输入：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列 ⑴ 把 ⑵ 对每个选择，尽可能地将选择向树的叶端移动。 ⑶ 对每个投影，尽可能地向树的叶端移动。 说明：过程中可能使某些投影操作消失；也可能把一个投影分成两个，其中一个将 靠近叶端；也可能消去该投影操作。 ⑷ 把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。 ⑸ 将上述步骤得到的语法树的内结点分组。 ⑹产生一个程序，上述每一组是这程序的一步，且先执行后代结点组。

优化算法(3) 例3.14 对于如下关系数据库： S（S#，SNAME，AGE，SEX） SC（S#，C#，GRADE） C（C#，CNAME，TEACHER） 现有一个查询语句：检索至少学习LIU老师所授一门课程的女生的学号和姓名。该查询语句的关系代数表达式如下： SC S)) 也可以得下式: L π σ × C SC S TEACHER=‘LIU’∧SEX=‘F’ C.C#,CNAME,TEACHER,S.S# GRADE,SNAME,AGE,SEX C.C#=SC.C#∧SC.S#=S.S# S.S#,SNAME 语法树

优化算法(4) π σ (1)将每个选择操作分裂成两个选择运算: (2)将四个选择操作尽可能向树的叶端靠拢， 并把两个投影合并为一个投影。 × C SC S.S#，SNAME SC.S#=S.S# C.C#=SC.C# SEX=‘F’ TEACHER=‘LIU’ S (2)将四个选择操作尽可能向树的叶端靠拢， 并把两个投影合并为一个投影。 见图 2.23 (3)把投影和选择进行交换，并在σ前增加一个投影操作。 过程中的语法树 新增加的投影

优化算法(5) π π σ × SC × σ S C S.S#，SNAME SC.S#=S.S# SC.S#,S.S#,SNAME 做投影 C.C#=SC.C# TEACHER=‘LIU’ π S.S#，SNAME SC.S#,S.S#,SNAME SC.S#=S.S# π × SEX=‘F’ σ 做投影 做投影 S C 再把该投影往叶端移

优化算法(6) (4) 执行时从叶端以次向上进行，每组运算只对关系一次扫描。 π × π σ SC C 优化的语法树及其分组 SC.S# S.S#，SNAME S TEACHER=‘LIU’ SC SC.S#,SC.C# (4) 执行时从叶端以次向上进行，每组运算只对关系一次扫描。 SC.S#=S.S# π S.S#,SNAME’ SEX=‘F’ C.C#=SC.C# 优化的语法树及其分组