SQLServer第3章关系数据库的基本理论课件

1、2022-1-27SQLServer第3章关系数据库的基本理论1第第3 3章章 关系数据库的基本理论关系数据库的基本理论 主要内容主要内容v关系数据模型关系数据模型 v关系模型的完整性规则关系模型的完整性规则 v关系代数的基本运算关系代数的基本运算v 查询优化查询优化 2022-1-27SQLServer第3章关系数据库的基本理论2本章重要概念本章重要概念 (1) 基本概念基本概念关系数据模型，关键码（主键和外键），关系的定义和性质，关系数据模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，三类完整性规则，ER模型到关系模型的转换规则，过程性模型到关系模型的转换规则，过程性语言与非

2、过程性语言。语言与非过程性语言。 (2 ) 关系代数关系代数五个基本操作，四个组合操作，七个扩充操作。五个基本操作，四个组合操作，七个扩充操作。 (3) 关系代数表达式的优化关系代数表达式的优化关系代数表达式的等价及等价转换规则，启化式优化算法。关系代数表达式的等价及等价转换规则，启化式优化算法。2022-1-27SQLServer第3章关系数据库的基本理论3本章概要本章概要 v本章先介绍关系模型的基本概念；然后主要介绍关系运算的本章先介绍关系模型的基本概念；然后主要介绍关系运算的三种理论之一：关系代数。三种理论之一：关系代数。 2022-1-27SQLServer第3章关系数据库的基本理论4

3、3.1 关系数据模型关系数据模型 主要内容主要内容v 关系模式关系模式 v 关系操作关系操作2022-1-27SQLServer第3章关系数据库的基本理论5关系模式关系模式(1) 每个关系都有一个模式，称为关系模式每个关系都有一个模式，称为关系模式(Relation Schema)，由一个，由一个关系名及它的所有属性名构成。在关系模式中，字段称为属性，字段值关系名及它的所有属性名构成。在关系模式中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图称为属性值，记录类型称为关系模式。在图3.1中，关系模式名是中，关系模式名是R。记。记录称为元组（录称为元组（tuple），元组的集合称为关

4、系（），元组的集合称为关系（relation）或实例）或实例（instance）。一般用前面的大写英语字母）。一般用前面的大写英语字母A、B、C、表示单个属性，表示单个属性，用后面的大写字母用后面的大写字母、W、X、Y、Z表示属性集，用小写字母表示属性表示属性集，用小写字母表示属性值。值。 v关系关系RABCDEa1b1c1d1e1a2b2c2d2e2a3b3c3d3e3 数据库技术的术语数据库技术的术语 关系模型的术语关系模型的术语 字段字段,数据项数据项 属性属性记录类型记录类型 关系模式关系模式记录记录1 元组元组1记录记录2 元组元组2记录记录3 元组元组3字段值字段值属性值属性值文文

5、件件关系（或实例）关系（或实例）2022-1-27SQLServer第3章关系数据库的基本理论6关系模式关系模式(2)关系具有的特点：关系具有的特点： 关系（表）可以看成是由行和列交叉组成的二维表格。它表示的是一关系（表）可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。个实体集合。 表中一行称为一个元组，可用来表示实体集中的一个实体。表中一行称为一个元组，可用来表示实体集中的一个实体。 表中的列称为属性，给每一列起一个名称即属性名，表中的属性名不表中的列称为属性，给每一列起一个名称即属性名，表中的属性名不能相同。能相同。 列的取值范围称为域，同列具有相同的域，不同的列可有相同的域

6、。列的取值范围称为域，同列具有相同的域，不同的列可有相同的域。例如，例如，SEX的取值范围是的取值范围是M（男），（男），F（女）（女），AGE为整数域。为整数域。 表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为主键。性组称为主键。 2022-1-27SQLServer第3章关系数据库的基本理论7关系模式关系模式(3)关系是一种规范化了的二维表格，具有如下性质：关系是一种规范化了的二维表格，具有如下性质：属性值是原子的，不可分解。属性值是原子的，不可分解。没有重复元组。没有重复元组。没有行序。没有行序。理论上没有

7、列序，但一般使用时都有列序。理论上没有列序，但一般使用时都有列序。 v 关键码和表之间的联系关键码和表之间的联系 超键：超键：在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。 候选键：候选键：如果一个属性集能惟一标识元组，且又不含有多余的属性，那如果一个属性集能惟一标识元组，且又不含有多余的属性，那么这个属性集称为关系的候选键。么这个属性集称为关系的候选键。 主键：主键：若一个关系中有多个候选键，则选其中的一个为关系的主键。若一个关系中有多个候选键，则选其中的一个为关系的主键。 外键：外键：若一个关系若一个关系R中包含有另一个

8、关系中包含有另一个关系S的主键所对应的属性组的主键所对应的属性组F，则，则称称F为为R的外键。并称关系的外键。并称关系S为参照关系，关系为参照关系，关系R为依赖关系。为依赖关系。 2022-1-27SQLServer第3章关系数据库的基本理论8关系模式关系模式(4)例如例如，学生关系和系部关系分别为：，学生关系和系部关系分别为： 学生（学生（SNO，SNAME，SEX，AGE，SDNO） 系部（系部（SDNO，SDNAME，CHAIR）学生关系的主键是学生关系的主键是SNO，系部关系的主键为，系部关系的主键为SDNO，在学生关系中，在学生关系中，SDNO是它的外键。更确切地说，是它的外键。更确

9、切地说，SDNO是系部表的主键，将它作为外键是系部表的主键，将它作为外键放在学生表中，实现两个表之间的联系。在关系数据库中，表与表之间的放在学生表中，实现两个表之间的联系。在关系数据库中，表与表之间的联系就是通过公共属性实现的。我们约定，在主键的属性下面加下划线，联系就是通过公共属性实现的。我们约定，在主键的属性下面加下划线，在外键的属性下面加波浪线。在外键的属性下面加波浪线。 2022-1-27SQLServer第3章关系数据库的基本理论9关系模式关系模式(5) 关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名

10、和模式的主键。名和模式的主键。SNOSNAMEAGESEXSDEPTSCCNOCNAMECDEPTETNAMESCMNGRADE 例例3.1 下图是一个教学模型的实体下图是一个教学模型的实体联系图。实体类型联系图。实体类型“学生学生”的属性的属性SNO、SNAME、SEX、AGE、SDEPT分别分别表示学生的学号、姓名、性别、年龄和表示学生的学号、姓名、性别、年龄和学生所在系部；实体类型学生所在系部；实体类型“课程课程”的属的属性性CNO、CNAME、CDEPT、TNAME分别表示课程号、课程名、课程所属系分别表示课程号、课程名、课程所属系和任课教师。学生用和任课教师。学生用S表示，课程用表示

11、，课程用C表示。表示。S和和C之间有之间有M:N的联系（一个学的联系（一个学生可选多门课程，一门课程可以被多个生可选多门课程，一门课程可以被多个学生选修），联系类型学生选修），联系类型SC的属性成绩的属性成绩用用GRADE表示。右图表示的实体联系表示。右图表示的实体联系图（图（ER图）。图）。2022-1-27SQLServer第3章关系数据库的基本理论10关系模式关系模式(6)该图表示的学生情况的部分转换成相应的关系模式为：该图表示的学生情况的部分转换成相应的关系模式为： S(SNO,SNAME,SEX,AGE,SDPET)关系模式关系模式S描述了学生的数据结构，它描述了学生的数据结构，它是

12、下表中学生实体的关系模式。其中是下表中学生实体的关系模式。其中SNO，CNO为关系为关系SC的主键，的主键，SNO、CNO又分别为关系又分别为关系SC的两个外键。的两个外键。 SNOSNAMESEXAGESDEPTS1程晓晴程晓晴F21CSS2姜姜 云云F20ISS3李小刚李小刚M21CS学生关系模式学生关系模式 S(SNO，SNAME，SEX，AGE，SDPET)选修关系模式选修关系模式 SC( SNO，CNO，GRADE)课程关系模式课程关系模式 C(CNO，CNAME，CDEPT，TNAME)SNOCNOGRADES1C187S1C278S1C390S2C167S2C279S2C356S

13、3C180S3C276S3C392学生关系实例如下表；选修关系实例如右表。学生关系实例如下表；选修关系实例如右表。2022-1-27SQLServer第3章关系数据库的基本理论11关系模式关系模式(7) CNOCNAMECDEPTTNAMEC1高等数学高等数学IS王红卫王红卫C2数据库原理数据库原理CS李绍丽李绍丽C3数据结构数据结构CS刘刘 良良课程关系实例如下表：课程关系实例如下表：关系子模式关系子模式 用户使用的数据不直接来自关系模式中的数据，而是从若干关系模用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件的数据构成关系子模式。关系子模式是用户所需式中抽取满

14、足一定条件的数据构成关系子模式。关系子模式是用户所需数据结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。数据结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。 例例3.2 用户需要用到成绩子模式用户需要用到成绩子模式G(SNO,SNAME,CNO,GRADE)。子。子模式模式G对应的数据来源于表对应的数据来源于表S和表和表SC，构造时应满足它们的，构造时应满足它们的SNO值相等。值相等。子模式子模式G的构造过程如下图所示。的构造过程如下图所示。 2022-1-27SQLServer第3章关系数据库的基本理论12关系模式关系模式(7)SNOSNAMECNOGRADES1程晓晴程

15、晓晴C187S2姜姜 云云C167SNOSNAMESEXAGESDEPTS1程晓晴程晓晴F21CSS2姜姜 云云F20IS SNOCNOGRADES1C187S2C167一一 一对应一对应2022-1-27SQLServer第3章关系数据库的基本理论13关系模式关系模式(8) 存储模式存储模式 描述关系是如何在物理存储设备上存储的。关系存储时的基本组织描述关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少（索引方法实现。如果关系中元

16、组数目较少（100以内），那么也可以用以内），那么也可以用堆文件方式实现。此外，还可以对任意的属性集建立辅助索引。堆文件方式实现。此外，还可以对任意的属性集建立辅助索引。 2022-1-27SQLServer第3章关系数据库的基本理论14关系操作关系操作(1) v 基本的关系操作基本的关系操作 关系模型中常用的关系操作包括查询（关系模型中常用的关系操作包括查询（Query）操作和插入）操作和插入（Insert）、删除（）、删除（Delete）、修改（）、修改（Update）操作。）操作。查询操作又可以分为：选择（查询操作又可以分为：选择（Select）、投影（）、投影（Project）、）、连

17、接（连接（Join）、除（）、除（Divide）、并（）、并（Union）、差（）、差（Except）、）、交（交（Intersection）、笛卡尔积等。其中选择、投影、并、差、）、笛卡尔积等。其中选择、投影、并、差、笛卡尔积是笛卡尔积是5种基本操作。种基本操作。其他操作是可以用基本操作来定义和导出的。就像乘法可以其他操作是可以用基本操作来定义和导出的。就像乘法可以用加法来定义和导出一样。用加法来定义和导出一样。关系操作的特点是集合操作方式，即操作的对象和结果都是关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称称为一次一集合（集合。这种操作方式也称称为一次一集合（s

18、et-at-a-time）的方）的方式。相应地，非关系数据模型的数据操作方式则为一次一纪录式。相应地，非关系数据模型的数据操作方式则为一次一纪录（record-at-a-time）的方式。）的方式。 2022-1-27SQLServer第3章关系数据库的基本理论15关系操作关系操作(2) 关系代数语言关系代数语言 例如例如 ISBL 元组关系演算语言元组关系演算语言 例如例如 APLHA，QUEL关系数据语言关系数据语言 关系演算语言关系演算语言 域关系演算语言域关系演算语言 例如例如 QBE 具有关系代数和关系演算双重特点的语言具有关系代数和关系演算双重特点的语言 例如例如 SQL 关系数据

19、语言可以分为三类关系数据语言可以分为三类 ：关系代数、元组关系演算和域关系关系代数、元组关系演算和域关系演算演算。该三种语言在表达能力上是完全等价的。该三种语言在表达能力上是完全等价的。 关系语言是一种高度非过程化的语言，用户不必请求关系语言是一种高度非过程化的语言，用户不必请求DBA为其建为其建立特殊的存取路径，存取路径的选择由立特殊的存取路径，存取路径的选择由RDBMS的优化机制来完成。的优化机制来完成。 2022-1-27SQLServer第3章关系数据库的基本理论163.2 关系模型的完整性规则关系模型的完整性规则 主要内容主要内容v 关系的三类完整性约束关系的三类完整性约束v 实体完

20、整性实体完整性v 参照完整性参照完整性v 用户定义完整性用户定义完整性2022-1-27SQLServer第3章关系数据库的基本理论17三类完整性约束三类完整性约束(1) 关系模型中有三类完整性约束：关系模型中有三类完整性约束：实体完整性、参照完整性和实体完整性、参照完整性和用户定义的完整性用户定义的完整性。其中实体完整性和参照完整性是关系模型必。其中实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。用户定义的完整性是应用领域需要遵循的约关系系统自动支持。用户定义的完整性是应用领域

21、需要遵循的约束条件，体现了具体领域中的语义约束。束条件，体现了具体领域中的语义约束。 v 规则规则3.1 实体完整性（实体完整性（Entity Integrity）规则：）规则：若属性若属性（指一个或一组属性）（指一个或一组属性）A是基本关系是基本关系R的主属性。则的主属性。则A不能取空不能取空值。值。 例如，例如，在关系在关系S(SNO,SNAME,SEX,AGE,SDPET)中，中，SNO这个属性为主码，则这个属性为主码，则SNO不能取空值。不能取空值。 实体完整性要求关系中元组在组成主键的属性上不能有空值。实体完整性要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起

22、不了惟一标织元组的作用。如果出现空值，那么主键值就起不了惟一标织元组的作用。2022-1-27SQLServer第3章关系数据库的基本理论18三类完整性约束三类完整性约束(2)对于实体完整性规则说明如下几点：对于实体完整性规则说明如下几点： 实体完整性规则是针对基本关系而言的。一个基本关实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。例如学生关系对应于学系通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。生的集合。 现实世界中的实体是可区分的，即它们具有某种唯一现实世界中的实体是可区分的，即它们具有某种唯一性标识。例如每个学生都是独立的个体，是不一样的。

23、性标识。例如每个学生都是独立的个体，是不一样的。 关系模型中以主码作为唯一性标识。关系模型中以主码作为唯一性标识。 主码中的属性即主属性不能取空值。如果主属性取空主码中的属性即主属性不能取空值。如果主属性取空值，就说明存在某个不可标识的实体，即存在不可区分的实值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与第点相矛盾，因此这个规则称为实体完整性。体，这与第点相矛盾，因此这个规则称为实体完整性。2022-1-27SQLServer第3章关系数据库的基本理论19三类完整性约束三类完整性约束(3)v参照完整性规则参照完整性规则（reference integrity rule）定义定义2

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

25、整性建立了多表之间的对应关系由参照完整性建立了多表之间的对应关系R(Kr，F，)， S(Ks，)参照关系参照关系 被参照关系（目标关系）被参照关系（目标关系）2022-1-27SQLServer第3章关系数据库的基本理论20三类完整性约束三类完整性约束(4)例例2.12.1 下面各种情况说明了参照完整性规则在关系中如何下面各种情况说明了参照完整性规则在关系中如何实现的。实现的。 在关系数据库中有下列两个关系模式：在关系数据库中有下列两个关系模式： S S（S#S#，SNAMESNAME，AGEAGE，SEXSEX） SCSC（S#S#，C#C#，GRADEGRADE）这里带下划线者为主键，带红

26、虚线者为外键。据规则要求，这里带下划线者为主键，带红虚线者为外键。据规则要求，关系关系SCSC中的中的S# S# 值应该在关系值应该在关系S S中出现。如果关系中出现。如果关系SCSC中有一个元中有一个元组（组（S7,C4,80S7,C4,80），而学号），而学号S7S7却在关系却在关系S S中找不到，那么我们就中找不到，那么我们就认为在关系认为在关系SCSC中引用了一个不存在的学生实体，这就违反了参中引用了一个不存在的学生实体，这就违反了参照完整性规则。照完整性规则。另外，在关系另外，在关系SCSC中中S#S#不仅是外键，也是主键的一部分，因不仅是外键，也是主键的一部分，因此这里此这里S#

27、S# 值不允许空。值不允许空。2022-1-27SQLServer第3章关系数据库的基本理论21三类完整性约束三类完整性约束(5) 设工厂数据库中有两个关系模式：设工厂数据库中有两个关系模式：DEPT(DEPT(D#D#，DNAME)DNAME)EMP(EMP(E#E#，ENAMEENAME，SALARYSALARY，D# )D# ) 车间模式车间模式DEPTDEPT的属性为车间编号、车间名，职工模式的属性为车间编号、车间名，职工模式EMPEMP的属性为工号、姓名、工资、所在车间的编号。每个的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在模式的主键与外键已标出。在EMP

28、EMP中，由于中，由于D#D#不在主键中，不在主键中，因此因此D# D# 值允许空。值允许空。 设课程之间有先修、后继联系。模式如下：设课程之间有先修、后继联系。模式如下：R(R(C#C# ，CNAMECNAME，PC# )PC# ) 2022-1-27SQLServer第3章关系数据库的基本理论22三类完整性约束三类完整性约束(6)其属性表示课程号、课程名、先修课的课程号。如果规其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式定，每门课程的直接先修课只有一门，那么模式R R的主键是的主键是C#C#，外键是，外键是PC#.PC#.。这里参照完整性在一个

29、模式中实现。即每。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。门课程的直接先修课必须在关系中出现。 v用户定义的完整性规则用户定义的完整性规则 在建立关系模式时，对属性定义了数据类型，即使这在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。例如学一的方法处理它们，不再由应用程序承担这项工作。例如学生的年龄定义为两位整数，

30、范围还太大，我们可以写如下规生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在则把年龄限制在15153030岁之间：岁之间：CHECKCHECK（AGE BETWEEN 15 AND 30AGE BETWEEN 15 AND 30） 2022-1-27SQLServer第3章关系数据库的基本理论233.3 关系代数的基本运算关系代数的基本运算 主要内容主要内容v 传统的集合运算传统的集合运算v 专门的关系运算专门的关系运算v 关系代数表达式及其应用实例关系代数表达式及其应用实例 2022-1-27SQLServer第3章关系数据库的基本理论24传统的集合运算传统的集合运算(1)

31、v 并（并（Union） 设关系设关系R和和S具有相同的关系模式，具有相同的关系模式，R和和S的并是由属于的并是由属于R或属或属于于S的元组构成的集合，记为的元组构成的集合，记为RS。形式定义如下：。形式定义如下：RSt | tR tS，t是元组变量，是元组变量，R和和S的元数相同。的元数相同。v 差（差（Difference） 设关系设关系R和和S具有相同的关系模式，具有相同的关系模式，R和和S的差是由属于的差是由属于R但不但不属于属于S的元组构成的集合，记为的元组构成的集合，记为RS。形式定义如下：。形式定义如下：RS t | tR tS，R和和S的元数相同。的元数相同。例子例子2022-

32、1-27SQLServer第3章关系数据库的基本理论25传统的集合运算传统的集合运算(2)v 交（交（intersection） 关系关系R和和S的交是由属于的交是由属于R又属于又属于S的元组构成的集合，记为的元组构成的集合，记为RS，这里要求，这里要求R和和S定义在相同的关系模式上。形式定义如定义在相同的关系模式上。形式定义如下：下： RSttR tS，R和和S的元数相同。的元数相同。由于由于RS = R-(R-S)，或，或RS = S-(S-R)，因此交操作不是一个独立的，因此交操作不是一个独立的操作。操作。 ABCa1a1a2b1b2b2c1c2c1ABCa1a1a2b2b3b2c2c2

33、c1bBCa1 a2b2 b2c2 c1例例 R S R S 2022-1-27SQLServer第3章关系数据库的基本理论26传统的集合运算传统的集合运算(3)v 笛卡儿积笛卡儿积(Cartesian Product) 设关系设关系R和和S的元数分别为的元数分别为r和和s,定义定义R和和S的一个的一个(r+s)元的元元的元组集合，每个元组的前组集合，每个元组的前r个分量来自个分量来自R的一个元组，后的一个元组，后s个分量个分量来自来自S的一个元组，记为的一个元组，记为RS。 RS t|t=trRtsS 若若R有有m个元组，个元组，S有有n个元组，则个元组，则RS有有mn个元组。个元组。202

34、2-1-27SQLServer第3章关系数据库的基本理论27专门的关系运算专门的关系运算 (1)v 选择（选择（Selection） 选择操作是根据某些条件对关系做水平分割，即选取符合条件的元选择操作是根据某些条件对关系做水平分割，即选取符合条件的元组。条件可用命题公式（即计算机语言中的条件表达式）组。条件可用命题公式（即计算机语言中的条件表达式）F表示。表示。 F中的基本形式为：中的基本形式为：X1Y1： 其中其中表示比较运算符表示比较运算符:，。，。 X1，Y1等是属性名，常量，或列序号。等是属性名，常量，或列序号。 关系关系R关于公式关于公式F的选择操作用的选择操作用F（R）表示，形式定

35、义如）表示，形式定义如下：下： F（R） t | tR F（t）= true 为选择运算符，为选择运算符，F（R）表示从）表示从R中挑选满足公式中挑选满足公式F为为真的元组所构成的关系。真的元组所构成的关系。 例如，例如，23（R）表示从）表示从R中挑选第中挑选第2个分量值大于个分量值大于3的的元组所构成的关系。书写时，为了与属性序号区别起见，元组所构成的关系。书写时，为了与属性序号区别起见，常量常量用引号括起来，而属性序号或属性名不要用引号括起来用引号括起来，而属性序号或属性名不要用引号括起来。2022-1-27SQLServer第3章关系数据库的基本理论28专门的关系运算专门的关系运算 (

36、2)v 投影（投影（ProjectionProjection） 这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列的顺序。的顺序。 设关系设关系R R是是k k元关系，元关系，R R在其分量在其分量A Ai1i1，A Aimim（mk imk i1 1，i im m ，为为1 1到到k k间的整数）上的投影用间的整数）上的投影用i1,.,im（R R）表示，它是一个）表示，它是一个m m元元组集合，元元组集合，形式定义如下：形式定义如下：i1i1，imim（R R） t | t t | tt ti1i1，t timimt t1

37、1，t tk kR R 例如例如，3 3，1 1（R R）表示关系）表示关系R R中取第中取第1 1、3 3列，组成新的关系，新关系列，组成新的关系，新关系中第中第1 1列为列为R R的第的第3 3列，新关系的第列，新关系的第2 2列为列为R R的第的第1 1列。如果列。如果R R的每列标上属的每列标上属性名，那么操作符性名，那么操作符的下标处也可以用属性名表示。例如，关系的下标处也可以用属性名表示。例如，关系R R（A A，B B，C C），那么），那么C C，A A（R R）与）与3 3，1 1（R R）是等价的。）是等价的。2022-1-27SQLServer第3章关系数据库的基本理论2

38、9专门的关系运算专门的关系运算 (3)v 连接（连接（join） 连接有两种：连接有两种：连接和连接和F连接（这里连接（这里是算术比较符，是算术比较符，F是是公式）。公式）。 连接连接 R St t= trR tsS 表达式表达式 表示元组表示元组tr的第的第i个分量、元组个分量、元组ts的第的第j个分量满足个分量满足操操作。作。 F连接连接 F连接是从关系连接是从关系R和和S的笛卡儿积中选取属性间满足某一公的笛卡儿积中选取属性间满足某一公式式F的元组的元组, 这里这里F是形为是形为F1F2Fn的公式，每个的公式，每个FP是形是形ij的式子，而的式子，而i和和j分别为关系分别为关系R和和S的第

39、的第i、第、第j个分量的序个分量的序号。号。ij2022-1-27SQLServer第3章关系数据库的基本理论30例例 连接和连接和F连接的例子连接的例子.说明: 1. 也可以写成。24（RS)2.。专门的关系运算专门的关系运算 (4)2022-1-27SQLServer第3章关系数据库的基本理论31v 自然连接（自然连接（natural join） 两个关系两个关系R和和S的自然连接的自然连接 操作操作具体计算过程如下具体计算过程如下： 计算计算RS ； 设设R和和S的公共属性是的公共属性是A1,AK，挑选，挑选RS中满足中满足R.A1=S.A1，R.AK=S.AK 的那些元组；的那些元组；

40、 去掉去掉S.A1，S.AK这些列。这些列。定义：定义： 其中其中i1,im为为R和和S的全部属性，但公共属性只出现一次。的全部属性，但公共属性只出现一次。 )(.R.A.,.,ik111SRkmASASARi专门的关系运算专门的关系运算 (5)2022-1-27SQLServer第3章关系数据库的基本理论32ABCa1a1a2a2b1b2b3b456812BEb1b2b3b3b5371022AR.BCS.BEa1a1a1a1a2b1 b1 b2 b2 b355668b2 b3 b2 b3 b37 10 7 10 10AR.BCS.BEa1a1a2a2b1b2b3b35688b1b2b3b33

41、7102ABCEa1a1a2a2b1b2b3b3568837102专门的关系运算专门的关系运算 (6)关系关系R关系关系S一般连接一般连接 R SCER.Cs0），那么），那么RS是一是一个（个（r-s）元的元组的集合。（）元的元组的集合。（RS）是满足下列条件的最大关）是满足下列条件的最大关系：其中每个元组系：其中每个元组t与与S中每个元组中每个元组u组成的新元组组成的新元组必在必在关系关系R中。中。 RS1,2,r-s（R）- 1,2,r-s (1,2,r-s(R)S)-R) 专门的关系运算专门的关系运算 (9)2022-1-27SQLServer第3章关系数据库的基本理论36例例 关系做

42、除法的例子。关系做除法的例子。专门的关系运算专门的关系运算 (10)2022-1-27SQLServer第3章关系数据库的基本理论37关系代数运算的应用实例关系代数运算的应用实例(1)(1) v在关系代数运算中，把由五个基本操作经过有限次复合的式子称为在关系代数运算中，把由五个基本操作经过有限次复合的式子称为关关系代数表达式系代数表达式。这种表达式的运算结果仍是一个关系。这种表达式的运算结果仍是一个关系。例例2.7 设设教学数据库中有三个关系教学数据库中有三个关系： 学生关系学生关系 S(S#,SNAME,AGE,SEX) 选课关系选课关系 SC(S#,C#,GRADE) 课程关系课程关系 C

43、(C#,CNAME,TEACHER) 用关系代数表达式表示查询语句。用关系代数表达式表示查询语句。 (1)1) 检索学习课程号为检索学习课程号为C2的学生学号与成绩。的学生学号与成绩。 S#,GRADE(C#=C2 (SCSC) (2) 检索学习课程号为检索学习课程号为C2的学生的学号与姓名。的学生的学号与姓名。 S#,SNAME(C#=C2 (S S SCSC) (3)(3) 检索选修课程名为检索选修课程名为MATHS的学生学号与姓名。的学生学号与姓名。 S#,SNAME(CNAME=MATHS (S S SCSC C C) 2022-1-27SQLServer第3章关系数据库的基本理论38

44、 (4)(4) 检索选修课程号为检索选修课程号为C2或或C4的学生学号。的学生学号。 S#(C#=C2 C#=C4(SCSC) (5)(5) 检索至少选修课程号为检索至少选修课程号为C2和和C4的学生学号。的学生学号。 1 1( (1=41=42=2=C2 5=C4 (SCSCSC)SC) (6)(6)检索不学检索不学C2C2课的学生姓名与年龄。课的学生姓名与年龄。 SNAME,AGESNAME,AGE ( S S)-SNAME,AGESNAME,AGE (C#=C2 (S S SCSC) (7)(7) 检索学习全部课程的学生姓名。检索学习全部课程的学生姓名。 学生选课情况可用操作学生选课情况

45、可用操作S#,C#S#,C#(SC);(SC); 全部课程可用操作全部课程可用操作C#C#(C(C)表示表示; ; 学了全部课程的学生学号可用除法操作表示学了全部课程的学生学号可用除法操作表示, ,操作结果是学号操作结果是学号S#S#集集; ; S#,C#S#,C# (SC(SC) C#C# (C C) 从从S#S#求学生姓名求学生姓名SNAME,SNAME,可以用自然连接和投影操作组合而成可以用自然连接和投影操作组合而成: : SNAMESNAME(S(S (S#,C#,C# (SCSC) C# (C C) (8)(8)检索所学课程包含学生检索所学课程包含学生S3S3所学课程的学生学号。所学

46、课程的学生学号。 学生选课情况可用操作学生选课情况可用操作S#,C#S#,C# (SCSC)表示表示; 学生学生S3S3所学课程可用操作所学课程可用操作C#C#( (S#=S#=S3S3(SC)(SC)表示表示; ; 所学课程包含学生所学课程包含学生S3S3所学课程的学生学号所学课程的学生学号, ,可以用除法操作求得可以用除法操作求得: : S#,CS#,C# (SCSC) C#C#( (S#=S#=S3S3(SC)(SC) S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE) C(C#,CNAME,TEACHER) 关系代数运算的应用实例关系代数运算的应用实例(2)2022-

47、1-27SQLServer第3章关系数据库的基本理论39关系代数运算的应用实例关系代数运算的应用实例(3)一般地有下列规律：一般地有下列规律：(1) 对于只涉及到选择、投影、连接的查询对于只涉及到选择、投影、连接的查询可用下列表达式表示：可用下列表达式表示： (RS) 或者或者(R S)(2) 对于否定的操作对于否定的操作，一般要用差操作表示，例如，一般要用差操作表示，例如“检索不学检索不学C2课的课的学生姓名学生姓名”。用下列表达式表示：。用下列表达式表示： SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式表示：但不能用下式表示： SNAME(CNOC2(S SC) 对于检

48、索对于检索具有具有“全部全部”特征特征的操作，一般要用除法操作表示，例的操作，一般要用除法操作表示，例如如“检索学习全部课程的学生学号检索学习全部课程的学生学号”。用下列表达式表示：。用下列表达式表示： 要用要用SNO,CNO(SC)CNO(C)表示，而不能写成表示，而不能写成 SNO (SCCNO(C)形式。形式。 这是因为一个学生学的课程的成绩可能是不一样的。这是因为一个学生学的课程的成绩可能是不一样的。 2022-1-27SQLServer第3章关系数据库的基本理论403.5 查询优化查询优化 主要内容主要内容v 查询优化的一般策略查询优化的一般策略v 代数表达式的等价变换规则代数表达式

49、的等价变换规则v 优化算法优化算法 2022-1-27SQLServer第3章关系数据库的基本理论41查询优化例子查询优化例子例例 设关系设关系R R和和S S都是二元关系，属性名分别为都是二元关系，属性名分别为A A，B B和和C C，D D。 设有一个查询可用关系代数表达式表示：设有一个查询可用关系代数表达式表示： E E1 1= =A A（B=CD=99B=CD=99（R RS S） 也可以把选择条件也可以把选择条件D=99D=99移到笛卡儿积中的关系移到笛卡儿积中的关系S S前面：前面： E E2 2= =A A（B=CB=C（R RD=99D=99（S S） 还可以把选择条件还可以把

50、选择条件B BC C与笛卡儿积结合成等值连接形式：与笛卡儿积结合成等值连接形式： E3=E3=A A（R R D=99D=99（S S） 这三个关系代数表达式是等价的，但执行的效率大不一这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求样。显然，求E El l，E E2 2，E E3 3的大部分时间是花在连接操作上的。的大部分时间是花在连接操作上的。 可以分析出，可以分析出，在时空性能上在时空性能上，E3最优，其次是最优，其次是E2，最，最后是后是E1。此例还可以看出，如何安排选择、投影和连接的。此例还可以看出，如何安排选择、投影和连接的顺序是个很重要的问题。顺序是个很重要的问题。2

51、022-1-27SQLServer第3章关系数据库的基本理论42查询优化的一般策略查询优化的一般策略 (1)v在关系代数表达式中需要指出若干关系的操作步骤。那么，在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为空间，而且效率也比较高呢？这个问题称为查询优化问题查询优化问题。v查询优化是实现关系系统的关键技术查询优化是实现关系系统的关键技术, ,它大大减轻了用户它大大减轻了用户选择存取路径的负担选择存取路径的负担, ,用户使用关系系统时用户使用关系系统时,

52、 ,只要提出只要提出“做做什么什么”, ,不必指出不必指出“怎么做怎么做”。v在关系代数运算中，笛卡儿积和连接运算是最费时间的。在关系代数运算中，笛卡儿积和连接运算是最费时间的。2022-1-27SQLServer第3章关系数据库的基本理论43查询优化的一般策略查询优化的一般策略 (2)查询优化采用的一般策略是：查询优化采用的一般策略是： 尽可能早地执行选择运算尽可能早地执行选择运算。在查询中这种变换最为重要，因为它可。在查询中这种变换最为重要，因为它可以以元组为单位减小中间结果，从而使执行时间成数量级地减少。以以元组为单位减小中间结果，从而使执行时间成数量级地减少。 把先做笛卡儿积，后做选择

53、结合起来把先做笛卡儿积，后做选择结合起来。使之成为一个连接运算。连。使之成为一个连接运算。连接运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿接运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿积积RS的结果再做选择时，并且这个选择是对的结果再做选择时，并且这个选择是对R和和S的属性进行比较，在的属性进行比较，在这样的条件下，这个笛卡儿积和选择运算等价于一个连接。这样的条件下，这个笛卡儿积和选择运算等价于一个连接。 一般对不含一般对不含R的属性或不含的属性或不含S的属性的比较，可以移到笛卡儿积运算前去做，这样做比转的属性的比较，可以移到笛卡儿积运算前去做，这样做比转换

54、到连接更好。换到连接更好。 同时计算一串选择和一串投影运算同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文，以免分开运算造成多次扫描文件，从而节省了操作时间。件，从而节省了操作时间。 找出表达式里的公共子表达式找出表达式里的公共子表达式。如果公共子表达式的结果不是很大，。如果公共子表达式的结果不是很大，并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个公并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个公共子表达式是有好处的。共子表达式是有好处的。子表达式内涉及到连接，但又不能把限定条件向内移入的那类表达式，子表达式内涉及到连接，但又不能把限定条件向内移入的那

55、类表达式，一般属于这一类。一般属于这一类。 2022-1-27SQLServer第3章关系数据库的基本理论44代数表达式的等价变换规则代数表达式的等价变换规则 (1)v 连接和笛卡儿积的交换律连接和笛卡儿积的交换律 E1 E2E1 E2E2 E1 E1 E2E2 E1 E1 E2 E2 E1 E1E2 E1 E1E2 E2 E1 E1E2E2v 连接和笛卡儿积的结合律连接和笛卡儿积的结合律 (E1 E2(E1 E2） E3E3E1 E1 (E2 E3E2 E3) (E1 E2) E3 (E1 E2) E3E1 (E2 E3)E1 (E2 E3) (E1 (E1E2)E2)E3 E3 E1E1(

56、E2(E2E3)E3)v 投影的串接投影的串接 设设L1,L1,设设L2,LnL2,Ln为属性集，并且为属性集，并且 , ,那么下式也成立那么下式也成立. . v 选择的串接选择的串接 LnLL.21)().)(.(121EELLnLL）（成立：，因此选择的交换律也由于E)E(F1F2F2F1)()(F1F2F2F12121EEFFFF2022-1-27SQLServer第3章关系数据库的基本理论45v 选择和投影操作的交换选择和投影操作的交换代数表达式的等价变换规则代数表达式的等价变换规则 (2)(（ )(1)()(1 LEE：，LLF，LFEELLFFLLFFL那么有下式成立中的属性集还涉

57、及到不在如果条件中的属性只涉及到这里要求v 选择对笛卡儿积的分配律选择对笛卡儿积的分配律 2) 1()21(EEEEFF 这里要求F只涉及到E1中的属性。如果F形为F1F2，且F1只涉及到E1的属性，F2只涉及到E2的属性，则有)2() 1()21(21EEEEFFF 此外，如果F形为F1F2，且F1只涉及到E1的属性，F2只涉及到E1和E2的属性，则有：)2) 1()21(12EEEEFFF2022-1-27SQLServer第3章关系数据库的基本理论46v 选择对并的分配律选择对并的分配律 E1和E2具有相同的属性名，或者E1和E2表达的关系的属性有对应性，则有：)2() 1()21(EE

58、EEFFF代数表达式的等价变换规则代数表达式的等价变换规则(3)(3)v 选择对集合差的分配律选择对集合差的分配律 E1和E2的属性有对应性，则有：2) 1()21()2() 1()21(EEEEEEEEFFFFF或v 选择对自然联接的分配律选择对自然联接的分配律 F只涉及到表达式E1和E2的公共属性，则有： （E1 E2） （E1） （E2）FFFv 投影对笛卡尔的分配律投影对笛卡尔的分配律 L1是E1中的属性集，L2是E2中的属性集，则有：)2() 1()21(2121EEEELLLLv 投影对并的分配律投影对并的分配律 E1和E2的属性有对应性，则有：)2() 1()21(EEEELLL

59、2022-1-27SQLServer第3章关系数据库的基本理论47代数表达式的等价变换规则代数表达式的等价变换规则 (4)(4)v 选择与联接操作的结合选择与联接操作的结合 F（E1E2）E1E21F（E1E2）E1E2v 并和交的交换律并和交的交换律 E1E2E2E1 E1E2E2E1v 并和交的结合律并和交的结合律 （E1E2）E3E1（E2E3） （E1E2）E3E1（E2E3）2022-1-27SQLServer第3章关系数据库的基本理论48优化算法优化算法 (1)(1)v 代数优化是利用上面的等价变换规则，对关系表达式进行代数优化是利用上面的等价变换规则，对关系表达式进行优化，以减少执行时的开销。虽然不能保证最优，但在多数情优化，以减少执行时的开销。虽然不能保证最优，但在多数情况下能使表达式更好些。在关系代数表达式中，最花费时间和况下能使表达式更好些。在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。则，用于对表达式进行转换，以减少中间关系的大小。优先应用单项的选择和投影；优先应用单项的选择和投影；优先应用一般选