关系规范化理论复习题.doc

五、证明题
已知关系模式R中，U={A，B，C，D, E, P},F={A→B, C→P, E→A, CE→D },证明CE→B为F所蕴含。
证明：即求CE关于函数依赖集F的闭包。
(1) X(0)=CE (2)X(1)=CEAPD=ACDEP (3)X(2)= ACDEP B=ABCDEP=U
因为B包含在CE的属性闭包中，所以CE→B为F所蕴含。

也可这样证：
因为E→A，根据自反律和传递律有CE→A
又因为A→B，根据传递律有CE→B

六、设有关系模式R（U，F），其中：U={A，B，C，D，E}，F={A→B，D→AB，C→AB，BE→A，AE→C }。（共15分）（仅理科生做）
解：（1）求出F的最小函数依赖集。（5分）
（1） a.先使F中的每个函数依赖的右部属性单一
F’={ A→B，D→A，D→B，C→A ，C→B，BE→A，AE→C }
b.去除冗余的函数依赖
因为 C→A，A→B，所以C→B冗余
又因为D→A，A→B，所以D→B冗余
判断A→B是否冗余。
设：G1＝{D→A， C→A，BE→A，AE→C｝，
求（A）+G1＝A
∵B不属于（A）+G1　　∴A→B不冗余
判断D→A是否冗余。
设：G2＝{A→B， C→A，BE→A，AE→C｝，
求（D）+G2＝D
∵A不属于（D）+G2　　∴D→A不冗余
判断C→A是否冗余。
设：G3＝{A→B， D→A，BE→A，AE→C｝，
求（C）+G3＝C
∵A不属于（C）+G3　∴ C→A不冗余
判断BE→A是否冗余。
设：G4＝{A→B， D→A，C→A，AE→C｝，
求（BE）+G4＝BE
∵A不属于（BE）+G4　∴ BE→A不冗余
判断AE→C是否冗余。
设：G5＝{A→B， D→A，C→A，BE→A｝，
求（AE）+G5＝ABE
∵C不属于（AE）+G5　∴ AE→C不冗余
F={ A→B，D→A，C→A ，BE→A，AE→C }
c.去除左边冗余的属性
对于BE→A
因为 （B）+F＝B; A不属于（B）+F，所以E不冗余
（E）+F＝E；A不属于（E）+F，所以B不冗余
对于AE→C
因为（A）+F＝AB; C不属于(A）+F，所以E不冗余
（E）+F＝E；C不属于（E）+F，所以A不冗余
Fmin={ A→B，D→A，C→A ，BE→A，AE→C }

（2）求出R的侯选码。(3分)
解：根据Fmin可知，R的L类属性是DE，LR类属性是ABC，
因为（DE）+F = ABCDE=U，所以R具有唯一的候选码为DE。

（3）指出R属于第几范式。
因为码为DE，而D→A，存在非主属性对码的部分依赖，所以R是1NF。(2分)

（4）判断R的一个分解P={R1（DE），R2（AD），R3（ABE），R4（CE）}是否具有无损连接性。（5分）
a. 首先构造原始表格

A
B
C
D
E
R1(DE)
b11
b12
b13
a4
a5
R2(AD)
a1
b22
b23
a4
b25
R3(ABE)
a1
a2
b33
b34
a5
R4(CE)
b41
b42
a3
b44
a5
b. 根据A→B，所以把b22改为a2。
根据D→A，所以把b11都改为a1。
根据AE→C，所以把b33都改为b13。

经过F的一次扫描后，表格变成如下：

A
B
C
D
E
R1(DE)
a1
b12
b13
a4
a5
R2(AD)
a1
a2
b23
a4
b25
R3(ABE)
a1
a2
b13
b34
a5
R4(CE)
b41
b42
a3
b44
a5
因为表格中没有一行全为a，且改动了表中的符号，所以要对F进行第二次扫描。
c.在对F的第二次扫描中：
根据A→B，所以把第一行的b12改为a2。
表格如下：

A
B
C
D
E
R1(DE)
a1
a2
b13
a4
a5
R2(AD)
a1
a2
b23
a4
b25
R3(ABE)
a1
a2
b13
b34
a5
R4(CE)
b41
b42
a3
b44
a5
因为表格中没有一行全为a，且改动了表中的符号，所以要对F进行第三次扫描。
d. 在对表格进行第三次扫描时，没有改变表格中的一个符号，且没有一行全为a ，所以该分解不具有无损连接性。

（5）将R分解成既具有函数依赖保持又具有无损连接性的3NF。
解：针对Fmin={ A→B，D→A，C→A ，BE→A，AE→C }
按照左部相同的原则进行分组，有：
U1={AB}, U2={AD}, U3={AC}, U4={ABE}, U5={ACE}
因为U3包含在U5中，所以把U3去掉；因为U1包含在U4中，所以把U1去掉。
得到分解P={R1(AD), R2(ABE), R3(ACE)}
因为R的候选码DE不包含在任意子关系模式中，所以把DE作为一个子关系模式并入到分解中，
P={R1(AD), R2(ABE), R3(ACE)，R4（DE）}为既具有函数依赖保持又具有无损连接性的3NF分解。

五、证明题
已知关系模式R中，U={A，B，C，D, E}，F={A→BC, CD→E, B→D, E→A }，证明BC→A为F所蕴含。
证明：即求BC关于函数依赖集F的闭包。
(1)X(0)=BC (2)X(1)=BCD=BCD
(3)X(2)= BCD E=BCDE (4) X(3)= BCDE A=ABCDE=U
因为A包含在BC的属性闭包中，所以BC→A为F所蕴含。

六、设有关系模式R（U，F），其中：U={A，B，C，D，E}，F={ C→D，B→E，C→B，CD→A，A→BE }。（共15分）（仅理科生做）
解：（1）求出F的最小函数依赖集。(2分)
a，将F中的函数依赖都分解为右部为单属性的函数依赖。
　　　　F={ C→D，B→E，C→B，CD→A，A→B， A→E }
b，去掉F中冗余的函数依赖。(2分)
判断C→D是否冗余。
设：G1＝｛B→E，C→B，CD→A，A→B， A→E｝，
求（C）+G1＝CBE
∵D不属于（C）+G1　　∴C→D不冗余
判断B→E是否冗余。
设：G2＝｛C→D， C→B，CD→A，A→B， A→E｝，
求（B）+G2＝B
∵E不属于（B）+G2　　　∴ B→E不冗余
判断C→B是否冗余。
设：G3＝｛C→D，B→E， CD→A，A→B， A→E｝，
求（C）+G3＝CDABE
∵B属于（C）+G3　　　∴C→B冗余
判断CD→A是否冗余。
设：G4＝｛C→D，B→E，A→B， A→E｝，
求（CD）+G4＝CD
∵A不属于（CD）+G4　　　∴ CD→A不冗余
判断A→B是否冗余。
设：G5＝｛C→D，B→E，CD→A， A→E｝，
求（A）+G5＝AE
∵B不属于（A）+G5　　　∴A→B不冗余
判断A→E是否冗余。
设：G6＝｛C→D，B→E，CD→A，A→B｝，
求（A）+G6＝ABE
∵E属于（A）+G6　　　∴ A→E冗余
F＝｛C→D，B→E，CD→A，A→B｝

c．去除左边冗余的属性
对于 CD→A
（C）+F＝CDABE;因为A包含在（C）+F中，所以D冗余
（D）+F＝D 因为A不包含在（D）+F中，所以C不冗余
∴ CD→A可用C→A代替
Fmin＝｛C→D，B→E，C→A，A→B｝(2分)

（2）求出R的侯选码。(3分)
解：根据Fmin可知，R的L类属性是C，LR类属性是AB，R类属性是DE
因为（C）+F =ABCDE，所以R具有唯一的候选码为C。

（3）指出R属于第几范式。
因为码为C，而C→A, A→B，存在非主属性对码的传递依赖，所以R是2NF。(3分)

（4）判断R的一个分解P={R1（AB），R2（BE），R3（ACD）}是否具有无损连接性。
a.首先构造原始表格（6分）

A
B
C
D
E
R1(AB)
a1
a2
b13
b14
b15
R2(BE)
b21
a2
b23
b24
a5
R3(ACD)
a1
b32
a3
a4
b35
b.然后根据Fmin来改造表格。Fmin＝｛C→D，B→E，C→A，A→B｝
根据B→E，所以把b15改为a5。
根据A→B，所以把b32改为a2。
经过F的一次扫描后，表格变成如下：

A
B
C
D
E
R1(AB)
a1
a2
b13
b14
a5
R2(BE)
b21
a2
b23
b24
a5
R3(ACD)
a1
a2
a3
a4
b35
没有一行全为a，必须对表格进行第二遍扫描。
根据B→E，所以把b35改为a5。

A
B
C
D
E
R1(AB)
a1
a2
b13
b14
a5
R2(BE)
b21
a2
b23
b24
a5
R3(ACD)
a1
a2
a3
a4
a5

此时已有一行全为a，所以该分解具有无损连接性。

（5）将R分解成既具有函数依赖保持又具有无损连接性的3NF。
解：针对Fmin=｛C→D，B→E，C→A，A→B｝
按照左部相同的原则进行分组，有：
U1={CD}, U2={BE }, U3={AC}, U4={AB}
得到分解P={R1(CD), R2(BE), R3(AC), R4(AB)}
因为R的候选码C包含在子关系模式R1和R3中
所以分解P={R1(CD), R2(BE), R3(AC), R4(AB)}为既具有函数依赖保持又具有无损连接性的3NF分解。

5