最近涉及了数据库设计规范的一些原理东西,整理整理。

概念

设U是关系模式R的属性集,F是R上成立的只涉及到U中属性的函数依赖集。FD的推理规则如下(比较有用的规则):

  • A1(自反性,reflexivity):若Y⊆X⊆U,则X→Y在R上成立。
  • A2(增广性,augmentation):若X→Y在R上成立,且Z⊆U,则XZ→YZ在R上成立。
  • A3(传递性,transitivity):若X→Y和Y→Z在R上成立,则X→Z在R上成立。
  • A4(合并性,union):{ X→Y,X→Z }⊨X→YZ。
  • A5(分解性,decomposition):{ X→Y,Z⊆Y }⊨X→Z。
  • A6(伪传递性):{ X→Y,WY→Z }⊨WX→Z。
  • A7(复合性,composition):{ X→Y,W→Z }⊨XW→YZ。
  • A8 { X→Y,W→Z }⊨X ∪(W-Y)→YZ。

需要注意的是求最小依赖集用的最多的是A5,也就是将右边双属性变为单属性。

定义

什么是属性集的闭包?

设F是属性集U上的FD集,X是U的子集,那么(相对于F)属性集X的闭包用X+表示,它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合:X+ ={ 属性A | X→A在F+中 }

一个有用的定理:

X→Y能用FD推理规则推出的充分必要条件是Y⊆X+

算法

理论算法:求属性集X相对于FD集F的闭包X+

设属性集X的闭包为closure,
closure=X;
do 
{ if F中有某个FD U→V 满足
      U ⊆ closure
      then  closure=closure ∪ V;
} while (closure有所改变);

结束的条件

上述算法中结束的条件如下:(满足任何一条即可)

  1. x(i+1) = x(i)

       
       也就是后一个结果和前面相同了
  2. 发现x(i)包含了全部的属性
  3. 在F中的函数依赖的右部属性中,再也找不到x(i) 中未出现的属性
  4. 在F中未用过的函数依赖的左部属性中已经没有x(i)的子集

举例

已知关系R,其属性集U={A,B,C,D,E},F={AB→C, B→D, C→E, EC→B, AC→B},求属性集AB相对于F的闭包(AB)+

  1. 另X(0)=AB
  2. X(1)=X(0) ∪ C ∪ D=ABCD

        因为B在AB中且AB也在AB中,因此2成立,下面依次类推即可
  3. X(2)=X(1) ∪ E ∪ B =ABCDE

        此时条件结束,while循环结束,因为已经包含了{ABCDE}全部属性
    

答案:(AB)+ = ABCDE

其他

有一个练习如下:

postbird