关系模式的函数依赖

回顾关系与关系模式这两个概念的联系和区别。
 关系：元组的集合，笛卡尔积的一个子集，其实质是一张二维表，表的每一行为一个元组。
 关系模式：对元组中数据组织方式的结构性描述，其实质是删去所有元组后的空表格。
 关系与关系模式的联系：关系模式是相对稳定的、静态的，而关系却是动态变化的，不稳定的，且关系的每一次变化结果，都是关系模式对应的一个新的具体关系。
这是因为：关系模式是对元组中数据组织方式的结构性描述，关系是关系模式的一个取值实例。一个具体关系不管增加或减少一个元组，都变成一个新的关系。一个关系都对应一个关系模式，而一个关系模式可以定义多个关系。
 注意：在以后的讨论中，关系模式R(U)对应的具体关系通常用小写字母r来表示。

 定义4.1 设R(U)是属性集U={A1, A2, …, An}上的关系模式，X和Y是U的子集。若对R(U)的任一具体关系r中的任意两个元组t1和t2，只要t1[X]=t2[X]就有t1[Y]=t2[Y]。则称“X函数确定Y”或“Y函数依赖于X”(Founctional Dependence)，记作X->Y。
在以上定义中，t1[X]和t1[Y]分别表示元组t1在属性X和Y上的取值。“X函数确定Y”的含义是：对关系r中的任意一个元组，如果它在属性集X上的值已经确定，则它在属性集Y上的值也随之确定。因此，定义4.1即是说，在关系模式R(U)的任意一个具体关系r中，不可能存在这样的两个元组，它们在X上的属性值相等，而在Y上的属性值不等。
 注意：函数依赖不是指关系模式R(U)的某个或某些具体关系满足的约束条件，而是指R(U)的一切具体关系r都要满足的约束条件。

从例子可知，函数依赖和其它数据依赖一样，是一个语义范畴的概念。我们只能根据属性的语义来确定一个函数依赖。例如Sname(姓名)->Birthday(出生日期)这个函数依赖，只有在没有同姓名学生的条件下才成立。如果允许出现相同姓名的学生，则出生日期就不再函数依赖于姓名了。
数据库设计者应在定义数据库模式时，指明属性之间的函数依赖，使数据库管理系统根据设计者的意图来维护数据库的完整性。因此，设计者可以对现实世界中的一些数据依赖作强制性规定.
例如，为了使Sname->Birthday这个函数依赖成立，用户可以强制规定关系中不允许同名同姓的人出现。这样当输入某个元组时，这个元组在Sname上的属性值必须满足规定的函数依赖，若发现新输入元组在Sname上的值与关系中已有元组在Sname上的值相同，则数据库管理系统就拒绝接受该元组。解决的办法是通过人工方式是同名者为不同名者。比如有两个张华，可改为“张华a”，“张华b”等。

 在定义4.1的基础上补充以下常用术语和记号： 
⑴ 若X->Y，则称X为这个函数依赖的决定(Determinant)因素，简称X是决定因素。
⑵ 若X->Y且Y->X，则记作X->Y。X->Y
若Y不函数依赖于X，则记作非X->Y 。
⑷ 若X->Y，但Y->X，则称X->Y是平凡函数依赖。
⑸ 若X->Y，但Y属于X，则称X->Y是非平凡函数依赖。
对于任一关系模式，平凡函数依赖都是必然成立的，但它不反映新的语义。
在下面的讨论中，若没有特别声明，“X?Y”都表示非平凡函数依赖。
 定义4.2设R(U)是属性集U={A1, A2, …, An}上的关系模式。X和Y是U的子集。
⑴ 如果X->Y，且对于 X的任何一个真子集X?，都有 ，则称Y对X完全函数依赖(Full Founctional Dependence)或者X完全决定Y,记作:X完全函数决定Y。
⑵ 如果X->Y，但Y不是完全函数依赖于X，则称Y对X部分函数依赖(Partial Founctional Dependence)，记作：X部分函数决定Y。
 定义4.3 对于关系模式R(U)，设X、Y和Z都是U的子集。如果X->Y，Y->Z，且Y?X，Z?Y ,
则称Z对X传递函数依赖(Transitive Founctional Dependence)，记作: X传递函数决定Z 。
在传递函数依赖的定义中加上条件 是必要的，因为如果Y?X，则X?Y，即说明X与Y之间是一一对应的，这样导致Z对X的函数依赖是直接依赖，而不是传递函数依赖。定义4.3中的条件 主要是强调X?Y和Y?Z都不是平凡函数依赖，否则同样Z对X是直接函数依赖，而不是传递函数依赖。当然，若 X?Z ，则必有X?Z。

 定义4.4 对关系模式R(U)，设K?U。如果 ，则称K为R(U)的候选键或候选关键字(Candidate Key)。通常在R(U)的所有候选键中选定一个作为主键(Primary Key)。主键也称为主码或主关键字。
 候选键是能够唯一确定关系中任何一个元组(实体)的最少属性集合，主键也是候选键，它是候选键中任意选定的一个。在最简单的情况，单个属性是候选键。最极端的情况是，关系模式的整个属性集全体是候选键，也是主键，这时称为全键或全码(All-key)

 定义4.5对关系模式R(U)，包含在任何一个候选键中的属性称为主属性(Primary Attribute)，不包含在任何候选键中的属性称为非主属性(Nonprimary Attribute)或非码属性(Non-key Attribtute)。

 定义4.6 对关系模式R(U)，设X属于U。若X不是R(U)的主键，但X是另一个关系模式的主键，则称X是R(U)的外键或外部关键字(Foreign key)。

在讨论函数依赖时会遇到这样的问题：以知关系模式R(U,F)的函数依赖集F={A->B，B->C}。问A->C是否成立? ，其中属性集U={A, B, C}。这是本节后面将讨论的有关问题，其内容安排如下：
 函数依赖的逻辑蕴涵
 Armstrong公理系统
 函数依赖推理规则的完备性
 闭包的计算
 函数依赖集的等价和覆盖

定义4.7 对于满足函数依赖集F的关系模式R(U,F)的任意一个具体关系r，若函数依赖X?Y都成立(即对于r中的任意两个元组t，s，若t[X]=s[X]，则有t[Y]=s[Y])，则称F逻辑蕴涵X->Y,记为F=>X->Y。
注意，在定义4.7中没有假定函数依赖(X->Y)属于F，X,Y都是属性集U的子集合。
定义4.8 被函数依赖集F逻辑蕴涵的函数依赖所构成的集合，称为F的闭包(Closure)，记作F+。即 F+={X->Y | F=>X->Y}。

 定理4.1 Armstrong公理系统中的推理规则⑴，⑵，⑶是正确的，即若X?Y由Armstrong公理导出，则X?Y属于F+。
 定理4.2 函数依赖的如下三个推理规则是正确的。
⑴ 合并律(Union Rule)：如果X?Y和X?Z成立，那么X?YZ成立，即若F?X?Y，F?X?Z，则F? X?YZ。
⑵ 伪传递律(Pseudotransivity Rule)：如果X?Y和WY?Z成立，那么WX?Z成立，即若F?X?Y，F?WY?Z，则F?WX?Z。。
⑶ 分解律(Decomposition Rule)：如果X?Y和Z?Y成立，那么X?Z成立，即若F?X?Y，Z?Y，则F? X?Z。 
 定义4.9 设F是属性集合U上的一个函数依赖集，X?U，称为属性集X关于F的闭包。
在以后的讨论中，如果只涉及一个函数依赖集F，则属性集X关于F的闭包常简记为X+。值得注意的是，定义4.9中的A是U中的单个属性，因此X?X+?U。
 定理4.3 设F是属性集U上的函数依赖集，X，Y是U的子集，则X?Y能由F根据Armstrong公理导出的充分必要条件是Y? X+。

前面我们曾经提到，为了判断函数依赖X?Y是否在F+中，只要计算出F+即可。因为F+是由F根据Armstrong公理导出的函数依赖的集合。因此，原则上说，只要按照Armstrong公理系统中的推理规则就可以计算出F+。但是，闭包F+的计算是一件很麻烦的事情，因为计算F+的问题是一个NP完全问题，即若F={X?A1, X?A2, …, X?An,}，则需要计算F+的O(2n)个函数依赖，因此，当 n比较大时，实际计算F+是不可行的。即使F的元素不多时， F+中的元素也可能很多。此外，闭包F+中也存在许多冗余信息。其实，判断一个函数依赖X?Y是否在F+中，完全不必计算闭包F+，因为，由定理4.3可知，只要判断X?Y能否从F根据Armstrong公理导出，即判断Y?X+是否成立即可。这样就把一个需要计算F+才能解决的问题简化为计算X+就能解决得问题。而计算X+并不太难，它所花费的时间与F中的全部函数依赖的长度成正比。下面介绍一个计算X+的算法。
 算法4.1 求属性集X?U关于函数依赖集F的闭包X+。
输入：有限的属性集合U、它上面的函数依赖集合F和U的一个子集X。
输出：X关于F的闭包X+。
计算方法和计算步骤：
⑴设置初始值：令X(0)＝空集，X(1)＝X，F'=空集；
⑵如果X(0)≠X(1)，令X(0)＝X(1)，否则转⑷；
⑶构造函数依赖集F'={Y->Z | (Y->Z)属于F且Y?X(1)}，令 F=F-F'
对F'中的每一个函数依赖Y->Z,令X(1)= X(1)∪Z,转⑵
⑷ 输出X(1)，它就是X+。
例4.10 设有关系模式R(A,B,C,D,E)，其属性集上函数依赖：F={AB->C, B->D, C->E, EC->B, AC->B}，这里的AB->C是{A, B}->{C}的简写。
令X={A, B}，求X+。
解： 计算过程是根据循环次数介绍的。由算法4.1 
第一次：⑴ X(0)=空集，X(1)={A, B}，F'=空集；
⑵ 由于X(0)≠X(1)，令X(0)＝X(1)={A, B}；
⑶ 函数依赖集F'={ AB->C, B->D}，令F=F-F'={C->E, EC->B, AC->B}，
将F'中的每一个函数依赖的右端属性C,D并入X(1)中，
即令X(1)={A, B}∪{C, D}={A, B, C, D}；
第二次：⑵ 由于X(0)?X(1)，令X(0)＝X(1)= {A, B, C, D}；
     ⑶ 函数依赖集F'={C->E, AC->B}，令F=F- F'={EC->B}，
将F'中的每一个函数依赖的右端属性E, B并入X(1)中，
即令X(1)={A, B, C, D }∪{E, B}={A, B, C, D, E} ；
第三次：⑵ 由于X(0)≠X(1)，令X(0)＝X(1)= {A, B, C, D, E } ；
   ⑶ 函数依赖集F'={EC->B}，令F=F-F'=空集,
将F'中的每一个函数依赖的右端属性B并入X(1)中，
即令X(1)={A, B, C, D, E }∪{B}={A, B, C, D, E}；
第四次：⑵ 由于X(0)=X(1)，转⑷
   ⑷输出X(1)={A, B, C, D, E}=X+。