关系模式的函数依赖

再论关系与关系模式
回顾关系与关系模式这两个概念的联系和区别。关系：元组的集合，笛卡尔积的一个子集，其实质是一张二维表，表的每一行为一个元组。关系模式：对元组中数据组织方式的结构性描述，其实质是删去所有元组后的空表格。关系与关系模式的联系：关系模式是相对稳定的、静态的，而关系却是动态变化的，不稳定的，且关系的每一次变化结果，都是关系模式对应的一个新的具体关系。这是因为：关系模式是对元组中数据组织方式的结构性描述，关系是关系模式的一个取值实例。一个具体关系不管增加或减少一个元组，都变成一个新的关系。一个关系都对应一个关系模式，而一个关系模式可以定义多个关系。注意：在以后的讨论中，关系模式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都要满足的约束条件。
例4.3 设有一个描述学生信息的关系模式: R(Sname, Sex, Birthday, Phone)，其属性名分别代表学生的姓名、性别、出生日期和电话号码属性。它的一个具体关系r如表所示。
如果仅从关系模式R(U)的一个具体关系r出发，由于r没有相同姓名的元组(学生)，所以我们就会得出：对于关系模式R有Sname->Sex，Same->Birthday，Sname->Phone的结论。但这个结论是不正确的。比如，对关系模式R的另外一个具体关系r1，这时，从关系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 对于例4.1的关系模式StudyInfo(Sno, Sname, DeptName, DeptHead, Cname, Grade)有如下的一些函数依赖：Sno->Sname, {Sno, Cname}->Grade，Sno->DeptName, DeptName->DeptHead。由最后两个函数依赖还可得出DeptHead传递函数依赖Sno，即 Sno->DeptHead 。如果没有同姓名的学生，还有Sno->Sname等。但显然有Grade->Sname ，{Sno, Cname}->Sname。其实，对关系模式StudyInfo还有Sno->Sname ，{Sno, Cname}->Grade 等。因此，Sno是 Sno->Sname的决定因素，{Sno,Cname}是的决定因素。
三.候选键与主键
定义4.4 对关系模式R(U)，设K?U。如果，则称K为R(U)的候选键或候选关键字(Candidate Key)。通常在R(U)的所有候选键中选定一个作为主键(Primary Key)。主键也称为主码或主关键字。候选键是能够唯一确定关系中任何一个元组(实体)的最少属性集合，主键也是候选键，它是候选键中任意选定的一个。在最简单的情况，单个属性是候选键。最极端的情况是，关系模式的整个属性集全体是候选键，也是主键，这时称为全键或全码(All-key)
例4.5 设有关系模式R(Teacher，Course，Sname)，其属性Teacher，Course，Sname 分别表示教师，课程和学生。由于一个教师可以讲授多门课程，某一课程可由多个教师讲授。学生也可以选修不同教师讲授的不同课程，因此，这个关系模式的候选键只有一个，就是关系模式的全部属性(Teacher，Course，Sname)，即全键(All-key)，它也是该关系模式的主键。为了便于区别候选键中的属性与其它属性，我们可以得到如下定义。
定义4.5对关系模式R(U)，包含在任何一个候选键中的属性称为主属性(Primary Attribute)，不包含在任何候选键中的属性称为非主属性(Nonprimary Attribute)或非码属性(Non-key Attribtute)。
例4.6 在关系模式StudyInfo(Sno，Sname，DeptName、DeptHead、Cname，Grade)中，{Sno, Cname}是其唯一候选键，因此，Sno和Cname都是主属性，而Sname，DeptName、DeptHead，Grade都是非主属性。
定义4.6 对关系模式R(U)，设X属于U。若X不是R(U)的主键，但X是另一个关系模式的主键，则称X是R(U)的外键或外部关键字(Foreign key)。
例4.7 在Reports(Sno, Cname, Grade)中，Sno不是关系模式Reports的主键，但Sno是关系模式Students (Sno, Sname, DeptName)中的主键。因此，Sno是关系模式Reports(Sno, Cname,Grade)的外键。主键与外键提供了一个表示两个关系中元组(实体)之间联系的手段。在数据设计中，经常人为地增加外键来表示两个关系中元组之间的联系。当两个关系进行连接操作时就是因为又外键在起作用。比如，我们需要查看每个学生的姓名、选课名称和成绩时，就涉及到Students(Sno, Sname, DeptName)和Reports(Sno, Cname,Grade)对应关系的连接操作，这时，只要使用第3章介绍的如下SQL命令即可。 SELECT Sname, Cname, Grade FROM Students, Reports WHERE Students.Sno=Reports.Sno。
四.函数依赖的推理规则
在讨论函数依赖时会遇到这样的问题：以知关系模式R(U,F)的函数依赖集F={A->B，B->C}。问A->C是否成立? ，其中属性集U={A, B, C}。这是本节后面将讨论的有关问题，其内容安排如下：函数依赖的逻辑蕴涵 Armstrong公理系统函数依赖推理规则的完备性闭包的计算函数依赖集的等价和覆盖
1.函数依赖的逻辑蕴涵
在介绍函数依赖的推理规则之前，先介绍两个函数依赖的逻辑蕴涵和闭包概念。
定义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}。
通常，F包含于F+。若F=F+，称F是函数依赖完备集。然而，对于给定的函数依赖集F和属性集X，Y，仅有定义4.7和定义4.8还难于回答F是否逻辑蕴涵X?Y的问题。当然，我们可以先计算F+，然后检查X->Y是否属于F+即可。但现在也没有计算一个函数依赖集F的闭包F+的方法。这些问题需要学习了Armstrong公理系统和函数依赖的推理规则等知识以后才能够解决。
2.Armstrong公理系统
通俗说，Armstrong公理系统是函数依赖基本推理规则的集合，又称Armstrong推理规则系统。 Armstrong公理系统设有关系模式R(U, F)，F是只涉及到U中属性的函数依赖集。若X，Y，Z，W均是U的子集，则有以下推理规则： ⑴ 自反律 (Reflexivity Rule)：如果Y?X?U，则X?Y成立，即F?X?Y。 ⑵ 增广律(Augmentation Rule)：如果X?Y成立, 则XZ?YZ 成立(其中XZ是X?Z的简单记法，其它类同)，即若F?X?Y，则F?XZ?YZ。 ⑶ 传递律(Transitivity rule)：如果X?Y，Y?Z成立，则X? Z成立，即若F?X?Y，F?Y?Z，则F若F? X?Z。
定理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+。
例4.8 设关系模式R(U,F)，其中U＝{A, B, C}，函数依赖集F＝{A?B, B?C}。则有： A+＝{A, B, C} B+＝{B, C} C+＝{C}
3.闭包的计算
前面我们曾经提到，为了判断函数依赖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+。