「 数据库原理 」求最小依赖集算法
文章主要介绍求最小依赖集的算法
定义
最小依赖集定义如下:
设F是属性集U上的FD集。如果Fmin是F的一个最小依赖集,那么Fmin应满足下列四个条件:
- Fmin+ =F+
- 每个FD的右边都是单属性
Fmin中没有冗余的FD
即F中不存在这样的函数依赖X→Y,使得F与F -{ X→Y }等价
每个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。
算法简单的说
先把F中的FD写成右边是单属性形式
这一步主要使用A5规则(分解性,decomposition):{ X→Y,Z⊆Y }⊨X→Z)
去掉FD左边的冗余属性
第一步将右边属性变成单属性,而第二步把左边属性尽量变成单属性,同样利用推理规则。
举例
这个示例详细说明了第1和第2步。
文章版权:Postbird-There I am , in the world more exciting!
本文链接:http://ptbird.cn/minimum-dependency-set.html
转载请注明文章原始出处 !
扫描二维码,在手机阅读!