数据库系统概论第4章补充练习答案

•补充习题•1.设关系模式R=(U,F),U=ABCDEG,F={AB→D,DB→EG,AC→E,BE→A,A→B}，求所有候选码。(AC,BCE,BCD)•2.设关系模式R=(U,F),U=ABCDEG,求下列函数依赖集F等价的最小函数依赖集Fmin.•（1）F={AB→CD,A→BE,D→E,B→D}1.F1={AB-C,AB-D,A-B,A-E,D-E,B-D}2.F2={AB-C,A-B,D-E,B-D}3.Fmin={A-C,A-B,D-E,B-D}•（2）F={ABC→D,AC→E,E→AB,B→D,CD→B}1.F1={ABC→D,AC→E,E→A,E→B,B→D,CD→B}2.F2={AC→E,E→A,E→B,B→D,CD→B}3.Fmin={AC→E,E→A,E→B,B→D,CD→B}•（3）F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}1.F1={AB→C,D→E,D-G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}2.F2={AB→C,D→E,D-G,C→A,BE→C,BC→D,CG-D,ACD→B,CE→G}或者F2={AB→C,D→E,D-G,C→A,BE→C,BC→D,CG-B,CE→G}3.{AB→C,D→E,D-G,C→A,BE→C,BC→D,CG-D,CD→B,CE→G}或者{AB→C,D→E,D-G,C→A,BE→C,BC→D,CG-B,CD→B,CE→G}•3.判断并证明下列关系模式最高属于哪一级范式•（1）R1：U=ABCD,F={AB→C,C→D}(AB,2)•（2）R2：U=ABCD,F={AB→C,D→A,D→B}(D,2)•（3）R3：U=ABCD,F={A→B,B→C,CD→A}(BD,CD,AD,3)•（4）R4：U=ABCD,F={A→B,B→C}(AD,1)•（5）R2：U=ABCDE,F={AB→C,BC→D,AB→E,ABCD→DE,BED→BE}(AB,2)•4.把下列关系模式分解为无损连接和保持函数依赖的3NF：•（1）U=ABCD,F={AB→CD,D→C,CD→B}1.Fmin={AB-D,D-C,D-B}，码AD,AB2.分组U1=ABD,根据算法后面合并成U2=BCD3.吸收，得U1,U24.ADB中包含了码F1={ABD,AB-D,D-B}F2={BCD,D-B,D-C}•（2）U=ABCDEG,F={B→CD,DE→A,E→C,C→A,BD→AC}1.Fmin={B-C,B→D,E→C,C→A}2.分组U1=BCD，U2=ECU3=CA，U0=G3.吸收，得U2,U3,U44.检查码F2={EC,E-C}F3={CA,C-A}F4={BCD,B-D,B-D},F4=(BEG.ф)•5.把下列关系模式分解为无损连接的BCNF：U=ABCD,F={A→C,B→AC,D→AC,BD→A}1.Fmin={A→C,B→A,D→A}2.码BD，A-C不符合R1={AC,A-C}R2=(ABD,B-A,D-A)B-A不符合R3={AB,B-A}R4={BD,ф}得到R1，R3,R4•算法4b.3（求最小函数依赖集的算法）•1)求最简式：对F中所有右边为多属性形如X→A1A2…An的函数依赖用X→Ai，i=1,2,…,n来代替，得到函数依赖集F1，F1全由最简式组成。•2）消除冗余函数依赖：对所有(X→A)∈F1逐个做①令G=F1-(X→A)；②对G求X+；③若A∈X+，则从F1中去掉X→A，否则不去掉；最终得到没有冗余函数依赖的函数依赖集F2。•3左边最简化：对F2中所有左边为多属性的形如X(=A1A2…An)→A的函数依赖，①i=1；②若in则结束本函数依赖的处理，转入对F2中下一个这样的函数依赖的处理；否则X-=X-Ai；③若X-为空，则结束本函数依赖的处理，转入对F2中下一个这样的函数依赖的处理；否则，对F2求X-+；④若A∈X-+，则F2=F2-(X→A)∪(X-→A),X=X-，i=i+1，转②；否则，i=i+1，转②。•所有这样的函数依赖处理完成后，F2的函数依赖左边都最简化。•最终得到的F2是一个最小函数依赖集Fmin。•例4b.4设F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}，求其Fmin。•解：•（1）求最简式•F1＝{AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}•（2）除冗余函数依赖•G=F1-(AB→C),对G的(AB)+={AB},C!∈(AB)+,所以AB→C不能去掉；•同理D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G都不能去掉；•G=F1-(CG→B),对G的(CG)+={CGDAB},B∈(CG)+,所以CG→B要去掉；同理，CE→A可去掉；•所以，F2＝{AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G}•（3）左边最简•F1＝{AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,•CG→D,ACD→B,CE→A,CE→G}•D→E,D→G,C→A左边是单属性，不能化简。•对AB→C化简•对F2，(B)+={B},C!∈(B)+,所以A不能去掉；同理，B不能去掉；所以，AB→C不能化简。•同理，BE→C,BC→D,CG→D,CE→G都不能化简。•对ACD→B化简•对F2，(CD)+={CDEGAB},B∈(CD)+,所以A可以去掉;•F2＝{AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G}•对F2，(D)+={DEG},B!∈(D)+,所以C不能去掉；同理，D不能去掉。•所以，ACD→B化简为CD→B。•F1＝{AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,•CG→D,ACD→B,CE→A,CE→G}•因此，•Fmin＝{AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}•注意：由F求Fmin，结果不是唯一的，不同的化简次序可能得到不同的结果。如设F＝{A→B,B→C,A→C,B→A};先去掉B→C,Fmin＝{A→B,A→C,B→A}；先去掉A→C,Fmin＝{A→B,B→C,B→A}。•1．函数依赖集在属性子集上的投影•定义4b.9设R(U,F)是一个关系模式。Ui是U的一个属性子集，Fi={X→Y|(X→Y)∈F+∧X是Ui的子集∧Y是Ui的子集}称为F在Ui上的投影，记作F(Ui)。•例4b.5设R(U,F)是一个关系模式，U=ABCD,F={A→B,C→B,BC→A,B→D}，U1=AD,U2=CBD,求F(U1)，F(U2)。•解：•(1){A}+={ABD},所以A→D∈F+,所以A→D∈F(U1)；{D}+={D},所以D→A!∈F+，所以D→A!∈F(U1)；因此F(U1)={A→D}。•(2)C→B∈F,B→D∈F,C→D被{C→B,B→D}所藴含，CBD能形成的其他非平凡又不被{C→B,B→D}所藴含的函数依赖都不属于F+，所以F(U2)={C→B,B→D}。•5．得到无损连接和函数依赖保持的3NF分解算法•算法4b.3•（1）求F的最小函数依赖集Fmin•（2）分组：对Fmin中的函数依赖中左边相同的各分为一组，设有以X1,X2,…,Xm等为相同左边的m个组，每组中的属性组成的属性子集为U1,U2,…,Um，把不在F中的属性单独组成一个属性子集U0。•（3）吸收：从U0,U1,U2,…,Um中去掉被其他属性子集所包含属性子集，得到U0,U1,U2,…,Uk，k=m。•（4）分解：组成分解ρ={Ri(Ui,Fi)|Fi是F在Ui的投影，i=0,1,2,…,k}，是保持函数依赖的得到3NF的分解。•（5）形成无损连接：若ρ中各子模式的属性子集中都无R的码，则取R的一个码X，把Rx(X,Fx)加进ρ中，ρ就是无损连接的3NF的分解；否则，ρ已是无损连接的3NF的分解。•定理4b.5：算法4b.3是可以终止的，且所得到的分解是全由3NF组成，也是无损连接和函数依赖保持的。•这里不作证明。•例4b.9•设U=ABCDE,F={AB→C,A→B,D→BC,C→B},求R(U,F)的保持函数依赖且无损连接的3NF分解。•解：（1）求Fmin•右边最简：F1={AB→C,A→B,D→B,D→C,C→B}•左边最简：A+(F1)=ABC,所以AB→C中B可去掉，F2={A→C,A→B,D→B,D→C,C→B}•去掉冗余函数依赖：{A→C,C→B}=A→B,所以A→B可去掉；{D→C,C→B}=D→B,所以D→B可去掉；得Fmin={A→C,D→C,C→B}。•（2）分组：U1＝AC,U2＝DC,U3＝CB,U0=E。•（3）吸收：U1,U2,U3互不包含，无需吸收。•得到R的一个保持函数依赖的3NF分解•ρ={R0(E,ф),R1(AC,A→C),R2(DC,D→C),R3(CB,C→B)}•（4）检查码：ADE不在Fmin右边出现，(ADE)+=ADECB=U,所以ADE是R的唯一的码，不在U1＝AC,U2＝DC,U3＝CB,U0=E的任何一个中，所以增加R4(ADE,ф),但U4=ADE要吸收U0=E,所以ρ={R1(AC,A→C),R2(DC,D→C),R3(CB,C→B),R4(ADE,ф)}是保持函数依赖且无损连接的3NF分解。•6．得到无损连接的BCNF的分解算法•算法4b.4•（1）求F的最小函数依赖集Fmin，令ρ={R(U,Fmin)}•（2）二项分解•①若ρ中所有子模式都属于BCNF，则算法结束；否则，进行②•②若ρ中存在R不是BCNF,则在R的F中存在函数依赖X→A,且X不是码，那就作二项分解：U1=X∪A,R1(U1,F(U1))；U2＝U-A，R2(U2,F(U2))•③ρ=ρ∪R1∪R2-R,转到①•定理4b.5：算法4b.4是可以终止的，且所得到的分解是全由BCNF组成，也是无损连接的。•这里不作证明。•例4b.10设U=ABCDE,F={A→B,B→C,CD→B},求R(U,F)的无损连接的BCNF分解。•解：•（1）F已是最小函数依赖集Fmin。•（2）ADE不在右边出现，(ADE)+=ADEBC=U，所以ADE是R的唯一的码，A→B不合BCNF要求，分解R：R1(AB,A→B),R2(ACDE,A→C))。•（3）R1是BCNF，但R2中A→C不合BCNF要求，分解R2：R3(AC,A→C),R4(ADE,ф))，R3、R4都是BCNF。•得到R的无损连接的BCNF分解ρ={R1(AB,A→B),R3(AC,A→C),R4(ADE,ф)}