候选码的求解方法.doc

候选码的求解方法姓名：xxx 学号：xxxxxxx 班级：xxxxxx在我们学习数据库原理与应用时，经常会遇到求解关系模型的一些相关问题，要看懂一个关系模型，我们必须知道这个关系模型中的候选码才能更好求解关系模型的问题，那么我该如何快速确定关系模型中的候选码呢？为此我查找相关资料得出以下一些方法，希望对我们的学习有所帮助。一、根据候选码的相关定理和推论求解候选码定理1 对于给定的关系模式R 及其函数依赖集F，若X（XR）是L 类属性，则X 必为R 的任一候选码的成员。推论l 对于给定的关系模式R 及其函数依赖集F，若X（XR）是L 类属性，且X+包含了R 的全部属性，则X 必为R 的唯一候选码。定理2 对于给定的关系模式R 及其函数依赖集F，若X（XR）是R 类属性，则X 不在任何候选码中。定理3 设有关系模式R 及其函数依赖集F，如果X 是R 的N 类属性，则X 必包含在R 的任一候选码中。推论2 对于给定的关系模式R 及其函数依赖集F，如果X 是R 的N 类和L 类组成的属性集，且X+包含了R 的有属性，则X 是R 的唯一候选码。二、利用属性闭包进行候选码求解的算法1、属性分类相关定义对于给定的关系模式R（U，F），其属性分为4 类：L 类（仅出现在F 的函数依赖左部的属性）；R 类（仅出现在F 的函数依赖右部的属性）；N 类（在F 的函数依赖左部和右部均未出现的属性）；LR 类（在F 的函数依赖左部和右部两部均出现的属性）。2、算法描述（1）将R 的所有属性分为L、R、LR 和N 四类，并令X 代表L、N 类，Y 代表LR 类。（2）求X+。若X+包含了R 的全部属性，则即为R 的唯一候选码，转（5）；否则，转（3）。（3）在Y 中取一属性A，求（XA）+ ，若它包含了R 的全部属性，则是候选码，转（4）；否则，调换一属性反复进行这一过程，直到试完所有Y 中的属性。（4）如果已找出所有候选码，则转（5）；否则在Y 中依次取2 个、3 个、，求它们的属性闭包，若其闭包包含R 的全部属性，则是候选码。（5）结束。3、举例例1设关系模式R=（A，B，C，D），函数依赖集F=DB，BD，ADB，ACD，求R 的候选码。解（1）L=（A，C），R=准，LR=（B，D），N=准；（2）LN=（A，C），因为（AC）+=ACBD=R，所以AC 是唯一候选码。例2 设关系模式R=（A，B，C，D，E，F），函数依赖集F=ABC，BCA，BCDEF，EC，求R 的候选码。解（1）L=（D），R=（F），LR=（A，B，C，E），N=准；（2）LN=（D）D+=D；（3）因为DA+=DABCEF=R，DB+=DB DC+=DC，DE+=DEC， 所以DA 是候选码； （4） 因为DBC+=DBCAEF=R，DBE+=DBECAF=R，DCE+=DCE， 所以DBC、DBE 是候选码；（5）R 的候选码有DA、DBC、DBE三、利用函数依赖图求解候选码1、相关知识定义 在有向图中，把关系模式的属性作为顶点，属性之间的函数依赖关系作为有向边，这样的有向图称为该关系模式的函数依赖图，即FDG（Function Depend Graph）。在一个函数依赖图中，存在下列术语：原始点：只有引出线而无引入线的结点，它表示对应L 类属性；终结点：只有引入线而无引出线的结点，它表示对应R 类属性；途中点：既有引入线又有引出线的结点，它表示对应LR 类属性；孤立点：既无引入线又无引出线的结点，它表示对应N 类属性；关键点：原始点和孤立点的统称；关键属性：关键点对应的属性；独立回路：不能被其它结点到达的回路。2、 利用函数依赖图求解候选码的算法左边为单属性的候选码求解算法描述（1）求最小函数依赖集Fm；（2）构造函数依赖图FDG；（3）从图中找出关键属性集X；（4）查看FDG 有无独立回路，若无则X 即为R 的唯一候选码，转（6），若有，则转（5）；（5）从各独立回路中各取一结点对应的属性与X 组合成一候选码，并重复这一过程，取尽所有可能的组合，即为R 的全部候选码；（6）结束。3、举例例3 设R=（O，B，I，S，O，D），F=SD，IB，BO，OQ，QI，求R 的候选码。解（1）Fm=F=SD，IB，BO，OQ，QI（2）构造函数依赖图如图1 所示； （3）关键属性集：S；（4）共有1 条独立回路IBOQI（5）R 的所有候选码为SI，SB，SO，SQ。5.3 左边为多属性的候选码求解算法7要寻找关系模式的候选码，只要找出一组顶点，通过这一组顶点能够遍历该关系模式的FDG，则该组顶点对应的属性组为一个候选码。例4 设R（U，F），U=（A，B，C，D，E，F，G），F=（ABC，CBD，DEB，BEGF）。根据相关定理与推论，A、E 的入度为0， （A，E）一定是候选码的元素。F、G 的出度为0，（F，G）一定不是候选码的元素；B、C、D 的入度和出度不为0，则可能是候选码的元素。根据能否遍历FDG，结果有三个候选码，分别为（A，E，B）、（A，E，四、依次递推法：具体方法:给出一个关系模式R及所对应的函数依赖集F,经过初步判断,在函数依赖集中没有属于L的属性,所有属性都是属于LR类的,此时可以在函数依赖集中找出作为确定因素在左部出现频率最多的属性,如X,求X闭包,若其闭包包含了R中的所有属性,则X为R的一个候选码;再找出能够确定X的属性,如YX,求Y的闭包,若Y的闭包包含了R中的所有属性,则Y为R的一个候选码,依次往下找,直到把所有的函数依赖找完;单个属性的找完了后再找两个属性结合的,注意:此时不应该把原来求解出的候选码再进行组合(可以采用一般求解法)。例5 设有关系模式R(A,B,C,D,E),其上的函数依赖集F=ABC,CDE,BD,EA,求出R的所有候选码。根据上述方法,具体求解步骤如下:把F右部单一化后F= AB,AC,CDE,BD,EA ;根据判断,A作为确定因素在左部出现的频率最高,求A+=ABCDE,又有EA,求E+=ABCDE而CDE,求(CD)+=ABCDE,可以得出属性A,E,CD为候选码;除去A,E,CD外,根据一般求解法求两个属性组合的闭包,可以得到(BC)+=ABCDE,最后可以算出R的候选码为:A,E,CD,BC简而言之：没有L，所有属性都属LR，取左边出现频率最多的属性X，求X+，若包含R中所有属性，则X为侯选码。找能决定X的属性Y，求Y+，说Y+包含R中所有属性，则Y也是。单个完后找两两结合，依次类推。（侯选码不参与结合）五、一般的求候选码的算法已知关系模式R(U)属性集是A1A2.An及R的函数依赖集F,求R(U)的一个候选码。算法：KEY(X,F)K=A1A2An;For i=1 to n求K-Ai相对于F的属性闭包(K-Ai)F+;if (K-Ai)F + =U then K=K-Aielse then K=K; return K;利用此算法求R(U)的候选码时,只能求出一个,并不能保证求出所有的码。但可以用同样的方法调整属性的删除次序而把所有的候选码都求解出来。如此题设关系R(ABCD)及R上成立的函数依赖集为F,F=ABC,CD,DA,求R的所有码。按照上面的算法具体步骤如下:设K=ABCD,当K=BCD时,由于KF+=ABCD，所以根据算法可删除A;K=CD,由于KF+=ACD又因KF+不等于ABCD,所以根据算法,B不可删除;K=BD,由于KF+=ABCD且因KF+=AB-CD,所以根据算法C可删除;K=B,由于KF+=B又因KF+不等于ABCD,所以根据算法,D不可删除;最后可求出KEY=BD,用同样的方法调整属性的删除次序,还可以得到另外的一个候选码AB,所以最后可以得到R的码为BD和AB。一般求解算法适用于在判断了所有的属性均是属于在函数依赖的左部和右部都出现且在后面的几种算法都不适合的情况下采用的。简而言之：算法概述有N个属性，从1到N循环。K初始为全部属性，每次循环时减去第N个属性，如果KF+包含全部属性，则K的值重新附值为K减去第