数据库求候选码的算法

【例1】关系模型R，U={A，B，C，D}，F={B→D，AB→C}，求R候选码。

在求解之前先要明白一些定理。我们把函数依赖集中F中的属性分为四类： 

L类：所有依赖关系中仅出现在函数依赖左部的属性。

R类：所有依赖关系中仅出现在函数依赖右部的属性。

LR类：所有依赖关系中即出现在函数依赖左部又出现在函数依赖右部的属性。

N类：所有依赖关系中没有出现的属性。

定理一：对于给定的关系模式R及其函数依赖集F，若X（X∈U）是L类属性，则X必为R的任一候选码的成员。

定理二：对于给定的关系模式R及其函数依赖集F，若X（X∈U）是R类属性，则X不在任何候选码中。

定理三：对于给定的关系模式R及其函数依赖集F，若X（X∈U）是LR类属性，则X可能在候选码中。

定理四：对于给定的关系模式R及其函数依赖集F，若X（X∈U）是N类属性，则X必包含在R的任一候选码中。

第一步：先判断属性集U中所有属性属于哪一类。A仅出现在AB→C左边，属于L类。B仅出现在B→D左边和AB→C左边，属于L 类。C仅出现在AB→C右边，属于R类。D仅出现在B→D右边，属于R类。

第二步：由定理可知，A，B必在候选码中，C，D必不在候选码中。因为不知道是否还有其他属性，假定目前候选码K=AB。

第三步：求K=AB的闭包。根据闭包算法(具体请见闭包求法)得，AB+ =ABCD，发现AB的闭包等于属性集U。可以得出结论K=AB就是R的候选码，且是唯一候选码。

但如果第三步中，求得的闭包不等于U,便要继续算下去，看例2。

【例2】关系模型R，U={A，B，C，D}，F={BCD→A，A→C}，求R候选码。

第一步：同样对U中属性进行分类，得出A是LR类，B是L类，C是LR类，D是类。

第二步：由定理可知，B，D必在候选码中，A，C可能在候选码中。假定目前候选码K=BD。

第三步：求K=BD的闭包。根据闭包算法得，BD+=BD，并不等于U。这时，我们从LR类中取一个属性，和BD组成临时候选码K。

第四步：先从LR类中取A，得到K=ABD。再求K=ABD的闭包，得到ABD+=ABCD，正好等于U,说明K=ABD是R的一个候选码。再从LR类中取C，得到K=BCD。再求K=BCD的闭包，得到BCD+=ABCD，也等于U,说明K=BCD也是R的一个候选码。所以R的候选码K={ABD,BCD}。

最后，如果第四步中在LR类中取一个属性的组合都不满足K的闭包等于数据集U，则从LR类中取2个，3个，……n个，分别组合，直到选出一个数据集K的闭包等于属性集U，K就是R的一个属性集。