第3小节 属性集的闭包.doc

第3小节 属性集的闭包 知识要点 1 函数依赖集与函数依赖集的闭包 F：FD的集合称为函数依赖集。F闭包：由F中的所有FD可以推导出所有FD的集合，记为F+。例3-25 对于关系模式R(ABC)，FAB,BC，求F+。根据FD的定义，可推出F+=,A,AA,AB,AC,AAB,ABC,AABC,，共有43个FD。其中，表示空属性集。2 属性集闭包定义 对F，F+中所有XA的A的集合称为X的闭包，记为X+。如上例：A+ABC结论：X+表示所有X可以决定的属性。 如上例：A+ABC表示AABC，以S(sno,sname,sex)(无同名)讲解。若X+包含R的所有属性，则X是超键。当X不可约时则为候选键。 如上例：A+ABC，则A为超键，因为A不可约则为候选键。(AB)+ABC，则AB为超键，因为AB可约则不为候选键，以S(sno,sname,sex)讲解。F+是指数级计算，而XY属于F+的必要充分条件是：Y是X+的子集。即不求F+，但可以判断FD是否属于F+。 如上例：R(ABC)，F=AB,BCF+=,A,AA,AB,AC,AAB,ABC,AABC,例3-26 对例3-25的关系模式R，求其候选键并判断AC和BA是否属于F。根据属性集闭包的定义可知：A+=ABC，B+=BC，C+=C。由于A+包含R的所有属性，则R候选键为A。由于C A+而A B+，则AC F而BA F。3 属性集闭包算法 A+：将A置入A+。对每一FD，若左部属于A+，则将右部置入A+。重复至A+不能扩大。例3-27 对于关系模式R(ABCD)，FAB,BC,DB，求其候选键。(1) 求A+。 A+A。 由AB，而A A+可知，则A+AB。 由BC，而B A+可知，则A+ABC。 A+封闭，即A+ABC。(2) 求B+、C+、D+。按步骤(1)可得：B+BC，C+C，D+BCD。(3) 求其候选键。显然，R的候选键为AD。例3-28 对于关系模式R(ABC)，F=ABC,BCA，求其候选键。(1) 求属性的闭包。按例3-27可得：A+ABC，B+B，C+C。(2) 求属性集的闭包。由BCA，则(BC)+ABC，其余属性集闭包为属性闭包的并集。(3) 求其候选键。显然，R的候选键为A和BC。4 FD集的最小依赖集 定义：对R(U)上的F1、F2，若F1+=F2+，则称F1与F2等价。eg. R(ABC)，F1=AB,ABC,DAC,DE与F2=ABC,DAE等价？ 对F1：A+ABC，B+B，C+C，D+ABCDE，E+E，(AB)+ABC。 对F2：A+ABC，B+B，C+C，D+ABCDE，E+E，(AB)+ABC。 故F1与F2等价。 定义：Fmin是F的最小依赖集的必要充分条件为： Fmin+=F+。 (重点)每个FD的右部是单属性。 Fmin中没有冗余的FD，即删除任何一个FD则不等价。 每个FD左部无冗余属性（即删除任一属性即不等价），称左部不可约。 结论：要实现一个F，只要实现Fmin即可。 每个F均存在一个Fmin，但不惟一。作业及练习 1 设关系模式R(ABCD)，FAB,BC，试写出(1) 属性集BD的闭包(BD)+。(2) 所有左部为B的FD，即形为“B?”的FD。2 设关系模式R(ABC)，FAB,BC，试写出F+中的43个FD。3 设关系模式R(ABCD)，FAB,CB，试写出R的候选键。4 设关系模式R(ABCD)，假设B与D为一对多联系，而A与C为一对