函数依赖的公理系统

函数依赖集的等价和覆盖
求最小函数依赖集的方法：

应用分解规则，使F中每一个依赖的右部单一化。 去掉各函数依赖左部多余的属性。
方法：检查F中左边是非单属性的依赖，如： XY→A， 要判定Y是否多余，只要求X闭包，若X闭包A，则Y 是多余的，以X →Y 代替XY→A。

去掉多余的依赖。
方法：从第一个依赖开始，若要从F中去掉X →Y ，则在 剩下的依赖中求X闭包，若X闭包包含Y,则去掉X →Y
属性集闭包计算举例
练习 已知R<U,F>, U= (A, B, C, G, H, I)，F={AB, AC, CGH,
CGI, BH}，计算(AG)+。 – 算法第一次循环的执行步骤： 步骤 FD closure
1．
2． 3． 4． 6． 6．
初值
AB AC CGH CGI BH
增广律得证。
定理 Armstrong推理规则是正确的
(3) 传递律：若X→Y及Y→Z为F所蕴含，则 X→Z为 F所蕴含。
证：设X→Y及Y→Z为F所蕴含。
对R<U，F> 的任一关系 r中的任意两个元组 t，s。 若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]；
再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含.
引理: X→A1 A2…Ak成立的充分必要条件 是X→Ai成立（i=l，2，…，k）。
总结:函数依赖(FD)的推理规则
函数依赖有一个正确的和完备的推理规则集——Armstrong 推理规则：
设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U 中属性的函数依赖集， 推理规则如下：
候选码的判断
设有关系R({A1,A2,…,An},F)，F为R的函数依赖集，X为
R的属性组，若X满足： 1 X→ A1,A2,…,An，即X+={A1,A2,…,An} 2 不存在X的真子集Y，Y → A1,A2,…,An。 则称X为R的码 例：关系R{A,B,C,D}，有FD如下： F={AB→C,C →B,BC →D,ACD →B}，R的码为？ AB+=ABCD,AC+=ABCD,ACD+=ABCD, 候选码为：AB，ACD;还是AB,AC？还是其他？思考！！
函数依赖闭包
函数依赖的闭包F+是指被F逻辑蕴涵的函数依赖的全体构成的集
合
函数依赖推理规则的完备性
函数依赖推理规则系统(自反律、增广律和传递律)是完备的。
由推理规则的完备性可得到两个重要结论： (1)属性集X+ 中的每个属性A，都有X→A被F逻辑蕴涵，即X+是 所有由F逻辑蕴含X→A的属性A的集合。 (2)F+是所有利用Amstrong推理规则从F导出的函数依赖的集合
传递律得证。
2. 导出规则
1.根据A1，A2，A3这三条推理规则可以得 到下面三条推理规则：
– 合并规则：由X→Y，X→Z，有X→YZ。
（A2， A3）
– 伪传递规则：由X→Y，WY→Z，有XW→Z。
（A2， A3）
– 分解规则：由X→Y及 ZY，有X→Z。
（A1， A3）
导出规则
2.根据合并规则和分解规则，可得引理1
函数依赖
[例]关系模式R(A, B, C, G, H, I)，函数依赖集
F={AB, AC, CGH, CGI, BH}。我们可列 出F中蕴含的几个依赖： – 由传递律可得AH，因为AB且BH； – 由合并律可得CGHI，因为CGH，CGI；
– 由伪传递律可得AGI，因为AC且CGI。
所以X→Y成立.
自反律得证
定理 Armstrong推理规则是正确的
(2)增广律: 若X→Y为F所蕴含，且Z U，则XZ→YZ
为F所蕴含。
证：设X→Y为F所蕴含，且Z U。
设R<U，F> 的任一关系r中任意的两个元组t，s； 若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]； 由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以 XZ→YZ为F所蕴含.
注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律
的使用并不依赖于F
定理 Armstrong推理规则是正确的
（l）自反律:若Y X U，则X →Y为F所蕴含
证: 设Y X U
对R <U，F> 的任一关系r中的任意两个元组t，s：
若t[X]=s[X]，由于Y X，有t[y]=s[y]，
求最小函数依赖集
在数据库设计过程中，实体及属性的冗
余可以通过分析确定，而联系的冗余通 过函数依赖集的极小化算法查出和消除。
最小依赖集
或者： 1。将函数依赖的右部分解为一个属性； 2。确保函数依赖左边是不可分的； 3。将具传递性的函数依赖去掉； 如：假设一个关系R中具有属性A、B、C、D。 F={A→BC,B →C,A →B,AB →C,AC →D} 解： （1）A→BC分解为A→B， A→C； （2）由 A→C知AB →C是冗余的，去掉； A →C得A → AC，而 AC →D，则A →D，所以， AC →D冗余。 （3） A→C可由A→B， B→C得，所以A→C要去掉。 得到R的最小依赖集F={A→B，B→C，A→D}
这套推理规则，是模式分解算法的理论基础。
用途
– 从一组函数依赖求得蕴含的函数依赖。 – 求给定关系模式的码。
1. Armstrong公理系统
关系模式R <U，F >来说有以下的推理规则：
– Al.自反律（Reflexivity）： 若Y X U，则X →Y为F所蕴含。 – A2.增广律（Augmentation）：若X→Y为F所蕴含， 且Z U，则XZ→YZ为F所蕴含。 – A3.传递律（Transitivity）：若X→Y及Y→Z为F所 蕴含，则X→Z为F所蕴含。
属性集闭包计算举例
R=(U,F),其中,U={A, B, C, D}, F={A B, AC D}; 求A+,B+,C+,AC+; 求R的侯选码
属性集闭包计算举例
U={A, B, C, D}; F={A B, AC D}; A+ = AB. 显然，AC是 C+ = C. 候选码 (AC)+ = ABCD. B
6. 最小依赖集
定义： 如果函数依赖集F满足下列条件，则称 F为一个极小函数依赖集。亦称为最小依赖集 或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖X→A，使得F与 F-{X→A}等价。 (3) F中不存在这样的函数依赖X→A， X有真 子集Z使得F-{X→A}∪{Z→A}与F等价。 如果函数依赖集F和G等价，并且G是最小集， 那么称G是F的一个最小覆盖。
函数依赖的公理系统
数据依赖的公理系统
逻辑蕴含
定义: 对于满足一组函数依赖 F 的关系
模式R <U，F>，其任何一个关系r，若函 数依赖X→Y都成立, 则称F 逻辑蕴含X →Y
Armstrong公理系统
从已知函数依赖集F要问X →Y是否为F逻辑蕴含，就要
一套推理规则，由Armstrong在1974年提出。
AG
ABG ABCG ABCGH ABCGHI ABCGHI
结果为closure=ABCGHI。
– (AG)+＝ABCGHI。（也就是说，AG可以决定右面的每一个属性）
计算属性集闭包的作用
计算属性集闭包的作用可归纳如下：
– 验证XY是否在F+中：看是否有YX+。 – 判断X是否为R的超码：通过计算X+，看其是否包含R 的所有属性。例如，(AG)+＝ABCGHI，则AG为R的 超码。 – 判断X是否为R的候选码：若X是超码，可检验X包含 的所有子集的闭包是否包含R的所有属性。若不存在 任何这样的属性子集，则X是R的候选码。
A
D
C
思考：哪些属性是L 类？（只出现在函 数依赖左边）哪些 是R类？哪些是LR 类？哪些是N类？它 们与候选码有什么 关系？
候选码的作用
例题：已知R(X,Y,Z),F={XY→Z}，请问
R为第几范式？（请思考：解题的思路是 什么？） XY为候选码，R属于BCNF。 练习：R(W,X,Y,Z),F={X→Z,WX→Y}， 请问R为第几范式？
闭包的计算
算法：求属性集X关于函数依赖F的闭包X+
方法：计算x（i）（I=0,1,……） (1)x(0)=x; (2)x(i+1)=x(i)A 其中A是这样的属性，在F中寻找尚未用过的左边是x(i)子集的函数 依赖 （3）判断是否有 A：x(i+1)=x(i); B:若在x(i+1)已包含了F中的全部属性； C：x(i+1) ≠x(i)，但x(i+1)的左部属性依赖已使用完 出现A，B，C 的一种即结束，否则转（2）
闭包的计算
例：在关系模式R（U，F）中，U=ABCDEF={A→C，AC→B，
B→D，C→E，EC→B} 计算(EC)+ 。
计算过程如下：
(1) x(0)=EC
(2) 检查函数依赖，因 EC→B ， X(1)=EC∪B=ECB (3)检查函数依赖，因 B→D，X(2)=ECB∪D=ECBD （4）X(3)= X(2)，所以(EC)+ =ECBD
关于闭包的引理
引理:
设F为属性集U上的一组函数依赖，X，Y U，X→Y能 由F 根据Armstrong公理导出的充分必要条件是Y XF+
用途
将判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为
求出XF+ ，判定Y是否为XF+的子集的问题(简单说，求逻辑蕴