《候选码的求解理论和算法》由会员分享，可在线阅读，更多相关《候选码的求解理论和算法（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） ；否则调换一属性反复进行这一过程，直到试完所有 Y 中的属
3、性。（4） 在 Y 中依次取两个、三个属性求它们的属性闭包直到其闭包包含 R 的全部属性。（5） 输出结果。算法 4.1 分解成 2NF 模式集的算法设关系模式 R（U） ，属性集 U，主键是 W，R 上还存在函数依赖 XZ，并且 Z 是非主属性，x 是 W 的子集，即 XW，那么 W Z，就是一个部分函数依赖。此时应把 R 分解成两个模式：p （1）R1（XZ） ，主键是 X；（2）R2（Y） ，其中 Y=U-Z，主键仍是 W，外键是 X（REFERENCES R1） 。利用外键和主键的自然连接可以从 R1 和 R2 重新得到 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 为止。
