候选码的求解基本方法集合
一、求解候选码基本算法的具体步骤.
第 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 个。
三、依次递推法: