P130习题5.2.1已知关系R(A,B):{(0,1),(2,3),(0,1),(2,4),(3,4)}S(B,
C):{(0,1),(2,4),(2,5),(3,4),(0,2),(3,4)}计算如下表达式：a)c)δ(R)γ
A,sum(B)(R)k)RLS5.2.2一元操作符f如果满足下面的条件则被称为是幂等的：
对于任何关系R有f(f(R))=f(R)。即，应用f若干次跟应用f一次的结果是一样的。判断下面哪些操作是幂等操作。a
)δb)ΠLc)σCd)γLe)τ5.2.3一种
能用扩展的投影操作来实现，但不能用一般的投影操作来实现的例子是复制列。例如，如果R(A,B)是一个关系，那么对于ΠA,A(R)任何
R中的(a,b)元组产生元组(a,a)。试问这个操作能否用传统的关系代数操作来实现？随着数据技术的不断提高，关系代数也暴露出了一
些局限性，例如无法有效地表示递归运算、逻辑表达能力弱等。在这种情况下，Datalog语言应运而生。Datalog语言是一种基于逻
辑编程语言Prolog的一种非过程化的语言。同关系演算类似，用户只需要给出所描述的信息，不需要给出获取信息的具体过程。本节介绍D
atalog语言的基本结构、规则、递归编程以及从关系代数到Datalog语言的转换等内容。5.4关系逻辑(1)基本概念逻
辑也是一种表示关系查询的方法，例如Datalog语言就可以表示相同类型的查询。Datalog语言不是使用过程语言来表示查询，而是
使用一种规则来表示出这种想法，即可以通过已知的关系中的某些元组的组合来推测元组是否在关系中。基本结构Datalog语言包括两
种基本的原子，即关系原子和算术原子，由原子按照一定的规则组成Datalog查询语句。在Datalog语言中，关系通过“谓词”来
表示，每一个谓词都有固定数量的参数。关系原子是由符号谓词和其后的参数组成，常简称原子。例如，如果谓词是R
，其参数分别是t1，t2，…，tn，那么R(t1，t2，…，tn)就是一个关系原子。算术原子是两个算术表达式的比较，算术原子的值
是布尔值。一般规则规则是Datalog语言中描述原子之间关联的规范，包括下列三个组成部分：1.一个称为头部的关系原子
2.左向箭头符号←，读作if3.主体部分，由一个或多个称为子目标的原子组成。子目标既可以是关系原子，也可以是算术原
子。各个子目标之间用逻辑运算符AND连接，且各个子目标前面可以有选择地增加取反逻辑运算符NOT。规则的目标是使规则的头部关系原子
为真。例如：LongMovie(t,y)←Movies(t,y,l,g,s,p)ANDl≥100等价于LongMovie:
=πtitle,year(σlength≥100(Movies))安全规则安全规则：由于关系实例总是有限，所以还需要
由规则保证得到的头部关系也都是有限的。每个在规则中任意位置出现的变量都必须出现在主体的某些非否定的关系子目标中。尤其是任何在规
则头部、否定关系子目标或任意算术子目标中出现的变量，也必须出现在主体的非否定的关系子目标中。例5.19安全规则Lo
ngMovie(t,y)←Movies(t,y,l,g,s,p)ANDl≥100例5.20非安全规则，不允许出现在Dat
alog中P(x,y)←Q(x,z)ANDNOTR(w,x,z)ANDx指的关系存储在数据库中，称该谓词为扩展谓词。当谓词所指的关系是通过一个或多个Datalog规则计算得到的，称该谓词是内涵谓词。
即扩展谓词和内涵谓词分别对应关系代数表达式中的操作数和使用关系代数表达式计算得到的关系。在Datalog规则中，可
以使用EDB(ExternalDatabase)表示扩展谓词或相应的关系，使用IDB(InternalDatabase)表
示内涵谓词或相应的关系。例如，Movies是一个EDB关系，而LongMovie是一个IDB关系。5.5关系代数
向Datalog规则的转换一般地，可以使用一个或多个Datalog规则来模拟关系代数的运算形式，并且可以模拟非常复杂的运算形式。
本节主要研究如何从关系代数的基本运算形式以及连接运算形式转换到Datalog规则。从集合运算到Datalog规则交集运算可
以使用一个Datalog规则来表示由于交集运算涉及了两个关系，那么在Datalog规则中，具有与两个关系对应的子目标。在规则中，
相应的参数使用相同的变量。假设R和S的关系模式是R(A,B,C)和S(A,B,C)，则R∩S可以使用规则
:I(a,b,c)←R(a,b,c)ANDS(a,b,c)并集运算使用两个规则来表
示每个规则对应一个并集运算中的关系，且两个规则的头部都有相同的IDB谓词；头部的参数与各个子目标中的参数完全相同。
假设R和S的关系模式是R(A,B,C)和S(A,B,C)，则R∪S可以使用规则:U(x
,y,z)←R(x,y,z)U(x,y,z)←S(x,y,z){或
U(a,b,c)←S(a,b,c)}注意：变量名对于规则是局部的，即每条规则是独立计算的，并且向其头部关系提供元组
，与其他规则无关，因此变量名是独立于规则的。差集运算可以使用具有求反子目标的一个规则来计算即如果计算两个关系U和V的差集，非求
反子目标是谓词U，求反子目标是谓词V；在该规则中，子目标和头部对于相应的参数都有相同的变量。
假设R和S的关系模式是R(A,B,C)和S(A,B,C)，则R-S可以使用规则:D(x,y,
z)←R(x,y,z)ANDNOTS(x,y,z)从投影运算到Datalog规则关系代数中的投影运算转换成
Datalog规则使用一个具有单一子目标的规则，该子目标的参数是不同的变量，每个变量代表关系的一个属性；头部是带有参数的原子，
其参数按照期望顺序对应于投影列表的属性。例5.25将关系Movies(title,year,lengt
h,genre,studioName,producerC#)投影到前三个属性：P(t,y,l)←M
ovies(t,y,l,g,s,p)从选择运算到Datalog规则如果选择条件是一个或多个算术比较表达式的AND运算，可以建
立一个具有下列子目标的Datalog规则：一个关系子目标对应于将其进行选择的关系。该关系子目标的每个分量都有不同的变量，且每个分
量都对应关系的一个属性；多个算术子目标，每个算术子目标对应选择条件的一个比较运算。在算术子目标中使用相应的变量，并且与关系子目标
中建立的变量保持一致。复杂条件可以将逻辑表达式转化成“析取范式”，即正负文字的合取的析取。例5.26σlength≥100
andstudioName=‘Fox’(Movies)S(t,y,l,g,s,p)←Movies(t,y,l
,g,s,p)ANDl≥100ANDs=‘Fox’例5.27σlength≥100orstudioName=‘F
ox’(Movies)S(t,y,l,g,s,p)←Movies(t,y,l,g,s,p)ANDl≥10
0S(t,y,l,g,s,p)←Movies(t,y,l,g,s,p)ANDs=‘Fox’例5.28σNO
T(length≥100orstudioName=‘Fox’）(Movies)根据狄摩根定律，等价于σ(NOT
(length≥100)AND(NOT(studioName=‘Fox’)）(Movies)即σlength
<100ANDstudioName≠‘Fox’(Movies)再转化为Datalog规则：S(t,y,l,g
,s,p)←Movies(t,y,l,g,s,p)ANDl<100ANDs≠‘Fox’从笛卡尔乘积到Datalo
g规则R×S可以使用单一的Datalog规则来表示规则包含两个子目标，一个对应R一个对应S，两个子目标有不同的变量分别对应R
和S的属性。头部IDB谓词拥有所有在这两个子目标中出现的参数，R子目标中的变量列在S子目标中变量的前面。
p(a,b,c,x,y,z)←R(a,b,c)ANDS(x,y,z)从连接运算到Datalog规则自然连接R
S使用一条近似于笛卡尔积的Datalog规则来表示，区别在于R和S的同名属性使用相同的变量，否则使用不同的变量。规则头部是一个
IDB谓词，它的每个变量出现一次。假设R和S的关系模式是R(A,B)和S(B,C,D)，则自然连接RS
可以用规则J(a,b,c,d)←R(a,b)ANDS(b,c,d)θ连接先对笛卡尔积进
行转化，再对选择条件进行转化。例5.32考虑关系U(A,B,C)和V(B,C,D)，其θ连接
对应的Datalog规则：J(a,ub,
uc,vb,vc,d)←U(a,ub,uc)ANDV(vb,vc,d)ANDaJ(a,ub,uc,vb,vc,d)←U(a,ub,uc)ANDV(vb,vc,d)ANDauc,vb,vc,d)←U(a,ub,uc)ANDV(vb,vc,d)ANDub≠vbUAU.B≠V.BVUA系代数的表达式树。其中，表达式树就是使用树状结构表示关系代数表达式的计算程序。表达式树的叶子节点由相应的扩展谓词EDB表示；为
表达式树的每一个内部节点建立一个IDB谓词。IDB谓词的一条或多条规则对应树节点上需要使用的算子。代数表达式的结果就是与表达树根
相关联的谓词关系。包的逻辑运算关系代数和Datalog规则都可以运用于包运算。将Datalog规则应用于包时，其运算步骤如
下：第一步，对不同子目标对应的关系进行包连接运算；第二步，按照算术子目标包含的内容，对连接运算的结果进行包选择运算；第三步，
把选择结果按照规则头部的关系进行包投影运算。例如：求Πx.z(R(x,y)S(y,z))
H(x,z)←R(x,y)ANDS(y,z)R=S=H=Datalog与关系代数的比较基本关系代数的每一种操
作都可以用Datalog查询表达，但扩展关系代数中的分组和聚集等操作无法用Datalog表达。任何单个Datalog规则都可以用
关系代数表达，但Datalog可以表达递归，而关系代数不能。由于IDB谓词也可以在主体中出现，于是规则头部的元组可以反馈到规则主
体，从而为头部生成更多的元组。例5.35：假定关系Edge(X,Y)，表示从节点X到节点Y直接存在一条边，关系Path
(X,Y)表示从节点X到节点Y存在一条长度至少为1的路径，则描述边的传递闭包为：Path(X,Y
)←Edge(X,Y)Path(X,Y)←Edge(X,Z)ANDPath(Z,Y)
机械三P141习题5.4.1d)g)5.4.2b)e)5.4.5
a)第五章代数和逻辑查询语言5.1关系代数操作(1)关系代数的传统定义一个元组集合(即关系)，能用来进
行典型的基于关系的查询集合上的五个操作：并、差、笛卡尔积、选择、投影在基本操作上定义的附加操作：各种连接关系代数的操作规则对
于集合和包是不一样的简单的说，包是以空间代价换取时间效率所以对一般小例子来说，包的综合效率更高但对实际应用中的数据库来说，用
集合更加合理5.1关系代数操作(2)关系中的集合操作基本集合操作：并、交、差应用到关系操作时，需要附加约束属性列表和属
性类型必须一致属性的排列顺序也要一致原则上属性名也要对应一致，如果不一致，需要利用重命名操作处理5.1关系代数操作(3)
投影πA1,A2,…,An(R)只保留指定部分列由于属性减少，元组可能会因为重值而合并，因此数目可能减少选择σC(R)该操
作产生的新关系的元组必须满足条件C结果关系和原关系的模式相同5.1关系代数操作(4)笛卡尔积R×S一个有序对的集合，有
序对的第一个元素来自R，第二个元素来自S一般地，笛卡尔积对应一个关系，其元组维度更大，个数更多如果R和S有重名属性，则在结果中
加前缀区分连接操作参与连接操作的一般是两个关系，且连接时相应的元组在某些方面具有一致性，连接分为三类全连接即笛卡尔积自然连
接θ连接5.2包上的关系操作(1)一组元素的一种聚集形式，允许重复元素出现，而集合set中不允许元素重复出现。对一个
包去掉其中重复元素，就可得到一个集合。一个集合可认为是一个特殊的包，其中没有重复元组。什么是包bag为何需要包关系中的
元组应该不重复，但经运算得到的新关系中的元组可以重复；数据库系统支持提高投影计算效率对聚合运算有用(汇总值、平均值、计数等)
5.2包上的关系操作(2)包上的运算：集合并(交、差)、投影、选择、乘积和连接等都允许运算之前和之后元组重复对两个关系求并，
集合方式要先合并再去重，而包方式只合并不去重，所以效率更高投影操作后不去重对后面要出现的聚集操作来说，只能用包方式，用集合方式
的话会出现逻辑错误。例：求投影后A属性的平均值包的并、交、差设R和S是包，若元组t在R和S中分别出现m次和n次（这里
的m和n可以是0），则：R∪S的包并操作结果中：元组t出现m+n次；R∩S的包交操作结果中：元组t出现min(m,
n)次；R-S的包差操作结果中：元组t出现max(0,m-n)次；/减后为负数则取0包的并、交、差举例：设关系R、S
如下：AB13112422AB13352446R∪S：AB131113
3524222446R∩S：AB1324R-S：AB1122R=S=5.2
包上的关系操作(3)集合上的包操作（文本框内容释义）如果对两个集合R、S进行基于包的交和差操作，其结果与集合方式运算一样因
为作为被处理对象的两个关系本身没有重复的元组，所以交或差之后结果中仍然没有重值元组但对两个集合R和S，进行基于包的并操作，其操作
结果可能不再是集合结论：必须看清（答题）/声明（出题）是包方式还是集合方式5.2包上的关系操作(4)关于包的代数定律并运
算的交换律对包和集合都成立R∪S=S∪R差运算对并的分配律只适用于集合而不能适用于包(R∪S)-
T=(R-T)∪(S-T)假设R,S和T各有元组t的一个副本包的投影操作和集合操作基本一致，只是不再需要去重包的选择
操作也是不需要去重R=5.2包上的关系操作(5)包的笛卡尔积一样，不去重包的连接自然连接θ连接R=
S=R×S=RS=5.3关系代数的扩展操作(1)1.消除重复清除包中的重复元素，只保留一个副本在关系中2
.聚集操作独立于同一关系中的其它元组而对某些元组进行运算3.分组根据元组的值对他们在一个或多个属性上分组4.排序根据一个
或多个属性对关系的元组来排序5.扩展投影以原有的列作为参数来计算，并产生新的列6.外连接运算连接运算的变体，防止了悬浮元组
的出现消除重复将包转化为集合δ(R)例5.8AB13112422AB1324Rδ(R)
聚集操作符汇总或“聚集”关系中某一列出现的值SUM用来产生一列总和，得到的是一个数字值AVG用来产生一列平均值，结果也是数
字值MAX和MIN当用于数字值列的时候，产生的分别是这一列中最大的和最小的值；当应用于字符列的时候产生是字典序的最大者和最小者
COUNT产生一列中的“值”的数目(并不一定指不同的值)。同样，COUNT应用于一个关系的任何属性时，产生的是这个关系的元组数，包
括重复的元组例子考虑关系AB123412121.SUM(B)=2+4+2+2=102.AVG(
A)=(1+3+1+1)/4=1.53.MIN(A)=14.MAX(B)=45.COUNT(A)=4分组操作为什么
要分组分组是便于各分组中元组的聚集。如何分组算符γ的下标是一个元素的列表，其中每个元素是
下列情况之一：⑴分组属性：应用γ操作将R中在分组属性上取值相同的元组分为一组。⑵聚集属性：应用到关系的一个属性上的
聚集操作符(max,min,sum,avg,count)。为了在结果中对应此聚集，用一个箭头和一个新的名字附在这个聚集的后面。分
组操作符γL(R)分组操作符的下标是一个元素的列表L，可以是：应用γ操作的关系的一个属性，R使用这个属性分组，称为分组属性；
例如：图5-4γstudioname(Movies)应用到关系的一个属性上的聚集操作符，可以使用箭头给聚集属性
列命名；例如：γstudioname，SUM(length)?sumOFLength(Movies)表达式γL
(R)的求解过程根据L中的分组属性，按照该属性上的不同取值进行分组对每一组产生一个元组，包括：L中的分组属性|该组在分
组属性上的值L中的属性聚集结果（箭头右侧属性）例5.23对关系StarsIn(title,year,starNam
e),查询至少出演了三部电影的影星，以及他们在电影中出现的最早年份。γstarname，MIN(year)?minYear,
COUNT(title)?ctTitle(StarsIn)先聚集，再选择，最后投影得到结果设关系student（学生）
、course（课程）和sc（成绩）如下：学号sno姓名sname性别sex年龄sage系sdept9500
1950029500395004李勇刘晨王敏张立男女女男20191819CSISMAIS课
程号cno课程名cname先行课cpno学分credit1234567数据库数学信息系统操作系
统数据结构数据处理C语言516764243424学号sno课程号Cno成绩grade
9500195001950019500295002123239285889080分组操作符举例γ
1、查询各个专业的学生人数及平均年龄2、统计各门课的平均成绩、最高成绩、最低成绩及选修人数3、查询被两个以上同学选修的
课程的课程名及平均成绩γsdept，count(sno)?snum,avg(sage)?avgage(student)
注意：分组后取出姓名、学号、性别是没意义的γcname,avg(grade)?avggrade,max(grade)?
maxgrade,count(sno)?snum(coursesc)Πcname,avggrade(σsnum
>=2(γcname,avg(grade)?avggrade,count(sno)?snum(coursesc)))扩
展的投影操作符ΠL(R)扩展投影是在投影的基础上增加一些计算操作作为投影列表；投影列表可以是：关系R的一个属性；形如x→
y的表达式：将R中的属性x重命名为y；形如E→z的表达式，其中E是一个涉及R的属性、常量、算术运算符或者串运算符表达式，z是表
达式E计算结果的属性的新名字。例子设有关系RABC012012345xY111111
AX030339∏A,B+C→X(R)∏B-A→X,C-B→Y(R)排序操作τL(R)表达式τL(R)，其
中R是关系，L是R中的某些属性的列表。这个表达式表示的就是关系R的本身，只是结果中的所有元组是按L来排序的。设L是由A1,A2,
…,An组成，那么R的元组就先按A1的值排序，对于A1属性相等的元组则按A2的值排序，依次类推。外连接自然连接操作的缺陷
自然连接操作的一个性质是可能产生悬挂元组。而这些元组不能跟另外关系的任何一个元组匹配，所以这种连接操作并不能完全反映原始
关系的全部信息。什么是外连接先计算两个关系R和S的自然连接，然后再把来自R或S的悬浮元组加入其中，用null
的表示符号补齐结果元组中那些不具有值的属性。我们称之为外连接，用符号表示。设有关系ABC123456789BCD231023116712UVABCD12310123114567896712UV外连接的不同变体只是将左变量R的悬浮元组补齐加入到结果中，称之左外连接，用符号RLS表示。只是将右变量S的悬浮元组补齐加入到结果中，称之左外连接，用符号RRS表示。θ外连接的操作是，先进行θ连接，然后将那些不能匹配其他关系的元组，也用补齐，用UCV表示一个带条件C的θ外连接。同样，可用L或R来修饰这个算符，使其表示θ的左外连接或右外连接。ABCD12310123116712ABCD1231012311456789ULVURVUA>V.CVAU.BU.CV.BV.CD45623104562311789231078923111236712P1255.1.15.1.4a)h)5.1.5(扩展操作)P1305.2.15.2.25.2.3 |
|
