数据库期末复习

发表于 2026/07/01

作者 Metahumanz

21 分钟阅读

数据库期末复习

🧮 一、关系代数大题（4大模板）

题型： 给定自然语言查询，写出关系代数表达式。 解题步骤：

交集查询（既A又B）：
- 步骤：分别写出查 A 和查 B 的表达式（只保留主键列），中间用 $\cap$ 或 $\bowtie$ 连接。
差集查询（没有、从未）：
- 步骤：定义 全集 $\leftarrow \Pi_{id}(表)$；定义 命中集 $\leftarrow \Pi_{id}(\sigma_{条件}(表))$；计算 结果 $\leftarrow 全集 - 命中集$。
极值查询（最高、最大）：
- 步骤 1：给原表起两个别名 $T_1, T_2$。
- 步骤 2：找“小弟” $NotMax \leftarrow \Pi_{T1.id}(\sigma_{T1.val < T2.val}(T_1 \times T_2))$。
- 步骤 3：用全集减去小弟 $Result \leftarrow \Pi_{id}(表) - NotMax$。
除法查询（所有、全部）：
- 步骤 1：造全集 $All \leftarrow \Pi_{Sno}(Student) \times \Pi_{Cno}(Course)$。
- 步骤 2：找缺失 $Miss \leftarrow All - \Pi_{Sno, Cno}(SC)$。
- 步骤 3：找懒汉 $Lazy \leftarrow \Pi_{Sno}(Miss)$。
- 步骤 4：求学霸 $Result \leftarrow \Pi_{Sno}(Student) - Lazy$。

💻 二、复杂 SQL 大题（3大句型）

题型： 编写带有特定限制条件的 SQL 查询或更新。 解题步骤：

包含“所有/全部”的查询（双重 NOT EXISTS）：
- 步骤 1：写外层 SELECT * FROM A WHERE NOT EXISTS (
- 步骤 2：写中层 SELECT * FROM B(所有的目标集合) EXCEPT
- 步骤 3：写内层 SELECT * FROM C(实际发生的关系表) WHERE C.aid = A.id )。
带条件的分支更新（UPDATE + CASE WHEN）：
- 步骤：UPDATE 表 SET 列 = CASE WHEN 条件1 THEN 结果1 ELSE 结果2 END; （绝对不要写成两句连续的 UPDATE）。
递归查询（WITH RECURSIVE 求闭包）：
- 步骤 1：WITH RECURSIVE 表名(列1, 列2) AS (
- 步骤 2：写基础查询（起点数据），加 UNION。
- 步骤 3：写递归查询（用自己 JOIN 原表）。
- 步骤 4：) SELECT * FROM 表名;

🏭 三、 E-R 图转关系模式大题

题型： 将画好的 ER 图转换成建表语句或关系模式。 解题步骤（严格遵循“5大铁律”）：

强实体：直接建表，主键照抄。
1:N 联系：不建表！ 把 “1” 端的主键塞进 “N” 端的表里做外键。
M:N 联系：必须建表！ 字段 = 左主键 + 右主键 + 联系自身属性。主键 = (左主键, 右主键)。
弱实体：建表。字段 = 强实体主键 + 自身属性。主键 = (强实体主键, 自身虚线下划线属性)。关联的弱联系不建表。
多值属性：必须建表！ 字段 = 实体主键 + 多值属性。主键 = (实体主键, 多值属性)。

📐 四、范式推导与分解大题（流水线）

题型： 给定 $R$ 和 $F$，求候选码、正则覆盖、BCNF/3NF分解。 解题步骤：

找候选码：
- 将属性分为 $L, R, N, LR$ 四类。
- 必在候选码中的是 $L$ 和 $N$。求 $(L \cup N)^+$。
- 如果闭包是全集，候选码就是 $(L \cup N)$；如果不是，把 $LR$ 里的属性挨个加进去试，找出极小超键。
求正则覆盖 $F_c$：
- 第一步：右边打碎（$A \rightarrow BC$ 改为 $A \rightarrow B, A \rightarrow C$）。
- 第二步：去左边多余属性（对于 $AB \rightarrow C$，遮住A算 $B^+$，若包含C则A多余；遮住B同理）。
- 第三步：去多余依赖（假装划掉 $A \rightarrow B$，在剩下的规则里算 $A^+$，若包含 B，则彻底划掉）。
- 第四步：左部合并。
BCNF 分解（不一定保持依赖）：
- 步骤 1：找一个左边不是超键的违规依赖 $X \rightarrow Y$。
- 步骤 2：分解为 $R_1 = (X \cup Y)$，以及 $R_2 = R - (Y - X)$。
- 步骤 3：递归检查 $R_1, R_2$ 直到全满足 BCNF。
3NF 分解（无损且保持依赖）：
- 步骤 1：求出 $F_c$。
- 步骤 2：为 $F_c$ 中的每一个规则建一张表 $R_i = X \cup Y$。
- 步骤 3：如果发现有子集表（如 $R_1(A,B)$ 被 $R_2(A,B,C)$ 包含），删掉小的。
- 步骤 4：必做检查：看看现有的表里有没有哪张表包含完整的候选码？如果没有，补建一张只含候选码的表。

🌳 五、 B+ 树画图题

题型： 给定阶数 $n$，按顺序插入/删除节点，画出树的演变。 解题步骤（设定节点最多存 $n-1$ 个值，满 $n$ 个即分裂）：

插入导致分裂 (Split)：
- 叶子分裂：把 $n$ 个值排好序。前 $\lceil n/2 \rceil$ 个留左边，剩下的放右边。把右边的第一个值复制上去给父节点。
- 内部节点分裂：把 $n$ 个路由值排好序。正中间的那个值（第 $\lceil n/2 \rceil$ 个）直接顶上去给父节点，不在当前层保留。
删除导致下溢 (Underflow)（叶子低于 $\lceil (n-1)/2 \rceil$ 个值）：
- 借 (Borrow)：先看左右兄弟，谁富裕（借出一个后仍达标）就向谁借一个最靠边的值。关键动作：必须更新父节点的路由键！
- 合 (Merge)：兄弟也穷，只能合并。把残余值和兄弟拼在一起。关键动作：必须把父节点里充当三八线的路由键拉下来删掉！（这可能引起父节点的连环下溢）。

🧮 六、结果集估算大题

题型： 给定 $n_r, n_s, V(A,r), V(A,s)$，求连接或选择后的行数。 解题步骤：

选择估算 $\sigma_{A=v}(r)$：直接算 $n_r / V(A, r)$。
自然连接估算 $r \bowtie s$ (在公共属性 A 上)：
- 如果 A 是 $s$ 的主键，并在 $r$ 里是外键 $\rightarrow$ 结果行数 = $n_r$。
- 如果是普通连接 $\rightarrow$ 公式代入：$(n_r \times n_s) / \max(V(A,r), V(A,s))$。分母用两个V里的最大值。

⏱️ 七、事务并发与调度大题

题型： 给出表格形式的时间线，判断冲突可串行化与可恢复性。 解题步骤：

判断冲突可串行化：
- 步骤 1：画圈，代表事务 $T_1, T_2 \dots$
- 步骤 2：从上往下扫，寻找对同一个字母的交叉操作。
- 步骤 3：只要发现 读-写、写-读、写-写 并且不在同一个事务里，画箭头 从先操作的指向后操作的。
- 步骤 4：查环。无环 $\rightarrow$ 可串行化（写出拓扑排序）；有环 $\rightarrow$ 不是。
判断可恢复调度 (Recoverable)：
- 步骤 1：寻找“脏读”。即 $T_j$ 的 Read(A) 在 $T_i$ 的 Write(A) 之后发生。
- 步骤 2：如果有脏读，检查 $T_i$ 的 Commit 是否在 $T_j$ 的 Commit 之上（之前）。如果满足，则可恢复；如果不满足（或 $T_j$ 提了 $T_i$ 没提），直接判不可恢复。
判断无级联 (Cascadeless)：
- 步骤 1：同样寻找 $T_j$ Read(A) 跟着 $T_i$ Write(A)。
- 步骤 2：检查 $T_i$ 的 Commit 是不是在 $T_j$ 的 Read(A) 之上（之前）！必须先提交，才能被读。满足则无级联。

💡 八、小散计算题（防守套路）

关联规则：Support(A$\rightarrow$B) = (买A又买B的数量 / 总单数)；Confidence(A$\rightarrow$B) = (买A又买B的数量 / 买A的数量)。
磁盘访问时间：平均寻道时间 + 平均旋转延迟 ($0.5 \times \frac{60}{RPM}$) + $\frac{\text{Block Size}}{\text{Transfer Rate}}$。

答题套路、核心公式和防坑指南

🗄️ 模块一：SQL 与关系代数 (Ch2-5)

【题型速览】：给定表结构，写出纯关系代数式和复杂 SQL。

1. 关系代数 4 大必考套路

交集（既…又…）：$\Pi_{id}(\sigma_A(R)) \cap \Pi_{id}(\sigma_B(R))$ 或用自然连接 $\bowtie$。
差集（没有、从未）：$\Pi_{id}(全集) - \Pi_{id}(\sigma_{选中}(R))$。
极值（最高、最大）：找小弟！$T1 \times T2$，条件 $T1 < T2$，用全集减去所有 T1（小弟），剩下的就是最大值。
除法（所有、全部）：全集组合 $(Sno \times Cno)$ 减去实际组合 $(SC)$ = 漏选组合；全集学生减去漏选学生 = 选了所有的学生。

2. SQL 核心关键字与题型对应

分组统计带条件 $\rightarrow$ GROUP BY ... HAVING
- 铁律：SELECT 里的非聚合字段，必须原封不动抄进 GROUP BY 里！
保留空缺记录（如：没选课的学生） $\rightarrow$ LEFT OUTER JOIN ... ON
- 铁律：想找“没有关联”的数据，用左外连接后加 WHERE 右表.id IS NULL。
条件分支更新（如：按不同薪水涨工资） $\rightarrow$ UPDATE ... SET ... CASE WHEN
- 铁律：绝对不能写两条 UPDATE，会重复涨薪 (Halloween Problem)！
包含“所有/全部”的查询 $\rightarrow$ 双重 NOT EXISTS
- 句型：WHERE NOT EXISTS ( SELECT 目标全集 EXCEPT SELECT 该实体实际包含的集合 )。
树状/图状层级查询（如：先修课的先修课） $\rightarrow$ WITH RECURSIVE
- 句型：WITH RECURSIVE 视图名 AS ( 基础起点 SELECT UNION 递归自连接 SELECT )。

📐 模块二：E-R 图与建表铁律 (Ch6)

【题型速览】：根据文字画 ER 图，并转为关系模式（表）。

1. 画图符号防抽查

双矩形 = 弱实体；双菱形 = 弱实体的识别联系；双实线 = 全部参与 (Total)。
虚下划线 = 弱实体分辨符；双椭圆 = 多值属性；虚线椭圆 = 派生属性。
箭头 ($\rightarrow$) = 1；直线 (—) = 多 (N)。

2. ER 转表“5大生死线”

1:N 联系：绝对不建新表！ 把 “1” 端的主键塞进 “N” 端当外键。
M:N 联系：必须建新表！ 主键是 (左主键, 右主键)。
弱实体：建表！ 包含强实体主键。主键是 (强实体主键, 自身虚线分辨符)。
多值属性：必须建新表！ 主键是 (原实体主键, 该多值属性)。
外键约束：只要用到了别人的主键，写 SQL 时必须加 FOREIGN KEY ... ON DELETE CASCADE。

🧩 模块三：正则覆盖与范式推导 (Ch7)

【题型速览】：给 $R$ 和 $F$，求候选码、$F_c$、判断并分解 BCNF 或 3NF。

1. 求候选码快速法则

L（只在左边出现）：必在候选码中。
R（只在右边出现）：绝对不在候选码中。
N（没出现）：必在候选码中。
先把 L 和 N 拿出来求闭包，如果是全集，它就是唯一候选码。

2. 求正则覆盖 $F_c$（4步走，不漏分）

右边打碎：$A \rightarrow BC$ 拆成 $A \rightarrow B$ 和 $A \rightarrow C$。
去左边多余属性：对于 $AB \rightarrow C$，遮住 A，在当前所有规则下算 $B^+$，若包含 C，则 A 是废话，删掉 A。
去多余规则：假装划掉 $A \rightarrow B$，在剩下的规则里算 $A^+$，若包含 B，则彻底删掉此规则。
左边合并：同左部的重新合起来。

3. 范式分解套路

BCNF 分裂法（无损，但不一定保持依赖）：
- 找违规依赖 $X \rightarrow Y$（$X$ 不是超键）。
- 一刀劈成两张表：$R_1 = (X \cup Y)$， $R_2 = (R - (Y - X))$。
3NF 积木法（无损，且一定保持依赖）：
- 先求 $F_c$。对 $F_c$ 里每个规则建一张表。
- 删掉被其他表完全包含的小表。
- 【关键一步】检查现有的所有表，有没有一张表包含了原表的候选码？没有的话，补建一张只含候选码的表！

🌲 模块四：B+ 树与底层物理 (Ch12-14)

【题型速览】：画 B+ 树的插入/删除，算 RAID I/O 次数。

1. B+ 树操作法则 (设阶数为 $n$)

容量限制：叶子最多 $n-1$ 个值，最少 $\lceil (n-1)/2 \rceil$ 个值。满了就分裂，少了就借/合。
插入满 $\rightarrow$ 分裂 (Split)：
- 叶子分裂：前 $\lceil n/2 \rceil$ 留左边，剩下的去右边。把右边的第一个值“复制”上去（Copy up）。
- 内部节点分裂：正中间的值“踢”上去（Push up），本层不再保留！
删除少 $\rightarrow$ 借/合 (Underflow)：
- 借 (Borrow)：向富裕的兄弟借，必须更新父节点的三八线（路由Key）！
- 合 (Merge)：跟穷兄弟合并，必须把父节点的三八线扯下来删掉！（可能导致父节点也下溢）。

2. 磁盘与缓冲池 (Buffer) 必考定论

嵌套循环 JOIN 为什么不用 LRU？ 因为内表每次刚扫完，最前面的块就被踢了，下一轮循环命中率为0。最佳策略是 MRU。
列存 (Column-Oriented) 的优缺点：优点是极高压缩率、分析查单列 I/O 极小；缺点是元组重组 (Tuple reconstruction) 极慢，不适合 OLTP 频繁插入。

3. RAID 系列定论

RAID 1（镜像）：写 1 个逻辑块 = 2 次 I/O。适合小文件高频随机写。
RAID 5（奇偶校验）：写 1 个逻辑块 = 4 次 I/O（读老数据、读老校验、写新数据、写新校验）。写惩罚极大！

📊 模块五：查询代价与事务调度 (Ch15-17)

【题型速览】：算 JOIN 后的大小，画优先图判断可串行化。

1. 代价与大小估算公式

I/O 代价基本公式：$\text{Cost} = b \times t_T + S \times t_S$ （块数 $\times$ 传输时间 + 寻道次数 $\times$ 寻道时间）。
自然连接大小估算 ($r \bowtie s$)：
- 如果是外键 $\rightarrow$ 大小 = 子表的行数。
- 如果是普通连接 $\rightarrow$ 大小 = $\frac{n_r \times n_s}{\max(V(A,r), V(A,s))}$ （拿两者里面 Distinct Value 最大的作分母）。

2. 事务并发调度 (Schedule) 分析

画优先图 (找冲突)：寻找同一变量的读-写 / 写-读 / 写-写操作（不在同一事务里）。箭头从先操作的指向后操作的。
可串行化：图无环就是冲突可串行化。拓扑排序即为串行化顺序。
可恢复性 (Recoverability)：只要 $T_2$ 读取了 $T_1$ 还没提交的数据（脏读），那么 $T_1$ 必须在 $T_2$ 之前 Commit，否则不可恢复。
无级联 (Cascadeless)：绝对不允许脏读。$T_2$ 只能读 $T_1$ 已经 Commit 之后的数据。

🧩 模块六：零散白给公式 (Ch8-11)

TF-IDF 文本匹配：$TF = \log(1 + \frac{\text{词频}}{\text{文档总词数}})$， $IDF = \frac{1}{\text{含该词文档数}}$。
Gini 指数 (决策树纯度)：$Gini = 1 - \sum p_i^2$。越小越纯。
关联规则 (A $\rightarrow$ B)：
- 支持度 Support = $\frac{\text{AB都有的订单}}{\text{总订单}}$
- 置信度 Confidence = $\frac{\text{AB都有的订单}}{\text{只有A的订单}}$
OLAP 聚合：CUBE(A,B,C) 产生 $2^3=8$ 种组合；ROLLUP(A,B,C) 产生 $4$ 种递减组合。

发卷子先看 B+ 树的度数 $n$ 是几！
遇到 NATURAL JOIN 脑子里敲响警钟。
ER图转表，看到 1:N 绝不建表。
正则覆盖删完属性后，闭包要在新集合里算。

学习, 数据库原理与应用

本文由作者按照 CC BY 4.0 进行授权

🧮 一、 关系代数大题（4大模板）

💻 二、 复杂 SQL 大题（3大句型）