关系代数重点

1、第二章关系代数教学目的：本章实际上研究的是关系的运算。学习目的：关系运算是设计关系数据库操作语言的基础，因为其中的每一个询问往往表示成一个 关系运算表达式，在我们的课程中，数据及联系都是用关系表示的，所以实现数据间的联 系也可以用关系运算来完成。通过本章学习，应重点掌握：(1) 关系数据库的基本概念；(2) 如何用关系代数表达式来表达实际查询问题；(3) 如何用元组演算表达式来表达实际查询问题；(4) 如何用域演算表达式来表达实际查询问题；(5) 如何将关系代数表达式转换为元组演算表达式或转换为域演算表达式。 了解和掌握关系数据结构中涉及到的域、笛卡儿积、关系模式等有关内容的含义； 掌握关系的

2、实体完整性和参照完整性的定义；掌握关系代数中的并、交、差、笛卡儿积运算，以及选择、投影和连接运算。 教学重点： 关系的实体完整性和参照完整性的定义； 关系代数中的并、交、差、笛卡儿积运算，以及选择、投影和连接运算。 教学难点：关系代数中的并、交、差、笛卡儿积运算，以及选择、投影和连接运算。 教学方法：实例法 教学内容：如下： 2.1关系模型关系模型是一种简单的二维表格结构，每个二维表称做一个关系，一个二维表的表头, 即所有列的标题称为一个元组，每一列数据称为一个属性，列标题称估属性名。同一个关 系中不允许出现重复元组和相同属性名的属性。1 关系模型组成关系模型由关系数据结构、关系操作集合和关系

3、完整性约束三部分组成。关系操作分 为两大部分如图所示。查询其它选择 Select增加 In sert投影 Project删除 Delete连接 Join修改 Update除 Divide并 Union交In tersecti on差Differe nee2.关系操作的特点关系操作的特点是操作对象和操作结果都是集合。而非关系数据模型的数据操作方式则为一次一个记录的方式。关系数据语言分为三类：(1) 关系代数语言：如ISBL;(2) 关系演算语言：分为元组关系演算语言(如Alpha , Quel)、域关系演算语言(如QBE);(3) 具有关系代数和关系演算双重特点的语言：如SQL3.关系数据结构及

4、其形式化定义(1) 域定义 域是一组具有相同数据类型的值的集合。(2) 笛卡尔积定义 设D, D2, D,，D,为任意集合，定义D, D2, D,，Dn的笛卡尔积为Di x D2x D3x-x Dn = (di , d2, d3,dn)di Di , i = 1, 2, 3，n其中每一个元素(dl , d2, d3，dn,)叫做一个n元组(n 一 tuple)或简称为元组 (Tuple)，每一个值di叫做一个分量(Component)，若Di(i = l , 2,n)为有限集，其基数 (Cardinal number) 为 mi(i=l , 2, 3,，n),n则Dx D2x Dxx Dn的基

5、数M为M =门mii 3笛卡尔积可以用二维表来表示。例 D仁0 , 1 , D2= a , b, c 则：D1x D2= (0 , a) , (0 , b) , (0 , c), 表来表示，如图2 2所示。(3)关系的形式化定义及相关名词 定义 D 1x D2 x D xx Dn的子集叫做DD20a0b0c1a1b1c在域 D,D2,D3,Dn上的关(1 , a) , (1 , b), (1 , c)用二维系，用R(D1,D2,D3,Dn),称关系R为n元关系。候选码 若关系中的某一属性组的值能惟一的标识一个元组，则称该属性组为候选码(Ca ndidate Key)。主码若一个关系有多个候选码

6、，则选定其中一个为主码(PrimaryKey)。主码诸属性称为主属性。不包含在任何候选码中的属性称为非码属性(Non Key attribute)。关系模型的所有属性组是这个关系模式的候选码，称为全码(Allkey)(4 )关系的三种类型基本关系(通常又称为基本表或基表)，是实际存在的表，它是实际存储数据的逻辑 表示查询表，查询结果对应的表视图表，是由基本表或其他视图表导出的表，也常称为虚表(5)基本关系有以下五条性质每一列中的分量必须是同一类型的数据，来自同一个域属性不能重名行列的顺序无关任何两个元组不能完全相同每一个分量必须是不可再分的数据项3.关系完整性关系模型的完整性规则是对关系的某种

7、约束条件。关系的完整性共分为三类: 实体完整性、参照完整性、用户定义完整性。(1) 实体的完整性 (Entity Integrity) 规定：若属性 A 是基本关系 R 的主属性，则属性 A 不能取空值。即主属性不能为空。(2) 参照的完整性 (Referential Integrity) 规定：若 F 是基本关系 R 的外码，它与基 本关系S的主码Ks相对应(基本关系R和S不一定是不同的关系)则对于R中每个元 组在F上的值必须为： 或者取空值 (F 的每个属性值均为空值 ) ；即外码可以为空 或者等于 S 中某个元组的主码值。(3) 用户定义的完整性 (User defined Integr

8、ity) ：就是针对某一具体的关系数据库的 约束条件，由应用的环境决定。4关系模式 在数据库中要区分型和值。关系数据库中的型也称为关系数据库模式，是关系数据库 的描述。它包括若干域的定义以及在这些域上定义的若干关系模式。关系数据库的值是这 些关系模式在某一时刻对应的关系的集合，通常称之为关系数据库。定义 关系的描述称为关系模式 (Relation Schema) 。可以形式化的表示为R(U ， D， dom， F)其中，R表示关系名；U是组成该关系的属性名集合；D是属性的域；dom是属性向域的映像集合； F 为属性间数据的依赖关系集合。通常将关系模式简记为：R(U)或 R(AI , A2, A

9、3,，An。)其中R为关系名，A1, A2, A3,，An。为属性名，域名、属性向域的映像常常直接 说明属性的类型、长度。例 定义学生与课程关系模式及主码如下：(1) S(Sno, Sname, SD, SA) Key(Sno)(2) C(Cno, Cname, PCno)Key(Cno) Dom(PCno)=Cno这里，Pcno是先行课程号，来自 Cno域，但由于Pc no属性名不等于 Cno值域名，所以 要用Dom来定义。能否将Pcno直接改为Cno呢？ 不能,因为在关系模型中,各列属性必须取相异的名字。(3) SC(Sno, Cno, Grade)Key(Sno, Cno)其中，SC关系

10、中的Sno、Cno又分别为外码。因为它们分别是S、C关系中的主码。2 2 关系代数 关系代数是一种抽象的查询语言,是关系数据操纵语言的一种传统表达方式。它是用 对关系的运算来表达查询的。关系运算符有四类：集合运算符,专门的关系运算符,算术比较符和逻辑运算符, 如图 2 3 所示。运算符含义运算符含义并大于集合-差比较大于等于运算符交运算符S trt s | tR A t S A t r A 0 t sB A* b=其中：二是比较运算符，A和B分别为R和S上度数相等，且可比的属性组。 等值连接：当 二为“=”时，称之为等值连接，记为：R 関 tGs | t ER AtsSAtrA = t sB

11、A=B = 自然连接：是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相 同的属性组，并且在结果中将重复属性列去掉。若R和S具有相同的属性组 B,则自然连接可以记为：R S = t7t s | t r 三 R A t S A t r B = t sB 特别需要说明的是：一般连接是从关系的水平方向运算，而自然连接不仅要从关系 的水平方向，而且要从关系的垂直方向运算。因为自然连接要去掉重复属性，如果没 有重复属性，那么自然连接就转化为笛卡尔积。(4) 除(Divisio n);除运算是同时从关系的水平方向和垂直方向进行运算。给定关系R(X, Y)和S(Y, Z), X, Y, Z为属性组

12、。R- S应当满足元组在 X上的分量值 x的像集Yx包含S在Y上投影的集合。记作：R - S = t r X | t r R A 二 ySYx其中：Yx为x在R中的像集，x = tr X。且R- S的结果集的属性组为 X。(5) 需要注意的四个问题： 关系代数的五个基本操作为：并、差、笛卡尔积、投影和选择。其它的操作都可以 由5个基本的操作导出，因此它们构成了关系代数完备的操作集。例如两个关系R与S的交运算等价于：R - S= R 一 (R S)或 R S= S 一 (S R)所以交运算不是一个独立的运算。 关系代数在使用的过程中对于只涉及选择、投影、连接的查询可用表达式：二 A1,AK(；f

13、(S R)l 或二 A1,AK(匚 f(S X R) 对于否定操作，一般要用差操作表示，例如不学“操作系统”课的学生姓名，通常 不要用如下的形式表示：兀 Sname( b Cnam辱操作系统)(S SCCXC)而采用如下形式：二 Sname - 二 Sname (二 Cname =操作系统 )(S SC C ) 对于检索具有全部特征的操作，一般要用除法操作表示， 例如查询选修全部课程的学生学号。通常不要用如下的形式表示；二 Sn o,C no (SC 二 Cn o(C)而采用如下形式：二 Sn o,C no (SC)二 Cn o(C)2. 3关系演算关系演算分为元组演算和域演算，下面分别介绍。

14、元组演算ABCabccde元组达式在元组演算中，其元组表达式中的变量是以 为单位的，其一般形式为：t | P(t)其中：t是元组变量，P(t)是关系演算公式。 下面将五种基本的关系运算用元组演算表 表示如下。(1) 并 RUS= t | R(t) V S(t)(2) 差 R- S= t | R(t)- S(t)(3) 笛卡尔积R x S= t (n+m) | (u(n) ) ( -I v(m) ( R(u) S(v) t1= u1 tn = untn+1= v1tn+m= vm)R x S后生成的新关系是 n+m目关系。t1= ui 1tk = 投影 二 i1,i2,ik(R) = t (k)

15、 | ( u )(R(u) u (ik)(5) 选择-(R) = t | R(t)F域演算在域演算中，表达式中的域变量是表示域的变量，可将关系的属性名视为域变量，域 演算表达式的一般形式为：t1,t k | P(t 1,t k)其中，11 tk是域变量，P(t 1t k)是域演算公式。关系代数、元组演算、域演算三类关系运算的表达能力是等价的，可以互相转换。可 以证明如下三个结论：(1) 每一个关系代数表达式有一个等价的安全的元组演算表达式；(2) 每一个安全的元组演算表达式有一个等价的安全的域演算表达式;(3) 每一个安全的域演算表达式有一个等价的关系代数表达式。2 1设有关系R, S如图2

16、4所示。请求出：RUS R S, Rc S, Rx S,兀 a,c(R) , a ab(R)。ABCabcbadcdedfgRSABCbaddfgfhkABCabcbadcdedfgfhk解 RUS , R S, R S, RX S,二 a,c(R),:二ab(R)如图所示:RUSR SACacbdcedgABCb；SdcdeABCbadR.AR 八R.BR.CS.AS.BS.Cabcbadabcdfgabcfhkbadbadbaddfgbadfhkcdebadcdedfgcdefhkdfgbaddfgdfgdfgfhk二 A,c (R)匚 ab(R)例2 2设有关系R, S如图2 4所示，求

17、：Hr.bABCabcbadcdedfgRSABCbaddfgfhk解 本题的F公式为R.AS.B，意为将R关系中属性A的值小于S关系中属性B的值的 元组取出来作为结果集的元组。结果集的前三个属性为：R.A，R.B，R.C结果集的后三个属性为：S.A，S.B，S.C结果如图所示。R.AR.BR.CS.AS.BS.Cabcdfgabcfhkbacdfgbadfhkcdedfgcdefhkdfgdfgdfgfhk例2-3设有关系R, S如图2-7所示，求：RgRSABCABCBADCDEDFGfhkACDacddfgcekbdg解 本题要求R与S关系的自然连接，自然连接是一种特殊的等值连接，它要求

18、两个关系中进行比较的分量必须是相同的属性组，并且在结果中将重复属性列去掉。本题R与S关系中相同的属性组为 AC,因此，结果中的属性列应为：ABCD其结果如图2 8所示。分析1根据除法定义，此题的 X有属性AB, Y有属性CD那么，R+ S应当满足元组 在X上的分量值x的像集Yx包含S在Y上投影的集合。而结果集的属性为ABoABCDabcdabefabhkbdefbddlckcdckef例2-4设有关系R, S如图2-9所示，求：R- SRSCDcdefR S.ABCDabcdbadgcdek分析1根据除法定义，此题的X有属性AB, Y有属性CD,那么，R+ S应当满足元组在 X上的分量值x的像

19、集Yx包含S在Y上投影的集合。而结果集的属性为ABo分析2在关系R中，属性组X(即AB)可以取3个值(a , b) , (b , d) , (c , k),其中：(a, b)的像集为：(c , d) , (e , f) , (h , k)(b, d)的像集为：(e , f) , (d , 1)(c, k)的像集为:(c , d) , (e , f)分析3 S在Y(即CD)的投影为(c , d) , (e , f)从上分析可以看出，只有(a , b) , (c , k)包含了 S在Y(即CD)的投影，所以，R- S=(a , b) , (c , k) o结果如图所示：ABabckR S例2 5设

20、有学生课程数据库中包含三个关系：学生关系S、课程关系 C、学生选课关系SC如图211(a) , (b) , (c)所示。请用关系代数表达式、元组演算表达式查询如下问题：CnoCn amePcnoCredit1数据库332数学43操作系统444数据结构735数字通信636信息系统147程序设计22CSnoCnoGrade3001193300128430013843002283300239310421841042282SCSnoSn ameSexSDAge3001王平女计算机183002张勇男计算机194003黎明女机械184004刘明远男机械191041赵国庆男通信201042樊建玺男通信20S

21、(1)检索选修课程名为“数学”的学生号和学生姓名解：检索选修课程名为“数学”的学生号和学生姓名：关系代数表达式为：兀 Sno,Sname( Cname=数学SCXC)因为S 竝 K 为自然连接，所以去掉重复列后的结果如图(a) , (b)所示。SnoSn ameSexSDAgeCnoGradeCn amePcnoCredit3001王平女:计算18193数据库333001王平女机18284数学43001王平女计算18384操作系统443002张勇男机19283数学43002张勇男计算19393操作系统441042樊建玺男机20184数据库331042樊建玺男计算机计算机通信通信20282数学4

22、(a)SnoSn ame3001王平3002张勇1042樊建玺(b)从图中可见我们可将上述的关系代数表达式写为:CnoCn amePcnoCredit1数据库332数学43操作系统444数据结构735数字通信636信息系统147程序设计22SnoCnoGrade3001193300128430013843002283300239310421841042282-1,2（ - 8=数学（S SC 一 C ）元组演算表达式为：t |(u)(v)(-1 w)S(u)SC(v)C(w)u1 =V1v2=w1w2=数学tl = u(l)t2=u2例2 6给定学生数据库,有s,SSC, C三个关系如图211所示：SnoSn ameSexSDAge3001王平女计算机183002张勇男计算机194003黎明女机械184004刘明远男机械191041赵国庆男通信201042樊建玺男通信202. 4查询优化查询实例要查询学生“李明”选修的所有课程的成绩。有几种查询表示：E1=nscore (s.sno=sc.snoANDs.sname=李明” (Student x SC)E2=nscore (s.sn