闭包和函数最小依赖集的求法(含例题)

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 等价。算法：计算最小函数依赖集。输入 一个函数依赖集输出 f 的一个等价的最小函数依赖集g 步骤： 用

2、分解的法则，使f 中的任何一个函数依赖的右部仅含有一个属性； 去掉多余的函数依赖： 从第一个函数依赖xy 开始将其从 f 中去掉， 然后在剩下的函数依赖中求x的闭包 x+， 看 x+是否包含 y， 若是， 则去掉 xy；否则不能去掉，依次做下去。直到找不到冗余的函数依赖； 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如xy a，若要判 y为多余的，则以xa 代替 xy a 是否等价？若 a (x)+ ，则 y是多余属性，可以去掉。举例：已知关系模式r ，u=a,b,c,d,e,g ，f=abc,deg,c a,bec,bc d,cg bd,acd b,ce ag ，

3、求f 的最小函数依赖集。解 1：利用算法求解，使得其满足三个条件 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得 f 为：f=abc,de,dg,c a,bec,bc d,cg b,cg d,acd b,ce a,ce g 去掉 f 中多余的函数依赖a设 ab c 为冗余的函数依赖，则去掉ab c ，得：f1=de,dg,c a,bec,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

4、，算法终止。(ab)f1+= ab 不包含 c，故 ab c 不是冗余的函数依赖，不能从f1中去掉。b设 cg b 为冗余的函数依赖，则去掉cg b，得：f2=abc,de,dg,c a,bec,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=ac

5、dg。计算 x(3) ：扫描 f2中的各个函数依赖，找到左部为acdg 或 acdg 子集的函数依赖，得到两个acd b 和 d e 函数依赖。故有 x(3)=x(2) be=abcdeg，因为 x(3)=u，算法终止。(cg)f2+=abcdeg 包含 b，故 cg b 是冗余的函数依赖，从f2中去掉。c设 cg d 为冗余的函数依赖，则去掉cg d ，得：f3=ab c,de,dg,c a,bec,bc d,acd b,ce a,ce g计算(cg)f3+：设 x(0)=cg 计算 x(1) ：扫描 f3中的各个函数依赖，找到左部为cg或 cg子集的函数依赖，得到一个 c a 函数依赖。故

6、有 x(1)=x(0) a=cga=acg。计算 x(2) ：扫描 f3中的各个函数依赖，找到左部为acg 或 acg 子集的函数依赖，因为找不到这样的函数依赖。故有x(2)=x(1) ，算法终止。 (cg)f3+=acg 。(cg)f3+=acg 不包含 d，故 cg d 不是冗余的函数依赖，不能从f3中去掉。d设 ce a 为冗余的函数依赖，则去掉ce a，得：f4=ab c,de,dg,c a,bec,bc d,cg d,acd b,ce g计算(cg)f4+：设 x(0)=ce 计算 x(1) ：扫描 f4中的各个函数依赖，找到左部为ce或 ce子集的函数依赖，得到一个 c a 函数依

7、赖。故有 x(1)=x(0) a=cea=ace。计算 x(2) ：扫描 f4中的各个函数依赖，找到左部为ace或 ace子集的函数依赖，得到一个 ce g 函数依赖。故有 x(2)=x(1) g=aceg。计算 x(3) ：扫描 f4中的各个函数依赖，找到左部为aceg 或 aceg 子集的函数依赖，得到一个cg d 函数依赖。故有 x(3)=x(2) d=acdeg。计算 x(4) ：扫描 f4中的各个函数依赖，找到左部为acdeg 或 acdeg 子集的函数依赖，得到一个 acd b 函数依赖。故有 x(4)=x(3) b=abcdeg。 因为 x(4)=u，算法终止。(ce)f4+=a

8、bcdeg 包含 a，故 ce a 是冗余的函数依赖，从f4中去掉。 去掉 f4 中各函数依赖左边多余的属性 （只检查左部不是单个属性的函数依赖）由于 c a，函数依赖 acd b 中的属性 a是多余的，去掉a得 cd b。故最小函数依赖集为：f=abc,de,dg,c a,bec,bc d,cg d,cd b,ce g解 2：利用 armstrong 公理系统的推理规则求解 假设 cg b 为冗余的函数依赖， 那么，从 f中去掉它后能根据armstrong公理系统的推理规则导出。因为 cg d （已知）所以 cga ad ，cga acd （增广律）因为 acd b （已知）所以 cga b （传递律）因为 c a （已知）所以 cg b （