最小函数依赖集的求解

nibiru 2020年03月04日 141次浏览

一、定义

  最小函数依赖集也称为极小函数依赖集、最小覆盖;如果函数依赖集 F 满足下列条件,则称 F 为一个最小依赖集。

1.F 中任意函数依赖的右部仅含有一个属性
2.F 中不存在这样的函数依赖X→A,使得 F 与 F - {X→A}等价,即 F 中的函数依赖均不能由 F 中其他函数依赖导出
3.F 中不存在这样的函数依赖X→A,X有真子集 Z 使得 F - {X→A} ∪ {Z→A}与 F 等价,即 F 中各函数依赖左部均为最小属性集(不存在冗余属性)

二、算法步骤:

1.将 F 中的所有函数依赖的右边化为单一属性
2.去掉 F 中的所有函数依赖左边的冗余属性(只针对F中左部不是单一属性的函数依赖)
3.去掉 F 中的所有冗余的函数依赖

三、例子说明

假设R<U , F> ,U = ABCD,函数依赖集F={A→BD,AB→C,C→D},求:F 最小函数依赖集

  • 第一步:将F中的所有函数依赖的右边化为单一属性:

因为F = {A→BD,AB→C,C→D},函数依赖右边化为单一属性得:F = {A→B,A→D,AB→C,C→D};

  • 第二步:去掉F中的所有函数依赖左边的冗余属性(只针对F中左部不是单一属性的函数依赖)

   F={A→B,A→D,AB→C,C→D}中只有函数依赖AB→C左部不是单一属性,所以要对其进行去掉左边冗余属性的处理:
先看A是不是冗余属性:因为BF+ =
不包含A,所以A属性不冗余

这里应该注意的是,要看哪一个属性是否是冗余属性,则求该函数依赖左部除要查看的属性外的其他属性的集关于 F 的闭包是否包含要查看属性,再看B是不是冗余属性:因为AF+ ={A,B,C,D} 包含的B,所以B属性冗余因此只将函数依赖AB→C左部B属性去掉,所以F={A→B,A→D,A→C,C→D}。

  • 第三步:去掉 F 中的所有冗余的函数依赖

依据引理:设F为属性集U上的一组函数依赖,X,Y ⊆ U,X→Y 能由 F 根据Armstrong公理导出的充分必要条件是Y⊆ XF+ 。即判断 F 中一个函数依赖X→Y是否冗余,则只需要判定 Y 是否为的XF+ 子集。

因为有F={A→B,A→D,A→C,C→D}:

先看判断函数依赖A→D是否冗余,则把函数依赖A→D从F={A→B,A→D,A→C,C→D}中去掉后得F={A→B,A→C,C→D},求得AF+ = { A,B,C,D} 包含了D,所以为函数依赖A→D冗余,所以应该从F={A→B,A→D,A→C,C→D}中去掉函数依赖A→D,得F={A→B,A→C,C→D},再从F={A→B,A→C,C→D}依次判断每一个函数依赖是否冗余,直至所有冗余的函数依赖都被消除。本例子中经过第1步后已消除 F 中的所有冗余函数依赖了,因此原F={A→BD,AB→C,C→D}的最小函数依赖集为 F ={A→B,A→C,C→D}。

注意点:

F的最小依赖集F m 不一定是唯一的,它与对个函数依赖FDi 及X→A中个属性的处置的顺序有关。在本例子中在去掉F中的冗余的函数依赖时(绿色字体那一步)若不是首先判断A→D是否冗余,而是首先判断其它函数依赖是否冗余,那么所得的最小函数依赖就可能不同了要搞清楚在判断一个函数依赖X→A是否为冗余时,是求X关于上一步所求得的新的函数依赖集 F 的闭包XF+ ,然后在判断A是否包含在该XF+