第五章 关系数据理论
1. 在关系模式R(D,E,G)中,存在函数依赖关系{E→D,(D,G)→E},则候选码是__________,关系模式R(D,E,G)属于____________。
正确答案: (E,G),(D,G) 3NF
2. 理解并给出下列术语的定义: 函数依赖、部分函数依赖、完全函数依赖、传递依赖、候选码、主码、 外码、全码(All-key)、1NF、2NF、3NF、BCNF、多值依赖、4NF。
正确答案: 函数依赖:设R (U)是一个关系模式,U是R的属性集合,X和Y是U的子集。对于R (U)的任意一个可能的关系r,如果r中不存在两个元组,它们在X上的属性值相同, 而在Y上的属性值不同, 则称“X函数确定Y"或“Y函数依赖于X",记作X→Y。 *解析: 1)函数依赖是最基本的一种数据依赖,也是最重要的一种数据依赖。 2)函数依赖是属性之间的一种联系,体现在属性值是否相等。由上面的定义可以知道,如果X→Y,则r中任意两个元组,若它们在X上的属性值相同,那么在Y上的属性值一定也相同。 3)我们要从属性间实际存在的语义来确定他们之间的函数依赖,即函数依赖反映了(描述了)现实世界的一种语义。 4)函数依赖不是指关系模式R的在某个时刻的关系(值)满足的约束条件,而是指R任何时刻的一切关系均要满足的约束条件。 答: 完全函数依赖、部分函数依赖:在R(U)中,如果X→Y,并且对于X的任何一个真子集X,都有X′→Y,则称Y对X完全函数依赖,记作: 若X→Y,但Y不完全函数依赖于X,则称Y对X部分函数依赖,记作: 传递依赖:在R(U)中,如果X →Y,(Y X),Y →X,Y→Z,则称Z对X传递函数依赖。 候选码、主码: 设K为R中的属性或属性组合,若K → U则K为R的候选码(Candidate key)。若候选码多于一个,则选定其中的一个为主码(Primary key)。 *解析: 1) 这里我们用函数依赖来严格定义码的概念。在第二章中我们只是描述性地定义码(可以复习2.2.1):若关系中的某一属性组的值能唯一地标识一个元组,则称该属性组为候选码(Candidate key)。 2)因为码有了严格定义,同学在学习了《概论》5.3数据依赖的公理系统后就可以从R的函数依赖集F出发,用算法来求候选码。 答: 外码:关系模式R中属性或属性组X并非R的码,但X是另一个关系模式的码,则称X是R的外部码(Foreign key)也称外码。 全码:整个属性组是码,称为全码(All-key)。 答: 1NF:如果一个关系模式R的所有属性都是不可分的基本数据项,则R∈1NF。 *解析:第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。 答: 2NF:若关系模式R∈1NF,并且每一个非主属性都完全函数依赖于R的码,则R∈2NF。 3NF:关系模式R 中若不存在这样的码X,属性组Y及非主属性Z(Z Y)使得X→Y,(Y → X)Y→Z,成立,则称R 3NF。 BCNF:关系模式R 1NF。若X→Y且Y X时X必含有码,则R BCNF。 *解析: 同学们要真正理解这些范式的内涵。各种范式之间的联系:5NF 4NF BCNF 3NF 2NF lNF(《概论》上图5.2)。能够理解为什么有这种包含关系。 答: 多值依赖:设R(U)是属性集U上的一个关系模式。X,Y,Z是U的子集,并且Z=U-X-Y。关系模式R(U)中多值依赖X→→Y成立,当且仅当对R(U)的任一关系r,给定的一对(x,z)值,有一组Y的值,这组值仅仅决定于x值而与z值无关。 4NF:关系模式R lNF,如果对于R的每个非平凡多值依赖X→→Y(Y X),X都含有码,则称R 4NF。 *解析: 对于多值依赖的定义有多种。《概论》上定义 5.9后面又给出了一种等价的定义。习题中的第4题是另一种等价的定义。同学们可以对比不同的定义来理解多值依赖。选择自己容易理解的一种定义来掌握多值依赖概念。
3. 在关系模式R(A,C,D)中,存在函数依赖关系{ A→C,A→D },则候选码是___________ ,关系模式R(A,C,D)最高可以达到_____________ 。
正确答案: A BCNF
4.试由Armostrong公理系统推导出下面三条推理规则: (1) 合并规则:若X→Z,X→Y,则有X→YZ (2) 伪传递规则:由X→Y,WY→Z有XW→Z (3) 分解规则:X→Y,Z Y,有X→Z
正确答案: (1) 已知X→Z,由增广律知XY→YZ,又因为X→Y,可得XX→XY→YZ,最后根据传递律得X→YZ。 (2) 已知X→Y,据增广律得XW→WY,因为WY→Z,所以XW→WY→Z,通过传递律可知XW→Z。 (3) 已知Z Y,根据自反律知Y→Z,又因为X→Y,所以由传递律可得X→Z。
5.关于多值依赖的另一种定义是: 给定一个关系模式R(X,Y,Z),其中X,Y,Z可以是属性或属性组合。 设x∈X,y∈Y,z∈Z,xz在R中的像集为: Yx z = {r.Y | r.X=x ∧ r.Z = z ∧ rR} 定义 R(X,Y,Z)当且仅当Yxz =Yxz′对于每一组(x,z,z′)都成立,则Y对X多值依赖,记作X→→Y。这里,允许Z为空集,在Z为空集时,称为平凡的多值依赖。 请证明这里的定义和《概论》5.2.7节中定义5.9是等价的。
正确答案: 设Yxz=Yxz’对于每一组(x,z,z′)都成立,现证其能推出定义5.9的条件: 设s、t是关系r中的两个元组,s[X]= t[X],由新定义的条件知对于每一个z值,都对应相同的一组y值。这样一来,对相同的x值,交换y值后所得的元组仍然属于关系r,即定义5.9的条件成立; 如果定义5.9的条件成立,则对相同的x值,交换y值后所得的元组仍然属于关系r,由于任意性及其对称性,可知每个z值对应相同的一组y值,所以Yxz=Yxz’对于每一组(x,z,z′)都成立。 综上可知,新定义和定义5.9的条件是等价的,所以新定义和定义5.9是等价的。
6.试举出三个多值依赖的实例。
正确答案: (1) 关系模式MSC(M,S,C)中,M表示专业,S表示学生,C表示该专业的必修课。假设每个专业有多个学生,有一组必修课。设同专业内所有学生的选修的必修课相同,实例关系如下。按照语义对于M的每一个值M i,S有一个完整的集合与之对应而不问C取何值,所以M→→S。由于C与S的完全对称性,必然有M→→C成立。 (2) 关系模式ISA(I,S,A)中,I表示学生兴趣小组,S表示学生,A表示某兴趣小组的活动项目。假设每个兴趣小组有多个学生,有若干活动项目。每个学生必须参加所 在兴趣小组的所有活动项目,每个活动项目要求该兴趣小组的所有学生参加。 按照语义有I→→S,I→→A成立。 (3) 关系模式RDP(R,D,P)中,R表示医院的病房,D表示责任医务人员,P表示病人。假设每个病房住有多个病人,有多个责任医务人员负责医治和护理该病房的所有病人。按照语义有R→→D,R→→P成立。
7.试证明《概论》上给出的关于FD和MVD公理系统的A4,A6和A8。
正确答案: A4:若X→→Y,VWU,则XW→→YV 设Z=U-X-Y 已知X→→Y,设r是R上的任一关系,s、t∈r,且t[X]=s[X],则存在元组p、q∈r,使p[X]=q[X]=t[X],而p[Y]=t[Y],p[Z]=s[Z],q[Y]=s[Y],q[Z]=t[Z]。 设t[XW]=s[XW],我们以上构造的元组p和q,是某部分属性在s和t上翻转而成,所以p[W]=q[W],可知p[XW]=q[XW],同理p[YV]=t[YV](由VW知t[V]=s[V]),q[YV]=s[YV],p[U-YV-XW]=s[U-YV-XW](因为U-YV-XWZ),q[U-YV-XW]=t[U-YV-XW]。所以XW→→YV。 A6:若X→→Y,Y→→Z则X→→Z-Y 由Y→→Z容易证得Y→→Z-Y。 设R1=U-X-Y,R2=U-Y-Z,R3=U-X-Z+Y。 已知X→→Y,设r是R上的任一关系,s、t∈r,且t[X]=s[X],则存在元组p、q∈r,使p[X]=q[X]=t[X],而p[Y]=t[Y],p[R1]=s[R1],q[Y]=s[Y],q[R1]=t[R1]。 对元组t、p,已知t[Y]=p[Y],t[X]=p[X],由Y→→Z-Y知:存在元组m∈r,使m[Z-Y]=p[Z-Y],m[R2]=t[R2]。因为(Z-Y)R1,又p[R1]=s[R1],所以m[Z-Y]=s[Z-Y]。因为元组p和s在除属性Y之外的属性上值相等,所以m[R2]=t[R2],另外元组m是由元组t和p交换某些属性上的值而产生的,而t和p在属性X上值相等,显然m[X]=t[X],所以m[U-(Z-Y)]=t[U-(Z-Y)],即m[R3]=t[R3]。 对元组s、q,同理可知s[Y]=q[Y],存在元组n,使n[Z-Y]=t[Z-Y],即n[R3]=s[R3]。 综上所述,对t、s∈r,t[X]=s[X],存在元组m、n∈r,使m[X]=n[X]=t[X],而m[Z-Y]=s[Z-Y],m[R3]=t[R3],n[Z-Y]=t[Z-Y],n[R3]=s[R3]。 A8:若X→→Y,W→Z,W∩Y=Φ,ZY,则X→Z。 设r是R上的任一关系,对任意s、t∈r,若t[X]=s[X],设R1=U-X-Y,则根据X→→Y知:存在元组p、q∈r,使p[X]=q[X]=t[X],而p[Y]=t[Y],p[R1]=s[R1],q[Y]=s[Y],q[R1]=t[R1]。因为W∩Y=Φ,所以s[W]=p[W],又W→Z,所以s[Z]=p[Z];因为ZY,且p[Y]=t[Y],所以p[Z]=t[Z];所以可得t[Z]=s[Z],即X→Z。
8.设关系模式为R(U,F),X,Y为属性集,X,YU。证明: (1)XXF+ (2)(XF+)F+=XF+ (3)若XY则XF+YF+ (4)UF+=U
正确答案: (1)因为X→X 所以XXF+ (根据XF+的定义) (2) *解析 1 要证明(XF+)F+=XF+ 只要证明 XF+ (XF+)F+ 并且(XF+)F+ XF+ 而XF+ (XF+)F+ 是显然的,因此只要证明(XF+)F+ XF+ 2 这里的证明要用集合论的基本知识,同学们应该复习一下有关集合论中的有关概念和证明方法。 证明:下面求证(XF+)F+XF+ 任意A∈(XF+)F+,(由题意知)存在B∈XF+,使B→A能由F根据Armstrong公理导出,而从B∈XF+ 可知X→B能由F根据Armstrong公理导出,根据公理中的传递律可知X→A能由F根据Armstrong公理导出,所以A∈XF+,因此(XF+)F+ XF+。 所以(XF+)F+=XF+。 (3)对任意A∈XF+ ,可知X→A能由F根据Armstrong公理导出,因为XY,由自反律可以得Y→X,由传递律得Y→A,所以A∈YF+ 。 XF+YF+ 得证。 (4) *解析 要证明UF+=U 只要证明 U UF+ 并且 UF+ U U UF+ 是显然的; 下面证明UF+ U,即证U由F据Armstrong公理推出的集合仍属于U: 自反律:Y U,U→Y为F所蕴含。显然U由F据Armstrong公理的自反律推出的Y仍属于U; 增广律:U→Y为F所蕴含,且ZU,则U Z→YZ为F所蕴含,YZU。 传递律:U→Y 和Y→Z都为F所蕴含,则U→Z为F所蕴含。ZU。
9.设关系模式为R(U,F),若XF+=X,则称X相对于F是饱和的。 定义饱和集F={X | X=XF+}, 试证明F = {XF+ | XU }。
正确答案: 证:1)证 F {XF+|XU} 对任意A∈F ,由已知条件得A=AF+ ,因为AU,A=AF+ 所以A∈{XF+|XU}。 2)证 {XF+| XU} F 对任意A∈{AF+|AU},因为(AF+)F+ = AF+(见习题7),令B=AF+,有BF+ =B 所以 B∈F 即AF+∈F ,A∈F 得证。
10. 在一个关系R中,若每个数据项都是不可再分割的,那么R一定属于__________ 。
正确答案: 第一范式(1NF)
11. 若关系为1NF,且它的每一非主属性都__________ 候选码,则该关系为2NF。
正确答案: 完全函数依赖于
12. 如果X→Y和X→Z成立,那么X→YZ也成立,这个推理规则称为___________ 。
正确答案: 合并规则
13. 如果关系模式R是第二范式,且每个非主属性都不传递依赖于R的候选码,则称R为________ 关系模式。
正确答案: 3NF
14. 在函数依赖中,平凡函数依赖是可以根据Armstrong推理规则中的__________ 律推出的。
正确答案: 自反
15. 关系模式规范化需要考虑数据间的依赖关系,人们已经提出了多种类型的数据依赖,其中最重要的是_____________和___________。
正确答案: 函数依赖 多值依赖
16. 设关系R(U),X,Y∈U,X→Y是R的一个函数依赖,如果存在X′∈X,使X′→Y成立,则称函数依赖X→Y是___________ 函数依赖。
正确答案: 部分
17. 在关系模式R(A,B,C,D)中,存在函数依赖关系{A→B,A→C,A→D,(B,C)→A},则候选码是___________,关系模式R(A,B,C,D)属于____________ 。
正确答案: A,(B,C) 2NF