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

定义

最小依赖集定义如下:

设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