为什么需要规范化

  • 坏表的典型问题
    • 冗余 redundancy: 比如 供应商地址, 商品描述被重复存储
    • 插入异常: 插入供应商必须附带商品信息, 关联不大的两个信息要一起插入
    • 删除异常: 删除商品时可能导致供应商信息丢失
    • 更新异常: 修改供应商地址需要更新多行

Normalization 目标: 避免冗余, 找到不同属性之间的依赖性和继承关系

Short Summary: We want tables where the attributes depend on the primary key,
on the whole key, and nothing but (有且仅有) the key.

不过这个方法完全可以用 ER 来解决, 但是这里讲得是另一种思路, 即更加侧重形式化方法实现 functional dependency 的分析和分解.

Redundancy Problems

  • Redundant Storage: 同样的信息被重复存储, 浪费空间
  • Update Anomalies: 更新时需要修改多处, 容易出错
  • Insertion Anomalies: 插入新数据时需要提供不相关的信息
  • Deletion Anomalies: 删除数据时可能丢失有用信息

函数依赖(Functional Dependency, FD)

  • 定义: X →\rightarrow Y, 表示 属性集 X 唯一决定 Y
    • Formal Definition: a form of Integrity Constraint between two sets of attributes
    • 可以理解为给定 X 集合内的所有值, 可以唯一确定整个数据表中每一个 X 对应的 Y 值
    • 例如: SupplierID →\rightarrow SupplierName, SupplierAddress
    • FD 是用来精确描述不同 attributes 之间的 dependency 关系的
    • 一般左边的称为 superkey, 也就是能唯一标识一行的属性集 (candidate/primary key 要求最小集合, superkey 可以不是最小集合)
  • Primary Key IC (Integrity Constraint) 是 FD 的特例
    • 主键决定所有其他属性, 本质上就是一个 FD;
    • PrimKey -> all other attributes

已有数据表的抽象

  • Relation: R(sid, sname, address, birthdate)
  • FDs: FDs(sid -> ..., iid -> ...)

对于这样的数据表关系要找到一个好的 schema , 即我们的目的是 Algo(R,FDs) -> good_schema

Closure 闭包

  • 定义: 给定一个函数依赖集合 F, F+F^+ = 所有能从 F 推导出来的 (推导方法基于下面说的 Armstrong Axioms) 有效 FD 的集合 (包括原本在 F 中的和通过推理得出的);
  • 举例:
    • 已知依赖
      • SupplierID →\rightarrow SupplierName
      • Item →\rightarrow Desc
      • SupplierID, Item →\rightarrow Price
    • 通过推理, 还可以得到:
      • SupplierID, Item →\rightarrow Desc (因为 Item →\rightarrow Desc, 可以和 SupplierID, Item 联合推出)

Armstrong Axioms 公理(推理规则)

  • Reflexivity(自反): Y⊆\subseteqX →\rightarrow X →\rightarrow Y

    • 如果 Y 是 X 的子集, 则 X 决定 Y, 这很好理解, 所以在实际应用中称为 trivial dependency

  • Augmentation(增广): X→\rightarrowY →\rightarrow XZ→\rightarrowYZ

    • 类似 homomorphism 的空间同等变化

  • Transitivity(传递): X→\rightarrowY, Y→\rightarrowZ ⇒\Rightarrow X→\rightarrowZ

  • 可推导:

    • Union: if X→\rightarrowY and X→\rightarrowZ, then X→\rightarrowYZ
    • Decomposition: if X→\rightarrowYZ, then X→\rightarrowY and X→\rightarrowZ

  • 现在的问题就是 AA 这些公理的效果了, 如何判断通过这些公里能否将一个给定 dependency F 能够标准的推导出来的所有空间 F∗F^* 计算出来呢?

    • 这里默认 AA(F) 生成的是 F+F^+, 那么剩下就是证明 set F+=F∗F^+ = F^*, 也就是证明 AA 的 soundness 和 completeness
    • Soundness: 通过 AA 推导出来的 FD 都是有效的, 即 F+⊆F∗F^+ \subseteq F^*
    • Completeness: 所有有效的 FD 都能通过 AA 推导出来, 即 F∗⊆F+F^* \subseteq F^+
    • 这课不考证明, 这里默认二者成立 -> F+=F∗F^+ = F^*

范式(Normal Forms)

逐层约束, 减少问题, 也就是通过定义范式来约束 FD, 进而约束 schema

BCNF(Boyce-Codd Normal Form)

  • 对于任意 FD X →\rightarrow A
    • A ⊆\subseteq X (trivial)
    • X 必须是 superkey (能唯一标识一行)

也就是对所有的依赖关系都必须是从 superkey 出发的, 这样就能保证没有冗余

想象一个供货信息表, 有 oreder_id, customer_id, customer_name 三列, order_id 是主键

  • order_id -> customer_id, customer_name
  • customer_id -> customer_name

由于这里的 customer_id 不是 superkey, 所以不满足 BCNF, 需要拆分成两个表

当然我们直接看也可以看出, customer 除了 id 之外的信息都属于是冗余的, 因为 customer_id 决定了 customer_name

3NF

  • 对于每个 FD X →\rightarrow A:
    • A ∈\in X (平凡依赖)
    • X 是超键
    • A 出现在某个候选键里
      • 这里指的是对任何一个 candidate key K, A ∈\in K, A 只要是一个属性即可, 不用本身是一个 candidate key
  • 允许少量冗余(比 BCNF 宽松)

从直观上理解, 3NF 的额外一条就是说明所有关系都可以部分地提供主键的功能, 冗余有限

分解(Decomposition): 消除 redundancy 的方法

  • 目的: 拆分大表, 消除冗余
  • 两个核心要求
    • Lossless Join(无损连接): 拆开再 join 回来可以完全恢复原始表
      • 判定条件: 交集属性必须能决定其中一个表
    • Dependency Preservation(保持依赖): 原始 FD 可以直接在子表里检查, 不需要 join

优先保证 Lossless Join, 其次考虑 Dependency Preservation
Decomposition 的缺点之一是有些 query 会变得更复杂, 需要 join

Lossless Join

在数据库规范化里, 我们经常会把一个大关系 R 分解成两个子关系 X 和 Y, 例如:

  • R(A, B, C) 分解成 R1R_1(A, B) 和 R2R_2(B, C);

那么问题来了: 当我们把这两个子表再 自然连接 (⋈\bowtie) 回去的时候, 是否能 完全还原原始关系?
用形式化语言来说, 就是 r=πX(r)⋈πY(r)r = \pi_X(r) \bowtie \pi_Y(r) 是否成立?
注意这里的 r⊆(πX(r)⋈πY(r))r\subseteq (\pi_X(r) \bowtie \pi_Y(r)) 总是成立的, 因为自然连接不会 丢失 任何信息, 但是反过来不一定成立. 反过来成立的情况就是 lossless join.

如果能还原 原始关系且不产生额外元组, 就叫 Lossless Join(无损连接);
如果产生了"假 tuple"(spurious tuple), 就叫 有损连接 (Lossy Join);

判定条件

为了方便形式化理解, 判定 Lossless Join 的条件是:

  • 对于关系 R(A,B,C) 分解成 R1R_1(A,B) 和 R2R_2(B,C), 交集属性是 B
  • 如果 B →\rightarrow A 或 B →\rightarrow C, 则分解是无损的

或者直接对子表进行评价, 那么就是 子表 A, B 是否 lossless join, 就看 A∩B→AA \cap B \to A 或 A∩B→BA \cap B \to B 是否成立.

Dependency Preservation

We don’t want the original FDs to span two tables.

当我们把一个关系 R 分解成若干子关系时, 原本的函数依赖集合 F 也需要在子关系中能被检查到;

  • 要求: 分解后, 每个函数依赖最好都能在 某一个子表内部 直接检查, 而不用跨表 join;
  • 形式化: 分解 R→XR \to X, Y 是 依赖保持的, 当且仅当 F+=(FX∪FY)+F^+ = (F_X \cup F_Y)^+
    • 其中 F_X 是定义在 X 上的依赖, F_Y 是定义在 Y 上的依赖

如何将一个关系 R 分解到 BCNF

  • 一个关系 R 本身不满足 BCNF, 通常是因为存在某个依赖 X→YX \to Y, 而 X 不是 superkey;

  • 所以我们要"切开"关系, 让这个违反的依赖在一个小表里单独成立, 从而消除 BCNF 违例;

  • 输入: 关系 R + FDs F

  • 输出: 分解后的若干子关系 满足 BCNF + Lossless Join + 尽量保持依赖

  • BCNF 分解步骤

    1. 找出违反 BCNF 的依赖 X→\rightarrowY
    2. 分解为 R1=(X∪\cupY), R2=(R−Y)
    3. 重复直到所有子关系满足 BCNF

  • 原来的大表 R 不在 BCNF;

  • 但 两个子表 R1,R2R_1, R_2 各自可能已经是 BCNF(或者还需要进一步分解); 最终, 经过递归, 所有子表都会是 BCNF;

  • Lossless Join 一定保证在分解出的 R2R_2 = XY 中, X 是候选键, 所以分解一定是无损连接;

  • Dependency Preserving 不一定保证 BCNF 的分解有可能打散依赖, 使得某些 FD 需要跨表 join 才能检查;