《数据库最小函数依赖集》由会员分享，可在线阅读，更多相关《数据库最小函数依赖集（5页珍藏版）》请在金锄头文库上搜索。
1、一、等价和覆盖一、等价和覆盖 定义：关系模式 R上的两个依赖集 F 和 G，如果 F+=G+，则称 F 和 G 是等价的，记做FG。若 FG，则称 G 是 F 的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。 二、最小函数依赖集二、最小函数依赖集 定义：如果函数依赖集 F 满足下列条件，则称 F 为最小函数依赖集或最小覆盖。 F 中的任何一个函数依赖的右部仅含有一个属性； F 中不存在这样一个函数依赖 XA，使得 F 与 F-XA等价； F 中不存在这样一个函数依赖 XA，X 有真子集 Z 使得 F-XAZA与 F 等价。 算法：计算最小函数依赖集。 输入 一个函数依赖集
2、输出 F的一个等价的最小函数依赖集 G 步骤：步骤： 用分解的法则，使 F 中的任何一个函数依赖的右部仅含有一个属性； 去掉多余的函数依赖：从第一个函数依赖 XY 开始将其从 F 中去掉，然后在剩下的函数依赖中求 X 的闭包 X+，看 X+是否包含 Y，若是，则去掉 XY；否则不能去掉，依次做下去。直到找不到冗余的函数依赖； 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如 XYA，若要判 Y 为多余的，则以 XA 代替XYA 是否等价？若 A (X)+，则 Y 是多余属性，可以去掉。 举例：举例：已知关系模式 R，U=A,B,C,D,E,G， F=ABC,DEG,C
3、A,BEC,BCD,CGBD,ACDB,CEAG，求 F的最小函数依赖集。 解 1：利用算法求解，使得其满足三个条件 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得 F 为： F=ABC,DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG 去掉 F 中多余的函数依赖 A设 ABC 为冗余的函数依赖，则去掉 ABC，得： F1=DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG 计算(AB)F1+：设 X(0)=AB 计算 X(1)：扫描 F1 中各个函数依赖，找到左部为 AB 或 AB 子集的函数依赖，因为找不到这样的函数依赖。
4、故有 X(1)=X(0)=AB，算法终止。 (AB)F1+= AB 不包含 C，故 ABC 不是冗余的函数依赖，不能从 F1中去掉.B设 CGB 为冗余的函数依赖，则去掉 CGB，得： F2=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEA,CEG 计算(CG)F2+：设 X(0)=CG 计算 X(1)：扫描 F2 中的各个函数依赖，找到左部为 CG 或 CG 子集的函数依赖，得到一个 CA 函数依赖。故有 X(1)=X(0)A=CGA=ACG。 计算 X(2)：扫描 F2 中的各个函数依赖，找到左部为 ACG 或 ACG 子集的函数依赖，得到一个 CGD 函数依赖。故有 X
5、(2)=X(1)D=ACDG。 计算 X(3)：扫描 F2 中的各个函数依赖，找到左部为 ACDG 或 ACDG 子集的函数依赖，得到两个 ACDB 和 DE 函数依赖。故有 X(3)=X(2)BE=ABCDEG，因为 X(3)=U，算法终止。 (CG)F2+=ABCDEG 包含 B，故 CGB 是冗余的函数依赖，从 F2 中去掉。C设 CGD 为冗余的函数依赖，则去掉 CGD，得： F3=ABC,DE,DG,CA,BEC,BCD,ACDB,CEA,CEG 计算(CG)F3+：设 X(0)=CG 计算 X(1)：扫描 F3 中的各个函数依赖，找到左部为 CG 或 CG 子集的函数依赖，得到一个
6、 CA 函数依赖。故有 X(1)=X(0)A=CGA=ACG。 计算 X(2)：扫描 F3 中的各个函数依赖，找到左部为 ACG 或 ACG 子集的函数依赖，因为找不到这样的函数依赖。故有 X(2)=X(1)，算法终止。(CG)F3+=ACG。 (CG)F3+=ACG 不包含 D，故 CGD 不是冗余的函数依赖，不能从 F3 中去掉。D设 CEA 为冗余的函数依赖，则去掉 CEA，得： F4=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEG 计算(CG)F4+：设 X(0)=CE 计算 X(1)：扫描 F4 中的各个函数依赖，找到左部为 CE 或 CE 子集的函数依赖，得到一
7、个 CA 函数依赖。故有 X(1)=X(0)A=CEA=ACE。 计算 X(2)：扫描 F4 中的各个函数依赖，找到左部为 ACE 或 ACE 子集的函数依赖，得到一个 CEG函数依赖。故有 X(2)=X(1)G=ACEG。 计算 X(3)：扫描 F4 中的各个函数依赖，找到左部为 ACEG 或 ACEG 子集的函数依赖，得到一个 CGD 函数依赖。故有 X(3)=X(2)D=ACDEG。 计算 X(4)：扫描 F4 中的各个函数依赖，找到左部为 ACDEG 或 ACDEG 子集的函数依赖，得到一个 ACDB 函数依赖。故有 X(4)=X(3)B=ABCDEG。因为X(4)=U，算法终止。 (
8、CE)F4+=ABCDEG 包含 A，故 CEA 是冗余的函数依赖，从 F4 中去掉。 去掉 F4 中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于 CA，函数依赖 ACDB 中的属性 A 是多余的，去掉 A 得CDB。 故最小函数依赖集为： F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG解 2：利用 Armstrong 公理系统的推理规则求解 假设 CGB为冗余的函数依赖，那么，从 F 中去掉它后能根据 Armstrong 公理系统的推理规则导出。 因为 CGD （已知） 所以 CGAAD，CGAACD （增广律） 因为 ACDB （已知） 所以 CGAB （传递律） 因为 CA （已知） 所以 CGB （伪传递律） 故 CGB 是冗余的。 同理可证：CEA 是多余的。 又因 CA，可知函数依赖 ACDB 中的属性 A 是多余的，去掉 A得 CDB。 故最小函数依赖集为： F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG
