第5章 关系代数.ppt

第5章关系代数,主讲人：喻小光Email：40016076,2,主要内容,5.1一个数据库模式的例子P1185.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,address:string,gender:char,birthdate:date)MoiveExec(name:string,address:srting,CERT#:integer,netWorth:integer)Studio(name:string,address:string,presC#:integer),4,关系代数一种抽象的查询语言关系模型数据操纵语言的一种传统的表达方式使用户可以对数据进行查询和修改,关系代数表达的运算总是由旧关系构造新关系运算对象-关系运算结果-关系运算符：.查询（更新）：关系代数表达式关系代数基础:代数通常是由一些操作符和一些原子操作数组成,5,关系代数运算分类:,1.传统集合运算：并、交、差,2.删除部分数据的运算:选择(删行)、投影(删列、),3.合并关系元组的运算:连接（两个关系中的元组有选择地组成对）笛卡尔积(两个关系中的元组以所有可能的方式组成对),4.改变关系模式(关系名、属性名):改名,6,1.关系的集合运算关系R和S是元组的集合(不存在重复元组)前提：R和S的模式具有相同的属性集(属性域匹配)且属性顺序相同属性名不同，可以改名。,等价的说法：“并相容”-属性数目相同，对应属性取自同一个域。假定，结果关系的模式使用R的名字。,7,RS:R和S的并由R或S中的元组组成,RS=R-(R-S),RS:R和S的交由R和S中都存在的元组组成,R-S:R和S的差由在R中而不在S中的元组组成,8,例：R：选修数据结构的学生学号姓名年龄班级010812张明180108010820李力190108S：选修操作系统的学生学号姓名年龄班级010812张明180108010814陈东190108,9,1）查询选修数据结构或操作系统的学生信息RS学号姓名年龄班级010812张明180108010820李力190108010814陈东190108,10,2）查询选修数据结构及操作系统的学生信息RS学号姓名年龄班级010812张明180108,11,3）查询选修数据结构没选修操作系统的学生信息R-S学号姓名年龄班级010820李力190108,岳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张明180108010820李力190108011004童雪180110,丌年龄(学生),年龄1819,14,P120例5.2查询所有电影的片名、年份、长度P121图5-3关系的实例Movies(title,year,length,inColor,studioName,producerC#),丌title,year,length(Movies)结果：P121,查询所有电影的类型丌inColor(Movies),inColortrue,15,3.选择关系R上的选择运算，即从指定关系中选择满足一定条件C的元组,得到新的关系。结果集的模式与R相同.记：C(R)一元运算,C是一个条件，取值为“true”或“false”。C由逻辑运算符ORANDNOT连接各条件表达式组成。,条件表达式形如XY，是比较运算符=，,18(学生),学号姓名年龄班级010820李力190108010814陈东190108,查询的实现：依次考察每一个元组，满足条件的放入结果集,17,对于P121图5-3Movies(title,year,length,genre,studioName,producerC#),例5.3查询片长在100分钟以上的电影的信息,length=100(Movies),例5.4查询制片公司为Fox的且片长在100分钟以上的电影的信息length=100ANDstudioName=Fox(Movies),18,4.笛卡尔积R和S的笛卡尔积(即乘积)是有序对的集合：由R的元组和S的元组构成更长的元组。有序对的第1个元素是关系R的任何一个元组第2个元素是关系S的任何一个元组.记作:RS,结果关系模式中的属性:由R的属性和S的属性构成。,当R和S有公共属性A时，分别用R.A和S.A表示。,19,R：ABS：BCD122563447891011,RSAR.BS.BCD1225612478129101134256344783491011,P122例5.5,20,例：R学号姓名兴趣班0202李一美术0202李一电脑0205吴晓电脑0304石玉美术S兴趣班老师美术张电脑郑,21,RS学号姓名R.兴趣班S.兴趣班老师0202李一美术美术张0202李一电脑电脑郑0202李一美术电脑郑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：ABS：BCD122563447891011,ABCD12563478公共属性：B去掉重复列,P123例5.6,24,P123例5.7两个公共属性,R:ABC123678978,S:BCD2342357810,ABCD123412356781097810,25,例：R学号姓名兴趣班0202李一美术0202李一电脑0205吴晓电脑0304石玉美术S兴趣班老师美术张电脑郑,RS学号姓名兴趣班老师0202李一美术张0202李一电脑郑0205吴晓电脑郑0304石玉美术张公共属性：兴趣班,26,RS学号姓名兴趣班老师0202李一美术张0202李一电脑郑0205吴晓电脑郑0304石玉美术张公共属性：兴趣班,27,自然连接由笛卡尔积、选择、投影三个步骤实现的：笛卡尔积：拼接元组选择：选出公共属性上相同的行投影：去掉一组公共属性,自然连接符合结合律：(R1R2)R3等价于R1(R2R3)可简记为R1R2R3悬挂元组：在一个连接中，不能和另外关系中的任何元组配对的元组。,28,6.连接R和S基于条件C的连接,记为:RCS1)RS2)选满足条件C的元组3)重名属性通过附加前缀的办法进行处理结果关系模式的属性:由R的属性和S的属性组成。笛卡尔积、选择连接自然连接和连接的区别前者要将公共属性合并，后者不合并原因：条件连接时，相同属性的属性值不一定约束成等值关系，而要合并的话，基本前提肯定是要等值.,29,R:ABC123678978,S:BCD2342357810,P123例5.8,RA=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,综合示例学生-课程数据库:Students(Sno,Sname,Ssex,Sage,Sdept)Courses(Cno,Cname,Cpno,Ccredit)Cpno先修课号SC(Sno,Cno,Grade),Students:SnoSnameSsexSageSdept020501李勇男20计算机020502刘雪女19计算机020503王敏女18经管020504张功男19计算机,35,SnoCnoGrade020501198020501277020502165020502280020502493,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连接用Sno,例：查询选修了课程的学生的名字,40,解2：,丌Sno,Sname(Students),丌Sno(SC),先投影？先连接？先选择？交集？组合成多种解法一般参与运算（尤其连接运算）的数据越少速度越快,41,例：查询选修4学分课程，成绩在90以上的同学的学号,其他解法,CoursesSC连接：Cno,42,例:查询选修了以2号课为先修课的课程的学生的名字,CpnoCoursesSnameStudents必须借助SC表连接,解1：,43,解2:,Cpno=2(Courses),丌Sno,Sname(Students),44,例：选修数据结构课的学生的名字,名字在表Students中课程名在Courses中无公共属性用SC,45,例：没有选修数据结构课的学生的名字,全体学生除去选修的,46,例：求至少选了一门4学分课程的同学的名字,CoursesStudentsSC,解1：,Ccredit=4(Courses),Ccredit=4(Courses)SCStudents,丌Sname(Ccredit=4(Courses)SCStudents),47,解2：,Ccredit=4(Courses),丌Cno(Ccredit=4(Courses),丌Sno,sname(Students),48,8.改名(重命名)改名运算:S(A1,A2,An)(R)将关系名R改为S、S的属性依次命名为A1,A2,AnS(R)将关系名R改为S,49,P125例5.12：R(A,B)S(B,C,D)求RS不用R.BS.B改名:,法2:RS(A,B,X,C,D)(RS),法1:S(X,C,D)(S)S(X,C,D)RS(X,C,D)(S),50,9.基本和导出运算（操作之间的联系）关系代数的某些运算可以由其他运算导出RS=R-(R-S),51,U:ABC123678978,V:BCD2342357810,ABCD123412356781097810,丌A,U.B,U.C,D(U.B=V.BANDU.C=V.C(UV),P127例5.13（1）,52,P127例5.13（2）,R:ABC123678978,S:BCD2342357810,53,其余的6个运算:并,差,选择,投影,乘积,改名构成独立集，其中任一个不能由其他5个给出。称为去：关系代数操作集合的最小化完备集,54,9.关系代数表达式中的线性符号复杂的关系代数表达式：1）表达式树2）线性符号生成若干临时关系，用来表示树的内节点，并写一系列的赋值语句使其具有正确的值。涉及的符号：关系名（属性列表）赋值符号：=写在赋值号右边的任何代数表达式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):=studioName=Fox(Movies),R(t,y,l,i,s,p):=length=100(Movies),56,主要内容,5.1一个数据库模式的例子P1185.2关系代数操作5.3包上的关系操作5.4关系代数的扩展操作5.5关系的约束,57,什么是包,包，也叫多集(multi)：与集合不同，当关系是包时，同一个元组可以在关系中多次出现。例5.15,包允许重复元组元组没有顺序,58,为什么采用包,商业DBMS实现的关系都是包，而不是集合，重要的原因是采用基于包的关系，一些关系操作的实现效率会更好。例如：两个包关系的并，只需将一个关系的所有元组复制到另一个关系，而不必消除两个关系中的重复元组在集合关系上作投影时，需将每一个投影元组与所有元组逐个比较，以确定每次投影只出现一次。而如果接受包作为结果，就可以简单地投影每个元组并将其加入结果中，无须比较，消除重复元组。,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,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两个关系的属性B，在积中出现两次，于是属性的前面要加上关系名的前缀,66,包的连接,首先对比两个关系中的元组，看是不是能组成一对，如果可以，这个配对起来的元组就是结果中的一员。产生结果时，不需要去掉重复元组。示例5.20,R,S,67,主要内容,5.1一个数据库模式的例子P1185.2关系代数操作5.3包上的关系操作5.4关系代数的扩展操作5.5关系的约束,68,关系代数的扩展操作符,(1)消重复操作符(2)聚集操作符(3)分组操作(4)扩展投影(5)排序算子(6)外连接算符,69,(1)消重复操作符,把包中的重复元组去掉，只保留一个拷贝在关系中用符号表示，(R)返回没有重复元组的关系R示例：,R,(R),70,(2)聚集操作符,应用在数值或字符串类型的集合或者包上的操作符，用于汇总或聚集关系某一列中出现的值SUM：产生一列的总和，得到数字值AVG：产生一列的平均值，结果也是数字值MIN/MAX：用于数字值列时，产生该列的最大/小值；用于字符值列时，产生字典序的第一个/最后一个值COUNT：产生一列中“值”的数目(包括重复值),71,聚集操作符示例,SUM(B)=2+4+2+2=10AVG(A)=(1+3+1+1)/4=1.5MIN(A)=1MAX(B)=4COUNT(A)=4,R,72,(3)分组,人们不仅希望对简单的一整列作聚集操作，还需要根据元组在一个或多个属性上的值把关系的元组拆分成“组”，使得聚集操作可以对分好组的各个列进行计算示例：,73,分组操作符,分组操作符：下标是一个元素的列表L。其中每一个元素是下面情况之一：分组属性：应用操作的关系R的一个属性，R使用这个属性分组聚集属性：应用到关系的一个属性的聚集操作符为了在结果中给该聚集一个属性名称，使用一个箭头和一个新名字附加在这个聚集后面。,74,示例1,假设有关系：Movies(title,year,length,genre,studioName)要计算每一个电影公司出品的电影总长度studioName,SUM(length)sumOfLength(Movies),75,表达式L(R)返回关系的过程,把关系R的元组分组。每一组由L中分组属性为特定赋值的所有元组构成对于每一组，产生一个如下内容的元组那个组的分组属性本组中所有元组对列表L的聚集属性进行聚集操作的结果,76,示例2,假设有关系：StarsIn(title,year,starName)请找出至少出演了三部电影的影星，以及他们在电影中出现的最早年份,77,(4)扩展的投影操作符,普通的投影运算符上增加一些增强功能的算子，可将变量关系的列作为参数进行计算，并产生新的列。仍用L(R)来表示扩展投影操作，其中投影列表L可以是以下所列出的元素之一：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,81,排序操作符说明,排序操作符是关系代数中唯一一个结果是元组列表的操作符。这样，从查询的表达方面来讲，它只能作为一串操作的最后一个算符来使用才有意义。如果使用其它操作符到的排序结果，排序的顺序通常无意义。不过包投影可以保持顺序，选择操作将丢弃关系中不满足选择条件的元组，余下的元组可以按原来的顺序排序,82,悬浮元组,在一个连接中，若一个元组不能和另外关系中的任何一个元组配对，则该元组称为悬浮元组，一般被舍弃自然连接RS的悬浮元组是？,83,外连接,外连接（OUTERJOIN）若把舍弃元组(悬浮元组)也保存在结果关系中，而在其他属性上填空值(Null)，这种连接即外连接。,84,左外连接和右外连接,左外连接如果只把左边关系R中要舍弃的元组保留就叫做左外连接(LEFTOUTERJOIN或LEFTJOIN)右外连接如果只把右边关系S中要舍弃的元组保留就叫做右外连接(RIGHTOUTERJOIN或RIGHTJOIN)。,85,左右外连接示例,86,课本示例,87,*半连接连接运算，结果只取第一个关系中的属性RS半连接相当于连接再投影半连接不具交换性例：RPAYSCALEPAYSEMPPAYSCALE11000E1122000E2233000E31E42RSPAYSCALEPAY语义11000本系统职工具有的工资级及工资额22000,88,例：查找选课的学生的有关信息StudentsSC,89,*自连接同一个关系自己与自己进行连接运算对上述关系S找工资级别相同的雇员对RSR就是S改名R.pascale=S.payscaleANDR.empS.empEMPPAYSCALEEMPPAYSCALEE11E31E31E11E22E42E42E22,90,例:查找比刘雪年龄小的同学的姓名R:=StudentsStudents1改名,Students.sageStudents1.sageANDStudents1.Sname=刘雪,丌Students.Sname(R),91,CnoCnameCpnoCcredit1C语言32DS143OS234DB245SE44,例:查找数据库的先修课的先修课的编号R:=Courses1Courses改名,Courses.Cno=Courses1.CpnoANDCourses1.Cname=DB,丌Courses.Cpno(R),92,CnoCnameCpnoCcredit.2DS143OS234DB245SE44,CnoCnameCpnoCcredit1C语言32DS142DS144DB24,Courses1,Courses,例:查找数据库的先修课的先修课的编号R:=Courses1Courses改名,Courses.Cno=Courses1.CpnoANDCourses1.Cname=DB,丌Courses.Cpno(R),93,主要内容,5.1一个数据库模式的例子P1185.2关系代数操作5.3包上的关系操作5.4关系代数的扩展操作5.5关系的约束,94,作为约束语言的关系代数,用关系代数表示约束有2种方法(1)如果R是关系代数表达式，那么R=表示“R的值必须为空”的约束，与“R中没有元组”等价。等价于(2)如果R和S是关系代数表达式，那么表示“任何在R中出现的元组都必须在S中出现”的约束。当然S中可以包括其他不在R中出现的元组。等价于R-S=,RS,R,95,引用完整性约束,即前面所学的“参照完整性约束”复习若属性(组)F是基本关系R的外码，它与基本关系S的主码Ks相对应，则对于R中每个元组在F上的值必须为：空值(F的每个属性值均