Introduction to Databases - Course Review

章节

关系数据库的规范化理论

1. 模式设计


同一个数据库可以有多种不同的模式设计方案。比如对于一个有8个属性的学生数据库{S#,Sn,Sd,Sa,C#,G,CN,P#}，可以设计左边表1与右边表2两种类型的数据模式：

表1    表2

这两种设计模式的影响是不同的。对于表1的第一种设计模式，其就存在以下几点问题：

  1. 数据冗余度大。
  2. 插入异常：如果需要新开设一门尚未有学生选修的课程，就无法执行插入。
  3. 删除异常：比如删除0003号学生的107号课程选修记录，这样就必然也将107号这门课程也从数据库中删除掉了。

因此，不同的设计模式有好坏之分！

要设计出一个好的关系模式，必须从数据库中所有属性的语义上进行分析，从语义上入手分清每个属性的语义含义及其相互之间的依存关系。


2. 规范化理论 - 函数依赖

2.1 函数依赖（FD – Functional Dependency）

1.函数依赖定义：在一个关系模式R(U)中，如果一部分属性Y的取值依赖于另一部分属性X的取值，则在属性集X和属性集Y之间存在着一种数据依赖关系，我们称之为函数依赖。

函数依赖比如:
{学号} -> {姓名}
{学号} -> {院系}
{学号，课程号} -> {成绩}

Y被称为函数依赖于X。

函数依赖的性质是：一旦在属性X上的取值确定，那么在属性Y上的取值也确定。

{院系} \(\rightarrow\) {学号} 就不是函数依赖。

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

一个函数依赖关系 X\(\rightarrow\)Y 如果满足Y\(\nsubseteq\)X，则称此函数依赖是非平凡的函数依赖。否则，我们称其为平凡函数依赖。

非平凡函数依赖比如：
{学号} -> {姓名}
{课程号} -> {课程名}

平凡函数依赖比如：
{学号，姓名} -> {姓名}

如无特殊声明，凡提到函数依赖时总认为指的是非平凡的函数依赖。

2) 完全/部分函数依赖

一个函数依赖关系 X\(\rightarrow\)Y，如果满足对于 X 的任意一个真子集 X' 都有 X'\(\not\rightarrow\)Y，则称 Y 完全函数依赖于 X，并记为 X \(\xrightarrow{\text{f}}\) Y。如果 Y 不完全函数依赖于 X，则称 Y 部分依赖于 X，并记作 X \(\xrightarrow{\text{p}}\) Y。

完全函数依赖比如：
{学号} -> {姓名}
{学号，课程号} -> {成绩}

部分函数依赖比如：
{学号，课程号} -> {课程名}

3) 直接/传递函数依赖

如果满足函数依赖关系 X\(\rightarrow\)Y，Y\(\not\subset\)X，Y\(\not\rightarrow\)X，Y\(\rightarrow\)Z，则称 Z 传递函数依赖于 X；否则，称为直接函数依赖（非传递函数依赖）。

传递函数依赖比如：
{学号} -> {院系号}
{院系号} -> {院系名}
于是：
{学号} -> {院系名}

2.2 Armstrong公理系统

Armstrong公理系统包含了有关函数依赖的六条推理规则：

1.基本规则： 自反规则，增广规则，传递规则。
2.扩充规则： 分解规则，合并规则，伪传递规则。

1）自反规则

如果 Y 是 X 的子集，则 X\(\rightarrow\)Y。

表3

2）增广规则

如果 X\(\rightarrow\)Y，则 XZ\(\rightarrow\)YZ。

表4

3）传递规则

如果 X\(\rightarrow\)Y，Y\(\rightarrow\)Z，则 X\(\rightarrow\)Z。

表5

4）分解规则

如果 X\(\rightarrow\)YZ，则 X\(\rightarrow\)Y。

表6

5）合并规则

如果 X\(\rightarrow\)Y，X\(\rightarrow\)Z，则 X\(\rightarrow\)YZ。

表7

6）伪传递规则

如果 X\(\rightarrow\)Y，WY\(\rightarrow\)Z，则 WX\(\rightarrow\)Z。

表8


Armstrong公理系统规则总结：

  1. Y\(\subseteq\)X:   X\(\rightarrow\)Y
  2. X\(\rightarrow\)Y:   XZ\(\rightarrow\)YZ
  3. X\(\rightarrow\)Y,   Y\(\rightarrow\)Z: X\(\rightarrow\)Z
  4. X\(\rightarrow\)YZ:   X\(\rightarrow\)Y
  5. X\(\rightarrow\)Y,   X\(\rightarrow\)Z: X\(\rightarrow\)YZ
  6. X\(\rightarrow\)Y,   WY\(\rightarrow\)Z: WX\(\rightarrow\)Z

2.3 逻辑蕴含

设 F 是一个函数依赖集，如果从 F 中的已有函数依赖关系利用Armstrong公理系统规则能推导出 X\(\rightarrow\)Y，则称 F 逻辑蕴涵 X\(\rightarrow\)Y。并记为： F \(\models\) X\(\rightarrow\)Y。

2.4 函数依赖集的闭包

由被 F 函数依赖集逻辑蕴涵的所有函数依赖关系构成的集合被称为函数依赖集 F 的闭包，并记作: F\(^{+}\)。

  • 函数依赖集的等价：如果两个函数依赖集 F1 和 F2 的闭包是相等的，即 F1\(^{+}\) = F2\(^{+}\)，则称函数依赖集 F1 等价于函数依赖集 F2

  • 最小函数依赖集：与函数依赖集 F 相等价的所有函数依赖集中的最小者被称为函数依赖集 F 的最小函数依赖集。

2.5 属性集的闭包

设 F 是关系模式 R(U) 上的函数依赖集，X 是关系模式 R(U) 的属性子集，由所有函数依赖于 X 的属性所构成的集合被称为属性集 X 在函数依赖集 F 上的闭包。记作：X\(^{+}_{\text{F}}\)，或简写成 X\(^{+}\)。

2.6 关键字

在关系模式 R(U, F) 中，如有 K\(\subseteq\)U 且满足：K\(\xrightarrow{\text{f}}\)U，则称 K 为R 的关键字。

几种不同的关键字：

  1. 候选关键字
  2. 主关键字
  3. 全关键字

2.7 主属性/非主属性

由关系模式 R 的所有关键字中的属性所构成的集合被称为关系模式 R 的主属性集。主属性集中的属性被称为关系模式 R 的主属性。

由主属性集之外的其它属性所构成的集合被称为关系模式 R 的非主属性集，非主属性集中的属性被称为关系模式 R 的非主属性。


3. 规范化理论 - 范式及模式分解

3.1 第一范式 (1NF)

如果关系模式 R(U) 中的每个属性值都是一个不可分割的数据量，则称该关系模式满足第一范式，并记为：R\(\in\)1NF

3.2 第二范式 (2NF)

设有关系模式满足1NF，且其每个非主属性都完全函数依赖于关键字，则称关系模式 R(U) 满足第二范式，并记为：R\(\in\)2NF

3.3 模式分解

设在关系模式 R 上成立的函数依赖集为 F, Head(R) 是由关系R中的所有属性所构成的属性集合。如果存在一组子关系模式 {R1, R2, ..., Rk } 满足下述的两个条件，则我们称 {R1, R2, ..., Rk } 是关系模式R的一个分解。

  1. Head(R) = Head(R1) \(\cup\) Head(R2) \(\cup\) ... \(\cup\) Head(Rk)
  2. 设子关系 Ri 上的函数依赖集为 Fi(i=1,2,...,k), 则：Fi= { X\(\rightarrow\)Y | X\(\rightarrow\)Y\(\in\)F\(^{+}\) 且(X\(\cup\)Y)\(\in\)Head(Ri) }

模式分解的过程：

1.找出所有不满足范式 M 要求的函数依赖关系。
2.选择一个不符合要求的函数依赖关系作如下的分解:

  • 假设 X\(\xrightarrow{\text{p}}\)Y\(\in\)F\(^{+}\) 且不满足范式 M 的要求，则我们将关系模式 R 分解为如下的两个子关系:
    R1( X\(\cup\)Y, { X\(\rightarrow\)Y } )
    R2( Head(R) – Y, F2 ) 其中：F2 = { A\(\rightarrow\)B｜A\(\rightarrow\)B\(\in\)F\({^{+}}\) 且 (A\(\cup\)B) \(\subseteq\) Head(R2) }

3.对于分解得到的子关系模式 R2 重复上述的步骤1和步骤2，直到所有的子关系模式都能满足范式 M 的要求。
4.合并那些具有相同关键字的子关系模式。

3.4 第三范式 (3NF)

设有关系模式 R(U)\(\in\)2NF，且其每个非主属性都不传递函数依赖于关键字，则称关系模式 R(U) 满足第三范式，并记作：R\(\in\)3NF

3.5 BCNF

设关系模式 R(U) 满足1NF，且若 X\(\rightarrow\)Y 时 X 必包含有该关系模式的关键字，则称关系模式 R(U) 满足 BCNF 范式，并记作：R\(\in\)BCNF

定理：

如果关系模式 R(U) \(\in\) BCNF，则 R(U) \(\in\) 3NF


3. 规范化理论 - 多值依赖与第四范式

3.1 多值依赖 (MVD)

设有关系模式 R(U)，X, Y 是 U 的子集 ( X,Y\(\in\)U )，若对 R(U) 的任何一个关系 r，对 X 的一个确定值，存在 Y 的一组值与之对应，且 Y 的这组值又与 Z = U - X - Y 中的属性值不相关，此时称 Y 多值依赖于X，并记为：X\(\rightarrow\)\(\rightarrow\)Y。

例如对于下表：一个 C 的值与一组 T 的值相对应，这组 T 的值与其它属性 (L) 的值无关。

表9

3.2 非平凡的多值依赖

设在关系模式 R(U)中，X\(\rightarrow\)\(\rightarrow\)Y 且 U-X-Y\(\neq\)F，

则称 X\(\rightarrow\)\(\rightarrow\)Y 是非平凡的多值依赖，否则称为平凡的多值依赖。

3.3 多值依赖的性质

在一个关系模式 R(U) 中，

1.如有 X\(\rightarrow\)\(\rightarrow\)Y，则必有:

    X\(\rightarrow\)\(\rightarrow\)(U-X-Y)

2.如有 X\(\rightarrow\)Y，则必有: X\(\rightarrow\)\(\rightarrow\)Y

3.4 有关函数依赖(FD)和多值依赖(MVD)的推导规则

关系模式 R(U)，其中X，Y，Z，W 是 U 的子集

1.规则 IR\(_{1}\)：自反规则

  • 如果 Y 是 X 的子集，则：X\(\rightarrow\)Y。

2.规则 IR\(_{2}\)：增广规则

  • 如果 X\(\rightarrow\)Y，则：XZ\(\rightarrow\)YZ。

3.规则 IR\(_{3}\)：传递规则

  • 如果 X\(\rightarrow\)Y，Y\(\rightarrow\)Z，则：X\(\rightarrow\)Z。

4.规则 IR\(_{4}\)：求补规则

  • 如果 X\(\rightarrow\)\(\rightarrow\)Y，则：

    X \(\rightarrow\)\(\rightarrow\) (U-X-Y)

5.规则 IR\(_{5}\)：多值依赖的增广规则

  • 如果 X\(\rightarrow\)\(\rightarrow\)Y 且 Z \(\subset\) W，则：

    WX \(\rightarrow\)\(\rightarrow\) YZ

6.规则 IR\(_{6}\)：多值依赖的传递规则

  • 如果X\(\rightarrow\)\(\rightarrow\)Y，

  • 且Y\(\rightarrow\)\(\rightarrow\)Z，则：

    X\(\rightarrow\)\(\rightarrow\) ( Z –Y )

7.规则 IR\(_{7}\)：转换规则

  • 如果 X\(\rightarrow\)Y，则 X\(\rightarrow\)\(\rightarrow\)Y。

8.规则 IR\(_{8}\)：结合规则

  • 如果 X\(\rightarrow\)\(\rightarrow\)Y，且存在另一个属性集合 W 满足：W \(\cap\) Y = \(\emptyset\)，W \(\rightarrow\) Z，Y \(\supseteq\) Z，则：X \(\rightarrow\) Z。

3.5 第四范式 (4NF)

在关系模式 R(U) 中，如果 X\(\rightarrow\)\(\rightarrow\)Y 是非平凡多值依赖，则 X 必含有关键字，此时称关系模式 R 满足第四范式，并记作 R\(\in\)4NF。

第四范式的特点:

  1. 只允许出现平凡多值依赖
  2. 函数依赖要满足 BCNF