数据库系统复习学习笔记

一、课程复习总览

从课件、作业和 2023/2024 回忆版看，这门课的期末重点不是单纯写 SQL，而是完整考查数据库系统的理论与实现链条：

$$\text{数据库基本概念} \rightarrow \text{关系模型与关系代数} \rightarrow \text{SQL} \rightarrow \text{E-R 设计} \rightarrow \text{函数依赖与范式} \\ \rightarrow \text{完整性与安全性} \rightarrow \text{存储与索引} \rightarrow \text{查询处理与优化} \rightarrow \text{并发控制} \rightarrow \text{故障恢复}$$

作业一集中在关系代数计算和关系代数查询表达，尤其是连接、选择、投影、差、除法语义等题型；作业二集中在函数依赖、闭包、候选码、最小依赖集、范式和分解；作业三集中在外部排序 I/O 和选择运算大小估算。 2024 回忆版则覆盖连接 I/O、投影与差的等价变换、强制安全、函数依赖、散列索引、稀疏索引、E-R 转换、冲突可串行性、锁、3NF 等综合考点。

---

二、数据库系统基本概念

2.1 数据库、数据库管理系统、数据库系统

• 数据库 (DB) 是相互关联的数据集合，通常表现为多个表的集合。
• 数据库管理系统 (DBMS) 是管理数据库的软件系统，例如 MySQL、PostgreSQL、Oracle、SQL Server。
• 数据库系统 (DBS) 是数据库、DBMS、数据库应用、用户、DBA 和硬件平台组成的整体环境。
• 数据库管理员 (DBA) 负责数据库定义、权限管理、备份恢复、性能监控、索引和物理组织维护等。

从用户角度看，DBMS 的功能可以概括为：

功能	含义
数据定义	定义表、视图、索引、约束
数据操纵	插入、删除、修改、查询
数据控制	授权、安全、并发控制
数据维护	备份、恢复、重组、性能分析

---

2.2 数据库三级模式结构

数据库系统的标准结构包括三个层次：

层次	又称	含义
外模式	用户视图	某类用户能看到和使用的数据
概念模式	逻辑模式 / 全局模式	数据库的全局逻辑结构
内模式	物理模式	数据在存储介质上的组织方式

两层映像对应两类数据独立性：

$\text{外模式}/\text{概念模式映像} \Rightarrow \text{逻辑数据独立性}$

$\text{概念模式}/\text{内模式映像} \Rightarrow \text{物理数据独立性}$

常考表述：

• 概念模式又称逻辑模式。
• 将概念模式映射为内模式，体现物理数据独立性。
• 将概念模式映射到外模式，体现逻辑数据独立性。

2023 和 2024 回忆版都出现过模式映像与数据独立性的填空。

---

2.3 数据模型

经典数据模型：

数据模型	数据结构
层次模型	树结构
网状模型	图结构
关系模型	二维表结构
E-R 模型	实体、属性、联系

课件中明确给出：层次模型以树形式组织数据，网状模型以图形式组织数据，关系模型以表形式组织数据，E-R 模型认为现实世界由实体及其联系构成。

关系模型三要素：

1. 数据结构：关系，即表。
2. 数据操作：关系代数、关系演算、SQL。
3. 完整性约束：实体完整性、参照完整性、用户自定义完整性。

---

三、关系模型与关系代数

3.1 关系、关系模式与关系实例

关系模式描述表的结构，例如：

$$Student(Sno, Sname, Sage, Dno)$$

关系实例是某一时刻该关系模式下的具体元组集合。

关系具有以下性质：

性质	说明
列同质	同一列的分量来自同一域
属性名唯一	同一关系模式中属性名不能重复
行列无序	元组顺序和属性顺序在理论上无关
元组不重复	关系是集合，理论上不允许重复元组
属性原子性	每个属性值不可再分，即满足 (1NF)

关系模型是从传统表及其操作抽象而来的，关系模型的基本操作包括并、差、广义积、选择、投影、更名，扩展操作包括交、连接、除法等。

---

3.2 键的概念

概念	定义
超键	能唯一标识元组的属性集
候选键	最小超键，去掉任一属性后不再唯一标识元组
主键	从候选键中选定的一个主要标识
主属性	出现在任一候选键中的属性
非主属性	不出现在任何候选键中的属性
外键	一个关系中的属性集引用另一个关系的候选键或主键

严谨区分：

• 候选键具有唯一性和最小性。
• 超键只要求唯一性，不要求最小性。
• 主键值不能为 NULL。
• 外键可以由多个属性组成。
• 外键允许为空，除非显式声明 NOT NULL。
• 外键删除时不一定级联删除，是否级联取决于 ON DELETE CASCADE 等约束定义。

---

3.3 关系代数基本运算

关系代数五种基本运算：

$$\cup,\quad -,\quad \times,\quad \sigma,\quad \pi$$

即：

运算	符号	含义
并	$R \cup S$	合并两个并相容关系的元组
差	$R - S$	属于 $R$ 但不属于 $S$ 的元组
笛卡尔积	$R \times S$	元组两两组合
选择	$\sigma_F(R)$	按条件 $F$ 筛选行
投影	$\pi_A(R)$	按属性集 $A$ 选列并去重

扩展运算：

$$R \cap S,\quad R \bowtie S,\quad R \div S,\quad \rho(R)$$

2023 回忆版选择题考过关系代数五种基本运算。

---

3.4 选择、投影、连接

选择运算：

$$\sigma_{age>18 \wedge department='CS'}(Student)$$

表示选出年龄大于 18 且属于计算机系的学生。

投影运算：

$$\pi_{Sno,Sname}(Student)$$

表示只保留学号和姓名两列。关系代数是集合语义，投影后自动消除重复元组。

连接运算：

$$R \bowtie_F S = \sigma_F(R \times S)$$

自然连接：

$$R \bowtie S$$

自然连接会在同名属性上自动做等值连接，并且同名属性只保留一份。
注意：如果两个表有多个同名属性，但只希望按其中某一个属性相等连接，应使用等值连接，不要直接使用自然连接。

---

3.5 除法运算

除法用于表达“全部”“所有”“至少包含某集合”等语义。
若：

$$R(X,Y),\quad S(Y)$$

则：

$$R \div S$$

返回所有这样的 $x$：对 $S$ 中每一个 $y$，都有 $(x,y) \in R$。
即：

$$R \div S = \{x \mid \forall y \in S,\ (x,y) \in R\}$$

典型题型：

查询至少学过 21030101 号同学所学全部课程的学生。

关系代数可写为：

$$\pi_{Sno,Cno}(SC) \div \pi_{Cno}(\sigma_{Sno='21030101'}(SC))$$

SQL 中通常用双重 NOT EXISTS 表达“全部”。课件中专门讲了“至少学过某同学学过所有课程”的 NOT EXISTS 模板。

通用逻辑：

$$\text{X 满足所有 Y} \iff \text{不存在某个 Y，使得 X 不满足 Y}$$

---

3.6 关系代数等价变换

查询优化中常用的等价变换：

选择串接律

$$\sigma_{F_1}(\sigma_{F_2}(E)) \equiv \sigma_{F_1 \wedge F_2}(E)$$

投影串接律

若 $A \subseteq B$，则：

$$\pi_A(\pi_B(E)) \equiv \pi_A(E)$$

连接交换律

$$E_1 \bowtie E_2 \equiv E_2 \bowtie E_1$$

连接结合律

$$(E_1 \bowtie E_2) \bowtie E_3 \equiv E_1 \bowtie (E_2 \bowtie E_3)$$

选择下推

若条件 $F$ 只涉及 $E_1$ 中的属性，则：

$$\sigma_F(E_1 \times E_2) \equiv \sigma_F(E_1) \times E_2$$

优化原则：

• 选择尽量下推。
• 投影尽量下推。
• 先做结果较小的连接。
• 尽量避免中间产生巨大笛卡尔积。

---

3.7 一个高频易错变换

2024 回忆版考过：

$$\pi_{A_1,\dots,A_n}(E_1 - E_2) \quad \text{是否等价于} \quad \pi_{A_1,\dots,A_n}(E_1) - \pi_{A_1,\dots,A_n}(E_2)$$

答案：不等价。

反例：

$$E_1(A,B)=\{(1,1)\}$$ $$E_2(A,B)=\{(1,2)\}$$

则：

$$E_1-E_2=\{(1,1)\}$$ $$\pi_A(E_1-E_2)=\{1\}$$

但：

$$\pi_A(E_1)-\pi_A(E_2) = \{1\}-\{1\} = \varnothing$$

所以二者不等价。

根本原因：投影会丢失区分元组的属性，先投影再做差可能错误地删除本不应删除的结果。

---

四、SQL 语言

4.1 SQL 分类

SQL 集 DDL、DML、DCL 于一体。

类别	语句	功能
DDL	CREATE, ALTER, DROP	定义和修改数据库对象
DML	SELECT, INSERT, UPDATE, DELETE	查询与更新数据
DCL	GRANT, REVOKE	授权与撤权

常考：SELECT 是 DML，不是 DDL。2023 回忆版填空考过。

---

4.2 CREATE TABLE 与完整性约束

CREATE TABLE 的功能：

1. 定义关系模式。
2. 定义完整性约束。
3. 定义物理存储特性。

常见约束：

约束	含义
PRIMARY KEY	主键，唯一且非空
UNIQUE	候选键，唯一
NOT NULL	非空
CHECK	用户自定义取值约束
FOREIGN KEY	外键
DEFAULT	默认值

列级约束作用于单列，表级约束可以作用于多列。
例如组合主键必须写成表级约束：

$$PRIMARY\ KEY(Sno,Cno)$$

---

4.3 SELECT 查询结构

标准查询结构：

$$SELECT \quad FROM \quad WHERE \quad GROUP\ BY \quad HAVING \quad ORDER\ BY$$

逻辑处理顺序可理解为：

$$FROM \rightarrow WHERE \rightarrow GROUP\ BY \rightarrow HAVING \\ \rightarrow SELECT \rightarrow DISTINCT \rightarrow ORDER\ BY$$

其中：

• WHERE：分组前筛选元组。
• HAVING：分组后筛选分组。
• DISTINCT：去重。
• 聚集函数包括 COUNT, SUM, AVG, MAX, MIN。

---

4.4 连接查询

隐式连接：

SELECT S.Sname, SC.Cno
FROM Student S, SC
WHERE S.Sno = SC.Sno;

显式连接：

SELECT S.Sname, SC.Cno
FROM Student S
JOIN SC ON S.Sno = SC.Sno;

建议考试书写时优先使用显式 JOIN，语义清晰。

---

4.5 子查询

课件重点讲了三类子查询：IN、SOME/ALL、EXISTS。

4.5.1 IN 子查询

$$x \in S$$

表示 $x$ 是集合 $S$ 的成员。
例如：查询选修 001 号课程的学生姓名。

SELECT Sname
FROM Student
WHERE Sno IN (
    SELECT Sno
    FROM SC
    WHERE Cno = '001'
);

---

4.5.2 SOME / ALL 子查询

$$x > SOME(S)$$

表示 $x$ 大于集合 $S$ 中至少一个值。

$$x > ALL(S)$$

表示 $x$ 大于集合 $S$ 中所有值。

重要等价关系：

$$= SOME \equiv IN$$ $$<> ALL \equiv NOT\ IN$$

注意：

$$<> SOME \not\equiv NOT\ IN$$

例：找工资最低的教师。

SELECT Tname
FROM Teacher
WHERE Salary <= ALL (
    SELECT Salary
    FROM Teacher
);

---

4.5.3 EXISTS 子查询

$$EXISTS(S)$$

判断子查询结果是否非空。

例如：查询选修了 001 号课程的学生姓名。

SELECT Sname
FROM Student S
WHERE EXISTS (
    SELECT *
    FROM SC
    WHERE SC.Sno = S.Sno
      AND SC.Cno = '001'
);

这是相关子查询，因为内层查询引用了外层的 S.Sno。

---

4.6 相关子查询与非相关子查询

类型	特征
非相关子查询	内层查询不依赖外层查询，可独立执行
相关子查询	内层查询依赖外层当前元组，通常反复执行

相关子查询只能由外层向内层传递参数，不能反向传递。

---

4.7 “所有 / 全部”查询模板

这类题是 SQL 和关系代数的高频综合题。

题型：

• 查询学过某教师主讲所有课程的学生。
• 查询至少学过某学生所学全部课程的学生。
• 查询在某员工所有工作分支机构中都工作的员工。

通用 SQL 逻辑：

SELECT ...
FROM X
WHERE NOT EXISTS (
    SELECT *
    FROM Y
    WHERE NOT EXISTS (
        SELECT *
        FROM R
        WHERE R.x_id = X.id
          AND R.y_id = Y.id
    )
);

含义：

$$\neg \exists y \in Y,\ \neg R(x,y)$$

等价于：

$$\forall y \in Y,\ R(x,y)$$

所以双重 NOT EXISTS 是 SQL 中表达“所有”的核心模板。

---

五、E-R 模型与数据库设计

5.1 数据库设计过程

数据库设计分为三层：

阶段	结果
概念设计	E-R 图 / 概念模型
逻辑设计	关系模式
物理设计	文件组织、索引、存储结构

课件中把概念设计、逻辑设计和物理设计分别对应概念模式、逻辑模式和物理模式。

---

5.2 E-R 模型基本概念

概念	含义
实体	客观存在并可区分的对象
实体集	同类实体的集合
属性	实体的特征
键	唯一标识实体的属性或属性组
联系	实体之间的关联
角色	实体在联系中扮演的作用

属性类型：

类型	说明
简单属性	不可再分
复合属性	可继续分解，如地址
单值属性	每个实体一个值
多值属性	每个实体多个值，如电话号码
派生属性	可由其他属性计算得到，如年龄
可空属性	允许为空

联系的度：

$$1元联系,\quad 2元联系,\quad n元联系$$

联系的映射基数：

$$1:1,\quad 1:N,\quad M:N$$

参与约束：

• 完全参与：每个实体实例都必须参与联系。
• 部分参与：实体实例可以不参与联系。

---

5.3 E-R 图转换为关系模式

强实体转换

每个强实体集转换为一个关系模式。

例如：

$$Student(Sno,Sname,Sage)$$

---

1:1 联系转换

可将任意一方主键加入另一方作为外键；若某一方完全参与，通常把外键放在完全参与的一方。

---

1:N 联系转换

把 1 端主键加入 N 端作为外键。

例如：

$$Dept(Dno,Dname)$$ $$Student(Sno,Sname,Dno)$$

其中 Student.Dno 是外键。

2024 回忆版问过：无属性的 1:m 联系如何转换。答案是：不必单独建联系表，把 1 端主键加入 m 端关系作为外键即可。

---

M:N 联系转换

必须单独转换为一个关系模式，联系双方主键作为外键，并通常共同组成主键。

例如学生选课：

$$Student(Sno,Sname)$$ $$Course(Cno,Cname)$$ $$SC(Sno,Cno,Score)$$

其中：

$$PRIMARY\ KEY(Sno,Cno)$$

2024 选择题也考过两个实体之间存在 m:n 联系时，转换后通常包含三个关系模式：两个实体关系 + 一个联系关系。

---

多值属性转换

多值属性应单独建关系。

例如学生有多个电话：

$$Student(Sno,Sname)$$ $$StudentPhone(Sno,Phone)$$

---

弱实体转换

弱实体关系中包含所属强实体的主键作为外键，并与弱实体自身的部分键共同组成主键。

---

六、完整性与安全性

6.1 数据库完整性

数据库完整性是指 DBMS 保证数据库在任何情况下的正确性、有效性和一致性。

关系模型中的三类完整性：

类型	含义
实体完整性	主键唯一且非空
参照完整性	外键要么为空，要么引用被参照关系中已有的键值
用户自定义完整性	用户定义的业务规则，如年龄范围、工资非负

---

6.2 完整性约束分类

按约束对象分：

类型	说明
域完整性约束	作用于单列
关系完整性约束	作用于元组、多列或关系之间

按约束来源分：

类型	说明
结构约束	主键、外键、函数依赖
内容约束	工资大于 0、成绩在 0 到 100

按约束状态分：

类型	说明
静态约束	任一时刻都应满足
动态约束	状态变化时应满足，如工资只能升不能降

---

6.3 安全性

数据库安全性控制主要包括自主访问控制和强制访问控制。

自主访问控制 DAC

常用 SQL：

$$GRANT,\quad REVOKE$$

例如：

GRANT SELECT ON Student TO user1;
REVOKE SELECT ON Student FROM user1;

---

强制访问控制 MAC

用户和数据对象都有安全级别：

$$Level(S),\quad Level(O)$$

其中 $S$ 表示主体，$O$ 表示客体。

典型规则：

• 读规则：主体可以读客体，当且仅当

$$Level(S) \ge Level(O)$$

• 写规则：主体可以写客体，当且仅当

$$Level(S) \le Level(O)$$

即：

$$\text{no read up},\quad \text{no write down}$$

一般来说，权限 $U < C < S < TS$。

2024 回忆版考过强制安全机制中“用户什么时候可以写数据对象”。

---

七、函数依赖、范式与模式分解

这是本课程最重要的理论部分之一，也是第二次作业核心。第二次作业明确要求计算闭包、找候选码、求最小等价依赖集、判断范式、判断分解是否保持依赖和是否满足 BCNF。

7.1 函数依赖

设关系模式为 $R(U)$，$X,Y \subseteq U$。若对 $R$ 的任意合法关系实例，任意两个元组只要在 $X$ 上取值相同，则在 $Y$ 上取值也相同，则称：

$$X \rightarrow Y$$

即 $X$ 函数决定 $Y$，或 $Y$ 函数依赖于 $X$。

例：

$$Sno \rightarrow Sname,Sage,Dno$$ $$Dno \rightarrow Dean$$ $$(Sno,Cno) \rightarrow Score$$

课件强调函数依赖、完全依赖、部分依赖、传递依赖、候选键、非主属性、逻辑蕴涵、属性闭包等是本章重点。

---

7.2 平凡函数依赖

若：

$$Y \subseteq X$$

则：

$$X \rightarrow Y$$

称为平凡函数依赖。

例如：

$$AB \rightarrow A$$ $$ABC \rightarrow BC$$

2024 回忆版问“函数依赖右端是左端子集时称为什么”，答案就是平凡函数依赖。

---

7.3 完全依赖、部分依赖、传递依赖

完全函数依赖

若：

$$X \rightarrow Y$$

且 $X$ 的任何真子集 $X'$ 都不能决定 $Y$，则 $Y$ 完全函数依赖于 $X$。

记作：

$$X \xrightarrow{f} Y$$

部分函数依赖

若：

$$X \rightarrow Y$$

但存在 $X' \subset X$，使得：

$$X' \rightarrow Y$$

则 $Y$ 部分函数依赖于 $X$。

传递函数依赖

若：

$$X \rightarrow Y,\quad Y \rightarrow Z$$

且 $Y$ 不是 $X$ 的子集，$Z$ 不函数依赖于 $Y$ 的平凡部分，则称：

$$X \rightarrow Z$$

为传递依赖。

---

7.4 属性闭包

属性集 $X$ 关于函数依赖集 $F$ 的闭包记为：

$$X_F^+$$

或简写为：

$$X^+$$

表示由 $X$ 根据 $F$ 能推出的所有属性。

计算步骤：

1. 初始令 $X^+ = X$。
2. 若存在依赖 $A \rightarrow B$，且 $A \subseteq X^+$，则把 $B$ 加入 $X^+$。
3. 重复直到 $X^+$ 不再变化。

用途：

• 判断 $X$ 是否为超键：若 $X^+=U$，则 $X$ 是超键。
• 判断 $X \rightarrow Y$ 是否被 $F$ 蕴涵：若 $Y \subseteq X^+$，则 $F \models X \rightarrow Y$。
• 求候选键。
• 判断依赖保持。

例：2024 回忆版给出：

$$F={A\rightarrow B,\ BC\rightarrow D,\ E\rightarrow A}$$

求 $(CE)^+$。

计算：

$$(CE)^+ = \{C, E\}$$

由 $E\rightarrow A$，加入 $A$：

$$\{C, E, A\}$$

由 $A\rightarrow B$，加入 $B$：

$$\{C, E, A, B\}$$

由 $BC\rightarrow D$，加入 $D$：

$$\{A, B, C, D, E\}$$

所以：

$$(CE)^+ = \{A, B, C, D, E\}$$

---

7.5 候选码求法

求候选码的一般步骤：

1. 先找从未出现在任何依赖右部的属性，这些属性必须出现在每个候选码中。
2. 从这些必含属性出发求闭包。
3. 若闭包不是全集，则逐步补充属性。
4. 最后检查最小性，删除冗余属性。

判断标准：

$$X^+=U \Rightarrow X \text{ 是超键}$$

若 $X$ 的任何真子集都不是超键，则 $X$ 是候选码。

---

7.6 最小依赖集

函数依赖集 $F$ 的最小覆盖通常要求：

1. 每个依赖右部只有一个属性。
2. 每个依赖左部没有冗余属性。
3. 没有冗余的函数依赖。

求解步骤：

第一步：右部分解

把：

$$X \rightarrow A_1A_2\cdots A_n$$

分解为：

$$X \rightarrow A_1,\quad X \rightarrow A_2,\quad \dots,\quad X \rightarrow A_n$$

第二步：消除左部冗余属性

对依赖：

$$XA \rightarrow B$$

若：

$$B \subseteq X^+$$

则 $A$ 是冗余属性，可以删去。

第三步：删除冗余依赖

对某个依赖 $f$，若：

$$(F-\{f\})^+ \models f$$

则 $f$ 冗余，可以删除。

---

7.7 第一范式 (1NF)

定义：

$$R \in 1NF$$

当且仅当关系中每个属性值都是不可再分的原子值。

违反 1NF 的情况：

• 一个属性中存多个电话号码。
• 一个地址属性中包含省、市、区但没有拆分。
• 一个单元格里存一个集合或列表。

注意：

一个表如果在关系模型中能称为关系，至少应满足 1NF。

---

7.8 第二范式 (2NF)

定义：

$$R \in 2NF$$

当且仅当：

1. $R \in 1NF$；
2. 每个非主属性都完全函数依赖于每个候选键。

本质：消除非主属性对候选键的部分依赖。

典型反例：

$$SC(Sno,Cno,Sname,Cname,Score)$$

候选键：

$$(Sno,Cno)$$

函数依赖：

$$Sno \rightarrow Sname$$ $$Cno \rightarrow Cname$$ $$(Sno,Cno) \rightarrow Score$$

其中 $Sname$ 只依赖候选键的一部分 $Sno$，$Cname$ 只依赖候选键的一部分 $Cno$，因此不满足 $2NF$。

分解为：

$$Student(Sno,Sname)$$ $$Course(Cno,Cname)$$ $$SC(Sno,Cno,Score)$$

---

7.9 第三范式 (3NF)

定义：

$$R \in 3NF$$

当且仅当：

1. $R \in 2NF$；
2. 不存在非主属性对候选键的传递依赖。

本质：消除非主属性对候选键的传递依赖。

典型反例：

$$Student(Sno,Dno,Dean)$$

函数依赖：

$$Sno \rightarrow Dno$$ $$Dno \rightarrow Dean$$

于是：

$$Sno \rightarrow Dno \rightarrow Dean$$

存在传递依赖，不满足 $3NF$。

分解为：

$$Student(Sno,Dno)$$ $$Dept(Dno,Dean)$$

2024 回忆版考过“第三范式要求满足 2NF，同时消除什么依赖”，答案是传递依赖。

---

7.10 BCNF

定义：

$$R \in BCNF$$

当且仅当对 $R$ 上每个非平凡函数依赖：

$$X \rightarrow Y$$

都有：

$$X \text{ 是 } R \text{ 的超键}$$

BCNF 比 3NF 更严格。

关系：

$$BCNF \Rightarrow 3NF \Rightarrow 2NF \Rightarrow 1NF$$

但反向不成立。

注意：

• 满足 BCNF 一定满足 3NF。
• 满足 3NF 不一定满足 BCNF。
• BCNF 分解通常可以做到无损连接，但不一定保持依赖。
• 3NF 分解通常可以做到无损连接且保持依赖。

2024 选择题考过 1NF, 2NF, 3NF, BCNF 之间的判断。

---

7.11 无损连接分解

设：

$$R \rightarrow R_1,R_2$$

若：

$$R_1 \cap R_2 \rightarrow R_1$$

或：

$$R_1 \cap R_2 \rightarrow R_2$$

则二元分解是无损连接分解。

直观理解：

两个子关系的公共属性必须能决定其中一个子关系，这样自然连接时不会产生伪元组。

---

7.12 函数依赖保持

分解：

$$\rho={R_1,R_2,\dots,R_n}$$

保持函数依赖，指原来 $F$ 中的依赖可以仅通过各子关系上的依赖检查出来，而不需要先把子关系连接回原关系。

判定思路：

1. 将 $F$ 投影到各子模式 $R_i$，得到 $F_i$。
2. 考察：

$$(F_1\cup F_2\cup \cdots \cup F_n)^+$$

是否能推出原 $F$ 中所有依赖。若能，则保持依赖；否则不保持依赖。

---

八、存储管理

8.1 存储层次

数据库管理系统通常管理远大于内存的数据，因此主要数据持久存储在二级存储器中，访问时再读入内存。课件强调 DBMS 要管理超过可用内存大小的数据库，并尽量减少磁盘 I/O。

存储层次大致为：

$$\text{寄存器} \rightarrow \text{Cache} \rightarrow \text{主存} \rightarrow \text{SSD/磁盘} \rightarrow \text{磁带}$$

越靠前速度越快、容量越小、单位成本越高；越靠后速度越慢、容量越大、单位成本越低。

---

8.2 磁盘块与页

磁盘 I/O 的基本单位是块或页，不是字节。

课件中说明磁盘被划分为大小相等的磁盘块或页，典型块大小为 512 B 到 4 KB。

常考结论：

• 磁盘读写以块 / 页为单位。
• 内存是易失性存储。
• 磁盘是非易失性存储。
• 查询代价中磁盘 I/O 通常最关键。

---

8.3 元组、页和记录标识

元组本质上是字节序列，DBMS 根据系统目录中的模式信息解释这些字节。

典型元组结构：

部分	内容
元组头	长度、可见性、NULL 位图、模式指针
元组数据	各属性值
元数据	辅助解释信息

页通常由页头和数据区组成。

常见页面布局是分槽页 (Slotted Page)：

• 页头记录槽数量、空闲空间位置等。
• 槽数组记录每个元组在页中的偏移量。
• 元组数据从页尾向前增长。

记录标识常写为：

$$RID=(PageID, SlotID)$$

即页号和槽号。

---

8.4 文件组织

常见文件组织方式：

文件组织	特点
堆文件	元组无序存储，插入快，查找慢
顺序文件	按某字段有序存储，范围查询较好
散列文件	按散列函数分桶，等值查询快
聚簇文件	相关记录物理上邻近存储

堆文件常用两种管理方式：

1. 链表法：维护空闲页链表和数据页链表。
2. 页目录法：目录页记录数据页位置和空闲空间。

---

九、索引

索引是近年考试高频点，尤其是稠密 / 稀疏索引、主 / 辅助索引、聚簇 / 非聚簇索引、B+ 树和动态散列。课件明确把这些列为重点难点。

9.1 索引基本概念

索引是定义在存储表基础上的辅助存储结构，用于快速定位记录。

索引项一般由两部分组成：

$$\text{索引字段值} + \text{指针}$$

索引作用：

$$\text{用较小的索引文件快速定位较大的主文件记录}$$

索引代价：

• 需要额外存储空间。
• 插入、删除、更新时必须同步维护索引。
• 索引并非越多越好。

课件强调：索引文件是一种辅助存储结构，它的存在与否不改变存储表的物理存储结构，目的在于提高访问速度。 2024 回忆版也直接考过这一点。

---

9.2 稠密索引与稀疏索引

稠密索引

稠密索引中，主文件中每个记录或每个搜索码值都有对应索引项。

特点：

• 查找快。
• 空间开销较大。
• 更新维护代价较高。
• 若某搜索码值不在稠密索引中，则主文件中一定不存在该搜索码值。

---

稀疏索引

稀疏索引中，只为部分搜索码值建立索引项，通常每个数据块一个索引项。

特点：

• 空间开销小。
• 维护代价较低。
• 查找时需要先定位到相邻索引项，再顺序扫描。
• 主文件必须按索引字段有序存储。
• 若某搜索码值不在稀疏索引中，不代表主文件中没有该值。

---

9.3 主索引与辅助索引

主索引

主索引通常建立在有序主文件的排序码 / 主码上。

特点：

• 通常是稀疏索引。
• 一个主文件只能有一个主索引。
• 主索引与主文件物理组织密切相关。
• 主索引指针通常指向数据块。

---

辅助索引

辅助索引建立在主文件任意非排序字段上。

特点：

• 通常是稠密索引。
• 一个主文件可以有多个辅助索引。
• 不能改变主文件物理组织。
• 若索引字段值不唯一，通常需要指针桶或链表保存多个记录指针。

注意：辅助索引可以建立在主键上，但它不是主索引，因为“主索引 / 辅助索引”的区别关键不只是属性是否为主键，而是该索引是否与主文件排序 / 物理组织对应。

---

9.4 聚簇索引与非聚簇索引

聚簇索引

若索引中邻近的记录在主文件中也邻近存储，则称为聚簇索引。

特点：

• 适合范围查询。
• 物理局部性好。
• 通常一个主文件只能有一个聚簇索引。
• 主索引通常是聚簇索引。

---

非聚簇索引

若索引中邻近的记录在主文件中不一定邻近存储，则称为非聚簇索引。

特点：

• 可以有多个。
• 适合等值查询。
• 范围查询可能产生大量随机 I/O。
• 辅助索引通常是非聚簇索引。

---

9.5 B+ 树索引

B+ 树是一种动态多级索引结构。

核心特点：

• 所有数据指针都在叶子结点。
• 非叶结点只保存搜索码和子树指针。
• 叶子结点按搜索码有序。
• 叶子结点之间通常有链指针，适合范围查询。
• 树高低，查找、插入、删除代价为 $O(\log n)$。

B 树与 B+ 树的本质区别：

$$\text{B 树的非叶结点也可存放数据指针}$$ $$\text{B+ 树的数据指针只出现在叶子结点}$$

2023 回忆版填空考过 B+ 树与 B 树的区别。

---

9.6 散列索引

静态散列

桶数固定，数据增长后可能产生大量溢出桶，性能下降。

---

可扩展散列

特点：

• 使用目录 / 指针数组。
• 目录大小按 $2^d$ 增长。
• 桶分裂时目录可能翻倍。
• 多个目录项可以指向同一个桶。

考点：

可扩展散列索引的指针数组每增长一次，桶数翻倍。

---

线性散列

特点：

• 不需要一次性目录翻倍。
• 按顺序逐个分裂桶。
• 增长更平滑。

考点：

线性散列索引的指针数组每增长一次，桶数增加 1。

2024 回忆版考过可扩展散列与线性散列的增长差异。

---

十、查询处理与查询优化

查询处理和优化对应第 9、10 讲，是 2024 回忆版计算和简答的重要来源。2024 选择题和大题涉及外部排序、关系代数表达式、语法树和查询优化。

10.1 查询处理过程

查询处理基本过程：

$$SQL查询 \rightarrow 语法分析与翻译 \rightarrow 关系代数表达式 \rightarrow 查询优化 \rightarrow 查询执行计划 \rightarrow 查询执行器 \rightarrow 查询结果$$

课件把查询处理分为语法分析与翻译、优化、执行三个主要阶段。

---

10.2 查询代价

查询代价可以包括：

• 磁盘 I/O 次数。
• CPU 时间。
• 内存使用。
• 中间结果存储代价。
• 网络通信代价。

在本课程中，通常最重视：

$$\text{磁盘 I/O 次数}$$

因为磁盘访问远慢于内存操作。

---

10.3 连接算法 I/O 代价

设：

$$B_R = R \text{ 的磁盘块数}$$ $$B_S = S \text{ 的磁盘块数}$$ $$M = \text{可用内存块数}$$

忽略最终结果写回代价。

基本块嵌套循环连接

若外关系为 $R$，每次读 $R$ 的一块并扫描整个 $S$，则：

$$Cost = B_R + B_RB_S$$

若外关系为 $S$，则：

$$Cost = B_S + B_SB_R$$

---

块嵌套循环连接

用 $M-2$ 块装外关系，1 块装内关系，1 块输出。

若外关系为 $R$，则：

$$Cost = B_R + \left\lceil \frac{B_R}{M-2} \right\rceil B_S$$

若外关系为 $S$，则：

$$Cost = B_S + \left\lceil \frac{B_S}{M-2} \right\rceil B_R$$

通常选择较小关系作为外关系.

2024 题给：

$$M=3,\quad B_R=4,\quad B_S=8$$

则：

$$M-2=1$$

以 $R$ 为外关系：

$$Cost = 4+\left\lceil \frac{4}{1} \right\rceil \cdot 8 \\ = 4 + 32 = 36$$

以 $S$ 为外关系：

$$Cost = 8+\left\lceil \frac{8}{1} \right\rceil \cdot 4 \\ = 8 + 32 = 40$$

所以最小 I/O 次数为：

$$36$$

---

10.4 外部排序与多路归并

设关系 $R$ 有 $B$ 个磁盘块，内存有 $M$ 个缓冲块。

初始归并段生成

每次读入 $M$ 块排序并写回，初始段数：

$$N_0 = \left\lceil \frac{B}{M} \right\rceil$$

该阶段 I/O：

$$2B$$

归并阶段

每趟最多归并：

$$M-1$$

个段，因为需要 1 块作为输出缓冲。

若需要 $p$ 趟归并，则总 I/O：

$$2B(1+p)$$

其中 1 表示初始段生成阶段。

---

作业三典型题

给定：

$$M=4,\quad B=42$$

初始段数：

$$N_0=\left\lceil \frac{42}{4} \right\rceil = 11$$

每趟最多归并：

$$M-1=3$$

归并过程：

$$11 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

归并阶段共 3 趟，加上初始段生成共 4 趟。

若考虑最终排序结果写回，总 I/O：

$$2 \times 42 \times 4 = 336$$

---

10.5 选择大小估算

若关系 $R$ 有 $T(R)$ 个元组，属性 $A$ 有 $V(R,A)$ 个不同值，且值均匀分布，则：

$$T(\sigma_{A=a}(R)) \approx \frac{T(R)}{V(R,A)}$$

若条件为：

$$A=a \wedge B=b$$

且 $A,B$ 独立，则：

$$T(\sigma_{A=a \wedge B=b}(R)) \approx \frac{T(R)}{V(R,A)V(R,B)}$$

作业三给：

$$T(R)=15000,\quad V(R,A)=30,\quad V(R,B)=25$$

若选择条件为：

$$A=a \wedge B=b$$

则估算结果为：

$$\frac{15000}{30 \times 25}=20$$

---

10.6 逻辑查询优化

逻辑优化本质是把一个关系代数表达式转换为等价但更高效的表达式。

核心原则：

1. 尽早做选择。
2. 尽早做投影。
3. 先连接较小关系或选择性强的结果。
4. 避免过早产生笛卡尔积。
5. 把复杂条件拆分后下推。

例如：

$$\pi_{Sno, Sname} ( \sigma_{Cno='001' \wedge Student.Sno=SC.Sno} (Student \times SC) )$$

可优化为：

$$\pi_{Sno, Sname} ( Student \bowtie_{Student.Sno=SC.Sno} \sigma_{Cno='001'}(SC) )$$

进一步可提前投影：

$$\pi_{Sno, Sname} ( \pi_{Sno, Sname}(Student) \bowtie \pi_{Sno}(\sigma_{Cno='001'}(SC)) )$$

---

10.7 物化执行与流水线执行

物化执行

每个中间结果都被完整生成并存储，再作为下一步输入。

缺点：

• 中间结果写入临时文件。
• 后续操作又要读临时文件。
• I/O 开销大。
• 延迟较高。

流水线执行

一个操作的输出元组直接传递给下一个操作。

优点：

• 避免大量中间结果物化。
• 减少 I/O。
• 用户可更早获得结果。
• 现代 DBMS 广泛使用。

---

十一、事务与并发控制

并发控制是期末稳定重点。第 12 讲明确要求掌握三种不一致现象、事务调度、可串行性、冲突可串行性判别算法、两段封锁法和基于时间戳的方法。

11.1 事务

事务是 DBMS 提供的控制数据操作的基本逻辑单位。课件定义事务为一组数据库操作组成的整体，用于保证数据库状态转换的一致性。

事务示例：银行转账。

$$read(A)$$ $$A:=A-500$$ $$write(A)$$ $$read(B)$$ $$B:=B+500$$ $$write(B)$$ $$commit$$

---

11.2 ACID 特性

特性	含义
原子性 (Atomicity)	要么全做，要么全不做
一致性 (Consistency)	事务执行前后数据库满足一致性约束
隔离性 (Isolation)	并发事务互不干扰，效果等价于某种串行执行
持久性 (Durability)	已提交事务结果永久保存

---

11.3 三种典型不一致现象

丢失修改

两个事务同时读并修改同一数据，后写入的事务覆盖先写入的事务。

脏读

一个事务读取了另一个未提交事务写入的数据，而该事务后来回滚。

不可重复读

同一事务两次读取同一数据，中间被其他事务修改，导致两次读取结果不同。

课件以车票售卖和读写交错说明了丢失修改、脏读和不可重复读。

---

11.4 调度与可串行性

调度是多个事务基本操作的一种执行顺序。

设读写操作表示为：

$$r_i(X),\quad w_i(X)$$

其中 $r_i(X)$ 表示事务 $T_i$ 读 $X$，$w_i(X)$ 表示事务 $T_i$ 写 $X$。

• 串行调度：事务一个接一个执行。
• 可串行调度：并发调度的效果等价于某个串行调度。
• 冲突可串行调度：可以通过交换相邻无冲突操作变成某个串行调度。

关系：

$$\text{冲突可串行} \Rightarrow \text{可串行}$$

但：

$$\text{可串行} \not\Rightarrow \text{冲突可串行}$$

---

11.5 冲突

两个操作冲突，当且仅当同时满足：

1. 属于不同事务；
2. 操作同一数据项；
3. 至少一个是写操作。

冲突类型：

$$r_i(X),w_j(X)$$ $$w_i(X),r_j(X)$$ $$w_i(X),w_j(X)$$

不冲突：

$$r_i(X),r_j(X)$$

也不冲突：

$$r_i(X),w_j(Y),\quad X \ne Y$$

---

11.6 前驱图判定冲突可串行性

判定算法：

1. 每个事务作为一个结点。
2. 若 $T_i$ 的某操作与 $T_j$ 的某操作冲突，且 $T_i$ 的操作先出现，则画边：$T_i \rightarrow T_j$
3. 若前驱图无环，则调度冲突可串行。
4. 若前驱图有环，则不是冲突可串行。

课件明确指出：构造前驱图，如果有向图没有环，则调度是冲突可串行化的。

---

2024 典型调度

$$r_2(A); r_1(B); w_2(A); r_2(B); r_3(A); w_1(B); w_3(A); w_2(B)$$

分析：

在 $A$ 上：

$$w_2(A)$$

先于：

$$r_3(A),\quad w_3(A)$$

所以有边：

$$T_2 \rightarrow T_3$$

在 $B$ 上：

$$r_1(B)$$

先于：

$$w_2(B)$$

所以：

$$T_1 \rightarrow T_2$$

同时：

$$r_2(B)$$

先于：

$$w_1(B)$$

所以：

$$T_2 \rightarrow T_1$$

前驱图中存在环：

$$T_1 \leftrightarrow T_2$$

因此该调度不是冲突可串行调度。

2024 回忆版直接给出该调度并要求判断是否冲突可串行。

---

11.7 封锁协议

锁类型：

锁	含义
$S$ 锁	共享锁 / 读锁
$X$ 锁	排他锁 / 写锁

相容性：

	$S$	$X$
$S$	相容	不相容
$X$	不相容	不相容

---

11.8 两段锁协议 (2PL)

两段锁协议分为两个阶段：

1. 增长阶段：只加锁，不解锁。
2. 收缩阶段：只解锁，不加锁。

结论：

$$2PL \Rightarrow \text{冲突可串行性}$$

注意：

普通“使用锁”本身不一定保证冲突可串行性；严格遵守两段封锁协议才能保证冲突可串行性。

这点容易与 2024 填空“锁能否保证冲突可串行性”混淆。严谨答法应区分：普通加锁不一定；两段锁协议可以。

---

11.9 一级、二级、三级封锁协议

课件给出三种封锁协议对不一致问题的防止能力。

协议	加锁规则	能防止	不能防止
一级封锁协议	写前加 $X$ 锁，事务结束释放	丢失修改	脏读、不可重复读
二级封锁协议	一级基础上，读前加 $S$ 锁，读完释放	丢失修改、脏读	不可重复读
三级封锁协议	一级基础上，读前加 $S$ 锁，事务结束释放	丢失修改、脏读、不可重复读	—

2024 简答题问“若只需要解决丢失修改和脏读，应使用哪种封锁协议”，答案应选二级封锁协议。

---

11.10 时间戳并发控制

时间戳排序协议为每个事务分配时间戳：

$$TS(T)$$

每个数据项 $X$ 维护：

$$RTS(X)$$

表示成功读过 $X$ 的事务最大时间戳。

$$WTS(X)$$

表示成功写过 $X$ 的事务最大时间戳。

基本时间戳排序协议的目标是使调度等价于按照时间戳顺序串行执行。

严谨结论：

• 基本时间戳排序协议能保证冲突可串行性。
• 不会发生死锁，因为事务不会等待锁。
• 可能产生较多回滚。
• Thomas 写规则会忽略过时写，可能得到视图可串行但不一定冲突可串行的调度。

2024 简答中出现了 Thomas 规则相关题目，应特别区分“基本时间戳排序”和“Thomas 写规则”。

---

十二、故障恢复

故障恢复重点来自第 23 讲。课件明确要求掌握三种故障、运行日志、检查点、Undo 日志、Redo 日志、Undo/Redo 日志及其恢复操作。

12.1 故障类型

故障	含义	影响
事务故障	单个事务自身错误	影响该事务
系统故障	掉电、崩溃、宕机	影响内存和正在运行事务
介质故障	磁盘损坏	影响数据库本身

恢复手段：

故障	恢复方法
事务故障	Undo
系统故障	日志 + Undo / Redo
介质故障	备份副本 + 日志

课件总结为：三种故障是事务故障、系统故障、介质故障；三种恢复手段是撤销与重做、运行日志和备份；两个重要时刻是检查点和转储点。

---

12.2 日志

日志是只能追加的顺序文件，按发生时间记录不同事务的日志记录。课件列出日志记录包括：

$$<Start\ T>$$ $$<Commit\ T>$$ $$<Abort\ T>$$ $$<T,X,v_1> \quad \text{或} \quad <T,X,v_2> \quad \text{或} \quad <T,X,v_1,v_2>$$

其中 $v_1$ 是旧值，$v_2$ 是新值。

系统故障恢复原则：

• 故障时已提交事务：重做 (Redo)。
• 故障时未提交事务：撤销 (Undo)。

---

12.3 WAL 原则

WAL，即 Write-Ahead Logging，先写日志。

核心规则：

1. 数据页写入磁盘前，对应日志必须先写入稳定存储。
2. 事务提交前，提交日志必须先写入稳定存储。

作用：

$$\text{保证未提交事务可 Undo}$$ $$\text{保证已提交事务可 Redo}$$

---

12.4 Undo 日志

Undo 日志记录旧值：

$$<T,X,old>$$

恢复时：

• 对未提交事务按日志反序执行 Undo。
• 把数据项恢复为旧值。

Undo 日志主要保证事务原子性。

---

12.5 Redo 日志

Redo 日志记录新值：

$$<T,X,new>$$

恢复时：

• 对已提交事务按日志正序执行 Redo。
• 把数据项恢复为新值。

Redo 日志主要保证事务持久性。

---

12.6 Undo/Redo 日志

Undo/Redo 日志同时记录旧值和新值：

$$<T,X,old,new>$$

恢复策略：

• 未提交事务：Undo，写回旧值。
• 已提交事务：Redo，写回新值。

课件中明确：Undo/Redo 日志恢复时，自后向前撤销所有未提交事务，自前向后重做所有已提交事务；先撤销，再重做。

2023 回忆版也考过 Undo/Redo 结合型日志的数据结构。

---

12.7 检查点

检查点 (checkpoint) 的作用是减少系统故障恢复时需要扫描的日志范围。

检查点时，DBMS 会将缓冲区中已修改的数据页写回磁盘，并在日志中记录检查点信息。

恢复时：

• 检查点之前已经完成且写回的数据通常无需恢复。
• 检查点之后开始或结束的事务需要根据日志判断 Undo 或 Redo。

---

12.8 缓冲区处理策略

课件将缓冲区策略分为：

$$Force,\quad No\ Force,\quad Steal,\quad No\ Steal$$

并说明不同策略影响是否需要 Undo / Redo。

Force

事务提交时，必须把该事务修改的数据页写回磁盘。

优点：提交后不需要 Redo。

缺点：提交开销大，效率低。

---

No Force

事务提交时，不要求立即把修改页写回磁盘。

优点：效率高。

缺点：系统故障后需要 Redo。

---

Steal

允许未提交事务修改过的页被写回磁盘。

优点：缓冲区管理灵活。

缺点：若事务回滚或故障，需要 Undo。

---

No Steal

不允许未提交事务修改过的页写回磁盘。

优点：不需要 Undo。

缺点：缓冲区压力大。

---

常用组合

实际系统常用：

$$Steal + No\ Force$$

优点：性能高，缓冲区利用灵活。

代价：

$$\text{需要 Undo，也需要 Redo}$$