前置知识: 计算机基础

数据库系统原理

6 min中级

数据库系统原理：关系模型、关系代数、函数依赖、范式理论与查询优化

1. 数据库系统概述

1.1 数据模型演进

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

1.2 数据库系统结构

三级模式结构：

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

两级映象：

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

2. 关系模型

2.1 基本概念

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

2.2 关系完整性

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

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

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

3. 关系代数

3.1 基本运算

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

选取满足条件的元组。

投影（Projection）：πA1,A2,...,An(R)\pi_{A_1,A_2,...,A_n}(R)

选取指定属性列。

并（Union）：R∪SR \cup S

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

差（Difference）：R−SR - S

在 R 但不在 S 的元组。

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

两关系元组的所有组合。

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

3.2 导出运算

交（Intersection）：

R∩S=R−(R−S)R \cap S = R - (R - S)

连接（Join）：

R⋈conditionS=σcondition(R×S)R \bowtie_{condition} S = \sigma_{condition}(R \times S)

自然连接：

R⋈S=πattrs(σR.A=S.A(R×S))R \bowtie S = \pi_{attrs}(\sigma_{R.A=S.A}(R \times S))

除（Division）：

R÷S={t∣∀s∈S:(t,s)∈R}R \div S = \{t \mid \forall s \in S: (t, s) \in R\}

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

3.3 关系代数示例

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

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

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

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

4. 函数依赖与范式

4.1 函数依赖

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

Armstrong 公理：

  1. 自反律：若 Y⊆XY \subseteq X，则 X→YX \to Y
  2. 增广律：若 X→YX \to Y，则 XZ→YZXZ \to YZ
  3. 传递律：若 X→YX \to Y 且 Y→ZY \to Z，则 X→ZX \to Z

推导规则：

  • 合并律：X→YX \to Y 且 X→ZX \to Z，则 X→YZX \to YZ
  • 分解律：X→YZX \to YZ，则 X→YX \to Y 且 X→ZX \to Z
  • 伪传递律：X→YX \to Y 且 YW→ZYW \to Z，则 XW→ZXW \to Z

4.2 属性闭包

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

用途：

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

4.3 最小函数依赖集

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

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

4.4 范式

1NF：属性不可再分。

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

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

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

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

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

范式关系：

BCNF⊂3NF⊂2NF⊂1NFBCNF \subset 3NF \subset 2NF \subset 1NF

4.5 模式分解

无损连接分解：

R=R1⋈R2R = R_1 \bowtie R_2

判定条件：(R1∩R2)→(R1−R2)(R_1 \cap R_2) \to (R_1 - R_2) 或 (R1∩R2)→(R2−R1)(R_1 \cap R_2) \to (R_2 - R_1)

保持函数依赖分解：

F+=(F1∪F2∪...∪Fn)+F^+ = (F_1 \cup F_2 \cup ... \cup F_n)^+

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

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

5. 关系演算

5.1 元组关系演算

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

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

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

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

5.2 域关系演算

{<x1,x2,...,xn>∣P(x1,x2,...,xn)}\{<x_1, x_2, ..., x_n> \mid P(x_1, x_2, ..., x_n)\}

5.3 表达能力等价

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

6. 查询优化

6.1 查询处理流程

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

6.2 逻辑优化（代数优化）

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

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

σc1∧c2(R⋈S)=σc1(R)⋈σc2(S)\sigma_{c_1 \wedge c_2}(R \bowtie S) = \sigma_{c_1}(R) \bowtie \sigma_{c_2}(S)

6.3 物理优化

选择操作的实现：

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

连接操作的实现：

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

6.4 代价模型

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

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

CIO=页面读写次数×tIOC_{IO} = \text{页面读写次数} \times t_{IO}

7. 事务管理

7.1 ACID 特性

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

7.2 并发问题

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

7.3 隔离级别

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

7.4 封锁协议

两阶段锁（2PL）：

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

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

死锁处理：

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