#### 转换成3NF的保持函数依赖的分解算法: ρ={R1,R2,...,Rk},是关系模式R的一个分解,U={A1,A2,...,An},F={FD1,FD2,...,FDp},并设F是一个最小依赖集,记FDi为Xi→Alj,其步骤如下: ① 对R的函数依赖集F进行极小化处理(处理后的结果仍记为F); ② 找出不在F中出现的属性,将这样的属性构成一个关系模式。把这些属性从U中去掉,剩余的属性仍记为U; ③ 若有X→A€ F,且XA=U,则ρ={R},算法终止; ④ 否则,对F按具有相同左部的原则分组(假定分为k组),每一组函数依赖Fi所涉及的全部属性形成一个属性集Ui。若Ui¢ Uj(i≠j),就去掉Ui。由于经过了步骤②,故,于是构成的一个保持函数依赖的分解。并且,每个Ri(Ui,Fi)均属于3NF且保持函数依赖。 对于步骤1中函数集的极小化处理可以参见博客https://www.internetblog.cn/archives/10.html #### 例题:关系模式R,其中U={C,T,H,I,S,G},F={CS→G,C→T,TH→I,HI→C,HS→I},将其分解成3NF并保持函数依赖。 #### (一)计算F的最小函数依赖集 **① 利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性,故不用分解。** **② 去掉F中多余的函数依赖** **A.设CS→G为冗余的函数依赖**,则去掉CS→G,得: F1={C→T,TH→I,HI→C,HS→I} 计算(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→I,HI→C,HS→I} 计算(C)F2+: 设X(0)=C 计算X(1):扫描F2中的各个函数依赖,没有找到左部为C的函数依赖。故有X(1)=X(0)。算法终止。故C→T不是冗余的函数依赖,不能从F2中去掉。 **C.设TH→I为冗余的函数依赖**,则去掉TH→I,得: F3={CS→G,C→T,HI→C,HS→I} 计算(TH)F3+: 设X(0)=TH 计算X(1):扫描F3中的各个函数依赖,没有找到左部为TH或TH子集的函数依赖。故有X(1)=X(0)。算法终止。故TH→I不是冗余的函数依赖,不能从F3中去掉。 **D.设HI→C为冗余的函数依赖**,则去掉HI→C,得: F4={CS→G,C→T,TH→I,HS→I} 计算(HI)F4+: 设X(0)=HI 计算X(1):扫描F4中的各个函数依赖,没有找到左部为HI或HI子集的函数依赖。故有X(1)=X(0)。算法终止。故HI→C不是冗余的函数依赖,不能从F4中去掉。 **E.设HS→I为冗余的函数依赖**,则去掉HS→I,得: F5={CS→G,C→T,TH→I,HI→C} 计算(HS)F5+: 设X(0)=HS 计算X(1):扫描F5中的各个函数依赖,没有找到左部为HS或HS子集的函数依赖。故有X(1)=X(0)。算法终止。故HS→I不是冗余的函数依赖,不能从F5中去掉。即:F5={CS→G,C→T,TH→I,HI→C,HS→I} **③ 去掉F5中各函数依赖左边多余的属性(只检查左部不是单个属性的函数依赖)** 没有发现左边有多余属性的函数依赖。 故最小函数依赖集为: F={CS→G,C→T,TH→I,HI→C,HS→I} #### (二)由于R中的所有属性均在F中都出现,所以转下一步。 #### (三)对F按具有相同左部的原则分为:R1=CSG,R2=CT,R3=THI,R4=HIC,R5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}。(三)对F按具有相同左部的原则分为:R1=CSG,R2=CT,R3=THI,R4=HIC,R5=HSI。所以ρ={R1(CSG),R2(CT),R3(THI),R4(HIC),R5(HSI)}。 声名:本文转载自百度文库 http://wenku.baidu.com/link?url=MUYZ--karIERpPnbvYAa5mb5f6LGCTtR41OFmv8lEMCivO96FmQ-ZbYtETZF-BlEw1Um6a3Bkb0qkxWE7d3AR9dyFsew-_HtMftPcbl0qli Last modification:June 17th, 2020 at 05:39 pm © The copyright belongs to the author Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author 谢谢,不用了 Pay by AliPay Pay by WeChat