试证明A1(自反性):若Y?X?U,则X→Y在R上成立。 证:设t1和t2是关系R中的任意两个元组。 如t1【X】=t2【X】,因Y?X,则有t1【Y】=t2【Y】,故X→Y在R上成立。
试证明A2(增广性):若X→Y在R上成立,且Z?U,则XZ→YZ在R上成立。 证:设t1和t2是关系R中的任意两个元组。
如果t1【XZ】=t2【XZ】,则有如t1【X】=t2【X】,t1【Z】=t2【Z】。 已知X→Y,因此可得t1【Y】=t2【Y】,由上可知如t1【YZ】=t2【YZ】,故XZ→YZ
成立。
试证明A3(传递性):若X→Y和若Y→Z在R上成立,则X→Z在R上成立。 证:设t1和t2是关系R中的任意两个元组。 根据传递函数依赖条件可知:
如t1【X】=t2【X】,则t1【Y】=t2【Y】, 如t1【Y】=t2【Y】,则t1【Z】=t2【Z】,
由上可得:如t1【X】=t2【X】,则t1【Z】=t2【Z】,即X→Z在R上成立。
试证明A4(合并性):{X→Y,X→Z} |=X→YZ。
证:根据A2增广性, 在X→Y的函数依赖表达式左部和右部分别并上X,得 X→X Y。
在X→Z的函数依赖表达式左部和右部分别并上Y,得 XY→YZ。
根据A3传递性,由X→X Y和XY→YZ得X→YZ。
试证明A5(分解性){X→Y,Z?Y} |=X→Z。 证:根据A 1自反性, 因为Z?Y所以Y→Z成立。
已知X→Y又知,Y→Z,根据A3,得X→Z。
试证明A6(伪传递性){X→Y,WY→Z} |=WX→Z。
证:根据A2增广性, 在X→Y的函数依赖表达式左部和右部分别并上W,得WX→WY。
根据A3传递性,由WX→WY 和WY→Z得WX→Z。
试证明A7(复合性){X→Y,W→Z} |=WX→YZ。 证:根据A2增广性,
在X→Y的函数依赖表达式左部和右部分别并上W,的WX→WY。 在W→Z的函数依赖表达式左部和右部分别并上Y,的WY→ZY。 根据A3传递性,由WX→WY和WY→ZY得WX→YZ。
试证明A8(复合性){X→Y,W→Z} |= X ∪(W→Y)→YZ。 证:根据A2增广性, 在X→Y两边用(W-Y)扩充, 得到X ∪(W-Y)→Y∪(W-Y),
而Y∪(W-Y)=WY,因此有X ∪(W-Y)→WY。
从已知W→Z,根据A2两边用Y扩充,得到WY→YZ。
在根据A3,从X ∪(W-Y)→WY和WY→YZ可得到X ∪(W→Y)→YZ
3.6设关系模式R有n个属性,在模式R上可能成立的函数依赖有多少个?其中平凡的FD有多少个?非平凡的FD有多少个?
(要考虑所有可能的情况,数学排列组合问题。对于数据库本身而言,本题没多大意义) 解:这个问题是排列组合问题。FD形为X→Y,从n个属性值中选择属性组成X共有:
nCn?Cn?Cn???Cn?2种方法;同理,组成Y也有2种方法。因此组成X→Y012nn形成应该有2n?2n?4n种方法。即可能成立的FD有4n个。
平凡的FD要求Y?X,组合X→Y形式的选择有:
Cn?C0?Cn?(C1?C1)?Cn?(C2?C2?C2)???Cn(Cn?Cn???Cn) ?Cn?2?Cn?2?Cn?2??Cn?2?(1?2)?3
001122nnnn001012012n012即平凡的FD有3n。因而非平凡的FD有4n?3n个。
3.7已知关系模式R(ABC),F是R上成立的FD集,F={A→B,B→C},试写出F的闭包F+(有43个)。 A→Φ AB→Φ AC→Φ ABC→Φ B→Φ BC→Φ C→Φ A→A AB→A AC→A ABC→A B→B BC→B C→C A→B AB→B AC→B ABC→B B→C BC→C Φ→Φ
φ→φ A+=ABC A→有: B+=BC B→有: C=C C→有:
+++
A→C AB→C AC→C ABC→C B→BC BC→BC A→AB AB→AB AC→AB ABC→AB A→AC AB→AC AC→AC ABC→AC A→BC AB→BC AC→BC ABC→BC A→ABC AB→ABC AC→ABC ABC→ABC
+ + +
+ +
1
+
=23=8个
=22=4个
=2=2个
(AB)=ABC AB→有:8个 (AC)=ABC AC→有:8个 (BC)+=BC AB→有:4个 (ABC)=ABC ABC→有:8个 共43个。
+
3.8设关系模式R(ABCD),F是R上成立的FD集,F={A→B,C→B},则相对于F,试写出关系模式R的关键码。并说明理由。
解:R的关键码为ACD。因为从已知的F。只能推出ACD→ABCD。F={AB→C,CD→E,DE→B},判断AB是R的候选键吗?ABC呢?请做出解释。
3.9设关系模式R(ABCDE),F是R上成立的FD集,
3.10设关系模式R(ABCD)上FD集为F,并且F={AB→C,C→D,D→A} ① 试从F求出所有非平凡的FD。
② 试求R的所有候选键
③ 试求R的所有不是候选键的超键。
解:
① 从已知的F可求出非平凡的FD有76个。
譬如,左边是C的FD有6个:C→A,C→D,C→AD,C→AC,C→CD,C→ACD。 左边是D的FD有2个:D→A,D→AD。
左边是AB的FD有12个:AB→C, AB→D, AB→CD, AB→AC,??。 感兴趣的读者可以自行把这76个FD写齐。
② 候选键是能函数决定所有属性的不含多余属性的属性集。根据这个概念可求出R的候选键有三个:AB、BC和BD。
③ R的所有不是候选键的超键有四个:ABC、ABD、BCD和ABCD。
3.13设关系模式R(ABCD)上FD集为F,并且F={A→B,B→C}
① 试写出属性集BD的闭包(BD)+。
② 试写出所有左部是B的函数依赖(即形为“B→?”)
解:① 从已知的F,可推出BD→BCD,所有(BD)+=BCD。
② 由于B+=BC,因此左部是B的FD有四个:B→Φ,B→B,B→C,B→BC。
3.14设关系模式R(ABCDE)上FD集为F,并且F={A→BC,CD→E,B→D,E→A}。 ① 试求R的候选键。
② 试求B+的值。
解:① R的候选键有A、E、CD和BC
3.15 设有关系模式R(ABC),其关系r如图3.1所示。
① 试判断下列三个FD在关系r中是否成立?
A→B BC→A B→A
② B+=BD。
② 根据关系r,你能断定哪些FD在关系模式R上不成立?
解:
A 1 4 5 B 2 2 3 C 3 3 3 图3.1
① 在关系r中,A→B成立,BC→A不成立,B→A不成立。 ② 在关系r中,不成立的FD有:B→A,C→A,C→B,C→AB,BC→A。
3.17 设关系模式R(ABC)分解成ρ={AB,BC},如果R上的FD集F={A→B},那么这个分解是损失分解。试举出R的一个关系r,不满足mρ(r)=r。 解:这个反例r可以举测试时的初始表格:
π
A B C AB a1 a2 b13 BC b21 a2 a3
AB(r)?πBC(r)有四个元组:
A B a1 a2 a1 a2 b21 a2 b21 a2 即mρ(r)≠r。
C b13 a3 b13 a3
4.18 试解释数据库“丢失信息”与“未丢失信息”两个概念。“丢失信息”与“丢失数据”
有什么区别?
答:数据库中丢失信息是指r≠mρ(r),未丢失信息是指r=mρ(r)。
丢失信息是指不能辨别元组的真伪,而丢失数据是指丢失元组。
3.19 设关系模式R(ABC),F是R上成立的FD集,F={A→C,B→C},试分别求F在模式AB和AC上的投影。
答: πAB(F)=φ(即不存在非平凡的FD)
πAC(F)={A→C}
3.20 设关系模式R(ABC),F是R上成立的FD集,F={B→C,C→A},那么分解ρ={AB,AC}相对于F,是否无损分解和保持FD?并说明理由。 答: