函数依赖总结

关系模式的外延和内涵

一个关系模式包含外延和内涵。

外延就是通常所说的关系、表或当前值。由于用户经常进行增删改查，所以外延是与时间有关的。

内涵是与时间独立的，是对数据的定义以及数据完整性约束的定义。对数据的定义包括关系、属性、域的定义和说明。

对数据完整性约束主要包括两个方面：

• 静态约束：涉及数据之间的联系（函数依赖）、主键和值域的设计。
• 动态约束：定义各种操作（增删改）对关系值的影响。

一般就把内涵称为关系模式。

关系模式的冗余和异常

数据冗余是指同一个数据在系统中多次出现。

由于数据的冗余，在对数据进行操作时会引发各种异常：如修改异常、插入异常、删除异常。根本原因是数据冗余可能造成操作后数据不一致现象。

“分解”是解决冗余的主要方法，也是规范化的一条原则“关系模式有冗余问题，就分解它”。

关系模式的非形式化设计准则

• 关系模式的设计应尽可能 只包含有直接联系的属性，不要包含有间接联系的属性。
• 关系模式的设计应尽可能 使相应关系中不出现插入、修改、删除等操作异常现象。
• 关系模式的设计应尽可能 使得相应关系中避免放置经常为空值的属性。
• 关系模式的设计应尽可能 使得关系的等值连接在主键和外键的属性上进行，并且保证链接后不会生成额外的元组。

函数依赖（FD）

FD的定义：

课本上使用数学集合论定义，其实函数依赖就是某个属性集决定另一个属性集时，称另一属性集依赖于该属性集。

在数据库中，FD是对关系模式R的一切可能的关系r定义的。对于当前关系r的任意两个元组，如果X值相同，则要求Y值也相同。这种依赖称为函数依赖。记为X->Y, 读作“X决定Y”，或“Y依赖与X”。

如果X->Y 和Y->X同时成立，则可记为X<-->Y,也就是在关系中，X和Y具有一一对应关系。

FD的逻辑蕴涵：

逻辑蕴含问题：比如A->B和B->C在关系模式上成立，那么A->C是否成立？这个问题就是逻辑蕴含问题。

设F是关系模式R上的一个函数依赖集合，X->Y是R上的一个函数依赖。如果对于R上的每个满足F的关系r也满足X->Y，那么称F逻辑蕴含X->Y。记为 F |= X->Y。

被F逻辑蕴含的函数依赖全体构成的集合，称为函数依赖集F的闭包，记为F+。

FD的推理规则：

从已知的一些FD，可以推导出另外一些FD，这需要一系列规则。这些规则常被称为“Armstrong"公理。

设U是关系模式R的属性集，F是R上成立的函数依赖集。FD的推广规则如下：

1. 自反性：若X1⊆X⊆U，则X->X1在R上成立。（X与自己的子集自反）
2. 增广性：若X->Y在R上成立，且Z⊆U，则XZ->YZ在R上成立。
3. 传递性：若X->Y和Y->Z在R上成立，则X->Z在R上成立。
4. 合并性：{X->Y, X->Z}  |= X->YZ
5. 分解性：{X->Y, Z⊆Y} |= X->Z
6. 伪传递性：{X->Y, WY->Z} |= WX->Z
7. 复合性：{X->Y, W->Z}  |= XW->YZ
8. 通用一致性原理：{X->Y, W->Z}  |= X∪(W-Y) ->YZ

FD和关键码的关系

有了FD的概念，可以把关键码和FD联系起来：

设关系模式R的属性集为U，X是U的一个子集，如果X->U在R上成立，那么称X是R的一个超键。如果X->U在R上成立，但X的任一真子集X1->U在R上不成立，则称X是是R的一个候选键。

一般键都是指候选键。

属性集闭包

求解函数依赖集闭包（F+）是NP完全问题，所以当需要判断是否能从已知FD集F中推导出FD X->Y，先求出F+再判断X->Y是否在F+中是很耗时间的事情。下面引入属性集闭包。

属性集闭包：F是属性集U上的FD集，X是U的子集，那么相对于F的属性集X的闭包X+可以定义为：它是一个从F集使用FD推理规则推出的所有满足X->A的属性A的集合。

求解属性集闭包的算法可以参考：属性集闭包算法