数据库系统 | 第六章关系数据理论

问题的提出

关系数据库逻辑设计
- 针对具体问题，如何构造一个适合于它的数据模式
- 数据库逻辑设计的工具 ── 关系数据库的规范化理论
关系模式由五部分组成，是一个五元组：

R(U, D, DOM, F)
- 关系名 R 是符号化的元组语义
- U 为一组属性
- D 为属性组 U 中的属性所来自的域
- DOM 为属性到域的映射
- F 为属性组 U 上的一组数据依赖
由于 D、DOM 与模式设计关系不大，因此在本章中把关系模式看作一个三元组：R<U,F>
当且仅当 U 上的一个关系 r 满足 F 时，r 称为关系模式 R<U,F>的一个关系
作为二维表，关系要符合一个最基本的条件：每个分量必须是不可分开的数据项。满足了这个条件的关系模式就属于第一范式（1NF）
数据依赖
- 是一个关系内部属性与属性之间的一种约束关系
- 通过属性间值的相等与否体现出来的数据间相互联系
- 是现实世界属性间相互联系的抽象
- 是数据内在的性质
- 是语义的体现
数据依赖的主要类型
- 函数依赖（Functional Dependency，简记为 FD）
- 多值依赖（Multi-Valued Dependency，简记为 MVD）
函数依赖普遍存在于现实生活中
- 描述一个学生关系，可以有学号、姓名、系名等属性。
- 一个学号只对应一个学生，一个学生只在一个系中学习
- “学号”值确定后，学生的姓名及所在系的值就被唯一确定。
- Sname=f(Sno)，Sdept=f(Sno)
  - 即 Sno 函数决定 Sname
  - Sno 函数决定 Sdept
  - 记作 Sno→Sname，Sno→Sdept
[例 6.1] 建立一个描述学校教务的数据库。涉及的对象包括：
- 学生的学号（Sno）
- 所在系（Sdept）
- 系主任姓名（Mname）
- 课程号（Cno）
- 成绩（Grade）
假设学校教务的数据库模式用一个单一的关系模式 Student 来表示，则该关系模式的属性集合为：U ＝{Sno, Sdept, Mname, Cno, Grade}
- 现实世界的已知事实（语义）：
  - 一个系有若干学生，但一个学生只属于一个系；
  - 一个系只有一名（正职）负责人；
  - 一个学生可以选修多门课程，每门课程有若干学生选修；
  - 每个学生学习每一门课程有一个成绩。
由此可得到属性组 U 上的一组函数依赖 F：
F={Sno→Sdept, Sdept→ Mname, (Sno, Cno)→ Grade}
关系模式 Student<U, F>中存在的问题：
（1）数据冗余
- 浪费大量的存储空间
  - 每一个系主任的姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同。
（2）更新异常（Update Anomalies）
- 数据冗余，更新数据时，维护数据完整性代价大。
  - 某系更换系主任后，必须修改与该系学生有关的每一个元组。
（3）插入异常（Insertion Anomalies）
- 如果一个系刚成立，尚无学生，则无法把这个系及其系主任的信息存入数据库。
（4）删除异常（Deletion Anomalies）
- 如果某个系的学生全部毕业了，则在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。
结论
- Student 关系模式不是一个好的模式。
- 一个“好”的模式应当不会发生插入异常、删除异常和更新异常，数据冗余应尽可能少。
原因
由存在于模式中的某些数据依赖引起的。
解决方法
用规范化理论改造关系模式来消除其中不合适的数据依赖
把这个单一的模式分成三个关系模式：
- S(Sno,Sdept,Sno → Sdept);
- SC(Sno,Cno,Grade,(Sno,Cno) → Grade);
- DEPT(Sdept,Mname,Sdept → Mname);
这三个模式都不会发生插入异常、删除异常的问题，数据的冗余也得到了控制。

规范化

函数依赖

定义 6.1

设 R(U)是一个属性集 U 上的关系模式，X 和 Y 是 U 的子集。若对于 R(U)的任意一个可能的关系 r，r 中不可能存在两个元组在 X 上的属性值相等，而在 Y 上的属性值不等，则称“X 函数确定 Y”或“Y 函数依赖于 X”，记作 X→Y。
[例] Student(Sno, Sname, Ssex, Sage, Sdept),
假设不允许重名，则有:
Sno → Ssex， Sno → Sage
Sno → Sdept， Sno ←→ Sname
Sname → Ssex， Sname → Sage
Sname → Sdept
但 Ssex →Sage, Ssex→ Sdept

若 X→Y，并且 Y→X, 则记为 X←→Y。
若 Y 不函数依赖于 X, 则记为 X→Y。
X→Y，但 Y⊈X 则称 X→Y 是非平凡的函数依赖。
X→Y，但 Y⊆X 则称 X→Y 是平凡的函数依赖。
对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义。
若不特别声明，我们总是讨论非平凡函数依赖。
若 X→Y，则 X 称为这个函数依赖的决定因素（Determinant）。
若 X→Y，Y→X，则记作 X←→Y。
若 Y 不函数依赖于 X，则记作 X↛Y。

定义 6.3 在 R(U)中，如果 X→Y(Y⊈X)，Y↛X，Y→Z，Z⊈Y, 则称 Z 对 X 传递函数依赖(transitive functional dependency)。记为：X → Z。
注: 如果 Y→X, 即 X←→Y，则 Z 直接依赖于 X，而不是传递函数依赖。
[例] 在关系 Std(Sno, Sdept, Mname)中，有：
Sno → Sdept，Sdept → Mname，
Mname 传递函数依赖于 Sno

码

定义 6.4

设 K 为 R<U,F>中的属性或属性组合。若 K → U，则 K 称为 R 的一个候选码(Candidate Key)。唯一标识实体的属性或属性组合称为码
如果 U 部分函数依赖于 K，即 K → U,则 K 称为超码（Surpkey）。候选码是最小的超码，即 K 的任意一个真子集都不是候选码。
若关系模式 R 有多个候选码，则选定其中的一个做为主码(Primary key)。
主属性与非主属性
包含在任何一个候选码中的属性，称为主属性（Prime attribute）
不包含在任何码中的属性称为非主属性（Nonprime attribute）或非码属性（Non-key attribute）
全码：整个属性组是码，称为全码（All-key）
主码=主键=主关键字，
关键字=候选码
候选关键字=候选码中除去主码的其他候选码
[例 6.2]S(Sno, Sdept, Sage)，单个属性 Sno 是码
SC(Sno, Cno, Grade)中，(Sno, Cno)是码
[例 6.3] R(P,W,A) P：演奏者 W：作品 A：听众
一个演奏者可以演奏多个作品
某一作品可被多个演奏者演奏
听众可以欣赏不同演奏者的不同作品
码为(P,W,A)，即 All-Key
定义 6.5 关系模式 R 中属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称 X 是 R 的外部码（Foreign key）也称外码。
- SC(Sno,Cno,Grade)中，Sno 不是码
- Sno 是 S(Sno,Sdept,Sage)的码，则 Sno 是 SC 的外码
主码与外部码一起提供了表示关系间联系的手段

范式

范式是符合某一种级别的关系模式的集合。
作为二维表，关系要符合一个最基本的条件：每个分量必须是不可分开的数据项。满足了这个条件的关系模式就属于第一范式（1NF）
关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。
范式的种类
- 第一范式（1NF）
- 第二范式（2NF）
- 第三范式（3NF）
- BC 范式（BCNF）
- 第四范式（4NF）
- 第五范式（5NF）
各种范式之间存在联系：
某一关系模式 R 为第 n 范式，可简记为 R∈nNF。
一个低一级范式的关系模式，通过模式分解（schema decomposition）可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化（normalization）。

2NF

定义 6.6 若关系模式 R∈1NF，并且每一个非主属性都完全函数依赖于任何一个候选码，则 R∈2NF
[例 6.4] S-L-C(Sno,Sdept,Sloc,Cno,Grade)， Sloc 为学生的住处，并且每个系的学生住在同一个地方。S-L-C 的码为(Sno,Cno)。
函数依赖有
- (Sno,Cno)→Grade
- Sno→Sdept, (Sno,Cno)→Sdept
- Sno→Sloc, (Sno,Cno)→Sloc
- Sdept→Sloc
一个关系模式不属于 2NF，会产生以下问题：
- 插入异常
  如果插入一个新学生，但该生未选课，即该生无 Cno，由于插入元组时，必须给定码值，因此插入失败。
- 删除异常
  如果 S4 只选了一门课 C3，现在他不再选这门课，则删除 C3 后，整个元组的其他信息也被删除了。
- 修改复杂
  如果一个学生选了多门课，则 Sdept，Sloc 被存储了多次。如果该生转系，则需要修改所有相关的 Sdept 和 Sloc，造成修改的复杂化。
出现这种问题的原因
- 例子中有两类非主属性：
  - 一类如 Grade，它对码完全函数依赖
  - 另一类如 Sdept、Sloc，它们对码不是完全函数依赖
解决方法：
- 用投影分解把关系模式 S-L-C 分解成两个关系模式
  - SC(Sno,Cno,Grade)
  - S-L(Sno,Sdept,Sloc)
SC 的码为(Sno,Cno),SL 的码为 Sno，这样使得非主属性对候选码都是完全函数依赖了，单关键字的数据库表都符合第二范式

3NF

定义 6.7（无传递函数依赖即 3NF）

设关系模式 R<U,F>∈1NF,若 R 中不存在这样的码 X、属性组 Y(非码)及非主属性 Z（Z ⊈ Y）, 使得 X→Y(Y⊈X，Y ↛ X)，Y→Z 成立，则称 R<U,F> ∈ 3NF。
- SC 没有传递依赖，因此 SC ∈ 3NF
- S-L 中 Sno →Sdept( Sdept ↛ Sno), Sdept→Sloc，可得 Sno → Sloc。
- 解决的办法是将 S-L 分解成
  - S-D(Sno,Sdept)∈ 3NF
  - D-L(Sdept,Sloc)∈ 3NF
基于 2NF，非主属性不能函数依赖于非码。此外，非主属性只能存在一个表中，不应该存在多个表中；

BCNF

BCNF（Boyce Codd Normal Form）由 Boyce 和 Codd 提出，比 3NF 更进了一步。通常认为 BCNF 是修正的第三范式，有时也称为扩充的第三范式。
定义 6.8

设关系模式 R<U,F>∈1NF，若 X →Y 且 Y ⊆ X 时 X 必含有码，则 R<U,F>∈BCNF。
换言之，在关系模式 R<U,F>中，如果每一个决定属性集都包含候选码，则 R∈BCNF。
BCNF 的关系模式所具有的性质
- 所有非主属性都完全函数依赖于每个候选码(2NF)
- 所有主属性都完全函数依赖于每个不包含它的候选码(BCNF)
- 没有任何属性完全函数依赖于非码的任何一组属性(3NF+)
如果一个关系数据库中的所有关系模式都属于 BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。
[例 6.5]考察关系模式 C(Cno,Cname,Pcno)
[例 6.6] 关系模式 S(Sno,Sname,Sdept,Sage)，
- 假定 Sname 也具有唯一性，那么 S 就有两个码，这两个码都由单个属性组成，彼此不相交。
- 其他属性不存在对码的传递依赖与部分依赖，所以 S∈3NF。
- 同时 S 中除 Sno，Sname 外没有其他决定因素，所以 S 也属于 BCNF。
[例 6.7] 关系模式 SJP(S,J,P)中，S 是学生，J 表示
课程，P 表示名次。每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生（即没有并列名次）。
- 由语义可得到函数依赖： (S,J)→P；(J,P)→S(S,J)与(J,P)都可以作为候选码。
- 关系模式中没有属性对码传递依赖或部分依赖，所以 SJP∈3NF。
- 除(S,J)与(J,P)以外没有其他决定因素，所以 SJP∈BCNF。
[例 6.8] 关系模式 STJ(S,T,J)中，S 表示学生，T 表示教师，J 表示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师。
- 由语义可得到函数依赖：(S,J)→T；(S,T)→J；T→J
- 因为没有任何非主属性对码传递依赖或部分依赖，STJ ∈ 3NF。
- 因为 T 是决定因素，而 T 不包含码，所以 STJ ∈ BCNF 关系。BCNF 每个属性均完全依赖于每个候选码(不含它)
对于不是 BCNF 的关系模式，仍然存在不合适的地方。
非 BCNF 的关系模式也可以通过分解成为 BCNF。例如 STJ 可分解为 ST(S,T)与 TJ(T,J)，它们都是 BCNF。
3NF 和 BCNF 是在函数依赖的条件下对模式分解所能达到的分离程度的测度。
- 一个模式中的关系模式如果都属于 BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除的异常。
- 3NF 的“不彻底”性表现在可能存在主属性对码的部分依赖和传递依赖。

规范化小结

在关系数据库中，对关系模式的基本要求是满足第一范式。
规范化程度过低的关系不一定能够很好地描述现实世界
- 可能存在插入异常、删除异常、修改复杂、数据冗余等问题
- 解决方法就是对其进行规范化，转换成高级范式。
一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。
关系数据库的规范化理论是数据库逻辑设计的工具。
规范化的基本思想
- 是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”。
- 即采用“一事一地”的模式设计原则
  - 让一个关系描述一个概念、一个实体或者实体间的一种联系。
  - 若多于一个概念就把它“分离”出去。
- 因此规范化实质上是概念的单一化。

数据依赖的公理系统

一套推理规则，是模式分解算法的理论基础
用途
- 求给定关系模式的码
- 从一组函数依赖求得蕴涵的函数依赖
Armstrong 公理系统设 U 为属性集总体，F 是 U 上的一组函数依赖，于是有关系模式 R <U,F >。对 R <U,F> 来说有以下的推理规则：
- A1 自反律（reflexivity rule）：若 Y  X  U，则 X →Y 为 F 所蕴涵。
- A2 增广律（augmentation rule）：若 X→Y 为 F 所蕴涵，且 Z  U，则 XZ→YZ 为 F 所蕴涵。
- A3 传递律（transitivity rule）：若 X→Y 及 Y→Z 为 F 所蕴涵，则 X→Z 为 F 所蕴涵。
根据 A1，A2，A3 这三条推理规则可以得到下面三条推理规则：
- 合并规则（union rule）：
  由 X→Y，X→Z，有 X→YZ。
- 伪传递规则（pseudo transitivity rule）：
  由 X→Y，WY→Z，有 XW→Z。
- 分解规则（decomposition rule）：
  由 X→Y 及 ZY，有 X→Z。
定义 6.12

在关系模式 R<U,F>中为 F 所逻辑蕴涵的函数依赖的全体叫作 F 的闭包，记为 F +。
定义 6.13

设 F 为属性集 U 上的一组函数依赖，X、Y U， XF+={ A|X→A 能由 F 根据 Armstrong 公理导出}，XF+称为属性集 X 关于函数依赖集 F 的闭包。
有效性与完备性的含义
- 有效性：由 F 出发根据 Armstrong 公理推导出来的每一个函数依赖一定在 F +中
- 完备性：F +中的每一个函数依赖，必定可以由 F 出发根据 Armstrong 公理推导出来