数据依赖的Armstrong公理系统

关系模式R <U，F >来说有以下的推理规则：

1.自反律（Reflexivity）：若Y Í X Í U，则X →Y为F所蕴含（平凡函数依赖）

2.增广律（Augmentation）：若X→Y为F所蕴含，且Z Í U，则XZ→YZ为F所蕴含

3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含（传递函数依赖）

4.合并规则：由X→Y，X→Z，有X→YZ  (2,3)

5.伪传递规则：由X→Y，WY→Z，有XW→Z  (2,3)

6.分解规则：由X→Y及 ZÍY，有X→Z   (1,3)

Armstrong公理系统是有效的、完备的

有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；

完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来

注：F={XàA1, …… , XàAn}的闭包F+计算是一个NP完全问题

 

最小函数依赖集

例题：

 候选码

求解方法

1.属性组：

单属性：

对左边为单属性的函数依赖集求所有候选码

(1) 求F的最小依赖集F’

(2) 作出函数依赖图FDG

(3) 从FDG图中找出无入边的属性集X

(4) 察看FDG图中有无回路，若无，则输出X并结 束,否则进行下一步

(5) 从各独立回路中各取一个结点的属性与X组成一个候选码，重复取得所有可能的组合，即R的全部候选码

例题：

例1：关系模式CTHRSG, 若最小依赖集为F’={C →T, HR →C,CS →G,HS →R,HT →R}

解：L、N类属性为HS，LR属性为CTR。HS+=HS RCTG，包含全部属性，所以为唯一候选码 

例2：

解：L或N类属性有E和C, LR类属性ADB，令X=EC,(EC)+=U,EC为R的唯一候选码。

例3：

例4：

例5：