Powers7's Blog

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://powers7.blogbus.com/logs/23675010.html

函数依赖(FD)
1、函数依赖的定义(领会)：设有关系模式R(A1，A2，...An)或简记为R(U)，X，Y是U的子集，r是
R的任一具体关系，如果对r的任意两个元组t1,t2,由t1[X]=t2[X]导致t1[Y]=t2[Y]，则称X函数决
定Y，或Y函数依赖于X，记为X→Y。X→Y为模式R的一个函数依赖。
其实函数依赖就和数学里函数概念差不多，只不过在这里不是变量而是属性列。比
如关系表里如果有身份证号和姓名两列，身份证号不会有相同的(假身份证和公安局失误造成的同
号不算)，知道身份证号肯定就能知道这个人的姓名了，所以就可以说有函数依赖：身份证号→姓
名 成立。
pay attention to:
a、对任一具体关系均要满足条件。比如表里有姓名和出生年月两个属性，现在没有
重名的，你可以说知道姓名就能知道出生年月，但万一增加记录时，来了个与已有的人重名的
呢？除非给这是在给孩子上户口，不允许重名，否则这时光知道姓名就不够了。根据这一点，我
们可以依据特例否定函数依赖。
b、函数依赖只能根据实际情况判断，不可证明

2、函数依赖的逻辑蕴涵(识记)
设F是关系模式R的一个函数依赖集，X,Y是R的属性子集，如果从F中的函数依赖能够推出X→Y，则
称F逻辑蕴涵X→Y，记为F│=X→Y.
就是说，一个关系模式可能有多个函数依赖形成函数依赖集，现在有一个新的函数
依赖不在函数依赖集里，但能从集合里根据一定的规则(就是后面的Armstrong规则)推导出来，就
说那个集合逻辑蕴涵这个新的函数依赖。
比如，“根据身份证号能确定出生年月和性别”是已知的函数依赖，根据已知和后面的知识能推
导出“根据身份证号能确定出生年月”，就说“根据身份证号能确定出生年月和性别”逻辑蕴涵
“根据身份证号能确定出生年月”。

而函数依赖的闭包F+是指被F逻辑蕴涵的函数依赖的全体构成的集合。
就是说根据F能推导出的全部函数依赖（至于怎么推导和如何保证没有遗漏都是以后
的事）。

3、键和FD的关系(领会)
键是唯一标识实体的属性集。
设关系模式R(A1,A2...An)，F是R上的函数依赖集，X是R的一个子集，
(1)X→A1A2...An∈F+  
(2)不存在X的真子集Y，使得Y也能决定唯一的一个元组，则X就是R的一个候选键。
在函数依赖概念的基础上，再加上能确定全部属性和没有富余的部分。比如：知道
身份证号就能知道这个人的姓名，但是不能确定婚否，所有假如一个关系模式有（身份证号、姓
名、婚否）这些属性时，身份证号不能叫侯选键。还有知道身份证号和出生年月肯定能知道这个
人的姓名，但出生年月在这里显得多余，以（身份证号，出生年月）也不能叫侯选键。

包含在任何一个候选键中的属性称为主属性，不包含在任何键中的属性为非主属性(非键属性)，
注意主属性应当包含在候选键中。
这没什么好理解的，就是概念了。

4、函数依赖(FD)的推理规则(简单应用)
Armstrong(胳膊壮?)推理规则
设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则
如下：
自反律：如果YXU,则X→Y在R上成立。 
增广律：如果X→Y为F所蕴涵，Z包含于U，则XZ→YZ在R上成立。(XZ表示X∪Z，下同) 
传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。
合并律：如果X→Y和X→Z成立，那么X→YZ成立。 
伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。 
分解律：如果X→Y和Z包含于Y成立，那么X→Z成立。 
其实这些东西都不难理解，记住就行了。书上还有引理4.1:Armstrong是正确的（不
正确放这干什么？）和定理4.1：X→Y的充要条件是Y包含于X+(闭包就是这么定义的嘛！)，结论
都没什么好说的，证明过程就算了吧。

5、函数依赖推理规则的完备性(识记)
Armstrong函数依赖推理规则系统是完备的。
属性集X+ 中的每个属性A，都有X→A被F逻辑蕴涵，即X+是所有由F逻辑蕴含X→A的属性A的集
合。 
F+是所有利用Amstrong推理规则从F导出的函数依赖的集合 
道理很简单，到这时，逻辑蕴涵、Armstrong规则、闭包这些概念应该有个整体的认
识：如果A逻辑蕴涵B,B一定在A的闭包中；A的闭包是由A根据Armstrong能推导出的所有函数依
赖。

6、闭包的计算（识记)
已知函数依赖集合F,如果知道X+,就能知道X→Y是否在F+中，所以，要会求X+，具体
求法是算法4.1，很简单的，看看例4.3就行，就是一个一个往后推，推到推不动为止。
定理4.3说那个算法是正确的，权且当成废话吧:)

7、函数依赖集的等价和覆盖(识记)
在关系模式R(U)上的两个函数依赖集F和G，如果满足F+=G+，则称F和G是等价的，称F和G等价也称
F覆盖G或G覆盖F。
每个函数依赖集F都可以被一个右部只有单属性的函数依赖集G所覆盖。
就是把合并律倒过来。

如果函数依赖集合F满足： 
(1)F中每一个函数依赖的右部都是单属性； 
(2)F中的任一函数依赖X→A，其F-{X→A}是不等价的； 
(3)F中的任一函数依赖X→A，Z为X的子集。(F-{X→A})∪{Z→A}与F不等价。 
则称F为最小函数依赖集合。 
如果函数依赖集F和G等价，并且G是最小集，那么称G是F的一个最小覆盖。

定理4.5的证明是最小覆盖的求法
第一步：函数依赖右边全转换为单属性
第二步：
while(对每个函数依赖的左边进行检查)
    while(对当前函数依赖左边的每个属性进行检查)
      if(左边-当前属性)的闭包包含右边
         当前函数依赖的左边=当前函数依赖的左边-当前属性；
第三步：
while(对每个函数依赖进行检查)
  {
   当前函数依赖集=F-当前函数依赖：
   if 当前函数依赖右边包含于（当前函数依赖左边相对于当前函数依赖集的闭包）
      去掉当前函数依赖；
   }

  转自吴志敏的专栏：http://blog.csdn.net/kauu/archive/2006/05/14/728501.aspx