规范化

同样是一种将现实中的实体抽象为数据库表的一种数据库设计方法。在规范化中比较关键的一个概念就是函数依赖。可以说数据库模式(Schema)就是由所有表标题（属性）和其上的函数依赖的集合。

函数依赖

概念

对于一张表中的两个属性集A和B，如果能够从两行A属性集属性相同这个条件，推出这两行B属性集的属性也完全相同，那么就说B函数依赖于A，或者A函数决定B，记作A->B。

首先要注意A和B是两个属性集，也就意味这可能有多个属性。通俗的理解，A函数决定B 就是说，一旦A属性集中的所有属性确定了，那么B也就被唯一确定了，类似函数中自变量和因变量之间的关系。

推导

可以使用Armstrong公理从一些函数依赖导出新的函数依赖关系。下面的字母表示的都是属性集。这三大公理分别是：

  1. 自反规则（又称作包含规则）：如果Y是X的子集，那么X->Y
  2. 传递规则：如果X->Y且Y->Z则X->Z
  3. 增广规则：如果X->Y则XZ->YZ。注意XZ就是X和Z两个属性集的并集，即X∪Z

如果说上面的公理有些细碎，那么可以直接使用下面的定理，他们都是从公理导出的，使用起来也更为方便：

  1. 合并规则：如果X->Y且X->Z那么X->YZ
  2. 分解规则：如果X->YZ则X->Y且X->Z
  3. 伪传递规则：如果X->Y且WY->Z则XW->Z
  4. 聚集规则：如果X->YZ且Z->W则X->YZW

上面这些东西说了也没人能明白，下面就用人话解释一下：

函数依赖可以理解成左边控制右边，可以看成是强决定弱的关系。

在->关系符号左边的变量越多，左边越强；同理右边的变量越多，右边越强。这样看来，如果有一个已存在的函数决定关系，那么在左边多放任意属性集，或者在右边去掉任意属性集，都是仍然成立的。那么如果想在右边加上一些属性集还要关系仍然成立，就要多一些其他的约束，这个多的约束就是“左边的属性集能够决定右边多加出来的属性集”，也就对应合并规则。同理，如果想在左边去掉一些属性集还要关系仍然成立，也要一个额外的约束，这个约束就是“去掉一些属性集后的左边，能够函数决定原来的左边”，这就是传递规则。最后，左右边可以同时加上或减掉同一个属性集，也就是增广规则。总结一下：

如果给出关系AB->CD，那么有

  1. 左边随便加一些码还成立，如ABE->CD还成立
  2. 右边随便减一些码还成立，如AB->C
  3. 如果有AB->E，那右边可以加一个E码，也就是AB->CDE成立
  4. 如果有A->AB，那么左边可以减掉没必要的B码，也就是A->CD成立
  5. 左右同时加上或减去一个码，还成立。例如ABE->CDE成立

个人觉得这对后面计算函数依赖集的覆盖等等要有帮助，如有错误欢迎指出。

函数依赖集的闭包

函数依赖集，顾名思义就是函数依赖关系的集合，通常用F或者H表示。

函数依赖集的闭包，指的是根据给出的函数依赖集中的关系，能够推导出的所有函数依赖的集合。如果原来的函数依赖集是F，则闭包表示为F+（右上角小加号，不便打字qwq）

计算算法包含以下步骤：

  1. F中的所有依赖关系都包含到F+中
  2. 由包含规则展开所有的函数依赖左边
  3. 由传递规则计算新依赖
  4. 由增广规则左右同时加码。
  5. 由合并规则合并出新的依赖。
  6. …

由于闭包通常非常大，一般不会让计算qwq

函数依赖集的覆盖

一个函数依赖集F覆盖另一个函数依赖集G，就是说G中的所有函数依赖关系都能用F中已有的关系推导出来。

如果F和G互相覆盖，就说他们是等价的。

属性集的闭包

指的是，给定一个属性集X和一个函数依赖集F，那么X的闭包X+就是所有X这个属性集能够确定的所有属性的集合。属性集的闭包也是一个属性集。

求属性集闭包的算法：

先取X+为X，重复下列步骤直到X==X+：先将X赋值为X+，然后遍历所有F中的函数依赖f，如果f的左侧属性集是X的子集，就把f的右侧属性集并入X+。

通俗来讲，就是不断迭代找这个属性集X能控制的最大范围。

最小覆盖

对于一个函数依赖集F，如果我们可以找到一个最为精简的表达方式G，保持G能够覆盖F（也就意味着F和G应该是等价的），那么我们就说G是F的最小覆盖。通俗理解就是用更精简的方式描述同一个依赖集的所有函数依赖关系。

这个最精简的严格定义是这样的：

  • 没有冗余的函数依赖，即函数依赖的数量越少越好。
  • 每个函数依赖的左边都没有多余的属性。

求最小覆盖的算法：

  1. 将F的所有函数依赖拆分为右边只有单个属性的形式。
  2. 遍历尝试去掉所有非关键的函数依赖。非关键指的是即使去掉了也不影响函数依赖集的闭包，即对函数依赖集没有影响的多余依赖。
  3. 遍历尝试用左边更少属性的函数依赖替换原来的函数依赖关系。
  4. 如果3对结果有了修改，就重新回到2再次检查有没有多余的依赖，反复2~3直到3处不会再发生修改。
  5. 合并结果中的左边相同的依赖。

其中第二步和第三步如果用属性集闭包的方法，会比较方便：

  • 第二步判断一个函数依赖f能不能去掉的时候，先假设f可以去掉，得到一个没有f的函数依赖集F1。然后计算f左边的属性集X在F1上的属性集闭包X+，如果f的右边属性集已经被包含在X+中，说明即使缺少这个f不影响X的控制范围，那么就把f去除。反之，如果发现f的右边属性集有的属性已经不再X+中了，说明f是必不可少的，f不能去掉。一言，尝试去掉，然后计算旧的依赖左侧在新依赖集上的闭包。
  • 第三步：从第二步得到结果F，判断其中一个函数依赖f的左侧属性集（例如AB->C的左侧属性集{A,B}）能不能精简的时候，先假设可以精简掉A，剩下B->C，称之为f1。然后计算f1的左侧（也就是{B}）在F上的属性集闭包，如果f1的右侧在这个闭包中，就说明去掉A只剩B仍可以控制C，A确实可以精简掉；否则说明B不能单独控制C，一旦精简掉之后就出现了之前没有的函数依赖关系，这是不允许的，那么A是不能精简的。一言，尝试去掉然后计算新的依赖左侧在旧依赖集上的闭包。

表的规范化

表的规范化就是把一张大表分成若干小表的分解过程。

一个数据库模式Schema就是所有表的标题(属性)和其上的函数依赖的集合。任何会破坏函数依赖的插入将失败。

有损分解和无损分解

如果将一个表T分解为若干小表T1,T2,T3…Tn，那么

  • 如果T1∞T2∞T3∞…∞Tn的结果和T一定是一致的，那么这个分解是无损分解。
  • 如果T1∞T2∞T3∞…∞Tn的结果可能比T多出一些行，那么这个分解是有损分解。

应该杜绝有损分解，因为会造成数据库异常。

无损分解的条件

把T分解为T1，T2两张表，Head(T1)和Head(T2)分别是两张表的属性集。如果：Head(T1)∩Head(T2)->HeadT1或者Head(T1)∩Head(T2)->HeadT2两个条件任意一个成立，则这次分解是无损分解。

要是分解为T1,T2,…,Tn更多的表，判断是不是无损分解可以先判断T1∞T2分解为T1和T2是不是有损的，再判断(T1∞T2∞T3)分解为T1∞T2和T3是不是有损的…依然用上面的方法就可以完成。一旦中间有一个地方发现是有损分解，那么结论也就是有损分解了。

依赖保持性

分解有可能造成依赖丢失，因为依赖只能存在于同一张表中的属性之间。如果把一个Schema上的函数依赖集F分为F1,F2,…,Fn，如果(F1∪F2∪...∪Fn)+ == F+那么这个分解具有依赖保持性。即总的依赖关系在分解中没有损失。

X+是X在表T的函数依赖集上的属性集闭包：一个属性集X是表T的超键 <=等价于=> X+==Head(T)

通俗来说，就是超键能够控制到一张表的所有属性。超键确定就确定了一行。超键也称作key，注意key是一个属性集，可能有多个属性。

寻找超键的方法无非就是依次尝试去掉表中的属性，来计算剩下的属性集闭包能不能覆盖整张表的属性。候选键是超键，而且属性要求尽量少，但凡再删去一个属性就不是超键了。

主属性：在任意候选键中的属性成为主属性。

题目要求候选键、关键字、候选关键字指的都是候选键。注意可能有多个。