数据库系统原理

1. 数据库系统概述

1.1 数据模型演进

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÷S=\{t\mid \forall s\in S:(t,s)\in R\}$

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

3.3 关系代数示例

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

${\pi }_{学号,课程号}(选课)÷{\pi }_{课程号}(课程)$

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

${\pi }_{姓名}({\sigma }_{年龄>20\wedge 系别{=}^{\prime }计算{机}^{\prime }}(学生))$

4. 函数依赖与范式

4.1 函数依赖

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

Armstrong 公理：

1. 自反律：若 $Y\subseteq X$，则 $X\to Y$
2. 增广律：若 $X\to Y$，则 $XZ\to YZ$
3. 传递律：若 $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$：

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

4.4 范式

1NF：属性不可再分。

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

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

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

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

$BCNF:X\to Y⟹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 查询处理流程

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

6.2 逻辑优化（代数优化）

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

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

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

6.3 物理优化

选择操作的实现：

连接操作的实现：

6.4 代价模型

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

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

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

7. 事务管理

7.1 ACID 特性

7.2 并发问题

7.3 隔离级别

7.4 封锁协议

两阶段锁（2PL）：

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

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

死锁处理：

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