候选码的求解

81 阅读 0 评论 54 点赞

我是靠谱客的博主长情项链，最近开发中收集的这篇文章主要介绍候选码的求解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

候选码的求解

1.一般求解方法（使用于属性较少的表）
主要方法：由少到多找出每个属性集的闭包，如果其属性集的闭包包含全部的属性集，那么这个属性集就是要求的候选码。
例子：
假设：R(U)，U={A,B,C,D}
F={AB->C,C->D,D->A},找出R的所有候选键。
方法：找出U中每个集合的闭包。
单属性集：
A+={A} B+={B} C+={C,D,A} D+={D,A}
（注，
1.上面的加号应该放到右上角，因为不便所以放到了右边
2.左边为U中属性集，右边大括号中的为通过左边的属性集可以唯一确定的属性集，比如通过A可以推出A，通过C可以推出D，通过D可以推出A，所以C的闭包有C,D,A）
二属性集：
（AB）+={A,B,C,D}
（AC）+={A,C,D}
（AD）+={A,D}
（BC）+={B,C,D,A}
（BD）+={B,D,A,C}
（CD）+={C,D,A}
可以看出AB和BC、BD的闭包为包含全部的属性集，所以这是三个为本例子的候选键。
由于候选键除其本身的任一子集的闭包都不能包含全部的集合，所以不用考虑包含候选键的属性集的闭包了。
比如ABC包含AB，AB是候选键，所以ABC不能是候选键，同理ABD。
所以三个属性的集合：（ACD）+={A,C,D},不符合要求
因为四个属性的集合已经包含有候选键，所以不考虑。
最终得出候选键为：AB、BC、BD
对于一个含有N个元素的属性集，它由2^N-1个真子集，如果按这种方法，我们就需要花费很多的时间去一一求解。所以下面将介绍一种较为简单的的求解方法。
2.计算候选键的快速方法
第1步：找出不在任何FD右侧出现的所有属性，构成属性组X，X一定会出现在任何候选码中。
第2步：计算X+
第3步：如果X+=U，则X是唯一的候选码，算法结束，否则
第4步：计算Y=U-X+
第5步：对Y的每个子集a,考察Xa是否是候选码（方法同上），如果所有属性k属性集都包含候选码，则算法可以提前结束
例子：
R(ABCDEG)
F={D->G,CD->E,E->D,A->B}
分析可知，GEDB都出现在了箭头的右边，即通过其他的属性可以将其确定，所以X=AC,易知X+=（AC）+={A,C,B},从而Y=U-X+={D,E,G}
下面接着用一般的求解方法扩充X中的属性：
（ACD)+={A,C,D,B,G,E}
(ACE)+={A,C,E,B,D,G}
(ACG)+={A,C,G,B}
ACDE,ACDG,ACEG不用考察，原因是其中已经包含了X，分析知ACD、ACE为候选键。