候选键计算

 给定关系模式R(U,F)。将R的所有属性分为L,R,LR和N四类。其中

L表示属性只在函数依赖左边出现;
R表示属性只在函数依赖右边出现;
LR表示属性既在左边出现,又在右边出现;
N表示函数依赖左右都未出现。

例:关系模式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中无新的属性组合(注意理解什么是候选键)】。
综上所述,输出的候选键为 DA,DBC和DBE。

 

 

求解步骤

  计算关系R的属性集X的闭包的步骤如下:

  第一步:设最终将成为闭包的属性集是Y,把Y初始化为X;

  第二步:检查F中的每一个函数依赖A→B,如果属性集A中所有属性均在Y中,而B中有的属性不在Y中,则将其加入到Y中;

  第三步:重复第二步,直到没有属性可以添加到属性集Y中为止。 最后得到的Y就是X的闭包

举个例子

关系R(A,B,C)满足函数依赖M(A -> B,A -> C,B -> AC)求A,B,C的闭包
求解A的闭包:此时需要求解A的闭包,那么根据上面的描述,初始状态Y = {A}
开始依次查找每一个函数依赖,如果函数依赖的左边只有A,并且右边的右边的元素不在Y中,就把它加入Y
首先碰到A -> B,B不在Y中,此时把B加入到Y, Y = {A,B}
再来遍历函数依赖,现在只要函数依赖左边是{A ,B ,AB}中的一个,我们都可以把右边的元素吸收至,碰到A -> C,左边是A,且右边是C,没有在Y中,我们将其加入Y 。此时Y = {A, B ,C}已经包含了所有元素,算法结束。所以A的闭包为{A,B,C}
求解B的闭包:初始状态Y={B}
依次遍历所有函数依赖,查找左边只有B的,查找到B -> AC,这个函数依赖的左边只有一个B,右边的元素不在Y中,我们将{A,C}加Y,此时Y已经达到{A,B,C},算法结束。所以B的闭包为{A,B,C}
求解C的闭包:初始状态Y={C}
依次遍历所有函数依赖,查找左边只有C的,查找不到,已经没有属性可以添加至Y中,算法结束。所以C的闭包为{C}
至此,闭包求解结束。








原文地址:https://www.cnblogs.com/zouhong/p/15331467.html