候选码的求解理论和算法.doc

求关系模式中的候选键，是软考中的考点，但视频中没有讲，所以值得一提。求闭包 给定关系模式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的函数依赖，得到A E。于是X(1)=X(0)EA=ADE。由于X(0)!=X(1)，所以继续扫描，于是X(2)=X(1)EA=ADE。由于X(2)=X(1)，所以算法到此为止，属性AD的闭包为X(2)，即ADE。首先来看候选键的定义：若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选键。若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,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进行组合先看ABDABD本身自包ABD,而AB-C,CD-E,A-G,所以ABD的闭包为ABDCEG=U 再看BDCCD-E,E-A,A-G,BDC本身自包,所以BDC的闭包为BDCEAG=U最后看BDEE-A,A-G,AB-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，所以候选键是AB，AC。例（1）；设有关系模式R(U，F)，其中U=A，B，C，D，E，I，F=AD，ABE，BIE，CDI，EC，计算(AE)+解:(1)令X=AE，X(0)=AE (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖，结果是:AD，EC；所以X(1)=X(0)DC=ACDE，显然X(1)X(0). (3)在F中寻找尚未使用过的左边是ACDE的子集的函数依赖，结果是:CDI；所以X(2)=X(1)I=ACDEI。虽然X（2）X(1)，但F中寻找尚未使用过函数依赖的左边已经没有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类在函数依赖左右两边均出现的属性。定理：对于给定的关系模式R及其函数依赖集F，若X（XR）是L类属性，则X必是候选码中的成员。推论：对于给定的关系模式R及其函数依赖集F，若X（XR）是L类属性，且X+包含了R的全部属性；则X必为R的唯一候选码。例（2）：设有关系模式R（A，B，C，D），其函数依赖集F=DB，BD，ADB，ACD，求R的所有候选码解：考察F发现，A，C两属性是L类属性，所以AC必是R的候选码成员(A的闭包一定不是全集)，又因为（AC）+=ABCD，所以AC是R的唯一候选码。定理：对于给定的关系模式R及其函数依赖集F，若X（XR）是R类属性，则X元素一定不是候选码中的。 对于LR类，求出其闭包，若包含所有属性，则为候选键；若不包含，再和LR类中的其他属性组合。 定理：对于给定的关系模式R及其函数依赖集F，若X（XR）是N类属性，则X必包含在R的任一候选码中。(直接加到候选码中)(对于N有元素的,那么要么候选键和N一样,要么只有与N合并的情况下,才有候选键)推论：对于给定的关系模式R及其函数依赖集F，若X（XR）是L类和N类组成的属性集，且X+包含了R的全部属性；则X是R的唯一候选码。算法4.1 分解成2NF模式集的算法设关系模式R（U），属性集U，主键是W，R上还存在函数依赖 XZ，并且Z是非主属性，x是W的子集，即XW，那么WZ，就是一个部分函数依赖。此时应把R分解成两个模式：（1）R1（XZ），主键是X；（2）R2（Y），其中Y=U-Z，主键仍是W，外键是X（REFERENCES R1）。利用外键和主键的自然连接可以从R1和R2重新得到R。如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。 算法4.2 分解成3NF模式集的算法设关系模式R（U），属性集U=WXY，主键是W，R上还存在函数依赖 XY。并且Y是非主属性，且X不是候选键，这样WY就是一个传递依赖。此时应把R分解成两个模式：（1）R1（XY）