数据库规范性理论

Armstrong公理系统

当满足以下条件时，F是一个最小函数依赖集。

1. F中任何一个函数依赖的右边只有一个属性
2. F中不存在冗余的函数依赖，也就是去掉之后跟原来等价
3. F中不存在$X\rarr A$，$X$有真子集$Z$使得$F-\{X\rarr A\}\cup\{Z\rarr A\}$

函数依赖

函数依赖是指属性之间体现出来的决定与被决定的关系，也就是哪个属性能决定另一个属性。在数据库中是语义上的体现，能够将语义表达进行抽象化。比如说:学号能够决定性别和姓名，此时学号就是一个属性，决定了另外两个属性，或者说学号能够唯一确定一个实体的属性。$学号\rarr 姓名$

有了函数依赖，但是不同属性之间的关系是不一样的，比如说:

• 一个系有若干的学生，一个学生只属于一个系
• 一个系有一名负责人
• 一个学生可以选修多门课，一门课也可以被多个学生选秀，每一个学生选修一门课都有一个成绩

上面几个例子可以看出，不同属性之间的数量对应关系也是不一样的，两者之间主要有三种关系，一对一，一对多，多对多。假设我们目前有两种属性$X,Y$。

• 一对一: 拥有两种函数依赖关系，$X\rarr Y, Y\rarr X$
• 一对多: 拥有一种函数依赖关系，多的一方可以依赖于少的一方(假设$Y$是多，$X$是一)，$Y\rarr X$
• 多对多: 没有函数依赖关系

平凡函数依赖/非平凡函数依赖

右边是否是左边的子集:

• 如果是，则为平凡函数依赖$(AB\rarr B)$
• 如果不是，则为非平凡函数依赖$(A\rarr B)$

完全函数依赖/部分函数依赖/传递函数依赖

• 完全函数依赖

左边没有其他子集可以确定右边,左边X如果是多个属性，那么就是少了一个都不能决定右边Y。

(学号,课程号)$\rarr$成绩成立，但只知道学号无法确定成绩，同理只知道课程号也无法确定成绩；只有学号和课程号组合在一起才能标识哪个学生哪门课程的成绩；所以(学号,课程号)$\rarr$成绩是"完全函数依赖"

• 部分函数依赖

左边有其他子集能够决定右边,左边X集合中存在多余的属性，不需要添加额外的属性也能决定右边Y.

姓名、性别和班级三个属性只依赖于主键中的学号，与“课程号”无关。(学号,课程号)$\rarr$姓名，(学号,课程号)$\rarr$性别，(学号,课程号)$\rarr$班级，都是部分函数依赖，意思就是左边有多余的属性。

• 传递函数依赖

依赖运算具有传递性。班主任依赖于班级，与学号无关，与课程号也无关。又因班级依赖于学号所以班主任间接依赖于学号，因此，(学号，课程号)$\rarr$班主任是“传递函数依赖”.

键

• 超键: 在关系中能唯一标识元组的属性集称为关系模式的超键。一个属性可以为作为一个超键，多个属性组合在一起也可以作为一个超键。超键包含候选键和主键。可以是多个组合，不是唯一的属性集合。
• 候选码(候选键): 能够唯一确定一个元组的属性集合。只需要里面其中一个或多个就能确定元组的属性。候选键的数量可以为一个或多个。
• 主键: 在数据表中能够唯一确定一个元组的属性，只能是一个。
• 外键: R1中一个属性不是主码，但是该属性在另一个R2中是主码，此时该属性就是外码

例子:

假设有如下两个表： 学生（学号，姓名，性别，身份证号，教师编号）

教师（教师编号，姓名，工资）

• 超键： 由超键的定义可知，学生表中含有学号或者身份证号的任意组合都为此表的超键。如：（学号）、（学号，姓名）、（身份证号，性别）等。

• 候选键： 候选键属于超键，它是最小的超键，就是说如果再去掉候选键中的任何一个属性它就不再是超键了。学生表中的候选键为：（学号）、（身份证号）。

• 主键： 主键就是候选键里面的一个，是人为规定的，例如学生表中，我们通常会让“学号”做主键，教师表中让“教师编号”做主键。

• 外键： 外键比较简单，学生表中的外键就是“教师编号”。外键主要是用来描述两个表的关系。

属性

主属性：从候选码中挑出来一个都是主属性.

非主属性：不在候选码里的属性.

求候选码理论

根据函数依赖，把属性分成四类

L:只在函数依赖左侧

R：只在函数依赖右侧

LR：函数依赖两侧

N: 没有出现过的

1. 若X是L类属性，且$X^+$包含了R的全部属性，则X为唯一候选码。
2. 若X是R类属性，则X不在任何候选码
3. 若X是N类属性，则X必包含在R的任意候选码中，需要L，N类元素进行组合
4. 若X是LR类属性，X可能为R的任意候选码的成员，也可能不是，所以需要跟L类属性组合。

L、N属性是候选码的子集，若L、N属性的闭包能涵盖全部的元素，则其是唯一候选码.

若不能，则从LR元素中于L、N元素进行组合，组合后的元素集的闭包能够涵盖全部元素，即为唯一候选码.(彼此之间是或的关系).

范式

• 第一范式: 能够写成表
• 第二范式:满足1NF且非主键的列完全依赖于主键，不存在非主属性对码的部分函数依赖$$
• 第三范式:满足2NF且非主键的列对于主键没有传递函数依赖，不存在非主属性对码的传递函数依赖$(主属性\rarr 非主属性1, 非主属性1\rarr 非主属性2)$(左边为超键，或右边全部由主属性构成)。也就是每一个非主属性，既不部分依赖于码，也不传递依赖于码
• BC范式:满足3NF且主属性之间没有依赖关系，不存在主属性对码的部分函数依赖和传递函数依赖。左边全是超键。

最小函数依赖求解

1. 先将函数依赖集右边拆成单一属性
2. 去除传递函数依赖，做法:找到出问题的函数依赖$X\rarr A$，在原来的函数依赖集中去掉之后求$X$的闭包，如果包含了A说明这个函数依赖是多余的，说明A可以被其他函数依赖推出，说明这个函数依赖不是必须的；如果不包含A则$X\rarr Y$是必须的。记经过筛选之后的函数依赖集为$F_1$。
3. 去除左边冗余项，做法:两个属性中去掉其中一个，看看是否依然还可以推导，不用考虑左边只有一个属性的。找到一个左边不是单一属性的$XY\rarr A$，进行如下操作:
   • 去除$X$，得$Y\rarr A$，替代$F_1$中的$XY\rarr A$, 得$F_2$，基于$F_2$计算 $Y$ 的闭包，如果 $Y^+ \in A$，则说明 $X$ 是多余属性，否则不是多余属性。
   • 去除$Y$，得$X\rarr A$，替代$F_1$中的$XY\rarr A$，得$F_2$，基于$F_2$计算 $X$ 的闭包，如果 $X^+ \in A$，则说明 $Y$ 是多余属性，否则不是多余属性。

例子:

$A\rarr B,AB\rarr C,D\rarr AC,D\rarr E$

1. 先将右边拆成单一属性，即$A\rarr B,AB\rarr C,D\rarr A,D\rarr C,D\rarr E$
2. 去除左边冗余项，因为$A\rarr B,AB\rarr C$冗余了，写成一个函数依赖集$F_1=\{A\rarr B,AB\rarr C\}$ 尝试去掉$A$后得，$AB\rarr C$ 变成 $B\rarr C$， 所以有$B\rarr C$；结果为：$A\rarr B,B\rarr C,D\rarr A,D\rarr C,D\rarr E$
3. 去除传递函数依赖，$D\rarr A\rarr B\rarr C,去除D\rarr C$
4. 最终结果为：$A\rarr B,B\rarr C,D\rarr A,D\rarr E$

函数依赖集的闭包

只需要求某个函数依赖在一个函数依赖集$F$上的闭包即可，如果能全覆盖，说明是属于这个函数依赖集的闭包。

例子:

设有关系$R(A,B,C,D,E)$，对应的函数依赖集$F=\{AB\rarr D, AC\rarr E, BC\rarr D, D\rarr A, E\rarr B\}$， 判定

1.函数依赖$AE\rarr CD$ 是否属于$F^+$?▁▁▁(填是或否)

2.函数依赖$CD\rarr BE$ 是否属于$F^+$？▁▁▁(填是或否)

对左边，根据F的函数依赖求闭包，如果左边的闭包 包含{左边+右边}则，说明该函数依赖属于$F^+$

第一题： $(AE)^+ = \{AEBD\}$ 不包含$\{AECD\}$，所以$AE\rarr CD$不属于$F^+$ 第二题： $(CD)^+ = \{CDAEB\}$ 包含$\{CDBE\}$，所以$CD\rarr BE$属于$F^+$

投影算法

假设有关系$R(A,B,C,D,E)$ 和 $FD$ 集 $\{AB\rarr DE,C\rarr E,D\rarr C,E\rarr A\}$,假设要把这些 $FD$ 投影到 $S(A,B,C)$ ，求出在 $S$ 上成立的 $FD$ 集合

第一步：将原来的FD转换成右边只有一个的情况,$AB\rarr D,AB\rarr E,C\rarr E,D\rarr C,E\rarr A$

第二步：通过直接观察，或传递依赖，找到$S(A,B,C)$上的函数依赖

$AB\rarr D\rarr C$ 即$AB\rarr C$

$C\rarr E\rarr A$ 即$C\rarr A$

所以在$S$上成立的$FD$集合为$\{AB\rarr C,C\rarr A\}$

• 正式算法: 输入:关系$R$及其投影$\pi_L(R),R$的函数依赖集合$F$ 输出:在$S$中成立的函数依赖集

  1. 设$T$为结果集合
  2. 对每个$S$的子集$X$，在$F$上计算$X$的闭包。对于所有的$X^+$ 中且其中的一个属性 $A\in S$，将所有非平凡的函数依赖集加入到$T$中。不属于的不用管，属于的就加入以$X\rarr A$的形式加入到结果集$T$中。
  3. 化简成为最小依赖集。
  tip

  1. 自己推自己的就不用写了
  2. 有冗余属性的也去掉，冗余属性就是指明明一个$X$就能推出$Z$，你偏偏还要多个$Y$
  3. 多多利用传递函数依赖，能消除的就消除。

  例子:假设有关系$R(A,B,C,D,E)$和$FD$集$\{AB\rarr DE,C\rarr E,D\rarr C,E\rarr A\}$,假设要把这些$FD$投影到$S(A,B,C)$，求出在$S$上成立的$FD$集合.

模式分解

通过分解范式，将几个级别比较高的关系模式分解成多个级别比较低的关系模式。

tip

使用任何一种分解算法的前提都是函数依赖集是最小依赖集。分解的时候建议先分解3NF，若不行再分BCNF。因为分了3NF，分解出来的都满足BCNF了。使用投影算法能够轻松找到任意关系模式的函数依赖。

• 2NF分解算法

  1. 求出关系模式$R(U)$的候选码$W$，找到一个部分函数依赖($X\rarr Z$,$Z$是非主属性且$X\subset W$)，就是非主属性对码的函数依赖。
  2. 将R分解为$R_1(XZ)$(主码是X)和$R_2(U-Z)$(主键是W，外键是X)。也就是拆开，将这个出问题的了函数依赖拆开，不出现。分解为一个包含这个部分函数依赖的属性的关系模式 (如:这里部分函数依赖包含X和Z，则分解出来的关系模式有一个就包含这两个，另一个关系模式在原来的关系模式上减去非主属性)
  3. 若$R_1$和$R_2$还不是2NF，则继续将$R_1$和$R_2$分解。(结合2NF定义)

  例子:

  $R(A,B,C), F=\{A,B\rarr C,A\rarr C\};$

  先求个码：

  L：A,B R:C

  N：空 LR：空

  码是$AB$,主属性是$A,B$

  $C$是非主属性且$A\rarr C$,存在非主属性对码的部分函数依赖

  于是将关系$R$分解为$R_1(A,B)$和$R_2(A,C)$，去除部分函数依赖

tip

1. 先求出关系模式的候选码
2. 找是否有非主属性对码的部分函数依赖
3. 将其对应的有的属性单独作为一个关系模式即可

• 3NF分解算法

  1. 先求最小依赖集，求出候选码
  2. 遵循左部相同合并原则，将其进行合并，形成属性集。也就是集合X，满足$X\rarr Y,X\rarr Z$，此时这两个函数依赖集有相同左部，就把他们所拥有的元素合并起来，变成一个关系模式$R(X,Y,Z)$，其他同理，只有单个就自己一个函数依赖所拥有的属性变成一个关系模式。
  3. 看分解出来的关系模式里有没有包含码(指要在同一个关系模式下出现所有的码)，包含了，就是无损且保持函数依赖的3NF，如果没有包含就不是无损的且保持函数依赖的3NF，就加一个分组把码加进去。将码的属性作为一个新的关系模式的属性集。

• BCNF分解算法

  1. 找出违例的一个函数依赖$X\rarr Y$
  2. 对其左部属性求闭包$X^+$
  3. 将其分解为$R_1=X^+$,$R_2=U-R_1+\{X\}$
  4. 使用投影算法计算出$R_1$和$R_2$，得$F_1$和$F_2$
  5. 判断$R_1$和$R_2$是否满足BCNF，若不满足，则继续求解。(结合BCNF定义)

  例子: $R(A,B,C,D,E),A\rarr B,A\rarr C,D\rarr A,D\rarr E$

  $A\rarr B$不符合BC范式的要求

  对A进行闭包，形成属性集$R_1=(A)^+=\{A,B,C\}$

  属性集$R_2$为：$U-R_1+\{A\} = \{A,D,E\}$

  在$R_1$中的最小函数依赖集为：$A\rarr B,A\rarr C$ ,此时A为这个属性集$R_1(A,B,C)$的码，并且满足BCNF的要求，分解停止

  在$R_2$中的最小函数依赖集为：$D\rarr A,D\rarr E$,此时D为这个属性集$R_2(A,D,E)$的码，并且满足BCNF的要求，停止分解

  最终分解成两个属性集：

  $R1\{A,B,C\}, R2\{A,D,E\}$ 这两个关系集上的函数依赖均满足BCNF的要求，同时也满足3NF的要求。

无损分解检查法

$R(A,B,C,D,E), A\rarr B,A\rarr C,D\rarr A,D\rarr E$

$R1(A,B,C),R2(A,D,E)$

直接列表，每个属性集一行，每行$|R|$个属性.

属性集	A	B	C	D	E
$\{A,B,C\}$	a	b	c	d1	e1
$\{A,D,E\}$	a	b2	c2	d	e

在属性集中的元素，就可以直接用小写字母表示，否则则用，小写字母+下标行号表示.

根据函数依赖，如果左边的值在表中对应列的值是一致的，右边也应该一致，如果不一致，就向行号小的同步。相同的$X$推出相同的$Y$，行号往小的改，若能出现一行无行号的就是无损的。

属性集	A	B	C	D	E
$\{A,B,C\}$	a	b	c	d1	e1
$\{A,D,E\}$	a	b	c	d	e