文章主要介绍求最小依赖集的算法

定义

最小依赖集定义如下：

设F是属性集U上的FD集。如果Fmin是F的一个最小依赖集，那么Fmin应满足下列四个条件：

  1. Fmin+ =F+
  2. 每个FD的右边都是单属性

  3. Fmin中没有冗余的FD

        即F中不存在这样的函数依赖X→Y，使得F与F -｛ X→Y ｝等价

  4. 每个FD的左边没有冗余的属性

        即F中不存在这样的函数依赖X→Y，X有真子集W使得F -｛ X→Y ｝∪｛ W→Y ｝与F等价

    算法

--
首先这个算法基于FD的推理规则：

  • A1（自反性，reflexivity）：若Y⊆X⊆U，则X→Y在R上成立。
  • A2（增广性，augmentation）：若X→Y在R上成立，且Z⊆U，则XZ→YZ在R上成立。
  • A3（传递性，transitivity）：若X→Y和Y→Z在R上成立，则X→Z在R上成立。
  • A4（合并性，union）：｛ X→Y，X→Z ｝⊨X→YZ。
  • A5（分解性，decomposition）：｛ X→Y，Z⊆Y ｝⊨X→Z。
  • A6（伪传递性）：｛ X→Y，WY→Z ｝⊨WX→Z。
  • A7（复合性，composition）：｛ X→Y，W→Z ｝⊨XW→YZ。
  • A8 ｛ X→Y，W→Z ｝⊨X ∪（W－Y）→YZ。

算法简单的说

  1. 先把F中的FD写成右边是单属性形式

    
    这一步主要使用A5规则（分解性，decomposition）：｛ X→Y，Z⊆Y ｝⊨X→Z）

  2. 去掉FD左边的冗余属性

        
    第一步将右边属性变成单属性，而第二步把左边属性尽量变成单属性，同样利用推理规则。

举例

这个示例详细说明了第1和第2步。

postbird