数据库系统概论—候选键的计算

候选键计算

    算法描述

    1.给定关系模式R（U，F）。将R的所有属性分为L，R，LR和N四类。其中

        L表示属性只在函数依赖左边出现；

        R表示属性只在函数依赖右边出现；

        LR表示属性既在左边出现，又在右边出现；

        N表示函数依赖左右都未出现。

    2.令X = L ∪ N，Y=LR。求X的闭包，若X的闭包包含了R的所有属性，则X为R的唯一候选码，转（5）。

    3.  Y中选取任意一个属性A，求（XA）的闭包，若它包含了R的全部属性，则是候选码。调换属性，反复进行这个过程，直到试完Y中的所有属性。

    4.如果已找出所有的候选码，转（5），否则在Y中依次选取2个属性，3个属性，...，求他们的闭包。若其闭包包含R的全部属性，则是候选码。

    5.结束算法，输出候选码

*注：看算法描述感觉很复杂，其实很简单。不妨先看看以下的例子。

例：关系模式R（A,B,C,D），函数依赖F={A→BC,BC→A,BCD→EF,E→C}，求R的候选码。

解：

        1.首选找出L,R,LR,N

                    只在函数依赖左边出现 L={D}

                    只在函数依赖右边出现R={F}

                    在函数依赖左右边都出现 LR={A,B,C,E}

                    函数依赖左右边都未出现 N={ }

        2.令X，判断是否是唯一候选码

                    令X=L ∪ N ={D}，则X={D}，故D的闭包D+ = {D}。因此不是候选码

        3.在LR中选取元素

                     1.选取A，则(AD)+ ={A,D,B,C,E,F}  与R相同，故AD是候选码

                     2.选取B，则(BD)+={B,D}，显然与R不同，故BD不是候选码

                    3.选取C，则(CD)+={C,D}，显然与R不同，故CD不是候选码

                    4.选取D，则(ED)+={D,E,C}，显然与R不同，故ED不是候选码

        4.因此，在LR中，使用了属性A，还剩下属性{B,C,E}未使用。

                    1.选取BC，则（BCD)+={D,B,C,E,F,A} 与R相同，故BCD是候选码

                    2.选取BE，则（BED)+={D,B,E,C,A,F}与R相同，故BDE是候选码

                    3.选取CE，则（CED)+={D,C,E}，显然与R不同，故CED不是候选码。

        此时，LR中无剩余属性【也可以理解为，LR中无新的属性组合（注意理解什么是候选键）】。

        5.算法结束

        综上所述，输出的候选键为 DA,DBC和DBE。