模式分解详解,分解为3NF与分解为BCNF
3NF:不存在非主属性对码的传递函数依赖或部分函数依赖。如AB-C,A->C 码为(A,B),A,B是主属性,C是非主属性,C部分函数依赖于码,即不满足3NFBCNF:每个决定因素都包含码(相比于3NF,优点是加上了对主属性的限制)另一种说法:①主属性完全函数依赖于不含它的码②没有任何属性完全函数依赖于非码的任何一组属性...
3NF:不存在非主属性对码的传递函数依赖或部分函数依赖。
如AB-C,A->C 码为(A,B),A,B是主属性,C是非主属性,C部分函数依赖于码,即不满足3NF
BCNF:每个决定因素都包含码(相比于3NF,优点是加上了对主属性的限制)
另一种说法:①主属性完全函数依赖于不含它的码
②没有任何属性完全函数依赖于非码的任何一组属性
③所有非主属性对每一个码都是完全函数依赖
任何属性都完全依赖于码,不完全函数依赖于非码的任何一组属性
将关系模式R<U,F>分解为一个3NF的基本步骤是
1).首先将关系模式R的函数最小依赖集求出来。
2).若求得的函数最小依赖集左部都是单属性,则完成对于关系模式R的3NF分解,结束。
3).去掉多余的函数传递依赖
3).找出不在F中的属性,将其构成一个关系模式并去掉,剩余的记为U。
4).将左部相同的属性分为一组。对于每一组的并集若组合成为U,则完成3NF的分解。
将关系模式R<U,F>分解为一个BCNF的基本步骤是
1).求出候选关键字,检查R中关系模式是否符合BCNF,若都符合输出即可
2).查看每个关系模式左部是否含有候选关键字,若R中有关系模式S不符合BCNF,则必有X->A属于F+,且X不是S的候选关键字。因为XA不包含S的全部属性,把S分为{S1,S2},其中S1=XA,S2=(S-A)X,分别计算其最小函数依赖集,并将{S1,S2}代替S代入第一步中。
设关系模式R(A,B,C,D,E)上的函数依赖集F是{A->BC,ABD->CE,E->D}
1:计算F的最小覆盖。
首先将右部不唯一的依赖分解。得到{A->B,A->C,ABD->C,ABD->E,E->D}
然后对每一个依赖判断 :对A->B,令G=F-{A->B},查看B是否属于A关于G的闭包。即A是否能从G推导出B。经推,不能。所以,保留A->B。
同理 A->C 保留;ABD->C 删除(因为A->C);ABD->E 保留;E->D 保留,
得F={A->B,A->C,ABD->E,E->D}
第二步,对左部不唯一的依赖进行判断:对ABD->E,依次去掉A/B/D,查看(ABD-A/B/D)关于F的闭包是否包含E,是则用其取代原依赖。经推,发现AD->E满足条件。
所以,综上所述。F的最小覆盖为{A->B,A->C,AD->E,E->D}
2:直接写出R的所有关键字。
易知,码为(A,D) (A,E)
3:直接将R分解到3NF,且满足无损连接性和依赖保持性。
对F的最小覆盖进行处理:
首先,按左部相同原则分组 A->B,A->C为R1({ABC},{A->B,A->C})
AD->E为R2({A,D,E},{AD->E})
E->D为R3({E,D},{E->D})
然后,将具有包含关系的元组进行合并 R2包含R3,所以将R2,R3合并为新的R2({A,D,E},{AD->E,E->D})
最后,判断分解后的关系模式中是否含有码,若含有则为无损连接且保持依赖的3NF
否则,则是保持依赖但不是无损连接的3NF,此时需要新建一个关系模式,将码放入其中(若此题不含,则加R3({A,D},{∅}))。
该例中,R2含有码,所以满足题意。
4:上述分解是否满足BCNF?若不满足,将其分解到满足BCNF。
对于上述分解,R2中E->D,E为决定因素,不含码,所以不为BCNF(另一种理解方式,码为AD,AE,主属性D部分函数依赖于不含它的码(A,E))
所以对R2分解,使ADE分为 1:E->D, 2:ADE->D
所以有R2({A,E},{A->E}) ,R3({E,D},{E->D})
最终分解为R1({ABC},{A->B,A->C}),R2({A,E},{A->E}) ,R3({E,D},{E->D})
例2.关系模式R<U,F>,有U={A,B,C,D,E,F,G},F={B->G,CE->B,C->A,CE->G,B->D,C->D},
(1)将关系模式分解为3NF且保持函数依赖
(2)将关系模式分解为BCNF
将关系模式分解为3NF且保持函数依赖:
假设B->G冗余,则(B)+=BD,没有G故不冗余。
假设CE->B冗余,则(CE)+=CEGDA,没有B故不冗余。
假设C->A冗余,则(C)+=CD,故不冗余。
一次可以得到最小函数依赖集Fm={B->G,CE->B,C->A,B->D,C->D}。
之后将左部相同的组合并成一个组有:(BDG),(CEB),(CAD).
所以将关系模式分解为3NF且保持函数依赖的结果为:(BDG),(CEB),(CAD).
将关系模式分解为BCNF:
首先求出关系模式的候选关键字
L型: CE
LR型:B
R型: ADG
因为CE是L型,所以必定是码中的一部分。(CE)+=ABCDEG
所以CE是码。
因为Fm={B->G,CE->B,C->A,B->D,C->D}。
开始找左部不包含CE的关系模式,第一个为B->G,
将其分为R1={(BG),{B->G}}与R2={(ABCDE),{CE->B,C->A,B->D,C->D}}。注意G不能出现在R2中,要根据与G相关的关系模式进行替代。
求R1与R2的最小函数依赖集,步骤均是按照上述算法严格进行的。
R1,R2最小函数依赖集是其本身。
然后再进行分解,R1符合BCNF,继续分解R2:
B->D,左部不含码,于是分解为R2={(BD),{B->D}},R3={(ABCE),{CE->B,C->A}}。
R2,R3的最小函数依赖集均是其本身。
于是BCNF分解的最后结果为{(BG),(BD),(ABCE)}。
例1:关系模式R<U,F>,其中U={C,T,H,R,S,G},
F={CS→G,C→T,TH→R,HR→C,HS→R},将其分解成3NF并保持函数依赖。
解:根据算法进行求解
(一)计算F的最小函数依赖集
① 利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性,故不用分解。
② 去掉F中多余的函数依赖
A.设CS→G为冗余的函数依赖,则去掉CS→G,得:
F1={C→T,TH→R,HR→C,HS→R}
计算(CS)F1+:
设X(0)=CS
计算X(1):扫描F1中各个函数依赖,找到左部为CS或CS子集的函数依赖,找到一个C→T函数依赖。故有X(1)=X(0)∪T=CST。
计算X(2):扫描F1中的各个函数依赖,找到左部为CST或CST子集的函数依赖,没有找到任何函数依赖。故有X(2)=X(1)。算法终止。
CS)F1+= CST不包含G,故CS→G不是冗余的函数依赖,不能从F1中去掉。
B.设C→T为冗余的函数依赖,则去掉C→T,得:
F2={CS→G,TH→R,HR→C,HS→R}
计算(C)F2+:
设X(0)=C
计算X(1):扫描F2中的各个函数依赖,没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故C→T不是冗余的函数依赖,不能从F2中去掉。
C.设TH→R为冗余的函数依赖,则去掉TH→R,得:
F3={CS→G,C→T,HR→C,HS→R}
计算(TH)F3+:
设X(0)=TH
计算X(1):扫描F3中的各个函数依赖,没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故TH→R不是冗余的函数依赖,不能从F3中去掉。
D.设HR→C为冗余的函数依赖,则去掉HR→C,得:
F4={CS→G,C→T,TH→R,HS→R}
计算(HR)F4+:
设X(0)=HR
计算X(1):扫描F4中的各个函数依赖,没有找到左部为HR或HR子集的函数依赖。故有X(1)=X(0)。算法终止。故HR→C不是冗余的函数依赖,不能从F4中去掉。
E.设HS→R为冗余的函数依赖,则去掉HS→R,得:
F5={CS→G,C→T,TH→R,HR→C}
计算(HS)F5+:
设X(0)=HS
计算X(1):扫描F5中的各个函数依赖,没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HS→R不是冗余的函数依赖,不能从F5中去掉。即:F5={CS→G,C→T,TH→R,HR→C,HS→R}
③ 去掉F5中各函数依赖左边多余的属性(只检查左部不是单个属性的函数依赖),没有发现左边有多余属性的函数依赖。
故最小函数依赖集为:F={CS→G,C→T,TH→R,HR→C,HS→R}
(二)由于R中的所有属性均在F中都出现,所以转下一步。
(三)对F按具有相同左部的原则分为:
R1=CSG,R2=CT,R3=THR,R4=HRC,R5=HSR。
所以ρ={R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR)}。
BCNF的保持无损连接的分解
将关系模式R<U,F>分解为一个BCNF的基本步骤是
1).检查R中关系模式是否符合BCNF,若都符合输出即可
2)若R中有关系模式S不符合BCNF,则必有X->A的闭包不包含S的全部属性,把S分为{S1,S2},其中S1=XA,S2=(S-A)X,分别计算其最小函数依赖集,并将{S1,S2}代替S代入第一步中。
例题:
关系模式R<U,F>,其中:U={A,B,C,D,E},F={A→C,C→D,B→C,DE→C,CE→A},将其分解成BCNF并保持无损连接。
解:
① 令ρ={R(U,F)}。
② ρ中不是所有的模式都是BCNF,转入下一步。
③ 分解R:考虑A→C函数依赖不满足BCNF条件(A所以不是候选关键码),将其分解成R1(AC)、R2(ABDE)。计算R1和R2的最小函数依赖集分别为:F1={A→C},F2={B→D,DE→D,BE→A}。其中B→D是由于R2中没有属性C且B→C,C→D;DE→D是由于R2中没有属性C且DE→C,C→D;BE→A是由于R2中没有属性C且B→C,CE→A。又由于DE→D是蕴含关系,可以去掉,故F2={B→D,BE→A}。
分解R2:考虑B→D函数依赖不满足BCNF条件,将其分解成R21(BD)、R22(ABE)。计算R21和R22的最小函数依赖集分别为:F21={B→D},F22={BE→A}。
由于R22上的候选关键字为BE,而F22中的所有函数依赖满足BCNF条件。故R可以分解为无损连接性的BCNF如:ρ={R1(AC),R21(BD),R22(ABE)}
更多推荐
所有评论(0)