规范化理论.docx
- 文档编号:15235173
- 上传时间:2023-07-02
- 格式:DOCX
- 页数:13
- 大小:479.15KB
规范化理论.docx
《规范化理论.docx》由会员分享,可在线阅读,更多相关《规范化理论.docx(13页珍藏版)》请在冰点文库上搜索。
规范化理论
闭包概念
以下是写的比较科学规范的闭包求解方法,设X和Y均为关系R的属性集的子集,F是R上的函数依赖集,若对R的任一属性集B,一旦X→B,必有B⊆Y,且对R的任一满足以上条件的属性集Y1,必有Y⊆Y1,此时称Y为属性集X在函数依赖集F下的闭包,记作X+。
计算关系R的属性集X的闭包的步骤如下:
第一步:
设最终将成为闭包的属性集是Y,把Y初始化为X;
第二步:
检查F中的每一个函数依赖A→B,如果属性集A中所有属性均在Y中,而B中有的属性不在Y中,则将其加入到Y中;
第三步:
重复第二步,直到没有属性可以添加到属性集Y中为止。
最后得到的Y就是X+
例
(1):
设有关系模式R(U,F),其中U={A,B,C,D,E,I},F={A→D,AB→E,BI→E,CD→I,E→C},计算(AE)+
解:
(1)令X={AE},X(0)=AE
(2)在F中寻找尚未使用过的左边是AE的子集的函数依赖,结果是:
A→D,E→C;所以X
(1)=X(0)DC=ACDE,显然X
(1)≠X(0).
(3)在F中寻找尚未使用过的左边是ACDE的子集的函数依赖,结果是:
CD→I;所以X
(2)=X
(1)I=ACDEI。
虽然X
(2)≠X
(1),但F中寻找尚未使用过函数依赖的左边已经没有X
(2)的子集,所以不必再计算下去,即(AE)+=ACDEI。
说白话一点:
闭包就是由一个属性直接或间接推导出的所有属性的集合。
例如:
f={a->b,b->c,a->d,e->f};由a可直接得到b和d,间接得到c,则a的闭包就是{a,b,c,d}
候选码的求解理论和算法
对于给定的关系R(A1,A2,…An)和函数依赖集F,可将其属性分为4类:
L类 仅出现在函数依赖左部的属性。
R类 仅出现在函数依赖右部的属性。
N类 在函数依赖左右两边均未出现的属性。
LR类 在函数依赖左右两边均出现的属性。
定理:
对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,则X必为R的任一候选码的成员。
推论:
对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,且X+包含了R的全部属性;则X必为R的唯一候选码。
例
(2):
设有关系模式R(A,B,C,D),其函数依赖集F={D→B,B→D,AD→B,AC→D},求R的所有候选码。
解:
考察F发现,A,C两属性是L类属性,所以AC必是R的候选码成员,又因为(AC)+=ABCD,所以AC是R的唯一候选码。
定理:
对于给定的关系模式R及其函数依赖集F,若X(X∈R)是R类属性,则X不在任何候选码中。
定理:
对于给定的关系模式R及其函数依赖集F,若X(X∈R)是N类属性,则X必包含在R的任一候选码中。
推论:
对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类和N类组成的属性集,且X+包含了R的全部属性;则X是R的唯一候选码。
最小函数依赖集
定义:
如果函数依赖集F满足下列条件,则称F为最小函数依赖集或最小覆盖。
①F中的任何一个函数依赖的右部仅含有一个属性;
②F中不存在这样一个函数依赖X→A,使得F与F-{X→A}等价;
③F中不存在这样一个函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。
算法:
计算最小函数依赖集。
输入一个函数依赖集
输出F的一个等价的最小函数依赖集G
步骤:
①用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;
②去掉多余的函数依赖:
从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的函数依赖中求X的闭包X+,看X+是否包含Y,若是,则去掉X→Y;否则不能去掉,依次做下去。
直到找不到冗余的函数依赖;
③去掉各依赖左部多余的属性。
一个一个地检查函数依赖左部非单个属性的依赖。
例如XY→A,若要判Y为多余的,则以X→A代替XY→A是否等价?
若A属于(X)+,则Y是多余属性,可以去掉。
举例:
已知关系模式R,U={A,B,C,D,E,G}F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG},求F的最小函数依赖。
解1:
利用算法求解,使得其满足三个条件
①利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖,得F为:
F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}
②去掉F中多余的函数依赖
A.设AB→C为冗余的函数依赖,则去掉AB→C,得:
F1={D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}
计算(AB)F1+:
设X(0)=AB
计算X
(1):
扫描F1中各个函数依赖,找到左部为AB或AB子集的函数依赖,因为找不到这样的函数依赖。
故有X
(1)=X(0)=AB,算法终止。
(AB)F1+=AB不包含C,故AB→C不是冗余的函数依赖,不能从F1中去掉。
B.设CG→B为冗余的函数依赖,则去掉CG→B,得:
F2={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→A,CE→G}
计算(CG)F2+:
设X(0)=CG
计算X
(1):
扫描F2中的各个函数依赖,找到左部为CG或CG子集的函数依赖,得到一个C→A函数依赖。
故有X
(1)=X(0)∪A=CGA=ACG。
计算X
(2):
扫描F2中的各个函数依赖,找到左部为ACG或ACG子集的函数依赖,得到一个CG→D函数依赖。
故有X
(2)=X
(1)∪D=ACDG。
计算X(3):
扫描F2中的各个函数依赖,找到左部为ACDG或ACDG子集的函数依赖,得到两个ACD→B和D→E函数依赖。
故有X(3)=X
(2)∪BE=ABCDEG,因为X(3)=U,算法终止。
(CG)F2+=ABCDEG包含B,故CG→B是冗余的函数依赖,从F2中去掉。
C.设CG→D为冗余的函数依赖,则去掉CG→D,得:
F3={AB→C,D→E,D→G,C→A,BE→C,BC→D,ACD→B,CE→A,CE→G}
计算(CG)F3+:
设X(0)=CG
计算X
(1):
扫描F3中的各个函数依赖,找到左部为CG或CG子集的函数依赖,得到一个C→A函数依赖。
故有X
(1)=X(0)∪A=CGA=ACG。
计算X
(2):
扫描F3中的各个函数依赖,找到左部为ACG或ACG子集的函数依赖,因为找不到这样的函数依赖。
故有X
(2)=X
(1),算法终止。
(CG)F3+=ACG。
(CG)F3+=ACG不包含D,故CG→D不是冗余的函数依赖,不能从F3中去掉。
D.设CE→A为冗余的函数依赖,则去掉CE→A,得:
F4={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G}
计算(CG)F4+:
设X(0)=CE
计算X
(1):
扫描F4中的各个函数依赖,找到左部为CE或CE子集的函数依赖,得到一个C→A函数依赖。
故有X
(1)=X(0)∪A=CEA=ACE。
计算X
(2):
扫描F4中的各个函数依赖,找到左部为ACE或ACE子集的函数依赖,得到一个CE→G函数依赖。
故有X
(2)=X
(1)∪G=ACEG。
计算X(3):
扫描F4中的各个函数依赖,找到左部为ACEG或ACEG子集的函数依赖,得到一个CG→D函数依赖。
故有X(3)=X
(2)∪D=ACDEG。
计算X(4):
扫描F4中的各个函数依赖,找到左部为ACDEG或ACDEG子集的函数依赖,得到一个ACD→B函数依赖。
故有X(4)=X(3)∪B=ABCDEG。
因为X(4)=U,算法终止。
(CE)F4+=ABCDEG包含A,故CE→A是冗余的函数依赖,从F4中去掉。
③去掉F4中各函数依赖左边多余的属性(只检查左部不是单个属性的函数依赖)由于C→A,函数依赖ACD→B中的属性A是多余的,去掉A得CD→B。
故最小函数依赖集为:
F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}
判别一个分解的无损连接性
转换成3NF的保持函数依赖的分解
转换成3NF的保持函数依赖的分解
例1:
关系模式R,其中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)}。
转换成3NF的保持无损连接和函数依赖的分解
例2:
关系模式R,其中:
U={C,T,H,R,S,G},
F={CS→G,C→T,TH→R,HR→C,HS→R},分解成3NF并保持无损连接和函数依赖。
解:
(1)根据上例例1,得到3NF并保持函数依赖的分解如下:
σ={R1(CSG),R2(CT),R3(THR),R4(HRC),R5(HSR)}。
(2)而HS是原模式的关键字,所以τ={CT,CSG,CHR,HSR,HRT,HS}。
由于HS是模式HSR的一个子集,所以消去HS后的分解{CT,CSG,CHR,HSR,HRT}就是具有无损联接性和保持函数依赖性的分解,且其中每一个模式均为3NF。
转换成BCNF的保持无损连接的分解
例3:
关系模式R,其中U={C,T,H,R,S,G},
F={CS→G,C→T,TH→R,HR→C,HS→R},将其分解成BCNF并保持无损连接。
例4:
关系模式R,其中:
U={A,B,C,D,E},F={A→C,C→D,B→C,DE→C,CE→A},将其分解成BCNF并保持无损连接。
解:
①令ρ={R(U,F)}。
②ρ中不是所有的模式都是BCNF,转入下一步。
③分解R:
R上的候选关键字为BE(因为所有函数依赖的右边没有BE)。
考虑A→C函数依赖不满足BCNF条件(因A不包含候选键BE),将其分解成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:
R2上的候选关键字为BE。
考虑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)}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 规范化 理论