数据库

数据库系统设计部分

键（Key）

  • 主键（Primary Key）
  • 候选键（Candidate Key）：满足唯一性且具备最小性，属性不允许冗余。
  • 超键（Super Key）：满足唯一性即可，不要求最小性。

外键约束（Foreign Key Constraint）

  • 外键（Foreign Key）：某关系中的属性（组）必须在另一关系的主键或候选键中出现。
  • 参照完整性（Referential Integrity）：外键取值必须能在参照关系的候选键中找到，或取 NULL。

外键约束示意

概念模型

  • 实体（Entity）：具备独立存在意义的事物，可具体（学生、课程）也可抽象（成绩单）。
  • 属性（Attribute）：实体的特征或性质。
  • 实体集（Entity Set）：同类实体的集合。
    • 强实体集：可独立存在，拥有自己的主键。
    • 弱实体集：依赖其他实体，不具主键（数据库中常对应从表）。
  • 关系（Relationship）：实体之间的联系，例如学生选课。
  • 关系集（Relationship Set）：同类关系的集合。

约束

  • 基数（Cardinality）：描述实体间关系数量。
    • 一对一（1:1）
    • 一对多（1:N）
    • 多对多（M:N）

E-R 图与关系模型映射

E-R 概念转换后数据库对象
实体集表（Table）
属性列（Column）
关系集外键或中间表
主键主键约束（Primary Key）

转化策略

  • 实体集 → 表，属性 → 列。
  • 关系转换：
    • 1:1：任选一侧添加外键指向另一侧主键。
    • 1:N：在 “多” 端添加外键指向 “一” 端主键。
    • M:N：创建中间表，包含两端主键并联合为主键。

Normalization

目标：对模式 $R$ 消除冗余且保持语义。

正确性条件

无损分解（Lossless Decomposition）

分解后的关系通过自然连接可恢复原关系：

\[r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie \cdots \bowtie \Pi_{R_n}(r)\]
函数依赖

在关系 $R$ 中，若属性集 $X$ 能函数决定属性集 $Y$，记作 $X \to Y$：任意两个元组 $t_1,t_2$，当 $t_1[X] = t_2[X]$ 时必有 $t_1[Y] = t_2[Y]$。

属性集闭包 $X^+$

给定函数依赖集 $F$，$X^+$ 为 $X$ 可推出的全部属性。若 $X^+$ 覆盖 $R$，则 $X$ 为超键；若其真子集都无法覆盖 $R$，则 $X$ 为候选键。

无损分解判据

$R$ 分解成 $R_1, R_2$ 无损，当且仅当

\[(R_1 \cap R_2) \to R_1 \in F^+ \quad \text{或} \quad (R_1 \cap R_2) \to R_2 \in F^+\]

常以属性集闭包表示：

\[(R_1 \cap R_2)^+ \supseteq R_1 \quad \text{或} \quad (R_1 \cap R_2)^+ \supseteq R_2\]

依赖保持（Dependency Preservation）

函数依赖闭包 $F^+$

Armstrong 公理：

  1. 自反性（Reflexivity）：若 $Y \subseteq X$，则 $X \to Y$。
  2. 增强性（Augmentation）：若 $X \to Y$，则 $XZ \to YZ$。
  3. 传递性（Transitivity）：若 $X \to Y$ 且 $Y \to Z$，则 $X \to Z$。

计算 $F^+$ 可自 $F$ 出发反复应用以上规则直至稳定（NP-Hard）。

依赖保持判据

若原模式的所有约束（$F^+$）可由分解后各子关系 $R_i$ 的约束集合 $F_i$ 推导，则称分解保持依赖，即 $F^+ = (\bigcup F_i)^+$。若不保持，则验证约束需跨表连接，代价高。判定同样为 NP-Hard。

实践中常只验证单条依赖 $\alpha \to \beta$：

  1. 初始化 $\rho = \alpha$。
  2. 对每个子关系 $R_i$：
    • 取 $\rho \cap R_i$，在 $F$ 下求闭包并限制在 $R_i$ 内，得 $t$。
    • 更新 $\rho = \rho \cup t$。
  3. 若收敛后 $\beta \subseteq \rho$，则该依赖在分解中被保持。

范式分解

  • 1NF：所有属性值为原子。
  • 2NF：在 1NF 基础上，非主属性完全依赖主键。
  • 3NF：在 2NF 基础上，无传递依赖。
  • BCNF：对 $F^+$ 中每个非平凡依赖 $X \to Y$，左部 $X$ 必为超键。

BCNF

BCNF 消除冗余最彻底，但可能不保持依赖，因此常退而求 3NF。

分解算法：

  1. 检查 $R$ 是否满足 BCNF；若是则结束。
  2. 若存在违反 BCNF 的依赖 $X \to Y$，分解为
    • $R_1 = X \cup Y$
    • $R_2 = R - (Y - X)$
  3. 对 $R_1, R_2$ 递归执行上述过程。

检测：对每条 $X \to Y \in F$，求 $X^+$；若 $X^+$ 不覆盖 $R$ 则不满足 BCNF。

3NF

3NF 在保持依赖与无损分解之间取得折衷。

分解步骤：

  1. 求函数依赖集 $F$ 的规范覆盖 $F_c$。
  2. 初始化分解结果 $\rho = \varnothing$。
  3. 对 $F_c$ 中每个依赖 $\alpha \to \beta$，建立关系模式 $R’ = \alpha \cup \beta$，若未被包含则加入 $\rho$。
  4. 若 $\rho$ 中无候选键，额外加入任意候选键对应的关系。

步骤 3 保证依赖保持，步骤 4 确保无损。

检测：需计算 $F^+$，同样是 NP-Hard。

规范覆盖（Canonical Cover）

给定依赖集 $F$，若 $F_c$ 满足：

  1. $F_c^+ = F^+$；
  2. 无冗余依赖；
  3. 每条依赖右部仅含单个属性；
  4. 无冗余属性；
  5. 左部唯一；

则 $F_c$ 为规范覆盖。

冗余属性 $A$：

  • 若 $A \in \alpha$ 且 $(F - {\alpha \to \beta}) \cup {(\alpha - A) \to \beta}$ 仍可推出 $F$，则 $A$ 在左部冗余。
  • 若 $A \in \beta$ 且 $(F - {\alpha \to \beta}) \cup {\alpha \to (\beta - A)}$ 仍可推出 $F$，则右部冗余。

算法：

  1. 合并相同左部：$\alpha \to \beta$ 与 $\alpha \to \gamma$ 合并为 $\alpha \to \beta\gamma$。
  2. 删除冗余属性，直至 $F$ 不再变化。

分解保持快速检查

只需验证关心的依赖 $\alpha \to \beta$ 是否在分解中成立：

  1. 置 $\rho = \alpha$。
  2. 遍历每个关系 $R_i$，计算 $((\rho \cap R_i)^+) \cap R_i$，并并入 $\rho$。
  3. 若最终 $\beta \subseteq \rho$，则该依赖被保持。

多值依赖

  • 4NF