《【教学课件】第3章关系数据库的基本理论.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第3章关系数据库的基本理论.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 关系数据库的基本理论冯万利冯万利本章重要概念(1)基本概念基本概念关系数据模型，关键码（主键和外键），关系的关系数据模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，定义和性质，三类完整性规则，ER模型到关系模型模型到关系模型的转换规则，过程性语言与非过程性语言。的转换规则，过程性语言与非过程性语言。(2)关系代数关系代数五个基本操作，四个组合操作，七个扩充操作。五个基本操作，四个组合操作，七个扩充操作。(3)关系代数表达式的优化关系代数表达式的优化关系代数表达式的等价及等价转换规则，启化式关系代数表达式的等价及等价转换规则，启化式优化算法。优化算法。主要内容3.1关系数据
2、模型关系数据模型v3.1.1 关系模式关系模式 v3.1.2 关系操作关系操作3.2关系模型的完整性规则关系模型的完整性规则v3.2.1 关系的三类完整性约关系的三类完整性约束束v3.2.2 实体完整性实体完整性v3.2.3 参照完整性参照完整性v3.2.4 用户自定义完整性用户自定义完整性3.3关系代数的基本运算关系代数的基本运算v3.3.1 传统的集合运算传统的集合运算v3.3.2 专门的关系运算专门的关系运算v3.3.3 关系代数表达式及其关系代数表达式及其应用实例应用实例*3.4关系演算关系演算v元组关系演算元组关系演算v域关系演算域关系演算3.5 查询优化查询优化v3.5.1 查询优
3、化的一般策略查询优化的一般策略v3.5.2 代数表达式的等价变代数表达式的等价变换规则换规则v3.5.3 优化算法优化算法3.1关系数据模型3.1.1 关系模式 每个关系都有一个模式，称为关系模式每个关系都有一个模式，称为关系模式(Relation Schema)，由一个关系名及它的所有属性名构成。，由一个关系名及它的所有属性名构成。在关系模式中，字段称为属性，字段值称为属性值，在关系模式中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图记录类型称为关系模式。在图3.1中：中：v关系模式名是关系模式名是Rv记录称为元组（记录称为元组（tuple）v元组的集合称为关系（元组的集合称为
4、关系（relation）或实例（）或实例（instance）一般用前面的大写英语字母一般用前面的大写英语字母A、B、C、表示单个属表示单个属性，用后面的大写字母性，用后面的大写字母、W、X、Y、Z表示属性集，表示属性集，用小写字母表示属性值。用小写字母表示属性值。数据库技术的术语数据库技术的术语 关系模型的术语关系模型的术语ABCDEa1 b1 c1 d1 e1a2 b2 c2 d2 e2a3 b3 c3 d3 e3 数据库技术的术语数据库技术的术语 关系模型的术语关系模型的术语 字段字段,数据项数据项 属性属性记录类型记录类型 关系模式关系模式记录记录1 元组元组1记录记录2 元组元组2记录
5、记录3 元组元组3字段值字段值属性值属性值文文件件关系（或实例）关系（或实例）关系具有的特点 关系（表）可以看成是由行和列交叉组成的二维表关系（表）可以看成是由行和列交叉组成的二维表格。它表示的是一个实体集合。格。它表示的是一个实体集合。表中一行称为一个元组，可用来表示实体集中的一表中一行称为一个元组，可用来表示实体集中的一个实体。个实体。表中的列称为属性，给每一列起一个名称即属性名，表中的列称为属性，给每一列起一个名称即属性名，表中的属性名不能相同。表中的属性名不能相同。列的取值范围称为域，同列具有相同的域，不同的列的取值范围称为域，同列具有相同的域，不同的列可有相同的域。列可有相同的域。v
6、例如，例如，SEX的取值范围是的取值范围是M（男），（男），F（女）（女），AGE为整为整数域。数域。表中任意两行（元组）不能相同。能惟一标识表中表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为主键。不同行的属性或属性组称为主键。关系的性质属性值是原子的，不可分解。属性值是原子的，不可分解。没有重复元组。没有重复元组。没有行序。没有行序。理论上没有列序，但一般使用时都有列序。理论上没有列序，但一般使用时都有列序。关键码和表之间的联系 超键：在一个关系中，能惟一标识元组的属性超键：在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。或属性集称为关系的超键。候选键：如果一
7、个属性集能惟一标识元组，且候选键：如果一个属性集能惟一标识元组，且又不含有多余的属性，那么这个属性集称为关又不含有多余的属性，那么这个属性集称为关系的候选键。系的候选键。主键：若一个关系中有多个候选键，则选其中主键：若一个关系中有多个候选键，则选其中的一个为关系的主键。的一个为关系的主键。外键：若一个关系外键：若一个关系R中包含有另一个关系中包含有另一个关系S的的主键所对应的属性组主键所对应的属性组F，则称，则称F为为R的外键。并的外键。并称关系称关系S为参照关系，关系为参照关系，关系R为依赖关系。为依赖关系。关系模式举例例如，学生关系和系部关系分别为：例如，学生关系和系部关系分别为：v 学生
8、（学生（SNO，SNAME，SEX，AGE，SDNO）v系部（系部（SDNO，SDNAME，CHAIR）学生关系的主键是学生关系的主键是SNO，系部关系的主键为，系部关系的主键为SDNO，在学生关系中，在学生关系中，SDNO是它的外键。是它的外键。更确切地说，更确切地说，SDNO是系部表的主键，将它作为外键是系部表的主键，将它作为外键放在学生表中，实现两个表之间的联系。放在学生表中，实现两个表之间的联系。在关系数据库中，表与表之间的联系就是通过公共属在关系数据库中，表与表之间的联系就是通过公共属性实现的。性实现的。我们约定，在主键的属性下面加下划线，在外键的属我们约定，在主键的属性下面加下划线
9、，在外键的属性下面加波浪线。性下面加波浪线。关系模式、关系子模式和存储模式SNOSNAMEAGESEXSDEPTSCCNOCNAMECDEPTETNAMESCMNGRADE例例3.1 下图是一个教学模型的实下图是一个教学模型的实体联系图。实体类型体联系图。实体类型“学生学生”的属性的属性SNO、SNAME、SEX、AGE、SDEPT分别表示学生的分别表示学生的学号、姓名、性别、年龄和学学号、姓名、性别、年龄和学生所在系部；实体类型生所在系部；实体类型“课程课程”的属性的属性CNO、CNAME、CDEPT、TNAME分别表示课分别表示课程号、课程名、课程所属系和程号、课程名、课程所属系和任课教师
10、。学生用任课教师。学生用S表示，课程表示，课程用用C表示。表示。S和和C之间有之间有M:N的的联系（一个学生可选多门课程，联系（一个学生可选多门课程，一门课程可以被多个学生选修）一门课程可以被多个学生选修），联系类型，联系类型SC的属性成绩用的属性成绩用GRADE表示。右图表示的实体表示。右图表示的实体联系图（联系图（ER图）。图）。关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的集合。具体的关系称为实例。和模式的集合。具体的关系称为实例。关系模式该图表示的学生情况的部分转换成相应的关系模式为：该图表示
11、的学生情况的部分转换成相应的关系模式为：S(SNO,SNAME,SEX,AGE,SDPET)关系模式关系模式S描述了学生的数据结构，它是描述了学生的数据结构，它是下表中学生实体的关系模式。其中下表中学生实体的关系模式。其中SNO，CNO为关系为关系SC的主键，的主键，SNO、CNO又分别为关系又分别为关系SC的两个外键。的两个外键。SNOSNAMESEXAGESDEPTS1程程晓晓晴晴F21CSS2姜姜 云云F20ISS3李小李小刚刚M21CS学生关系模式学生关系模式 S(SNO，SNAME，SEX，AGE，SDPET)选修关系模式选修关系模式 SC(SNO，CNO，GRADE)课程关系模式课
12、程关系模式 C(CNO，CNAME，CDEPT，TNAME)SNOCNOGRADES1C187S1C278S1C390S2C167S2C279S2C356S3C180S3C276S3C392学生关系实例如下表；选修关系实例如右表。学生关系实例如下表；选修关系实例如右表。关系模式(9)CNOCNAMECDEPTTNAMEC1高等数学高等数学IS王王红卫红卫C2数据数据库库原理原理CS李李绍丽绍丽C3数据数据结结构构CS刘刘 良良课程关系实例如下表：课程关系实例如下表：关系子模式用户使用的数据不直接来自关系模式中的数据，用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件
13、的数而是从若干关系模式中抽取满足一定条件的数据构成关系子模式。关系子模式是用户所需数据构成关系子模式。关系子模式是用户所需数据结构的描述，其中包括这些数据来自哪些模据结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。式和应满足哪些条件。例例3.2 用户需要用到成绩子模式用户需要用到成绩子模式G(SNO,SNAME,CNO,GRADE)。子模式。子模式G对对应的数据来源于表应的数据来源于表S和表和表SC，构造时应满足它，构造时应满足它们的们的SNO值相等。子模式值相等。子模式G的构造过程如下图的构造过程如下图所示。所示。SNOSNAMECNOGRADES1程程晓晓晴晴C187S2姜姜 云
14、云C167SNOSNAMESEXAGESDEPTS1程程晓晓晴晴F21CSS2姜姜 云云F20IS 关系子模式SNOCNOGRADES1C187S2C167一一 一对应一对应描述关系是如何在物理存储设备上存储的。关描述关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少索引方法实现。如果关系中元组数目较少（100以内），那么也可以用堆文件方式实现。以内），那么也可以用堆文件方式实现。此外，还可以对任意的属性集建立辅助
15、索引。此外，还可以对任意的属性集建立辅助索引。存储模式 关系模型中常用的关系操作包括查询（关系模型中常用的关系操作包括查询（Query）操作）操作和插入（和插入（Insert）、删除（）、删除（Delete）、修改）、修改（Update）操作。）操作。查询操作又可以分为：选择（查询操作又可以分为：选择（Select）、投影）、投影（Project）、连接（）、连接（Join）、除（）、除（Divide）、并）、并（Union）、差（）、差（Except）、交（）、交（Intersection）、）、笛卡尔积等。笛卡尔积等。基本操作：选择、投影、并、差、笛卡尔积。基本操作：选择、投影、并、差、笛
16、卡尔积。其他操作：可以用基本操作来定义和导出的。其他操作：可以用基本操作来定义和导出的。关系操作的特点是集合操作方式，即操作的对象和结关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称称为一次一集合果都是集合。这种操作方式也称称为一次一集合（set-at-a-time）的方式。相应地，非关系数据模型）的方式。相应地，非关系数据模型的数据操作方式则为一次一纪录（的数据操作方式则为一次一纪录（record-at-a-time）的方式。）的方式。3.1.2 关系操作 关系代数语言关系代数语言 例如例如 ISBL 元组关系演算语言元组关系演算语言 例如例如 APLHA，QUEL
17、关系数据语言关系数据语言 关系演算语言关系演算语言 域关系演算语言域关系演算语言 例如例如 QBE 具有关系代数和关系演算双重特点的语言具有关系代数和关系演算双重特点的语言 例如例如 SQL 关系语言是一种高度非过程化的语言，用户不关系语言是一种高度非过程化的语言，用户不必请求必请求DBA为其建立特殊的存取路径，存取路径为其建立特殊的存取路径，存取路径的选择由的选择由RDBMS的优化机制来完成。的优化机制来完成。关系数据语言的分类关系数据语言分为三类：关系代数、元组关系关系数据语言分为三类：关系代数、元组关系演算和域关系演算。该三种语言在表达能力上演算和域关系演算。该三种语言在表达能力上是完全
18、等价的。是完全等价的。3.2 关系模型的完整性规则主要内容3.2.1 关系的三类完整性约束关系的三类完整性约束3.2.2 实体完整性实体完整性3.2.3 参照完整性参照完整性3.2.4 用户定义完整性用户定义完整性关系模型的完整性规则关系模型中有三类完整性约束：实体完整性、关系模型中有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。参照完整性和用户定义的完整性。实体完整性和参照完整性是关系模型必须满足实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。性，应该由关系系统自动支持。用户定义的
19、完整性是应用领域需要遵循的约束用户定义的完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束。条件，体现了具体领域中的语义约束。规则规则3.1 实体完整性（实体完整性（Entity Integrity）规则：）规则：若属性（指一个或一组属性）若属性（指一个或一组属性）A是基本关系是基本关系R的主属性。则的主属性。则A不能取空值。不能取空值。例如例如:在关系在关系S(SNO,SNAME,SEX,AGE,SDPET)中，中，SNO这个属性为主码，则这个属性为主码，则SNO不能取空值。不能取空值。3.2.1 关系的三类完整性约束 实体完整性要求关系中元组在组成主键的属性上不能有空值。如实体
20、完整性要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标织元组的作用。果出现空值，那么主键值就起不了惟一标织元组的作用。对于实体完整性规则几点说明 实体完整性规则是针对基本关系而言的。一个基本实体完整性规则是针对基本关系而言的。一个基本关系通常对应现实世界的一个实体集。例如学生关系关系通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。对应于学生的集合。现实世界中的实体是可区分的，即它们具有某种唯现实世界中的实体是可区分的，即它们具有某种唯一性标识。例如每个学生都是独立的个体，是不一样一性标识。例如每个学生都是独立的个体，是不一样的。的。关系模型中以主码
21、作为唯一性标识。关系模型中以主码作为唯一性标识。主码中的属性即主属性不能取空值。如果主属性取主码中的属性即主属性不能取空值。如果主属性取空值，就说明存在某个不可标识的实体，即存在不可空值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与第区分的实体，这与第点相矛盾，因此这个规则称为点相矛盾，因此这个规则称为实体完整性。实体完整性。定义定义2.3 参照完整性规则的形式定义如下：参照完整性规则的形式定义如下：如果属性集如果属性集K是关系模式是关系模式R1的主键，的主键，K也是关也是关系模式系模式R2的外键，那么在的外键，那么在R2的关系中，的关系中，K的的取值只允许两种可能，或者为空值，或
22、者等于取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。关系中某个主键值。这条规则的实质是这条规则的实质是“不允许引用不存在的实不允许引用不存在的实体体”。在上述形式定义中，关系模式在上述形式定义中，关系模式R1的关系称为的关系称为“参照关系参照关系”，关系模式，关系模式R2的关系称为的关系称为“依依赖关系赖关系”。参照完整性规则由参照完整性建立了多表之间的对应关系由参照完整性建立了多表之间的对应关系参照完整性规则举例例例2.1 下面各种情况说明了参照完整性规则在关系中下面各种情况说明了参照完整性规则在关系中如何实现的。如何实现的。在关系数据库中有下列两个关系模式：在关系数据库中有
23、下列两个关系模式：S（S#，SNAME，AGE，SEX）SC（S#，C#，GRADE）据规则要求，关系据规则要求，关系SC中的中的S#值应该在关系值应该在关系S中出现。中出现。如果关系如果关系SC中有一个元组（中有一个元组（S7,C4,80），而学号），而学号S7却在关系却在关系S中找不到，那么我们就认为在关系中找不到，那么我们就认为在关系SC中引中引用了一个不存在的学生实体，这就违反了参照完整性用了一个不存在的学生实体，这就违反了参照完整性规则。规则。另外，在关系另外，在关系SC中中S#不仅是外键，也是主键的一部不仅是外键，也是主键的一部分，因此这里分，因此这里S#值不允许空。值不允许空。设
24、工厂数据库中有两个关系模式：设工厂数据库中有两个关系模式：DEPT(D#，DNAME)EMP(E#，ENAME，SALARY，D#)车间模式车间模式DEPT的属性为车间编号、车间名，的属性为车间编号、车间名，职工模式职工模式EMP的属性为工号、姓名、工资、所的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在车间的编号。每个模式的主键与外键已标出。在在EMP中，由于中，由于D#不在主键中，因此不在主键中，因此D#值允值允许空。许空。参照完整性规则举例参照完整性规则举例 设课程之间有先修、后继联系。模式如下：设课程之间有先修、后继联系。模式如下：R(C#，CNAME，PC#)
25、其属性表示课程号、课程名、先修课的课程号。其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，如果规定，每门课程的直接先修课只有一门，那么模式那么模式R的主键是的主键是C#，外键是，外键是PC#.。这里参。这里参照完整性在一个模式中实现。即每门课程的直照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。接先修课必须在关系中出现。用户定义的完整性规则 在建立关系模式时，对属性定义了数据类型，在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规用户
26、可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。例如理它们，不再由应用程序承担这项工作。例如学生的年龄定义为两位整数，范围还太大，我学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在们可以写如下规则把年龄限制在1530岁之间：岁之间：CHECK（AGE BETWEEN 15 AND 30）3.3 关系代数的基本运算 主要内容 传统的集合运算传统的集合运算专门的关系运算专门的关系运算关系代数表达式及其应用实例关系代数表达式及其应用实例 并（并（Union）v设关系设关系R和和
27、S具有相同的关系模式，具有相同的关系模式，R和和S的并是由的并是由属于属于R或属于或属于S的元组构成的集合，记为的元组构成的集合，记为RS。形。形式定义如下：式定义如下：vRSt|tR tS，t是元组变量，是元组变量，R和和S的的元数相同。元数相同。差（差（Difference）v设关系设关系R和和S具有相同的关系模式，具有相同的关系模式，R和和S的差是由的差是由属于属于R但不属于但不属于S的元组构成的集合，记为的元组构成的集合，记为RS。形式定义如下：形式定义如下：vRS t|tR tS，R和和S的元数相同。的元数相同。传统的集合运算举例关系运算举例关系运算举例交运算 交（交（interse
28、ction）v关系关系R和和S的交是由属于的交是由属于R又属于又属于S的元组构成的集的元组构成的集合，记为合，记为RS，这里要求，这里要求R和和S定义在相同的关系定义在相同的关系模式上。形式定义如下：模式上。形式定义如下：vRSttR tS，R和和S的元数相同。的元数相同。ABCa1a1a2b1b2b2c1c2c1ABCa1a1a2b2b3b2c2c2c1bBCa1 a2b2 b2c2 c1例例 R S R S 笛卡儿积运算 若若R有有m个元组，个元组，S有有n个元组，则个元组，则RS有有mn个元组。个元组。笛卡儿积笛卡儿积(Cartesian Product)v 设关系设关系R和和S的元数分
29、别为的元数分别为r和和s,定义定义R和和S的一个的一个(r+s)元的元组元的元组集合，每个元组的前集合，每个元组的前r个分量来自个分量来自R的一个元组，后的一个元组，后s个分量来自个分量来自S的一个元组，记为的一个元组，记为RS。vRS t|t=trRtsS专门的关系运算选择（选择（Selection）选择操作是根据某些条件对关系做水平分割，即选取符合条件的选择操作是根据某些条件对关系做水平分割，即选取符合条件的元组。条件可用命题公式（即计算机语言中的条件表达式）元组。条件可用命题公式（即计算机语言中的条件表达式）F表示。表示。F中的基本形式为：中的基本形式为：X1Y1：v其中其中表示比较运算
30、符表示比较运算符:，。，。vX1，Y1等是属性名，常量，或列序号。等是属性名，常量，或列序号。关系关系R关于公式关于公式F的选择操作用的选择操作用F（R）表示，形式定义为：）表示，形式定义为：F（R）t|tR F（t）=true 为选择运算符，为选择运算符，F（R）表示从）表示从R中挑选满足公式中挑选满足公式F为真的元组为真的元组所构成的关系。所构成的关系。例如，例如，23（R）表示从）表示从R中挑选第中挑选第2个分量值大于个分量值大于3的的元组所构成的关系。书写时，为了与属性序号区别起见，常量用元组所构成的关系。书写时，为了与属性序号区别起见，常量用引号括起来，而属性序号或属性名不要用引号括
31、起来。引号括起来，而属性序号或属性名不要用引号括起来。投影（Projection)这个操作是对一个关系进行垂直分割，消去某些列，这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列的顺序。并重新安排列的顺序。设关系设关系R是是k元关系，元关系，R在其分量在其分量Ai1，Aim（mk i1，im，为，为1到到k间的整数）上的投间的整数）上的投影用影用i1,.,im（R）表示，它是一个）表示，它是一个m元元组集合，元元组集合，形式定义为：形式定义为：i1，im（R）t|tti1，timt1，tkR 例如，例如，3，1（R）表示关系）表示关系R中取第中取第1、3列，组成列，组成新的关系，新关系
32、中第新的关系，新关系中第1列为列为R的第的第3列，新关系的第列，新关系的第2列为列为R的第的第1列。如果列。如果R的每列标上属性名，那么操的每列标上属性名，那么操作符作符的下标处也可以用属性名表示。例如，关系的下标处也可以用属性名表示。例如，关系R（A，B，C），那么），那么C，A（R）与）与3，1（R）是）是等价的。等价的。连接有两种：连接有两种：连接和连接和F连接（这里连接（这里是算术比较符，是算术比较符，F是公式）。是公式）。连接连接 vR St t=trR tsS v表达式表达式 表示元组表示元组tr的第的第i个分量、元组个分量、元组ts的第的第j个分量个分量满足满足操作。操作。F连接
33、连接 v F连接是从关系连接是从关系R和和S的笛卡儿积中选取属性间满足某一公的笛卡儿积中选取属性间满足某一公式式F的元组的元组,这里这里F是形为是形为F1F2Fn的公式，每个的公式，每个FP是形是形ij的式子，而的式子，而i和和j分别为关系分别为关系R和和S的第的第i、第、第j个分量的个分量的序号。序号。连接（join）运算ij例例 连连接和接和F连连接的例子接的例子.说明:1.也可以写成。24（RS)2.。连接运算举例 两个关系两个关系R和和S的自然连接的自然连接 操作具体操作具体计算过程如下：计算过程如下：v 计算计算RS；v 设设R和和S的公共属性是的公共属性是A1,AK，挑选，挑选RS
34、中满中满足足R.A1=S.A1，R.AK=S.AK的那些元组；的那些元组；v 去掉去掉S.A1，S.AK这些列。这些列。定义：定义：中中i1,im为为R和和S的全部属性，但公共属性只的全部属性，但公共属性只出现一次。出现一次。自然连接（natural join）ABCa1a1a2a2b1b2b3b456812BEb1b2b3b3b5371022AR.BCS.BEa1a1a1a1a2b1 b1 b2 b2 b355668b2 b3 b2 b3 b37 10 7 10 10AR.BCS.BEa1a1a2a2b1b2b3b35688b1b2b3b337102ABCEa1a1a2a2b1b2b3b35
35、68837102关系关系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)除法举例除法举例关系代数运算的应用实例(1)在在关关系系代代数数运运算算中中，把把由由五五个个基基本本操操作作经经过过有有限限次次复复合合的的式式子子称称为为关关系系代代数数表表达达式式。这种表达式的运算结果仍
36、是一个关系。这种表达式的运算结果仍是一个关系。例例2.7 设设教学数据库中有三个关系教学数据库中有三个关系：学生关系学生关系 S(S#,SNAME,AGE,SEX)选课关系选课关系 SC(S#,C#,GRADE)课程关系课程关系 C(C#,CNAME,TEACHER)用关系代数表达式表示查询语句。用关系代数表达式表示查询语句。(1)1)检索学习课程号为检索学习课程号为C2的学生学号与成绩。的学生学号与成绩。S#,GRADE(C#=C2(SCSC)(2)检检索学索学习课习课程号程号为为C2的学生的学号与姓名。的学生的学号与姓名。S#,SNAME(C#=C2(S S SCSC)(3)(3)检检索索
37、选选修修课课程名程名为为MATHS的学生学号与姓名。的学生学号与姓名。S#,SNAME(CNAME=MATHS(S S SCSC C C)(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 SC
38、SC)(7)(7)检索学习全部课程的学生姓名。检索学习全部课程的学生姓名。学生选课情况可用操作学生选课情况可用操作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)检索所
39、学课程包含学生检索所学课程包含学生S3S3所学课程的学生学号。所学课程的学生学号。学生选课情况可用操作学生选课情况可用操作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)关系代数运算的应用实例关系代数运算
40、的应用实例(2)关系代数运算的应用实例关系代数运算的应用实例(3)一般地有下列规律：一般地有下列规律：(1)对于只涉及到选择、投影、连接的查询对于只涉及到选择、投影、连接的查询可用下列表达式表示：可用下列表达式表示：(RS)或者或者(R S)(2)对于否定的操作对于否定的操作，一般要用差操作表示，例如，一般要用差操作表示，例如“检索不学检索不学C2课的课的学生姓名学生姓名”。用下列表达式表示：。用下列表达式表示：SNAME(S)-SNAME(CNO=C2(S SC)但不能用下式表示：但不能用下式表示：SNAME(CNOC2(S SC)对于检索对于检索具有具有“全部全部”特征特征的操作，一般要用
41、除法操作表示，例的操作，一般要用除法操作表示，例如如“检索学习全部课程的学生学号检索学习全部课程的学生学号”。用下列表达式表示：。用下列表达式表示：要用要用SNO,CNO(SC)CNO(C)表示，而不能写成表示，而不能写成 SNO(SCCNO(C)形式。形式。这是因为一个学生学的课程的成绩可能是不一样的。这是因为一个学生学的课程的成绩可能是不一样的。3.5 查询优化 主要内容查询优化的一般策略查询优化的一般策略代数表达式的等价变换规则代数表达式的等价变换规则优化算法优化算法 例例 设关系设关系R和和S都是二元关系，属性名分别为都是二元关系，属性名分别为A，B和和C，D。设有一个查询可用关系代数
42、表达式表示：设有一个查询可用关系代数表达式表示：E1=A（B=CD=99（RS）也可以把选择条件也可以把选择条件D=99移到笛卡儿积中的关系移到笛卡儿积中的关系S前面：前面：E2=A（B=C（RD=99（S）还可以把选择条件还可以把选择条件BC与笛卡儿积结合成等值连接形式：与笛卡儿积结合成等值连接形式：E3=A（R D=99（S）这三个关系代数表达式是等价的，但执行的效率大不一样。显然，这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求求El，E2，E3的大部分时间是花在连接操作上的。的大部分时间是花在连接操作上的。查询优化例子 可以分析出，可以分析出，在时空性能上在时空性能上，E3
43、最优，其次是最优，其次是E2，最，最后是后是E1。此例还可以看出，如何安排选择、投影和连接的。此例还可以看出，如何安排选择、投影和连接的顺序是个很重要的问题。顺序是个很重要的问题。查询优化的一般策略(1)在关系代数表达式中需要指出若干关系的操作在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。较高呢？这个问题称为查询优化问题。查询优化是实现关系系统的关键技术查询优化是实现关系系统的关键技术,它大大它大大减轻了用户
44、选择存取路径的负担减轻了用户选择存取路径的负担,用户使用关用户使用关系系统时系系统时,只要提出只要提出“做什么做什么”,不必指出不必指出“怎怎么做么做”。在关系代数运算中，笛卡儿积和连接运算是最在关系代数运算中，笛卡儿积和连接运算是最费时间的。费时间的。查询优化的一般策略(2)查询优化采用的一般策略是：查询优化采用的一般策略是：尽可能早地执行选择运算。在查询中这种变换最为重要，因为它可以尽可能早地执行选择运算。在查询中这种变换最为重要，因为它可以以元组为单位减小中间结果，从而使执行时间成数量级地减少。以元组为单位减小中间结果，从而使执行时间成数量级地减少。把先做笛卡儿积，后做选择结合起来。使之
45、成为一个连接运算。连接把先做笛卡儿积，后做选择结合起来。使之成为一个连接运算。连接运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿运算（特别是等值连接）要比笛卡儿积运算效率高得很多。当对笛卡儿积积RS的结果再做选择时，并且这个选择是对的结果再做选择时，并且这个选择是对R和和S的属性进行比较，在的属性进行比较，在这样的条件下，这个笛卡儿积和选择运算等价于一个连接。这样的条件下，这个笛卡儿积和选择运算等价于一个连接。一般对不含一般对不含R的属性或不含的属性或不含S的属性的比较，可以移到笛卡儿积运算前去做，这样做的属性的比较，可以移到笛卡儿积运算前去做，这样做比转换到连接更好。比转换到
46、连接更好。同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文件，同时计算一串选择和一串投影运算，以免分开运算造成多次扫描文件，从而节省了操作时间。从而节省了操作时间。找出表达式里的公共子表达式。如果公共子表达式的结果不是很大，找出表达式里的公共子表达式。如果公共子表达式的结果不是很大，并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个并且从外存读入比起计算它要节省许多时间，那么，预先计算一下这个公共子表达式是有好处的。公共子表达式是有好处的。子表达式内涉及到连接，但又不能把限定条件向内移入的那类表达式，子表达式内涉及到连接，但又不能把限定条件向内移入的那类表达式，一般属于这
47、一类。一般属于这一类。连接和笛卡儿积的交换律连接和笛卡儿积的交换律 E1 E2E1 E2E2 E1 E1 E2E2 E1 E1 E2 E2 E1 E2 E1 E1E1E2 E2 E1 E1E2E2连接和笛卡儿积的结合律连接和笛卡儿积的结合律 (E1 E2 (E1 E2）E3 E3E1 E1 (E2 E3E2 E3)(E1 E2)E3 (E1 E2)E3E1 (E2 E3)E1 (E2 E3)(E1 (E1E2)E2)E3 E3 E1E1(E2(E2E3)E3)投影的串接投影的串接 设设L1,L1,设设L2,LnL2,Ln为属性集，并且为属性集，并且 ,那么下式也成立那么下式也成立.选择的串接选
48、择的串接代数表达式的等价变换规则(1)v 选择和投影操作的交换选择和投影操作的交换代数表达式的等价变换规则(2)v 选择对笛卡儿积的分配律选择对笛卡儿积的分配律 这里要求F只涉及到E1中的属性。如果F形为F1F2，且F1只涉及到E1的属性，F2只涉及到E2的属性，则有 此外，如果F形为F1F2，且F1只涉及到E1的属性，F2只涉及到E1和E2的属性，则有：v 选择对并的分配律选择对并的分配律 E1和E2具有相同的属性名，或者E1和E2表达的关系的属性有对应性，则有：代数表达式的等价变换规则(3)v 选择对集合差的分配律选择对集合差的分配律 E1和E2的属性有对应性，则有：v 选择对自然联接的分
49、配律选择对自然联接的分配律 F只涉及到表达式E1和E2的公共属性，则有：（E1 E2）（E1）（E2）v 投影对笛卡尔的分配律投影对笛卡尔的分配律 L1是E1中的属性集，L2是E2中的属性集，则有：v 投影对并的分配律投影对并的分配律 E1和E2的属性有对应性，则有：代数表达式的等价变换规则(4)v 选择与联接操作的结合选择与联接操作的结合 （E1E2）E1E2（E1E2）E1E2v 并和交的交换律并和交的交换律 E1E2E2E1 E1E2E2E1v 并和交的结合律并和交的结合律 （E1E2）E3E1（E2E3）（E1E2）E3E1（E2E3）优化算法(1)代代数数优优化化是是利利用用上上面面
50、的的等等价价变变换换规规则则，对对关关系系表表达达式式进进行行优优化化，以以减减少少执执行行时时的的开开销销。虽虽然然不不能能保保证证最最优优，但但在在多多数数情情况况下下能能使使表表达达式式更更好好些些。在在关关系系代代数数表表达达式式中中，最最花花费费时时间间和和空空间间的的运运算算是是笛笛卡卡儿儿积积和和连连接接操操作作，为为此此，引引出出三三条条启启发发式式规规则则，用用于于对对表表达达式式进进行行转转换换，以以减减少少中中间间关系的大小。关系的大小。优先应用单项的选择和投影；优先应用单项的选择和投影；优先应用一般选择和投影；优先应用一般选择和投影；对笛卡儿积、并运算、差运算，若它们前