5关系数据库设计理论.ppt

第五章 关系数据库设计理论 * 用函数依赖定义键 超键：能唯一标识元组的属性集称为关系模式的超键。 候选键：如果一个属性集能唯一标识元组，且不含有多 余的属性，那么这个属性集成为候选键。 定义：如果关系模式R的属性集为A1,A2,…An，F是R上成立 的一个FD集，X是A1,A2,…An的一个子集，如果X－A1,A2, …An在F+中，那么称X是R的一个超键。如果X－A1,A2,…An 在F+中，且对于X的任何一个真子集X1， X1－A1,A2,…An 在都不在F+中，则称X是R的一个候选键。 属性集的闭包 定义：设F是属性集U上的FD集，X是U的子集，那么属性集 X的闭包X+，它是一个从F集使用FD推导规则推出的所有满 足X－A的属性集A的集合： 定理：X－Y能用FD推理规则推出的充分必要条件是 证明：(充分性)根据 ，设Y=A1,A2,…,An。由属性集 闭包定义可知：X－Ai在F+中。再根据合并规则，X－A1, A2,…,An 即X－Y。 (必要性)由X－Y，根据分解规则，X－Ai，根据属性集闭 包定义可得 ，所以 ，即 *用属性集的闭包来定义候选键 定义：如果关系模式R的属性集为U，F是R上成立的一个 FD集，X是U的一个子集，如果X的属性集的闭包X+ =U,则 称X为R的一个超键，如果对于X的任何一个真子集Y， 有Y+≠U。则X为R的一个候选键。 算法：求属性集X关于FD集F的闭包X+ 输入：属性集U，U上的FD集F，X是U的子集 输出：X关于F的闭包X＋ 方法： Result:=X; repeat for F 中的每个FD Y－Z do if then Result:=Result U Z; until (result 没有改变)； Result 即为所求的X+ 例：属性集U为ABCD，FD集为 , 求A+,AD+ A+ (1) Result=A (2) Result=A U B =AB (3) Result=AB U C =ABC AD+ = ABCD 例题： 求BD+ 1) result=BD, AB不含于result，result=BD 2) result=BD，D包含于result,result =BD U EG=BDEG 3) result=BDEG，C不含于result,result=BDEG 4) result=BDEG，BE包含于result,result =BDEG U C=BCDEG 5) result=BCDEG,BC包含于result,result=BCDEG U D=BCDEG 6) result=BCDEG,CG包含于result,result=BCDEG U BD=BCDEG 7) result=BCDEG,ACD不含于result,result=BCDEG 8) result=BCDEG,CE 含于result,result=BCDEGUAG=ABCDEG * 快速求解候选键的充分条件 对于给定的关系模式R=(A1,A2,…,An)和函数依赖集F， 可将其属性分为四类： 1、仅仅出现在F的函数依赖左部的属性L类； 2、仅仅出现在F的函数依赖右部的属性R类； 3、在F的函数依赖的左右两边都没有出现的属性N类； 4、在F的函数依赖的左右两边都出现的属性LR类； 定理：对于给定关系模式R及其函数依赖集F(不包含平凡FD) 1) X是L类属性，则X必为R的任何一个候选键的成员。 2) X是R类属性，则X不包含在任何候选键中。 3) X是R的N类属性，则X也必为R的任何一个候选键的成员。 4) X是R的LR类属性，则X可能是也可能不是候选键的成员。 1) 反证法：设W为R的任一候选键，X不是W的成员。由于 X仅仅出现在F的函数依赖左部，所以R中没有其它属性能 够函数决定X，这样W+中就不可能包含X，这样就与W是R的 候选键相矛盾。所以X必然是候选键W的成员。 （X为L类的情况） 2) 反证法：设W是R的任一候选键，X不是W的成员。由于X 没有出现在F中，那么R中没有其它属性能够函数决定X。 这样W+中就不可能包含X，这与W是R的候选键相矛盾。所以 X必然是候选键W的成员。 （X是N类的情况） 例：设有关系模式R(A,B,C,D)，其函数依赖集F如下， 求R的候选键。 传统步骤：1、分别求A/B/C/D/AB/AC/AD/BC/BD/CD ABC/ABD/ACD/BCD/ABCD的属性集的