第3章关系数据模型与关系运算

1、 教学内容教学内容： 3.1 3.1 关系模型概述关系模型概述 3.23.2关系的键与关系的完整性关系的键与关系的完整性 3.3 3.3 从从ERER模型到关系模型模型到关系模型 3.4 3.4 关系代数关系代数 3.5 3.5 关系演算关系演算 3.63.6关系代数表达式的优化关系代数表达式的优化1第第3章章 关系数据模型与关系运算关系数据模型与关系运算教学目的教学目的 掌握关系的形式化定义及其有关概念，掌握关系的形式化定义及其有关概念， 关系的性质，关系模式，关系数据库与关系数据库模式的定关系的性质，关系模式，关系数据库与关系数据库模式的定义，义， 掌握超键、候选键、主键、外键和关系的三类

2、完整性的定义，掌握超键、候选键、主键、外键和关系的三类完整性的定义， 掌握从掌握从ER模型到关系模型转换规则，模型到关系模型转换规则， 掌握关系代数的运算，掌握关系代数的运算， 了解元组关系演算和域关系演算。了解元组关系演算和域关系演算。2教学重点教学重点 关系的性质关系的性质 超键、候选键、主键和外键超键、候选键、主键和外键 关系的三类完整性关系的三类完整性 从从ER模型到关系模型转换规则模型到关系模型转换规则 关系代数的运算。关系代数的运算。33.1关系模型概述关系模型概述 3.1.1 关系的形式化定义及其有关概念关系的形式化定义及其有关概念 3.1.2关系的性质关系的性质 3.1.3关系

3、、关系模式、关系子模式和存储模式关系、关系模式、关系子模式和存储模式 3.1.4关系数据库与关系数据库模式关系数据库与关系数据库模式43.1.1 关系的形式化定义及其有关概念关系的形式化定义及其有关概念 关系模型关系模型是用二维表的形式表示实体和实体间联系的数据模是用二维表的形式表示实体和实体间联系的数据模型，关系模型由型，关系模型由关系数据结构、关系操作集合和关系完整性关系数据结构、关系操作集合和关系完整性约束约束三部分组成的。三部分组成的。 关系模型的数据结构关系模型的数据结构关系。关系。 关系模型的操作关系模型的操作集合包括数据的插入、修改、删除操作。集合包括数据的插入、修改、删除操作。

4、 关系模型的完整性约束关系模型的完整性约束主要由实体完整性、参照完整性和用主要由实体完整性、参照完整性和用户自定义完整性组成。户自定义完整性组成。5域，笛卡儿积，关系域，笛卡儿积，关系 1.域域：一组具有相同数据类型的值的集合。例：一组具有相同数据类型的值的集合。例 男男，女女 。 2.笛卡儿积笛卡儿积：给定一组域：给定一组域D1，D2，Dn，则则D1，D2，Dn的笛卡儿积为：的笛卡儿积为： D1D2Dn =（d1，d2，dn）di Di，i1，2，n. 3.关系的定义关系的定义：D1 D2 Dn的子集称作在域的子集称作在域D1，D2，Dn上的关系，表示为：上的关系，表示为：R（D1，D2，D

5、n） 其中其中R指关系名，指关系名，n是关系是关系R中属性的个数，又称关系的目或中属性的个数，又称关系的目或度。度。63.1.2关系的性质关系的性质 1) 同一属性的数据具有同质性，即同一属性为同一类型，同一属性的数据具有同质性，即同一属性为同一类型，来自同一个域。来自同一个域。 2) 同一关系的各属性名不能重复。同一关系的各属性名不能重复。 3) 关系中属性顺序可以任意交换，即关系中的属性的位置关系中属性顺序可以任意交换，即关系中的属性的位置具有顺序无关性。具有顺序无关性。 4) 关系不允许出现相同的元组，即关系中不能有重复的行。关系不允许出现相同的元组，即关系中不能有重复的行。 5) 关系

6、中元组顺序可以任意交换，即关系中的元组位置具关系中元组顺序可以任意交换，即关系中的元组位置具有顺序无关性。有顺序无关性。 6) 关系中每一个属性值都是不可分解的。关系中每一个属性值都是不可分解的。 7关系举例关系举例8姓名姓名性别性别年龄年龄电话电话王宏王宏男男21216779564267795642138562789513856278954 4张明张明女女23236779563667795636138562452613856245268 8李利李利女女21216779263567792635135859786513585978654 4姓名姓名性别性别年龄年龄固定电固定电话话手机手机王宏王宏

7、男男212167795642677956421385627895413856278954张明张明女女232367795636677956361385624526813856245268李利李利女女212167792635677926351358597865413585978654修改3.1.3关系、关系模式、关系子模式和存储模式关系、关系模式、关系子模式和存储模式 1.关系模式关系模式：实际就是记录类型，包括：模式名、属性名、：实际就是记录类型，包括：模式名、属性名、各属性值域名及关系模式的主键、外键以及用户定义的完整各属性值域名及关系模式的主键、外键以及用户定义的完整性。性。 2关系关系：关

8、系模式在某一时刻的状态或内容。：关系模式在某一时刻的状态或内容。 3.关系子模式关系子模式：用户所用到的那部分数据的描述。：用户所用到的那部分数据的描述。 4. 存储模式存储模式：关系存储时的基本组织方式是文件，元组是文：关系存储时的基本组织方式是文件，元组是文件中的记录。件中的记录。93.1.4关系数据库与关系数据库模式关系数据库与关系数据库模式 关系数据库模式关系数据库模式：包括关系数据库中每个关系模式的定义、：包括关系数据库中每个关系模式的定义、关系模式中每个属性的定义，每个属性域的定义，每个关系关系模式中每个属性的定义，每个属性域的定义，每个关系实体完整性、参照完整性的定义和用户自定义

9、完整性定义等。实体完整性、参照完整性的定义和用户自定义完整性定义等。 关系数据库关系数据库：即关系数据库的值，是这些关系模式在某一个：即关系数据库的值，是这些关系模式在某一个时刻对应的关系的集合。时刻对应的关系的集合。103.2关系的键与关系的完整性关系的键与关系的完整性 3.2.1超键、候选键、主键和外键超键、候选键、主键和外键 3.2.2关系的完整性关系的完整性113.2.1超键、候选键、主键和外键超键、候选键、主键和外键 超键超键：在关系中能唯一标识元组的属性组合。：在关系中能唯一标识元组的属性组合。 候选键候选键：如果一个属性或属性组合能唯一标识元组，且又不：如果一个属性或属性组合能唯

10、一标识元组，且又不包含多余属性，那么这个属性或属性组合称为候选键。也即，包含多余属性，那么这个属性或属性组合称为候选键。也即，候选键是没有多余属性的超键。候选键是没有多余属性的超键。 主键主键：若一个关系中有多个侯选键，则选其中的一个为关系：若一个关系中有多个侯选键，则选其中的一个为关系的主键。的主键。 外键外键：又称作外关键字，若某个属性组：又称作外关键字，若某个属性组F是关系是关系R的主键，的主键，F又在关系又在关系S中出现，则中出现，则F是是S的外键，的外键，R称为被参照表或主表，称为被参照表或主表，S称为参照表或副表。称为参照表或副表。123.2.2关系的完整性关系的完整性 实体完整性

11、实体完整性：指关系中元组的主键属性值不能为空且主键值：指关系中元组的主键属性值不能为空且主键值不能重复，在不能重复，在SQL中一般通过主键（中一般通过主键（PRIMARY KEY）子）子句来实现。句来实现。 参照完整性参照完整性：若某个属性组：若某个属性组F是关系是关系R的主键，的主键，F又在关系又在关系S中出现，则中出现，则F是是S的外键，的外键，F在在S中的取值只有两种可能，或中的取值只有两种可能，或者取空值，或者等于者取空值，或者等于R中的某个主键值。参照完整性通过外中的某个主键值。参照完整性通过外键（键（FOREIGN KEY）子句来实现。）子句来实现。 用户定义完整性用户定义完整性：

12、根据应用环境的要求和实际的需要，对某：根据应用环境的要求和实际的需要，对某一具体应用所涉及的数据提出的约束性条件。包括一具体应用所涉及的数据提出的约束性条件。包括CHECK约束、默认值约束、唯一约束、不为空等约束。约束、默认值约束、唯一约束、不为空等约束。133. 3 从从ER模型到关系模型模型到关系模型 3.3.1实体的转换规则实体的转换规则 3.3.2联系的转换规则联系的转换规则 3.3.3 ER模型转变成关系模型实例模型转变成关系模型实例143.3.1实体的转换规则实体的转换规则 实体的属性就是关系模式的属性；实体的标识符就是关系模实体的属性就是关系模式的属性；实体的标识符就是关系模式的

13、主键式的主键 学生关系模式（学生关系模式（学号学号，姓名，性别，年龄，所在系，姓名，性别，年龄，所在系153.3.2联系的转换规则联系的转换规则 1.二元联系的转换二元联系的转换 1）若二个实体间的联系是若二个实体间的联系是1：1，将联系与某一端实体对应，将联系与某一端实体对应的关系模式合并，合并后在关系的属性中加入相关的另一个的关系模式合并，合并后在关系的属性中加入相关的另一个实体集的码和联系本身的属性，合并后关系的码不变。实体集的码和联系本身的属性，合并后关系的码不变。 可在两个实体类型转换成的两个关系模式中的任意一个关系可在两个实体类型转换成的两个关系模式中的任意一个关系模式的属性中加入

14、另一个关系模式的键和联系类型的属性。模式的属性中加入另一个关系模式的键和联系类型的属性。161）1：1联系联系方案一：方案一：主任（主任（编号编号，姓名，出生年月，姓名，出生年月，性别，学历，系编号，任职时性别，学历，系编号，任职时间）间）系（系（系编号系编号，系名），系名）方案二：方案二：主任（主任（编号编号，姓名，出生年月，姓名，出生年月，性别，学历）性别，学历）系（系（系编号系编号，系名，编号，任，系名，编号，任职时间）职时间）172）1：N联系联系 2）若二个实体间的联系是若二个实体间的联系是1：N，将，将 1端实体的键和联系的端实体的键和联系的属性加入属性加入N端实体转变成的关系模式

15、中。端实体转变成的关系模式中。182）1：N联系联系部门（部门（部门号部门号、部门名）、部门名）职工（职工（职工号职工号、职工名、性别、职工名、性别、出生年月、电话，部门号，入出生年月、电话，部门号，入职时间）职时间）193）弱实体）弱实体 若实体间的联系是若实体间的联系是1：N的，而且在的，而且在N端实体类型为弱实体。端实体类型为弱实体。 转换成的关系模式中将转换成的关系模式中将1端实体类型端实体类型(父表父表)的键作为外键放的键作为外键放在在N端的弱实体端的弱实体(子表子表)中中。 弱实体的主键由父表的主键与弱实体本身的候选键组成。弱实体的主键由父表的主键与弱实体本身的候选键组成。也也可以

16、为弱实体建立新的独立的标识符可以为弱实体建立新的独立的标识符ID。203）弱实体）弱实体 职工关系模式（职工关系模式（职工号职工号，职，职工名，性别，出生年月，电工名，性别，出生年月，电话）话） 社会关系模式（社会关系模式（职工号，称职工号，称呼呼，姓名，年龄，工作单位，姓名，年龄，工作单位，政治面貌）政治面貌）214）M：N联系联系 若二个实体间的联系是若二个实体间的联系是M：N的，则将联系类型也转换成一的，则将联系类型也转换成一个关系模式，其属性为两端实体类型的键加上联系类型的属个关系模式，其属性为两端实体类型的键加上联系类型的属性，而键为两端实体键的组合。性，而键为两端实体键的组合。22

17、4）M：N联系联系 学生（学号，姓名，年龄，学生（学号，姓名，年龄，性别，班级）性别，班级） 课程（课号，课名，学时，课程（课号，课名，学时，学分，工号）学分，工号） 教师（工号，教师名，职教师（工号，教师名，职称）称） 选课（学号，课号，成绩）选课（学号，课号，成绩）235)超类和子类的转换规则超类和子类的转换规则 将超类和子类各转换成一个关系模式，在子类转换成的关系将超类和子类各转换成一个关系模式，在子类转换成的关系模式（子表）中加入超类转换成关系模式（父表）的键，从模式（子表）中加入超类转换成关系模式（父表）的键，从而实现父表与子表的联系。而实现父表与子表的联系。24 学生（学生（学号学

18、号，姓名，年龄，姓名，年龄，性别，电话，联系地址）性别，电话，联系地址） 本科生（本科生（学号学号，所在系），所在系） 研究生（研究生（学号学号，研究方向，研究方向，导师）导师）2一元联系的转换一元联系的转换 同一实体集的实体间的联系，即自联系，同一实体集的实体间的联系，即自联系， 可按二元联系中的可按二元联系中的1:1、1:n和和m:n三种情况分别处理。三种情况分别处理。25 转换成的关系模式如下：转换成的关系模式如下： 课程课程(课号课号，课名，学分，课名，学分，学时，任课教师，先修课学时，任课教师，先修课号号) 转换成的关系模式如下：转换成的关系模式如下： 版块版块(版块号版块号、版块名

19、、版块名、版主，父版块号版主，父版块号) 26 转换成的关系模式如下：转换成的关系模式如下： 零件（零件号，零件名，零件（零件号，零件名，规格）规格） 组成（零件号，子零件组成（零件号，子零件号，数量）号，数量）273三个或三个以上实体集间的多元联系三个或三个以上实体集间的多元联系 三个或三个以上实体间的一个多元联系可以转换为一个关系三个或三个以上实体间的一个多元联系可以转换为一个关系模式，该关系的属性为多元联系相连的各实体的码以及联系模式，该关系的属性为多元联系相连的各实体的码以及联系本身的属性，码为各实体码的组合。本身的属性，码为各实体码的组合。2829 转换成的关系模式如下：转换成的关系

20、模式如下： 顾客（顾客（顾客编号顾客编号，顾客名，顾客电话，顾客地址，顾客性别），顾客名，顾客电话，顾客地址，顾客性别） 收银员（收银员（工号工号，姓名，性别，年龄，电话，家庭地址），姓名，性别，年龄，电话，家庭地址） 商品（商品（商品号商品号，商品名，品牌，价格），商品名，品牌，价格） 销售（销售（顾客编号，工号，商品号顾客编号，工号，商品号，数量，购物时间），数量，购物时间）303.3.3 ER模型转变成关系模型实例模型转变成关系模型实例31 转换成的关系模式如下：转换成的关系模式如下： 书表书表 (书号书号、书名、作者、价格、出版社、类型、书名、作者、价格、出版社、类型) 读者表读者表

21、(读者编号读者编号、读者名、读者性别、读者电话、读者名、读者性别、读者电话) 借阅归还表借阅归还表(借阅序号借阅序号，书号，读者编号，借阅时间，归还，书号，读者编号，借阅时间，归还时间，超期天数时间，超期天数)323.4 关系代数关系代数 关系查询语言根据其理论基础的不同分成两大类：关系查询语言根据其理论基础的不同分成两大类： 1)关系代数语言关系代数语言：用对关系的运算来表达查询要求的方式，：用对关系的运算来表达查询要求的方式，查询操作是以集合操作为基础运算的查询操作是以集合操作为基础运算的DML语言。语言。 2)关系演算语言关系演算语言：用谓词来表达查询要求的方式，查询操作：用谓词来表达查

22、询要求的方式，查询操作是以谓词演算为基础运算的是以谓词演算为基础运算的DML语言。关系演算又可按谓语言。关系演算又可按谓词变元的基本对象是元组变量还是域变量分为元组关系演算词变元的基本对象是元组变量还是域变量分为元组关系演算和域关系演算。和域关系演算。33关系代数基本运算关系代数基本运算 一类是一类是传统的集合运算传统的集合运算，包括，包括（并运算），（差运算）（并运算），（差运算），（交运算），（交运算），（广义笛卡儿积）。（广义笛卡儿积）。 另一类是另一类是专门的关系运算专门的关系运算，包括，包括（选择），（选择），（投影），（投影）， （联接），（联接），（除）等。（除）等。 1、并（、

23、并（UNION） 设有两个关系设有两个关系R和和S，它们具有相同的结构。，它们具有相同的结构。R和和S的并是由属于的并是由属于R或属于或属于S的元组组成的集合，运算符为的元组组成的集合，运算符为。记为。记为TRS，用，用公式表示如下公式表示如下 RS=t| t R t S RS前提前提:R和和S均是均是n目关系，且相应的属性取自同一个域。目关系，且相应的属性取自同一个域。 RS结果结果:仍为仍为n目关系，其数据由属于目关系，其数据由属于R或属于或属于S的元组组成。的元组组成。 RS2、差（、差（DIFFERENCE） R和和S的差是由属于的差是由属于R但不属于但不属于S的元组组成的集合，运算符

24、为的元组组成的集合，运算符为。记为。记为TRS。用公式表示如下：。用公式表示如下： R S = t | t R t S R S前提前提:R和和S均是均是n目关系，且相应的属性取自同一个域。目关系，且相应的属性取自同一个域。 R S结果结果:由属于由属于R但但 不属于不属于S的所有元组组成。的所有元组组成。R-S3、交（、交（INTERSECTION） R和和S的交是由既属于的交是由既属于R又属于又属于S的元组组成的集合，运算符为的元组组成的集合，运算符为。记为。记为TRS。用公式表示如下：。用公式表示如下： R S = t | t R t S RS前提前提:R和和S均是均是n目关系，且相应的属

25、性取自同一个域。目关系，且相应的属性取自同一个域。 RS结果结果:由即属于由即属于R又属于又属于S的元组组成。的元组组成。R-S4笛卡儿积运算笛卡儿积运算 设关系设关系R和和S的元数分别为的元数分别为r和和s。R和和S的笛卡尔积是个的笛卡尔积是个(r+s)元的元组集合，元组的前元的元组集合，元组的前r列是关系列是关系R的一个元组，后的一个元组，后s列是列是关系关系S的一个元组。，记为的一个元组。，记为RS。 若若R有有M个元组，个元组，S有有n个元组，则个元组，则RS是一个元数为（是一个元数为（r+s）的，）的， 有有mn个元组的关系。个元组的关系。 R和和S的笛卡儿积表示为：的笛卡儿积表示为

26、： RS = tr ts | tr R ts S . 在一个学生选课系统数据库中，有表在一个学生选课系统数据库中，有表3.15、3.16、3.17的三的三个关系个关系S、C和和SC，求，求SC S 。 1、选择选择 从关系中找出满足给定条件从关系中找出满足给定条件F的元组称为选择的元组称为选择，记为，记为F（R）。其中的条件。其中的条件F是以逻辑表达式给出的是以逻辑表达式给出的 ，该逻辑表达式的值，该逻辑表达式的值为真的元组被选取，公式如下：为真的元组被选取，公式如下： F（R）= t | t R F（t）= 真真 . F是逻辑表达式，取值为是逻辑表达式，取值为“真真”或或“假假”。 F由逻辑

27、运算符由逻辑运算符（非）、（非）、（与）和（与）和（或）联接各条件（或）联接各条件表达式组成表达式组成 条件表达式：条件表达式：XY. 是比较运算符，、是比较运算符，、 5= 计算机计算机 （ S ） sdept 计算机计算机 （ S ） 举例举例在学生选课数据库中查询在学生选课数据库中查询C2成绩在成绩在90分以上的所有选课记分以上的所有选课记录。录。 CNO= C2 GRADE90(SC ） 2= C2 390(SC ）投影投影 从关系中挑选若干属性组成的新的关系称为投影。记为：从关系中挑选若干属性组成的新的关系称为投影。记为： A（R）= t A | t R . 投影是分两步产生一个新的

28、关系：投影是分两步产生一个新的关系： 第一步选择指定的属性，形成一个可能含有重复行的表；第一步选择指定的属性，形成一个可能含有重复行的表； 第二步删除重复行，形成新的关系；第二步删除重复行，形成新的关系；联接运算联接运算 联接运算是从两个关系的笛卡尔积中选择属性间满足一定条联接运算是从两个关系的笛卡尔积中选择属性间满足一定条件的元组，可以定义为件的元组，可以定义为RS后再做选择。后再做选择。它是关系代数中它是关系代数中使用最频繁的操作之一。记作：使用最频繁的操作之一。记作： ABABR S R S 其中：其中：A A和和B B分别为分别为R R和和S S上度数相等且可比的属性组，上度数相等且可

29、比的属性组，是比是比较运算符。较运算符。ttr r t ts s| t| tr r R tR ts s S tS tr r At Ats s B B 联接运算是从联接运算是从R和和S的广义笛卡儿积的广义笛卡儿积RS中，选取符合中，选取符合AB条件的元组，即选择在条件的元组，即选择在R关系中关系中A属性组上的值与在属性组上的值与在S关系中关系中B属性组上的值满足比较操作属性组上的值满足比较操作的元组。的元组。 联接有三种：联接有三种：联接、联接、F联接联接(是算术比较符，是算术比较符，F是公式是公式)、自、自然联接。然联接。49 联接联接 联接是从关系联接是从关系R和和S的笛卡尔积中选取属性值满

30、足某一的笛卡尔积中选取属性值满足某一操操作的元组作的元组，记为：，记为：50 ijij R S R S i(r+j)i(r+j)(R(RS)S) 如果如果为等号为等号“= =”，那么这个联结操作称为等，那么这个联结操作称为等值连接。值连接。 这里这里i i和和j j 分别是关系分别是关系R R和和S S中第中第 i i个、第个、第j j个属性的序个属性的序号，号，可以是、可以是、等比较运算符等比较运算符中的一个。中的一个。F联接联接 F联接操作是从关系联接操作是从关系R和和S的笛卡尔积中选取属性值满足某一的笛卡尔积中选取属性值满足某一公式公式F的元组的元组，记为：，记为： R S F (RS)

31、 这里的这里的F是形为是形为F1F2Fn的公式，每一个的公式，每一个Fi都是形为都是形为i j的式子，而的式子，而i和和j 可以是属性名、常量、或者是关系可以是属性名、常量、或者是关系R、S中第中第 i个、第个、第j个属性的序号。个属性的序号。51 F (3)自然联接自然联接 自然联接是一种特殊的等值联接，它要求两个关系中进行比自然联接是一种特殊的等值联接，它要求两个关系中进行比较的分量必须是公共的属性组，并且在结果中把重复的属性较的分量必须是公共的属性组，并且在结果中把重复的属性列去掉。列去掉。 R R SSi1,.imi1,.im(R.A1=S.A1. R.AK=S.AKR.A1=S.A1

32、. R.AK=S.AK(R(RS)S) 具体计算过程如下：具体计算过程如下： 计算计算RS 挑选挑选RS中满足中满足R .A1=S.A1R.Ak=S.Ak的那些的那些元组元组 去掉去掉S.A1,， S.Ak的这些列。的这些列。52举例举例 查询学生雷大雨选修课程的课程号和成绩。查询学生雷大雨选修课程的课程号和成绩。 CNO,GRADE(SNAME=雷大雨雷大雨 (S SC) 或：或：CNO,GRADE (SNAME=雷大雨雷大雨 S.SNO=SC.SNO (SSC) 查询每个学生及其选修课程的情况。查询每个学生及其选修课程的情况。 S SC 或：或：S.SNO=SC.SNO (SSC)534.

33、除法除法 给定关系给定关系R(X,Y)和和S(Y,Z)，其中，其中X，Y，Z为属性组。为属性组。R中的中的Y和和S中的中的Y可能有不同的属性名，但必须出自相同的域集。可能有不同的属性名，但必须出自相同的域集。R和和S的除运算的除运算RS得到一个新的关系得到一个新的关系P（X），），P是是R中满足中满足下列条件的元组在下列条件的元组在X属性上的投影：这些元组在属性上的投影：这些元组在X上分量值上分量值x的像集的像集YX包含包含S在在Y上投影的集合。上投影的集合。 54关系除法运算分下面关系除法运算分下面4步进行：步进行： （1) 将被除关系的属性分为像集属性和结果属性两部分：将被除关系的属性分为

34、像集属性和结果属性两部分：与除关系相同的属性属于像集属性，不相同的属性属于结果与除关系相同的属性属于像集属性，不相同的属性属于结果属性。属性。 （2) 在除关系中，对与被除关系相同的属性（像集属性）在除关系中，对与被除关系相同的属性（像集属性）进行投影，得到除目标数据集。进行投影，得到除目标数据集。 （3) 将被除关系分组，分组原则是，结果属性值一样的元将被除关系分组，分组原则是，结果属性值一样的元组为一组。组为一组。 （4) 逐一考察每个组，如果它的像集属性值中包括除目标逐一考察每个组，如果它的像集属性值中包括除目标数据集，则对应的结果属性值应属于该除法运算结果集数据集，则对应的结果属性值应

35、属于该除法运算结果集5556举例举例 用关系代数表示用关系代数表示:选修了全部课程的学生学号。选修了全部课程的学生学号。 SNO,CNO (SC) CNO (C) 用关系代数表示用关系代数表示:全部学生都选修了的课程号。全部学生都选修了的课程号。 SNO,CNO (SC) SNO (S) 57五、扩充的关系代数操作五、扩充的关系代数操作 1.外联接外联接（outer join） 在在R和和S做自然联接时，把原该舍弃的元组也保留在新关系做自然联接时，把原该舍弃的元组也保留在新关系中，同时在这些元组新增加的属性上填上空值（中，同时在这些元组新增加的属性上填上空值（null），这），这种操作称为种操

36、作称为“外联接外联接”操作，用符号操作，用符号R S表示。表示。 2左外联接左外联接 如果如果R和和S做自然联接时，把做自然联接时，把R中原该舍弃的元组放到新关系中原该舍弃的元组放到新关系中，那么这种操作称为中，那么这种操作称为“左外联接左外联接”操作，用符号操作，用符号: R S表表示。示。 58 3右外联接右外联接 如果如果R和和S做自然联接时，把做自然联接时，把S中原该舍弃的元组放到新关系中原该舍弃的元组放到新关系中，那么这种操作称为中，那么这种操作称为“右外联接右外联接”操作，用符号操作，用符号: R S表表示。示。 4. 半联接（半联接（semijoin） 关系关系R和和S的半联接操

37、作记为的半联接操作记为R S，就是，就是R和和S的自然联接的自然联接在关系在关系R的属性集上的投影的属性集上的投影: 59603.4.3 关系代数表达式实例关系代数表达式实例 S（SNO，SNAME，SEX，AGE，SDEPT） C(CNO,CNAME,CDEPT,TNAME) SC(SNO,CNO,GRADE) 检索计算机系的全体学生的学号、姓名和性别。检索计算机系的全体学生的学号、姓名和性别。 SNO,SNAME(SDEPT=计算机计算机(S) 61 求年龄大于求年龄大于19岁的学生的学号、姓名。岁的学生的学号、姓名。 SNO,SNAME(AGE19 (S) 查询轨道交通系年龄小于查询轨道

38、交通系年龄小于20岁的学生的学号、姓名和年龄。岁的学生的学号、姓名和年龄。 SNO,SNAME，AGE(SDEPT=轨道交通轨道交通 AGE=90S.SNO=SC.SNO C.CNO=SC.CNO (SSCC) 63 查询出学号为查询出学号为s02的学生的学号，姓名，所选课程名及成绩。的学生的学号，姓名，所选课程名及成绩。 SNO,SNAME，CNAME，GRADE(CNO=S02(S SC C) 或或SNO,SNAME，CNAME，GRADE (CNO=S02S.SNO=SC.SNO C.CNO=SC.CNO (SSCC) 检索选修课程号为检索选修课程号为C2或或C4的学生的学号。的学生的学

39、号。 SNO (CNO=C4 (SC) SNO (CNO=C2 (SC) 或或 SNO (CNO=C4 CNO=C2 (SC) 64 检索至少选修课程号为检索至少选修课程号为C2和和C4的学生的学号。的学生的学号。 SNO (CNO=C4 (SC) SNO (CNO=C2 (SC) 或或 1 (2=C4 5=C2 (SCSC) 检索没有选修检索没有选修C2课程的学生的学号和姓名。课程的学生的学号和姓名。 SNO,SNAME (S)SNO,SNAME(CNO=C2 S.SNO=SC.SNO (SSC) 检索选修了全部课程的学生的学号、姓名和所在系。检索选修了全部课程的学生的学号、姓名和所在系。

40、SNO,SNAME,SDEPT,CNOS.SNO=SC.SNO (SSC) CNO (C)65 检索选修了全部课程的学生的学号、姓名和所在系。检索选修了全部课程的学生的学号、姓名和所在系。 SNO,SNAME,SDEPT,CNOS.SNO=SC.SNO (SSC) CNO (C) 查询选修了查询选修了S01学生所选全部课程的学生学号，姓名。学生所选全部课程的学生学号，姓名。 SNO,SNAME, CNOS.SNO=SC.SNO (SSC) CNOSNO=S01 (SC) 663.5 关系演算关系演算 关系演算的概念最早是由关系演算的概念最早是由E.F.Codd提出来的，关系演算是提出来的，关系

41、演算是以数理逻辑中的谓词演算为基础的，按所用变量的不同分为以数理逻辑中的谓词演算为基础的，按所用变量的不同分为元组关系演算和域关系演算。元组关系演算和域关系演算。 3.5.1 元组关系演算元组关系演算 3.5.2域关系演算域关系演算673.5.1 元组关系演算元组关系演算 元组元组关系演算关系演算以元组以元组变量变量作为谓词变元的基本对象。在元组作为谓词变元的基本对象。在元组关系演算中，元组关系演算表达式（简称为元组表达式）用关系演算中，元组关系演算表达式（简称为元组表达式）用表达式：表达式： tQ（t） 来表示，其中来表示，其中t是元组变量，它表示一个定长的元组，是元组变量，它表示一个定长的

42、元组，Q(t)是是公式公式，公式是由元组关系演算的，公式是由元组关系演算的原子原子公式组成的。公式组成的。68元组关系演算的原子公式元组关系演算的原子公式 （1）R(t)， 其中其中R是关系名，是关系名，t是元组变量。是元组变量。 tR（t） （2）ti uj，其中，其中t和和u都是元组变量，都是元组变量，是算术是算术比较运算比较运算符符。 （3）ti a或或a ti，这里，这里a是一个常量。是一个常量。69公式中变量的递归定义如公式中变量的递归定义如下下 每个原子公式是一个公式。其中的元组变量是自由变量每个原子公式是一个公式。其中的元组变量是自由变量; 如果如果 1和和 2是元组关系演算公式

43、，则是元组关系演算公式，则: 1 2, 1 2, 1也是元组关系演算公式也是元组关系演算公式; 若若 是元组关系演算公式，则是元组关系演算公式，则( t)( )也是元组关系演算公式也是元组关系演算公式; 若若 是元组关系演算公式，则是元组关系演算公式，则( t)( )也是元组关系演算公式也是元组关系演算公式; 在元组演算公式中，各种运算符的优先次序为：在元组演算公式中，各种运算符的优先次序为： 括号括号,算术比较运算符算术比较运算符, , 、 有限次地使用上述五条规则得到的公式是元组关系演算公有限次地使用上述五条规则得到的公式是元组关系演算公式，式， 其他公式不是元组关系演算公式。其他公式不是

44、元组关系演算公式。70用元组表达式形式表示下列查用元组表达式形式表示下列查询询 检索计算机系的全体学生的学号、姓名和性别。检索计算机系的全体学生的学号、姓名和性别。 t|( u)(S(u)u5=计算机计算机tl=u1 t2=u2 t3=u3) 求年龄大于求年龄大于19岁的学生的学号、姓名。岁的学生的学号、姓名。 t|( u)(S(u)u419tl=u1 t2=u2) 查询轨道交通系年龄小于查询轨道交通系年龄小于20岁的学生的学号、姓名和年龄。岁的学生的学号、姓名和年龄。 t|( u)(S(u)u419t1=u1t2=u2 ) 查询轨道交通系年龄小于查询轨道交通系年龄小于20岁的学生的学号、姓名

45、和年龄。岁的学生的学号、姓名和年龄。 t1,t2,t3|( u1)( u2)( u3)( u4)( u5)(S(u) u420u5=” 轨道交通轨道交通”t1=u1t2=u2 t3=u4)753.6 关系代数表达式的优化关系代数表达式的优化 在关系代数表达式中需要指出若干关系的操作步骤。在关系代数表达式中需要指出若干关系的操作步骤。 系统系统应该以什么样的操作顺序，才能做到既省时间，又省空间，应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？而且效率也比较高呢？ 如何花费较少的时间和空间，有效地执行笛卡儿积操作如何花费较少的时间和空间，有效地执行笛卡儿积操作.76一、查询

46、优化的总目标一、查询优化的总目标 选择有效的策略，选择有效的策略， 求得给定关系代数表达式的值，求得给定关系代数表达式的值， 达到提高达到提高DBMS系统效率的目标。系统效率的目标。例例: :学生数据库：学生数据库：S(S(SNOSNO,SNAME,SEX,AGE,SDEPT),SNAME,SEX,AGE,SDEPT) C( C(CNOCNO,CNAME,CDEPT,TNAME),CNAME,CDEPT,TNAME) SC( SC(SNO,CNOSNO,CNO,GRADE),GRADE)检索学号为检索学号为S1S1的学生选修的课程号，课程名，成绩。用关系代数的学生选修的课程号，课程名，成绩。用

47、关系代数表达式表达式 E1 =E1 =CNO,CNAME,GRADECNO,CNAME,GRADE（S.SNO=SC.SNOSNO=S1S.SNO=SC.SNOSNO=S1（C CSCSC） E2 =E2 =CNO,CNAME,GRADECNO,CNAME,GRADE（SNO=S1SNO=S1（C C SC SC） E3 = CNO,CNAME,GRADECNO,CNAME,GRADE（C C SNO=S1SNO=S1（SC） 二、代数表达式的等价变换规则二、代数表达式的等价变换规则 1、 联接和笛卡儿积的交换律联接和笛卡儿积的交换律 E1 E1 E2 E2 E1 E2 E2 E1 E1 E2

48、 E2 E1 E1 E2 E2 E1 E1 E1 E2 E2 E2 E2 E1 E1 F F 2 2联接和笛卡儿积的结合律联接和笛卡儿积的结合律 （E1 E2 E1 E2 ） E3 E1 E3 E1 （E2 E3E2 E3） （E1 E2E1 E2） E3 E1 E3 E1 （E2 E3E2 E3） （E1 E1 E2 E2） E3 E1 E3 E1 （E2E2 E3 E3） F1 F1 F2 F2 3. 3. 投影的串接投影的串接 设设L1L1，L2L2，LnLn为属性集，并且为属性集，并且L1L1 L2L2 LnLn， 成立：成立： L1L1（L2L2（LnLn（E E）L1L1（E E）

49、4 4 选择的串接选择的串接 F1F1（F2F2（E E）F1 F2F1 F2（E E） 由于由于F1 F2 = F2 F1F1 F2 = F2 F1，选择的交换律也成立：，选择的交换律也成立： F1F1（F2F2（E E）F2F2（F1F1（E E） 5 5 选择和投影操作的交换选择和投影操作的交换 L L（F F（E E）F F（L L（E E）要求条件要求条件F F只涉及到只涉及到L L中的属性中的属性, ,如果如果F F还涉及到不在还涉及到不在L L中的属性集中的属性集L1L1： L L（F F（E E）L L（F F（LL1LL1（E E）6 6 选择对笛卡儿积的分配律选择对笛卡儿积

50、的分配律 F F（E1E1E2E2）F F（E1E1）E2E2 F F（E1E1E2E2）F1F1（E1E1）F2F2（E2E2） F F（E1E1E2E2）F2F2（F1F1（E1E1）E2E2） 7. 7. 选择对并的分配律选择对并的分配律 F F（E1E2E1E2）F1F1（E1E1）F2F2（E2E2） 8 8 选择对集合差的分配律选择对集合差的分配律 F F（E1E1E2E2）F F（E1E1）F F（E2E2） 9 9选择对自然联接的分配律选择对自然联接的分配律 F F（E1 E1 E2 E2）F F（E1E1） F F（E2E2）1010 投影对笛卡儿积的分配律投影对笛卡儿积的分

51、配律 L1L2L1L2（E1E1E2E2）L1L1（E1E1）L2L2（E2E2）1111 投影对并的分配律投影对并的分配律 L L（E1E2E1E2）L L（E1E1）L L（E2E2）1212 选择与联接操作的结合选择与联接操作的结合 F1F1（E1 E2E1 E2） E1 E1 E2E2 1313 并和交的交换律并和交的交换律 E1E2 E2E1 E1E2 E2E1 E1E2 E2E1 E1E2 E2E11414 并和交的结合律并和交的结合律 （E1E2E1E2）E3 E1E3 E1（E2E3E2E3） （E1E2E1E2）E3 E1E3 E1（E2E3E2E3） F2 F2F2 三、优

52、化的一般策略三、优化的一般策略 (1-6)(1-6)(1) (1) 在关系代数表达式中尽可能早地执行选择操作。在关系代数表达式中尽可能早地执行选择操作。(2) (2) 把笛卡儿积和其后的选择操作合并成把笛卡儿积和其后的选择操作合并成F F联接运算。联接运算。(3) (3) 同时计算一连串的选择和投影操作，以免分开运算造成多次同时计算一连串的选择和投影操作，以免分开运算造成多次 扫描文件，节省操作时间。扫描文件，节省操作时间。(4) (4) 如在一个表达式中多次出现某个子表达式，如在一个表达式中多次出现某个子表达式，可先对可先对该子该子 表达式表达式进行进行计算计算并并保存结果，以免重复计算。保存结果，以免重复计算。 (5) (5) 适当地对关系文件进行预处理。适当地对关系文件进行预处理。 (6) (6) 在计算表达式前应先估计一下怎么计算合算。在计算表达式前应先估计一下怎么计算合算。 三、关系代数表达式的优化算法三、关系代数表达式的优化算法 输入：输入：一棵关系代数表达式的语法树。一棵关