3-2-4

3.2.1 函数依赖的定义
1.定义
　　设有关系模式R（U），X和Y是属性集U的子集，函数依赖（functional dependency，简记为FD）是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s，都有t［X］=s［X］蕴涵t［Y］=s［Y］，那么称函数依赖X→Y在关系模式R（U）中成立。
　　对于当前关系r的任意两个元组，如果X值相同，则要求Y值也相同，即有一个X值就有一个Y值与之对应，或者说Y值由X值决定。因而这种依赖称为函数依赖。

2.实例1

(1)设有关系模式R（A，B，C，D）
(2)A→B在关系R上成立
(3)A→B在关系S上不成立
3.实例2
(1)学生选课、教师任课的关系模式
　　 ○R（S#，SNAME，AGE，SEX，C#，CNAME，Grade，T#，TNAME，TITLE）
(2)规定：
　　 ①每个学号只能有一个学生姓名
　　 ②每个课程号只能决定一门课程名
(3)函数依赖
　　 ①S#→SNAME
　　 ②C#→CNAME
　　 ③（S#，C#）→GRADE
　　 ④S#→（AGE，SEX）
　　 ⑤C#→T#
　　 ⑥T#→（TNAME，TITLE）
4.函数依赖的箭头表示

(1)每个函数依赖用一个箭头表示
(2)箭尾处表示函数依赖左边的属性
(3)箭头处表示函数依赖右边的属性
5.实例3
(1)描述
　　 ①设关系模式R（ABCD）。
　　 ②A值与B值有一对多联系，即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系。
　　 ③C值与D值之间有一对一联系，即每个C值只有一个D值与之联系，每个D值只有一个C值与之联系。
(2)函数依赖
　　 ①从A值与B值有一对多联系，可写出函数依赖B→A。
　　 ②从C值与D值有一对一联系，可写出两个函数依赖C→D和D→C（C←→D）。 3.2.2 函数依赖的逻辑蕴涵
　　1.设F是在关系模式R上成立的函数依赖的集合，X→Y是一个函数依赖。如果对于R的每个满足F的关系r也满足X→Y，那么称F逻辑蕴涵X→Y，记为F X→Y。
　　2.设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包（closure），记为F⁺。即F⁺ =｛X→Y | F X→Y｝
3.2.3 函数依赖的推理规则
1.Armstrong公理
(1)A1（自反性，reflexivity）：若YXU，则X→Y在R上成立。
(2)A2（增广性，augmentation）：若X→Y在R上成立，且ZU，则XZ→YZ在R上成立。
(3)A3（传递性，transitivity）：若X→Y和Y→Z在R上成立，则X→Z在R上成立。
2.定理
(1)FD推理规则A1、A2和A3是正确的。也就是，如果X→Y是从F用推理规则导出，那么X→Y在F⁺中。
(2)证明：
　　 ①根据FD的定义和使用反证法来证明。
　　 ②A1是显然的。因为不可能在一个关系中存在两个元组在X上是相等的，而在X的某个子集Y上不相等。
　　 ③假设R的某个关系r中存在两个元组t和s违反XZ→YZ，即t［XZ］=s［XZ］，但t［YZ］≠s［YZ］。从t［YZ］≠s［YZ］可知t［Y］≠s［Y］或t［Z］≠s［Z］。如果t［Y］≠s［Y］，则与已知的X→Y矛盾；如果t［Z］≠s［Z］，则与假设的t［XZ］=s［XZ］矛盾。因此，假设不成立，从而得出A2是正确的。
　　 ④假设R的某个关系r中存在两个元组t和s违反X→Z，即t［X］=s［X］，但t［Z］≠s［Z］。如果t［Y］≠s［Y］，则与已知的X→Y矛盾；如果t［Y］=s［Y］，则与已知的Y→Z矛盾。因而A3是正确的。
3.函数依赖的其他五条推理规则
(1)A4（合并性）：｛ X→Y，X→Z ｝X→YZ。
(2)A5（分解性）：｛ X→Y，ZY ｝X→Z。
(3)A6（伪传递性）：｛ X→Y，WY→Z ｝WX→Z。
(4)A7（复合性）：｛ X→Y，W→Z ｝XW→YZ。
(5)A8（通用一致性定理）：｛ X→Y，W→Z ｝X∪（W－Y）→YZ。
4.实例
(1)已知关系模式R（ABC），F=｛ A→B，B→C ｝，求F⁺。
　　根据FD的推理规则，可推出F的F⁺有43个FD。
　　F⁺ = {φ→φ，
　　　　　A→φ，A→A，A→B，A→C，A→AB，A→AC，A→BC，A→ABC，
　　　　　B→φ，B→B，B→C，B→BC，
　　　　　C→φ，C→C，
　　　　　AB→φ，AB→A，AB→B，AB→C，AB→AB，AB→AC，AB→BC，AB→ABC，
　　　　　AC→φ，AC→A，AC→B，AC→C，AC→AC，AC→BC，AC→AB，AC→ABC，
　　　　　BC→φ，BC→B，BC→C，BC→BC，
　　　　　ABC→φ，ABC→A，ABC→B，ABC→C，ABC→AB，ABC→AC，ABC→BC，ABC→ABC}
5.定义
(1)对于函数依赖X→Y，如果YX，那么称X→Y是一个“平凡的FD”，否则称为“非平凡的FD”。
(2)正如名称所示，平凡的FD并没有实际意义，根据规则A1就可推出。
(3)人们感兴趣的是非平凡的FD。只有非平凡的FD才和“真正的”完整性约束条件相关。
6.定理
(1)如果A1…An是关系模式R的属性集，那么X→A1…An成立的充分必要条件是X→Ai（i=1，…，n）成立。 3.2.4 FD和关键码的联系
1.关系键的定义
　　设关系模式R的属性集是U，X是U的一个子集。如果X→U在R上成立，那么称X是R的一个超键。如果X→U在R上成立，但对于X的任一真子集X1都有X1→U不成立，那么称X是R上的一个候选键。
2.实例
(1)对于关系模式R（S#，SNAME，AGE，SEX，C#，CNAME，SCORE，T#，TNAME，TITLE）
(2)根据已知的FD和推理规则，可以知道（S#，C#）能函数决定R的全部属性，并且是一个候选键。
(3)虽然（S#，SNAME，C#，TNAME）也能函数决定R的全部属性，但相比之下，只能说是一个超键，而不能说是候选键，因为其中含有多余属性。 3.2.5 属性集的闭包
1.规则集{A1，A2，A3}是函数依赖的一个正确的和完备的推理规则集。
(1)推理规则的正确性是指“从FD集F使用推理规则集推出的FD必定在F⁺中”。
(2)完备性是指“F⁺中的FD都能从F集使用推理规则集导出”。
(3)也就是正确性保证了推出的所有FD是正确的，完备性保证了可以推出所有被蕴涵的FD。这就保证了推导的有效性和可靠性。
2.属性集闭包的引出
(1)在实际使用中，经常要判断能否从已知的FD集F推导出FD X→Y。
(2)那么可先求出F的闭包F⁺，然后再看X→Y是否在F⁺中。
(3)但是从F求F⁺是一个复杂且困难的问题。
(4)下面引入属性集闭包概念，将使判断问题化为多项式级时间问题。
3.定义
　　设F是属性集U上的FD集，X是U的子集，那么（相对于F）属性集X的闭包用X⁺表示，它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合：X⁺ =｛属性A | F X→A｝
4.定理
(1)X→Y能用FD推理规则推出的充分必要条件是YX⁺。
5.实例
(1)属性集U为ABCD，FD集为｛A→B，B→C，D→B｝
(2)则可求出A⁺=ABC，(AD)⁺=ABCD，(BD)⁺=BCD 3.2.6 FD集的最小依赖集
1.定义
(1)如果关系模式R（U）上的两个函数依赖集F和G，有F⁺=G⁺，则称F和G是等价的函数依赖集。
(2)F和G等价，意味着F中每一个FD都可以从G推导出来，并且G中每一个FD也都可以从F推导出来。
(3)函数依赖集F中的FD很多，我们应该从F中去掉平凡的FD、无关的FD、FD中无关的属性，以求得与F等价的最小依赖集G。
2.最小依赖集的形式定义：
如果函数依赖集G满足下列三个条件，则称G是最小依赖集：
　　 ①G中每个FD的右边都是单属性；
　　 ②G中没有冗余的F，即G中不存在这样的函数依赖X→Y，使得G －｛X→Y｝与G等价；
　　 ③G中每个FD的左边没有冗余的属性，即G中不存在这样的函数依赖X→Y，X有真子集W使得G －｛X→Y｝∪｛W→Y｝与G等价。
3.实例
(1)问题
　　 ①设F是关系模式R（ABC）的FD集，F=｛A→BC，B→C，A→B，AB→C｝，试求其最小依赖集。
(2)解：
　　 ①先把F中的FD写成右边是单属性形式：
　　 F=｛A→B，A→C，B→C，A→B，AB→C｝
　　 显然多了一个A→B，可删去。得F=｛A→B，A→C，B→C，AB→C｝
　　 ②F中A→C可从A→B和B→C推出，因此A→C是冗余的，可删去。得F=｛A→B，B→C，AB→C｝
　　 ③F中AB→C可从B→C推出，因此AB→C也是冗余的，可以删去。
　　 最后得F=｛A→B，B→C｝，即所求的最小依赖集。
4.计算函数依赖集F的最小依赖集G的算法
(1)据推理规则的分解性（A5），得到一个与F等价的FD集G，G中每个FD的右边均为单属性。
(2)在G的每个FD中消除左边冗余的属性。
(3)在G中消除冗余的FD。