第2章：关系代数

---

元数据卡

维度	值
难度	（进阶入门）
前置	第1章 SQL 基础、集合论基本概念（并交差）
关键词	关系代数、选择 σ、投影 π、连接 ⋈、除运算 ÷、关系演算、查询优化
代码语言	SQL / 关系代数表达式

---

你的进度

你跟着老陈走进了他的书房。推开厚重的木门，扑面而来的是满墙的挂图——不是山水画，不是书法，而是一张张布满古怪符号的数学地图。

"别急着坐。"老陈指了指墙上那些挂着希腊字母的图表，"你知道我让小刘管仓库的时候，他第一周干了什么吗？他把自己关在房间里画了三天符号。"

你看了一眼最近的一张图。σ、π、∪、⋈、ρ——每一个符号旁边都画着简单的箭头和表格。

"你要管好一个仓库，光会开口喊'把货找出来'是不够的。你得知道管理员是怎么干的——他先走哪条通道，先翻哪个货架，遇到交叉口往哪拐。"老陈拍了拍你的肩膀，"这些符号，就是管理员干活的路线图。"

关系代数不是什么高深数学。它是 SQL 背后那套"管理员怎么做"的骨架。不懂它，你也能用 SQL——但懂了它，你能知道数据库到底在干什么，而且干得对不对。

等你坐回电脑前再写 SELECT 的时候，你会知道数据库优化器到底在你的 SQL 背后做了什么。

你的任务

理解关系代数中的六个基本运算和三个扩展运算。看懂 SQL 和关系代数表达式之间的映射关系。明白为什么关系代数定律可以让同一个查询产生不同的执行计划——并且结果完全相同。

你不是来学数学符号的。你是来理解 SQL 的执行逻辑的——关系代数就是那个执行逻辑的数学表示。

---

破局 · 溯源

为什么需要关系代数？

设想一个场景。你要查"战士等级高于 30 的冒险者姓名和职业"：

SELECT name class FROM adventurers
WHERE class = '战士' AND level > 30;

如果用一个直白的步骤描述，你可能会说：

1. 从 adventurers 表里，挑出 class = '战士' 的行
2. 从这些行里，再挑出 level > 30 的行
3. 从最终剩下的行里，只取 name 和 class 这两列

这段描述就是关系代数的雏形。如果我们用符号把它记下来，就变成：

π_name class( σ_class='战士' ∧ level>30( adventurers ))

这是同一个查询的数学表达式。和 SQL 不同的是，这个表达式没有歧义——它精确地描述了每步操作是什么、按什么顺序执行。

关系代数不是什么新发现——E. F. Codd 在 1970 年提出关系模型时就一并定义了它。那一年 SQL 还没出生。关系代数是关系模型的标准操作语言，SQL 则是它的一种友好用户界面。

关系代数和 SQL 的关系，就像算术和小学数学应用题的关系。 应用题说"小明有 5 个苹果，小红有 3 个，他们一共有几个？"——你脑子里的算式是 5 + 3 = 8。SQL 是应用题，关系代数是算式。

六大基本运算

关系代数只有六个基本运算是"底层的"——其他所有运算都可以由它们组合出来。老陈指了指墙上的符号：

"记住这六个，剩下的见了面你就能认。"

运算	符号	描述	SQL 类比
选择	σ (sigma)	按条件筛选行	WHERE
投影	π (pi)	选取列	SELECT 列名
并	∪	合并两个关系	UNION
差	−	一个关系减另一个	EXCEPT
笛卡尔积	×	所有行两两组合	CROSS JOIN
重命名	ρ (rho)	给属性或关系改名	AS 别名

逐个来看。

σ (选择)：按条件筛选行

选择运算 σₚ(R) 从关系 R 中选出满足条件 p 的所有行。

看一个例子。adventurers 表：

adventurer_id	name	class	level
1	赤焰	战士	28
2	寒冰	法师	35
3	铁壁	战士	42
4	翠风	法师	25
5	雷霆	战士	50

σ_class='战士'(adventurers)

结果：

adventurer_id	name	class	level
1	赤焰	战士	28
3	铁壁	战士	42
5	雷霆	战士	50

条件可以复合——用逻辑与 (∧)、逻辑或 (∨)、逻辑非 (¬)：

σ_class='战士' ∧ level>30(adventurers)

结果只剩铁壁和雷霆。

对应的 SQL：

SELECT * FROM adventurers
WHERE class = '战士' AND level > 30;

选择运算是行级别的过滤。它不改变列的个数，只减少行的个数。

条件中的比较符支持 = ≠ < ≤ > ≥，和 SQL 一样。

π (投影)：按列筛选

"这个 π 是投影。"老陈的手指移到下一个符号。"行选完了，但你只关心其中几列。π 帮你把不需要的列丢掉。"

π_{A₁ A₂ ... Aₙ}(R) 从关系 R 中只保留指定的列，去掉其他列。

π_name level(adventurers)

结果：

name	level
赤焰	28
寒冰	35
铁壁	42
翠风	25
雷霆	50

这里有一个微妙但重要的行为：投影自动去重。因为关系代数里"关系"是集合（不是包/multiset），所以重复行不存在。

对应的 SQL 是 SELECT DISTINCT：

SELECT DISTINCT name level FROM adventurers;

但通常的 SELECT name level FROM adventurers 在 SQL 里不去重，因为 SQL 的表是"包"语义。这是 SQL 和纯关系代数的一个差异点。

π_class(adventurers)

结果：

class
战士
法师

如果 adventurers 表有 100 行数据都是战士，投影后只有一行——因为重复被去掉了。

选 σ 和射 π 的区别：σ 删行，π 删列。

这是查询中最常用的两个运算，几乎所有查询的第一步都是"先 σ 再 π"或者"先 π 再 σ"。

× (笛卡尔积)：所有行两两组合

"× 是笛卡尔积。"老陈画了个叉。"你把两个货架的所有物品两两配对——不管它俩有没有关系。"

R × S 把 R 的每一行和 S 的每一行配对。

adventurers 表有 5 行，guilds 表（取个简化版）有 2 行：

guild_id	name	territory
1	战士	铁壁区
2	法师	秘法区

adventurers × guilds

结果有 5 × 2 = 10 行。其中两行是这样的：

a.adventurer_id	a.name	a.class	a.level	g.guild_id	g.name	g.territory
1	赤焰	战士	28	1	狮鹫团	铁壁区
1	赤焰	战士	28	2	霜狼部	秘法区
2	寒冰	法师	35	1	狮鹫团	铁壁区
2	寒冰	法师	35	2	霜狼部	秘法区
...

全排列——"狮鹫团的赤焰"和"狮鹫团"、"霜狼部"都配对了。这不是你想要的（你想让赤焰只和狮鹫团配对），但它是一个基础运算。

对应的 SQL：

SELECT * FROM adventurers CROSS JOIN guilds;
-- 或者
SELECT * FROM adventurers guilds;

没有 WHERE 条件的 JOIN 就是笛卡尔积。生产环境中几乎不会直接用笛卡尔积——但它是一切连接运算的起点。

ρ (重命名)：改名

"ρ 是重命名。"老陈拿起笔在图纸上写下这个符号。"同一个表要跟自己比的时候你得给它换个名字，不然分不清谁是谁。"

ρ_{新名←原名}(R) 给关系或属性起别名。

ρ_a(adventurers) -- 把 adventurers 改名为 e
ρ_{adv_name←name}(adventurers) -- 把 name 列改名为 emp_name

对应的 SQL：

SELECT name AS adv_name FROM adventurers a;

重命名在自连接时特别有用。如果你要查"和冒险者赤焰在同一个公会的所有冒险者"：

SELECT a2.name
FROM adventurers a1
JOIN adventurers a2 ON a1.guild = a2.guild
WHERE a1.name = '赤焰';

在关系代数里你需要重命名才能区分两个 roles：

π_a2.name( σ_a1.name='赤焰' ∧ a1.guild=a2.guild( ρ_a1(adventurers) × ρ_a2(adventurers) ))

∪ (并) 与 − (差)：集合运算

"∪ 和 − 是你认识的老朋友——集合的并与差。"老陈笑着说。"只不过现在操作对象不是数字，是关系。"

并运算 R ∪ S 合并两个关系——前提是它们有相同的属性集合（即"并兼容"）。

π_class(adventurers) ∪ π_name(guilds)

这在 SQL 里就是：

SELECT class AS guild_or_class FROM adventurers
UNION
SELECT name AS guild_or_class FROM guilds;

差运算 R − S 返回在 R 中但不在 S 中的行。

π_class(adventurers) − π_name(guilds)

如果 guilds 表里有"战士"和"法师"，但 adventurers 里还有"斥候"（如果你插入了这样的数据），那么结果就是"斥候"。

这在 SQL 里是：

SELECT class AS class_only FROM adventurers
EXCEPT
SELECT name AS guild_name FROM guilds;

基本运算就这六个。现在你来组合它们——所有你能想到的 SQL 查询，都可以用这六个运算搭出来。

三大派生运算

"六个基本运算搭好了，剩下的是组合工具。"老陈在纸上画了几条连线。"连接、交、除——这三样能省你不少事。"

⋈ (连接)：关系代数的 JOIN

"连接就是你天天写的 JOIN。"老陈指着两张图的交叉部分。"它本质上就是笛卡尔积加了一个选择条件——先全配对，再挑对的。"

最常见的是自然连接和条件连接。

条件连接 θ-join（读作 theta-join，θ 是条件占位符）：

R ⋈_θ S = σ_θ(R × S)

条件连接就是先做笛卡尔积，再按条件筛选。

adventurers ⋈_{adventurers.guild = guilds.name} guilds

等价于：

σ_{adventurers.guild = guilds.name}(adventurers × guilds)

对应的 SQL：

SELECT * FROM adventurers
JOIN guilds ON adventurers.guild = guilds.name;

自然连接 Natural Join: 自动按同名属性连接，并去重重复列。

假设 adventurers 和 guilds 都有同名属性 guild_code：

adventurers ⋈ guilds

自然连接自动按所有同名属性做等值连接，结果里只保留一列 guild_code。

对应的 SQL：

SELECT * FROM adventurers NATURAL JOIN guilds;

自然连接是理论上的优雅工具，但实际生产 SQL 几乎不用它。原因：表结构一变，同名属性可能不该连接了——隐式依赖让代码容易出错。生产代码永远写显式的 ON 条件。

∩ (交)：共同行

交运算 R ∩ S 返回在两个关系中的行——等于 R − (R − S)：

π_class(adventurers) ∩ π_name(guilds)

SQL 里是 INTERSECT：

SELECT class AS common FROM adventurers
INTERSECT
SELECT name AS common FROM guilds;

÷ (除运算)：查"全部"

除运算是关系代数中最抽象但也最强大的运算之一。它解决的问题是：找出包含了所有某种东西的对象。

典型问题：找出集齐了全部圣物的冒险者。

先看两个关系：

成就记录 achievements：

adventurer	relic
赤焰	龙鳞护符
赤焰	影遁披风
赤焰	魔力晶石
寒冰	龙鳞护符
寒冰	影遁披风
疾风	龙鳞护符

全部圣物 relics：

relic
龙鳞护符
影遁披风
魔力晶石

除运算 achievements ÷ relics 的结果：哪些冒险者集齐了 relics 里的全部圣物？

答案是"赤焰"——因为他集齐了龙鳞护符、影遁披风、魔力晶石全部三件圣物。寒冰缺了魔力晶石，疾风只拿到龙鳞护符。

achievements ÷ relics

结果：

adventurer
赤焰

除运算的定义：

R(XY) ÷ S(Y) = { x ∈ π_X(R) | 对于每一个 y ∈ π_Y(S)，有 (xy) ∈ R }

用基本运算表达是：

achievements ÷ relics = π_X(T) − π_X( (π_X(T) × π_Y(S)) − T )

这行表达式值得停下来看一下。它说的是：

1. 拿全部冒险者的名单 × 全部圣物的列表 —— 得到"理想全选矩阵"
2. 减去"实际成就记录"T —— 剩下的是"哪些冒险者缺了哪些圣物"
3. 投影出冒险者名 —— 得到"缺过圣物的冒险者"
4. 从全部冒险者里减去这些"缺圣物者" —— 剩下的就是"全收集者"

它在 SQL 里的实现通常用两层 NOT EXISTS 嵌套：

SELECT adventurer FROM achievements A1
WHERE NOT EXISTS (
 SELECT relic FROM relics
 EXCEPT
 SELECT relic FROM achievements A2
 WHERE A2.adventurer = A1.adventurer
);

除运算很抽象，但一旦你遇到过"查出做了所有 X 的 Y"这类问题，你就知道它的价值。面试题里常有人抱怨"这道 SQL 怎么写"——它在关系代数里就是一行 ÷。

---

深入冒险

从 SQL 到关系代数：转换练习

光看符号不够。动手翻译几条 SQL，比看十遍理论管用。

例 1：简单过滤

SELECT name FROM adventurers WHERE level > 30;

π_name( σ_level>30(adventurers) )

例 2：两表 JOIN

SELECT a.name g.territory
FROM adventurers a
JOIN guilds g ON a.guild = g.name
WHERE g.territory = '铁壁区';

π_a.name g.territory( σ_g.territory='铁壁区'( ρ_a(adventurers) ⋈_{a.guild=g.name} ρ_g(guilds) ))

或者先做 JOIN 再过滤——顺序不同，结果相同：

π_a.name g.territory( ρ_a(adventurers) ⋈_{a.guild=g.name} σ_territory='铁壁区'( ρ_g(guilds) ))

σ_location='铁壁区' 被提前到了 guilds 刚出现的时候就执行。这两种表达式是等价的——但性能可能天差地别。

这就是查询优化的核心：同一个 SQL 可以翻译成多个等价的关系代数表达式，数据库选一个最快的去执行。

例 3：嵌套查询

SELECT name FROM adventurers
WHERE level > (SELECT AVG(level) FROM adventurers);

这就有趣了。标量子查询的出现让关系代数变得复杂，因为 AVG 是聚合运算。我们需要引入扩展关系代数中的聚合运算：

π_name( σ_level > ρ_avg(𝒢_AVG(level)(adventurers)) (adventurers) )

这里的 𝒢 是分组聚合运算，ρ_avg 把聚合结果当作一个值供比较。

在实际的优化器里，标量子查询会被展开成 JOIN 或者窗口函数——但数学本质是一样的。

例 4：多表 JOIN 的优化问题

SELECT a.name q.start_date i.name
FROM adventurers a
JOIN quests q ON a.adventurer_id = q.adventurer_id
JOIN vault_items i ON q.item_id = i.item_id
WHERE a.class = '战士';

关系代数表达式可以写成：

π_name start_date name(
 (σ_class='战士'(adventurers))
 ⋈_{a.adventurer_id=q.adventurer_id}
 quests
 ⋈_{q.item_id=i.item_id}
 vault_items
)

也可以写成：

π_name start_date name(
 σ_class='战士'(
 adventurers ⋈ quests ⋈ vault_items
 )
)

先过滤再 JOIN（第一种）通常更快——因为 adventurers 变小了，后续的笛卡尔积中间结果更小。

这里出现的就是选择下推：把 σ 尽可能往表达式树的下方（即尽早执行）移。这是优化器最常用、最有效的变换规则之一。

关系代数定律与查询优化

"所以关系代数有什么用？"老陈从抽屉里抽出一张发黄的纸。"因为它有代数定律。你可以在不改变结果的前提下，把同一个表达式换成不同的写法——哪个快用哪个。"

最重要的几条定律：

选择下推：

σ_C(R ⋈ S) ≡ σ_C(R) ⋈ S -- 如果 C 只涉及 R 的属性
σ_C(R ⋈ S) ≡ σ_C(R) ⋈ σ_C(S) -- 如果 C 涉及 R 和 S 的属性

选择运算对交换律：

σ_C₁(σ_C₂(R)) ≡ σ_C₂(σ_C₁(R)) ≡ σ_C₁∧C₂(R)

投影与连接的结合：

π_{A}(R ⋈_θ S) ≡ π_{A}(π_{A_R}(R) ⋈_θ π_{A_S}(S))
-- 其中 A_R = A 中属于 R 的属性 + 连接条件所需的属性
-- 其中 A_S = A 中属于 S 的属性 + 连接条件所需的属性

连接的结合律与交换律：

R ⋈ S ≡ S ⋈ R
(R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T)

这几条定律看起来简单，但它们是查询优化的全部数学基础。优化器实际做的事情就是：

1. 把你的 SQL 翻译成关系代数表达式树
2. 应用代数定律，生成多个等价的候选表达式
3. 估算每个候选表达式的执行代价
4. 选择代价最小的那个

你现在理解为什么 SQL 查询可以优化了——因为代数定律可以让表达式等价变换。

关系演算：另一种视角

"代数说怎么拿，演算说要什么。"老陈伸出两只手比了比。"这是两种思维方式。"

关系代数是过程式的——你说怎么拿数据（先 σ 再 π 再 ⋈）。

关系演算是声明式的——你说要什么数据，系统自己想办法。

关系演算分两种：

元组关系演算（Tuple Relational Calculus TRC）：

{ t.name | Adventurer(t) ∧ t.level > 30 ∧ t.class = '战士' }

读作：找到所有满足 Adventurer 关系、等级大于 30、属于战士的元组 t，取它们的 name。

域关系演算（Domain Relational Calculus DRC）：

{ ⟨n⟩ | ∃id c l g ( Adventurer(id n c l g) ∧ l > 30 ∧ c = '战士' ) }

按列（域）来写查询——更接近逻辑表达式的风格。

SQL 的设计灵感主要来自关系演算——它的"你说要什么"的风格直接源自演算的声明式本性。而数据库内部则用关系代数来执行——因为代数表达式是可操作的。

E. F. Codd 证明了关系代数与关系演算在表达能力上是等价的。这意味着任何可以用关系代数写的查询，也一定可以用关系演算写出——反之亦然。这就是Codd 定理。

面试常见问题：关系代数和关系演算的区别？一句话：代数=怎样做，演算=做什么。SQL 是演算写法的，数据库用代数来跑。

---

常见陷阱

陷阱 1：把 SQL 当作关系代数去理解

"你写 SQL 和画代数符号，用的是两套规则。"老陈敲了敲桌面。

SQL 的表是"包"（允许重复行），关系代数的关系是"集合"（无重复）。所以 π_name(adventurers) 会自动去重，但 SELECT name FROM adventurers 不去重。这是 SQL 设计中最大的不一致之一。

写 SQL 用 SQL 的语义，做优化分析时切换回关系代数语义。别用一套思维打全场。

陷阱 2：笛卡尔积后忘记条件

SELECT * FROM adventurers guilds; -- 忘记 WHERE 条件 = 10行

在生产代码里，忘记连接条件会导致笛卡尔积——瞬间把 1 万行变成 1 亿行，数据库直接卡死。这是新手最容易犯的灾难性错误。

陷阱 3：除运算的 SQL 翻译误区

不要把 ÷ 翻译成 NOT IN。上面已经看到了，除运算的等价 SQL 需要双重 NOT EXISTS 或者集合差运算。

-- 错误的除运算实现
SELECT adventurer FROM achievements
WHERE relic IN (SELECT relic FROM relics);
-- 这只会返回选了"某一件"圣物的冒险者，而不是"全部"

-- 正确的除运算实现
SELECT adventurer FROM achievements A1
WHERE NOT EXISTS (
 SELECT relic FROM relics
 EXCEPT
 SELECT relic FROM achievements A2
 WHERE A2.adventurer = A1.adventurer
);

陷阱 4：自然连接的隐式依赖

SELECT * FROM adventurers NATURAL JOIN guilds;

如果两个表意外出现了同名属性（比如都有 modified_at），自然连接会用它作为连接条件——结果可能完全错误。这也是为什么 PostgreSQL 的 NATURAL JOIN 被很多团队禁用。显式写 JOIN ... ON，永远。

---

通关挑战

** 热身（10 分钟）**

给定关系：recruits(rid name age specialty) 和 enrollments(rid cid grade)

1. 用关系代数写出：找出年龄大于 20 的符文系学徒姓名
2. 用关系代数写出：找出所有选修了试炼编号为 R101 的学徒姓名
3. 将以下 SQL 转成关系代数：

SELECT r.name
FROM recruits r
JOIN enrollments e ON r.rid = e.rid
WHERE e.grade = 'A';

参考解答

1. π_name( σ_age>20 ∧ specialty='符文系'(recruits) )
2. π_name( recruits ⋈_{recruits.rid=enrollments.rid} σ_cid='R101'(enrollments) )
3. π_r.name( σ_e.grade='A'( ρ_r(recruits) ⋈_{r.rid=e.rid} ρ_e(enrollments) ))

注意第三个：先连接、再过滤、再投影。你也可以先过滤再连接——结果等价，但性能不同。

** 挑战（30 分钟）**

使用以下关系模式来完成除运算练习：

trials(tid name difficulty) mentors(mid name specialty) assignments(mid tid season)

问题：找出在所有季节都带过试炼的导师。

提示：先思考"所有学期"是指什么——是所有出现在 assignments 表里的不同 season 值。

提示

1. 先投影出所有不同的 season：π_season(assignments)
2. 然后用除运算 assignments(mid season) ÷ π_season(assignments)

注意 assignments 表包含 mid、tid、season——要除，你需要先投影出 mid 和 season：

(π_mid season(assignments)) ÷ (π_season(assignments))

** 观察（15 分钟）**

打开 SQLite 或 PostgreSQL，运行以下查询并查看执行计划：

-- SQLite
EXPLAIN QUERY PLAN
SELECT a.name g.territory
FROM adventurers a
JOIN guilds g ON a.guild = g.name
WHERE a.level > 30;

-- 再看这个
EXPLAIN QUERY PLAN
SELECT a.name g.territory
FROM (SELECT * FROM adventurers WHERE level > 30) a
JOIN guilds g ON a.guild = g.name;

两个查询执行计划是否相同？优化器是否自动做了"选择下推"？如果不同，为什么？

---

验收标准

到这一步你应该能：

• 把简单的 SQL 查询手动转为关系代数表达式
• 解释 σ、π、×、⋈、÷ 五个核心运算符各自做什么
• 说出为什么关系代数支持查询优化（代数定律允许等价变换）
• 用双重 NOT EXISTS 或集合差实现除运算
• 区分关系代数（过程式）和关系演算（声明式）

---

常见卡点

卡点	原因	解决
"σ 和 π 分不清"	都是"筛选"，一个删行一个删列	σ 筛行（水平切片），π 筛列（垂直切片）
"÷ 看不懂"	除运算太抽象	用具体例子走一遍公式。全部冒险者 × 全部圣物 − 实际成就 = 缺圣物者，再反转
"关系代数表达式太长"	不用重命名时属性冲突	ρ(重命名) 是工具——自连接和跨表条件必须用到
"关系代数查不出我要的"	SQL 有聚合、排序、LIMIT	关系代数基本运算不包括聚合——需要扩展关系代数（加了 𝒢、排序 τ 等）
"不理解为什么能优化"	以为 SQL 是按写顺序执行的	SQL 是声明式；优化器把 SQL 变成代数表达式，再用交换律、选择下推等定律重写成不同形式

---

现在不需要理解

• 扩展关系代数中的聚合运算 𝒢：它引入了分组和聚合，但基本关系代数不支持——SQL 里的 GROUP BY 需要扩展
• 外连接：LEFT/RIGHT/FULL JOIN 不能用基本关系代数表达，需要扩展。它在 SQL 层面是直观的，但到代数层面会有 NULL 标记的问题
• 查询代价估算：关系代数给出等价变换，但"哪个更快"需要统计信息（基数、选择率、数据分布）——那是第 8 章优化器的事
• 关系代数与 SQL 的三值逻辑：SQL 的 NULL 使得 WHERE 条件有 TRUE/FALSE/UNKNOWN 三种结果，但关系代数默认是二值逻辑

---

旅人笔记

"你现在懂了。"老陈拍了拍图纸。"σ 是你的 WHERE，π 是你的 SELECT 列，⋈ 是你的 JOIN，÷ 是你的「有没有全部」——你写的每一条 SELECT，优化器都先翻译成这些符号，再用代数定律找到最快的那条路。"

→ 下一站预告