保持函数依赖的模式分解

前端之家收集整理的这篇文章主要介绍了保持函数依赖的模式分解前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

一、转换成3NF的保持函数依赖的分解

算法

ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解,U={A1,A2,An}F={FD1,FD2,FDp},并设F是一个最小依赖集,记FDiXiAlj,其步骤如下:

R<U,F>函数依赖集F进行极小化处理(处理后的结果仍记为F);

找出不在F中出现的属性,将这样的属性构成一个关系模式。把这些属性U中去掉,剩余的属性仍记为U

若有XAF,且XA=U,则ρ={R},算法终止;

否则,对F按具有相同左部的原则分组(假定分为k),每一组函数依赖Fi所涉及的全部属性形成一个属性Ui。若UiUj(ij),就去掉Ui。由于经过了步骤②,故

,于是构成的一个保持函数依赖的分解。并且,每个Ri(Ui,Fi)均属于3NF且保持函数依赖。

1:关系模式R<U,F>,其中U={C,T,H,I,S,G}F={CSG,CT,THI,HIC,HSI},将其分解成3NF并保持函数依赖。

解:根据算法进行求解

()计算F的最小函数依赖集

利用分解规则,将所有的函数依赖变成右边都是单个属性函数依赖。由于F的所有函数依赖的右边都是单个属性,故不用分解。

去掉F中多余的函数依赖

A.设CSG为冗余的函数依赖,则去掉CSG,得

F1={CT,HSI}

计算(CS)F1+

X(0)=CS

计算X(1):扫描F1中各个函数依赖,找到左部为CSCS子集的函数依赖,找到一个CT函数依赖。故有X(1)=X(0)T=CST

计算X(2):扫描F1中的各个函数依赖,找到左部为CSTCST子集的函数依赖,没有找到任何函数依赖。故有X(2)=X(1)。算法终止。

(CS)F1+= CST不包含GCSG不是冗余的函数依赖,不能从F1中去掉。

B.设CT为冗余的函数依赖,则去掉CT,得

F2={CSG,HSI}

计算(C)F2+

X(0)=C

计算X(1):扫描F2中的各个函数依赖,没有找到左部为C函数依赖。故有X(1)=X(0)。算法终止。故CT不是冗余的函数依赖,不能从F2中去掉。

C.设THI为冗余的函数依赖,则去掉THI,得

F3={CSG,HSI}

计算(TH)F3+

X(0)=TH

计算X(1):扫描F3中的各个函数依赖,没有找到左部为THTH子集的函数依赖。故有X(1)=X(0)。算法终止。故THI不是冗余的函数依赖,不能从F3中去掉。

D.设HIC为冗余的函数依赖,则去掉HIC,得

F4={CSG,HSI}

计算(HI)F4+

X(0)=HI

计算X(1):扫描F4中的各个函数依赖,没有找到左部为HIHI子集的函数依赖。故有X(1)=X(0)。算法终止。故HIC不是冗余的函数依赖,不能从F4中去掉。

E.设HSI为冗余的函数依赖,则去掉HSI,得

F5={CSG,HIC}

计算(HS)F5+

X(0)=HS

计算X(1):扫描F5中的各个函数依赖,没有找到左部为HSHS子集的函数依赖。故有X(1)=X(0)。算法终止。故HSI不是冗余的函数依赖,不能从F5中去掉。即:F5={CSG,HSI}

去掉F5中各函数依赖左边多余的属性(只检查左部不是单个属性函数依赖)

没有发现左边有多余属性函数依赖。故最小函数依赖集为:

F={CSG,HSI}

()由于R中的所有属性均在F中都出现,所以转下一步。

()F按具有相同左部的原则分为:R1=CSGR2=CTR3=THIR4=HICR5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}

猜你在找的设计模式相关文章