精华内容
下载资源
问答
  • 关于数据库的 最小函数依赖集求法.对数据库的初学者有帮助。
  • 最小函数依赖集的求解过程

    千次阅读 2020-12-08 18:54:29
    ①先拆右边,假如依赖集F中的右边项包含不止一个属性,那么将这些项都拆为单个项。例如A->BC,拆分为A->B和A->C ②去除冗余依赖项,例如A->C和AB->C,那么就要去除AB->C这个冗余项 ③拆左边,假如...

    流程

    先拆右边,假如依赖集F中的右边项包含不止一个属性,那么将这些项都拆为单个项。例如A->BC,拆分为A->B和A->C
    去除冗余依赖项,例如A->C和AB->C,那么就要去除AB->C这个冗余项
    拆左边,假如依赖集F中的左边项包含不止一个属性,那么将这些项中的第一个属性先遮住,看剩下的属性能否推出结果,不行的话就换第二属性遮住,看剩余的属性能否推出结果,以此类推


    例题
    已知G={A->BC,CD->E,B->D,BE->F,EF->A},求最小函数依赖集
    答:
    1.先拆右边
    将G中依赖项右边包含两个属性的拆为单个属性
    拆完G={A->B,A->C,CD->E,B->D,BE->F,EF->A}

    2.去除冗余依赖项
    诀窍:一个个试
    ①先去掉A->B,发现剩余的{A->C,CD->E,B->D,BE->F,EF->A}没法推出B,所以A->B不是冗余项
    ②以此类推,最后发现G中不存在冗余项

    3.再拆左边
    ①第一个左边包含两个属性的为CD->E,先遮住C,看能否由D->E。首先由A->C可获得C,那么C与剩下的D就能推出E,因此C为冗余属性;然后再遮住D,看能否由C->E,因为A->B,A->C中都得不到D,因此没法组成CD->E,所以D不是冗余项。
    经过第一步得出的G暂为{A->B,A->C,D->E,B->D}
    ②以此类推,第二个左边包含两个属性的为BE->F,先遮住B,看能否由E->F。因为A->B可获得B,那么B与剩下的E就能推出F,因此B为冗余属性;然后在遮住E,看能否由B->F,因为D->E,那么BE->F,因此E也可以为冗余属性。可知最小函数依赖集不止一个
    暂定G为{A->B,A->C,D->E,B->D,E->F}
    ③同上,最后G为{A->B,A->C,D->E,B->D,E->F,F->A}

    最小函数依赖集为{A->B,A->C,D->E,B->D,E->F,F->A}

    展开全文
  • 数据库求最小函数依赖集

    万次阅读 多人点赞 2019-03-01 16:26:50
    ,U={A,B,C,D,E},F={A→BC,ABD→CE,E→D},F的最小依赖。 第一步:将F中所有函数依赖的右边化为单一属性。得到F1={A→B,A→C,ABD→C,ABD→E,E→D}。 第二步:将第一步得到的F1去除其中的冗余依赖...

    【例1】关系模型R<U,F>,U={A,B,C,D,E},F={A→BC,ABD→CE,E→D},求F的最小依赖集。

    第一步:将F中所有函数依赖的右边化为单一属性。得到F1={A→B,A→C,ABD→C,ABD→E,E→D}。

    第二步:将第一步得到的F1去除其中的冗余依赖关系。假设A→B是冗余依赖关系,去除后F1'={A→C,ABD→C,ABD→E,E→D},我们求A对F'的闭包(算法详见闭包算法)得,A(F1')+ =AC,不包含B,所以A→B不是冗余依赖关系,不能删除。依次判断F1中的所有函数依赖,去除冗余依赖关系。就得出F2={A→B,A→C,ABD→E,E→D}。

    第三步:对第二步所得F2去除其冗余属性。我们只关注函数依赖关系左边为多个的情况(一个必不可能为冗余属性),即观察ABD→E是否包含冗余属性。观察F2发现A→B,所以ABD中B是冗余属性可以删除,得到AD→E,最终得到了F的最小依赖关系F3={A→B,A→C,AD→E,E→D},也可以合并为F3={A→BC,AD→E,E→D}。

    展开全文
  • 最小函数依赖集求法.doc
  • 最小函数依赖集 关系模式R(U,D,DOM,F) R:关系名,符号化的元组定义 U:一组属性 D:属性组U中的属性所来自的域 DOM:属性到域的映射 F:属性组U上的一组数据依赖 函数依赖的闭包 F:FD(Functional ...

    目录

    关系模式

    函数依赖的闭包

    属性集闭包

    求候选键算法

    最小函数依赖集


    关系模式R(U,D,DOM,F)

    R:关系名,符号化的元组定义

    U:一组属性

    D:属性组U中的属性所来自的域

    DOM:属性到域的映射

    F:属性组U上的一组数据依赖

    函数依赖集的闭包

    F:FD(Functional Dependency)的集合称为函数依赖集。

    F闭包:由F中的所有FD可以推导出所有FD的集合,记为F+。

     

    例1,对于关系模式R(ABC),F={A→B,B→C},求F+。

    根据FD的定义,可推出F+={φ→φ,A→φ,A→A,A→B,A→C,A→AB,A→BC,A→ABC,…},共有43个FD。其中,φ表示空属性集。

     

    属性集闭包

    属性集闭包定义 :
    对F,F+中所有X→A的A的集合称为X的闭包,记为X+。可以理解为X+表示所有X可以决定的属性。

    属性集闭包的算法:

    A+:将A置入A+。对每一FD,若左部属于A+,则将右部置入A+,一直重复至A+不能扩大。

     

    设K为R(U,F)中的属性或属性集合,

    候选码:若U对K完全函数依赖。则K为R的候选码。

    超码:若U对K部分函数依赖。则K为R的超码,候选码是最小的超码。若候选码多余一个,则选择一个作为主码

     设关系模式R中U=ABC.......等N个属性,U中的属性在FD中有四种范围:

    (1)左右出现;

    (2)只在左部出现;

    (3)只在右部出现;

    (4)不在左右出现;

     

     求候选键算法:

    1.R:只在FD右部出现的属性,不属于候选码;

    2.L:只在FD左部出现的属性,一定存在于某候选码当中;

    3.N:外部属性一定存在于任何候选码当中;

    4.其他属性逐个与2,3的属性组合,求属性闭包,直至X的闭包等于U,若等于U,则X为候选码。

    例2,对于关系模式R(ABCD),F={A→B,B→C,D→B},求其候选键。

    先按照属性集闭包的算法,求各个闭包,然后求得候选键。

    (1)      求A+。 

    ①       A+=A。 
    ②       由A→B,而A €A+可知,则A+=AB。

    ③       由B→C,而B  A+可知,则A+=ABC。

    ④       A+封闭,即A+=ABC。

    (2) 求B+、C+、D+。 

    按步骤(1)可得:B+=BC,C+=C,D+=BCD。

    (3) 求其候选键。 显然,R的候选键为AD。

    例3,对于关系模式R(ABC),F={A→BC,BC→A},求其候选键。

    (1)   求属性的闭包。 
    按例2可得:A+=ABC,B+=B,C+=C。 

    (2)    求属性集的闭包。 
    由BC→A,则(BC)+=ABC,其余属性集闭包为属性闭包的并集。

    (3)   求其候选键。 显然,R的候选键为A和BC。

     

    最小函数依赖集

    定义:如果函数依赖集F满足以下条件,则称F为一个极小函数依赖集。也称为最小依赖集或最小覆盖。

    (1)F中任一函数依赖的右部仅含有一个属性。

    (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价。

    (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}U{Z→A}与F等价。

    最小依赖集通用算法:

    ① 用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;

    去掉多余的函数依赖:从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的函数依赖中求X的闭包X+,看X+是否包含Y,若是,则去掉X→Y;否则不能去掉,依次做下去。直到找不到冗余的函数依赖;

    ③ 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如XY→A,若要判Y为多余的,则以X→A代替XY→A是否等价?若A属于(X)+,则Y是多余属性,可以去掉。

    例4、求F={A→B,B→A,B→C,A→C,C→A},最小(极小)函数依赖集合

    1、利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖。从题目来看,F中的任何一个函数依赖的右部仅含有一个属性:
    {A→B,B→A,B→C,A→C,C→A}

    2、去掉F中多余的函数依赖

    (1)设A→B冗余,从F中去掉A→B,则F1={B→A,B→C,A→C,C→A}。计算(A)F1+:设X(0)=A,计算X(1):扫描F1中各个函数依赖,找到左部为A或A子集的函数依赖,A→C。故有X(1)=X(0)U C=AC;扫描F1中各个函数依赖,找到左部为AC或为AC子集的函数依赖,C→A,X(2)=X(1)U C=AC.但AC不包含B,故A->B不能从F中去掉。

    (2)设B→A冗余,从F中去掉B→A,则F2={A→B,B→C,A→C,C→A}。计算(B)F2+:设X(0)=B,计算X(1):扫描F2中各个函数依赖,找到左部为B或者B子集的函数依赖,B→C.故有X(1)=X(0)U C =BC;扫描F2中各个函数依赖,找到左部为BC或为BC子集的函数依赖,C->A,X(2)=X(1)U A=ABC.X(2)包含所有属性,故B→A可从F中去掉。

    (3)设B→C冗余,从F中去掉B→C,则F3={A→B,A→C,C→A}。计算(B)F3+:扫描F3中各个函数依赖,找不到左部为B或B子集的函数依赖,因为找不到这样的函数依赖,故有X(1)=X(0)=B,(B)F1+= B不包含C,故B→C不是冗余的函数依赖,不能从F1中去掉。

    (4)设A→C冗余,从F中去掉A→C,则F4={A→B,B→C,C→A}。计算(A)F4+:设X(0)=A,计算X(1):扫描F4中各个函数依赖,找到左部为A或A子集的函数依赖,A→B。故有X(1)=X(0)U B=AB;扫描F4中各个函数依赖,找到左部为AB或为AB子集的函数依赖,B→C,X(2)=X(1)U C=ABC.X(2)包含所有属性,故A→C可从F中去掉。

    (5)设C→A冗余,从F中去掉C→A,则F4={A→B,B→C}。计算(C)F5+:设X(0)=C,计算X(1):扫描F5中各个函数依赖,找到左部为C或C子集的函数依赖,找不到左部为C或C子集的函数依赖,因为找不到这样的函数依赖,故有X(1)=X(0)=C,(B)F1+= C不包含A,故C→A不是冗余的函数依赖,不能从F中去掉。

    (6)至此,所有依赖均以验算完毕,故F最小(极小)函数依赖集合为:{A→B,B→C,C→A}

      转载自原文作者:itwolf

    展开全文
  • 求最小函数依赖集

    2020-05-11 17:15:36
    例1:关系模式R(U,F)中,U=...F的最小函数依赖集 (1)用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;得到:F={B->D,DG->C,BD->E,AG->B,ADG->B,ADG->C}; (2)去掉多余的函

    参考:https://blog.csdn.net/prdslf001001/article/details/80336835

    例1:关系模式R(U,F)中,U=ABCDEG,F={B->D,DG->C,BD->E,AG->B,ADG->BC};求F的最小函数依赖集

    (1)用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;得到:

    F={B->D,DG->C,BD->E,AG->B,ADG->BADG->C};

    (2)去掉多余的函数依赖:从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的函数依赖中求X的闭包X+,依次做下去。直到找不到冗余的函数依赖;

    ① 去掉B->D,此时F={DG->C,BD->E,AG->B,ADG->B,ADG->C},此条件下得出B的闭包 B+ = B;B+不包含D,所以B->D保留。

    ②去掉DG->C,此时F={B->D,BD->E,AG->B,ADG->B,ADG->C},此时DG闭包DG+ = DG,不包含C,所以不能去掉DG->C.

    ③ 去掉BD->E,此时F={B->D,DG->C,AG->B,ADG->B,ADG->C},此时闭包BD+ = BD,不包含E,所以不能去掉BD->E,继续保留。

    ④去掉AG->B,此时F={B->D,DG->C,BD->E,ADG->B,ADG->C};此时AG+ = AG,不包含B,所以不能去掉AG->B,继续保留。

    ⑤去掉ADG->B,此时F={B->D,DG->C,BD->E,AG->B,ADG->C},此时ADG+ = ADGCBE,包含了B,所以删除ADG->B,不保留。

    ⑥去掉ADG->C,此时F={B->D,DG->C,BD->E,AG->B},此时ADG+ = ADGCBD,包含了C,所以删除ADG->C,不保留。

    综上所得,此时得到F={B->D,DG->C,BD->E,AG->B};

    (3)去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。

    此时函数依赖左边非单个属性有:DG->C,BD->E,AG->B;所以做如下操作:

    ①先来看DG->C,首先去掉D,则此时G的闭包G+ = G,不包含C,保留D。再次去掉G,此时D+ = D,不包含C,所以G也不能去掉;

    ②再来看BD->E,首先去掉B,得到此时D的闭包D+ = D,不含E,保留B。然后去掉D,此时B+ = BDE,包含了E,所以去掉D,即得出:B->E;

    ③最后再来看AG->B,去掉A,G+ = G,不包含B,不能去掉A。去掉G的时候,A的闭包A+ =A,不含B,不能去掉A,还是AG->B ;

    所以最后得出:F的最小函数依赖集是:F={B->D,DG->C,B->E,AG->B};

    参考:https://blog.csdn.net/prdslf001001/article/details/80336835

     

    展开全文
  • 最小函数依赖

    2015-05-05 15:13:35
     举例:已知关系模式R,U={A,B,C,D,E,G},F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG},F的最小函数依赖集。  解1:利用算法求解,使得其满足三个条件  ① 利用分解规则,将所有的函数依赖变成...
  • 关系数据库理论之最小函数依赖集

    万次阅读 多人点赞 2019-04-06 23:38:53
    在本文中,会介绍为什么要引入最小函数依赖集最小函数依赖集是什么,以及如何求最小函数依赖集。 为什么需要最小函数依赖集 在关系数据模型中,一个关系通常由R(U,F)构成,U为属性的全集,F为函数依赖。在实际...
  • 根据函数依赖求最小依赖

    万次阅读 多人点赞 2019-06-26 13:37:36
    【例1】关系模式R<U,F>...第二步:逐个去掉X→A依赖后,设剩下函数依赖集为G,属性X关于G的闭包,如果闭包包含右边属性A,则去掉该函数依赖。 A→B:(A)+=AC,不包含B,保留。 A→C:(A)+...
  • 最小函数依赖集的求解 一、定义  最小函数依赖集也称为极小函数依赖、最小覆盖;如果函数依赖F满足下列条件,则称F为一个最小依赖。 F中任意函数依赖的右部仅含有一个属性 F中不存在这样的函数依赖X→A...
  • 数据库闭包,最小函数依赖集

    万次阅读 多人点赞 2018-07-08 19:56:16
     例(1): 设有关系模式R(U,F),其中U={A,B,C,D,E,I},F={A→D,AB→E,BI→E,CD→I,E→C},计算(AE)+ 解: (1) 令X={AE},X(0)=AE (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖,结果是: A→D, ...
  • 求最小函数依赖集的方法

    万次阅读 多人点赞 2011-01-15 23:47:00
    求最小函数依赖集分三步: 1.将F中的所有依赖右边化为单一元素 此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足 2.去掉F中的所有依赖左边的冗余属性. 作法是属性中去掉其中的一个,看...
  • 数据库求最小函数依赖集(最小覆盖)

    千次阅读 多人点赞 2020-03-03 21:57:11
    4.对每一个X->A,暂时将其去除得到N,在N中X的闭包,如果闭包包含A,那么就从G中移除X->A 还不懂??来到题你就懂了 主要看步骤3,4。 3有解释,我来说一下4:E->D被移除了,来看看为什么被移除。 首先去除...
  • 主码求法,范式判断,最小函数依赖求法

    千次阅读 多人点赞 2019-05-08 18:45:21
    数据库中主码求法,NF判断,最小函数依赖
  • 数据库:最小函数依赖集

    千次阅读 2019-05-21 20:11:04
    1.对于函数依赖的右端,将其分解为单个属性...2.对于函数依赖集F中每一个X->A,计算G=F-{X->A},再判断对于函数依赖集合G,是否能由X->A,如果能,在F中删除X->A。 3.对于F中每个函数依赖执行上述操作。 ...
  • 怎样数据库最小函数依赖集

    千次阅读 2019-05-09 09:44:17
    设F是关系模式R(ABC)的FD,F={A->BC,B->C,A->B,AB->C},试Fmin ** 步骤如下: ** ①先把F中的FD写成单属性模式 如题得到F={A->B,A->C,B->C,A->B,AB-C} 这里显然多了一个A->B可以删除...
  • 关系规范化之求最小函数依赖集(最小覆盖)

    万次阅读 多人点赞 2016-04-25 10:02:53
    最小函数依赖集 一、等价和覆盖  定义:关系模式R上的两个依赖F和G,如果F+=G+,则称F和G是等价的,记做F≡G。若F≡G,则称G是F的一个覆盖,反之亦然。两个等价的函数依赖在表达能力上是完全相同的。   二、...
  • 【闭包就是由一个属性直接或间接推导出的所有属性的集合】  例(1): 设有关系模式R(U,F),其中U={A,B,C,D,E,I},... (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖,结果是: A→D, E→C;所以 X(1...
  • 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖最小覆盖(minimal cover)。 (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X->A,使得F与F-{X->A}...
  • 根据已知条件和推理规则,可知F+有43个函数依赖。各种情况如下: 答:F的闭包F+有43个;(AB)的闭包(AB)+ =ABC 设关系R(ABCDE)上FD为F,并且F={A→BC,CD→E,B→D,E→A}。出R的所有候选键。 解:A+=ABCDE ...
  • 一、函数依赖:在关系R中,若属性或者属性 A 中 两个元祖的值相等,如果这两个元祖中对应的属性或者属性B中的值也相同,则记作A——&gt;B。 A函数决定B; 或者 B函数依赖于A。例1:下表就是问题领域, 则存在...
  • 如果函数依赖集F满足下列3个条件,则称F为最小依赖: (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价 (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X...
  • 候选码和最小函数依赖集

    千次阅读 2015-11-10 14:25:46
    (1)候选码 设关系模式R为(BOISQD),F={S→D,I→S,IS→Q,B→Q}关系中l类(只出现在左边)L=(IB) 关系中R类(只出现在右边)R=(DQ) 关系中LR类(两边都有)LR=(S) 关系中NLR类(两边都没有)NLR=(O) NLR类O一定...
  • 求最小函数依赖

    千次阅读 2020-04-22 17:22:10
    已知关系模式R(A, B, C, D, E, G, H),函数依赖F为{BC→AE, DC→EH, DG→E, B→CD, D→G},请严格按步骤来对F进行最小化处理,得到F的最小函数依赖集 第一步 对F中的函数依赖运用分解原则来创建一个等价函数依赖...
  • ,U=ABCD,函数依赖F={A→BD,AB→C,C→D},F最小函数依赖集。 解: 1.将F中的所有函数依赖右边化为单一属性 F={A→B,A→D,AB→C,C→D} 2.去掉F中所有函数依赖左边的冗余属性 只有AB→C中左边可能出现冗余属性,...
  • 求函数依赖集F的最小覆盖

    千次阅读 2017-03-18 11:59:45
    求最小函数依赖集分三步: 1.将F中的所有依赖右边化为单一元素 此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足 2.去掉F中的所有依赖左边的冗余属性. 作法是属性中去掉其中的一个,看看是否依然可以...
  • .................... 超级详细的最小函数依赖集求解

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 185,186
精华内容 74,074
关键字:

最小函数依赖集求法