第6章 关系数据库的设计理论
习题参考答案
6.2 函数依赖
Driver-id ? Name，Driver-id ? Address，Driver-id ? Phone-no Car-no ? Model，Car-no ? Year Report-no ? Date，Report-no ? Location，Report-no ? Damage
6.3 函数依赖
Cno ? Balance，Cno ? CreditLimit Ono ? Date，Ono ? Address
Ono,Ino ? QTY
Ino ? Description（假设同一种货物可以由不同制造商制造，但具有相同描述） Ino,Plant ? QTYOH
6.4
(1) S→D表示股票红利由股票唯一确定 I→B表示每个投资人至多有一个经纪人 IS→Q表示投资人和股票唯一确定他/她对该股票的拥有量
B→O表示每个经纪人都有唯一的办公室 (2) R(B, O, I, S, Q, D)的一个码为IS
6.5 初始：Result ? BD
Result ? BDEG（使用D?EG） Result ? BCDEG（使用BE?C） 使用CG?BD不改变Result
Result ? ABCDEG（使用CE?AG）
Result已包含所有属性，不可能再增大。因此 (BD)+= ABCDEG
6.6 初始：Result=AC
Result ? ABC（使用A→B）
Result ? ABCDE（使用BC→DE）
再无可用的函数依赖。因此(AC)+= ABCDE。
F不逻辑蕴涵函数依赖ACF→DG，因为DG不在AC的闭包中。
6.7 F1和F2等价。这是因为
显然A→B在F2+中。而AB关于F2的闭包为ABC，因此AB→C在F2+中。而D关于F2的闭包为ABCDE，因此D→AC和D→E都在F2+中。这就证明了F1?F2+。
反过来，A关于F1的闭包为ABC，因此A→BC在F1中。D关于F1的闭包为ABCDE，因此D→AE在F1中。这表明F2?F1+。
综上，F2+?F1+。
6.8 事实上，F还有3个极小依赖集。对F右端极小化，得到：
A?B, A?C, B?A, B?C, C?A, C?B
依次删除A?C和C?A得到F的一个极小覆盖Fm2={A?B, B?A, B?C, C?B} 依次删除B?C和C?B得到F的一个极小覆盖Fm3={A?B, A?C, B?A, C?A} 依次删除A?B和B?A得到F的一个极小覆盖Fm4={A?C, B?C, C?A, C?B}
6.9 F不是极小函数依赖集。
显然，F右部是极小的。
考虑ABD?E：(AB)+=ABGH，不包含E；(AD)+=AD，不包含E；(BD)+=BDK，不包含E；因此，ABD?E的左部是极小的。
考虑AB?G：A+=A，不包含G；B+=BK，不包含G；因此，AB?G的左部是极小的。 考虑CJ?I：C+=CIJ，包含I；因此CJ?I的左部不是极小的。可以删除J，得到C?I。 现在，我们有F的等价函数依赖集F’={ABD?E, AB?G, B?K, C?J, C?I, G?H}。容易验证它是极小的。
关系模式R的码是ABCD。
6.10 初始化表在（a）中。
A?C将b23和b53改变为b13，B?C将b33改变为b13，结果表在（b）中。
A
B
C
D
E
A
B
C
D
E
a1 b12 b13 a4 b15 a1 b12 b13 a4 b15 a1 a2 b23 b24 b25 a1 a2 b13 b24 b25 b31 a2 b33 b34 a5 b31 a2 b13 b34 a5 b41 b42 a3 a4 a5 b41 b42 a3 a4 a5 a1 b52 b53 b54 a5 a1 b52 b13 b54 a5 (a) (b)
C?D将b24、b34和b54改变为a4，DE?C将b13改变为a3，结果表在（c）中。
CE?A将b31和b41改变为a1，结果表在（d）中。此时，表的第三行为 a1a2a3a4a5，因此?是无损连接分解。
A a1 a1 b31 b41 a1
B b12 a2 a2 b42 b52
C a3 a3 a3 a3 a3 (c)
D a4 a4 a4 a4 a4
E b15 b25 a5 a5 a5
A a1 a1 a1 a1 a1
B b12 a2 a2 b42 b52
C a3 a3 a3 a3 a3 (d)
D a4 a4 a4 a4 a4
E b15 b25 a5 a5 a5
6.11 因为R1? R2=S，R1? R2=A，而S?A?F，所以?={R1(S, A), R2(S, I, P)}是无损连接分解。
6.12 使用完全函数依赖概念，2NF的等价定义如下：
如果关系模式R∈1NF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。
6.13 证明：我们用反证法证明。
设R满足6.5.2节的3NF定义。假设R不满足习题中的3NF定义，则存在非主属性A，它传递地依赖于R的某个码，设为K。于是，存在Y使得Y→K在R中不成立，但是A既不属于K也不属于Y，并且Y→A。由于Y→K在R中不成立，Y不是R的超码。又因为A不
是主属性，因此Y→A违反6.5.2节的3NF定义，这与R满足6.5.2节的3NF定义相矛盾。这一矛盾表明“R不满足习题中的3NF定义”的假设不成立。
设R满足习题中的3NF定义。假设R不满足6.5.2节中的3NF定义，则存在属性A，属性集Y使得Y→A，但是A不是主属性，而Y不是R的超码。设K为R的超码，则K→Y，但Y→K在R中不成立。于是非主属性A传递地依赖于R的码K，与R满足习题中的3NF定义相矛盾。这一矛盾表明“R不满足6.5.2节中的3NF定义”的假设不成立。
综上，习题中的3NF定义与6.5.2节的3NF定义等价。
6.14 证明：
(1) 如果R的所有属性都是主属性，则R中的任何函数依赖都不违反3NF条件，因此R是3NF。
(2) （反证法）设R的码包含R的的所有属性（全码），但R不是BCNF。于是，R中存在X→A（即X?A?F+），并且A?X，但是X不是R的超码。令Y=R?{A}。由于A?X，于是X?Y。由此，Y→X。注意到X→A，于是Y→A。又因为Y=R?{A}，于是Y→R。这与R的码包含所有属性矛盾。这一矛盾表明“R不是BCNF”的假设不成立。
6.15 证明：
(1) 证明：如果关系模式R是3NF，则R一定是2NF。举例说明其逆不真。
设R是3NF。假设R不是2NF。于是，R中存在X→A，并且A?X，但是A不是主属性，而X是R的某个码（设为K）的真子集。因为X是K的真子集，因此X不可能是R的超码（否则与K是R的码矛盾）。X→A违反3NF定义，于是R不是3NF，与设R是3NF矛盾。这一矛盾表明“R不是2NF”的假设不成立。
例如，考虑关系模式SDL(Sno, Sdept, Sloc)，其中Sn0、Sdept和Sloc分别为学生的学号、所在系和住处。假设每个系的学生住在同一座楼，我们有函数依赖：
Sno→Sdept，Sdept→Sloc
SDL的码为Sno。容易验证SDL是2NF，但不是3NF。
(2) 如果关系模式R是BCNF，则R一定是3NF。举例说明其逆不真。
设R是BCNF。假设R不是3NF。于是，R中存在X→A，并且A?X，但是A不是主属性，并且X不是R的超码。这显然与R是BCNF矛盾。这一矛盾表明“R不是3NF”的假设不成立。
例如，考虑关系模式STC(S, T, C)，其中S、T和C分别表示学生、教师和课程。这里，非平凡的函数依赖为SC→T和ST→C。STC有两个码(S,C)和(S,T)。STC∈3NF，但STC不是BCNF。
(3) 如果关系模式R是4NF，则R一定是BCNF。举例说明其逆不真。
设R是4NF。假设R不是BCNF。于是，R中存在X→A，并且A?X，但是X不是R的超码。如果XA=R，则X是超码。因此，XA不包含所有属性。根据A8，X→A意味X→→A。由于XA?R，并且A?X，X→→A违反4NF条件，与R是4NF矛盾。
例如，考虑关系模式CTB(C,T,B)，其中C表示课程，T表示教师，B表示参考书。一门课程可以由多位教师讲述，但他们必须使用通一组参考书。CTB中存在如下多值依赖：
C→→T, C→→B
CTB为全码，因此是BCNF（习题16.14）。但C→→T违反4NF条件，因此CTB不是4NF。
6.16 该关系模式的码是HS（例6.14），所以不是BCNF。C?T违反BCNF条件，使用它将CTHRSG分解为{CT, CHRSG}。
CHRSG的码仍然是HS，不是BCNF。CS?G违反BCNF条件，使用它将CHRSG分解为{CSG, CHRS}。
CHRS的码仍然是HS，不是BCNF。HR?C违反BCNF条件，使用它将CHRS分解为{HRC, HRS}。
现在，所有的模式都是BCNF。我们得到的具有无损连接性的BCNF分解{CT, CSG, HRC, HRS}
6.17 R (B, O, I, S, Q, D)的函数依赖为 S→D，I→B，IS→Q，B→O，码为IS。
(1) S→D违反BCNF条件，使用它将R分解为{SD, BOISQ}。
BOISQ的码为IS。B→O违反BCNF条件，使用它将BOISQ分解为{BO, BISQ}。 BISQ的码为IS。I→B违反BCNF条件，使用它将BISQ分解为{IB, ISQ}。 最后得到R的一个具有无损连接性的BCNF分解{SD, BO, IB, ISQ}
(2) R的函数依赖已经是正则的，R的一个具有无损连接性和保持函数依赖的3NF分解为{ SD, IB, ISQ, BO}
6.18 容易明白，R的码为VD和SD。
(1) S?T违反BCNF条件，使用它将R分解为{ST, SVCPD}. SVCPD的码为VD和SD。V?SC违反BCNF条件，使用它将SVCPD分解为{VSC, VPD}。最后得到R的一个具有无损连接性的BCNF分解{ST, VSC, VPD}
(2) R的函数依赖已经是正则的，R的一个具有无损连接性和保持函数依赖的3NF分解为{ST, VSC, SDPV}
(3) 解释R为什么不存在具有无损连接性和保持函数依赖的BCNF分解. S?T，V?SC和SD?PV
6.19 例子很多，但需要注意的是：多值依赖的成立依赖于属性集，举例时需要说明属性集。
6.20 (1)用定义和公理两种方法证明，其余用公理证明。
(1) 多值依赖的合并规则：如果X→→Y，X→→Z成立，则X→→YZ成立。 证明：方法一：使用公理证明：
对X→→Y用X增广得到X→→XY。对X→→Z用Y增广得到XY→→YZ。使用自反律，得到XY→→(U?XY?YZ)。而U?XY?YZ=U?X?Y?Z，于是XY→→(U?X?Y?Z)。由X→→XY和XY→→(U?X?Y?Z)，使用多值依赖的传递律得到X→→((U?X?Y?Z) ?XY)。而(U?X?Y?Z)?XY =U?X?Y?Z。因此，我们有X→→(U?X?Y?Z)。再次利用自反律，得到X→→(U?X? (U?X?Y?Z))。由于U?X? (U?X?Y?Z)= YZ，于是我们有X→→YZ。
方法二：使用定义证明：设U为属性全集。
设r是属性集U上的任意关系，满足X→→Y和X→→Z。设t1和t2是r的任意元组，满足t1[X]= t2[X]。为证明X→→YZ成立，我们只要证明存在t3,t4?r，使得 (1) t3[X]=t4[X]= t1[X]= t2[X]，(2) t3[YZ]= t1[YZ]，并且t3[U?XYZ]= t2[U?XYZ]，(3) t4[YZ]= t2[YZ]，并且t4[U?XYZ]= t1[U?XYZ]。
由于t1,t2?r，X→→Y，存在u1,u2?r，使得 (1) u1[X]= u2[X]= t1[X]= t2[X]，(2) u1[Y]= t1[Y]，并且u1[U?XY]= t2[U?XY]，(3) u2[Y]= t2[Y]，并且u2[U?XY]= t1[U?XY]。
t1,u1?r，X→→Z，存在u3,u4?r，使得 (1) u3[X]= u4[X]= t1[X]= u1[X]，(2) u3[Z]= t1[Z]，并且u3[U?XZ]= u1[U?XZ]，(3) u4[Z]= u1[Z]，并且u4[U?XZ]= t1[U?XZ]。
t2,u2?r，X→→Z，存在u5,u6?r，使得 (1) u5[X]= u6[X]= t2[X]= u2[X]，(2) u5[Z]= t2[Z]，并
且u5[U?XZ]= u2[U?XZ]，(3) u6[Z]= u2[Z]，并且u6[U?XZ]= t2[U?XZ]。
这些元组如下所示： X Y Z U?X?Y t1 a1 … ai ai+1 … aj aj+1 … ak ak+1 … an t2 a1 … ai bi+1 … bj bi+1 … bk bk+1 … bn u1 a1 … ai ai+1 … aj bj+1 … bk bj+1 … bn u2 a1 … ai bi+1 … bj ai+1 … ak aj+1 … an u3 a1 … ai ai+1 … aj aj+1 … ak bj+1 … bn u4 a1 … ai ai+1 … aj bj+1 … bk aj+1 … an u5 a1 … ai bi+1 … bj bj+1 … bk aj+1 … an u6 a1 … ai bi+1 … bj ai+1 … ak bj+1 … bn 令t3= u3，t4=u5，于是t3,t4?r，并且(1) t3[X]=t4[X]= t1[X]= t2[X]，(2) t3[YZ]= t1[YZ]，并且t3[U?XYZ]= t2[U?XYZ]，(3) t4[YZ]= t2[YZ]，并且t4[U?XYZ]= t1[U?XYZ]。
(2) 多值依赖的伪传递规则：如果X→→Y，WY→→Z成立，则WX→→(Z?WY) 成立。 证明：用W增广X→→Y，得到WX→→WY。注意到WY→→Z成立，使用多值依赖的传递率，我们有WX→→(Z?WY)。
(3) 混合伪传递规则：如果X→→Y，XY→Z成立，则X→(Z?Y) 成立。 证明：：用X增广X→→Y，得到X→→XY。由XY→Z和A7得到XY→→Z。由X→→XY和XY→→Z，利用多值依赖的传递率得到X→→(Z?XY)。由于X→→(Z?XY)，(Z?XY)?(Z?XY)，XY与(Z?XY)不相交，并且XY→Z，A8表明X→(Z?Y) 成立。
(4) 多值依赖的分解规则：如果X→→Y，X→→Z成立，则X→→(Y?Z)，X→→(Y?Z)，X→→(Z?Y) 成立。
证明：由(Y?Z)?Y得到Y→(Y?Z)。再利用A7，得到Y→→(Y?Z)。由X→→Y和Y→→(Y?Z)，利用多值依赖的传递率得到X→→((Y?Z) ?Z)。此即X→→(Y?Z)。
类似地，可以证明X→→(Z?Y)。 由X→→Y和Y→→(Y?Z（上面已证）)，利用多值依赖的传递率，我们有X→→(Y? (Y?Z))。而Y? (Y?Z)= Y?Z，因而有X→→(Y?Z)。
6.21 只考虑函数依赖，?={CHR, CT, CSG}不是无损连接分解。这可以用算法6.3检测。初始表如（a）所示。
C T H R S G C T H R S G
a1 a1 a1
b12 a3 a4 b15 a2 b23 b24 b25 b32 b33 b34 a5 (a)
b16
b26 a6
a1 a1 a1
a2 a2 a2
a3 b23 b33 (b)
a4 b24 b34
b15 b16 b25 b26 a5 a6
C?T将b12和b32改为a2，结果如（b）所示。任何函数依赖都不能再改变该表，算法结束。由于不存在一行为a1a2a3a4a5a6，因此?={CHR, CT, CSG}不是无损连接分解。
6.22 通过模式分解产生关系模式（仅考虑函数依赖）的三个目标是：无损连接分解、BCNF和保持函数依赖的分解。
分解的无损连接性是对分解的基本要求，是必须保证的。不具有无损连接性的分解是有害的。这是因为关系模式R的分解?={R1, R2,…, Rk}将原关系模式下的关系r分解成k个关系r1, r2,…, rk。除了自然连接之外，没有其他一般性方法从这些关系得到原来的关系。因此，对r和r1, r2,…, rk进行相同的查询可能得到不同的结果。这样，我们就不能认为R和{R1, R2,…, Rk}反映相同的现实世界。