精华内容
下载资源
问答
  • 根据函数依赖求最小依赖集

    万次阅读 多人点赞 2019-06-26 13:37:36
    ,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} 第二步:逐个去掉X→A依赖后,设剩下函数依赖集为G,求属性集X关于G的闭包,...

    【例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}

    第二步:逐个去掉X→A依赖后,设剩下函数依赖集为G,求属性集X关于G的闭包,如果闭包包含右边属性A,则去掉该函数依赖。

    A→B:(A)+=AC,不包含B,保留。

    A→C:(A)+=AB,不包含C,保留。

    ABD→C:(ABD)+=ABCDE,包含C,去掉。

    ABD→E:(ABD)+=ABCD,不包含E,保留。

    E→D:(E)+=E,不包含D,保留。
    (在这里,求闭包的时候,不能再用前面去掉的函数依赖了,所以最小依赖集不唯一,写出一个即可。)

    所以F2={A→B,A→C,ABD→E,E→D}

    第三步:对左边属性单一化,X=B1B2...Bi,逐个用B1→A替代原依赖X→A,判断属性集(X-B1)关于F的闭包,如果包含A则用X-B1代替X。

    ABD→E:A→E,求(BD)+=BD,不包含E,不冗余
                     B→E,求(AD)+=ABCDE,包含E,存在冗余则使用AD→E替换ABD→E
                     D→E,求(AB)+=ABC,不包含E,不冗余

    所以F3={A→B,A→C,AD→E,E→D}
    继续第三步
    AD→E:A→E,求(D)+=D,不包含E,不冗余
                   D→E,求(A)+=ABC,不包含E,不冗余

    所以最小依赖集Fm={A→B,A→C,AD→E,E→D}

     

    展开全文
  • 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集或最小覆盖(minimal cover)。 (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X->A,使得F与F-{X->A}...

    小声bb:如果里面有错的地方请提出来~感激不尽XDDDD


    一、定义

               如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集F_{m},亦称为最小依赖集最小覆盖(minimal cover)。

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

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

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

              最小依赖集不是唯一的,它与对各函数依赖FD_{i}及X->A中X各属性的处置顺序有关。

    二、分析(求解方法)

              对于条件(1),即将比如X->YZ,分解为X->Y和X->Z。

              (对于条件2和3为了便于理解我写出了简便的理解方式,大家可以通过举F和F-某个依赖集来验证以加深理解)

              对于条件(2),说明F_{m}中不能有多余的函数依赖,此处多余即为可以通过推导得到:比如F{A->B,B->C,A->C},则A->C为多余的。但是F_{m}可以是{A->B,B->C,C->A},即把这个函数依赖删去后剩下的F`与F不能相同。

              对于条件(3),有两种情况(因为F_{m}不唯一,但这两种情况不能同时写在一个F_{m}中),即把这个能互推的函数依赖删去后剩下的F`与F不能相同。:

             1.F_{m}中不存在可以互相依赖的,比如F{A->B,B->A},则其中一个为多余的,删去其中一个。

             2.条件中为“真子集”,真子集不包含它本身,则F_{m}可以是{A->B,B->A}。

    三、实例

    【实例1:求最小依赖集】

    问题:已知F={A->B,B->A,B->C,A->C,C->A},求F_{m}

    解答

    1.看条件(1):F函数依赖的右部都只含有一个属性,满足条件(1);

    2.结合条件(2)和(3):

    F中有 A->B,B->C,A->C,删去A->C,得F_{m1}={A->B,B->A,B->C,C->A}

    删去B->A得F_{m2}={A->B,B->C,C->A};

    留下所有可以相互推导的F_{m3}={A->B,B->A,A->C,C->A}

    【实例2:判断最小依赖集】

    问题:U={A,B,C,D,E},判断F_{1}={A->B,B->C,(A,D)->E},F_{2}={A->B,A->C,B->C,(A,D)->E,(A,B)->B}是否是最小依赖集。

    解答:直接可以判断出F_{1}是最小依赖集,F_{2}中有A->B,A->C,B->C,所以不是最小依赖集

     

    展开全文
  • 求闭包和最小依赖集

    2011-12-04 06:41:08
    求闭包和最小依赖集
  • 最小依赖集

    千次阅读 2020-04-28 09:27:07
    ,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} 第二步:逐个去掉X→A依赖后,设剩下函数依赖集为G,求属性集X关于G的闭包,...

    【例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}

    第二步:逐个去掉X→A依赖后,设剩下函数依赖集为G,求属性集X关于G的闭包,如果闭包包含右边属性A,则去掉该函数依赖。

    A→B:(A)+=AC,不包含B,保留。

    A→C:(A)+=AB,不包含C,保留。

    ABD→C:(ABD)+=ABCDE,包含C,去掉。

    ABD→E:(ABD)+=ABCD,不包含B,保留。

    E→D:(E)+=E,不包含D,保留。
    (在这里,求闭包的时候,不能再用前面去掉的函数依赖了,所以最小依赖集不唯一,写出一个即可。)

    所以F2={A→B,A→C,ABD→E,E→D}

    第三步:对左边属性单一化,X=B1B2...Bi,逐个用B1→A替代原依赖X→A,判断属性集(X-B1)关于F的闭包,如果包含A则用X-B1代替X。

    ABD→E:A→E,求(BD)+=BD,不包含E,不冗余
                     B→E,求(AD)+=ABCDE,包含E,存在冗余则使用AD→E替换ABD→E
                     D→E,求(AB)+=ABC,不包含E,不冗余

    所以F3={A→B,A→C,AD→E,E→D}
    继续第三步
    AD→E:A→E,求(D)+=D,不包含E,不冗余
                   D→E,求(A)+=ABC,不包含E,不冗余

    所以最小依赖集Fm={A→B,A→C,AD→E,E→D}

    原文链接:https://blog.csdn.net/Long_H_Zhu/article/details/93725797

    https://blog.csdn.net/breathN/article/details/88432401

    展开全文
  • 规范化理论:如何计算最小依赖集

    千次阅读 多人点赞 2019-05-14 21:31:49
    什么是最小依赖集? 如果函数依赖集F满足一下条件,则称F为一个最小依赖集。 (1)F中任意一函数的右部仅含有一个属性。 (2)F中不存在这样的函数依赖X→A,使得F与F-{X-A}等价,即F中的函数依赖均不能由F中其他...

    什么是最小函数依赖集?

    如果函数依赖集F满足一下条件,则称F为一个最小函数依赖集

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

    (2)F中不存在这样的函数依赖X→A,使得F与F-{X-A}等价,即F中的函数依赖均不能由F中其他函数依赖导出。

    (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}\cup{Z→A}与F等价,即F中各函数依赖的左部均为最小属性集(也就是说左部不存在冗余属性)。

     

    如何计算最小函数依赖集?

    算法步骤:

    (1)将F中的所有函数依赖的右边化为单一属性;

    (2)去掉F中的所有函数依赖左边的冗余属性;

    (3)去掉F中所有冗余的函数依赖。

    F的函数最小依赖集_{}F_{min}并不是唯一的,它与对各函数依赖FD_{i}及X→A中X个属性的处置的顺序有关。

     

    【例题】已知函数依赖集F={A→BD, AB→C, C→D},求F的最小函数依赖集。

    解题思路:

    (1)将F中的所有函数依赖的右边化为单一属性:F={A→B, A→D, AB→C, C→D}。

    (2)去掉F中的所有函数依赖左边的冗余属性:观察F,发现可能要处理的函数依赖为AB→C。

             先求属性A关于F的闭包A_{F}^{+}

             A→B,A,B自然在A_{F}^{+}中;

             AB→C,C也在A_{F}^{+}中;

             C→D,D也在A_{F}^{+}中;

    (闭包的具体求解算法请参考:如何求属性集X关于F的闭包?

    因此,A_{F}^{+}={A, B, C, D},即A能根据Armstrong公理推导出B,C,D,说明函数依赖AB→C左边的属性B是冗余的,可以去掉。处理后的F={A→B, A→D, A→C, C→D}。

    同理,还需要看属性B关于F的闭包B_{F}^{+},来判断AB→C左边的A是否是冗余的。B_{F}^{+}={B},因此A不是冗余的。

    (3)去掉F中所有冗余的函数依赖关系:我们试着看一下函数依赖A→D是否是冗余的。

             先去掉A→D,处理后的F={A→B, A→C, C→D};

             求A关于处理后F的闭包A_{F}^{+}^{'}^{}A_{F}^{+}^{'}={A, B, C, D};

     发现A_{F}^{+}^{'}=A_{F}^{+},说明即使不需要F中的函数依赖A→D,属性A也能根据Armstrong公理导出D,因此A→D是冗余的,可以去掉,去掉后得到F的最小依赖集F_{min}={A→B, A→C, C→D}。

              

     

    参考自:《数据库系统概论》,王珊,萨师煊编著

     

     

     

    展开全文
  • 如果函数依赖集F满足下列3个条件,则称F为最小依赖集: (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价 (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X...
  • 数据库系统概论——最小依赖集

    千次阅读 2020-05-20 22:09:19
    数据库系统概论——最小依赖集 文章目录数据库系统概论——最小依赖集1.求F={A->B,B->A,B->C,A->C,C->A}的最小依赖集(从左到右的顺序)2.求F={A->BC,ABD->CE,E->D}的最小依赖集(从左到右的...
  • 最小依赖集 (解法+例题)

    千次阅读 多人点赞 2020-12-01 14:36:25
    最小依赖集 (解法+例题) 网上看了很多最小依赖集的解法和例题,许多都存在错误,故自己参考总结写了一篇,如果有错误,感谢指正。 一、求最小依赖集的算法 ①根据推理规则的分解性,右部最小化 ②消除左边的冗余...
  • 数据库规范化:最小依赖集(函数极小化)

    千次阅读 多人点赞 2020-06-09 14:52:06
    什么是最小函数依赖集?...F的函数最小依赖集F{min}并不是唯一的,它与对各函数依赖FD{i}及X→A中X个属性的处置的顺序有关。 例题 1 (闭包如何求解请参考:数据库规范化:闭包求解) 例题2 例题3 ...
  • 最小依赖集、最小覆盖

    千次阅读 2019-12-25 21:46:45
    1、F中任一函数依赖的右边只有一个属性 2、F中不存在这样的函数依赖X---->A,使得F与F-{X---->A}等价 3、F中不存在这样的函数依赖X---->A,X有真子集Z,使得F与-{X---->A并上{Z---->A}与F等价。 看到...
  • 数据库关系模式中函数依赖的理论涉及不少算法,此次根据课程需要将求属性闭包(closure)和函数最小依赖集(basis)用代码实现。 思路 两个算法已有理论支撑,因此第一步是设计合适的数据结构,存储算法过程需要的...
  • 设R,F>,U={W,X,Y,Z,T,V},F={W->XY,XY->W,WZ->TV,XYZ->TV} (1)求F的最小依赖集。 (2)求R的所有候选码。 (3)根据函数依赖关系,确定R最高能到第几范式。
  • 数据库候选码和最小依赖集的求解

    千次阅读 2019-05-13 22:34:57
    数据库 函数依赖 属性 候选码 范式定义例子求候选码合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 最小依赖集 步骤: 1.先把FD的右边分解到只含有一个属性 2.对每个FD的左边求闭包不包含(所求的函数依赖),如果不包含右边,则保留,否则去掉 3.在第二部的前提下,对左边包含不止一个属性,对其真子集求闭包,...
  • 设U 是R 的属性集,F 是R 上成立的只涉及U 中属性的函数依赖集,函数依赖的推理规则有以下三条: 自反律:若属性集Y包含于属性集X,属性集X 包含于U,则X→Y 在R 上成立 增广律:若X→Y 在R 上成立,且属性集Z ...
  • 说明最小依赖集不唯一 */ 所以有 F2={BD→G,CD→A,CE→G,CDE→B,B→D} ③左边单一化,判断冗余,若冗余则代替 对于BD→G : { B→G,(B)+ =BD,闭包含属性D,所以D冗余 ; D→G, (D)+ = D, 闭包不含属性B,B不...
  • 2NF----满足1NF,并且非主键属性不能不分依赖于主键 e.g A B C D E 其中A和B为主键,如果A能单独决定C的属性,那么就不符合2NF. BTW:如果主键只有一个,那肯定2nf 3NF----满足2NF,人话就是 不存在这个关系:...
  • 数据库求最小函数依赖集

    万次阅读 多人点赞 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去除其中的冗余依赖...
  • 最小函数依赖集

    千次阅读 2009-05-28 09:07:00
    亦称为最小依赖集或最小覆盖。 1) F 中任一函数依赖的右部仅含有一个属性。 2) F 中不存在这样的函数依赖X →A ,使得F 与F-{X →A} 等价。 3) F 中不存在这样的函数依赖X →A ,X 有真子集Z 使得F-{X →A} ∪{Z-A} ...
  • 关系数据库理论之最小函数依赖集

    万次阅读 多人点赞 2019-04-06 23:38:53
    在本文中,会介绍为什么要引入最小函数依赖集最小函数依赖集是什么,以及如何求最小函数依赖集。 为什么需要最小函数依赖集 在关系数据模型中,一个关系通常由R(U,F)构成,U为属性的全集,F为函数依赖集。在实际...
  • 关于数据库的 最小函数依赖集的求法.对数据库的初学者有帮助。
  • 如果函数依赖集F满足下列条件,则称F为一个最小依赖集。 F中任意函数依赖的右部仅含有一个属性 F中不存在这样的函数依赖X→A,使得F与F- {X→A}等价,即F中的函数依赖均不能由F中其他函数依赖导出 F中不存在这样...
  • 数据库:最小函数依赖集

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 117,338
精华内容 46,935
关键字:

最小依赖集