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

1、补充习题 1. 设关系模式R=(U,F),U=ABCDEG,F=ABD,DBEG,ACE,BEA, AB ，求所有候选码。(AC,BCE,BCD) 2. 设关系模式R=(U,F),U=ABCDEG,求下列函数依赖集F等价的最小函数依赖集Fmin. （1）F=ABCD,ABE,DE,BD 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=ABCD, ACE, EAB,BD,CDB 1.F1=ABCD, ACE, EA, EB,BD,CDB 2.F2=ACE, EA, EB,BD,CD

2、B 3.Fmin=ACE, EA, EB,BD,CDB,（3）F=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG 1.F1=ABC,DE,D-G,CA,BEC,BCD, CGB, CGD,ACDB,CEA, CEG 2.F2=ABC,DE,D-G,CA,BEC, BCD,CG-D,ACDB, CEG 或者F2=ABC,DE,D-G,CA,BEC, BCD,CG-B,CEG 3. ABC,DE,D-G,CA,BEC,BCD, CG-D,CDB, CEG或者 ABC,DE,D-G,CA,BEC,BCD, CG-B,CDB, CEG,3.判断并证明下列关系模式最高属于哪一级范式

3、（1）R1：U=ABCD, F=ABC,CD ( AB,2 ) （2）R2：U=ABCD, F=ABC,DA, DB (D,2) （3）R3：U=ABCD, F=AB,BC, CDA (BD,CD,AD,3) （4）R4：U=ABCD, F= AB,BC (AD,1) （5）R2：U=ABCDE, F=ABC, BCD, ABE, ABCDDE, BEDBE(AB,2),4. 把下列关系模式分解为无损连接和保持函数依赖的3NF： （1）U=ABCD, F=ABCD,DC, CDB 1.Fmin=AB-D,D-C,D-B，码AD,AB 2.分组U1=ABD, 根据算法 后面合并成 U2=BCD

4、3.吸收，得U1,U2 4. ADB中包含了码 F1=ABD,AB-D,D-BF2=BCD,D-B,D-C,（2）U=ABCDEG, F= BCD,DEA, EC, CA, BDAC 1. Fmin=B-C,BD, EC, CA 2.分组U1=BCD，U2=EC U3=CA，U0=G 3.吸收，得U2,U3,U4 4.检查码 F2=EC,E-CF3=CA,C-AF4=BCD,B-D,B-D, F4=(BEG. ),5. 把下列关系模式分解为无损连接的BCNF： U=ABCD, F=AC,BAC, DAC, BDA 1.Fmin=AC,BA, DA 2.码 BD，A-C不符合 R1=AC,A-C

5、 R2=(ABD,B-A,D-A) B-A不符合 R3=AB,B-A R4=BD, 得到R1，R3,R4,算法4b.3（求最小函数依赖集的算法） 1)求最简式：对F中所有右边为多属性形如X A1A2An的函数依赖用XAi，i=1,2, ,n来代替，得到函数依赖集F1，F1全由最简式组成。 2）消除冗余函数依赖：对所有(XA)F1逐个做令G= F1-(XA)；对G求X+；若AX+，则从F1中去掉XA，否则不去掉；最终得到没有冗余函数依赖的函数依赖集F2。 3左边最简化：对F2中所有左边为多属性的形如X(= A1A2An)A的函数依赖，i=1； 若in则结束本函数依赖的处理，转入对F2中下一个这样

6、的函数依赖的处理；否则X-=X-Ai；若X-为空，则结束本函数依赖的处理，转入对F2中下一个这样的函数依赖的处理；否则，对F2求X-+；若AX-+，则F2= F2-(XA)(X-A),X=X-，i=i+1，转；否则，i=i+1，转。 所有这样的函数依赖处理完成后，F2的函数依赖左边都最简化。 最终得到的F2是一个最小函数依赖集Fmin 。,例4b.4 设F= ABC,DEG, CA,BEC,BCD, CGBD,ACDB,CEAG，求其Fmin。 解： （1）求最简式 F1ABC,DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG （2）除冗余函数依赖 G=F1-(ABC

7、),对G的(AB)+=AB,C!(AB)+,所以ABC不能去掉； 同理 DE,DG,CA,BEC,BCD, CGD,ACDB, CEG都不能去掉； G=F1-(CGB),对G的(CG)+=CGDAB,B(CG)+,所以CGB 要去掉；同理，CEA 可去掉； 所以，F2ABC,DE,DG,CA,BEC,BCD, CGD,ACDB, CEG,（3）左边最简 F1ABC,DE,DG,CA,BEC,BCD,CGB, CGD,ACDB,CEA,CEG DE,DG,CA 左边是单属性，不能化简。 对ABC化简 对F2，(B)+=B,C!(B)+,所以A不能去掉；同理，B不能去掉；所以，ABC不能化简。 同

8、理，BEC,BCD, CGD, CEG 都不能化简。 对ACDB化简 对F2，(CD)+=CDEGAB,B(CD)+,所以A可以去掉; F2ABC,DE,DG,CA,BEC,BCD, CGD,ACDB, CEG 对F2，(D)+=DEG,B!(D)+,所以C不能去掉；同理，D不能去掉。 所以，ACDB化简为CDB。,F1ABC,DE,DG,CA,BEC,BCD,CGB, CGD,ACDB,CEA,CEG 因此， FminABC,DE,DG,CA,BEC,BCD, CGD, CDB, CEG 注意：由F求Fmin ，结果不是唯一的，不同的化简次序可能得到不同的结果。如设FAB,BC,AC, BA

9、; 先去掉BC, Fmin AB, AC,BA；先去掉AC, Fmin AB,BC, BA。,1函数依赖集在属性子集上的投影 定义4b.9 设R(U,F)是一个关系模式。Ui是U的一个属性子集，Fi=XY|(XY)F+X是Ui的子集Y是Ui的子集 称为F在Ui上的投影，记作F(Ui)。 例4b.5设R(U,F)是一个关系模式，U=ABCD, F= AB,CB,BCA, BD，U1=AD, U2=CBD,求F(U1)，F(U2)。 解： (1)A + =ABD,所以ADF+,所以ADF(U1)；D+=D,所以DA!F+，所以DA!F(U1)；因此F(U1)= AD。 (2) CBF, BDF,

10、CD被CB,BD所藴含，CBD能形成的其他非平凡又不被CB,BD所藴含的函数依赖都不属于F+，所以F(U2)=CB,BD。,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 AB,所以AB可去掉；DC,CB=DB,所以DB可去掉；得Fmin=AC, D

11、C,CB。,（2）分组：U1AC, U2DC,U3CB, U0=E 。 （3）吸收：U1,U2,U3互不包含，无需吸收。 得到R的一个保持函数依赖的3NF分解 =R0(E,), R1(AC, AC),R2(DC,DC),R3(CB,CB) （4）检查码：ADE不在Fmin右边出现，(ADE)+=ADECB=U,所以ADE是R的唯一的码，不在U1AC, U2DC,U3CB, U0=E的任何一个中，所以增加R4(ADE,),但U4=ADE要吸收U0=E,所以=R1(AC, AC),R2(DC,DC),R3(CB,CB), R4(ADE,)是保持函数依赖且无损连接的3NF分解。,6得到无损连接的BC

12、NF的分解算法 算法4b.4 （1）求F的最小函数依赖集Fmin，令=R(U, Fmin) （2）二项分解 若中所有子模式都属于BCNF，则算法结束；否则，进行 若中存在R不是BCNF,则在R的F中存在函数依赖XA,且X不是码，那就作二项分解：U1=X A, R1(U1,F(U1)；U2U-A， R2(U2, F(U2) =R1R2-R,转到 定理4b.5：算法4b.4是可以终止的，且所得到的分解是全由BCNF组成，也是无损连接的。 这里不作证明。,例4b.10 设U=ABCDE, F= AB,BC,CDB,求R(U,F)的无损连接的BCNF分解。 解： （1）F已是最小函数依赖集Fmin。 （2）ADE不在右