【数据库】极小函数依赖集最小依赖集最小覆盖 定义+求解方法+实例

    xiaoxiao2022-07-05  184

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


    一、定义

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

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

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

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

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

    二、分析(求解方法)

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

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

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

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

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

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

    三、实例

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

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

    解答:

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

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

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

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

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

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

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

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

     

    最新回复(0)