候选码求解方法

候选码的求解基本方法集合

一、求解候选码基本算法的具体步骤.

第1 步,求关系模式R < U , F > 的最小函数依赖集F
第2 步, 按照上面的定义, 分别计算出UL ,UR , UB （UL 表示仅在函数依赖集中各依赖关系式左边出现的属性的集合; UR 表示仅在函数依赖集中各依赖关系式右边出现的属性的集合;另记UB = U - UL - UR ）
第3 步,若UL ≠Φ,计算UL的闭包，若UL+ = U ,则UL 为R 的唯一的候选码,算法结束. 若UL+ ≠U ,转第4 步. 若UL = Φ,转第5 步.
第4 步,将UL 依次与UB 中的属性组合,利用上述的定义4 判断该组合属性是否是候选码; 找出所有的候选码后,算法结束.
第5 步,对UB 中的属性及属性组合利用上述的定义4 依次进行判断;找出所有的候选码后,算法结束.

简而言之：取最小依赖集，计算UL闭包，如果UL闭包包含全属性，则UL为唯一侯选码，如果不包含，则依次与UB属性组合后再求闭包是否包含全属性。
（UL为空时，直接取UB依次组合求闭包）

二、多属性依赖集候选码求解法

输入:关系模式R及其函数依赖集F。
输出:R的所有候选码。

具体步骤:
1)把R的所有属性分为L、R、N和LR四类,并令X代表L、N类,Y代表LR类。
2)求X+,如果X+包含了R的全部属性,则X为R的唯一候选码,转(5);否则,转(3)。
3)在Y中取一个属性A,求(XA)+,如果它包含了R的全部属性,则转(4);否则,调换一个属性反复进行这一过程,直到试完所有Y中的属性。
4)如果已经找到所有的候选码,则转(5);否则在Y中依次去两个、三个……求它们的属性闭包,直到其闭包包含R的所有属性。
5)停止,输出结果。

简而言之：取一个X属性（X为L、N类）求闭包，如果包含R全部属性则为码，否则取一个LR类的Y属性A，求XA闭包，未包含R全属性则调换A，包含R全属性且找到所有码则结束，否则依次取2、3个。

三、依次递推法：

具体方法:给出一个关系模式R及所对应的函数依赖集F,经过初步判断,在函数依赖集中没有属于L的属性,所有属性都是属于LR类的,此时可以在函数依赖集中找出作为确定因素在左部出现频率最多的属性,如X,求X闭包,若其闭包包含了R中的所有属性,则X为R的一个候选码;再找出能够确定X的属性,如Y→X,求Y的闭包,若Y的闭包包含了R中的所有属性,则Y为R的一个候选码,依次往下找,直到把所有的函数依赖找完;单个属性的找完了后再找两个属性结合的,注意:此时不应该把原来求解出的候选码再进行组合(可以采用一般求解法)。

如设有关系模式R(A,B,C,D,E),其上的函数依赖集F={A→BC,CD→E,B→D,E→A},求出R的所有候选码。

根据上述方法,具体求解步骤如下:把F右部单一化后F={ A→B,A→C,CD→E,B→D,E→A };根据判断,A作为确定因素在左部出现的频率最高,求A+=ABCDE,又有E→A,求E+=ABCDE而CD→E,求(CD)+=ABCDE,可以得出属性A,E,CD为候选码;除去A,E,CD外,根据一般求解法求两个属性组合的闭包,可以得到(BC)+=ABCDE,最后可以算出R的候选码为:A,E,CD,BC。

简而言之：没有L，所有属性都属LR，取左边出现频率最多的属性X，求X+，若包含R中所有属性，则X为侯选码。找能决定X的属性Y，求Y+，说Y+包含R中所有属性，则Y也是。单个完后找两两结合，依次类推。（侯选码不参与结合）

四、一般的求候选码的算法

已知关系模式R(U)属性集是A1A2...An及R的函数依赖集F,求R(U)的一个候选码。

算法：
KEY(X,F)
K=A1A2…An;
For i=1 to n
{求K-Ai相对于F的属性闭包(K-Ai)F+;
if (K-Ai)F + =U then K=K-Ai
else then K=K; }
return K;

利用此算法求R(U)的候选码时,只能求出一个,并不能保证求出所有的码。但可以用同样的方法调整属性的删除次序而把所有的候选码都求解出来。

如此题设关系R(ABCD)及R上成立的函数依赖集为F,F={AB→C,C→D,D→A},求R的所有码。

按照上面的算法具体步骤如下:

设K={ABCD},当K=BCD时,由于KF+=ABCD，所以根据算法可删除A;

K=CD,由于KF+=ACD又因KF+不等于ABCD,所以根据算法,B不可删除;

K=BD,由于KF+=ABCD且因KF+=AB-CD,所以根据算法C可删除;

K=B,由于KF+=B又因KF+不等于ABCD,

所以根据算法,D不可删除;最后可求出KEY=BD,用同样的方法调整属性的删除次序,还可以得到另外的一个候选码AB,所以最后可以得到R的码为BD和AB。

一般求解算法适用于在判断了所有的属性均是属于在函数依赖的左部和右部都出现且在后面的几种算法都不适合的情况下采用的。

简而言之：算法概述——有N个属性，从1到N循环。K初始为全部属性，每次循环时减去第N个属性，如果KF+包含全部属性，则K的值重新附值为K减去第N个属性后的值；否则K仍为上次循环后的值。（算法适于所有属性皆为LR类且其他算法不合适时，实际算时要更换删除顺序后反复计算）

五、快速求候选码的方法

首先对于给定的R(U)和函数依赖集F,可以将它的属性划分为4类:
L类,仅出现在F的函数依赖左部的属性。
R类,仅出现在F的函数依赖右部的属性。
N类,在F的函数依赖左部和右部均未出现的属性。
LR类,在F的函数依赖左部和右部两部均出现的属性。

根据以下定理和推论来求解候选码。

定理1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,则X必为R的任一候选码的成员。
推论1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,且X+包含了R的全部属性,则X必为R的唯一候选码。

定理2:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是R类属性,则X不在任何候选码中。

定理3:设有关系模式R及其函数依赖集F,如果X是R的N类属性,则X必包含在R的任一候选码中。

推论2:对于给定的关系模式R及其函数依赖集F,如果X是R的N类和L类组成的属性集,且X+包含了R的有属性,则X是R的唯一候选码。

例：如设有关系模式R(U),其函数依赖集为F,其中:
U={A,B,C,D,E},　F={A→C,C→A,B→AC,D→AC}
求R的候选码。
解:根据函数依赖可得:
属性B、D为L类,E为N类,因此属性B、D、E必为候选码的成员,且此三个属性的闭包:B+=ABC,(BD)+=ABCD,(BDE)+=ABCDE,根据推论2可得BDE是R的唯一候选码。所以R的候选码为BDE。

如果把例题中关系模式R(U)中的属性E去掉,那么再求R的候选码的话可以根据推论1得出BD为R的唯一候选码。

快速求解方法适用于判断有属性是属于L类、N类或其中一种的情况下求解。如果有L类和N类的属性,则求解候选码速度非常快。

简而言之：L、R、N、LR类。根据定理，L、N类必为侯选码之一，如果L+包含全部R，则L为唯一侯选。R类不在任何侯选码中。L+N类且（L+N）+包含所有R，则L+N为唯一侯选。（适于有L、N类至少一种的情况。）

六、左边为单属性的函数依赖集的候选码成员的图论判定方法

算法2:单属性依赖集图论求解法。
输入:关系模式R,R的单属性函数依赖集F。
输出:R的所有候选码。

步骤:
1、求F的最小函数依赖集;
2、构造函数依赖图FDG;
3、从图中找出关键属性集X(X可为空);
4、查看G中有无独立回路,如果没有则输出X即为R的唯一候选码,转6);如果有则转5);
5、从各独立回路中去取一结点对应的属性与X组合成一候选码,并重复这一过程,取尽所有可能的组合,即为R的全部候选码;
6、结束。

如已知有关系模式R(U),其函数依赖集为F,其中：
R={A,B,C,D,E,F}，　F={A→B,C→D,D→E,E→F,F→C},求R的所有候选码。
根据算法，具体步骤如下：
求最小函数依赖集Fm,Fm={ A→B,C→D,D→E,E→F,F→C };
构造函数依赖图。
关键属性为:A
在图1中可以看到有一条独立回路CDFE,所以M=4,因此共有4个候选码,每个候选码有N=1+1=2个属性。

最后可得R的候选码为:AC,AD,AE,AF。 

此方法适用于左部是单个属性的函数依赖求解候选码,而且如果用快速求解法又不是能很快地求解出来候选码来的情况。