第五章-关系数据理论

前言：为什么要学习关系数据理论？

在数据库设计的过程中，我们从现实世界的需求出发，通过E-R图等工具构建出概念模型，最终将其转换为关系数据库中的一系列关系模式（即“表结构”）。这时，我们会面临一系列核心问题：

• 应该设计几个关系（表）？

• 每个关系应该包含哪些属性（字段）？

• 不同的设计方案之间，有好坏之分吗？

• 如何评价一个关系模式设计是“好”的，并避免“坏”的设计？

关系数据理论，特别是其中的 规范化理论 (Normalization Theory)，正是为了回答这些问题而生的。它为我们提供了一套系统化的方法，用以评判关系模式的优劣，并将“不好”的设计改进为“好”的设计。本章的学习，将围绕如何设计出结构合理、冗余少且不易出错的关系模式展开。

1. 一个糟糕的设计引发的问题

我们通过一个例子来直观感受什么是“不好”的关系模式。假设要为一个学校设计学生管理数据库，管理的信息包括：学号(S#)、课程名(CN)、成绩(G)、系名(SDN)和系负责人(MN)。

一个直观但粗糙的设计是把所有信息都放在一张大表里： UN (S#, CN, G, SDN, MN)

这个看似方便的“大一统”设计，在实际操作中会带来一系列严重的问题，我们称之为 “数据异常”：

1. 数据冗余：

   • 一个学生选修多门课，他的系名、系负责人信息就会重复存储多次。

   • 一个系有多名学生，该系的系负责人信息也会重复存储多次。

   • 后果：不仅浪费存储空间，更是导致其他异常的根源。

2. 更新异常：

   • 如果某系的系负责人更换了，我们需要修改 所有 属于该系的学生记录。

   • 后果：一旦漏改，就会导致数据不一致。

3. 插入异常：

   • 如果一个新系成立了，但还没有招生，那么这个系及其负责人的信息将 无法存入 数据库。因为没有学号(S#)和课程号(CN)，主键 (S#, CN) 无法形成，记录就无法插入。

   • 后果：导致信息丢失。

4. 删除异常：

   • 如果某个学生只选了一门课，并且他是其所在系的最后一名学生。一旦该学生毕业，其选课记录被删除，那么这个系及其负责人的信息也 随之丢失。

   • 后果：删除了不想删除的数据。

由于存在上述种种问题，我们称 UN 是一个 “不好” 的关系模式。

2. “好”的设计与问题的根源

与上述糟糕的设计相对，一个更好的设计是将 UN 分解为三个更小的关系模式：

• SD (S#, SDN) —— 学生与系的关系

• SG (S#, CN, G) —— 学生选课与成绩的关系

• DM (SDN, MN) —— 系与负责人的关系

这个设计方案可以有效避免上述所有异常，数据冗余也降到了最低。因此，我们称它是一个 “好” 的数据库模式。

那么，导致一个关系模式“好”与“坏”的根本原因是什么？ 答案在于 关系内部属性之间的依赖关系。在“不好”的 UN 模式中，存在着多重且复杂的依赖关系。这些不合适的依赖关系共存于同一个关系模式中，引发了各种异常。

3.数据依赖

为了科学地分析和解决这些问题，我们需要一个理论工具来描述属性间的这种约束关系，这就是 数据依赖。

• 定义：数据依赖是一个关系内部属性值之间的一种 约束和制约关系。它不是根据某个具体的关系实例（表中的数据）来判断的，而是由现实世界的 语义 所决定的。

• 示例：

  • S# → SDN：表示只要学号确定，他所在的系名也就唯一确定了。

  • (S#, CN) → G：表示只要学号和课程名都确定，他的成绩也就唯一确定了。

• 主要类型：

  1. 函数依赖：最重要、最常见的数据依赖。例如 X → Y，表示 X 的值唯一确定 Y 的值。

  2. 多值依赖：处理更复杂的一对多、多对多关系。

本章的核心任务，就是研究以函数依赖为代表的数据依赖，并以此为基础，学习如何运用规范化理论，将一个可能存在问题的关系模式，通过模式分解，转换成一组更优的、更高范式的关系模式集合，从而设计出高质量的数据库。

好的，我们继续深入学习第五章的核心内容—— 函数依赖。这部分笔记将严格遵循PPT的子大纲结构进行组织。

函数依赖

第一部分-概念

1. 函数依赖的定义

• 形式化定义： 设 R(U) 是属性集 U 上的一个关系模式，X 和 Y 是 U 的子集。对于 R 的任意一个具体关系 r，如果 r 中不存在两个元组 t 和 s，使得 t[X] = s[X] 但 t[Y] ≠ s[Y]，则称 “X 函数确定 Y” 或 “Y 函数依赖于 X”，记作 X → Y。

• 通俗理解： X → Y 意味着，只要属性（或属性组） X 的值一旦确定，属性（或属性组） Y 的值也就被 唯一地 确定了。可以把它想象成数学中的函数关系 y = f(x)，给定一个 x，有且只有一个 y 与之对应。

  • 在函数依赖 X → Y 中，X 称为 决定因素。

• 示例 (在 UN(S#, CN, G, SDN, MN) 关系中)：

  • S# → SDN：给定一个学号，就能唯一确定他所在的系。

  • SDN → MN：给定一个系名，就能唯一确定该系的负责人。

  • (S#, CN) → G：给定一个学号和一门课程名，就能唯一确定这门课的成绩。

• 重要特性：

  1. 语义范畴：函数依赖是由现实世界的业务规则（语义）决定的，而不是通过观察表中的数据推断出来的。数据可以验证或反驳一个函数依赖，但不能创建它。

  2. 不随时间变化：函数依赖是关系模式的内在属性，只要业务规则不变，它就保持稳定，即使表中的数据在不断增删改查。

2. 函数依赖的类型

根据决定因素和被决定属性之间的关系，函数依赖可以细分为以下几种：

2.1 平凡与非平凡函数依赖

• 平凡函数依赖： 如果 X → Y，且 Y ⊆ X (Y 是 X 的子集或等于 X)，则称此函数依赖是平凡的。

  • 示例：(S#, CN) → S#。这总是成立的，因为它没有提供任何新信息。

• 非平凡函数依赖： 如果 X → Y，但 Y ⊈ X，则称此函数依赖是非平凡的。

  • 示例：S# → SDN。这是有意义的约束。

  • 我们主要研究的是非平凡函数依赖。

2.2 完全与部分函数依赖

这个分类只在决定因素 X 是一个 复合属性（由多个属性组成）时才有意义。

• 完全函数依赖： 在 X → Y 中，如果 X 的任何一个真子集 X' 都不能决定 Y (即 X' ↛ Y)，则称 Y 对 X 完全函数依赖。

  • 记作：X --f--> Y

  • 示例：(S#, CN) → G。因为 S# 单独不能决定 G（一个学生有多门成绩），CN 单独也不能决定 G（一门课有多个学生），必须 (S#, CN) 组合在一起才能唯一确定一个成绩。

• 部分函数依赖： 在 X → Y 中，如果存在 X 的一个真子集 X'，使得 X' → Y 成立，则称 Y 对 X 部分函数依赖。

  • 记作：X --p--> Y

  • 示例：(S#, CN) → SDN。虽然 (S#, CN) 可以决定 SDN，但其真子集 S# 也能决定 SDN (S# → SDN)。因此，SDN 对 (S#, CN) 是部分函数依赖。

  • 部分函数依赖是导致数据冗余和异常的重要原因，是2NF要解决的核心问题。

2.3 传递函数依赖

• 定义： 在 X → Z 中，如果存在一个属性（或属性组）Y，使得 X → Y 和 Y → Z 同时成立，但 Y ⊈ X 且 Y ↛ X，则称 Z 对 X 传递函数依赖。

  • 通俗讲：X 通过一个“中间人” Y 来间接决定 Z。

  • 示例：在 UN 模式中，S# → MN 就是一个传递函数依赖。因为 S# → SDN 和 SDN → MN 成立，且 SDN 不是 S# 的一部分，SDN 也不能反过来决定 S#。

  • 传递函数依赖是导致数据冗余和异常的另一个重要原因，是3NF要解决的核心问题。

3. 关系键的形式化定义

函数依赖的概念让我们能够更精确地定义数据库中的各种“键”。

• 候选码 (Candidate Key) / 键 (Key)： 设 K 是关系模式 R(U) 的一个属性（或属性组）。如果 K 完全函数决定 U (即 K --f--> U)，则 K 称为 R 的一个候选码。

  • 它满足两个性质：

    1. 唯一性：K → U，即 K 能唯一标识一个元组。

    2. 最小性：K 的任何真子集都不能唯一标识元组。

• 主码 (Primary Key)： 当一个关系模式有多个候选码时，可以人为选定 一个 作为主码。

• 主属性 (Primary Attribute) & 非主属性 (Non-prime Attribute)：

  • 包含在 任何一个 候选码中的属性，称为 主属性。

  • 不包含在任何候选码中的属性，称为 非主属性。

• 外码 (Foreign Key)： 属性（或属性组）X 在关系模式 R1 中不是码，但它是另一个关系模式 R2 的码，则称 X 是 R1 的外码。

4. 函数依赖公理系统 (Armstrong's Axioms)

函数依赖不仅有定义，还有一套可以进行逻辑推导的规则，称为 Armstrong公理系统。这是所有函数依赖推理的基础。

• 基本公理 (3条)：

  1. 自反律：如果 Y ⊆ X，则 X → Y 成立。（平凡依赖）

  2. 增广律：如果 X → Y，则对于任意属性组 Z，有 XZ → YZ 成立。

  3. 传递律：如果 X → Y 且 Y → Z，则 X → Z 成立。

• 重要推论 (3条)：

  1. 合并规则：如果 X → Y 且 X → Z，则 X → YZ 成立。

  2. 分解规则：如果 X → YZ，则 X → Y 且 X → Z 成立。

  3. 伪传递规则：如果 X → Y 且 WY → Z，则 WX → Z 成立。

     由合并规则和分解规则可以得到定理： X→A₁A₂...Aₖ成立 ⇔ X→Aᵢ成立(i=1, 2, ...,k)

这些公理和推论构成了我们进行函数依赖相关计算（如求闭包、求候选码）的理论基础。

第二部分-推理与计算

在掌握了Armstrong公理系统之后，我们可以利用它来进行更复杂的推理和计算，从而分析函数依赖集、求解候选码以及为模式分解做准备。

1. 函数依赖的逻辑蕴涵与闭包

• 逻辑蕴涵

  • 定义：对于一个给定的函数依赖集 F，如果某个函数依赖 X → Y 能够由 F 根据Armstrong公理系统推导出来，那么就称 F 逻辑蕴涵 X → Y。

• 函数依赖集 F 的闭包

  • 定义：由一个函数依赖集 F 所能逻辑蕴涵的 所有函数依赖 的集合，称为 F 的 闭包，记作 F⁺。

  • F⁺ 是我们能从 F 出发，通过公理推导出的全部知识。

2. 属性集的闭包

在实际应用中，我们更关心的是：给定一个属性（或属性组）X 和一个函数依赖集 F，我们能用 X 唯一确定哪些其他的属性？

• 定义：属性集 X 关于函数依赖集 F 的 闭包，是指所有能被 X 函数确定的属性的集合。记作 X_F⁺ (或简写为 X⁺)。

  • 形式化定义：X⁺ = {A | X → A 能被 F 逻辑蕴涵}。

• 计算 X⁺ 的算法 这是一个非常重要的基础算法，采用迭代的方式：

  1. 初始化：令结果集 X⁺ = X。

  2. 迭代：反复扫描函数依赖集 F 中的每一个函数依赖 W → Z。

     • 如果 W 的所有属性都已在 X⁺ 中 (即 W ⊆ X⁺)，并且 Z 中有属性还不在 X⁺ 中。

     • 则将 Z 中的所有属性加入到 X⁺ 中：X⁺ = X⁺ ∪ Z。

  3. 终止：重复第2步，直到 X⁺ 不再增大为止。

• 示例：

  • 设 U = (A, B, C, D, E)，F = {AB→C, B→D, C→E}。求 (AB)⁺。

  1. 初始化：(AB)⁺ = {A, B}

  2. 扫描 F：

     • AB → C：{A, B} ⊆ (AB)⁺，将 C 加入。(AB)⁺ = {A, B, C}。

     • B → D：{B} ⊆ (AB)⁺，将 D 加入。(AB)⁺ = {A, B, C, D}。

     • C → E：{C} ⊆ (AB)⁺，将 E 加入。(AB)⁺ = {A, B, C, D, E}。

  3. 再次扫描，(AB)⁺ 不再变化。

  • 最终结果：(AB)⁺ = {A, B, C, D, E}。

• 属性闭包的应用：

  • 判断函数依赖：要判断 X → Y 是否成立，只需计算 X⁺，看 Y 是否是 X⁺ 的子集 (Y ⊆ X⁺)。

  • 求解候选码：如果 X⁺ 包含了关系模式中的所有属性 (即 X⁺ = U)，那么 X 就是一个 超码 (Superkey)。如果这个 X 还是最小的（其任何真子集都不是超码），那么 X 就是一个 候选码。

3. 函数依赖集的等价与覆盖

在进行数据库设计时，我们可能会遇到不同形式但表达相同约束的函数依赖集。

• 等价

  • 定义：如果两个函数依赖集 F 和 G 的闭包相等 (F⁺ = G⁺)，则称 F 和 G 是 等价 的。

  • 这意味着 F 和 G 虽然形式不同，但它们所能表达的全部约束信息是完全一样的。

• 覆盖

  • 定义：如果 F⁺ ⊇ G⁺，则称 F 覆盖 G。如果 F 和 G 相互覆盖，则它们等价。

4. 最小依赖集

一个函数依赖集 F 中可能存在冗余的依赖，或者某个依赖的左部有冗余的属性。为了简化分析和后续的模式分解，我们需要找到一个与 F 等价的、最简洁的函数依赖集，这就是 最小依赖集（也称 最小覆盖）。

• 定义：一个函数依赖集 F 如果满足以下三个条件，则称其为最小依赖集：

  1. 右部单属性：F 中所有函数依赖的右部都只有一个属性。

     • 例如，X → YZ 应分解为 X → Y 和 X → Z。

  2. 左部无冗余属性：F 中不存在形如 X → A 的函数依赖，使得我们可以用 X 的某个真子集 Z ⊂ X 来替换 X，得到 Z → A，且替换后的依赖集与原依赖集等价。

  3. 依赖无冗余：F 中不存在任何一个函数依赖，去掉它之后，剩余的依赖集与原依赖集等价。

5. 最小依赖集的求解算法（极小化处理）

这是一个三步算法，用于将任意函数依赖集 F 转换为一个与之等价的最小依赖集 Fm：

1. 分解右部： 遍历 F 中的每个函数依赖，如果其右部有多个属性，则使用 分解规则 将其拆分为多个右部为单属性的函数依赖。

   • 例如，将 A → BC 替换为 A → B 和 A → C。

2. 消除左部冗余属性 (通过求属性集闭包)： 逐一检查 F 中每个函数依赖 X → A（此时 A 必为单属性）：

   • 遍历 X 中的每个属性 B。

   • 尝试从 X 中去掉 B，得到 Z = X - {B}。

   • 计算 Z 在 当前 F 下的闭包 Z⁺。

   • 如果 A ∈ Z⁺，也即 Z → A ，说明 B 是冗余的，可以从 X 中永久删除 B。

   • 对所有依赖和依赖中的所有左部属性重复此过程。

3. 消除冗余依赖 (通过求函数依赖集闭包)： 逐一检查 F 中的每个函数依赖 X → A：

   • 暂时从 F 中移除 X → A，得到新的依赖集 G = F - {X → A}。

   • 在 G 的基础上计算 X 的闭包 X⁺。

   • 如果 A ∈ X⁺，说明 X → A 是冗余的，可以被 G 中的其他依赖推导出来，因此将其 永久删除。

   • 如果 A ∉ X⁺，则该依赖是必要的，将其加回 F 中。

   • 对 F 中所有依赖重复此过程。

经过这三步处理后，最终得到的函数依赖集就是一个与原始 F 等价的最小依赖集 Fm。这个 Fm 是进行 3NF 模式分解 的基础。

范式

范式是衡量关系模式“好”的程度的标准。一个关系模式满足的约束条件越多、越严格，它的范式级别就越高。级别越高的范式，其数据冗余就越少，插入、删除、更新异常等问题就越少。

通过逐步消除数据依赖中不合适的部分（如部分依赖、传递依赖），就能将一个低级范式的关系模式分解为若干个高级范式的关系模式的集合。

范式的级别是向下兼容的，即一个关系模式如果属于某个范式，那它必定属于所有比它级别低的范式。 1NF ⊃ 2NF ⊃ 3NF ⊃ BCNF ⊃ 4NF ⊃ 5NF (⊃ 表示“包含于”)

1. 第一范式 (1NF)

• 定义：关系模式 R 中所有的属性值都是不可再分的原子值。

• 要求：字段不能是集合、列表或“表中有表”的形式。

2. 第二范式 (2NF)

• 定义：一个关系模式 R 首先是 1NF，并且其中每一个非主属性都完全函数依赖于 R 的任何一个候选码。

• 要求：消除非主属性对码的部分函数依赖。

• 理解：一张表中，非主键字段必须完整地依赖于整个主键，而不能只依赖于主键的一部分。

• 示例：

  • 问题模式：UN(S#, CN, G, SDN, MN)。候选码为 (S#, CN)。

    • 主属性：S#, CN

    • 非主属性：G, SDN, MN

  • 依赖分析：

    • (S#, CN) → G：G 完全依赖于码 (√)。

    • (S#, CN) → SDN：这是部分依赖，因为 S# → SDN 成立，SDN 仅依赖于码的一部分 S# (×)。

    • (S#, CN) → MN：同理，这也是部分依赖 (×)。

      UN 不属于 2NF。

  • 规范化：采用“投影分解法”，将导致部分依赖的属性分离出去。

    • SG = UN[S#, CN, G]：保留完全依赖的部分。

    • SDM = UN[S#, SDN, MN]：将部分依赖的属性及其决定因素分离成新表。

  • 结果：分解后的 SG 和 SDM 均满足 2NF。

• 2NF 的问题：虽然解决了部分依赖，但仍可能存在插入、删除异常和数据冗余。例如，在 SDM 中，如果一个系没有学生，系和负责人的信息就无法插入。这是因为还存在传递依赖。

3. 第三范式 (3NF)

• 定义：一个关系模式 R 首先是 2NF，并且其中没有非主属性传递函数依赖于 R 的任何一个候选码。

• 要求：消除非主属性对码的传递函数依赖。

• 理解：非主键字段之间不能存在依赖关系，即不能出现“非主键 A 决定 非主键 B” 的情况。

• 示例：

  • 问题模式：我们继续分析 2NF 分解后的 SDM(S#, SDN, MN)。其候选码为 S#。

    • 主属性：S#

    • 非主属性：SDN, MN

  • 依赖分析：存在依赖链 S# → SDN → MN。非主属性 MN 依赖于另一个非主属性 SDN，因此 MN 传递依赖于码 S# (×)。

    SDM 不属于 3NF。

  • 规范化：将导致传递依赖的属性分离出去。

    • SD(S#, SDN)：保留主键和直接依赖于它的属性。

    • DM(SDN, MN)：将传递依赖的“中间人”和它所决定的属性分离成新表。

  • 最终结果：原始的 UN 模式被规范化为三个关系：

    • SG(S#, CN, G) ∈ 3NF

    • SD(S#, SDN) ∈ 3NF

    • DM(SDN, MN) ∈ 3NF 至此，我们在最开始时提到的所有异常和冗余问题都得到了解决。

4. BCNF (Boyce-Codd Normal Form)

BCNF 是 3NF 的一个修正和增强版，规则更严格。

• 定义：一个关系模式 R 首先是 1NF，并且其中每一个非平凡函数依赖 X → Y 的决定因素 X 都必须包含一个候选码 (即 X 是一个超码)。

• 解决的核心问题：消除所有决定因素不是超码的函数依赖，包括主属性对码的部分依赖和传递依赖。

• 与 3NF 的区别：3NF 只要求“非主属性”不能部分或传递依赖于码，但没有限制“主属性”。而 BCNF 要求所有依赖的左侧都必须是超码，更为彻底。

• 示例：

  • 问题模式：STC(S, T, C) (S:学生, T:教师, C:课程)。规定：一个教师只教一门课 (T → C)，一门课可由多名教师教；一个学生选修一门课，只会被分配给一个固定的教师 ((S, C) → T)。

  • 依赖分析：

    • 函数依赖集 F = {T → C, (S, C) → T}。

    • 候选码：(S, C) 和 (S, T)。所有属性都是主属性。

    • 3NF 判断：由于没有非主属性，所以该模式属于 3NF。

    • BCNF 判断：检查函数依赖 T → C。其决定因素 T 既不是候选码 (S, C)，也不是 (S, T)，因此 T 不是超码。

    STC 属于 3NF，但不属于 BCNF。这会导致异常（如：为某门课指派新教师时，必须有学生选这门课，否则无法插入）。

  • 规范化：根据违规的依赖 T → C 进行分解。

    • TC(T, C)

    • ST(S, T)

  • 结果：分解后的 TC 和 ST 均满足 BCNF。

多值依赖与第四范式

函数依赖只描述了一对一或多对一的约束。现实世界中还有更复杂的一对多约束，这需要用多值依赖来描述。

1. 多值依赖

• 问题引入：即使一个关系模式达到了 BCNF，仍可能存在数据冗余。

  • 示例：TEACH(C, T, B) (C:课程, T:教师, B:参考书)。业务规则：一门课程可由多位教师讲授，也使用多本参考书。并且，某门课的教师集合与参考书集合是相互独立的。

  • 该模式的唯一候选码是 (C, T, B)，没有非平凡的函数依赖，所以它属于 BCNF。

  • 但它存在严重的数据冗余：如果课程 C1 有2个老师 T1, T2，用了3本参考书 B1, B2, B3，那么为了表示这种独立关系，必须存储 2 x 3 = 6 条记录。

• 定义：设 R(U) 是一个关系模式，X, Y, Z 是 U 的子集，且 Z = U - X - Y。如果对于给定的 X 的一个值 x，Y 的值集合仅仅取决于 x，而与 Z 的值无关，则称 “Y 多值依赖于 X”，记作 X →→ Y。

• 示例的多值依赖表示：C →→ T (课程确定了教师集合) 和 C →→ B (课程确定了参考书集合)。

• 重要性质：

  • 对称性：如果 X →→ Y，那么 X →→ Z (其中 Z = U - X - Y)。

  • 函数依赖是多值依赖的特例：如果 X → Y，那么 X →→ Y。

2. 第四范式 (4NF)

• 定义：一个关系模式 R 首先是 1NF，并且其中对于任何一个非平凡的多值依赖 X →→ Y，X 都必须包含一个候选码 (即 X 是一个超码)。

• 要求：消除非平凡且非函数的多值依赖。

• 理解：一张表中不能包含两个或多个相互独立的“一对多”关系。

• 示例：

  • 问题模式：TEACH(C, T, B)。

  • 依赖分析：存在非平凡的多值依赖 C →→ T 和 C →→ B。其决定因素 C 不是超码（码是 (C, T, B)）。

    TEACH 属于 BCNF，但不属于 4NF。

  • 规范化：根据违规的多值依赖进行分解。

    • CT(C, T)

    • CB(C, B)

  • 结果：分解后，冗余被彻底消除。如果课程 C1 有2个老师，3本参考书，只需存储 2 + 3 = 5 条记录。分解后的 CT 和 CB 均满足 4NF。

规范化与模式分解

一、 规范化

1. 规范化的目的

   规范化的根本目的，是消除设计不佳的关系模式所导致的各种问题，从而创建一个结构合理、数据清晰的数据库。这些问题具体表现为：

   • 数据冗余：相同的信息被不必要地重复存储，浪费空间且容易导致数据不一致。

   • 更新异常：修改一处数据时，需要同步修改多个地方，一旦遗漏就会造成数据不一致。

   • 插入异常 ：本应能够独立存在的信息，因为缺少其他信息而无法存入数据库。

   • 删除异常：在删除某条记录时，导致了本应保留的其他有用信息一同丢失。

2. 规范化的基本思想

   规范化的核心思想可以概括为“一事一地”原则。

   • 原则：一个关系模式（一张表）应该只描述一个独立的实体或一种实体间的联系。

   • 实质：通过逐步消除数据依赖中不合适的成分（如部分依赖、传递依赖等），实现概念的单一化。

   • 实现手段：规范化是通过模式分解 来完成的。即将一个存在问题的、低范式的关系模式，分解成若干个结构更优、范式更高的关系模式的集合。

3. 规范化的过程

二、模式分解理论

在规范化过程中，我们发现一个低级范式的关系模式（如1NF的UN）存在各种问题。解决这些问题的手段就是模式分解，即用一组高级范式的、更小的关系模式来等价地替代它。但是，分解不能随意进行，必须遵循两个基本准则，否则分解后的数据库可能会丢失信息或无法维持原有的约束。

1. 模式分解的定义

• 分解的含义：将一个关系模式 R<U, F> (U是属性集, F是函数依赖集) 替换为一组关系模式的集合 ρ = {R₁<U₁, F₁>, R₂<U₂, F₂>, ..., Rₖ<Uₖ, Fₖ>}。

• 分解的要求：

  1. 属性集的完整性：分解后所有子模式的属性并集必须等于原模式的属性集，即 U = U₁ ∪ U₂ ∪ ... ∪ Uₖ。不能丢失任何属性。

  2. 依赖集的映射：每个子模式 Rᵢ 上的函数依赖集 Fᵢ 是原依赖集 F 在其属性子集 Uᵢ 上的投影。通俗讲，Fᵢ包含了所有那些只涉及Uᵢ中属性的原有依赖。

2. 模式分解的两个核心准则

一个“好”的分解，必须同时满足以下两个性质：

2.1 分解的无损连接性

• 直观含义：将一个关系（表）按照分解后的模式拆分成多个小表后，我们必须能够通过自然连接 (Natural Join) 操作，将这些小表无损地、不多不少地还原成原始的大表。如果连接后产生了原始表中不存在的元组（伪元组），或者丢失了原始表中的某些元组，那么这个分解就是“有损的”。

• 重要性：这是模式分解最基本、必须满足的准则。如果连接是有损的，意味着信息在分解过程中被破坏了，这样的分解是不可接受的。

• 判定准则 (针对分解为两个子模式的情况)：

  • 定理：关系模式 R<U, F> 的一个分解 ρ = {R₁, R₂} 是无损连接的，当且仅当 R₁ 和 R₂ 的公共属性 (U₁ ∩ U₂) 是 R₁ 或 R₂ 中至少一个的超码。

  • 形式化表达：(U₁ ∩ U₂) → (U₁ - U₂) 或者 (U₁ ∩ U₂) → (U₂ - U₁) 至少有一个成立。

  • 例子：SDM(S#, SDN, MN) 分解为 SD(S#, SDN) 和 DM(SDN, MN)。

    • 公共属性是 SDN。

    • 在 DM 中，有函数依赖 SDN → MN，所以 SDN 是 DM 的码（也是超码）。

    • 满足判定准则，因此这个分解是无损连接的。

• 判定算法 (针对分解为多个子模式的情况)：

  • 这是一个通用的表格法，也称为Chase算法。

  • 步骤：

    1. 创建一个 k 行 n 列的表，k 是分解出的子模式数量，n 是原始属性数量。

    2. 如果属性 Aj 属于子模式 Ui，则在表中第 i 行 j 列填入符号 aj。否则，填入 bij。

    3. 反复利用给定的函数依赖集 F。对于每个 X → Y，如果在表中找到两行，它们在 X 对应的列上值相同，就在这两行中将 Y 对应的列的值统一起来（如果一个是 a，另一个是 b，则都改为 a）。

    4. 如果经过反复操作后，表中出现了某一行全部为 a (即 a₁, a₂, ..., an)，则该分解是无损连接的。否则是有损的。

2.2 分解的保持函数依赖性

• 直观含义：原始关系 R 中存在的那些业务约束（即函数依赖集 F），在分解为多个子模式后，仍然能够通过各个子模式的约束（F₁, F₂...）来共同体现。如果某个原始依赖在分解后无法由任何一个子模式单独或组合起来表达，那么这个依赖就丢失了。

• 重要性：保持依赖意味着数据的完整性约束没有丢失。如果依赖不保持，那么应用程序就需要承担额外的逻辑来检查这些跨表的约束，这会增加系统的复杂性和出错的风险。

• 判定方法：

  • 核心思想：判断 F 中每一个函数依赖 X → Y，是否都能从分解后的所有依赖的并集 G = F₁ ∪ F₂ ∪ ... ∪ Fₖ 中推导出来。

  • 算法：

    1. 对于 F 中的每一个依赖 X → Y：

    2. 计算属性集 X 在依赖集 G 下的闭包 X_{G}^{+}。

    3. 如果 Y 的所有属性都包含在 X_{G}^{+} 中 (即 Y ⊆ X_{G}^{+})，说明这个依赖被保持了。

    4. 如果 F 中所有的依赖都被保持了，那么整个分解就是保持函数依赖的。只要有一个没被保持，就不是。

• 例子：

  • R(A, B, C)，F={A→B, B→C}。分解为 R₁(AB) 和 R₂(AC)。

  • F₁={A→B}, F₂={A→C} (因为B→C无法在AC上投影，A→C是推导出的)。G = {A→B, A→C}。

  • 检查 B→C：计算 B 在 G 下的闭包 BG⁺ = {B}。C 不在其中。

  • 结论：依赖 B→C 没有被保持。

3. 模式分解的原则和算法

3.1 模式分解应遵循的原则

理想的模式分解应该同时满足无损连接性和保持函数依赖性。

3.2 模式分解能够达到的范式等级

• 权衡与取舍：有时，为了达到更高的范式（如 BCNF），我们可能不得不放弃保持函数依赖性。

  • 如果目标是既无损连接又保持依赖，那么分解总可以达到 3NF。

  • 如果只要求无损连接，那么分解一定可以达到 BCNF，甚至 4NF。

3.3 模式分解的算法

• 达到3NF且保持依赖的分解算法：

  1. 计算函数依赖集 F 的最小依赖集 Fm。

  2. 对于 Fm 中每个具有相同左部的依赖，将它们分为一组。例如，{X→A, X→B, ...} 成为一组。

  3. 对于每一组依赖，创建一个关系模式，其属性集包含该组依赖中出现的所有属性。

  4. 如果所有这些新创建的关系模式中，没有一个包含原模式 R 的候选码，那么需要额外创建一个只包含 R 某个候选码属性的关系模式。（这条用于保证无损连接）

  • 结果：这样得到的分解既是3NF，又保持依赖，并且是无损连接的。

• 达到BCNF且无损连接的分解算法 (不一定保持依赖)：

  1. 初始分解集合为 {R(U)}。

  2. 循环检查集合中的每个关系模式 Rᵢ：

  3. 如果 Rᵢ 不满足 BCNF，说明存在一个非平凡依赖 X → Y，其中 X 不是 Rᵢ 的超码。

  4. 将 Rᵢ 分解为两个子模式：Rᵢ₁ (XY) 和 Rᵢ₂ (Uᵢ - Y)。

  5. 用 {Rᵢ₁, Rᵢ₂} 替换掉集合中的 Rᵢ。

  6. 重复此过程，直到集合中所有关系模式都满足 BCNF。

  • 结果：这样得到的分解一定是BCNF，并且是无损连接的，但不保证保持依赖。

候选码的求解理论和算法

在关系模式 R<U, F> 中，候选码是能唯一标识元组的最小属性集。求解候选码的过程，本质上就是寻找满足 K⁺ = U (K的闭包等于全集U) 且自身无冗余的属性集K。

1. 快速求解候选码的理论基础

通过分析属性在函数依赖集 F 的左右两边出现的情况，我们可以快速地对属性进行分类，从而缩小寻找候选码的范围。

属性分类： 对于关系 R<U, F>，其所有属性可分为以下四类：

• L类 (Left)：仅出现在函数依赖左部的属性。

• R类 (Right)：仅出现在函数依赖右部的属性。

• N类 (Neither)：在函数依赖左右两边均未出现的属性。

• LR类 (Left-Right)：在函数依赖左右两边均出现的属性。

基于分类的三个核心定理：

• 定理1 (L类属性)：L类属性必定包含在 R 的任何一个候选码中。

  • 直观理解：L类属性无法被其他任何属性推导出来（因为它从未出现在右部），所以要推导出所有属性，它必须作为起点。因此，任何想成为候选码的属性组合，都必须包含所有的L类属性。

• 定理2 (R类属性)：R类属性必定不包含在 R 的任何候选码中。

  • 直观理解：R类属性可以被其他属性推导出来，但它不能推导出任何其他属性（因为它从未出现在左部）。如果一个属性集包含了R类属性，那么去掉这个R类属性后，剩下的属性集仍然能推导出它，说明原来的属性集不是最小的，所以不可能是候选码。

• 定理3 (N类属性)：N类属性必定包含在 R 的任何一个候选码中。

  • 直观理解：N类属性既不能推导出其他属性，也不能被其他属性推导出。它是一个“孤立”的属性。要推导出包含它在内的全集 U，它必须被包含在候选码内。

重要推论：

• 将所有 L类 和 N类 的属性组合在一起，形成一个属性集 X。

• 计算 X 的闭包 X⁺。

• 如果 X⁺ = U (包含了所有属性)，那么 X 就是 R 的唯一候选码。这是一个非常快速的判定方法。

2. 多属性依赖集候选码求解算法

当仅靠L类和N类属性无法确定唯一候选码时（即 (L ∪ N)⁺ ≠ U），我们需要进一步考虑LR类属性的组合。

算法步骤：

1. 分类：将关系 R 的所有属性分为 L、R、N、LR 四类。

2. 确定基础：令基础属性集 X = L ∪ N。根据定理1和3，任何候选码都必须包含 X。

3. 计算基础闭包：计算 X⁺。

   • 如果 X⁺ = U，则 X 是唯一候选码，算法结束。

   • 如果 X⁺ ≠ U，则说明候选码还需要从 LR类 属性中添加成员。

4. 组合测试：将 LR 类中的属性逐个或组合地加入到基础集 X 中，并测试其闭包。

   • 逐个添加：依次取 LR 类中的一个属性 A，形成测试集 (X ∪ {A})，计算其闭包 (X ∪ {A})⁺。如果闭包等于 U，则 (X ∪ {A}) 是一个候选码。

   • 组合添加：如果逐个添加都不能构成候选码，则依次取 LR 类中的两个属性 A, B，形成测试集 (X ∪ {A, B})，计算其闭包... 以此类推，直到找到所有最小的组合，使其闭包为 U。

示例： R(A, B, C, D, E)，F = {A→B, BC→D, D→E, E→A}

1. 分类：

   • L类：{C} (仅在 BC→D 左部)

   • R类：无

   • N类：无

   • LR类：{A, B, D, E}

2. 基础集：X = {C}

3. 计算基础闭包：C⁺ = {C}。不等于 U。

4. 组合测试 (从LR类中添加)：

   • (C ∪ {A})⁺ = (CA)⁺ = {C, A, B, D, E} = U。 (CA) 是一个候选码。

   • (C ∪ {B})⁺ = (CB)⁺ = {C, B, D, E, A} = U。 (CB) 是一个候选码。

   • (C ∪ {D})⁺ = (CD)⁺ = {C, D, E, A, B} = U。 (CD) 是一个候选码。

   • (C ∪ {E})⁺ = (CE)⁺ = {C, E, A, B, D} = U。 (CE) 是一个候选码。

结论：该关系模式有四个候选码：(CA), (CB), (CD), (CE)。

3. 左边为单属性的候选码图论判定法

这是一个更直观但有使用限制的方法，仅当函数依赖集的最小依赖集中所有依赖的左部都是单个属性时适用。

• 构造依赖图：

  • 每个属性是一个节点。

  • 每个单属性依赖 A→B 是一条从 A 到 B 的有向边。

• 术语定义：

  • 入度：指向一个节点的边的数量。

  • 出度：从一个节点出发的边的数量。

• 节点分类：

  • 源点 (Source)：入度为0，出度>0的节点。（对应L类属性）

  • 汇点 (Sink)：入度>0，出度=0的节点。（对应R类属性）

  • 孤立点 (Isolated)：入度和出度都为0的节点。（对应N类属性）

  • 中间点 (Intermediate)：入度和出度都>0的节点。（对应LR类属性）

• 求解规则：

  1. 关键属性：找到图中所有的源点和孤立点。这些节点对应的属性是任何候选码都必须包含的。

  2. 唯一候选码判定：如果关键属性的集合能够到达图中的所有其他节点（即其闭包为U），则它就是唯一候选码。

  3. 多候选码情况：如果关键属性不能到达所有节点，则需要从中间点中选择一部分加入到关键属性集中，形成候选码。通常，这与图中的回路 (cycle) 有关。

这个图论方法提供了一个可视化的视角来理解属性间的依赖传递关系，对于简单的单属性依赖集，求解过程非常直观。但对于包含多属性左部的依赖集，还是需要使用通用的闭包求解算法。

第六章 数据库设计

数据库设计阶段概述

1. 什么是数据库设计？

数据库设计是指针对一个给定的应用环境，通过分析和建模，设计出优化的数据库逻辑结构和物理结构，并在此基础上建立数据库及其应用系统。其根本目标是能够有效地存储数据，并为开发满足用户需求的应用程序奠定坚实基础。

• 特点：

  • 数据库设计既需要像第五章学习的规范化理论等科学方法作为指导，也需要结合具体的业务场景和经验进行权衡。

  • 设计不仅要关注数据如何组织存储（数据设计），还要紧密结合数据如何被使用（处理设计）。

  • 它是一个复杂的工程过程，涉及硬件、软件和管理等多个层面，需要迭代和逐步求精。

2. 数据库设计的两种方法

历史上，数据库设计方法经历了从简单到复杂、从非规范到规范的演变。

• 手工试凑法 (直接设计法)：

  • 过程：设计者根据个人经验和对业务的理解，直接确定数据库的表结构、字段等。

  • 缺点：

    • 缺乏科学依据：高度依赖设计者个人能力，面对复杂系统时很难保证设计的质量和效率。

    • 设计一体化：将逻辑结构、物理结构、处理需求等混在一起考虑，难以优化和评估。

    • 维护性差：缺乏设计文档，难以适应需求变化，不易于团队协作和后期维护。

    • 移植性差：设计与具体的DBMS紧密耦合。

  • 适用场景：仅适用于非常简单、关系清晰的小型系统。

• 数据库规范设计法 (主流方法)：

  • 核心思想：借鉴软件工程的思想，将整个设计过程划分为多个相互独立又紧密衔接的阶段。通过“自顶向下，逐步求精”的方式，将一个复杂的大问题分解为若干个简单的小问题，在每个阶段集中解决一部分问题。

  • 特点：

    • 阶段化、结构化：设计过程清晰，每个阶段有明确的任务和产出。

    • 迭代与求精：每个阶段完成后都会进行评审和分析，不满足要求则返回前一阶段修改，是一个循环上升的过程。

    • 文档驱动：每个阶段都会产生标准的设计文档（如数据字典、E-R图等），便于沟通、评审和维护。

3. 数据库设计的六个阶段 (规范设计法)

1. 需求分析

   • 任务：深入了解用户的实际需求，包括需要存储哪些数据以及对这些数据进行哪些处理。

   • 核心：这是整个设计的基石，此阶段的准确性和完整性直接决定了最终系统的成败。

   • 产出：需求说明书、数据字典、数据流图等。

2. 概念结构设计

   • 任务：将需求分析阶段得到的用户需求，抽象成一个独立于任何具体DBMS的概念模型。

   • 核心：构建能够真实、完整反映现实世界信息结构的 E-R 图。这个模型是设计者与用户沟通的桥梁。

   • 产出：E-R图。

3. 逻辑结构设计

   • 任务：将概念模型（E-R图）转换为特定DBMS所支持的数据模型（如关系模型），并对其进行优化。

   • 核心：

     1. E-R图到关系模式的转换。

     2. 应用规范化理论（1NF, 2NF, 3NF, BCNF...）对关系模式进行检查和优化，消除冗余和异常。

   • 产出：一组优化的关系模式（表结构定义）。

4. 物理结构设计

   • 任务：为逻辑结构设计好的关系模式选择最合适的物理存储结构和存取方法。

   • 核心：关注性能、存储效率和响应时间。包括确定数据的存放位置、设计索引、选择聚集等。

   • 产出：数据库的内模式定义（存储参数、索引定义等）。

5. 数据库实施

   • 任务：根据逻辑设计和物理设计的结果，在目标DBMS上建立数据库。

   • 核心：

     1. 使用DBMS提供的DDL（数据定义语言）创建数据库、表、视图、索引等。

     2. 组织数据入库。

     3. 编写和调试应用程序。

   • 产出：一个可以运行的数据库系统。

6. 数据库运行和维护

   • 任务：在数据库系统投入运行后，进行长期的监控、维护和优化。

   • 核心：保证系统的稳定、高效和安全。包括数据备份与恢复、性能监控与调优、数据库重组与重构等。

   • 产出：系统运行报告、维护日志等。

需求分析

需求分析是数据库设计的起点，其核心任务是深入理解并准确描述用户需要什么。

1. 需求分析的目标

需求分析始终围绕两个核心要素：“数据”和“处理”。

具体来说，目标包括收集以下三类需求：

1. 信息要求 (数据需求)：

   • 内容：指系统中需要存储和管理哪些数据，以及这些数据之间存在什么样的联系。

   • 任务：

     • 识别数据项：收集所有需要用到的数据字段，明确它们的名称（如“学生姓名”）、类型（如文本、数字、日期）、长度（如 VARCHAR(50)）、值域等。

     • 识别实体与联系：搞清楚系统中有哪些核心的客观事物（如“学生”、“课程”、“教师”），以及它们之间是如何关联的（如一个学生可以选修多门课程，构成“多对多”联系）。

2. 处理要求 (功能需求)：

   • 内容：指用户希望对数据执行哪些操作，以及对这些操作的性能要求。

   • 任务：

     • 明确处理功能：用户要完成什么业务功能？（如录入学生信息、查询课程成绩、生成统计报表等）。

     • 明确处理性能：对关键操作的响应时间有什么要求？（如查询必须在1秒内返回结果）。

     • 明确处理方式：是联机事务处理还是批处理？数据更新的频率是怎样的？

3. 安全性与完整性要求：

   • 安全性要求：

     • 哪些数据是敏感的？

     • 不同类型的用户（如管理员、普通员工、访客）对数据的访问权限（增、删、改、查）应该如何控制？

   • 完整性要求：

     • 实体完整性：如学号必须唯一且不能为空。

     • 参照完整性：如选课表中的学号必须在学生表中存在。

     • 用户自定义完整性：定义一些特定的业务规则，如“学生年龄必须在15到30岁之间”，“成绩必须在0到100分之间”。

2. 需求分析的方法与阶段

1. 调查用户需求 (收集阶段)：

   • 目标：与用户充分沟通，收集第一手资料，形成对需求的初步理解。

   • 关键：与用户达成共识，确保设计者和用户的理解是一致的。

2. 分析与表达需求 (整理与建模阶段)：

   • 目标：将收集到的、可能是零散的、非结构化的需求信息，整理成规范的、结构化的文档，以便于后续的设计和评审。

   • 核心工具：

     • 数据流图 (Data Flow Diagram, DFD)

     • 数据字典 (Data Dictionary, DD)

3. 需求的表达工具

a. 数据流图 (Data Flow Diagram, DFD)

DFD 是一种图形化工具，用于描述系统的数据流动和处理过程。它直观地展示了数据从何而来（数据源）、经过了哪些处理（处理）、存储在哪里（数据存储）以及最终流向何处（数据终点）。

• 基本元素：

  • 数据源/数据终点 (方框)：系统外部的实体，是数据的起点或终点。

  • 处理 (圆角矩形或圆形)：对数据进行变换或操作的功能。

  • 数据存储 (两条平行线)：数据的静态存储位置，可以看作是“文件”或“数据表”。

  • 数据流 (带箭头的线)：表示数据在以上三种元素之间的流动方向和内容。

• 特点 (结构化分析)：DFD 采用自顶向下、逐层分解的方法。从一个表示整个系统的顶层图开始，逐步将复杂的“处理”分解为更详细的子图，形成层次化的数据流图集合，从而清晰地展现系统的全貌和细节。

b. 数据字典 (Data Dictionary, DD)

数据字典是对 DFD 中所有数据元素进行集中定义和详细描述的文档。

概念结构设计

1. 概念结构设计的目标与工具

• 目标：

  1. 真实反映现实世界：准确、完整地描述应用所涉及的数据和它们之间的联系。

  2. 易于理解：模型应清晰直观，不仅设计人员能看懂，也要能方便地与用户进行沟通和确认。

  3. 独立于具体技术：不考虑所选用的DBMS是关系型、层次型还是网状型，也不考虑具体的存储细节，只关注信息本身的逻辑结构。

• 核心工具——E-R法 (实体-联系法, Entity-Relationship Approach)：

  • 思想：E-R法认为，现实世界是由一组称作实体的基本对象和这些对象之间的联系组成的。它提供了一套图形化的表示方法（E-R图），用以描述这种实体、联系以及它们的属性。

  • 两个组成部分：

    1. 用E-R图描述现实世界：建立概念模型。

    2. 将E-R图转换为具体的数据模型：这是下一阶段“逻辑结构设计”的任务。

2. 概念结构设计方法

对于大型复杂系统，直接绘制一个完整的E-R图非常困难。因此，通常采用结构化的设计方法，最常用的是自底向上的方法。

自底向上设计方法 (视图集成法)

该方法将整个设计过程分为两个阶段：

阶段一：局部E-R图设计 (分E-R图设计)

1. 选择局部应用：从整个系统中划分出一个个功能明确、相对独立的子系统或用户视图（如“物资管理子系统”、“销售管理子系统”）。

2. 建立实体模型：基于需求分析阶段的数据字典，对每个局部应用进行初步抽象，识别出该范围内的实体和属性。

3. 确定联系类型：分析实体之间的关联，确定它们是1:1, 1:n还是m:n的联系。

4. 绘制分E-R图：用E-R图表示出该局部应用中的实体、属性和联系。

实体模型设计的调整原则：

• 属性的原子性：属性必须是不可再分的。如果一个属性（如“职称”）还需要描述更多信息（如“职称代码”、“工资标准”），那么它应该被提升为一个新的实体。

• 联系的归属：联系是实体之间的，属性不能直接与其他实体发生联系。如果一个属性（如“病房号”）实际上与另一个实体（“病房”）相关，那么应将该属性提升为实体。

• 实体与属性的联系：实体与其属性之间应为1:1或n:1的关系。如果出现1:n或m:n关系（如一个学生有多个“课程号”），那么该属性（“课程号”）应被提升为一个新的实体（“课程”），并通过一个m:n的联系（“选修”）与原实体（“学生”）连接。

阶段二：综合局部E-R图形成总E-R图 (视图集成)

当所有子系统或用户视图的局部E-R图（分E-R图）设计完成后，就需要将它们综合起来，形成一个能反映整个系统、统一的、全局的概念模型，即总E-R图。

设计总E-R图的两种方法

根据集成的策略不同，主要有两种方法：

1. 一次性集成 (a)：将所有设计好的分E-R图一次性地合并起来，进行冲突解决和优化。

   • 优点：比较直接。

   • 缺点：当分E-R图数量很多时，一次性处理所有冲突会非常复杂，难以驾驭。

2. 逐步集成 (b) - 更常用：采用累加的方式，一次只集成两个分E-R图。先将两个分E-R图集成为一个中间结果，然后再用这个中间结果去和第三个分E-R图集成，以此类推，直到所有分E-R图都被集成进来。

   • 优点：每次处理的冲突范围较小，问题分解得更细，更易于控制和实现。

集成局部E-R图的两个步骤

无论采用哪种集成方法，具体的集成过程都包含以下两个核心步骤。

步骤一：合并与冲突解决 -> 生成“初步E-R图”

• 任务：将各个分E-R图的实体、属性和联系进行叠加合并，同时识别并解决在合并过程中出现的各种冲突。

• 冲突的主要类型：

  1. 属性冲突：

     • 类型冲突：同一属性在不同视图中被定义为不同的数据类型（如一个视图中“职工号”是数值型，另一个是字符型）。

     • 取值范围/集合冲突：同一属性的合法取值范围不同。

     • 单位冲突：同一属性的度量单位不同（如“重量”在A视图中是“公斤”，在B视图中是“克”）。

     • 解决方法：通过讨论和协商，统一为一个标准的定义。

  2. 命名冲突：

     • 同名异义：不同的对象（实体、属性或联系）在不同视图中使用了相同的名字。

     • 异名同义：相同的对象在不同视图中使用了不同的名字（如“教师”和“教员”都指同一种实体）。

     • 解决方法：建立全局的命名标准表，对同名异义的对象进行重命名，对异名同义的对象统一为一个标准名称，其他名称可作为别名保留。

  3. 结构冲突：

     • 同一对象的抽象不同：同一个概念在A视图中被抽象为实体，而在B视图中可能被抽象为属性。

       • 解决方法：遵守“属性不能再具有需要描述的性质”和“属性不能与其他实体有联系”的原则。通常将更复杂的抽象（实体）作为标准，即把属性提升为实体。

     • 同一实体在不同视图中的属性不同：实体A在一个视图中有属性{P1, P2}，在另一个视图中有{P1, P3}。

       • 解决方法：取所有属性的并集，即合并后实体A的属性为{P1, P2, P3}。

     • 实体间的联系类型不同：

       • 解决方法：根据全局业务语义进行综合分析和调整。通常，更泛化、约束更弱的联系（如m:n）会覆盖更严格的联系（如1:n）。

         示例

         

• 经过合并和冲突解决后，我们得到一个包含了所有信息但可能存在冗余的初步E-R图。

步骤二：修改与重构 -> 生成“基本E-R图”

• 任务：消除“初步E-R图”中不必要的冗余，设计出结构更简洁、更优化的最终E-R图。

• 冗余的类型：

  • 冗余数据（属性冗余）：指可以由其他基本数据计算或推导出的数据。例如，用量(Q3) = 零件数(Q1) * 耗用量(Q2)，那么“用量”就是一个冗余属性。

  • 冗余联系：指可以由图中其他联系间接导出的联系。例如，如果存在 “产品-组装-零件” 和 “零件-消耗-材料” 的联系，那么 “产品” 和 “材料” 之间的 “使用” 联系，就是一个可以被前两者推导出的冗余联系。

• 消除冗余的方法：

  1. 分析法：

     • 以数据字典和数据流图为依据，通过对业务逻辑的深入分析，找出可由其他数据计算或推导出的属性和联系，然后将其移除。这是最常用、最直接的方法。

       示例

       

  2. 规范化方法：

     • 这是一个更形式化、更理论化的方法。

     • 步骤： a. 把初步E-R图中的每个实体和联系都看作一个关系模式。 b. 写出这些关系模式之间的函数依赖。 c. 应用规范化理论（如求最小覆盖集）来分析这些函数依赖，找出并消除其中的冗余依赖。 d. 将消除冗余依赖后的结果反映回E-R图中，即去掉对应的冗余联系。

• 经过消除冗余后，我们得到一个结构精炼、表达准确的基本E-R图，也即最终的全局概念模型。

逻辑结构设计

逻辑结构设计是概念设计与物理设计之间的关键过渡阶段。

1. 逻辑结构设计的任务

• 核心任务：将概念结构（E-R图）转换为选用的DBMS所支持的数据模型（在现代数据库中，通常指关系模型），并对生成的关系模式进行优化。

• 输入：

  • 全局概念模型（总E-R图）。

  • 需求分析阶段整理的数据字典。

  • 所选用的目标DBMS的特性和限制。

• 输出：

  • 一组优化的关系模式（表结构）。

  • 用户视图（子模式）的定义。

2. 逻辑结构设计的步骤

逻辑结构设计主要包含以下四个步骤：

1. 形成初始关系数据库模式：将E-R图转换为关系模式的集合。

2. 关系模式规范化：应用数据依赖理论（范式理论）对初始模式进行分析和优化。

3. 关系模式优化：根据应用处理要求，对规范化后的模式进行必要的调整。

4. 设计用户子模式（视图）：为不同的用户或应用设计其所需的数据视图。

步骤一：将E-R图转换为关系模型

这是逻辑设计的第一步，也是最核心的技术环节。转换遵循一组明确的规则：

1. 实体的转换

• 规则：一个实体型转换为一个关系模式。

• 属性：实体的属性就是关系模式的属性。

• 码：实体的码（主键）就是关系模式的码。

2. 联系的转换

一个联系也需要转换为一个关系模式，其具体构成取决于联系的类型：

• 1:1 联系：

  • 可以转换为一个独立的关系模式，其属性为参与联系的两个实体的主码以及联系自身的属性。这两个实体的主码在该关系中互为候选码。

  • 更常见的做法：将联系及其属性合并到参与联系的任意一端实体对应的关系模式中，并将另一端实体的主码作为外码加入。

• 1:n 联系：

  • 可以转换为一个独立的关系模式，其属性为参与联系的两个实体的主码以及联系自身的属性。关系模式的码是 n端实体的主码。

  • 更常见的做法：将联系及其属性合并到 n端实体对应的关系模式中，并将 1端实体的主码作为外码加入，可以避免产生空值。

• m:n 联系：

  • 规则：必须转换为一个独立的关系模式。

  • 属性：该关系模式的属性由参与联系的所有实体的主码以及联系自身的属性构成。

  • 码：该关系模式的码是参与联系的所有实体主码的组合。

• 多元联系 (三个或以上实体参与)：

  • 规则：与 m:n 联系类似，必须转换为一个独立的关系模式。

  • 属性与码：由参与联系的所有实体的主码及联系属性构成，码是所有实体主码的组合。

在转换过程中，如果生成了两个具有完全相同主码的关系模式，可以将它们合并成一个关系模式，以减少表的数量。

3. 弱实体类型的转换

• 规则：对于每个弱实体类型，创建一个新的关系模式。

• 属性：该关系包含弱实体类型的所有属性。

• 外码：将标识该弱实体的强实体（被依赖方）的主码加入到新关系中，作为其外码。

• 主码：新关系的主码是强实体的主码与弱实体自身的部分标识（部分码）的组合。

4. 超类/子类联系的转换

• 规则：为超类和每个子类都创建一个单独的关系模式。

• 超类关系：包含所有子类共有的属性，包括整个层次结构的主码。可以增加一个“子类判定符”属性（如‘类型’字段）来区分元组属于哪个子类。

• 子类关系：每个子类关系包含超类的主码（作为其主码和外码）以及该子类特有的属性。

步骤二、三：关系模型的规范化与优化

1. 规范化：

   • 任务：按照数据依赖的理论（第五章内容），逐一分析上一步转换所得的关系模式。

   • 目标：判断是否存在部分函数依赖、传递函数依赖等问题，确定每个模式的范式等级（至少达到3NF或BCNF），以消除数据冗余和操作异常。如果范式等级不够，则需要通过模式分解来提高。

2. 优化：

   • 规范化追求的是“一事一地”，可能会导致关系模式被分解得过细，从而在查询时需要进行大量的连接操作，影响性能。因此，需要根据实际应用的处理需求进行权衡和优化。

   • 模式合并：如果两个关系经常被连接查询，并且它们之间是1:1或1:n的联系，可以考虑将它们合并以提高查询效率。这是一种反规范化操作。

   • 模式分解：

     • 水平分解：将一个表的行（元组）按某种条件划分到多个独立的表中（如按地区、按年份）。适用于数据量巨大且访问具有明显局部性的情况。

     • 垂直分解：将一个表的列（属性）划分到多个表中。原则是把经常一起访问的属性放在一个表里，不常用的或特别大的字段（如备注、二进制对象）单独存放。垂直分解必须确保无损连接性和保持函数依赖。

步骤四：设计用户子模式 (视图)

• 任务：根据不同用户或局部应用的需求，在最终确定的关系模式（基本表）之上，设计用户视图（外模式）。

• 目的：

  • 简化用户操作：为用户提供一个定制化的、更简洁的数据视图，隐藏底层表的复杂性。可以将复杂的连接查询封装成一个简单的视图。

  • 保障数据安全：通过视图，可以对不同级别的用户屏蔽敏感数据，只向他们暴露其有权访问的字段和记录。

  • 提供逻辑数据独立性：当底层基本表的结构发生变化时，只要视图的定义不变，面向视图的应用程序就可以不受影响。

• 实现：使用SQL的 CREATE VIEW 语句来定义。

物理结构设计

物理设计是数据库设计过程的第四阶段，它将逻辑数据模型映射到物理存储设备上。

1. 物理设计的任务

• 核心任务：根据目标DBMS的特性、硬件环境以及应用的事务处理需求，设计数据库在物理设备上的存储结构与存取方法。

• 目标：为数据库应用提供高效的存取路径，提高数据库的整体性能（查询速度、更新效率等）。

• 设计内容：

  1. 确定数据库的存储结构：如何将数据文件组织存放在物理磁盘上。

  2. 选择关系的存取方法：为表中的数据建立怎样的数据结构（如索引、聚集等），以加速访问。

2. 确定数据库的存储结构

这部分主要涉及数据文件在物理磁盘上的组织和管理策略。

1. 确定存放位置：

   • 原则：将不同类型、不同访问频率的数据文件分布在不同的物理设备上，以实现I/O负载均衡，减少磁盘竞争。

   • 常见策略：

     • 将经常存取的数据（如热点表、索引）与存取频率较低的数据（如历史归档表）分开放置在不同的磁盘上。

     • 将数据库文件与事务日志文件分开放置在不同的磁盘上。日志文件需要频繁地顺序写入，将其独立出来可以避免与数据文件的随机读写相互干扰。

     • 将数据备份文件放置在与源数据完全独立的磁盘阵列或服务器上，保证数据恢复能力。

2. 确定系统配置：

   • 任务：根据DBMS提供的参数，调整系统配置以优化物理性能。

   • 常见配置项：

     • 内存分配：为数据库缓冲区、日志缓冲区、排序区等分配多大的内存。

     • I/O块大小 (Block Size)：数据库进行读写操作的最小单位。

     • 并发用户数：系统支持的同时连接数量。

     • 锁的配置：锁的数量、升级策略等。

3. 选择关系的存取方法

存取方法是数据在文件中组织的方式，它直接决定了对数据进行查找、插入、删除和更新的效率。物理设计的核心就是为每个关系（表）选择合适的存取方法。

a. 索引 (Index)

• 基本概念：索引是一种独立于数据表的、有序的数据结构，用于加速对表中数据的访问。它类似于书的目录，允许数据库系统直接定位到包含特定值的记录，而无需扫描整个表。

• 核心组成 (索引项)：

  • 索引域 (键值, Key)：通常是表中一个或多个列的值。

  • 指针 (Pointer)：指向数据表中包含该键值的记录所在的物理地址（磁盘块地址）。

• 常用索引类型——B+树索引：

  • 特点：是一种平衡多路查找树。所有关键字都出现在叶子节点上，并且所有叶子节点通过指针链接在一起，形成一个有序链表。

  • 优点：

    1. 支持随机查找：可以从根节点开始快速定位到任何一个键值。

    2. 支持范围查询和顺序查找：由于叶子节点是有序且相互链接的，可以高效地进行范围扫描（如 WHERE age > 20）和全表有序遍历。

• 选择索引的原则 (创建索引的建议)：

  1. WHERE子句中的列：经常在查询条件中出现的列，是创建索引的首选。

  2. 连接属性 (JOIN列)：经常用于表连接的列（通常是外键），创建索引可以极大地提高连接性能。

  3. 聚合函数中的列：经常作为 MAX(), MIN(), COUNT() 等聚合函数参数的列。

  4. ORDER BY / GROUP BY 子句中的列：经常用于排序和分组的列。

• 注意事项：

  • 索引并非越多越好：

    • 空间开销：每个索引都需要额外的磁盘空间来存储。

    • 维护开销：当对表中的数据进行增、删、改操作时，所有相关的索引都必须同步更新，这会降低数据写入的性能。

  • 因此，需要权衡查询性能的提升和写操作性能的下降，只在必要的列上创建索引。

b. 聚集 (Clustering)

• 基本概念：聚集是指把某个属性（聚集键）值相同的数据记录集中存放在连续的物理块中。

• 核心思想：让数据的逻辑顺序（按聚集键排序）和物理存储顺序尽可能保持一致。

• 优点：当查询条件涉及聚集键时（特别是范围查询），可以极大地减少磁盘I/O次数，因为相关的数据都集中在一起，一次I/O可以读取大量所需记录。

• 限制与选择：

  1. 一个关系只能有一个聚集：因为物理存储顺序只能有一种。

  2. 选择原则：

     • 经常进行范围查询或排序的列。

     • 经常进行连接操作的列。

     • 值重复率高的列（如果每个值都唯一，聚集意义不大）。

  3. 维护开销大：建立和维护聚集的系统开销很大，对于更新操作远多于查询操作的表，不宜使用聚集。

c. HASH方法

• 基本概念：通过一个哈希函数 (HASH function)，将记录的某个属性值（哈希键）直接计算成一个物理存储地址。

• 优点：对于基于哈希键的精确等值查询（如 WHERE id = 'xyz'），其查找速度极快，理论上只需要一次I/O。

• 缺点与选择：

  1. 不支持范围查询：哈希后的地址是无序的，无法高效处理范围查找（如 WHERE id > 'xyz'）。

  2. 适用场景：

     • 表的属性主要用于等值连接或相等比较。

     • 表的大小相对固定、可预知。如果表大小动态变化，容易产生大量哈希冲突，性能会急剧下降（除非DBMS支持动态HASH）。