数据库系统原理练习题3)

试证明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?并说明理由。 答:

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4