候选码求解方法

《候选码求解方法》由会员分享，可在线阅读，更多相关《候选码求解方法（4页珍藏版）》请在金锄头文库上搜索。

1、候选码的求解基本方法集合一、求解候选码基本算法的具体步骤.第 1 步,求关系模式 R 的最小函数依赖集 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 判

2、断该组合属性是 否是候选码; 找出所有的候选码后,算法结束. 第 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+,

3、如果 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 全 属性且找到所有码则结束，

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

5、解法)。如设有关系模式 R(A,B,C,D,E),其上的函数依赖集 F=ABC,CDE,BD,EA,求 出 R 的所有候选码。根据上述方法,具体求解步骤如下:把 F 右部单一化后 F= AB,AC,CDE,BD,EA ;根据判断,A 作为确定因素在左部出现的频率最 高,求 A+=ABCDE,又有 EA,求 E+=ABCDE 而 CDE,求(CD)+=ABCDE,可以得出属 性 A,E,CD 为候选码;除去 A,E,CD 外,根据一般求解法求两个属性组合的闭包,可 以得到(BC)+=ABCDE,最后可以算出 R 的候选码为:A,E,CD,BC。简而言之：没有 L，所有属性都属 LR，取左边出现频

6、率最多的属性 X，求 X+， 若包含 R 中所有属性，则 X 为侯选码。找能决定 X 的属性 Y，求 Y+，说 Y+包含 R 中所有属性，则 Y 也是。单个完后找两两结合，依次类推。（侯选码不参与 结合）四、一般的求候选码的算法已知关系模式 R(U)属性集是 A1A2.An 及 R 的函数依赖集 F,求 R(U)的一个候 选码。算法： KEY(X,F) K=A1A2An; 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)的候选码时,只能

7、求出一个,并不能保证求出所有的码。但可 以用同样的方法调整属性的删除次序而把所有的候选码都求解出来。如此题设关系 R(ABCD)及 R 上成立的函数依赖集为 F,F=ABC,CD,DA,求 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=B

8、D,用同样的方法调整属性的删除次 序,还可以得到另外的一个候选码 AB,所以最后可以得到 R 的码为 BD 和 AB。一般求解算法适用于在判断了所有的属性均是属于在函数依赖的左部和右部都 出现且在后面的几种算法都不适合的情况下采用的。简而言之：算法概述有 N 个属性，从 1 到 N 循环。K 初始为全部属性，每 次循环时减去第 N 个属性，如果 KF+包含全部属性，则 K 的值重新附值为 K 减 去第 N 个属性后的值；否则 K 仍为上次循环后的值。（算法适于所有属性皆为 LR 类且其他算法不合适时，实际算时要更换删除顺序后反复计算）五、快速求候选码的方法首先对于给定的 R(U)和函数依赖集

9、F,可以将它的属性划分为 4 类: L 类,仅出现在 F 的函数依赖左部的属性。 R 类,仅出现在 F 的函数依赖右部的属性。 N 类,在 F 的函数依赖左部和右部均未出现的属性。 LR 类,在 F 的函数依赖左部和右部两部均出现的属性。根据以下定理和推论来求解候选码。定理 1:对于给定的关系模式 R 及其函数依赖集 F,若 X(XR)是 L 类属性,则 X 必为 R 的任一候选码的成员。 推论 1:对于给定的关系模式 R 及其函数依赖集 F,若 X(XR)是 L 类属性,且 X+ 包含了 R 的全部属性,则 X 必为 R 的唯一候选码。定理 2:对于给定的关系模式 R 及其函数依赖集 F,若

10、 X(XR)是 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=AC,CA,BAC,DAC 求 R 的候选码。 解:根据函数依赖可得: 属性 B、D 为 L 类,E 为 N 类,因此属性 B、D、E 必为候选码的成员,且此三个属性的

11、闭包: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

12、为唯一侯选。（适于有 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=AB,CD,DE,EF,FC,求 R 的所有候选码。 根据算法，具体步骤如下： 求最小函数依赖集 Fm,Fm= AB,CD,DE,EF,FC ; 构造函数依赖图。 关键属性为:A 在图 1 中可以看到有一条独立回路 CDFE,所以 M=4,因此共有 4 个候选码,每个候 选码有 N=1+1=2 个属性。最后可得 R 的候选码为:AC,AD,AE,AF。 此方法适用于左部是单个属性的函数依赖求解候选码,而且如果用快速求解法又 不是能很快地求解出来候选码来的情况。