第2章 关系模型和关系运算

1、第二章 关系模型和关系运算理论2.1 关系模型的基本概念2.1.1 基本术语1、关系：所谓关系就是一种规范化的二维表，如图所示。关系模型的数据结构就是这种被称为“关系”的二维表，也就是说关系模型用二维表结构来表示数据及数据之间的联系。从数学角度上看：“关系”就是“集合”。 学生学号姓名性别民族生日电话家庭住址图门毕力格男蒙古族1987-3-6努恩吉雅女蒙族1988-10-2李强男汉族1986-4-5王蕾女回族1986-5-5石艳女汉族1989-12-10李强男汉族1990-2-1 课程课号课名课程类型学时要求教室要求先导课号计算机导轮专业54普通C语言程序设计专业72多媒体C+专业72多媒体数

2、据结构专业90多媒体数据库原理专业90多媒体VB程序设计公共80实验室 教学班教学班号课号学年学期容纳人数-012008160-022008160-012008180-022008180-012008160选课学号教学班号成绩-01-0170-01-01-022、属性：我们把表的列称为属性(又称字段或数据项)。例如：学生表有七列，那么它就有七个属性。每个属性都包括属性名、属性的取值类型及范围三个方面。例如：学生表的第一个属性的名称是：学号，其取值类型是字符串，取值范围是数字字符。3、关系模式：我们把 关系名称(属性1名称，属性2名称，属性n名称) 称为一个关系的模式。例如：学生（学号，姓名，性

3、别，民族，生日，电话，家庭住址）就是学生关系的模式。4、元组：我们把表的行称为元组（又称记录）。5、候选键：如果一个属性集能唯一地标识元组，且又不含有多余的属性，那么我们把这个属性集称为候选键。例如：“学号”属性是学生关系的候选键，（学号，教学班号）是选课关系的候选键。6、主键：用户可以从候选键中选出一个作为主键。例如：我们可以选“学号”属性作为学生关系的主键7、外键：如果关系模式R中的某属性集A是另一个关系模式的主键，那么我们称A是关系模式R的外键。例如：“选课”关系中的“学号”属性就是“学生”关系的主键，因此，我们称“学号”属性是“选课”关系的外键。2.1.2 关系的数学定义和性质一、定义

4、从数学上看：关系是一个属性数目相同的元组的集合。二、性质1、关系中每一个属性都是不可分解的。2、关系中不允许出现重复元组。3、由于关系是一个集合，因此不考虑元组之间的顺序。4、关系的属性也是无序的。2.1.3 关系模型的三类完整性规则了维护数据库中数据与现实世界的一致性，关系数据库的数据更新操作必须遵守下列三类完整性约束规则，具体如下：1、实体完整性规则：这条规则要求“关系中的元组在组成主键的属性上不能有空值”。例如：一个元组插入“学生”关系时，学号不能没有值。2、参照完整性规则：这条规则要求“不能引用不存在的元组”。例如：“选课”关系中不能出现“学生”关系中没有的“学号”。3、用户定义的完整

5、性规则：这是针对某一具体数据的约束条件，有应用环境决定。例如：根据学校的实际规定，可以对“选课”关系的成绩属性作约束：0成绩1002.1.4 ER模型向关系模型的转换规则一、实体类型的转换规则将每个实体类型转换成一个关系模式，实体的属性即为关系模式的属性，实体标识符即为关系模式的属性。二、实体之间联系的转换规则1、若实体间联系是1：1的，可以在两个实体转换的关系模式中的任何一个关系模式的属性中加入另一个关系模式的键以及联系类型的属性。示例12、若实体间联系是1：n的，则在n端实体类型转换成的关系模式中加入1端的键和联系类型的属性。示例23、若实体间的联系是m：n的，则将联系类型也转换成一个关系

6、模式，其属性为两端实体的键和联系类型的属性。示例3三、示例2.1.5 关系模型的三级体系结构一、模式我们称构成一个数据库的所有关系模式为数据库模式。二、子模式子模式是用户所用到的那部分数据的描述。三、存储模式数据在计算机的外存储器（如：磁盘）上的存储结构及特征的描述。2.1.6 关系模型的优点1、关系模型的数据结构单一、简单。2、关系模型的逻辑结构和相应的操作完全独立于数据存储方式，具有高度的数据独立性。3、关系模型的数学基础比较坚实。4、关系数据库语言与一阶谓词逻辑的固有内在联系，为以关系数据库为基础的推理系统和知识库系统的研究开发提供了方便。2.1.7 关系查询语言和关系运算关系数据库的数

7、据操纵语言（DML）的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各种检索要求；更新语句用于描述用户进行插入、删除、修改等操作。从计算机语言的角度看，后者是在前者的基础上工作，前者比后者复杂。但前者有理论基础，是主要研究对象。关于查询的理论称为“关系运算理论”。关系查询语言根据其理论基础的不同分成三类：1、关系代数语言：查询操作是以集合操作为基础的运算。2、关系演算语言：查询操作是以谓词演算基础的运算。3、关系逻辑语言：查询操作是以ifthen逻辑操作为基础的运算。2.2 关系代数2.2.1 关系代数的五个基本操作关系代数是以关系为运算对象的一组高级运算的集合。由于关系是属性个数相

8、同的元组的集合，因此集合代数的操作就可以引入到关系代数中。1、并（Union）设关系R和关系S具有相同的模式，我们把 RSt | t R t S ,t 是元组变量 称为R和S的并。从定义可见R和S的并是由属于R或属于S的元组组成的集合。例如： R S RSAB a1 b1 a2 b2 a3 b3AB a1 b1 a2 b3 a3 b3AB a1 b1 a2 b2 a2 b3 a3 b32、差（Difference）设关系R和关系S具有相同的模式，我们把 RSt | t R t S ,t 是元组变量称为R和S的差。从定义可见R和S的差是由属于R而不属于S的元组组成的集合。 R S RSAB a1

9、 b1 a2 b2 a3 b3AB a1 b1 a4 b4 a3 b3AB a2 b2 3、笛卡儿积（Cartesian Product）设关系R和关系S的元数（关系的元数就是关系所具有的属性个数）分别为r和s。定义R和S的笛卡尔积是一个（r+s）元的元组集合，其每个元组的前r个分量来自R的一个元组，后s个分量来自S的一个元组，记为 RS 。RSt | t=tr,tstrRts S 例如：关系R 关系 S A B a1 b1 a2 b2 C D E c1 d1 e1 c1 d2 e1 关系 RS A B C D Ea1 b1 c1 d1 e1 a1 b1 c1 d2 e1 a2 b2 c1 d

10、1 e1 a2 b2 c1 d2 e1 4、投影（Projection）这个操作是对一个关系进行垂直分割，削去某些列，并重新安排列的顺序，再删去重复元组。关系R（A1，A2，An）在属性列Ai1，Ai2，Aik 的投影记为：(Ai1，Ai2，Aik ) （R） 例如： 关系R 在属性 A ， B 上的投影为：(A，B )(R) A B C D Ea1 b1 c1 d1 e1 a1 b1 c1 d2 e1 a2 b2 c1 d1 e1 a2 b2 c1 d2 e1 A B a1 b1 a2 b2 5、选择（Selection）这个操作是根据某些条件对关系的元组进行筛选。关系R关于公式F 的选择操

11、作用 (F)（R）表示。 (F)（R）=t | t R F（t）=true公式F是由R的属性、常数，关系运算符等构成的逻辑表达式。举例： R (A=a1 or B=b2)（R）ABC a1 b1 c1 a1 b2 c2 a2 b1 c3 a2 b2 c4 a2 b3 c4 a3 b2 c1ABC a1 b1 c1 a1 b2 c2 a2 b2 c4 a3 b2 c1 以上五个操作组成了关系代数的完备的操作集。2.2.2 关系代数的四个组合操作1、交(intersection) 关系R和S的交是由既属于R又属于S的元组构成的集合，记为：RS，这里要求R和S定义在相同关系模式上。形式定义如下： R

12、St | t R t S ,t 是元组变量，R和S的元数相同。由于RS=R-（R-S），因此交操作不是一个独立的操作。2、联接（join） 连接有两种：连接和F连接（这里是算术比较符，F是公式）。 连接连接是从关系R和S的笛卡尔积中选取属性值满足某一操作的元组，记为：R ij S ，这里i和j分别是关系R和S中的第i个、第j个属性的序号。形式定义为：R ij S=t | t=tr,tstrRts St t此处t是元组tr的第i个分量，t是元组ts的第j个分量，t t表示这两个分量值满足比较。显然连接是由笛卡尔积和选择操作组合而成。既：R ij S=i(r+j)（RS）该式表示连接是在关系R和S

13、的笛卡尔积中挑选第i个分量和第(r+j)个分量满足比较操作的元组。如果是“=”则称该连接是等值连接。F 连接F连接是从关系R和S的笛卡尔积中挑选属性值满足某一公式F的元组，记为：R F S这里F是形为F1F2Fn 的公式，每个Fp（p=1,2n）是形为ij的式子（i和j分别为关系R和S的第i个分量和第j个分量的序号。）举例： R S R S R S 21 211s0），R的属性集包含S的属性集。那么RS是一个(r-s)元的元组集合。（RS）是满足下列条件的最大关系：RS中每个元组t与S中每个元组u组成的新元组必在关系R中。为方便，我们假设S的属性为R的后s个属性。RS的计算过程如下：T=1，2

14、，r - s（R）W=（TS）R （计算TS中不在R的元组）V=1，2，r - s（W）RSTV举例：学号 姓名S1 BAOS2 GUS3 ANS4 LI R学号 姓名 课号 课名S1 BAO C1 DBS1 BAO C2 OSS1 BAO C3 DSS1 BAO C4 MISS2 GU C1 DBS2 GU C2 OSS3 AN C2 OSS4 LI C2 OSS4 LI C4 MIS课号 课名C2 OS S1 课号 课名C2 OSC4 MIS S2学号 姓名S1 BAOS4 LI 课号 课名C1 DBC2 OSC4 MIS S3学号 姓名S1 BAO 2.2.3 关系代数运算的应用实例题目

15、：设教学数据库中有三个关系学生关系：S（S#，SNAME，AGE，SEX）选课关系：SC（S#，C#，GRADE）课程关系：C（C#，CNAME，TEACHER）请用关系代数表达下面每个查询1、检索学习课号为C2的学生的学号与成绩。2、检索选修课号为C2或C4的学生学号。3、检索选修课名为OS的学生的学号及姓名。4、检索至少选修了课号为C2和C4的学生学号。5、查询至少选了两门课程的学生学号。选课关系：SC（S#，C#，GRADE） S1 c1 S1 c2 S2 c1 S3 c4 1=4 AND 25 (SCxSC)6、检索没选C2课的学生的姓名及年龄。 sname,age (S#(S) -

16、S# (C#=C2(SC) ) S)7、检索选修了全部课程的学生学号。 S# (S#,C# (SC)C# (C)8、检索所学的课程包含学生S3所学课程的学生学号。 s#,C# (SC)C# (S#=S3 (SC)解答：1、检索学习课号为C2的学生学号与成绩。S#, GRADE(C#=C2(SC)2、检索选修课号为C2或C4的学生学号。S#(C#=C2 C#=C4(SC)3、检索选修课名为OS的学生学号及姓名。S#, SNAME(C#（CNAME=OS(C)） SC S)4、检索至少选修了课号为C2和C4的学生学号。 T1=C#=C2(SC) T2=C#=C4(SC)T3=T1 T1.S# =

17、T2.C# T2练习：请用其他运算解决该问题5、查询至少选了两门课程的学生学号。 T1=SC T1=SC T3=T1 T1.S# = T2.S# and T1.C# T2.C# T26、检索不学C2课的学生的姓名及年龄。SNAME, AGE(S)SNAME, AGE（C#=C2(S SC)）7、检索选修了全部课程的学生学号，成绩。T1=C#(C)T3=SCT1 8、检索所学的课程包含学生S3所学课程的学生学号。学生S3所选的课程：T1=C#（S#=S3(SC)）T2=S#，C#(SC)结果： T3= T2T12.2.4 关系代数的七个扩充操作1、改名2、广义投影3、赋值4、外连接（Outer

18、Join）5、外部并（Outer Union）6、半连接（Semijion）7、聚集操作*2.3 关系演算所谓关系演算就是用数理逻辑的谓词演算来表示查询。关系演算可分为元组演算和域演算，前者以元组（行）为变量，后者以域（列）为变量。2.3.1 元组关系演算下面我们就来看看，在元组关系演算中是如何表达关系代数中的那些运算的。1、原子公式、公式的概念定义原子公式的定义R(s)：表示这样一个命题：s是R的一个元组，R是关系名，s是元组变量。siuj：s,u是元组变量，是比较运算符，si 和uj分别表示s的第i个分量和u的第j个分量。此原子公式表示它们分量的比较。 sia：a是常数，该原子公式表示：s

19、的i第个分量与常数a之间满足运算。公式的定义每个原子公式是一个公式。如果P1 和P2 是公式，则P1 ，P1 P2 ，P1 P2 ，P1 P2 也是公式。如果P1 是公式，则（s）（P1 ）也是公式。它表示存在一个s使P1 为真。如果P1 是公式，则（s）（P1 ）也是公式。它表示任意一个s使P1 为真。以上公式中，运算符的优先级为：，、，。公式只能由上面四种形式公式组合而成。2、元组关系演算公式的等价规则 P1 P2 等价于 （P1 P2），P1 P2 等价于 （P1 P2） （s）（P1 （s）等价于 （s）（P1 （s） (s)（P1 （s）等价于 （s）（P1 （s）P1 P2 等价于

20、 P1 P23、各种代数运算的谓词表示 RSt | R(t) S(t)RSt | R(t) S(t)R S= t | (u) (v)( R(u) S(v) t(1)=u(1) t(r)=u(r) t(r+1)=v(1) t(r+s)=u(s) r, s为R, S的元数 )（R）=t | R(u) t1=ui1 tn=uin )(F)（R）=t |R(t) F/ F/是F在元组演算中的等价形式2.3.2 域关系演算2.3.3 关系运算的安全约束和等价性在关系演算时，如果不加以约束，会出现无限关系。这是不允许的。例如： t | R(t) 是个有限关系，而 t | R(t) 就可能是个无限关系。为了

21、避免出现无限关系，必须对元组运算表达式加以约束。具体做法如下：对于每个元组表达式 t | P(t) ，将公式P(t) 的“域”定义为： 由出现在公式P(t)中的常量和在P(t)中出现的关系的所有属性值组成的集合。 记为：DOM( P(t) )。 安全元组表达式 t | P(t) 应满足如下条件： 如果t 满足公式P(t)，那么t的每个分量必定是DOM( P(t) )的元素。对于P(t)中每个形如 (u) ( P1(u) ) 的子公式，如果元组u使P1(u)为真，那么u的每个分量必定是DOM( P1(u) )的元素。对于P(t)中每个形如 (u) ( P1(u) ) 的子公式，如果元组u使P1(

22、u)为假，那么u的每个分量必定是DOM( P1(u) )的元素。2.4 关系代数表达式的优化2.4.1 关系代数表达式的优化问题在关系代数运算中需要指出关系的操作步骤。不同的操作步骤执行起来，所花费的时间、占据的内存空间，也是不一样的。例如： 对关系 R( A,B ) ,S( C,D ) 有以下三个等价的查询 ： E1= (A ) （(B=C D=“99”)（RS） E2= (A ) （(B=C) （R( D=“99”)（S） E3= (A ) （R B=C ( D=“99”)（S） 大家可以分析以下，看哪个算法节省时间、空间。显然是第三个算法。那么我们如何从众多的算法中，找到好的算法呢？有没有理论的指导原则呢？2.4.2 关系代数表达式的等价变换规则1、连接和笛卡尔积的交换律 设E1和E2是关系代数表达式，F是连接条件，那么下列式子成立： E1 F E2E2 F E1 E1 E2E2 E1 E1 E2E2 E12、连接和笛卡尔积的结合律 设E1、E2和E2是关系代数表达式，F1和F2是连接条件，F1只涉及E1和E2、F2只涉及E2和E3，那么下列式子成立： （E1 F1 E2）F2 E2E1 F