精华内容
下载资源
问答
  • 最小等价依赖集

    2021-10-15 22:56:18
    最小等价依赖(最小覆盖) 证明兼算法: 例题:https://blog.csdn.net/Wonz5130/article/details/80465245

    最小等价依赖(最小覆盖)

    证明兼算法:

    例题:https://blog.csdn.net/Wonz5130/article/details/80465245

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

    万次阅读 多人点赞 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}

     

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

    千次阅读 多人点赞 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}。

              

     

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

     

     

     

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

    2018-01-17 19:30:00
    SQLServer中最小函数依赖集 来源: 程序员之家 编辑:sevenleaf 2010-04-16 09:55 评论:0 条 今天小编要和大家分享的是SQLServer中的最小函数依赖集,假设S 1和S 2是两个函数依赖集,如果所有为S 1所蕴涵...

    SQLServer中最小函数依赖集

    来源: 程序员之家 编辑:sevenleaf 2010-04-16 09:55 评论:0

     
     

          今天小编要和大家分享的是SQLServer中的最小函数依赖集,假设S 1和S 2是两个函数依赖集,如果所有为S 1所蕴涵的函数依赖都为S 2所蕴涵,—即S 1+是S 2+的子集,则S 2是S 1的覆盖,D B M S只要实现了S 2中的函数依赖,就自动实现S 1中的函数依赖。
          如果S 2是S 1的覆盖,同时S 1是S 2的覆盖—则S 1和S 2等价,即S 1+=S 2+。很显然,如果S 1和S 2等价,则D B M S只要实现S 1中的函数依赖,就自动实现S 2中的函数依赖,反之亦然。
          当且仅当函数依赖集满足以下条件时,该函数依赖集为最小函数依赖集:
          1) 每个函数依赖的右边(应变量)只含有一个属性(即它是单元素集合)。
          2) 每个函数依赖的左边(自变量)是不可约的—删除自变量的任何一个属性都将改变闭包S+(即会使S转变为一个不等价于原来的S的集合)。这种函数依赖被称为左部不可约的函数依赖。
          3) 删除S中任何一个函数依赖都将改变它的闭包S+,即使S转变为一个不等价于原来的S的集合。
          关于第2点和第3点,在这里要指出的是,为了知道如果删除某些元素是否会改变闭包,不必要清楚地知道闭包的内容。例如:观察大家熟悉的零件关系变量P,有下列函数依赖:
          P #→P N A M E
          P #→C O L O R
          P #→W E I G H T
          P #→C I T Y
          显而易见,该函数依赖集是最小依赖集:每个函数依赖中右边只含有一个属性,同样,左边也是不可约的,且任何一个函数依赖都不能被删除而不改变闭包(即不丢失信息)。相反,下面的函数依赖集不是最小依赖集。
          1 ) P #→{ P N A M E,COLOR} :第一个函数依赖的右边不是单属性集
          P #→W E I G H T
          P #→C I T Y
          2 ) { P #,P N A M E }→COLOR :第一个函数依赖左边的P N A M E可以删除而不改变闭包(即左边是可约的)
          P #→PNAME 
          P #→W E I G H T
          P #→C I T Y
          3 ) P #→P# : 第一个函数可以删除而不改变闭包
          P #→P N A M E
          P #→C O L O R
          P #→W E I G H T
          P #→C I T Y
          任何一个函数依赖集至少存在一个最小函数依赖集。假设函数依赖集为S,根据分解规则,可以假定每个函数依赖的右边是单属性的而不会失去它的一般性(如果右边不是单属性的,则可以利用分解规则把它分解成单属性),接着考察每个函数依赖f左边的每一个属性A,如果把A从f的左边删除而并不改变闭包,则把A从f的左边删除,然后考察S中剩余的每一个函数依赖f,如果把f删除而不改变闭包,则把f从S中删除,最后所得的集合S是和原来的函数依赖集S等价的最小函数依赖集。
          例:假设给定关系变量R、A、B、C、D是R的属性集,R满足函数依赖:
          A→B C
          B→C
          A→B
          A B→C
          A C→D
          现在计算该函数依赖的最小函数依赖集。
          1) 把所有的函数依赖写成右边是单属性的函数依赖:
          A→B
          A→C
          B→C
          A→B
          A B→C
          A C→D
          很显然,函数依赖A→B出现了两次,可以删除其中的一次。
          2) 可以把C从函数依赖A C→D的左边删除,因为A→C,根据增广律可以得出A→A C,给定A C→D,根据传递律可以得出A→D。所以C在函数依赖A C→D的左边是冗余的。
          3) 接着发现可以删除函数依赖A B→C,因为A→C,根据增广律可得A B→C B,又根据分解规则可以导出A B→C。
          4) 函数依赖A→C由函数依赖A→B和B→C蕴涵,所以它可以删除。最后剩下下列函数依赖:
          A→B
          B→C
          A→D
          该集合是不可约。
          一个函数依赖集I是不可约的,且等价于某个函数依赖集S,则说I是S的最小等价依赖集。
          这样,如果要实现一个函数依赖集S,系统只要实现它的一个最小依赖集就足够了(重复一次:要计算最小依赖集I不必计算闭包S+)。应该清楚的是给定函数依赖集的最小依赖集并不一定是唯一的。

    转载:http://edu.qudong.com/2010/0416/67217.shtml

    转载于:https://www.cnblogs.com/NewPigJack/p/8305113.html

    展开全文
  • 最小函数依赖集Fm的定义,求法以及举例定义求法举例 定义 如果函数依赖集F满足以下三个条件,则称F为最小函数依赖集,记作Fm。 ①F中每个函数依赖的右部都是单属性,即右部最...输出:F的一个等价最小函数依赖集Fm。
  • 关系规范化之求最小函数依赖集最小覆盖)

    万次阅读 多人点赞 2016-04-25 10:02:53
    最小函数依赖集 一、等价和覆盖  定义:关系模式R上的两个依赖集F和G,如果F+=G+,则称F和G是等价的,记做F≡G。若F≡G,则称G是F的一个覆盖,反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。   二、...
  • 数据库求最小函数依赖集

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

    万次阅读 多人点赞 2019-04-06 23:38:53
    在本文中,会介绍为什么要引入最小函数依赖集最小函数依赖集是什么,以及如何求最小函数依赖集。 为什么需要最小函数依赖集 在关系数据模型中,一个关系通常由R(U,F)构成,U为属性的全集,F为函数依赖集。在实际...
  • 一个是最小依赖函数,一个是求候选码,一个是求闭包,一个是要把关系模式分解成3NF且保持函数依赖,一个是分解成3NF且保持函数依赖和无损连接。 记录一下我对这几个问题的求法。可能会有哪里有漏洞,希望可以指...
  • 最小函数依赖集的方法

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

    2015-05-05 15:13:35
     输出 F的一个等价最小函数依赖集G  步骤:① 用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;  ② 去掉多余的函数依赖:从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的函数依赖中求X的...
  • 如果函数依赖集F满足下列3个条件,则称F为最小依赖集: (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价 (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X...
  • 最小依赖集 (解法+例题)

    千次阅读 多人点赞 2020-12-01 14:36:25
    最小依赖集 (解法+例题) 网上看了很多最小依赖集的解法和例题,许多都存在错误,故自己参考总结写了一篇,如果有错误,感谢指正。 一、求最小依赖集的算法 ①根据推理规则的分解性,右部最小化 ②消除左边的冗余...
  • 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集最小覆盖(minimal cover)。 (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X->A,使得F与F-{X->A}...
  • 最小函数依赖集的求解 一、定义  最小函数依赖集也称为极小函数依赖集最小覆盖;如果函数依赖集F满足下列条件,则称F为一个最小依赖集。 F中任意函数依赖的右部仅含有一个属性 F中不存在这样的函数依赖X→A...
  • 最小函数依赖集

    万次阅读 多人点赞 2018-09-19 11:33:57
    去掉多余的函数依赖:从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的函数依赖中求X的闭包X(  [Y1]闭包就是由一个属性直接或间接推导出的所有属性的集合,例如: f={a-&gt;b,b-&gt;c,a-&gt;d...
  • 最小函数依赖集 关系模式R(U,D,DOM,F) R:关系名,符号化的元组定义 U:一组属性 D:属性组U中的属性所来自的域 DOM:属性到域的映射 F:属性组U上的一组数据依赖 函数依赖集的闭包 F:FD(Functional ...
  • 最小依赖集最小覆盖

    千次阅读 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等价。 看到...
  • 求F={ABD→AC,C→BE,AD→BF,B→E}的最小函数依赖集Fm 注意:当在函数依赖已经改变的地方开始一个新步骤时,重写函数依赖集很重要,这样可以在下一步中方便引用。 第一步 对F中的函数依赖运用分解原则来创建一个...
  • 一、函数依赖:在关系R中,若属性或者属性 A 中 两个元祖的值相等,如果这两个元祖中对应的属性或者属性B中的值也相同,则记作A——&gt;B。 A函数决定B; 或者 B函数依赖于A。例1:下表就是问题领域, 则存在...
  • 最小函数依赖求解

    2021-06-07 19:05:16
    最小函数依赖集  定义:如果函数依赖集F满足下列条件,则称F为最小函数依赖集 或... 输出 F的一个等价最小函数依赖集G  步骤:① 用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性;  ② 去掉多余的
  • 假设S 1和S 2是两个函数依赖集,如果所有为S 1所蕴涵的函数依赖都为S 2所蕴涵,—即S 1+是S 2+的子集,则S 2是S 1的覆盖,D B M S只要实现了S 2中的函数依赖,就自动实现S 1中的函数依赖。 如果S 2是S 1的覆盖,...
  • 如果函数依赖集F满足下列条件,则称F为最小函数依赖集最小覆盖。 ① F中的任何一个函数依赖的右部仅含有一个属性; ② F中不存在这样一个函数依赖X→A,使得F与F-{X→A}等价; ③ F中不存在这样一个函数依赖X→A,...
  • 定义:如果函数依赖集F满足下列条件,则称F为最小函数依赖集最小覆盖。 ① F中的任何一个函数依赖的右部仅含有一个属性; ②F中不存在这样一个函数依赖X→A,使得F与F-fX→AJ等价; ③F中不存在这样一个函数依赖X...
  • 最小函数依赖

    千次阅读 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中的函数依赖运用分解原则来创建一个等价函数依赖...
  • 不含部分依赖,像F{AB—>C,A—>C}就不是最小函数依赖集 已知关系模式R(U,F),其中U={A,B,C},F是这样的关系集合{A—>BC,B—>C,AB—>C,A—>B} 求该模式的最小函数依赖集。 答案:F={B—>C,A—>B},A—...
  • 例7设关系模式R(A,B,C,D),函数依赖集F={A->C,C->A,B->AC,D->AC,BD->A}.求F的最小函数依赖. ①将F中的函数依赖都分解为右部为单属性的函数依赖.F={A→C,C→A,B→A,B→C,D→A,D→C,BD→A} ②去掉F中...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,222
精华内容 13,288
关键字:

最小等价依赖集