Lecture Notes: Database Management Systems

COMP3013 Database Management Systems

Dr. Zhiyuan Li

数据库规范化与 BCNF

Intro

1. 什么是规范化？

  • 目标：
    • 减少数据库中的数据冗余（Redundancy）。
    • 消除插入、删除和更新异常（Anomalies）。
  • 方法：
    • 将关系模式分解为符合一定范式的子关系模式。
    • 常见的范式包括：
      • 第一范式（1NF）
      • 第二范式（2NF）
      • 第三范式（3NF）
      • BCNF（Boyce-Codd Normal Form）

2. 规范化的核心原则

  • 无损分解（Lossless Decomposition）：
    • 分解后的子关系模式可以通过自然连接（Natural Join）无损恢复到原始关系模式。
  • 依赖保留（Dependency Preservation）：
    • 分解后仍然可以在子关系模式中检查所有函数依赖（Functional Dependencies）。

Lecture 09: Functional Dependencies

1. 什么是函数依赖 (Functional Dependency, FD)?

  • 定义：
    • 在关系模式 $R$ 中，如果属性集合 $\alpha$ 的值唯一确定属性集合 $\beta$ 的值，那么 $\alpha \to \beta$ 是一个函数依赖。
    • 公式：$\alpha \to \beta$
    • 含义：$\alpha$ 的值唯一决定 $\beta$ 的值。
  • 例子：
    • 学生表（Student）：Student_ID → Student_Name 表示学号唯一决定姓名。
    • 在关系 $r(A, B)$ 中，如果 $A → B$ 成立，则关系中的每个 $A$ 值对应唯一的 $B$ 值。

2. 平凡依赖 (Trivial Dependency)

  • 定义：
    • 如果 $\beta \subseteq \alpha$，则 $\alpha → \beta$ 是平凡依赖。
    • 平凡依赖总是成立，无论关系中的数据如何。
  • 例子：
    • $Course_{Code} → Course_{Code}$
    • $Student_{ID}, Course → Student_{ID}$

3. 闭包 (Closure)

  • 定义：给定函数依赖集合 $F$，其闭包 $F^+$ 是包含 $F$ 和所有由 $F$ 推导出的函数依赖的集合。
  • 如何计算闭包？
    • 规则（Armstrong 公理）：
      1. 自反性 (Reflexivity): 如果 $\beta \subseteq \alpha$，则 $\alpha → \beta$。
      2. 增广性 (Augmentation): 如果 $\alpha → \beta$，则 $\gamma\alpha → \gamma\beta$。
      3. 传递性 (Transitivity): 如果 $\alpha → \beta$ 且 $\beta → \gamma$，则 $\alpha → \gamma$。

4. 闭包例子

  • 给定 $R = \lbrace A, B, C \rbrace$ 和 $F = \lbrace A → B, B → C\rbrace$：
    • 计算 $F^+$:
      1. $A → B$（已知）。
      2. $B → C$（已知）。
      3. $A → C$（通过 $A → B$ 和 $B → C$ 的传递性推导）。

5. 如何检查超键？

  • 超键：一个属性集合是超键，如果其闭包包含关系中的所有属性。
  • 检查方法：
    1. 计算属性集合 $\alpha$ 的闭包 $\alpha^+$。
    2. 如果 $\alpha^+$ 包含关系中的所有属性，则 $\alpha$ 是超键。

6. 伪代码：闭包计算

1
2
3
4
5
6
7
8
输入: 属性集合 α, 函数依赖集合 F
输出: 属性集合 α 的闭包 α+
1. 初始化 α+ = α
2. 重复以下步骤，直到 α+ 不再变化:
    3. 对于每个函数依赖 β → γ ∈ F:
        a. 如果 β ⊆ α+:
            将 γ 加入 α+
4. 返回 α+
1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 函数依赖集合 F
输出: F 的闭包 F+

1. 初始化 F+ 为 F (即 F+ 开始时仅包含初始依赖集合 F)。
2. 重复以下步骤，直到 F+ 不再增加新的依赖：
    3. 对于 F+ 中的每个函数依赖 α → β:
        a. 根据以下规则生成新的函数依赖：
           i. 自反性 (Reflexivity): 如果 β ⊆ α，则 α → β。
           ii. 增广性 (Augmentation): 如果 α → β，则 γα → γβ。
           iii. 传递性 (Transitivity): 如果 α → β 且 β → γ，则 α → γ。
        b. 将新生成的依赖加入 F+，如果它尚未存在。
4. 返回 F+

Lecture 10: Boyce–Codd Normal Form (BCNF)

1. 什么是 BCNF？

BCNF 是一种数据库设计规则，用来解决数据冗余和更新异常的问题。它是第三范式（3NF）的增强版本，要求更严格。

核心要求：

如果一个表 $R$ 中存在一个函数依赖 $\alpha \to \beta$，那么：

  • 要么 $\beta$ 是 $\alpha$ 的子集（平凡依赖）。
  • 要么 $\alpha$ 是这个表的超键（Superkey）。

如果表中的每一个函数依赖都符合上面的要求，那么这个表就是 BCNF。

2. 直观例子

假设我们有一个表 Course_Info：

1
2
3
4
5
6
7
+------------+-------------+-------------+-----------+
| c_name     | professor   | credits     | domain    |
+------------+-------------+-------------+-----------+
| Database   | Dr. Smith   | 3           | CS        |
| Database   | Dr. Johnson | 3           | CS        |
| Algebra    | Dr. Smith   | 4           | Math      |
+------------+-------------+-------------+-----------+

函数依赖：

  1. $c_{name} \to credits, domain$（课程名称唯一决定学分和领域）。
  2. $c_{name}, professor \to credits, domain$（课程名称和教授一起也可以决定学分和领域）。

分析：

  1. 这里 $c_{name} \to credits, domain$ 是一个有效的函数依赖，但 $c_{name}$ 不是超键（不能唯一标识表中的每一行）。
  2. 因此，这个表不符合 BCNF。

3. 如何解决？

通过BCNF 分解，将表分解为两个更小的表：

  1. 一个表保存课程的基础信息：

    1
    2
    3
    4
    5
    6
    +------------+-------------+-----------+
    | c_name     | credits     | domain    |
    +------------+-------------+-----------+
    | Database   | 3           | CS        |
    | Algebra    | 4           | Math      |
    +------------+-------------+-----------+

  2. 另一个表保存教授信息：

    1
    2
    3
    4
    5
    6
    7
    +------------+-------------+
    | c_name     | professor   |
    +------------+-------------+
    | Database   | Dr. Smith   |
    | Database   | Dr. Johnson |
    | Algebra    | Dr. Smith   |
    +------------+-------------+

现在，每个表都符合 BCNF。

4. 总结

  • BCNF 的定义简化版：
    • 每个函数依赖的左边（$\alpha$）必须是超键。
  • 检查方法：
    1. 找出表中的函数依赖。
    2. 检查依赖的左边是否是超键。
  • 不符合时：
    • 通过分解表来解决，确保每个子表都符合 BCNF。

Lecture 11: Third Normal Form (3NF)

1. 什么是第三范式 (3NF)?

  • 定义：关系模式 $R$ 满足 3NF，当对于每个函数依赖 $\alpha → \beta$：
    1. $\beta \subseteq \alpha$ （平凡依赖），或
    2. $\alpha$ 是超键 (Superkey)，或
    3. $\beta - \alpha$ 中的每个属性是某个候选键的属性。

2. 为什么需要 3NF？

  • 在某些情况下，BCNF 分解可能无法保留依赖。
  • 3NF 允许一定的冗余，确保所有依赖都可以在分解后的关系中检查。

3. 示例

  • 给定关系模式 $R = \lbrace J, K, L\rbrace$ 和函数依赖 $F = \lbrace JK → L, L → K\rbrace$：
    1. 候选键：$\lbrace J, K\rbrace$, $\lbrace J, L\rbrace$。
    2. 检查函数依赖：
      • $JK → L$：满足 $JK$ 是超键。
      • $L → K$：满足 $K$ 属于候选键。
    3. 结论：$R$ 已满足 3NF。

4. 3NF 分解算法

1
2
3
4
5
6
输入: 关系模式 R, 函数依赖集合 F
输出: 分解后的 3NF 子关系模式
1. 计算 F 的标准覆盖 (Canonical Cover)。
2. 对于每个函数依赖 α → β:
    a. 创建子关系模式 {α ∪ β}。
3. 如果没有包含候选键的子关系模式，添加一个包含候选键的子关系。

Lecture 12: Multivalued Dependencies and 4NF

1. 什么是多值依赖 (Multivalued Dependency, MVD)?

  • 定义：如果属性集合 $\alpha$ 确定 $\beta$ 的多个独立值，则称 $\alpha ↠ \beta$ 是一个多值依赖。
  • 公式：$\alpha ↠ \beta$
  • 例子：
    • 学生 $ID ↠ ISBN$ 和 $ID ↠ Phone$。
    • 学生的书籍 $ISBN$ 和电话 $Phone$ 彼此独立。

2. 第四范式 (4NF)

  • 定义：关系模式 $R$ 满足 4NF，当对于每个多值依赖 $\alpha ↠ \beta$：
    1. $\beta \subseteq \alpha$ 或 $\alpha ∪ \beta = R$ （平凡 MVD），或
    2. $\alpha$ 是超键。

3. 示例

  • $R = \lbrace ID, ISBN, Phone \rbrace$
  • 多值依赖：$ID ↠ ISBN$ 和 $ID ↠ Phone$
  • 违反 4NF：
    • 因为 $ID$ 不是超键。
  • 分解：
    1. $R_1 = \lbrace ID, ISBN \rbrace$
    2. $R_2 = \lbrace ID, Phone \rbrace$

4. 4NF 分解算法

1
2
3
4
5
6
7
输入: 关系模式 R, 多值依赖集合 D
输出: 4NF 分解后的子关系模式
1. 找到违反 4NF 的多值依赖 α ↠ β。
2. 将 R 分解为:
    a. 包含 α ∪ β 的子关系。
    b. 包含 R - β 的子关系。
3. 重复以上步骤，直到所有子关系满足 4NF。

Lecture Notes: Database Management Systems

https://tosakaucw.github.io/lecture-notes-database-management-systems/

Author

TosakaUCW

Posted on

2024-12-04

Updated on

2024-12-15

Licensed under

Comments

×