函数依赖闭包

一、函数依赖的逻辑蕴涵
 
定义：设有关系模式R(U)及其函数依赖集F，如果对于R的任一个满足F的关系r函数依赖X→Y都成立，则称F逻辑蕴涵X→Y，或称X→Y可以由F推出。

例：关系模式 R=(A,B,C),函数依赖集F={A→B,B→C}, F逻辑蕴涵A→C。

证：设u,v为r中任意两个元组：
      若A→C不成立，则有u[A]=v[A],而u[C]≠v[C]
      而且A→B, B→C,知
      u[A]=v[A], u[B]=v[B], u[C]=v[C],
      即若u[A]=v[A]则u[C]=v[C]，和假设矛盾。
      故F逻辑蕴涵A→C。

满足F依赖集的所有元组都函数依赖X→Y（X→Y不属于F集），则称F逻辑蕴涵X→Y
（X→Y由F依赖集中所有依赖关系推断而出）

二、Armstrong公理 

 1、定理：若U为关系模式R的属性全集，F为U上的一组函数依赖，设X、Y、Z、W均为R的子集，对R(U,F)有：

        F1(自反性)：若X≥Y(表X包含Y），则X→Y为F所蕴涵；(F1':X→X)
        F2(增广性): 若X→Y为F所蕴涵，则XZ→YZ为F所蕴涵；(F2':XZ→Y)
        F3(传递性): 若X→Y,Y→Z为F所蕴涵，则X→Z为F所蕴涵；
        F4(伪增性)：若X→Y，W≥Z(表W包含Z）为F所蕴涵，则XW→YZ为F所蕴涵；
        F5(伪传性): 若X→Y，YW→Z为F所蕴涵, 则XW→Z为F所蕴涵；

        F6(合成性): 若X→Y,X→Z为F所蕴涵，则X→YZ为F所蕴涵；
        F7(分解性): 若X→Y,Z≤Y (表Z包含于Y）为F所蕴涵，则X→Z为F所蕴涵。

        函数依赖推理规则F1∽F7都是正确的。

 2、Armstrong公理：

推理规则F1、F2、F3合称Armstrong公理；
F4 ∽ F7可由F1、F2、F3推得，是Armstrong公理的推论部分。

 三、函数依赖的闭包 

定义：若F为关系模式R(U)的函数依赖集，我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包，记为F+。
即：F+={X→Y|X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”}

      △ F包含于F+，如果F=F+，则F为函数依赖的一个完备集。

     △ 规定：若X为U的子集，X→Φ 属于F+。

 前面我们曾经提到，为了判断函数依赖X->Y是否在F+中，只要计算出F+即可。因为F+是由F根据Armstrong公理导出的函数依赖的集合。因此，原则上说，只要按照Armstrong公理系统中的推理规则就可以计算出F+。但是，闭包F+的计算是一件很麻烦的事情，因为计算F+的问题是一个NP完全问题，即若F={X->A1, X->A2, …, X->An,}，则需要计算F+的O(2n)个函数依赖，因此，当 n比较大时，实际计算F+是不可行的。即使F的元素不多时， F+中的元素也可能很多。此外，闭包F+中也存在许多冗余信息。其实，判断一个函数依赖X?Y是否在F+中，完全不必计算闭包F+，因为，由定理4.3可知，只要判断X?Y能否从F根据Armstrong公理导出，即判断Y?X+是否成立即可。这样就把一个需要计算F+才能解决的问题简化为计算X+就能解决得问题。而计算X+并不太难，它所花费的时间与F中的全部函数依赖的长度成正比。下面介绍一个计算X+的算法。
http://xxgcxy.hutc.zj.cn/sjkyl/image/tball.gif 算法4.1 求属性集X?U关于函数依赖集F的闭包X+。
输入：有限的属性集合U、它上面的函数依赖集合F和U的一个子集X。
输出：X关于F的闭包X+。
计算方法和计算步骤：
⑴设置初始值：令X(0)＝空集，X(1)＝X，F'=空集；
⑵如果X(0)≠X(1)，令X(0)＝X(1)，否则转⑷；
⑶构造函数依赖集F'={Y->Z | (Y->Z)属于F且Y?X(1)}，令 F=F-F'
对F'中的每一个函数依赖Y->Z,令X(1)= X(1)∪Z,转⑵
⑷ 输出X(1)，它就是X+。
例4.10 设有关系模式R(A,B,C,D,E)，其属性集上函数依赖：F={AB->C, B->D, C->E, EC->B, AC->B}，这里的AB->C是{A, B}->{C}的简写。
令X={A, B}，求X+。
解： 计算过程是根据循环次数介绍的。由算法4.1 
第一次：⑴ X(0)=空集，X(1)={A, B}，F'=空集；
⑵ 由于X(0)≠X(1)，令X(0)＝X(1)={A, B}；
⑶ 函数依赖集F'={ AB->C, B->D}，令F=F-F'={C->E, EC->B, AC->B}，
将F'中的每一个函数依赖的右端属性C,D并入X(1)中，
即令X(1)={A, B}∪{C, D}={A, B, C, D}；
第二次：⑵ 由于X(0)?X(1)，令X(0)＝X(1)= {A, B, C, D}；
　　      ⑶ 函数依赖集F'={C->E, AC->B}，令F=F- F'={EC->B}，
将F'中的每一个函数依赖的右端属性E, B并入X(1)中，
即令X(1)={A, B, C, D }∪{E, B}={A, B, C, D, E} ；
第三次：⑵ 由于X(0)≠X(1)，令X(0)＝X(1)= {A, B, C, D, E } ；
　　　   ⑶ 函数依赖集F'={EC->B}，令F=F-F'=空集,
将F'中的每一个函数依赖的右端属性B并入X(1)中，
即令X(1)={A, B, C, D, E }∪{B}={A, B, C, D, E}；
第四次：⑵ 由于X(0)=X(1)，转⑷
　　　   ⑷输出X(1)={A, B, C, D, E}=X+。

        例：R=ABC,F={A→B, B→C}, 求F+

      解： F+ ={A→Φ,AB→Φ,AC→Φ,ABC→Φ,B→Φ,C→Φ,
                A→A,AB→A,AC→A,ABC→A,B→B,C→C,
                A→B,AB→B,AC→B,ABC→B,B→C,
                A→C,AB→C,AC→C,ABC→C,B→BC,
                A→AB,AB→AB,AC→AB,ABC→AB,BC→Φ,
                A→AC,AB→AC,AC→AC,ABC→AC,BC→B,
                A→BC,AB→BC,AC→BC,ABC→BC,BC→C,
                A→ABC,AB→ABC,AC→ABC,ABC→A,BC→BC}

       例：已知关系模式R中

           U={A，B，C，D, E, G},
           F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD, CE→AG},判断BD→AC是否属于F+
 
       解：由D→EG知D→E，BD→BE             … ①
           又知BE→C，C→A 所以BE→A, BE→AC … ②
           由①、②知，BD→AC，所以BD→AC被F所蕴涵，即BD→AC属于F+
     
       例：已知关系模式R中
           U={A，B，C，E, H, P, G},
           F={AC→PE, PG→A, B→CE, A→P, GA→B, GC→A, PAB→G, AE→GB, ABCP→H},证明BG→HE属于F+

        证：由B→CE知B→C，B→E, BG→GC         … ①
            又知GC→A，A→P 所以BG→A, BG→ABCP … ②
            又ABCP→H，由①、②知BG→HE，所以BG→HE被F所蕴涵，
            即BG→HE属于F+
 
四、属性集闭包 
　
1、定义：若F为关系模式R(U)的函数依赖集，X是U的子集，则由Armstrong公理推导出的所有X→Ai所形成的属性集

例：设R=ABC,F={A→B, B→C}当X分别为A,B,C是求X+。

解：当X=A时，X+=ABC
    当X=B时，X+=BC
    当X=C时，X+=C

* X代表的属性集可以决定的属性集（包括本身）

2、定理：当且仅当Y属于X+时，X→Y能根据Armstron公理由F导出。

证：设Y=A1,A2,…,An

   ①充分条件：当Y属于X+时,对于每个i,X→Ai可由公理导出。
               再用合并规则可得X→Y。
   ②必要条件：若X→Y能够由公理导出,则根据分解规,
               X→Ai(i=1,2,…,n)成立，所以Y属于X+。

3、计算X+

(1)算法依据：若F为关系模式R(U)的函数依赖集,X,Z,W是U的子集,对于任意的Z→W∈F,若 X≥Z（表X包含Z）,则X→XW。

(2)算法：

a.令X+ = X;
b.在F中依次查找每个没有被标记的函数依赖，若“左边属性集”包含于X+ ，则令 X+ = X+∪“右边属性集”,为被访问过的函数依赖设置访问标记。
c.反复执行b直到X+不改变为止。

（先令X+等于本身，然后在F+中依次查找左边包含于X+的属性，把其右边的对应属性并到X中）

(3)算法实现
               输入：关系模式R的子集X,R上的函数依赖集F。
               输出：X关于F的闭包X+

算法伪语言描述：

 Closure(X,F)
 {
    olds=Φ; news=X; G=F;
    while (olds!=news)
     {
       olds=news;
       for (G中的每个函数依赖W→Z)
        {
          if (news包含W)
            {
               news=news∪Z;
               从G中删除函数依赖W→Z;
             }
         }
     }
   return news;
 }

例：已知关系模式R中
U={A，B，C，D, E, G},
F={AB→C, C→A, BC→D, ACD→B, D→EG, BE→C, CG→BD, CE→AG},
求(BD)+，判断BD→AC是否属于F+

解：X+=BDEGCA
结论：(BD)+=ABCDEG,BD→AC可由F导出，即BD→AC属于F+

例：已知关系模式R中
U={A，B，C，E, H, P, G},
F={AC→PE, PG→A, B→CE, A→P, GA→B,GC→A, PAB→G, AE→GB, ABCP→H},
证明BG→HE属于F+

证：因为,(BG)+ =ABCEHPG,
所以BG→HE可由F导出，即BG→HE属于F+

4、结论

判定函数依赖X→Y是否能由F导出的问题，可转化为求X+并判定Y是否是X+子集的问题。
即求闭包问题可转化为求属性集问题。
判定给定函数依赖X→Y是否蕴涵于函数依赖集F算法实现：

输入：函数依赖集合F,函数依赖X→Y

输出：若X→Y∈F+输出真，否则输出假

算法伪语言描述：
number(F,X→Y)
{ if (Y包含于close(X,F))
      return 真
  else
      return 假
}

 
{Ai|i=1,2,…}称为X对于F的闭包，记为X+。