模式分解练习题

有关模式分解题目重点放在三范式的分解上，包括分解算法及无损连接性的判断，这类题目的解题步骤一般分为三步： 第一步、将已有的函数依赖集转化为最小的函数依赖集（我们已经练习很多，不再多讲） 第二步、进行三范式分解（分解算法见书P192——算法5.3）

第三步、判断分解是否具有无损连接性（分解算法见书P190——算法5.2）

一、已知关系模式R(U，F)，U=(A，B，C，D，E，G)；F={AB→C，D→EG，C→A，BE→C，BC→D，CG→BD，ACD→B，CE→AG}；试求最小依赖集，然后采用模式分解算法将其进行规范化处理，规范为三范式，并用算法说明该分解是否具有无损连接性。 1、求最小函数依赖集

（1）利用分解规则，将F中所有函数依赖变成右边是单个属性的函数依赖，得： F1={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→B，CG→D，ACD→B，CE→A，CE→G } （2）去掉F1中多余的函数依赖：

对AB→C，在F +

1-{ AB→C }中计算（AB）G=AB ∵C∈AB，∴AB→C不是多余的函数依赖，不能去掉 对D→E，在F +

1-{ D→E }中计算（D）G=DG

∵E∈DG，∴D→E不是多余的函数依赖，不能去掉 对D→G，在F +1-{ D→G }中计算（D）G=DE

∵G∈DE，∴D→G不是多余的函数依赖，不能去掉 对C→A，在F +1-{ C→A }中计算（C）G=C

∵A∈C，∴C→A不是多余的函数依赖，不能去掉 对BE→C，在F +1-{ BE→C }中计算（BE）G=BE ∵C∈BE，∴BE→C不是多余的函数依赖，不能去掉 对BC→D，在F +1-{ BC→D }中计算（BC）G=ABC ∵D∈ABC，∴BC→D不是多余的函数依赖，不能去掉 对CG→B，在F +1-{ CG→B }中计算（CG）G=ABCDEG ∵B∈ABCDEG，∴CG→B是多余的函数依赖，可以去掉 对CG→D，在F1-{ CG→D ，CG→B }中计算（CG） +

G=ACG ∵D∈ACG，∴CG→D不是多余的函数依赖，不能去掉 对ACD→B，在F +1-{ ACD→B，CG→B }中计算（ACD）G=ACDEG ∵B∈ACDEG，∴ACD→B不是多余的函数依赖，不能去掉 对CE→A，在F +

1-{ CE→A，CG→B }中计算（CE）G=ABCDEG ∵A∈ABCDEG，∴CE→A是多余的函数依赖，可以去掉 对CE→G，在F +

1-{ CE→G ，CG→B ，CE→A }中计算（CE）G=ACE ∵G∈ACE，∴CE→G不是多余的函数依赖，不能去掉

经上述计算得：

F2={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→D，ACD→B，CE→G } （3）去掉F2中函数依赖左部多余的属性： 对AB→C，在F2中分别计算

对于A，求（B） +

F=B，∵C∈B，∴A不是多余的属性，不可以去掉 对于B，求（A） +F=A，∵C∈A，∴B不是多余的属性，不可以去掉 对BE→C，在F2中分别计算

对于B，求（E） +F=E， ∵C∈E，∴B不是多余的属性，不可以去掉 对于E，求（B） +F=B， ∵C∈B，∴E不是多余的属性，不可以去掉 对BC→D，在F2中分别计算

1

对于B，求（C）F=AC， ∵D∈AC，∴B不是多余的属性，不可以去掉 对于C，求（B）F=B， ∵C∈B， ∴C不是多余的属性，不可以去掉 对CG→D，在F2中分别计算

对于C，求（G）F=G， ∵D∈G=（G）， ∴C不是多余的属性，不可以去掉 对于G，求（C）F=AC， ∵D∈AC=（C）， ∴C不是多余的属性，不可以去掉 对ACD→B，在F2中分别计算

对于A，求（CD）F=ABCDEG， ∵B∈ABCDEG =（CD）， ∴A是多余的属性，可以去掉 F2={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→D，CD→B，CE→G } 对CD→B，在F2中分别计算

+

+

+

+ +

+

+

+

对于C，求（D）=DEG， ∵B∈DEG，∴C不是多余的属性，不可以去掉 对于D，求（C）=AC， ∵B∈AC， ∴D不是多余的属性，不可以去掉 对CE→G，在F2中分别计算

对于C，求（E）=E， ∵G∈E=（E），∴C不是多余的属性，不可以去掉 对于E，求（C）=AC， ∵G∈AC=（C），∴E不是多余的属性，不可以去掉 最终得最小的函数依赖集：

Fm={AB→C，D→E，D→G，C→A，BE→C，BC→D，CG→D，CD→B，CE→G }

+

+

+

+

+

+

2、规范化处理分解为三范式

（1）找在Fm中不出现的属性，没有； （2）在Fm中找X→A,XA=U，没有；

（3）对Fm按具有相同左部的原则分解为：ρ={ABC, DEG, BCE, BCD, CDG,，CEG }

分解为三范式后的结果为：

R1（A，B，C） R2（D，E，G） R3（B，C，E） R4（B，C，D） R5（C，D，G） R6（C，E，G）

3、判断该分解是否具有无损连接性

首先构造初始表，如下图：

属性 模式 R1（A，B，C） R2（D，E，G） R3（B，C，E） R4（B，C，D） R5（C，D，G） R6（C，E，G）

由BC→D可以把B14、B34改为A4，由BC→E可以把B15、B45改为A5，由D→G可以把B16、B36、B46改为A6，此时表中第一行为A1、A2、A3、A4、A5、A6，所以此分解具有无损连接性。

属性

A B C D E G 2

A A1 B21 B31 B41 B51 B61 B A2 B22 A2 A2 B62 B62 C A3 B23 A3 A3 A3 A3 D B14 A4 B34 A4 A4 A4 E B15 A5 A5 B45 B55 B55 G B16 A6 B36 B46 A6 A6 模式 R1（A，B，C） R2（D，E，G） R3（B，C，E） R4（B，C，D） R5（C，D，G） R6（C，E，G）

二．已知R, 其中U=（A,B,C,D,E,F,G,H,I,J）满足下列函数依赖：F={AB→E,ABE→FG,B→FI,C→J,CJ→I,G→H}，试求最小依赖集，然后采用模式分解算法将其进行规范化处理，规范为三范式，并用算法说明该分解是否具有无损连接性。

1、求最小函数依赖集

（1）利用分解规则，将F中所有函数依赖变成右边是单个属性的函数依赖，得：

F1={AB→E，ABE→G，ABE→F，B→F，B→I，C→J，CJ→I，G→H } 对AB→E，在F1-{ AB→E }中计算（AB）=ABFI

∵E∈ABFI，∴AB→E不是多余的函数依赖，不能去掉 对ABE→G，在F1-{ ABE→G }中计算（ABE）= ABEFI ∵G∈ABEFI，∴ABE→G不是多余的函数依赖，不能去掉 对ABE→F，在F1-{ ABE→F }中计算（ABE）= ABEFGIH ∵F∈ABEFGIH，∴ABE→F是多余的函数依赖，可以去掉 对B→F，在F1-{ B→F }中计算（B）=BI

∵F∈BI，∴B→F不是多余的函数依赖，不能去掉 对B→I，在F1-{ B→I }中计算（B）=BF

∵I∈BF，∴B→I不是多余的函数依赖，不能去掉 对C→J，在F1-{ C→J }中计算（C）=C

∵F∈C，∴C→J不是多余的函数依赖，不能去掉 对CJ→I，在F1-{ CJ→I }中计算（CJ）=CJ

∵I∈CJ，∴CJ→I不是多余的函数依赖，不能去掉 对G→H，在F1-{ G→H }中计算（G）=G

∵H∈G，∴G→H不是多余的函数依赖，不能去掉 经上述计算得：

F1={AB→E，ABE→G，B→F，B→I，C→J，CJ→I，G→H } 对AB→E，在F2中分别计算

对于A，求（B）=BFI，∵E∈BFI=（B），∴A不是多余的属性，不可以去掉 对于B，求（A）=A， ∵C∈A=（A），∴B不是多余的属性，不可以去掉 对ABE→G，在F2中分别计算

对于A，求（BE）=BEFI， ∵G∈BEFI =（BE），∴A不是多余的属性，不可以去掉 对于B，求（AE）=AE， ∵G∈AE=（AE），∴B不是多余的属性，不可以去掉 对于E，求（AB）=ABEFGIH，∵G∈ABEFGIH，∴E是多余的属性，可以去掉

用AB→G取代ABE→G

+

+

++

+

+

+

+

++

+

+

++++

+++

A1 B21 B31 B41 B51 B61 A2 B22 A2 A2 B62 B62 A3 B23 A3 A3 A3 A3 A4 A4 A4 A4 A4 A4 A5 A5 A5 A5 B55 B55 A6 A6 A6 A6 A6 A6 （2）去掉F1中多余的函数依赖：

（3）去掉F2中函数依赖左部多余的属性：

对CJ→I，在F2中分别计算

对于C，求（J）=J， ∵I∈J=（J），∴C不是多余的属性，不可以去掉

3

对于J，求（C）=CIJ， ∵I∈CIJ=（C），∴C是多余属性，可以去掉

用C→I取代CJ→I 最终得最小的函数依赖集：

Fm={AB→E，AB→G，B→F，B→I，C→J，C→I，G→H }

（1）找在Fm中不出现的属性，D没有出现过，将其从U中去掉得：U=（A,B,C,E,F,G,H,I,J）； （2）在Fm中找X→A,XA=U，没有；

++

2、规范化处理分解为三范式

（3）对Fm按具有相同左部的原则分解为：ρ={ABEG, BFI, CIJ, GH}

分解为三范式后的结果为：

R1（A，B，E，G） R2（B，F，I） R3（C，I，J） R4（G，H）

3、判断该分解是否具有无损连接性

首先构造初始表，如下图

属性 模式 R1（A，B，E，G） R2（B，F，I） R3（C，I，J） R4（G，H）

由B→F可以把B15改为A5，由B→I可以把B18改为A8，由G→H可以把B17改为A7，而对于C→J、C→I、AB→E、AB→G，表不改变，所以此分解不具有无损连接性。

属性 模式 R1（A，B，E，G） R2（B，F，I） R3（C，I，J） R4（G，H）

三．设一关系模式R, 其中U={c,t,h,r,s,g,q}，F={c→tq,cs→g,ht→r, hr→c,hs→r}，试求最小依赖集，然后采用模式分解算法将其进行规范化处理，规范为三范式，并用算法说明该分解是否具有无损连接性。 1、求最小函数依赖集

（1）利用分解规则，将F中所有函数依赖变成右边是单个属性的函数依赖，得：

F1={c→t, c→q, cs→g,ht→r, hr→c,hs→r} 对c→t，在F1-{ c→t }中计算（c）=cq

∵ t∈cq，∴c→t不是多余的函数依赖，不能去掉 对c→q，在F1-{ c→q }中计算（c）=ct

∵q∈ct，∴c→q不是多余的函数依赖，不能去掉

4

++

A A1 B21 B31 B41 B A2 A2 B32 B42 C B13 B23 A3 B43 E A4 B24 B34 B44 F B15 A5 B35 B45 G A6 B26 B36 A6 H B17 B27 B37 A7 I B18 A8 A8 B48 J B19 B29 A9 B49 A A1 B21 B31 B41 B A2 A2 B32 B42 C B13 B23 A3 B43 E A4 B24 B34 B44 F A5 A5 B35 B45 G A6 B26 B36 A6 H A7 B27 B37 A7 I A8 A8 A8 B48 J B19 B29 A9 B49 （2）去掉F1中多余的函数依赖：