4. 数据库管理系统

本章从体系结构、访问路径、查询优化、事务恢复与并发控制等角度梳理 DBMS 核心机制。

4.1 体系结构概览

DBMS 架构：整体划分为存储管理、查询处理、事务管理、安全目录等模块。
进程/线程模型：
- 单进程：应用与 DBMS 链接为一个可执行文件。
- 多进程：每个应用进程对应一个 DBMS 服务器进程。
- 多线程：单一 DBMS 进程内部为每个会话派生线程，通过共享内存通信。

4.2 DBMS 核心组件

组件	作用
接口层	解析命令、图形界面、API 与驱动
查询处理	语法分析、语义检查、查询重写、优化与执行器
存储管理	文件/页/缓冲区管理、记录组织、访问方法
目录管理	维护模式、统计信息、权限等元数据
事务与并发	锁/时间戳/多版本、调度、死锁处理
恢复系统	日志、检查点、备份还原
安全与完整性	认证、授权、审计、约束检查

4.3 数据库访问管理

访问效率依赖于合适的文件组织与索引。

常见访问类型

全表或大范围扫描。
定位单条记录（点查）。
小比例条件检索、范围查询。
插入、更新与删除。

文件组织

堆文件：按插入顺序堆积，通用但定位慢。
直接/哈希文件：通过哈希函数计算地址，适合点查。
动态哈希：可扩展桶数，避免冲突集中。
索引顺序文件：索引配合堆或簇文件。
网格文件：支持多属性查询。
原始磁盘（Raw Device）：绕过文件系统直接管理物理块。

索引技术

B+ 树：通用的平衡树索引；可做聚簇或非聚簇。
哈希索引：适合等值查询。
倒排/位图索引：适合文本或低基数属性，常用于数据仓库。
多维结构：如网格文件、分区哈希等。

4.4 查询优化

4.4.1 概述

优化包括两阶段：

代数优化：通过等价变换生成更优的关系代数表示。
代价优化：为每个操作选择具体算法与访问路径，估算 I/O/CPU 成本并选出较优计划。

示例

针对查询：

SELECT SNAME
FROM S, SP, P
WHERE S.SNUM = SP.SNUM
  AND SP.PNUM = P.PNUM
  AND S.CITY = 'Nanjing'
  AND P.PNAME = 'Bolt'
  AND SP.QUAN > 1000;

首先将选择下推、投影裁剪，减少连接输入规模。
再决定连接顺序与算法（嵌套循环、排序-归并、哈希等）。

4.4.2 关系代数等价规则

常用规则包括：

交换律： $E_{1} \times E_{2} \equiv E_{2} \times E_{1}$ ；连接也满足交换。
结合律： $E_{1} \times (E_{2} \times E_{3}) \equiv (E_{1} \times E_{2}) \times E_{3}$ 。
投影吸收：若外层投影属性属于内层，则可合并。
选择吸收：多个选择可合并为一个 conjunction；选择可与投影交互（前提属性满足）。
选择下推： $σ_{F} (E_{1} \times E_{2})$ 可拆分到单个输入，或将仅涉及某表的谓词提前执行。
投影分布到笛卡尔积/并/差。

目标是在连接前尽量缩小操作数，并寻找公共子表达式。

4.4.3 操作层优化

选择/投影：使用索引、位图或覆盖索引；仅保留需要的列。
集合操作：基于排序或哈希实现 UNION/INTERSECT/EXCEPT。
连接：
- 嵌套循环（Block Nested-Loop）：b_R + ceil(b_R / (n_B-1)) * b_S。
- 排序-归并连接：先排序后线性合并，适合已排序数据。
- 索引/哈希辅助连接：利用被连接表上的索引加速探测。
- 哈希连接：构建哈希表再匹配，适合等值连接。

4.5 恢复系统

4.5.1 目标

预防：通过日志、冗余降低故障影响。
恢复：在故障后将数据库恢复到一致状态。

4.5.2 事务与 ACID

原子性：事务要么全部成功要么全部回滚。
一致性：执行前后数据库应满足所有约束。
隔离性：并发事务互不干扰。
持久性：提交后的更新必须持久保存。

4.5.3 恢复相关结构

日志（Log）：记录更新的前像（B.I）与后像（A.I）。
提交列表：记录已提交事务 ID。
活动列表：记录正在执行的事务 ID。
日志应写在非易失性存储，遵守写前日志（WAL）原则。

4.5.4 写入策略与恢复

策略	说明	故障后操作
a. 提交前写 DB	A.I 可在提交前写入；需 WAL（B.I 先写日志）	对活动事务执行 UNDO
b. 提交后写 DB	提交前仅写日志；提交后再写 DB	对已提交但未完成写入的事务执行 REDO
c. 与提交并发	A.I、B.I 均写入日志，部分写入 DB	需要对活动事务 UNDO，对已提交事务 REDO

UNDO/REDO 都是幂等操作，可根据提交/活动列表判定策略。常见实现采用日志 + 周期性备份。

4.6 并发控制

4.6.1 并发与异常

并发提升资源利用率与响应时间，但会导致：

写-写冲突 → 丢失更新。
写-读冲突 → 脏读。
读-写冲突 → 不可重复读、幻读。

4.6.2 可串行化

如果并发调度的效果等价于某个串行执行，则称该调度可串行化。这是并发控制的目标。

4.6.3 锁协议

X 锁（排他锁）

单一锁类型，任何读写都需获取 X 锁。
兼容矩阵：X 仅与 NL 兼容。
两阶段锁（2PL）：所有加锁在解锁之前完成；若事务也遵循“先锁后操作”（well-formed），调度可串行化。

(S, X) 锁

S 锁用于读，X 锁用于写。
兼容性：S 与 S 兼容，X 与任何锁都不兼容。
2PL + 在事务结束（EOT）释放写锁，可避免多米诺效应；若所有锁都持有到 EOT，则为严格 2PL。

(S, U, X) 锁

U（Update）锁用于即将写的读操作，先获取 U 锁后再升级为 X 锁，以缩短排他时间，减少死锁机会。

4.6.4 死锁与活锁

活锁：可通过 FIFO 等调度策略避免。
死锁检测：
1. 超时策略。
2. 绘制等待图（Wait-For Graph），若存在环则发生死锁，需选择牺牲事务回滚。
死锁避免：
1. 事务开始时请求全部锁。
2. 按资源序列加锁。
3. 时间戳策略：
  - Wait-Die：年长事务等待，年轻事务回滚。
  - Wound-Wait：年长事务抢占（杀死）年轻事务，年轻事务等待年长事务。

通过这些机制，DBMS 能在保障正确性的前提下提供高效的并发访问。

Quartz 4

Explorer

CH4-数据库管理系统