,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第5章 代数和逻辑查询语言,主讲人：颜 颖,Email,：,第5章 代数和逻辑查询语言主讲人：颜 颖,2,主要内容,5.1,包上的关系操作,5.2,关系代数的扩展操作符,5.3,关系逻辑,5.4,关系代数与,datalog,2主要内容5.1 包上的关系操作,3,什么是包,包，也叫多集,(multi),：与集合不同，当关系是包时，同一个元组可以在关系中多次出现。,示例,A,B,1,2,3,4,1,2,1,2,包允许重复元组,元组没有顺序,3什么是包包，也叫多集(multi)：与集合不同，当关系是包,4,为什么采用包,商业,DBMS,实现的关系都是包，而不是集合，重要的原因是采用基于包的关系，一些关系操作的实现效率会更好。例如：,两个包关系的并，只需将一个关系的所有元组复制到另一个关系，而不必消除两个关系中的重复元组,在集合关系上作投影时，需将每一个投影元组与所有元组逐个比较，以确定每次投影只出现一次。而如果接受包作为结果，就可以简单地投影每个元组并将其加入结果中，无须比较，消除重复元组。,4为什么采用包商业DBMS实现的关系都是包，而不是集合，重要,5,示例,把如下关系投影到,A,B,属性上,集合,包,A,B,1,2,3,4,1,2,1,2,A,B,C,1,2,5,3,4,6,1,2,7,1,2,8,A,B,1,2,3,4,效率较高,求,A,的平均值,:,(,1+3)/2=2,与原来关系中,A,的平均值不符,求,A,的平均值：,(1+3+1+1)/4=1.5,与原来关系中,A,的平均值相符,5示例把如下关系投影到A,B属性上集合包AB12341212,6,包的并、交、差,假定,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,中的一次出现,6包的并、交、差假定R和S是包，其中元组t在R中出现了n次，,7,示例,A,B,1,2,3,4,1,2,1,2,A,B,1,2,3,4,3,4,5,6,R,S,A,B,1,2,3,4,1,2,1,2,1,2,3,4,3,4,5,6,A,B,1,2,3,4,A,B,1,2,1,2,A,B,3,4,5,6,RS,RS,R-S,S-R,7示例AB12341212AB12343456RSAB123,8,包上的投影操作,包,A,B,1,2,3,4,1,2,1,2,A,B,C,1,2,5,3,4,6,1,2,7,1,2,8,8包上的投影操作包AB12341212ABC12534612,9,包上的选择操作,在包上应用选择操作的时候，要独立对每个元组应用选择条件，在结果中不去掉重复元组。,示例：,如果,R,是包,A,B,C,1,2,5,3,4,6,1,2,7,1,2,7,包选择,A,B,C,3,4,6,1,2,7,1,2,7,9包上的选择操作在包上应用选择操作的时候，要独立对每个元组应,10,包的笛卡尔积,一个关系中的每个元组跟另外一个关系中的每个元组配对，而不管这个元组是不是重复出现。,如果元组,r,在关系,R,中出现了,m,次，元组,s,在关系,S,中出现了,n,次，那么元组,rs,在,RS,中出现,m*n,次,10包的笛卡尔积一个关系中的每个元组跟另外一个关系中的每个元,11,示例,A,B,1,2,1,2,R,B,C,2,3,4,5,4,5,S,A,R.B,S.B,C,1,2,2,3,1,2,2,3,1,2,4,5,1,2,4,5,1,2,4,5,1,2,4,5,RS,同时属于,R,和,S,两个关系的属性,B,，在积中出现两次，于是属性的前面要加上关系名的前缀,11示例AB1212RBC234545SAR.BS.BC12,12,包的连接,首先对比两个关系中的元组，看是不是能组成一对，如果可以，这个配对起来的元组就是结果中的一员。产生结果时，不需要去掉重复元组。,A,B,1,2,1,2,R,B,C,2,3,4,5,4,5,S,A,B,C,1,2,3,1,2,3,R S,R,R.BS.B,S,A,R.B,S.B,C,1,2,4,5,1,2,4,5,1,2,4,5,1,2,4,5,12包的连接首先对比两个关系中的元组，看是不是能组成一对，如,13,主要内容,5.1,包上的关系操作,5.2,关系代数的扩展操作符,5.3,关系逻辑,5.4,关系代数与,datalog,13主要内容5.1 包上的关系操作,14,关系代数的扩展操作符,(1),消重复操作符,(2),聚集操作符,(3),分组操作,(4),扩展投影,(5),排序算子,(6),外连接算符,14关系代数的扩展操作符(1)消重复操作符,15,(1),消重复操作符,把包中的重复元组去掉，只保留一个拷贝在关系中,用符号,表示，,(R),返回没有重复元组的关系,R,示例：,A,B,1,2,3,4,1,2,1,2,R,A,B,1,2,3,4,(R),15(1)消重复操作符把包中的重复元组去掉，只保留一个拷贝,16,(2),聚集操作符,应用在数值或字符串类型的集合或者包上的操作符，用于汇总或聚集关系某一列中出现的值,SUM,：,产生一列的总和，得到数字值,AVG,：,产生一列的平均值，结果也是数字值,MIN/MAX,：,用于数字值列时，产生该列的最大,/,小值；,用于字符值列时，产生字典序的第一个,/,最后一个值,COUNT,：,产生一列中,“,值,”,的数目,(,包括重复值,),16(2)聚集操作符应用在数值或字符串类型的集合或者包上的,17,聚集操作符示例,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,A,B,1,2,3,4,1,2,1,2,R,17聚集操作符示例SUM(B)=2+4+2+2=10AB12,18,(3),分组,人们不仅希望对简单的一整列作聚集操作，还需要根据元组在一个或多个属性上的值把关系的元组拆分成,“,组,”,，使得聚集操作可以对分好组的各个列进行计算,示例：,title,year,length,genre,studioName,120,Disney,150,MGM,100,Disney,110,Disney,125,MGM,title,year,length,genre,studioName,120,Disney,100,Disney,110,Disney,150,MGM,125,MGM,18(3)分组人们不仅希望对简单的一整列作聚集操作，还需要,19,分组操作符,分组操作符,：下标是一个元素的列表,L,。其中每一个元素是下面情况之一：,分组属性：,应用,操作的关系,R,的一个属性，,R,使用这个属性分组,聚集属性：,应用到关系的一个属性的聚集操作符,为了在结果中给该聚集一个属性名称，使用一个箭头和一个新名字附加在这个聚集后面。,聚集属性需加下划线,19分组操作符分组操作符：下标是一个元素的列表L。其中每一,20,表达式,L,(R),返回关系的过程,把关系,R,的元组分组。每一组由,L,中分组属性为特定赋值的所有元组构成,对于每一组，产生一个如下内容的元组,那个组的分组属性,本组中所有元组对列表,L,的聚集属性进行聚集操作的结果,20表达式L(R)返回关系的过程把关系R的元组分组。每一组,21,示例,1,假设有关系：,Movies(title,year,length,genre,studioName),要计算每一个电影公司出品的电影总长度,studioName,SUM(length)sumOfLength,(Movies),21示例1假设有关系：,22,示例,2,假设有关系：,StarsIn(title,year,starName),请找出至少出演了三部电影的影星,starName,MIN(year)minYear,COUNT(title)ctTitle,(Movies),StarsIn,ctTitle,3,starName,minYear,22示例2 假设有关系：StarsIn(title,ye,23,(4),扩展的投影操作符,普通的投影运算符,上增加一些增强功能的算子，可将变量关系的列作为参数进行计算，并产生新的列。,仍用,L,(R),来表示扩展投影操作，其中投影列表,L,可以是以下所列出的元素之一：,R,的一个属性,形如,xy,的表达式,，,x,和,y,都是属性名，元素,xy,表示把,R,中的,x,属性重命名为,y,在结果模式中出现,形如,Ez,的表达式,，其中,E,是一个涉及,R,的属性、常量、算术运算符或者串运算符的表达式，,z,是表达式,E,计算结果的属性的新名字,23(4)扩展的投影操作符普通的投影运算符上增加一些增强,24,示例,A,B,C,0,1,2,0,1,2,3,4,5,A,X,0,3,0,3,3,9,R,A,B+CX,(R),R1,B-AX,C-BY,(R),X,Y,1,1,1,1,1,1,R2,24示例ABC012012345AX030339R A,25,(5),排序操作符,对关系中的元组按一个或多个属性排序,排序操作符用,来表示,表达式,L,(R),表示的是按照,L,排序的关系,R,本身,其中,R,是关系，,L,是,R,中属性,A,1,A,2,A,n,的列表,那么,R,的元组就先按属性,A,1,的值先排序，对于,A,1,属性相等的元组，就按,A,2,的值排序，依次类推,如果,A,n,属性上的值也相等，则这些元组的顺序可以任意。,25(5)排序操作符对关系中的元组按一个或多个属性排序,26,示例,A,B,C,5,5,3,4,1,3,7,6,5,8,2,6,1,4,7,3,8,4,R,C,B,(R),A,B,C,4,1,3,5,5,3,3,8,4,7,6,5,8,2,6,1,4,7,R,26示例ABC553413765826147384RC,B,27,排序操作符说明,排序操作符是关系代数中唯一一个结果是元组列表的操作符。,如果使用其它操作符到,的排序结果，排序的顺序通常是无意义的。列表上的元素被视为包而不是列表,不过包投影可以保持顺序，选择操作将丢弃关系中不满足选择条件的元组，余下的元组可以按原来的顺序排序,27排序操作符说明排序操作符是关系代数中唯一一个结果是元组列,28,悬浮元组,在一个连接中，若一个元组不能和另外关系中的任何一个元组配对，则该元组称为悬浮元组，一般被舍弃,自然连接,R,S,的悬浮元组是？,28悬浮元组在一个连接中，若一个元组不能和另外关系中的任何一,29,外连接,外连接（,OUTER JOIN,）,若把舍弃元组,(,悬浮元组,),也保存在结果关系中，而在其他属性上填空值,(,Null,),，这种连接即外连接。,R,和,S,的外连接,R,S,29外连接外连接（OUTER JOIN）R和S的外连接R,30,左外连接和右外连接,左外连接,如果只把,左边关系,R,中要舍弃的元组保留,就叫做左外连接,(LEFT OUTER JOIN,或,LEFT JOIN),右外连接,如果只把,右边关系,S,中要舍弃的元组保留,就叫做右外连接,(RIGHT OUTER JOIN,或,RIGHT JOIN),。,30左外连接和右外连接左外连接,31,左右外连接示例,R,和,S,左外连接,R,L,S,R,和,S,右外连接,R,R,S,31左右外连接示例R和S左外连接R L SR和S右,32,课本示例,32课本示例,33,33,人有了知识，就会具备各种分析能力，,明辨是非的能力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”