当前位置:文档之家› 最小函数依赖集Fm的求法

最小函数依赖集Fm的求法

最小函数依赖集Fm的求法:
1.根据分解规则,将函数依赖的右端分解成单个属性
2.对于F中的每个函数X→A,设G=F-{X→A},如果A∈X G+,则
将X→A从中删除,否则保留。

3.对于F中每一个左端包含多个属性的X→A,选择X的每个子
集Z,如果A∈Z F+,则用Z→A代替X→A。

例如:
F={BE→G,BD→G,CDE→AB,CD→A,CE→G,BC→A,B→D,C→D}
求Fm。

解:1)右端分解成单个属性
F={BE→G,BD→G,CDE→A, CDE→B,CD→A,CE→G,BC→A,B→D,C →D}
2)设G=F-{X→A},如果A∈X G+,则将X→A删除,否则保留(1)G=F-{ BE→G }={BD→G,CDE→A, CDE→B,CD→A,CE→G,BC →A,B→D,C→D},则(BE)G+=BEDG,包含G,则删除。

(2)G=F-{BD→G, }={ CDE→A, CDE→B,CD→A,CE→G,BC→A,B →D,C→D},则(BD)G+=BD,不包含G,则保留。

(3)G=F-{CDE→A}={ BD→G, CDE→B,CD→A,CE→G,BC→A,B →D,C→D},则(CDE)G+= CDEBGA,包含A,则删除。

(4)G=F-{CDE→B}={ BD→G, CD→A,CE→G,BC→A,B→D,C→D},则(CDE)G+= CDEAG,不包含B,则保留。

(4)G=F-{CD→A,}={ BD→G, CDE→B,CE→G,BC→A,B→D,C
→D},则(CD)G+= CD,不包含A,则保留。

(5)G=F-{ CE→G,}={ BD→G, CDE→B,CD→A, BC→A,B→D,C →D},则(CE)G+= CEDBAG,包含G,则删除。

(5)G=F-{ BC→A,}={ BD→G, CDE→B,CD→A, B→D,C→D},则(BC)G+= BCDGA,包含A,则删除。

(6)G=F-{ B→D,}={ BD→G, CDE→B,CD→A, C→D},
则(B)G+= B,不包含D,则保留。

(7)G=F-{ C→D }={ BD→G, CDE→B,CD→A, B→D,},
则(C)G+= C,不包含D,则保留。

所以F={ BD→G, CDE→B,CD→A, B→D, C→D}
3) 左端包含多个属性的函数依赖X→A,选择X的每个子集Z,如果A∈Z F+,则用Z→A代替X→A
左端包含多个属性的函数依赖有BD→G, CDE→B,CD→A;
(1)BD→G的左端子集包含{B}和{D}
B F+=BDG,B F+包含G,则用B→G代替BD→G;
D F+=D,D F+不包含G;
F={ B→G, CDE→B,CD→A, B→D, C→D}
(2)CDE→B的左端子集包含{C}、{D}、{E}、{CD}、{CE}和{DE}
C F+=CDA,C F+不包含B;
D F+=D,D F+不包含B;
E F+=E,E F+不包含B;
CD F+=CDA,CD F+不包含B;
CE F+=CEDBGA,CE F+包含B,则用CE→B代替CDE→B;DE F+=DE,DE F+不包含B;
F={ B→G, CE→B,CD→A, B→D, C→D}
(3)CD→A的左端子集包含{C}、{D}
C F+=CDA,C
D F+包含A,则用C→A代替CD→A;
D F+=D,D F+不包含A;
F={ B→G, CE→B,C→A, B→D, C→D}
综上所述:Fm={ B→G, CE→B,C→A, B→D, C→D}。

相关主题