规范化理论:闭包,候选键,最小函数依赖,3NF分解

您所在的位置:网站首页 R的闭包怎么求 规范化理论:闭包,候选键,最小函数依赖,3NF分解

规范化理论:闭包,候选键,最小函数依赖,3NF分解

2023-10-30 16:31| 来源: 网络整理| 查看: 265

闭包

通俗点:求 “x” 的闭包就是求 “x” 能直接或者间接推出的属性的集合,使用符号表示就是 X +   X^{+}\, X+

求解步骤

计算关系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} 至此,闭包求解结束。

候选键

设关系模式R的属性集是U,X是U的一个子集,F是在R上成立的一个函数依赖集。如果X→U在R上成立(即X→U在F+中),那么称X是R的一个超键。如果X→U在R上成立,但对X的任一真子集X’→U都不成立(即X’不在F+中,),那么称X是R上的一个候选键,候选键是最小的超键。

求解候选键的算法

对于一个给定的关系模式,需要先对关系模式中的属性分类。以-> 为界限,左右分开 (1)L类:仅出现在F中的函数依赖左部的属性; (2)R类:仅出现在F的函数依赖右部的属性; (3)N类:在F的函数依赖左右两边均未出现的属性; (4)LR类:在F的函数依赖左右两边均出现的属性。 例子:设有关系模式R(A, B, C, D, E, P)与它的函数依赖集F={A→D, E→D, D→B, BC→D, DC→A} 对其分类: A,既有左边也有右边 A→D DC→A B,既有左边也有右边 D→B BC→D C,只出现在左边 BC→D D,既有左边也有右边 D→B, BC→D, DC→A E,只出现在左边 E→D P,未出现 所以 L类:C,E R类:空 N类:P LR类:A,B,D

根据以下定理和推论来求解候选码。 定理1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,则X必为R的任一候选码的成员。 推论1:对于给定的关系模式R及其函数依赖集F若X(X∈R)是L类属性,且X包含了R的全部属性,则X必为R的唯一候选码。 定理2:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是R类属性,则X不在任何候选码中。 定理3:设有关系模式R及其函数依赖集F,如果X是R的N类属性,则X必包含在R的任一候选码中。 步骤: (1)根据上文已经分好的类,继续下面的步骤。令X代表L、N两类,Y代表LR类。 (2)求X+。若X+包含了R的全部属性,则X即为R的惟一候选码,只需转(5);否则转(3) (3)在Y中逐一取每个属性A,求(AX)+。若它包含了R的全部属性,则XA是R的一个候选键,再换Y中另一个属性反复进行这一过程,直到试完Y中所有的属性; (4)在Y中依次取两个、三个属性…求它们的属性闭包直到其闭包包含R的 全部属性。 (5)输出结果。

继续上面的例子,此时X=PCE Y= ABD 首先求X+ 求得(PCE)+ =(A, B, C, D, E, P) ,所以PCE是唯一候选码,算法结束。

举第二个例子

设有关系模式R(A, B, C, D, E)与它的函数依赖集F={A→BC, CD→E, B→D, E→A},求R的所有候选键。 首先分类 L类: R类: N类: LR类:A,B,C,D,E,F 那就直接从LR中挑选元素,首先挑选A,计算A的闭包, A+ = (A, B, C, D, E) ,所以A就是候选码 接着试B,求 B+ =(B,D) 接着试C,求 C+ =(C) 接着试D,求 D+ =(D) 接着试E,求 E+ = (A, B, C, D, E) ,所以E就是候选码 试完了单个了,继续试两个元素的,首先试BC,计算闭包 (BC)+ = (A, B, C, D, E) 所以BC就是候选码 接着试BD,求 BD+ =(B,D) 接着试CE, (CE)+ = (A, B, C, D, E)所以CE就是候选码 至此,算完了所有的候选码。因此,关系模式R的所有的候选键分别是A、E、BC和CD。

最小函数依赖 最小函数依赖存在的意义

在关系数据模型中,一个关系通常由R(U,F)构成,U为属性的全集,F为函数依赖集。在实际生活中,我们可以根据语义来定义关系中属性的依赖关系,例如学号可以唯一确定一位学生的姓名、性别等等。但是,有时候给出的函数依赖集并不是最简的,这有时会拖累我们对关系的后续处理,例如关系的分解、判断是否为无损分解等。所以,我们在必要时,需要对函数依赖集进行化简,这就是需要最小函数依赖集的原因。

最小函数依赖的求解算法 首先将函数依赖集中右部不为单个属性的分解为单个属性,比如 A->BC 分解为A->B A->C接着试着删除函数依赖集中的每一个函数依赖,并且计算删除函数依赖左部的闭包,如果该元素的闭包包含函数依赖的右边,则说明这个函数依赖是多余的,可以删除。否则,留下。比如:F = {B→D,DG→ C,BD→ E,AG→ B,ADG→ B,ADG→C} 删除B→D,求(B)+ = {B},不包含D,所以不删除 删除DG→ C,求(DG)+ = {D,G},不包含C,所以不删除 删除BD→ E,求(BD)+ = {B,D},不包含E,所以不删除 删除AG→ B,求(AG)+ = {A,G},不包含B,所以不删除 删除ADG→ B,求(ADG)+ = {ABCDGE},包含B,所以删除 删除ADG→C,求(ADG)+ = {ABCDGE},包含C,所以删除

此时,F变为{B→D,DG→ C,BD→E,AG→ B}

对于经过第2步筛选后的函数依赖集F中每个左部不为单个属性的函数依赖AB →Y,进行以下操作: 因为我们试图去除A或者B,我们先计算在不删除A或者B情况下(这里以A为例)A的闭包,然后计算将函数依赖集AB →Y变成B→Y之后B的闭包。 如果二者相等,则说明它们是等价的,A可以去除;如果不相等,则A不能去除。如果A不能去除,再试B。 针对上面的式子{B→D,DG→ C,BD→E,AG→ B} 以DG→ C为例, 未做任何变动下,计算G+={G} 删除D,即G→ C,计算G+={G,C} 二者不相等,所以不能删除D 未做任何变动下,计算D+={D} 删除D,即G→ C,计算G+={D,C} 二者不相等,所以不能删除G 以BD→E为例, 未做任何变动下,计算D+={D} 删除B,即D→ E,计算D+={D,E} 二者不相等,所以不能删除B 未做任何变动下,计算B+={B,D,E} 删除D,即B→ E,计算B+={B,D,E} 二者相等,所以能删除D 化简后式子变成,B→ E

同理可以处理AG→ B,R的最小函数依赖集为 F = {B→D,DG→ C,B→ E,AG→ B}

3NF分解 将关系R转化3NF的保持函数依赖的分解 首先计算出F的最小依赖集F’,比如根据上述算法已经算得F’={A→B,A→C,AD→E,E→D}观察U中是否有属性未在F’中出现,如果有,则这个属性组成一对关系R,并在原来的U中删除这些属性。F’已经包含所有的属性。对F’中的函数依赖,把左边的相同分为一组,一组中出现的所有属性为一个关系。如F={A→B,A→C,……},左边都为A的分为一组,出项的所有属性组为一个关系R{A,B,C,……} 所以得到R1(A,B,C) R2(A,D,E)R3(E,D) 将关系R转化3NF的既有无损连接性又保持函数依赖的分解 先计算R转化3NF的保持函数依赖的分解。这个可以直接通过上一步得到。计算出候选码,这里可以使用上面已经介绍的方法求解。候选码为AD和AE。将候选码单独组成关系得R4{A,D}和R5{A,E},然后与保持函数依赖后的分解取并集。得R1{A,B,C},R2{A,D,E},R3{E,D},R4{A,D},R5{A,E}。观察新组成的分解模式中,是否存在包含关系,有则去掉被包含的。如R3{E,D},R4{A,D},R5{A,E}都包含于R2{A,D,E},则删去,最终得到转化3NF的既有无损连接性又保持函数依赖的分解R1{A,B,C},R2{A,D,E}。


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3