第5章 关系代数

1、第5章 关系代数,主讲人：喻小光 Email：,2,主要内容,5.1 一个数据库模式的例子 P118 5.2 关系代数操作 5.3 包上的关系操作 5.4 关系代数的扩展操作 5.5 关系的约束,3,5.1 一个数据库模式的例子,Moive(title:string,year:integer,length:integer,incolor:boolean,studioname:string,producerC#:integer) StarsIn(movietitle:string,movieyear:integer,starname:string) MovieStar(name:string,a

2、ddress:string,gender:char,birthdate:date) MoiveExec(name:string,address:srting,CERT#:integer,netWorth:integer) Studio(name:string,address:string,presC#:integer),4,关系代数 一种抽象的查询语言 关系模型数据操纵语言的一种传统的表达方式 使用户可以对数据进行查询和修改,关系代数表达的运算总是由旧关系构造新关系 运算对象-关系 运算结果-关系 运算符：. 查询（更新）：关系代数表达式 关系代数基础:代数通常是由一些操作符和一些原子操作数组

3、成,5,关系代数运算分类:,1. 传统集合运算：并、交、差,2. 删除部分数据的运算: 选择(删行)、投影(删列、),3. 合并关系元组的运算: 连接（两个关系中的元组有选择地组成对） 笛卡尔积(两个关系中的元组以所有可能的方式组成对),4. 改变关系模式(关系名、属性名):改名,6,1. 关系的集合运算 关系R和S 是元组的集合(不存在重复元组) 前提：R和S的模式具有相同的属性集(属性域匹配) 且属性顺序相同 属性名不同，可以改名。,等价的说法：“并相容”-属性数目相同，对应属性取自同一个域。假定，结果关系的模式使用R的名字。,7,RS: R和S的并 由R或S中的元组组成,RS=R-(R-

4、S),RS: R和S的交 由R和S中都存在的元组组成,R-S: R和S的差 由在R中而不在S中的元组组成,8,例： R ：选修数据结构的学生 学号 姓名 年龄 班级 010812 张明 18 0108 010820 李力 19 0108 S：选修操作系统的学生 学号 姓名 年龄 班级 010812 张明 18 0108 010814 陈东 19 0108,9,1）查询选修数据结构或操作系统的学生信息 RS 学号 姓名 年龄 班级 010812 张明 18 0108 010820 李力 19 0108 010814 陈东 19 0108,10,2）查询选修数据结构及操作系统的学生信息 RS 学号

5、 姓名 年龄 班级 010812 张明 18 0108,11,3）查询选修数据结构没选修操作系统的学生信息 R - S 学号 姓名 年龄 班级 010820 李力 19 0108,岳1：P120 例5.1，岳2：P22 例2.8，史P122：例4.1,12,2. 投影 关系R上的投影是从R中选择若干属性A1,A2,A3An组成的新的关系(去掉重复元组)。 记 丌A1,A2,A3.An (R) A1,A2,A3An是R中的属性 习惯上按所列出的顺序显示,删除一些属性 和 重复的元组 一元运算,13,例：查询学生的年龄 学生 学号 姓名 年龄 班级 010812 张明 18 0108 010820

6、 李力 19 0108 011004 童雪 18 0110,丌年龄(学生),年龄 18 19,14,P120 例5.2 查询所有电影的片名、年份、长度 P121 图5-3 关系的实例 Movies(title,year,length,inColor,studioName,producerC#),丌title,year,length(Movies) 结果：P121,查询所有电影的类型 丌inColor(Movies),inColor true,15,3. 选择 关系R上的选择运算，即从指定关系中选择满足一定条件C的元组, 得到新的关系。结果集的模式与R相同. 记： C(R) 一元运算,C是一个条

7、件，取值为“true”或“false”。 C由逻辑运算符OR AND NOT 连接各条件表达式组成。,条件表达式形如 XY， 是比较运算符=，,之一; X 、Y是属性名，常量、 简单函数等,16,例：查询0108班年龄大于18岁的学生信息 学号 姓名 年龄 班级 010812 张明 18 0108 010820 李力 19 0108 010814 陈东 19 0108,班级=0108AND 年龄18(学生),学号 姓名 年龄 班级 010820 李力 19 0108 010814 陈东 19 0108,查询的实现：依次考察每一个元组，满足条件的放入结果集,17,对于P121 图5-3 Movi

8、es(title,year,length,genre,studioName,producerC#),例5.3 查询片长在100分钟以上的电影的信息,length=100( Movies),例5.4 查询制片公司为Fox的且片长在100分钟以上的电影的信息 length=100 AND studioName=Fox( Movies),18,4. 笛卡尔积 R和S的笛卡尔积(即乘积)是有序对的集合： 由R的元组和S的元组构成更长的元组。有序对的 第1个元素是关系R的任何一个元组 第2个元素是 关系S的任何一个元组. 记作 : RS,结果关系模式中的属性: 由R的属性和S的属性构成。,当R和S有公共

9、属性A时，分别用R.A和S.A表示。,19,R： A B S： B C D 1 2 2 5 6 3 4 4 7 8 9 10 11,R S A R.B S.B C D 1 2 2 5 6 1 2 4 7 8 1 2 9 10 11 3 4 2 5 6 3 4 4 7 8 3 4 9 10 11,P122 例5.5,20,例：R 学号 姓名 兴趣班 0202 李一 美术 0202 李一 电脑 0205 吴晓 电脑 0304 石玉 美术 S 兴趣班 老师 美术 张 电脑 郑,21,R S 学号 姓名 R.兴趣班 S.兴趣班 老师 0202 李一 美术 美术 张 0202 李一 电脑 电脑 郑 02

10、02 李一 美术 电脑 郑 0202 李一 电脑 美术 张 0205 吴晓 电脑 美术 张 0205 吴晓 电脑 电脑 郑 0304 石玉 美术 美术 张 0304 石玉 美术 电脑 郑 笛卡尔积得到的元组不一定有意义 R、 S不一定有公共属性,22,5. 自然连接 由R和S在公共属性上相同的元组成对连接构成。 (去掉重复的列) 假设A1,A2,An为R和S的公共属性,当且仅当R的元组r和S的元组s在A1,A2,An每一个属性上都一致时,r和s才能成功地组成一对。 记为:,结果关系模式的属性: R和S的属性的并集。,23,R： A B S： B C D 1 2 2 5 6 3 4 4 7 8

11、9 10 11,A B C D 1 2 5 6 3 4 7 8 公共属性：B 去掉重复列,P123 例5.6,24,P123 例 5.7 两个公共属性,R: A B C 1 2 3 6 7 8 9 7 8,S: B C D 2 3 4 2 3 5 7 8 10,A B C D 1 2 3 4 1 2 3 5 6 7 8 10 9 7 8 10,25,例：R 学号 姓名 兴趣班 0202 李一 美术 0202 李一 电脑 0205 吴晓 电脑 0304 石玉 美术 S 兴趣班 老师 美术 张 电脑 郑,R S 学号 姓名 兴趣班 老师 0202 李一 美术 张 0202 李一 电脑 郑 0205

12、 吴晓 电脑 郑 0304 石玉 美术 张 公共属性： 兴趣班,26,R S 学号 姓名 兴趣班 老师 0202 李一 美术 张 0202 李一 电脑 郑 0205 吴晓 电脑 郑 0304 石玉 美术 张 公共属性： 兴趣班,27,自然连接由笛卡尔积、选择、投影三个步骤实现的： 笛卡尔积：拼接元组 选择：选出公共属性上相同的行 投影：去掉一组公共属性,自然连接符合结合律： (R1 R2) R3 等价于 R1 (R2 R3) 可简记为 R1 R2 R3 悬挂元组：在一个连接中，不能和另外关系中的任何元组配对的元组。,28,6.连接 R和S基于条件C的连接,记为:R C S 1) R S 2)选

13、满足条件C的元组 3)重名属性通过附加前缀的办法进行处理 结果关系模式的属性: 由R的属性和S的属性组成。 笛卡尔积、选择 连接 自然连接和连接的区别 前者要将公共属性合并，后者不合并 原因：条件连接时，相同属性的属性值不一定约束成等值关系，而要合并的话，基本前提肯定是要等值.,29,R: A B C 1 2 3 6 7 8 9 7 8,S: B C D 2 3 4 2 3 5 7 8 10,P123 例5.8,R AD S A R.B R.C S.B S.C D 1 2 3 2 3 4 1 2 3 2 3 5 1 2 3 7 8 10 6 7 8 7 8 10 9 7 8 7 8 10 连接

14、条件与公共属性无关 ，可以不是等值连接 ，保留重复的列,30,P124 例5.9 R AD AND R.B S.B S A R.B R.C S.B S.C D 1 2 3 7 8 10 可以是组合条件,31,7.组合操作构成查询,关系代数允许任意复杂的表达式，其操作符可以用于任何关系之上，这个关系既可以是某个给定关系，也可以是操作得到的结果关系。 可以在子表达式上应用算符来构造新的关系代数表达式，必要的时候用括号把操作数分割开 也可以用表达式树来表示这种表达式，虽然这种表达式对机器来说比较难以处理，但是它更易于理解,32,查询表达式与表达式树 P124 例5.10 查询Movies关系中由Fo

15、x制作的至少100分钟的电影的名称(title)和年份(year) 丌title,year (length=100(Movies) StudioName=“Fox”(Movies),length=100,33,P125 例5.11 将分解为BCNF的关系重新组合,Movies(title,year,length,filmType,studioName,starName) 分解为2个BCNF： Movies1(title,year,length,filmType,studioName) Movies2(title,year,starName) 现在查询：“超过100分钟长的电影中的影星”,34,

16、综合示例 学生-课程 数据库: Students(Sno,Sname,Ssex,Sage,Sdept) Courses(Cno, Cname, Cpno,Ccredit) Cpno先修课号 SC(Sno,Cno,Grade),Students: Sno Sname Ssex Sage Sdept 020501 李勇 男 20 计算机 020502 刘雪 女 19 计算机 020503 王敏 女 18 经管 020504 张功 男 19 计算机,35,Sno Cno Grade 020501 1 98 020501 2 77 020502 1 65 020502 2 80 020502 4 93

17、,Courses:,SC:,36,例：查询选修了2号课程的学生的学号,条件 目标 在？表,Cno=2 (SC) /选行,丌Sno (Cno=2 (SC) ) /选列,37,例：查询学分大于3的课程号和课程名 Ccredit3 (Courses) /选行 丌 Cno，Cname (Ccredit3 (Courses) ) /选列,38,例：计算机系 没有选课的同学的学号,丌Sno (Sdept=计算机 (Students) -丌Sno (SC ),选修-SC,丌Sno (Sdept=计算机 (Students) ),丌Sno (SC ),39,解1： 选修-SC 名字-Student 连接用Sn

18、o,例：查询选修了课程的学生的名字,40,解2：,丌 Sno,Sname (Students),丌 Sno (SC),先投影？先连接？先选择？ 交集？ 组合成多种解法 一般参与运算（尤其连接运算）的数据越少速度越快,41,例：查询选修4学分课程，成绩在90 以上的同学的学号,其他解法,Courses SC 连接：Cno,42,例: 查询选修了 以2号课为先修课的 课程的学生的名字,Cpno Courses Sname Students 必须借助SC表连接,解1：,43,解2:,Cpno=2 (Courses),丌Sno,Sname ( Students ),44,例：选修数据结构课的学生的名字

19、,名字 在表Students中 课程名 在Courses中 无公共属性 用SC,45,例：没有选修数据结构课的学生的名字,全体学生 除去 选修的,46,例：求至少选了一门4学分课程的同学的名字,Courses Students SC,解1：,Ccredit=4( Courses),Ccredit=4( Courses) SC Students,丌Sname(Ccredit=4( Courses) SC Students),47,解2：,Ccredit=4( Courses),丌Cno(Ccredit=4( Courses),丌Sno, sname (Students),48,8. 改名 (重命

20、名) 改名运算: S(A1,A2,An) (R) 将关系名R改为S、S的属性依次命名为 A1,A2,An S (R) 将关系名R改为S,49,P125 例5.12： R(A,B) S(B,C,D) 求 R S 不用 R.B S.B 改名:,法2: RS(A,B,X,C,D) (R S ),法1: S(X,C,D) (S) S(X,C,D) R S(X,C,D) (S),50,9. 基本和导出运算 （操作之间的联系） 关系代数的某些运算可以由其他运算导出 RS = R - (R-S),51,U: A B C 1 2 3 6 7 8 9 7 8,V: B C D 2 3 4 2 3 5 7 8 1

21、0,A B C D 1 2 3 4 1 2 3 5 6 7 8 10 9 7 8 10,丌A, U.B, U.C, D ( U.B=V.B AND U.C=V.C (U V),P127 例5.13（1）,52,P127 例5.13（2）,R: A B C 1 2 3 6 7 8 9 7 8,S: B C D 2 3 4 2 3 5 7 8 10,53,其余的6个运算: 并, 差, 选择, 投影, 乘积, 改名 构成独立集，其中任一个不能由其他5个给出。 称为去：关系代数操作集合的最小化完备集,54,9. 关系代数表达式中的线性符号 复杂的关系代数表达式： 1）表达式树 2）线性符号 生成若干临

22、时关系，用来表示树的内节点，并 写一系列的赋值语句使其具有正确的值。 涉及的符号： 关系名（属性列表） 赋值符号 ：= 写在赋值号右边的任何代数表达式 Answer(属性列表)：最后运算得到的结果关系,55,P127 例5.14 查询Movies关系中由Fox制作的至少100分钟的电影的名称(title)和年份(year) 丌title,year (length=100(Movies) StudioName=“Fox”(Movies),Answer(title,year):= 丌t,y (T),T(t,y,l,i, s,p ) :=RS,S(t,y,l,i, s,p ) := studioNa

23、me=Fox(Movies),R(t,y,l,i, s,p ) := length=100(Movies),56,主要内容,5.1 一个数据库模式的例子 P118 5.2 关系代数操作 5.3 包上的关系操作 5.4 关系代数的扩展操作 5.5 关系的约束,57,什么是包,包，也叫多集(multi)：与集合不同，当关系是包时，同一个元组可以在关系中多次出现。 例5.15,包允许重复元组 元组没有顺序,58,为什么采用包,商业DBMS实现的关系都是包，而不是集合，重要的原因是采用基于包的关系，一些关系操作的实现效率会更好。例如： 两个包关系的并，只需将一个关系的所有元组复制到另一个关系，而不必消

24、除两个关系中的重复元组 在集合关系上作投影时，需将每一个投影元组与所有元组逐个比较，以确定每次投影只出现一次。而如果接受包作为结果，就可以简单地投影每个元组并将其加入结果中，无须比较，消除重复元组。,59,示例5.16,把如下关系投影到A,B属性上,效率较高,求A的平均值: (1+3)/2=2 与原来关系中A的平均值不符,求A的平均值： (1+3+1+1)/4=1.5 与原来关系中A的平均值相符,60,1.包的并、交、差,假定R和S是包，其中元组t在R中出现了n次，在S中出现了m次。注意：这里的n和m都可以是0。 在RS的包并操作中，元组t出现n+m次 在RS的包交操作中，元组t出现min(m

25、,n)次 在R-S的包差操作中，元组t出现max(0,n-m)次 直观上，t在S中的每次出现都抵消了它在R中的一次出现,61,示例5.17,R,S,RS,RS,R-S,S-R,62,2.包上的投影操作,63,3.包上的选择操作,在包上应用选择操作的时候，要独立对每个元组应用选择条件，在结果中不去掉重复元组。 示例5.18：如果R是包,64,4.包的笛卡尔积,一个关系中的每个元组跟另外一个关系中的每个元组配对，而不管这个元组是不是重复出现。 如果元组r在关系R中出现了m次，元组s在关系S中出现了n次，那么元组rs在RS中出现m*n次,65,示例5.19,R,S,RS,同时属于R和S两个关系的属性

26、B，在积中出现两次，于是属性的前面要加上关系名的前缀,66,包的连接,首先对比两个关系中的元组，看是不是能组成一对，如果可以，这个配对起来的元组就是结果中的一员。产生结果时，不需要去掉重复元组。 示例5.20,R,S,67,主要内容,5.1 一个数据库模式的例子 P118 5.2 关系代数操作 5.3 包上的关系操作 5.4 关系代数的扩展操作 5.5 关系的约束,68,关系代数的扩展操作符,(1) 消重复操作符 (2) 聚集操作符 (3) 分组操作 (4) 扩展投影 (5) 排序算子 (6) 外连接算符,69,(1) 消重复操作符,把包中的重复元组去掉，只保留一个拷贝在关系中 用符号表示，

27、(R)返回没有重复元组的关系R 示例：,R,(R),70,(2) 聚集操作符,应用在数值或字符串类型的集合或者包上的操作符，用于汇总或聚集关系某一列中出现的值 SUM：产生一列的总和，得到数字值 AVG：产生一列的平均值，结果也是数字值 MIN/MAX： 用于数字值列时，产生该列的最大/小值； 用于字符值列时，产生字典序的第一个/最后一个值 COUNT：产生一列中“值”的数目(包括重复值),71,聚集操作符示例,SUM(B)=2+4+2+2=10 AVG(A)=(1+3+1+1)/4=1.5 MIN(A)=1 MAX(B)=4 COUNT(A)=4,R,72,(3) 分组,人们不仅希望对简单的

28、一整列作聚集操作，还需要根据元组在一个或多个属性上的值把关系的元组拆分成“组”，使得聚集操作可以对分好组的各个列进行计算 示例：,73,分组操作符,分组操作符：下标是一个元素的列表L。其中每一个元素是下面情况之一： 分组属性：应用操作的关系R 的一个属性，R使用这个属性分组 聚集属性：应用到关系的一个属性的聚集操作符 为了在结果中给该聚集一个属性名称，使用一个箭头和一个新名字附加在这个聚集后面。,74,示例1,假设有关系： Movies(title,year,length,genre,studioName) 要计算每一个电影公司出品的电影总长度 studioName, SUM(length)

29、sumOfLength (Movies),75,表达式L(R)返回关系的过程,把关系R的元组分组。每一组由L中分组属性为特定赋值的所有元组构成 对于每一组，产生一个如下内容的元组 那个组的分组属性 本组中所有元组对列表L的聚集属性进行聚集操作的结果,76,示例2,假设有关系：StarsIn (title, year, starName) 请找出至少出演了三部电影的影星，以及他们在电影中出现的最早年份,77,(4) 扩展的投影操作符,普通的投影运算符上增加一些增强功能的算子，可将变量关系的列作为参数进行计算，并产生新的列。 仍用L(R)来表示扩展投影操作，其中投影列表L可以是以下所列出的元素之一

30、： R的一个属性 形如xy的表达式，x和y都是属性名，元素xy表示把R中的x属性重命名为y在结果模式中出现 形如Ez的表达式，其中E是一个涉及R的属性、常量、算术运算符或者串运算符的表达式，z是表达式E计算结果的属性的新名字,78,示例,R,R1,R2,79,(5) 排序操作符,对关系中的元组按一个或多个属性排序 排序操作符用来表示 表达式L(R) 表示的是按照L排序的关系R本身 其中R是关系，L是R中属性A1,A2,An的列表 那么R的元组就先按属性A1的值先排序，对于A1属性相等的元组，就按A2的值排序，依次类推 如果An 属性上的值也相等，则这些元组的顺序可以任意。,80,示例,R,R,

31、81,排序操作符说明,排序操作符是关系代数中唯一一个结果是元组列表的操作符。这样，从查询的表达方面来讲，它只能作为一串操作的最后一个算符来使用才有意义。 如果使用其它操作符到的排序结果，排序的顺序通常无意义。 不过包投影可以保持顺序，选择操作将丢弃关系中不满足选择条件的元组，余下的元组可以按原来的顺序排序,82,悬浮元组,在一个连接中，若一个元组不能和另外关系中的任何一个元组配对，则该元组称为悬浮元组，一般被舍弃 自然连接 R S的悬浮元组是？,83,外连接,外连接（OUTER JOIN） 若把舍弃元组(悬浮元组)也保存在结果关系中，而在其他属性上填空值(Null)，这种连接即外连接。,84,

32、左外连接和右外连接,左外连接 如果只把左边关系R中要舍弃的元组保留就叫做左外连接(LEFT OUTER JOIN或LEFT JOIN) 右外连接 如果只把右边关系S中要舍弃的元组保留就叫做右外连接(RIGHT OUTER JOIN或RIGHT JOIN)。,85,左右外连接示例,86,课本示例,87,*半连接 连接运算，结果只取第一个关系中的属性 R S 半连接相当于连接再投影 半连接不具交换性 例： R PAYSCALE PAY S EMP PAYSCALE 1 1000 E1 1 2 2000 E2 2 3 3000 E3 1 E4 2 R S PAYSCALE PAY 语义 1 1000

33、 本系统职工具有的工资级及工资额 2 2000,88,例：查找选课的学生的有关信息 Students SC,89,*自连接 同一个关系自己与自己进行连接运算 对上述关系S 找工资级别相同的雇员对 R S R就是S 改名 R.pascale=S.payscale AND R.emp S.emp EMP PAYSCALE EMP PAYSCALE E1 1 E3 1 E3 1 E1 1 E2 2 E4 2 E4 2 E2 2,90,例:查找比刘雪年龄小的同学的姓名 R:= Students Students1 改名,Students.sageStudents1.sage AND Students1

34、.Sname=刘雪,丌Students.Sname(R),91,Cno Cname Cpno Ccredit 1 C语言 3 2 DS 1 4 3 OS 2 3 4 DB 2 4 5 SE 4 4,例:查找数据库的先修课的先修课的编号 R:=Courses1 Courses 改名,Courses.Cno=Courses1.Cpno AND Courses1.Cname=DB,丌Courses.Cpno(R),92,Cno Cname Cpno Ccredit . 2 DS 1 4 3 OS 2 3 4 DB 2 4 5 SE 4 4,Cno Cname Cpno Ccredit 1 C语言 3

35、 2 DS 1 4 2 DS 1 4 4 DB 2 4,Courses1,Courses,例:查找数据库的先修课的先修课的编号 R:=Courses1 Courses 改名,Courses.Cno=Courses1.Cpno AND Courses1.Cname=DB,丌Courses.Cpno(R),93,主要内容,5.1 一个数据库模式的例子 P118 5.2 关系代数操作 5.3 包上的关系操作 5.4 关系代数的扩展操作 5.5 关系的约束,94,作为约束语言的关系代数,用关系代数表示约束有2种方法 (1) 如果R是关系代数表达式，那么R=表示“R的值必须为空”的约束，与“R中没有元组”等价。 等价于 (2) 如果R和S是关系代数表达式，那么 表示“任何在R中出现的元组都必须在S中出现”的约束。当然S中可以包括其他不在R中