Software Systems Atlas

中文

English

中文

English

主题

第 5 卷 / 第 3 章 / 第 2 课

3.2 函数依赖、范式与可验证分解 ​

客户改了名字，多张任务表却各留一份旧称，报表就会开始各说各话。规范化用函数依赖判断哪些事实应当放在同一张表，再验证拆表后能否无损重建、能否分别约束。减少重复是结果，拆掉事实可不算完成。

一个混合 relation ​

假设存在：

text
TaskAssignment(
  task_id,
  item_id,
  customer_id,
  customer_name,
  item_name,
  quantity,
  reward_cents
)

业务规则给出 functional dependencies：

text
task_id -> customer_id, reward_cents
customer_id -> customer_name
item_id -> item_name
(task_id, item_id) -> quantity

若一项 task 可以有多种 item，则 candidate key 是 (task_id, item_id)。把 customer/item 名称重复放在每个 assignment row，会产生 update、insert 与 delete anomaly。

Functional dependency 的含义 ​

X -> Y 表示：在所有合法 relation states 中，任意两 tuples 只要 X 相同，Y 就必须相同。

它是业务 invariant，不是从当前 sample data 猜出来的 correlation。今天每个 name 恰好唯一，不足以证明 name -> id；必须由业务规则保证所有未来合法状态也成立。

Trivial 与 non-trivial ​

若 Y ⊆ X，X -> Y 是 trivial，例如 (task_id, item_id) -> task_id。规范化主要关注 non-trivial dependencies。

Attribute closure 与 candidate key ​

使用 Armstrong axioms 可以推导 dependency：

  • reflexivity：若 Y ⊆ X，则 X -> Y；
  • augmentation：若 X -> Y，则 XZ -> YZ；
  • transitivity：若 X -> Y 且 Y -> Z，则 X -> Z。

对 (task_id, item_id) 求 closure：

text
start: task_id, item_id
task_id -> customer_id, reward_cents
customer_id -> customer_name
item_id -> item_name
(task_id, item_id) -> quantity

closure = all attributes

所以它是 superkey；如果删除其中任一 attribute 都不能决定全部 attributes，它还是 candidate key。

一个 relation 可以有多个 candidate keys。选为 PRIMARY KEY 的是其中一个，其他业务 candidate keys 仍应通过 UNIQUE + NOT NULL 等方式表达。

1NF：不要把它简化成“不能有数组” ​

First Normal Form 要求 relation attribute 在关系模型采用的 domain 中取 atomic value，并且没有 repeating groups。atomic 与具体 domain/查询语义有关：数据库可以把 JSON 当作一个值，但如果业务要对其中 item IDs 做 FK、join 和独立更新，那么把它当 opaque scalar 会失去关系约束。

判断时看内部结构是否属于当前 relation model 需要独立操作的事实，存储类型的名字并不重要。

2NF：消除对 candidate key 的 partial dependency ​

2NF 要求 relation 已在 1NF，且每个 non-prime attribute fully functionally depends on every candidate key。

在 composite key (task_id, item_id) 下：

text
task_id -> reward_cents
item_id  -> item_name

它们只依赖 key 的一部分，违反 2NF。分出：

text
tasks(task_id, customer_id, customer_name, reward_cents)
Items(item_id, item_name)
TaskItems(task_id, item_id, quantity)

若 relation 的每个 candidate key 都只有一个 attribute，就不会有 partial dependency，因此自动满足 2NF；但仍可能违反 3NF/BCNF。

3NF：处理 transitive dependency ​

在 tasks(task_id, customer_id, customer_name, reward_cents) 中：

text
task_id -> customer_id
customer_id -> customer_name

于是 task_id -> customer_name 是 transitive dependency。customer_name 描述 customer，不应由每项 task 重复维护：

text
Customers(customer_id, customer_name)
tasks(task_id, customer_id, reward_cents)

正式 3NF 条件：对每个 non-trivial FD X -> A，X 是 superkey，或 A 是 prime attribute（属于某个 candidate key）。口诀“非 key 只依赖 key”帮助入门，但处理多个 candidate keys 时不够精确。

BCNF：每个 determinant 都是 superkey ​

BCNF 要求对每个 non-trivial FD X -> Y，X 都是 superkey。它比 3NF 更严格。

某些 relation 可以满足 3NF 但不满足 BCNF，因为 RHS 是 prime attribute。分解到 BCNF 可能无法保留所有 dependencies，于是设计者要在 stronger redundancy control 与 dependency preservation 之间取舍。

例如 Teaching(student, course, instructor) 有 student, course -> instructor 和 instructor -> course。候选键是 (student, course) 与 (student, instructor)；instructor -> course 的右侧是主属性，所以符合 3NF，但左侧不是超键，因此不符合 BCNF。

分为 InstructorCourse(instructor, course) 和 StudentInstructor(student, instructor) 后可以无损连接，却不能只靠两表各自的键阻止同一学生选了同一课程的两位教师。这个反例说明：是否分到 BCNF，需要连同跨表约束成本一起决定。 无损连接与依赖保持的正式定义可参阅 Berkeley 规范化讲义。

Lossless join 是分解底线 ​

把 relation R 分解成 R1、R2 后，natural join 应能恢复恰好原 relation，而不是产生 spurious tuples 或丢失事实。

对 binary decomposition，一个常用判据是交集 attributes 能 functionally determine R1 或 R2：

text
(R1 ∩ R2) -> R1
or
(R1 ∩ R2) -> R2

例如：

text
R(task_id, customer_id, customer_name)
R1(task_id, customer_id)
R2(customer_id, customer_name)

交集是 customer_id，且 customer_id -> customer_name，所以这个 binary decomposition 是 lossless。

Dependency preservation ​

若分解后每个原 dependency 都能通过单个 relation constraints 或其投影组合检查，而无需 join 全部 relation，则 dependency-preserving。

lossless 与 dependency preservation 是两个不同属性。一个 decomposition 可以 lossless，却让某项 dependency 只能跨表检查；这会提高 constraint 实现成本。

映射成 SQL schema ​

以下是独立的 SQLite 3.37.0+ 建模练习。使用空数据库和 STRICT 表，连接后先启用 PRAGMA foreign_keys = ON。它没有沿用前两章同名表的全部列。

sql
CREATE TABLE customers (
    customer_id   INTEGER PRIMARY KEY,
    customer_name TEXT NOT NULL
) STRICT;

CREATE TABLE items (
    item_id   INTEGER PRIMARY KEY,
    item_name TEXT NOT NULL
) STRICT;

CREATE TABLE tasks (
    task_id      INTEGER PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    reward_cents  INTEGER NOT NULL CHECK (reward_cents >= 0),
    FOREIGN KEY (customer_id)
        REFERENCES customers(customer_id)
) STRICT;

CREATE TABLE task_items (
    task_id INTEGER NOT NULL,
    item_id  INTEGER NOT NULL,
    quantity INTEGER NOT NULL CHECK (quantity > 0),
    PRIMARY KEY (task_id, item_id),
    FOREIGN KEY (task_id) REFERENCES tasks(task_id),
    FOREIGN KEY (item_id) REFERENCES items(item_id)
) STRICT;

这个 schema 表达了列出的 dependencies，但还没有表达 status transition、历史价格或 tenant isolation；normalization 不替代完整 domain modeling。

Denormalization 是受控复制 ​

为读性能复制 customer_name、保存汇总表或构建 materialized view 可能合理，但要先回答：

  • source of truth 是谁；
  • 何时同步：同 transaction、async event、periodic refresh；
  • 可容忍多长 staleness；
  • 失败如何补偿/rebuild；
  • 如何检测 drift；
  • 是否真的比 index/query rewrite/cache 更合适。

denormalization 指在理解 dependency 后有意维护额外 representation，并非抛弃范式。

不要用范式解决所有问题 ​

Normalization 主要处理 dependency 与 redundancy。以下问题需要其他机制：

  • concurrent write anomalies：transaction isolation/concurrency control；
  • append-only audit：history/event model；
  • analytics performance：columnar layout/materialization；
  • distributed consistency：replication/consensus/transaction protocol；
  • authorization：policy and access control；
  • schema evolution：migration/backfill/compatibility。

练习 ​

给定：

text
Enrollment(student_id, course_id, instructor_id,
           student_name, course_title, instructor_office, grade)

以及：

text
student_id -> student_name
course_id -> course_title, instructor_id
instructor_id -> instructor_office
(student_id, course_id) -> grade
  1. 求 (student_id, course_id)+。
  2. 找出 partial 与 transitive dependencies。
  3. 分解到 3NF。
  4. 说明每一步为什么 lossless。
  5. 列出 keys/FKs/UNIQUE/CHECK，指出仍无法直接用这些 constraint 保证的规则。

验收标准 ​

  • [ ] FD 来自业务 invariant，不从样本偶然性猜测；
  • [ ] 能用 closure 识别 candidate key；
  • [ ] 能精确定义 2NF、3NF 与 BCNF；
  • [ ] decomposition 检查 lossless 与 dependency preservation；
  • [ ] denormalization 写明 source、freshness、repair；
  • [ ] 不把 normalization 与 transaction isolation 混为一谈。

本章小结 ​

ER modeling 决定系统要记录哪些 identity 与 relationship，functional dependencies 则检查每个 relation 是否混合了不同决定因素。好的 schema 让业务事实、key、dependency 和 lifecycle 都有清晰归属，并尽量用 constraint 与 transaction 执行这些约束；表的数量并非目标。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang