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

    千次阅读 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可以删除...

    **

    设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可以删除一个,得到F={A->B,A->C,B->C,AB-C}

    展开全文
  • 关于数据库最小函数依赖集的求法.对数据库的初学者有帮助。
  • 数据库最小函数依赖集

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

    展开全文
  • 关系数据库理论之最小函数依赖集

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

    前言

    在本文中,会介绍为什么要引入最小函数依赖集,最小函数依赖集是什么,以及如何求最小函数依赖集。

    为什么需要最小函数依赖集

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

    闭包

    闭包分为两种,一种是函数依赖集F的闭包,另外一种是属性集X关于函数依赖集F的闭包。前者不做讨论,重点说说后者。先来看定义

    F为属性集U上的一组函数依赖集,XY ∈ \in U X F + X_F^+ XF+= {A|X → \rightarrow A能由F根据Armstrong公理导出}, X F + X_F^+ XF+称为属性集X关于函数依赖集F的闭包。

    说白了,就是给定属性集X,根据现有的函数依赖集,看其能推出什么属性。
    这里的Armstrong公理系统不用深究,想具体了解的可以点击查看百度百科。
    举例:

    已知关系模式R<U,F>,其中:
    U = {A,B,C,D,E},
    F = {AB → \rightarrow C,B → \rightarrow D,C → \rightarrow E,EC → \rightarrow B,AC → \rightarrow B}
    ( A B ) F + (AB)_F^+ (AB)F+

    解:

    从AB出发,此时我们的集合里已经包含了{A,B}。
    我们从现有的函数依赖集中可知,
    AB可以推出C,于是C加入集合,
    B可以推出D,于是D加入集合,
    C可以推出E,于是E加入集合,
    EC可以推出B,因为C、E、B都在集合中,于是不加入,
    AC可以推出B,因为A、B、C都在集合中,于是不加入
    至此,可求得 ( A B ) F + (AB)_F^+ (AB)F+ ={A、B、C、D、E}。

    最小函数依赖集

    定义

    如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集最小覆盖
    (1)、F中任一函数依赖右部仅含有一个属性。
    (2)、F中不存在这样的函数依赖 X → \rightarrow A,使得FF-{X → \rightarrow A} 等价。
    (3)、F中不存在这样的函数依赖X → \rightarrow AX有真子集Z使得F-{X → \rightarrow A} ⋃ \bigcup {Z → \rightarrow A}F等价。

    解释

    以上定义翻译成大白话就是,一个函数依赖集F要想称为最小函数依赖集,要满足以下三点:
    1、F中任一函数依赖的右边只有一个属性。
    2、F中不存在这样的函数依赖:从现有的函数依赖集中删除一个函数依赖X → \rightarrow A,删除后所得的函数依赖集与原来的函数依赖集等价,这样的函数依赖是不允许存在的。
    3、F中不存在这样的函数依赖:假设函数依赖集中存在AB → \rightarrow Y,现对该依赖的左部进行化简,即删除A,得B → \rightarrow Y;或删除B,得A → \rightarrow Y,若经过化简后的函数依赖集与没有化简前的函数依赖集等价,那么这样的函数依赖是不允许存在的。

    算法

    1、首先,先利用函数依赖的分解性,将函数依赖集中右部不为单个属性的分解为单属性。

    2、对于经过第1步筛选后的函数依赖集F中的每一个函数依赖X → \rightarrow A,进行以下操作:

    • 2.1、将X → \rightarrow A从函数依赖中剔除
    • 2.2、基于剔除后的函数依赖,计算属性X的闭包,看其是否包含了A,若是,则该函数依赖是多余的(这里体现出前面说的等价,因为如果基于化简后的函数依赖依赖,计算X的闭包依然包含A,则说明A可以由其他依赖推出,X → \rightarrow A不是必须的),可以删除,否则不能删除

    3、对于经过第2步筛选后的函数依赖集F中每个左部不为单个属性的函数依赖AB → \rightarrow Y,进行以下操作:
    我们约定,经过第二步筛选后的函数依赖集记为F1,经过第三步处理后的函数依赖集为F2。

    • 3.1、去除A,得B → \rightarrow Y,得F2,基于F1和F2计算属性B的闭包,如果二者相等,则说明它们是等价的,A可以去除;如果不相等,则A不能去除。
    • 3.2、去除B,得A → \rightarrow Y,得F2,基于F1和F2计算属性A的闭包,如果二者相等则说明它们是等价的,B可以去除;如果不相等,则B不能去除。

    知识链接:函数依赖的分解性
    若X → \rightarrow YZ,则X → \rightarrow Y 且 X → \rightarrow Z。

    举例

    关系模式R(U,F)中,U={A,B,C,D,E,G},F={B → \rightarrow D,DG → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B,ADG → \rightarrow BC};求F的最小函数依赖集。

    解:
    1、首先根据函数依赖的分解性,对F进行第一次筛选,需要变动的有:
    ADG → \rightarrow BC拆解成ADG → \rightarrow B、ADG → \rightarrow C
    得新函数依赖集:
    F = {B → \rightarrow D,DG → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B,ADG → \rightarrow B,ADG → \rightarrow C}

    2、筛选多余的函数依赖

    • 2.1:去除B → \rightarrow D,得F = {DG → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B,ADG → \rightarrow B,ADG → \rightarrow C}, B F + B_F^+ BF+ = {B},不包含D,故B → \rightarrow D不删除。
    • 2.2:去除DG → \rightarrow C,得F = {B → \rightarrow D、BD → \rightarrow E,AG → \rightarrow B,ADG → \rightarrow B,ADG → \rightarrow C}, ( D G ) F + (DG)_F^+ (DG)F+={D,G},不包含C,故DG → \rightarrow C不删除。
    • 2.3:去除BD → \rightarrow E,得F = {B → \rightarrow D,DG → \rightarrow C,AG → \rightarrow B,ADG → \rightarrow B,ADG → \rightarrow C}, ( B D ) F + (BD)_F^+ (BD)F+ = {B,D},不包含E,故BD → \rightarrow E不删除。
    • 2.4:去除AG → \rightarrow B,得F = {B → \rightarrow D,DG → \rightarrow C,BD → \rightarrow E,ADG → \rightarrow B,ADG → \rightarrow C}, ( A G ) F + (AG)_F^+ (AG)F+ = {A,G},不包含B,故AG → \rightarrow B不删除。
    • 2.5:去除ADG → \rightarrow B,得F = {B → \rightarrow D,DG → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B,ADG → \rightarrow C}, ( A D G ) F + (ADG)_F^+ (ADG)F+ = {A,D,G,C,B,E},包含B,故ADG → \rightarrow B去除
    • 2.6:去除ADG → \rightarrow C,得F = {B → \rightarrow D,DG → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B,ADG → \rightarrow B}, ( A D G ) F + (ADG)_F^+ (ADG)F+ = {A,D,G,C,B,E},包含C,故ADG → \rightarrow C去除
      经过第二部筛选后,函数依赖集F变为{B → \rightarrow D,DG → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B}。

    3、化简函数依赖左侧不为单个属性的函数依赖

    • 3.1:先看DG → \rightarrow C
      • 3.1.1:去除D,得G → \rightarrow C,得函数依赖集F1 = {B → \rightarrow D,G → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B}。
        基于F1,可求得 G F + G_F^+ GF+ = {G,C}。
        基于F(第二步求出的,下同),可求得 G F + G_F^+ GF+ = {G}
        可见二者并不相同,所以D不去除。
      • 3.1.2:去除G,得D → \rightarrow C,得函数依赖集F1 = {B → \rightarrow D,D → \rightarrow C,BD → \rightarrow E,AG → \rightarrow B}
        基于F1,可求得 D F + D_F^+ DF+ = {D,C}
        基于F,可求得 D F + D_F^+ DF+ ={D}
        可见二者并不相同,所以G不去除。

    综上,DG → \rightarrow C,已是最简。

    • 3.2:再看BD → \rightarrow E
      • 3.2.1:去除B,得D → \rightarrow E,得函数依赖集F1 = {B → \rightarrow D,DG → \rightarrow C,D → \rightarrow E,AG → \rightarrow B}
        基于F1,可求得 D F + D_F^+ DF+ = {D,E}
        基于F,可求得 D F + D_F^+ DF+ = {D}
        可见二者并不相同,所以B不去除。
      • 3.2.2:去除D,得B → \rightarrow E,得函数依赖集F1 = {B → \rightarrow D,DG → \rightarrow C,B → \rightarrow E,AG → \rightarrow B}
        基于F1,可求得 B F + B_F^+ BF+ = {B,E,D}
        基于F,可求得 B F + B_F^+ BF+ = {B,D,E}
        可见二者相同,所以D可以去除

    综上,BD → \rightarrow E,可化简为B → \rightarrow E。

    • 3.3:最后看AG → \rightarrow B
      • 3.3.1:去除A,得G → \rightarrow B,得函数依赖集F1 = {B → \rightarrow D,DG → \rightarrow C,B → \rightarrow E,G → \rightarrow B}
        基于F1,可求得 G F + G_F^+ GF+ = {G,B}
        基于F,可求得 G F + G_F^+ GF+ = {G}
        可见二者并不相同,所以A不可去除。
      • 3.3.2:去除G,得A → \rightarrow B,得函数依赖F1 = {B → \rightarrow D,DG → \rightarrow C,B → \rightarrow E,A → \rightarrow B}
        基于F1,可求得 A F + A_F^+ AF+ = {A,B}
        基于F,可求得 A F + A_F^+ AF+ = {A}
        可见二者并不相同,所以G不可去除。

    综上,AG → \rightarrow B,已是最简。
    综上,R的最小函数依赖集为F = {B → \rightarrow D,DG → \rightarrow C,B → \rightarrow E,AG → \rightarrow B}

    写在最后

    这个问题是我在考研复试的时候复习过程中遇到的,主要的纠结点在于第三步的判断上,查资料的时候发现网上很多都没有写清,最后还是在度娘的文库里找到了比较清楚的解释,在此做一下思路的整理。
    本文定义以及例子参考自:

    展开全文
  • 数据库最小函数依赖集(最小覆盖)

    千次阅读 多人点赞 2020-03-03 21:57:11
    这个英文流程反而清晰,主要过程如下: 1.设置G=F; 2.右边属性单一化(这个很容易理解,网上的教学第一步都是这个),即对属性集中每一个X->(A1…An),将其拆为 X->A1,X->A2…,X->An ...

    在这里插入图片描述在这里插入图片描述
    这个英文流程反而清晰,主要过程如下
    1.设置G=F;

    2.右边属性单一化(这个很容易理解,网上的教学第一步都是这个),即对属性集中每一个X->(A1…An),将其拆为 X->A1,X->A2…,X->An

    3.对每一个X->A,对X中的每一个属性B,计算去除B之后的X在G中的闭包,如果闭包包含A,那么就用去除B之后的X替换之前的X,注意此步实际上是两个for循环,而且此步仅需针对属性个数大于1的X就行了

    4.对每一个X->A,暂时将其去除得到N,在N中求X的闭包,如果闭包包含A,那么就从G中移除X->A

    还不懂??来到题你就懂了
    在这里插入图片描述
    在这里插入图片描述
    主要看步骤3,4。 3有解释,我来说一下4:E->D被移除了,来看看为什么被移除。
    首先去除E->D得到N={A->C,A->D,E->A,E->H},在N中求E的闭包为E,A,D,是包含D的,所以E->D被移除。剩余的为什么没去除?自己按这个流程操作就知道了

    什么?闭包怎么求?

    说通俗一点:闭包就是由一个属性直接或间接推导出的所有属性的集合。

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

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

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

    万次阅读 多人点赞 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, ...
  • 如果函数依赖集F满足下列3个条件,则称F为最小依赖集: (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价 (3)F中不存在这样的函数依赖X→A,X有真子集Z使得F-{X...
  • 一、函数依赖:在关系R中,若属性或者属性 A 中 两个元祖的值相等,如果这两个元祖中对应的属性或者属性B中的值也相同,则记作A——&gt;B。 A函数决定B; 或者 B函数依赖于A。例1:下表就是问题领域, 则存在...
  • 根据已知条件和推理规则,可知F+有43个函数依赖。各种情况如下: 答:F的闭包F+有43个;(AB)的闭包(AB)+ =ABC 设关系R(ABCDE)上FD为F,并且F={A→BC,CD→E,B→D,E→A}。求出R的所有候选键。 解:A+=ABCDE ...
  • 例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中...
  • ,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满足下列条件,则称F为一个极小函数依赖集,亦称为最小依赖集或最小覆盖(minimal cover)。 (1)F中任一函数依赖的右部仅含有一个属性 (2)F中不存在这样的函数依赖X->A,使得F与F-{X->A}...
  • (1)求F的最小函数依赖集F’。 (2)求关系R的候选码。 (3)求具有无损连接且保持函数依赖性的3NF分解。 答: (1) ①:将函数依赖右边全变为单属性: F = {A→D, A→B, E→D, D→B,BC →D, DC →A}。 ②:检查每...
  • 最小依赖集 (解法+例题)

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

    千次阅读 多人点赞 2020-06-09 14:52:06
    什么是最小函数依赖集? 如何计算最小函数依赖集? 算法步骤 (1)将F中的所有函数依赖的右边化为单一属性; (2)去掉F中的所有函数依赖左边的冗余属性; (3)去掉F中所有冗余的函数依赖。 F的函数最小依赖集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)+...
  • ```mermaid graph TD; A-->B; B-->C;
  • 数据库系统原理课件:作业讲评 计算最小函数依赖集.ppt
  • 数据库求闭包,求最小函数依赖集,求候选码,判断模式分解是否为无损连接,3NF,BCNF1.说白话一点:闭包就是由一个属性直接或间接推导出的所有属性的集合。 例(1): 设有关系模式R(U,F),其中U={A,B,C,D,E...
  • 最小函数依赖/最小覆盖Fm的方法之一: 1、把右部分化为单属性 2、去掉左部分的冗余属性 例如XY→A,假设Y是多余的,看A是否属于(X)+,若是,则Y是多余属性,可以去掉。 3、去掉冗余的函数依赖 从第一个函数依赖X→...
  • 数据库 函数依赖

    2020-05-03 18:21:45
    用处:指导关系模型的设计,规范...函数依赖(FD) 单值映射 码是一种特殊的FD: 比如超码:可以唯一标识一个元组(SK -> R) 候选码(最小超码):CK -> R 且 不存在CK的子集可以 -> R FD的作用:可以检测...
  • 最小函数依赖集定义: 如果函数依赖集F满足下列条件,则称F为最小函数依赖集或最小覆盖。 ① F中的任何一个函数依赖的右部仅含有一个属性; ② F中不存在这样一个函数依赖X→A,使得F与F-{X→A}等价; ③ F中不存在...
  • 数据库系统概论——最小依赖集

    千次阅读 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}的最小依赖集(从左到右的...
  • 目录数据库系统原理-函数依赖和关系模式分解第一范式如何处理非原子值原子性关系数据库设计中易犯的错误模式分解无损连接分解优化关系模式的步骤函数依赖函数依赖定义函数依赖的使用函数依赖集的闭包Armstrong公理...
  • 最小函数依赖

    千次阅读 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中的函数依赖运用分解原则来创建一个等价函数依赖...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,036
精华内容 28,014
关键字:

数据库最小函数依赖集