资源描述：
《候选码的求解理论和算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、求关系模式中的候选键，是软考中的考点，但视频中没有讲，所以值得一提。 求闭包给定关系模式R（U，F），U={A，B，C，D，E}，F={B->A,D->A,A->E,AC->B},其属性AD的闭包为______.解：设X(0)=AD，计算X(1)：逐一扫描F集中的各个函数依赖，找左部是A、D、AD的函数依赖，得到AE。于是X(1)=X(0)∪EA=ADE。由于X(0)!=X(1)，所以继续扫描，于是X(2)=X(1)∪EA=ADE。由于X(2)=X(1)，所以算法到此为止，属性AD的闭包为X(2)，即ADE。 首先来看候选键的定义：若关系中
2、的某一属性组的值能唯一地标识一个元组，则称该属性组为候选键。若W是候选键，则必须满足两个条件：W的闭包是U；W没有冗余。设关系模式R中U=ABC.......等N个属性，U中的属性在FD中有四种范围：(1)左右出现;(2)只在左部出现;(3)只在右部出现;(4)不在左右出现;算法：按以下步骤求候选键：1.只在FD右部出现的属性，不属于候选码;2.只在FD左部出现的属性，一定存在于某候选码当中;3.外部属性一定存在于任何候选码当中;4.其他属性逐个与2,3的属性组合，求属性闭包，直至X的闭包等于U,若等于U,则X为候选码。例1：R,
3、U=(A,B,C,D,E,G),F={AB-->C,CD-->E,E-->A.A-->G},求候选码。 因G只在右边出现,所以G一定不属于候选码;而B,D只在左边出现,所以B,D一定属于候选码;BD的闭包还是BD,则对BD进行组合,除了G以外,BD可以跟A,C,E进行组合 先看ABD ABD本身自包ABD,而AB-->C,CD-->E,A-->G,所以ABD的闭包为ABDCEG=U 再看BDC CD-->E,E-->A,A-->G,BDC本身自包,所以BDC的闭包为BDCEAG=U 最后看BDE E-->A,A-->G,AB--
4、>C,BDE本身自包,所以BDE的闭包为BDEAGC=U 因为(ABD)、(BCD)、(BDE)的闭包都是ABCDEG所以本问题的候选码有3个分别是ABC、BCD和BDE 例2：R,U=(A,B,C),F={AB-->C,C-->B},求候选码。因为A只出现在左边，所以A一定是候选键。A的闭包还是A，则对A进行组合，可以和B,C进行组合。首先看AB，AB本身自包AB，而AB-->C，所以AB的闭包是ABC=U。再看AC，AC本身自包AC，而C-->B，所以AC的闭包是ABC=U。因为AB,AC的闭包都是ABC，也就是U，所以候选
5、键是AB，AC。 例（1）；设有关系模式R(U，F)，其中U={A，B，C，D，E，I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算(AE)+ 解: (1) 令X={AE}，X(0)=AE (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖，结果是: A→D， E→C；所以 X(1)=X(0)DC=ACDE， 显然 X(1)≠X(0). (3) 在F中寻找尚未使用过的左边是ACDE的子集的函数依赖， 结果是: CD→I；所以 X(2)=X(1)I=ACDEI。虽然X（2）≠X(1)，但F中寻找尚
6、未使用过函数依赖的左边已经没有X（2）的子集，所以不必再计算下去，即(AE)+=ACDEI。 说白话一点：闭包就是由一个属性直接或间接推导出的所有属性的集合。 例如：f={a->b，b->c，a->d，e->f}；由a可直接得到b和d，间接得到c，则a的闭包就是{a，b，c，d} 候选码的求解理论和算法 对于给定的关系R（A1，A2，…An）和函数依赖集F，可将其属性分为4类： L类 仅出现在函数依赖左部的属性。 R 类 仅出现在函数依赖右部的属性。 N 类 在函数依赖左右两边均未出现的属性。 LR
7、类 在函数依赖左右两边均出现的属性。 定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，则X必是候选码中的成员。 推论：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，且X+包含了R的全部属性；则X必为R的唯一候选码。 例（2）：设有关系模式R（A，B，C，D），其函数依赖集F={D→B，B →D，AD →B，AC →D}，求R的所有候选码解：考察F发现，A，C两属性是L类属性，所以AC必是R的候选码成员(A的闭包一定不是全集)，又因为（AC）+=ABCD，所以AC是R的唯一候选码。 定理：对于
8、给定的关系模式R及其函数依赖集F，若X（X∈R）是R类属性，则X元素一定不是候选码中的。 对于LR类，求出其闭包，若包含所有属性，则为候选键；若不包含，再和LR类中的其他属性组
