规范化理论.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）}
升级会员 