规范化理论详解.doc

闭包概念 　　以下是写的比较科学规范的闭包求解方法，设X和Y均为关系R的属性集的子集，F是R上的函数依赖集，若对R的任一属性集B，一旦X→B，必有B?Y，且对R的任一满足以上条件的属性集Y1 ，必有Y?Y1，此时称Y为属性集X在函数依赖集F下的闭包，记作X＋。? 　　计算关系R的属性集X的闭包的步骤如下：? 　　第一步：设最终将成为闭包的属性集是Y，把Y初始化为X；? 　　第二步：检查F中的每一个函数依赖A→B，如果属性集A中所有属性均在Y中，而B中有的属性不在Y中，则将其加入到Y中；? 　　第三步：重复第二步，直到没有属性可以添加到属性集Y中为止。 最后得到的Y就是X＋ ??????例（1）：?? 设有关系模式R(U，F)，其中U={A，B，C，D，E，I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算(AE)+ ????????解: ?(1) 令X={AE}，X(0)=AE ???????? ???? (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖，结果是: A→D， E→C；所以 X(1)=X(0)DC=ACDE， 显然 X(1)≠X(0). ??????????????(3) 在F中寻找尚未使用过的左边是ACDE的子集的函数依赖， 结果是: CD→I；所以 X(2)=X(1)I=ACDEI。虽然X（2）≠X(1)，但F中寻找尚未使用过函数依赖的左边已经没有X（2）的子集，所以不必再计算下去，即(AE)+=ACDEI。 　　　说白话一点：闭包就是由一个属性直接或间接推导出的所有属性的集合。 ???????? 例如：f={a-b，b-c，a-d，e-f}；由a可直接得到b和d，间接得到c，则a的闭包就是{a，b，c，d} ? 候选码的求解理论和算法 　　对于给定的关系R（A1，A2，…An）和函数依赖集F，可将其属性分为4类： 　　　　L类? 仅出现在函数依赖左部的属性。 　　　　R 类? 仅出现在函数依赖右部的属性。 　　　　N 类? 在函数依赖左右两边均未出现的属性。 　　　　LR类? 在函数依赖左右两边均出现的属性。 　　定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，则X必为R的任一候选码的成员。 　　推论：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，且X+包含了R的全部属性；则X必为R的唯一候选码。 　　例（2）：设有关系模式R（A，B，C，D），其函数依赖集F={D→B，B →D，AD →B，AC →D}，求R的所有候选码。 　　?????? 解：考察F发现，A，C两属性是L类属性，所以AC必是R的候选码成员，又因为（AC）+=ABCD，所以AC是R的唯一候选码。 　　定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是R类属性，则X不在任何候选码中。 　　定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是N类属性，则X必包含在R的任一候选码中。 推论：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类和N类组成的属性集，且X+包含了R的全部属性；则X是R的唯一候选码。 最小函数依赖集，U={A,B,C,D,E,G} F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→AG}，求F的最小函数解1：利用算法求解，使得其满足三个条件　　① 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}　　② 去掉F中多余的函数依赖　　A．设AB→C为冗余的函数依赖，则去掉AB→C，得：F1={D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G}　　计算(AB)F1+：设X(0)=AB　　计算X(1)：扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。　　(AB)F1+= AB不包含C，故AB→C不是冗余的函数依赖，不能从F1中去掉。　　B．设CG→B为冗余的函数依赖，则去掉CG→B，得：F2={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→A,CE→G}　　计算(CG)F2+：设X(0)=CG　　计算X(1)：扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。　　计算X(2)：扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到一个CG→D函数依赖。故有X(2)=X(1)∪D=ACDG