《候选码的求解理论和算法》由会员分享，可在线阅读，更多相关《候选码的求解理论和算法（2页珍藏版）》请在金锄头文库上搜索。
1、候选码的求解理论和算法 首先对于给定的 R(U)和函数依赖集 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、候选码。定理 2:对于给定的关系模式 R 及其函数依赖集 F,若 X(XR)是 R 类属性,则 X 不 在任何候选码中。定理 3:设有关系模式 R 及其函数依赖集 F,如果 X 是 R 的 N 类属性,则 X 必包含 在 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 的全部属性，则转 （5） ；否则调换一属性反复进行这一
3、过程，直到试完所有 Y 中的属性。 （4） 在 Y 中依次取两个、三个属性求它们的属性闭包直到其闭包包含 R 的 全部属性。 （5） 输出结果。算法算法 4.1 分解成分解成 2NF 模式集的算法模式集的算法 设关系模式 R（U） ，属性集 U，主键是 W，R 上还存在函数依赖 XZ，并且 Z 是非 主属性，x 是 W 的子集，即 X W，那么 WZ，就是一个部分函数依赖。此时应把 R 分解成两个模式：p （1）R1（XZ） ，主键是 X； （2）R2（Y） ，其中 Y=U-Z，主键仍是 W，外键是 X（REFERENCES R1） 。 利用外键和主键的自然连接可以从 R1 和 R2 重新得到
4、 R。 如果 R1 和 R2 还不是 2NF，则重复上述过程，一直到数据库模式中每一个关系模式都 是 2NF 为止。 算法算法 4.2 分解成分解成 3NF 模式集的算法模式集的算法 设关系模式 R（U） ，属性集 U=WXY，主键是 W，R 上还存在函数依赖 XY。并 且 Y 是非主属性，且 X 不是候选键，这样 WY 就是一个传递依赖。此时应把 R 分解成 两个模式： （1）R1（XY） ，主键是 X； （2）R2（WX） ，主键仍是 W，外键是 X（REFERENCES R1） 。 利用外键和主键的参照完整性，R1 和 R2 通过自然连接可以重新得到 R。 如果 R1 和 R2 还不是 3NF，则重复上述过程，一直到数据库模式中每一个关系模式都 是 3NF 为止。
