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

    千次阅读 多人点赞 2020-12-01 14:36:25
    最小依赖 (解法+例题) 网上看了很多最小依赖的解法和例题,许多都存在错误,故自己参考总结写了一篇,如果有错误,感谢指正。 一、求最小依赖的算法 ...(2)规则最小化:除本求包(对每个函数依赖的左部做除

    最小依赖集 (解法+例题)

    网上看了很多最小依赖集的解法和例题,许多都存在错误,故自己参考总结写了一篇,如果有错误,感谢指正。

    一、求最小依赖集的算法

    ①根据推理规则的分解性,右部最小化

    ②消除左边的冗余属性

    ③消除冗余的FD(依赖)

    重点:操作步骤的顺序不能颠倒,颠倒了可能消除不了FD中左边冗余的属性,或冗余的依赖。

    二、具体操作详解(以下两种意思相同,表述略有区别罢了)

    (1)右部最小化:右切,使每个函数依赖的右部仅有一个属性
    (2)规则最小化:除本求包(对每个函数依赖的左部做除本求包,求包的结果如果不包含本函数依赖的右部,本函数依赖保留;求包的结果如果包含了本函数依赖的右部,删除本函数依赖)
    (3)左部最小化

    注意,解题一定要先(3)后(2)

    三、例题,反例等

    反例,假如将②③步骤颠倒

    例:求**F={ABD→AC,C→BE,AD→BF,B→E}**的最小函数依赖集 F m F_m Fm

    注意:当在函数依赖已经改变的地方开始一个新步骤时,重写函数依赖集很重要,这样可以在下一步中方便引用。

    第一步 对F中的函数依赖运用分解原则来创建一个等价函数依赖集H,该集合中每一个函数依赖的右部是单个属性:

    H={①ABD→A,②ABD→C,③C→B,④C→E,⑤AD→B,⑥AD→F,⑦B→E}

    第二步 考察每一个函数依赖是否是必须的,去除非必要的函数依赖

    (1)ABD→A是平凡的函数依赖(就是A是ABD的子集,所以他是平凡的依赖),所以显然是非必要的函数依赖,因此去除。保留在H中的函数依赖是H={②ABD→C,③C→B,④C→E,⑤AD→B,⑥AD→F,⑦B→E}

    (2)考察ABD→C,去掉此函数依赖将会得到新的函数依赖集J={③C→B,④C→E,⑤AD→B,⑥AD→F,⑦B→E}。如果ABD→C是非必要的,则 ( A B D ) J + (ABD)_J^+ (ABD)J+=ABDFE,不包含C,因此ABD→C是必要的函数依赖,不能去掉。

    H={②ABD→C,③C→B,④C→E,⑤AD→B,⑥AD→F,⑦B→E}

    (3)考察C→BJ={②ABD→C,④C→E,⑤AD→B,⑥AD→F,⑦B→E},则** C J + C_J^+ CJ+=CE**,不包含B,因此C→B是必要的函数依赖,保留在H中。

    (4)考察C→EJ={②ABD→C,③C→B,⑤AD→B,⑥AD→F,⑦B→E},则 C J + C_J^+ CJ+=CBE,包含E,因此是不必要的,去除后得到的函数依赖集为H={②ABD→C,③C→B,⑤AD→B,⑥AD→F,⑦B→E}

    (5)同理考察函数依赖⑤、⑥和⑦,最后得到的函数依赖集为H={②ABD→C,③C→B,⑤AD→B,⑥AD→F,⑦B→E}。为了第三步方便引用,我们进行重新编号:

    H={①ABD→C,②C→B,③AD→B,④ AD→F,⑤ B→E}。

    第三步 考察每一个左部为多个属性的函数依赖,看左部的每个属性是否是必须的,能否用更小的属性集替代原有的属性集。

    首先从函数依赖①ABD→C开始。

    (1)去除A?

    如果A可以去除,那么可得到新的函数依赖集J={①BD→C,②C→B,③AD→B,④ AD→F,⑤ B→E}。去掉A后BD在J上的闭包将比在H下函数决定更多的属性,如果 ( B D ) J + (BD)_J^+ (BD)J+= ( B D ) H + (BD)_H^+ (BD)H+或者C∈ ( B D ) H + (BD)_H^+ (BD)H+,则说明去掉A得到的函数依赖集和原有的函数依赖集是等价的,可以用BD→C替换ABD→C。

    ( B D ) H + (BD)_H^+ (BD)H+=BDE,不包含C,所以A不能去掉。

    (2)去掉B?

    J={①AD→C,②C→B,③AD→B,④ AD→F,⑤ B→E} 。

    ( A D ) H + (AD)_H^+ (AD)H+=ADBC,包含了B,因此B→C是冗余的函数依赖,所以去除

    (3)去掉D?J={①A→C,②C→B,③AD→B,④ AD→F,⑤ B→E}。

    因为H的函数依赖集在第三步发生了改变,因此我们需要回到第二步。如果顺序颠倒,则在消除左部冗余使F发生变化后,需要重新进行消除函数依赖的操作

    此时H={①AD→C,②C→B,③AD→B,④ AD→F,⑤ B→E}。

    在进行第二步即重新进行消除函数依赖操作

    其中考察到③,有 ( A D ) H + (AD)_H^+ (AD)H+=ADCB,包含B,因此AD→B是不必要的函数依赖,所以去除

    最后

    得到的函数依赖集为H={AD→C, C→B, AD→F, B→E}


    例题:已知关系模式R(U,F),U={A,B,C,D,E,F,G},F={BCD→A,BC→E,A→F,F→G,C→D,A→G},求F的最小函数依赖集。

    原参考省略了左部最小化的步骤,现我将其补上,仅供参考

    ③左部最小化

    经过右部最小化和消除冗余依赖后F={BCD→A,BC→E,A→F,F→G,C→D}

    针对BCD→A

    1. 去B? 则 ( C D ) F + (CD)_F^+ (CD)F+=CD,无A,保留
    2. 去C? 则 ( B D ) F + = B D (BD)_F^+=BD (BD)F+=BD,无A,保留
    3. 去D? 则 ( B C ) F + = B C D A E F G (BC)_F^+=BCDAEFG (BC)F+=BCDAEFG,有A,则D冗余,可以去掉。

    所以F={BC→A,BC→E,A→F,F→G,C→D}

    针对BC→E

    1. 去B 则 C F + C_F^+ CF+=CD,保留
    2. 去C 则 B F + B_F^+ BF+=B,保留

    所以F={BC→A,BC→E,A→F,F→G,C→D}

    但是

    由于操作顺序颠倒,还需要进行冗余依赖的判断,判断后发现现在依赖保持不变。

    所以F={BC→A,BC→E,A→F,F→G,C→D}


    四、其他例题

    例题一

    例题二

    例题(注意:本题由于顺序错误,导致了错误,纸质的部分进行了修改,但还是放出来以便大家更好的理解)

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

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

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

    展开全文
  • 根据已知条件和推理规则,可知F+有43个函数依赖。各种情况如下: 答:F的闭包F+有43个;(AB)的闭包(AB)+ =ABC 设关系R(ABCDE)上FD为F,并且F={A→BC,CD→E,B→D,E→A}。求出R的所有候选键。 解:A+=ABCDE ...

    闭包

    1. 已知关系模式R(A,B,C),F是R上成立的FD集,F={A→B,B→C}, F的闭包F+有多少个?试写出(AB)+的所有闭包。

      根据已知条件和推理规则,可知F+有43个函数依赖。各种情况如下:
      函数依赖
      答:F的闭包F+有43个;(AB)的闭包(AB)+ =ABC

    2. 设关系R(ABCDE)上FD集为F,并且F={A→BC,CD→E,B→D,E→A}。求出R的所有候选键。
      :A+=ABCDE B+=BD C+=C D+=D E+=EABCD 候选码有A、E。
             对剩下的B 、C、D进行组合:
             可以求出:BC+=ABCDE BD+=BD CD+=ABCDE
             BC、CD也为候选码
             所以R的候选键有四个:A、E、BC和CD。

    3. R<U,F>,
      U={A,B,C,D,E,G}
      F{AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}
      X=BD,求X+,并判断BD->A是否成立?

      因为X=BD 所以X+=(BD)+;
      因为D→EG
      所以BD→BDEG
      因为BE→C
      所以BD→BCDEG
      因为C→A
      所以BD→ABCDEG
      所以(BD)+=ABCDEG
      所以 X+=ABCDEG
      因为(BD)+=ABCDEG,A属于(BD)+
      所以BD->A是成立的。

    范式

    1. 给定一个学校的学生选课系统,为了方便起见,我们只确定了以下需要的内容:
      R(学号、学生姓名、年龄、性别、课程名称、课程学分、系别、学科成绩、系办地址、系办电话)
      首先判断它是几范式?如何把它规范化成3NF?

      范式首先要找主码:(学号,课程名称)
      学号单独决定学生姓名,所以学生姓名就是部分函数依赖于主码
      所以R是1NF(第一范式)
      拆成2NF(消除部分函数依赖)
      R1(学号、学生姓名、年龄、性别、系别、系办地址、系办电话)
      R2(学号、课程名称、课程学分、学科成绩)
      在R1中,存在学号→系别→系办地址,传递函数依赖(非第三范式)
      拆成3NF(消除传递函数依赖):
      R11(学号、学生姓名、年龄、性别、系别)
      R12(系别、系办地址、系办电话)
      R2(学号、课程名称、课程学分、学科成绩)

    求最小函数依赖集

    1. 给定关系模式R(A,B,C) F={A->BC,B->AC,C->A} 求F的最小函数依赖集。

      (1)将F中的函数依赖进行拆分:
      F={A->B,A->C,B->A,B->C,C->A}
      (2)假设A->B冗余(去掉A->B)
      剩下:F={A->C,B->A,B->C,C->A}
      A+=AC
      但是B不属于AC,也就是不属于A的闭包,留下
      (3)假设A->C冗余
      剩下:F={A->B,B->A,B->C,C->A}
      A+=ABC
      C属于A的闭包,所以删除
      (4)删除后F={A->B,B->A,B->C,C->A}
      假设B->A冗余
      F={A->B,B->C,C->A}
      B+=ABC 删除
      (5)删除后F={A->B,B->C,C->A}
      假设B->C冗余
      F={A->B,C->A}
      B+=B 留下
      (6)假设C->A冗余
      F={A->B,B->C}
      C+=C A不属于C的闭包 留下
      所以F的最小函数依赖集为:{A->B,B->C,C->A}
    展开全文
  • 如果函数依赖集F满足下列3个条件,则称F为最小依赖: (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价 (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X...

    一、定义:
    如果函数依赖集F满足下列3个条件,则称F为最小依赖集:
    (1)F中任一函数依赖的右部仅含有一个属性
    (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价
    (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价
    二、步骤:
    (1)右部最小化:右切,使每个函数依赖的右部仅有一个属性
    (2)规则最小化:除本求包(对每个函数依赖的左部做除本求包,求包的结果如果不包含本函数依赖的右部,本函数依赖保留;求包的结果如果包含了本函数依赖的右部,删除本函数依赖)
    (3)左部最小化
    三、例题:已知关系模式R(U,F),U={A,B,C,D,E,F,G},F={BCD→A,BC→E,A→F,F→G,C→D,A→G},求F的最小函数依赖集。
    在这里插入图片描述
    四、例题:设F={C→A,CG→D,CG→B,CE→A,ACD→B},求最小函数依赖集
    在这里插入图片描述

    展开全文
  • (1)求F的最小函数依赖集F’。 (2)求关系R的候选码。 (3)求具有无损连接且保持函数依赖性的3NF分解。 答: (1) ①:将函数依赖右边全变为单属性: F = {A→D, A→B, E→D, D→B,BC →D, DC →A}。 ②:检查每...
  • 求F={ABD→AC,C→BE,AD→BF,B→E}的最小函数依赖集Fm 注意:当在函数依赖已经改变的地方开始一个新步骤时,重写函数依赖很重要,这样可以在下一步中方便引用。 第一步 对F中的函数依赖运用分解原则来创建一个...
  • 最小函数依赖集的求解过程

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

    千次阅读 多人点赞 2020-03-03 21:57:11
    这个英文流程反而清晰,主要过程如下: 1.设置G=F; 2.右边属性单一化(这个很容易理解,网上的教学第一步都是这个),即对属性集中每一个X->(A1…An),将其拆为 X->A1,X->A2…,X->An ...
  • 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖最小覆盖(minimal cover)。 (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X->A,使得F与F-{X->A}...
  • 最小函数依赖例题

    千次阅读 2005-05-27 10:46:00
    最小函数依赖例题(1) AB----->C (2) C---->A (3) BC----->D (4) ACD----->B (5) BE----->C(6) CE----->A (7) CE----->F (8) CF----->B (9) CF----->D (10) D----->E (11) D----->F求最小函数依赖(2)蕴涵...
  • ,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中左边可能出现冗余属性,...
  • 最小函数依赖集分三步:、判别一个分解的无损连接性、转换为3NF既具有无损连接性又保持函数依赖的分解算法(有详细例子)数据库原理必考
  • 数据库规范化:最小依赖集函数极小化)

    千次阅读 多人点赞 2020-06-09 14:52:06
    什么是最小函数依赖集? 如何计算最小函数依赖集? 算法步骤 (1)将F中的所有函数依赖的右边化为单一属性; (2)去掉F中的所有函数依赖左边的冗余属性; (3)去掉F中所有冗余的函数依赖。 F的函数最小依赖F{...
  • 主码求法,范式判断,最小函数依赖求法

    千次阅读 多人点赞 2019-05-08 18:45:21
    数据库中主码求法,NF判断,最小函数依赖
  • 数据库复习——最小依赖的求解 博主学校所使用的教材是由斯坦福大学的知名计算机科学家Jeffrey D. Ullman和Jennifer Widom所著的...(1)将题干所给的函数依赖右部都拆成单属性(例如A→BC拆成A→B和A→C),得到的
  • 怎样判断一个函数依赖集属于第几范式

    千次阅读 多人点赞 2019-05-25 16:40:52
    判断一个函数依赖集属于第几范式—— 首先,要懂得以下几条概念: 1.完全函数依赖: 如果X→Y,且对于任意一个X的子集X’,都有X’↛ Y,则称Y完全函数依赖于X 2.部分函数依赖:Y不完全函数依赖于X 总之,如果一...
  • 规范化理论:如何计算最小依赖集

    千次阅读 多人点赞 2019-05-14 21:31:49
    什么是最小依赖? 如果函数依赖集F满足一下条件,则称F为一个...(3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X→A}{Z→A}与F等价,即F中各函数依赖左部均为最小属性(不存在冗余属性)。 如何计...
  • 1.求闭包 推理规则推导 2. 求最小依赖 具体步骤 1.右边单一化 2.除去自身求闭包 3.左部最小化 练习1: ...3.无损分解及保持函数依赖 无损分解两个方法: 1.表格法 2.适用于分解为2个ρ ...
  • 最小依赖集

    万次阅读 多人点赞 2018-05-26 23:58:45
    这个比较烦,要写好多好多好多...D},求F最小依赖集。解:第一步:右边单一化。F1={BG-&gt;C,BD-&gt;E,DG-&gt;C,ADG-&gt;B,ADG-&gt;C,AG-&gt;B,B-&gt;D}第二步:逐个求,在去掉它的F中...
  • 数据库——如何求出最小依赖集 如何求出候选码
  • 给定函数依赖集合F={ A2→(A3,A5); (A1, A3)→A6; (A2,A6)→ A4 },则关于R既保持 依赖又无损连接地分解成第三范式,分解正确 的是 A.p={R1(A2,A3, A5), R2(A1,A3,A6), R3(A2,A4,A6) } B.p={R1(A2,A3, A5), R2(A1...
  • 文章目录什么是函数依赖部分函数依赖与完全函数依赖传递函数依赖函数依赖相关的几个重要概念关于函数依赖的 Armstrong 公理Armstrong 公理Armstrong 公理对应的引理什么是属性()闭包属性闭包的计算算法与覆盖...
  • 【数据库复习】函数依赖

    千次阅读 2018-11-10 10:58:05
    【数据库复习】函数依赖
  • ,其中U属性,F为属性上的函数依赖,将其分解成3NF并保持函数依赖算法如下: ①求F最小依赖F‘;极小依赖算法参考地址: ②将既不在左部,又不在右部的属性,构成一个独立的一个关系模式; ③若有唯一依赖X
  • 求(1)F的最小函数依赖集: ①右边单一化 F1={BE→G,BD→G,CD→A,CE→G, CDE→A,CDE→B ,BC→A,B→D} ②分别求F1中各函数依赖的闭包 对BE→G,(BE)+ = BDEG,闭包含有右边属性G,去掉该函数依赖 …… /*如果...
  • 判断分解的无损连接性和保持函数依赖

    千次阅读 多人点赞 2019-06-29 21:36:41
    对于属性ABCDEF和函数依赖集 {A→BC,CD→E,B→D,BE→F,EF→A} ,说明下列分解a.是否是无损连接分解;b.是否保持函数依赖。 (1) {ABCD,EFA} a.判断无损连接分解 U1∩U2=A, U1-U2=BCD, U2-U1=EF 存在A→...
  • 例题:设关系模式R(U, F),其中R上的属性U={A, B, C, D, E},R上的函数依赖集F={A→B,DE→B,CB→E,E→A,B→D}。( )为关系R的候选关键字。分解( )是无损连接,并保持函数依赖的。 问题一: A: AB B...
  • (13)函数依赖的推理规则(armstrong公理)

    千次阅读 多人点赞 2019-06-28 17:33:49
    6.函数依赖集的规范覆盖 问题引入: ①除了给定的函数依赖,我们需要考虑模式上成立的所有函数依赖? ② 给定一组函数依赖,是否能导出另外一些函数依赖,或另外的函数依赖是否成立。 如FD={A ->B,B ->...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,628
精华内容 1,051
关键字:

最小函数依赖集例题