范式

范式

UNF：不属于范式体系内，包含了复合属性和多值属性

第一范式：若关系模式$R(U)$中关系的每个分量都是不可分的数据项（值，原子），则称$R(U)$属于第一范式，记为$R(U) \in 1NF$，处理办法是将复合属性处理为简单属性，或者将多值属性与关键字单独组合称新的关系。

第二范式：为了进一步减少更新异常，第二范式消除了非主属性对候选键的部分函数依赖。若$R(U) \in 1NF$，且$U$中每一个非主属性完全函数依赖于候选键。

举个例子$A \rightarrow C, B \rightarrow D$，不难得出$AB \rightarrow CD$，其中$A,B$为候选键，$C,D$为非主属性，因为存在$A \rightarrow C, B \rightarrow D$非主属性部分依赖于候选键，所以不满足第二范式。处理办法是拆成两个表，比如对于这个例子拆成$AC,BD$两个表，这样，$AC,BD$均满足了第二范式。

所以，第二范式满足了非主属性对候选键的完全函数依赖。

需要说明，非主属性在COMP9311中的定义为不属于所有候选键的属性

第三范式：在$2NF$基础上，消除非主属性对键的传递依赖。参考

举个例子$A \rightarrow C, C \rightarrow DE$，并且$C$不是$A$的子集，$DE$不是$C$的子集，也不是$A$的子集，$C$也不可以函数决定$A$，这满足了传递函数依赖，所以同时也不满足第三范式，处理办法还是拆，这里就拆成$AC,CDE$，这样$AC,CDE$各自均满足了第三范式。

判断当前的关系模式为第几范式

比如对于ABCDEF

A->BCDEF
BC->ADEF
D->E
B->F

先判断是否满足第二范式，根据BC->ADEF，不满足第二范式，所以为第一范式；但不难发现对于A->BCDEF有A->D，并且D->E，D非A的子集，E非D的子集也非A的子集，D也不能函数依赖决定A，不满足第三范式。

分解B->F
R'(ABCDE)
A->BCDE
BC->ADE
D->E
R1(BF)
B->F
目前为止，已经满足了第二范式，继续分解
分解D->E
R''(ABCD)
A->BCD
BC->AD
R2(DE)
D->E
目前为止，R1(BF) B->F, R2(DE) D->E, R''(ABCD) A->BCD BC->AD 均满足了第三范式。

BCNF：若$R(U,F) \in 1NF$，若对于任何$X \rightarrow Y \in F$，如果$X \rightarrow Y$满足非平凡函数依赖，$X$必含有候选键（X可以是候选键，也可以是超键，但不可以为候选键的一部分），则称$R(U)$属于$BCNF$。

如何分解？

假如给定的ABCDEF添加D->B

A->BCDEF
BC->ADEF
D->E
B->F
D->B

接着将B->F,D->E分解得到第三范式，D->B中，D不包含候选键，需要分解

R1(BF) B->F
R2(DE) D->E
R'''(ABCD) D->B 分解
R''''(ACD) A->CD
R3(DB) D->B

最小覆盖

R={A,B,C,D,E,G}
F={A->BCD,B->CDE,AC->E}

步骤:

• 展开右侧（为了满足定义1，FD的右侧只能有一个属性）
  A->B
  A->C
  A->D
  B->C
  B->D
  B->E
  AC->E
• 展开左侧（为了满足定义3，X->A成立，如果Z是X的子集，那么F-(X->A)∪(Z->A)不等价于F）
  对于AC->E，删除A，判断C的闭包是否能得到E，不能；删除C，判断A的闭包是否能得到E，可以
  这样就说明AC->E可以由A->E替代
  A->B
  A->C
  A->D
  B->C
  B->D
  B->E
  A->E
• 删除FD中的冗余项，挨个删除，根据化简得到的FD来判断
  删除A->B，看A的闭包能否得到B，不能
  删除A->C，看A的闭包能否得到C，可以
  删除A->D，看A的闭包能否得到D，可以
  删除B->C，看B的闭包能否得到C，不能
  删除B->D，看B的闭包能否得到D，不能
  删除B->E，看B的闭包能否得到E，不能
  删除A->E，看A的闭包能否得到E，可以
• 剩下来A->B,B->C,B->D,B->E

注意：如果有互相指向，有不同的结果

有过简化的思路，对于
A->B
A->C
A->D
B->C
B->D
B->E
A->E
两边只出现一次的不能删，比如B在右边只出现一次，不能删，CDE在右侧各出现两次，所以A->C,A->D,A->E删了。