

跟着论文学习数据库11：关系代数

程序猿读历史

2025-09-03

往前回顾

1970年，埃德加·科德（Edgar F. Codd）发表了一篇划时代的论文《A Relational Model of Data for Large Shared Data Banks》，文中首次系统性地提出了数据库关系理论，它以数学集合论为基础，用数学代数模型统一数据逻辑，将数据库中的关系（二维表）定义为集合，数据操作通过关系代数运算实现。2年后后，他又在《Relational Completeness of Database Sublanguages》一文中，进一步论证了关系代数与关系演算的等价性。可以说，是这两篇论文为现代数据库的五十年蓬勃发展打下了坚实的数学根基。

本文将以上述两篇经典论文为依据，深入浅出地解析关系模型、关系代数的知识点，介绍关系代数如何将复杂的数据库查询转化为一系列精确的数学运算。

01 早期模型的问题

在关系模型提出之前，当时数据库流行的是层次和网络模型。科德《A Relational Model 》文中，总结了这类数据模型的排序、索引、访问路径三种问题，被统称为数据依赖 “Data Dependencies”。

排序依赖（Ordering Dependence）

排序依赖指应用程序逻辑与数据物理存储顺序的强绑定。在早期的数据库系统中，数据若按特定字段排序存储，程序会默认依赖该顺序输出结果。当存储结构因优化调整时，未显式声明排序逻辑的程序可能产生错误。这限制了数据的物理独立性，迫使应用层感知存储细节。

索引依赖（Indexing Dependence）

索引依赖指程序直接调用特定索引结构而非通过逻辑描述访问数据。文章举例在IDS系统中，程序需显式引用索引链名称，一旦索引被删除，程序将失效。这种设计将性能优化机制暴露给用户层，使程序与物理优化机制强耦合，破坏数据抽象的完整性。

访问路径依赖（Access Path Dependence）

在层次/网络模型中，程序必须按预设路径（如父-子指针链）导航数据。科德证明，同一查询在不同结构下需不同实现，且路径组合数随关系维度指数增长，严重损害了查询灵活性与可维护性。

这类采用的是过程式（procedural）的查询方式。用户在编写查询时，必须详细指定“如何”一步步地遍历指针、跳转记录来获取数据。这种方式要求用户对数据的物理存储结构有深入的了解，不仅学习成本高，而且编写的查询语句与底层实现紧密耦合，一旦存储结构改变，查询语句就需要重写。

科德的革命性的提出了一种声明式（declarative）的视角。用户只需关心“是什么”，即数据的定义属性（defining properties），而无需关心“如何做”。例如用户只想知道“杭州地区的客户”，而不关心数据库是通过索引扫描还是全表扫描来找到这些客户。正如科德在《Relational Completeness》中所强调的，这种基于数据属性的查询方式远比设计特定的检索算法或操作序列更自然。

02 关系模型基本概念

在原论文中，科德对关系(Relation）给出了严格定义：

给定任意集合S₁, S₂, ..., Sₙ，R是这些n个集合上的关系，如果它第一个元素来自S₁，第二个元素来自S₂，依此类推的n元组的集合。我们称Sⱼ为R的第j个域(domain)。

用更简洁的数学语言表达：

关系R 是 S₁ × S₂ × ... × Sₙ 的笛卡尔积一个子集

在科德的定义中，一个表就是一个关系，而关系本质上就是元组的集合（Set of Tuples）。比如一张Students 关系（表）就是由所有有效的学生元组组成的集合。Students = { (S001, 张三, 20, 计算机科学), (S002, 李四, 19, 数学), (S003, 王五, 21, 物理), ... } 。那为什么要用数学中的集合概念呢？因为集合带来了几个非常重要的特性：

无序性 (Unordered)：集合中的元素是无序的。这表示在 Students 关系中，张三的记录排在第一行还是第三行，在数学上是完全等价的。数据库系统可以为了性能优化而改变物理存储顺序，但不会改变关系的逻辑含义。这与早期的网状或层次数据库形成了鲜明对比。
唯一性 (No Duplicates)：集合中不能有重复的元素。因此，在 Students 关系中，不可能存在两个完全相同的元组，即所有属性值都一样的记录，主键也不同。这保证了数据的唯一性。

数据库的核心价值是支持灵活的数据操作，而集合论中的集合运算，比如并、交、差、笛卡尔积能为关系操作提供统一、严谨的数学逻辑，这解决了网状、层次模型进行数据操作需要依赖具体存储结构的问题。

在原论文中，介绍了关系由四个关键部分：

关系名 (Relation Name)

关系就是数据库表的名称，比如Students（学生）、Courses（课程）就是一个关系名。

属性 (Attributes)

属性就是常说的表中的“列”（Column）。比如在 Students 关系中，属性有 StudentID（学号）、Name（姓名）、Age（年龄）、Course（课程）。

域 (Domains)

域 (Domains)是关系理论中非常关键的一环，是属性的取值范围，它定义了该属性可以取哪些值，以及这些值的数据类型和语义。

StudentID 的域可能是“长度为8的数字字符串”。
Name 的域是“长度不超过50的字符序列”。
Age 的域是“1到150之间的整数”。
Course 的域是“{语文,英语,计算机科学, 数学, 物理, 化学, 生物}”这个集合。

通俗理解的可以把“域”想象成一个数据池。比如 Age 的域是一个装了1到150所有整数的池子，它的属性只能从这个池子里取值。如果一个学生的年龄填了“abc”或者“1000”，那就违反了域的定义，数据就是无效的。

元组 (Tuples)

元组 (Tuple)对应我们通常说的“行”（Row）或“记录”（Record），代表了现实世界中的一个具体实体或一次具体事件。在 Students 关系中，每一行就是一个元组。例如：

(S001, 张三, 20, 计算机科学)
(S002, 李四, 19, 数学)
(S003, 王五, 21, 物理)

将元组定义为一个有序的值的集合，这些值分别对应关系中的各个属性。元组 (S001, 张三, 20, 计算机科学) 表示存在一个学生，其学号是S001，姓名是张三，年龄是20，专业是计算机科学。

关系模型的伟大之处不在于发明了关系这个概念，而是用数学，特别是集合论（Set Theory）和谓词逻辑（Predicate Logic）为数据库中的数据赋予了精确、严谨的定义，并将其命名为关系。可以说是关系模型，让数据库从一种文件存储系统提升为一个建立在坚实数学基础上的数据模型。

实际上，关系模型奠定了数据描述的结构基础，关系代数（Relational Algebra）则构成了数据操作的方法论。但这一重要概念的完全明晰，仍需要等待大师的解释。

03 关系代数基本概念

1972年，科德在《Relational Completeness of Database Sublanguages》一文中，进一步完善了关系数据模型的理论体系，明确提出关系完备性概念，指出任何具备关系处理能力的查询语言，其表达能力至少应与关系代数（Relational Algebra）相当。

那什么是关系代数呢？在论文中科德给出了定义，它是一种基于逻辑和集合论的、形式化的查询语言，由一个有限的、封闭的运算符集合组成，这些运算符严格地定义在关系之上，其输入和输出均为关系。

从操作类型上看，关系代数的运算符可分为两大类。一类源自经典集合论的传统运算，包括并（∪）、交（∩）、差（−）和笛卡尔积（×）；另一类则是专为关系模型特化的操作，主要包括投影（π）、选择（σ）、连接（⋈）。这些操作共同构成了关系数据操作的形式化方法论，为查询语言的设计与优化奠定了坚实的理论基础。

关系代数主要操作符，图来自CMU课程

传统集合操作

并集(Union, ∪)：R∪S，所有属于R或S的元组。

交集(Intersection, ∩)：R∩S，同时属于R和S的所有元组。

差集(Difference, -)：R-S，属于R但不属于S的所有元组。

笛卡尔积( Cartesian Product, x)：R x S，由R中的每一个元组与S中的每一个元组组合而成的所有有序对。

专门的关系操作

投影 (Projection, π)：π(R)，从关系R中选出属性集A所包含的列，并去除结果中的重复元组。

连接 (Join, ⋈)：R ⋈ S，对R和S进行笛卡尔积后，再根据指定的连接条件进行选择所得到的结果关系。当连接条件为公共属性上的相等比较且结果中公共属性只保留一份时，称为自然连接。

选择(Selection, σ)：σ(R)，从关系R中选取满足给定选择条件的所有元组。

下面结合具体的 SQL 逐个介绍每个操作的含义。

并集（Union）

含义：生成一个关系，其中包含只出现在一个或两个输入关系中的所有元组。

语法：R∪S

SQL：

(SELECT * FROM R)
UNION ALL
(SELECT * FROM S);

交集（Intersection）

含义：生成一个关系，该关系只包含出现在两个输入关系中的元组。

语法：R∩S

SQL：

(SELECT * FROM R)
INTERSECT
(SELECT * FROM S);

差集（Difference）

含义：生成一个关系，其中只包含第一个输入关系中出现的元组，而不包含第二个输入关系中出现的元组。

语法：R-S

SQL：

(SELECT * FROM R)
EXCEPT
(SELECT * FROM S);

笛卡尔积（Cartesian Product）

含义：生成包含来自输入关系的元组的所有可能组合的关系。

语法：R x S

SQL：

SELECT * FROM R CROSS JOIN S;

投影（Projection）

含义：用只包含指定属性的元组生成关系。可用于重新排列属性顺序和操作属性的值。

语法：π_{A1,A2,A3...An}(R)

例子：π_ID,name(R)

SQL：

SELECT id,name FROM R ;

连接（Join）

含义：生成一个包含元组的关系，该元组是两个具有一个或多个属性的共同值元组(每个输入关系一个)的组合。

语法：R ⋈ S

SQL：

SELECT * FROM R NATURAL JOIN S;

选择（Selection）

从关系中选择满足选择谓词的元组。谓词用来充当过滤器，仅保留满足谓词条件的元组。可以使用合取/析取合并多个谓词。

语法：σ_predicate(R)

例子： π_name(σ_id=1(R))

SQL：

SELECT name FROM R WHERE id='1' ;

关系代数扩展操作符，图来自CMU课程

除以上述基本代数操作以外，还包括扩展操作符，如：重命名 (Rename，ρ)、赋值(Assignment，←)、去重 (Duplicate Elimination，δ)、聚合 (Aggregation，γ)、排序 (Sorting，τ)、除(Division，÷)等操作运算。这些扩展操作极大地提升了数据库关系代数的实用性和表达效率，使其不再是纯粹的数学理论，而成为了现代SQL等数据库查询语言最直接的理论根基。SQL中的 DISTINCT、GROUP BY、ORDER BY、窗口函数 等特性都可以在这些扩展操作符中找到对应的概念。

04 关系代数数学特性

关系代数不只是一组理论操作符，更重要的是它遵循严格数学定律。这些定律保证了数据操作的正确性，为数据库优化器提供理论依据，实际上查询优化器是关系代数等价变换的应用。下面简单介绍关系代数主要数学特性，大部分是中学数学代数知识。

交换律 (Commutativity)

指操作顺序可以交换而不影响结果。

在连接运算中， R ⋈ S = S ⋈ R，优化器可以自由地决定连接顺序。对于多表连接，这产生了大量等价的执行计划。优化器会估算每个计划的成本，根据中间结果集大小、I/O次数等选择最优的一个。这是决定连接顺序优化 的基础。对于并集运算: R ∪ S = S ∪ R，交集运算: R ∩ S = S ∩ R ，也适合使用交换律。

结合律 (Associativity)

指操作可以重新分组而不影响结果。

在连接运算中， (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T) ，可以结合律与交换律结合，为优化器提供了巨大的灵活性。优化器将一个复杂的多表连接表达式拆开，以不同的顺序和分组进行重新组合，以找到执行成本最低的物理计划，是连接重排序优化 的关键。

分配律 (Distributivity)

这是谓词下推（Predicate Pushdown） 这一最重要优化技术的直接理论来源。它允许将一元操作分配到二元操作中。

选择对连接的分配场景中，如果选择条件 c只涉及关系R的属性，那么：σ_c(R ⋈ S) = [σ_c(R)] ⋈ S ；如果选择条件 c 可分解为 c1 AND c2，且 c1 只含R的属性，c2 只含S的属性，那么：σ_c(R ⋈ S) = [σ_c1(R)] ⋈ [σ_c2(S)] 。这告诉优化器，应尽早执行选择操作，以减少参与连接的数据量，从而降低成本开销。

幂等律 (Ldempotence)

选择运算: σ_c(σ_c(R)) = σ_c(R) ，优化器可以识别并合并重复的选择条件，避免无谓的计算。比如一个 SQL被写成 WHERE salary > 10000 AND salary > 1000，优化器会将其简化为 WHERE salary > 1000。

除了上述特性以外，其他还包括恒等律 (Ldentity Laws)、吸收律 (Absorption Laws) 、投影与选择的交换律 (Commutation of Selection and Projection)等特性，正是这套基于数学定律的、系统性的转换规则，使得现代数据库优化器能够智能地将用户声明式的 SQL 查询，自动转化为高效至极的执行计划。可以说，理解这些特性是进行高级数据库性能调优和深度问题诊断的关键。

05 关系代数实际应用

下面以笔者经历为例子，经过脱敏和简化后，整个优化过程大致如下。某金融系统夜间批量生成报表的SQL语句执行时间突然从1分钟激增至20分钟，通过执行 EXPLAIN ANALYZE 获取到该语句如下关键执行计划：

Hash Join (cost=1,253,421.34..1,876,532.19 rows=1,253,421 width=256)
-> Seq Scan on xxx_info  (cost=0.00..623,421.34 rows=125,342,134 width=128)
-> Seq Scan on xxx_user_info (cost=0.00..253,110.85 rows=2,531,108 width=128)
Filter: (status = 'active'::text)

分析执行计划发现：

优化器选择对全量 xxx_info 表（1.25亿行）和全量 xxx_user_info 表（253万行）执行哈希连接
连接完成后才对 xxx_user_info 表应用status='active'的过滤条件
该计划生成了庞大的中间结果集，约316万亿条潜在连接记录

结合关系代数原理识别出问题：σ(status='active')( xxx_user_info ⋈ xxx_info)的执行效率远低于(xxx_user_info ⋈ σ(status='active')(xxx_info))。

优化方案：

SELECT /*报表字段*/ 
FROM xxx_info  t
JOIN ( SELECT * FROM xxx_user_info  WHERE status = 'active' -- 先过滤 ) c 
ON t.customer_id = c.id -- 后连接

优化后的执行计划变为：

Hash Join (cost=253,110.85..876,532.19 rows=1,253,421 width=256)
-> Seq Scan on xxx_info 
-> Bitmap Heap Scan on xxx_user_info 
   Recheck Cond: (status = 'active'::text)
   -> Bitmap Index Scan on xxx_user_info_status_idx

优化后，先过滤出active客户（约50万行）、参与连接的数据量减少98%、内存消耗也大幅减少，执行时间从20分钟降至1分钟。

这个简单案例介绍了关系代数在实际SQL 优化中的具体使用，首先分析执行计划，洞察操作顺序优劣；再诊断优化器误判，定位性能瓶颈根源；最后查询重写，通过调整代数路径，实现谓词下推、连接充足，从而实现SQL的高效执行。