候选码的求解方法

《候选码的求解方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、候选码的求解方法姓名：xxx学号：xxxxxxx班级：xxxxxx在我们学习数据库原理与应用时，经常会遇到求解关系模型的一些相关问题，要看懂一个关系模型，我们必须知道这个关系模型中的候选码才能更好求解关系模型的问题，那么我该如何快速确定关系模型中的候选码呢？为此我查找相关资料得出以下一些方法，希望对我们的学习有所帮助。一、根据候选码的相关定理和推论求解候选码定理1对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，则X必为R的任一候选码的成员。推论l对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，且X+包含了R的全部属性，则X必为R的唯一候选码。定理2对于

2、给定的关系模式R及其函数依赖集F，若X（X∈R）是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、算法

3、描述（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={D→B，B→D，AD→B，AC→D}，求R4的候选码。解（1）L=（A，C

4、），R=准，LR=（B，D），N=准；（2）L∪N=（A，C），因为（AC）+=ACBD=R，所以AC是唯一候选码。例2设关系模式R=（A，B，C，D，E，F），函数依赖集F={A→BC，BC→A，BCD→EF，E→C}，求R的候选码。解（1）L=（D），R=（F），LR=（A，B，C，E），N=准；（2）L∪N=（D）D+=D；（3）因为DA+=DABCEF=R，DB+=DBDC+=DC，DE+=DEC，所以DA是候选码；（4）因为DBC+=DBCAEF=R，DBE+=DBECAF=R，DCE+=DCE，所以DBC、DBE是候选码；（5）R的候选码有DA、DBC、DBE三、利用函数

5、依赖图求解候选码1、相关知识定义在有向图中，把关系模式的属性作为顶点，属性之间的函数依赖关系作为有向边，这样的有向图称为该关系模式的函数依赖图，即FDG（FunctionDependGraph）。在一个函数依赖图中，存在下列术语：原始点：只有引出线而无引入线的结点，它表示对应L类属性；终结点：只有引入线而无引出线的结点，它表示对应R类属性；途中点：既有引入线又有引出线的结点，它表示对应LR类属性；孤立点：既无引入线又无引出线的结点，它表示对应N类属性；关键点：原始点和孤立点的统称；关键属性：关键点对应的属性；独立回路：不能被其它结点到达的回路。2、利用函数依赖图求解候选码的算法左边为

6、单属性的候选码求解算法描述（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={S→D，I→B，B→O，O→Q，Q→I}，求R的候选码。解（1）Fm=F={S→D，I→B，B→O，O→Q，Q→I}（2）构造函数依赖图如图1所示；（3）关键属性集：{S}；（4）共有1条独立回路IBOQI（5）

7、R的所有候选码为SI，SB，SO，SQ。5.3左边为多属性的候选码求解算法[7]要寻找关系模式的候选码，只要找出一组顶点，通过这一组顶点能够遍历该关系模式的FDG，则该组顶点对应的属性组为一个候选码。例4设R（U，F），U=（A，B，C，D，E，F，G），F=（AB→C，C→BD，DE→B，BE→GF）。4根据相关定理与推论，A、E的入度为0，（A，E）一定是候选码的元素。F、G的出度为0，（F，G）一定不是候选码的元素；B、C、D的入度和出度不为0，则可