数据依赖是关系内部属性之间相关联系的表达，是语义的体现，是构成数据的约束，大多数数据依赖是函数依赖，它是关系中“键”概念的范化。
使用数据依赖这一概念来定义关系模式的规范形式，即规范化理论。
函数依赖FD
A1,A2,……,An——>B1,B2,……,Bm
（若两个元组A1到An上相同则B1到Bm也相同，A1到An函数决定B1到Bm）
从已知FD推断其它FD
FD的集合T，S
T与S等价：关系实例集合满足S与其满足T的情况完全一样
（S是从T中推断而来，T也是从S中推断而来）
S从T中推断而来：满足T的关系实例也满足S（S蕴涵于T）
分解/结合规则：
A1,A2,……,An——>B1,B2,……,Bm
等价于
A1,A2,……,An——>B1，A1,A2,……,An——>B2，……
A1,A2,……,An——>Bm
平凡函数依赖
一个约束对所有关系实例都成立，且与其它约束无关
平凡FD的右边是左边的子集
平凡依赖规则：
A1,A2,……,An——>B1,B2,……,Bm（B中部分属于A）
等价于
A1,A2,……,An——>C1,C2,……Ck（B中不属于A的部分）
（注：
非平凡函数依赖：仅当其右边属性集中至少有一个属性不属于左边的集合。例如： title year →year length
完全非平凡函数依赖：仅当其右边集合中的属性均不在左边集合中。例如： title year →length）
属性的闭包
S下{A1,A2,……An}的闭包{A1，……An}上标+
就是A中可以从S推断出来的右边变成一个集合
从一个给定集合A出发，不断扩展这个集合，对于S中的FD分解使右边只有一个属性，然后对于FD，只要左边都在集合中就把右边也加到集合中。p42
传递规则
若A1,A2,……,An——>B1,B2,……,Bm且B1,B2,……,Bm——>C1,C2,……Ck
则A1,A2,……,An——>C1,C2,……Ck
函数依赖的闭包集合
求函数依赖集F的闭包F+：求所有属性子集的闭包（不考虑空集），然后利用每个闭包来写FD（A->空集也要写）
S的基本集：任何和S等价的FD集合
最小化基本集：右边均是单一属性；删除任何一个FD后不再是基本集；
对于任何一个FD，若删除其左边一个或多个属性，不再是基本集
投影函数依赖
R投影到R1
函数依赖集S的投影为满足以下条件的FD的集合：1.从S推断而来2.只包含R1中的属性
对R1的所有子集求闭包，得到FD的基本集，简化为最小基本集
“求属性子集闭包”的几个主要应用
1.求所有候选键
2.求所有非平凡FD
3.求所有违反BCNF的非平凡FD（投影函数依赖应用1）
4.求非平凡FD的最小基本集（投影函数依赖应用2）
简化规则：
1.不必考虑空集（适用于1-4）
2.不必考虑不能推出非平凡函数依赖的属性子集X（适用于1-4）
2.1属性子集X的任何一个子集都不是FD的左部，无法推出非平凡FD，无需求该属性子集X的闭包。如例1.
2.2不必考虑属性全集U的闭包。
2.3 属性子集X+的闭包依然是X+本身，无法推出非平凡FD，不需要再求X+的闭包
3.如果已知属性子集X, X+是属性全集，那么就无需考虑任何X超集的闭包。（注意：！！！！！！不适用于2！！！！！！）
- 关系数据库模式设计
异常：冗余；更新异常；删除异常
分解关系
将一个关系用多个不存在异常的关系替换
Boyce-Codd范式BCNF
每个非平凡FD的左边都必须是超键
任何一个二元关系属于BCNF
(BCNF范式在3NF的基础上，消除主属性对键的部分函数依赖与传递函数依赖)
分解为BCNF
输入：关系R0其上的函数依赖集S0
输出：由R0分解出的关系集合，每个关系都属于BCNF
方法：R=R0 S=S0
1.检验R是否属于BCNF若是则返回{R}
2.有BCNF违例X->Y，计算X的闭包，令R1为X的闭包，R2为X与不在X的闭包中的属性
3.计算R1，R2的投影函数依赖S1,S2
4.递归检验R1，R2
分解的优势
1.消除异常
2.信息的可恢复
3.依赖的保持
BCNF可保持1，2
3NF可保持2，3
无损连接的分解
子关系经连接(这里指自然连接)运算可恢复原关系
保持依赖的分解
子关系的函数依赖集可蕴涵原函数依赖集
从分解中恢复信息
无损连接：可通过连接分解的各个关系重构原关系
若Y->Z在关系R上成立，且R的属性集为X∪Y∪Z，则R=π{下标X∪Y}(R)⋈π{下标Y∪Z}(R)
chase算法：检验一个分解是否含有无损连接，即判断是否可以根据F中的FD来证明所有属于π{下标s1}(R)⋈π{下标s2}(R)⋈……⋈π{下标sk}(R)的元组t也属于R
例，
关系R（A，B，C，D）被分解为S1（A，D），S2（A，C），S3（B，C，D）
FD：A->B,B->C,CD->A
A B C D
S1 a b1 c1 d 有下标的表示在这行表示的关系中未知
S2 a b2 c d2
S3 a3 b c d
利用FD来进行一些等同操作，如果有那一行和t相同（即为a，b，c，d）则说明该分解包含无损连接，若FD都用完了还是没出现t则有损
A->B b2=b1
A B C D
S1 a b1 c1 d
S2 a b1 c d2
S3 a3 b c d
B->C c1=c
A B C D
S1 a b1 c d
S2 a b1 c d2
S3 a3 b c d
CD->a a3=a
A B C D
S1 a b1 c d
S2 a b1 c d2
S3 a b c d 出现t
投影到S1上有{(a,d),(a,d2)}
投影到S2上有{(a,c)}
投影到S3上有{(b1,c,d),(b1,c,d2),(b,c,d)}
自然连接S1，S2，S3
{(a,b1,c,d),(a,b,c,d),(a,b1,c,d2)}元组相对于R并没有变多
在考虑一个有损的情况
R（A，B，C，D） FD：B->AD S1(A,B) S2(B,C) S3(C,D)
A B C D
S1 a b c1 d1
S2 a2 b c d2
S3 a3 b3 c d
B->AD d2=d1 a2=a
A B C D
S1 a b c1 d1
S2 a b c d1
S3 a3 b3 c d
投影到S1上有{(a,b),(a3,b3)}
投影到S2上有{(b,c),(b,c1),(b3,c)}
投影到S3上有{(c1,d1),(c,d1),(c,d)}
自然连接S1，S2，S3
{(a,b,c,d1),(a,b,c,d),(a,b,c1,d1),(a3,b3,c,d1),(a3,b3,c,d)}元组相对于R变多了
依赖的保持
BCNF无法保持 p57例3.25
第三范式3NF
拥有无损连接和依赖保持性质
条件：对于每个非平凡FD，或者其左边是超键，或者其右边仅由主属性构成
输入：关系R和其上成立的函数依赖集FD
输出：由R分解出的关系集合，其中每个关系均属于3NF，分解具有无损连接和依赖保持性质
步骤：
1.找出F的最小基本集G
2.对于G中的每个FD X->A，将XA作为分解出的某个关系的模式
3.若2中分解出的模式中不含R的超键，增加一个关系其模式为R的任意一个键
如果一个模式是另一个的子集，则要去掉它
网友评论