数据库系统原理

8 min中级2026/10/11

数据库系统原理：关系模型、关系代数、函数依赖、范式理论与查询优化；索引与事务机制的展开深读见 595

知识点地图

知识类别：数据库系统理论——关系模型、关系代数、范式与查询优化的课程主线。
解决什么问题：如何用数学化的模型（集合与关系代数）描述数据，如何设计无冗余的表结构（范式），以及查询语句如何被系统转化为高效的执行计划。
什么时候用到：设计表结构评审范式与反范式、读懂执行计划的理论基础、学习 016-sql/017-mysql 语法篇之前的系统观打底。

本文第 6-7 节的索引复杂度表与事务管理是速查级展开；两大机制的完整深读（B+ 树页 IO 推演、WAL 崩溃恢复）见 595-DatabaseIndexAndTransaction。

1. 数据库系统概述

1.1 数据模型演进

模型	年代	特点
层次模型	1960s	树形结构
网状模型	1960s	图形结构
关系模型	1970s	二维表，数学基础
对象模型	1990s	面向对象
NoSQL	2000s	非关系型
NewSQL	2010s	兼顾关系与扩展

1.2 数据库系统结构

三级模式结构：

外模式：用户视图
概念模式：全局逻辑结构
内模式：物理存储结构

两级映象：

外模式/模式映象：保证逻辑数据独立性
模式/内模式映象：保证物理数据独立性

2. 关系模型

2.1 基本概念

关系：一个二维表
元组：表中的一行
属性：表中的一列
域：属性的取值范围
键：唯一标识元组的属性集

2.2 关系完整性

实体完整性：主键不能为 NULL。

参照完整性：外键必须引用已存在的主键值或为 NULL。

用户定义完整性：业务规则约束（如年龄 > 0）。

3. 关系代数

3.1 基本运算

选择（Selection）： $\sigma_{condition}(R)$

选取满足条件的元组。

投影（Projection）： $\pi_{A_1,A_2,...,A_n}(R)$

选取指定属性列。

并（Union）： $R \cup S$

两关系元组的并集（需并相容）。

差（Difference）： $R - S$

在 R 但不在 S 的元组。

笛卡尔积（Cartesian Product）： $R \times S$

两关系元组的所有组合。

更名（Rename）： $\rho_{new\_name}(R)$

3.2 导出运算

交（Intersection）：

$R \cap S = R - (R - S)$

连接（Join）：

$R \bowtie_{condition} S = \sigma_{condition}(R \times S)$

自然连接：

$R \bowtie S = \pi_{attrs}(\sigma_{R.A=S.A}(R \times S))$

除（Division）：

$R \div S = \{t \mid \forall s \in S: (t, s) \in R\}$

用于”查找包含所有…的…”查询。

3.3 关系代数示例

“查找选修了所有课程的学生”：

$\pi_{学号,课程号}(选课) \div \pi_{课程号}(课程)$

“查找年龄大于20的计算机系学生姓名”：

$\pi_{姓名}(\sigma_{年龄>20 \wedge 系别='计算机'}(学生))$

4. 函数依赖与范式

4.1 函数依赖

定义：若 $R$ 中任意两个元组在属性集 $X$ 上的值相同，则在属性集 $Y$ 上的值也相同，记为 $X \to Y$ 。

Armstrong 公理：

自反律：若 $Y \subseteq X$ ，则 $X \to Y$
增广律：若 $X \to Y$ ，则 $XZ \to YZ$
传递律：若 $X \to Y$ 且 $Y \to Z$ ，则 $X \to Z$

推导规则：

合并律： $X \to Y$ 且 $X \to Z$ ，则 $X \to YZ$
分解律： $X \to YZ$ ，则 $X \to Y$ 且 $X \to Z$
伪传递律： $X \to Y$ 且 $YW \to Z$ ，则 $XW \to Z$

4.2 属性闭包

$X^+ = \{A \mid X \to A \text{ 可由 Armstrong 公理推出}\}$

用途：

判断 $X \to Y$ 是否成立： $Y \subseteq X^+$
求候选键： $X^+ = U$ 的最小属性集

4.3 最小函数依赖集

满足以下条件的函数依赖集 $F$ ：

每个依赖的右部是单个属性
不存在冗余依赖
每个依赖的左部无冗余属性

4.4 范式

1NF：属性不可再分。

2NF：在 1NF 基础上，非主属性完全函数依赖于候选键（消除部分依赖）。

3NF：在 2NF 基础上，非主属性不传递依赖于候选键。

$3NF: X \to Y \implies X \text{ 是超键} \vee Y \text{ 是主属性}$

BCNF：在 3NF 基础上，每个决定因素都是候选键。

$BCNF: X \to Y \implies X \text{ 是超键}$

范式关系：

$BCNF \subset 3NF \subset 2NF \subset 1NF$

4.5 模式分解

无损连接分解：

$R = R_1 \bowtie R_2$

判定条件： $(R_1 \cap R_2) \to (R_1 - R_2)$ 或 $(R_1 \cap R_2) \to (R_2 - R_1)$

保持函数依赖分解：

$F^+ = (F_1 \cup F_2 \cup ... \cup F_n)^+$

目标：既无损连接又保持函数依赖的分解。

总能无损连接地分解到 BCNF
不一定能既无损又保依赖地分解到 BCNF
总能既无损又保依赖地分解到 3NF

5. 关系演算

5.1 元组关系演算

$\{t \mid P(t)\}$

其中 $P(t)$ 是谓词公式。

示例：查找年龄大于20的学生

$\{t \mid Student(t) \wedge t.age > 20\}$

5.2 域关系演算

$\{<x_1, x_2, ..., x_n> \mid P(x_1, x_2, ..., x_n)\}$

5.3 表达能力等价

关系代数 ≡ 元组关系演算（安全表达式）≡ 域关系演算（安全表达式）

6. 查询优化

6.1 查询处理流程

plaintext

SQL 查询 → 解析 → 查询树 → 逻辑优化 → 物理优化 → 执行计划

6.2 逻辑优化（代数优化）

基于等价变换规则的优化：

选择下推：尽早执行选择操作
投影下推：尽早执行投影操作
连接顺序优化：小关系先连接

$\sigma_{c_1 \wedge c_2}(R \bowtie S) = \sigma_{c_1}(R) \bowtie \sigma_{c_2}(S)$

6.3 物理优化

选择操作的实现：

方法	适用条件	代价
顺序扫描	无索引	$O(n)$
索引扫描	有合适索引	$O(\log n + k)$

连接操作的实现：

方法	代价	内存需求
嵌套循环	$O(n \times m)$	低
排序归并	$O(n\log n + m\log m)$	中
哈希连接	$O(n + m)$	高

6.4 代价模型

$\text{总代价} = \text{I/O 代价} + \text{CPU 代价}$

通常 I/O 代价是主要因素：

$C_{IO} = \text{页面读写次数} \times t_{IO}$

7. 事务管理

7.1 ACID 特性

特性	含义	实现技术
原子性	事务不可分割	日志（WAL）
一致性	数据保持一致	约束检查
隔离性	事务互不干扰	锁/MVCC
持久性	提交后永久保存	日志刷盘

7.2 并发问题

问题	描述
脏读	读到未提交数据
不可重复读	同一查询两次结果不同
幻读	同一查询两次行数不同

7.3 隔离级别

级别	脏读	不可重复读	幻读
读未提交	可能	可能	可能
读已提交	避免	可能	可能
可重复读	避免	避免	可能
序列化	避免	避免	避免

7.4 封锁协议

两阶段锁（2PL）：

增长阶段：只加锁，不放锁
收缩阶段：只放锁，不加锁

2PL 保证可串行化，但可能导致死锁。

死锁处理：

超时检测
等待图检测
死锁预防（等待-死亡、伤害-等待）

动手实践

任务：把第 4 节范式理论变成一次真实的设计推演——给「订单系统」设计三套表结构（1NF 带冗余、3NF 规范化、反范式宽表），用同一组查询对比三者的数据量与更新代价。

需求：订单含客户姓名/所在城市、商品名/单价/数量；查询「某城市订单总额」；
第一套（1NF 边缘）：一张大表，客户姓名与城市随每行订单重复；
第二套（3NF）：orders / customers / order_items / products 四表；
第三套（反范式）：在 orders 上冗余 city 列；
用 Python 脚本生成 10 万行模拟数据，分别统计：存储行数 x 重复字段数、「客户改名」要更新几行、「某城市订单总额」要 join 几次。

提示：不用真建数据库，用字典列表模拟即可；关键观察点是「读优化的反范式」与「写优化的 3NF」在两个查询上的代价互换，这正是第 6 节查询优化的设计动机。

参考实现骨架（先自己写，再展开对照）

python

# normalize_lab.py —— 三套结构的代价对比（模拟层，非真 SQL）
import random

CITIES = ["BJ", "SH", "SZ"]
customers = {i: {"name": f"c{i}", "city": random.choice(CITIES)}
             for i in range(1000)}

# 3NF：订单行只存外键
orders_3nf = [{"oid": n, "cust": random.randrange(1000),
               "amount": random.randrange(100, 1000)}
              for n in range(100_000)]
# 1NF：城市随订单冗余
orders_1nf = [{**o, "city": customers[o["cust"]]["city"]} for o in orders_3nf]

def total_by_city_3nf(rows):                 # 两次查表 + 聚合
    total = {}
    for o in rows:
        city = customers[o["cust"]]["city"]
        total[city] = total.get(city, 0) + o["amount"]
    return total

def total_by_city_denorm(rows):              # 直接聚合，零 join
    total = {}
    for o in rows:
        total[o["city"]] = total.get(o["city"], 0) + o["amount"]
    return total

# 更新代价：客户 42 改名 -> 3NF 改 1 行，1NF 需改其所有订单行
rename_hits = [o for o in orders_1nf if o["cust"] == 42]
print("3NF 改 1 行; 1NF 需改", len(rename_hits), "行")

逐段讲解：两套聚合函数的差别就是 join 代价的模拟——3NF 每行都要回 customers 查城市（字典查找模拟 join），反范式版直接读本行； rename_hits 的长度演示了更新异常：冗余列把「改 1 行」放大成「改 N 行」，这正是第 4 节函数依赖 city -> 客户 造成的传递冗余。把 10 万行改成 100 万行再跑，两个 total 函数的耗时差会拉开到肉眼可见 ——查询优化器要消掉的正是这部分代价。

数据库系统原理

知识点地图#

1. 数据库系统概述#

1.1 数据模型演进#

1.2 数据库系统结构#

2. 关系模型#

2.1 基本概念#

2.2 关系完整性#

3. 关系代数#

3.1 基本运算#

3.2 导出运算#

3.3 关系代数示例#

4. 函数依赖与范式#

4.1 函数依赖#

4.2 属性闭包#

4.3 最小函数依赖集#

4.4 范式#

4.5 模式分解#

5. 关系演算#

5.1 元组关系演算#

5.2 域关系演算#

5.3 表达能力等价#

6. 查询优化#

6.1 查询处理流程#

6.2 逻辑优化（代数优化）#

6.3 物理优化#

6.4 代价模型#

7. 事务管理#

7.1 ACID 特性#

7.2 并发问题#

7.3 隔离级别#

7.4 封锁协议#

动手实践#