3NF既具有无损连接性又保持函数依赖的分解算法.doc

求最小函数依赖集分三步:={abd->e,ab->g,b->f,c->j,cj->i,g->h};,看看是否依然可以推导此题:abd->e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性ab->g,也没有cj->i,因为c+={c,j,i}->i将成为c->iF={abd->e,ab->g,b->f,c->j,c->i,g->h};,如去掉(X->Y),然后在F中求X+,如果Y在X+中,则表明x->->e,F将等于{ab->g,b->f,c->j,c->i,g->h},而(abd)+={a,d,b,f,g,h},(ab)+={a,b,f}也不包含g,+={b}不多余,c+={c,i}不多余c->i,g->={abd->e,ab->g,b->f,c->j,c->i,g->h};转换为3NF既具有无损连接性又保持函数依赖的分解算法:第一步:首先用算法1求出R的保持函数依赖的3NF分解,设为q={R1,R2,…,Rk}(这步完成后分解已经是保持函数依赖,但不一定具有保持无损连接)第二步:设X是R的码,求出p=q {R(X)}第三步:若X是q中某个Ri的子集,则在p中去掉R(X)第四步:得到的p就是最终结果例题:R(S#,SN,P,C,S,Z)F={S#→SN,S#→P,S#→C,S#→S,S#→Z,{P,C,S}→Z,Z→P,Z→C}l第一步:求出最小FD集:F={S#→SN,S#→P,S#→C,S#→S,{P,C,S→Z,Z→P,Z→C}//S#→Z冗余,FD:最小函数依赖按具有相同左部分组:q={R1(S#,SN,P,C,S),R2(P,C,S,Z),R3(Z,P,C)}R3是R2的子集,所以去掉R3q={R1(S#,SN,P,C,S),R2(P,C,S,Z)}l第二步:R的主码为S#,于是p=q {R(X)}={R1(S#,SN,P,C,S),R2(P,C,S,Z), R(S#)}l第三步:因为{S#}是R1的子集,所以从p中去掉R(S#)l第四步:p={R1(S#,SN,P,C,S),R2(P,C,S,Z)}即最终结果判别一个分解的无损连接性举例2:已知R<U,F>,U={A,B,C,D,E},F={A→C,B→C,C→D,DE→C,CE→A},R的一个分解为R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),判断这个分解是否具有无损连接性。解:用判断无损连接的算法来解。①构造一个初始的二维表,若“属性”属于“模式”中的属性,则填aj,否则填bij。②根据A→C,对上表进行处理,由于属性列A上第1、2、5行相同均为a1,所以将属性列C上的b13、b23、b53改为同一个符号b13(取行号最小值)。③根据B→C,对上表进行处理,由于属性列B上第2、3行相同均为a2,所以将属性列C上的b13、b33改为同一个符号b13(取行号最小值)。④根据C→D,对上表进行处理,由于属性列C上第1、2、3、