【数据库系统原理】第6篇：关系代数基础：传统的集合运算与专门的关系运算

目录

一、关系代数为何重要：声明性查询的代数引擎

二、传统的集合运算：朴素集合论的四则操作

三、专门的关系运算之一：选择与投影

四、专门的关系运算之二：连接

五、专门的关系运算之三：除法

六、关系代数的完备性与结语

一、关系代数为何重要：声明性查询的代数引擎

在层次模型和网状模型的时代，查询是一种过程性活动：程序员编写代码，指定从哪个入口记录出发，沿哪条指针链路遍历，在哪个节点截取数据。这一模式要求程序员掌握物理存储结构，查询逻辑与存取路径紧密耦合，任何存储结构的调整都可能导致查询程序重写。

科德在设计关系模型时提出了一种截然不同的范式：声明性查询——用户只需描述想要什么数据，系统自行决定如何获取。这一设想的实现需要一个中间层，它能够将用户的声明性需求表达为一个可被系统分析、等价变换和执行规划的数学对象。这个中间层，就是关系代数。

关系代数是一种过程性的形式化语言——它用基本运算的组合来表达一个查询的步骤。但用户通常不直接书写关系代数表达式，他们使用的是声明性的SQL语句。数据库系统的查询处理模块负责将声明性的SQL翻译为关系代数表达式树，然后运用代数等价变换规则对这棵树进行优化重写，最终生成物理执行计划。在这个意义上，关系代数是声明性查询语言与物理执行引擎之间的代数桥梁。

关系代数的运算符具有一个关键的代数属性——封闭性：每一个运算符的输入都是关系，输出也是关系。正是因为输入和输出的类型相同，运算符可以任意嵌套，理论上可以构造出无限复杂的查询。这种封闭性是代数的核心特征——如同整数在加减乘除下封闭一样，关系在关系代数运算下也是封闭的。

二、传统的集合运算：朴素集合论的四则操作

关系是元组的集合。既然是集合，朴素集合论中的基本运算——并、差、交、笛卡尔积——自然可以应用于关系之上。但需要稍作限定：这些运算要求参与运算的两个关系具有相容的模式。

并相容性（Union Compatibility）是传统集合运算的前提条件。两个关系R和S要参与并、差、交运算，必须满足：它们具有相同数量的属性（即度数n相同）；且第i个属性域必须与第i个属性域相同（或域相容）。换言之，R和S的结构必须完全一致——这保证了运算结果的每个元组在结构上是合法的。

并运算（Union）记作R ∪ S，结果包含所有出现在R中或出现在S中（或同时出现）的元组。形式化定义：R ∪ S = { t | t ∈ R ∨ t ∈ S }。并运算要求R和S并相容，结果关系的模式与R（即与S）相同。并运算通常用于合并两个结构相同的数据库片——例如，将“上半年订单”与“下半年订单”合并为“全年订单”。

差运算（Difference）记作R - S，结果包含所有出现在R中但不出现在S中的元组。形式化定义：R - S = { t | t ∈ R ∧ t ∉ S }。差运算同样要求并相容。差运算的典型应用场景是找出“属于某集合但不属于另一集合”的记录——例如，“所有已经注册但尚未选课的学生”可以通过学生集与选课学生集的差来获得。

交运算（Intersection）记作R ∩ S，结果包含所有同时出现在R和S中的元组。形式化定义：R ∩ S = { t | t ∈ R ∧ t ∈ S }。交运算不是基本运算——它可以用差运算表达：R ∩ S = R - (R - S)。也就是说，先从R中减去所有不在S中的元组，剩下的就是R与S的交集。但出于表达上的便利和实现效率的考虑，交运算常被作为独立运算符提供。

笛卡尔积（Cartesian Product）记作R × S，它是传统集合运算中的异类——它不要求并相容，也不要求参与运算的两个关系有任何模式上的关联。其形式化定义：设R的模式为(A₁, A₂, ..., Aₙ)，S的模式为(B₁, B₂, ..., Bₘ)，则R × S的结果模式为(A₁, ..., Aₙ, B₁, ..., Bₘ)，结果关系包含所有的元组串联——R的每一个元组与S的每一个元组拼接形成的所有可能组合。结果关系的基数等于R的元组数乘以S的元组数。

笛卡尔积本身不携带任何查询语义——它只是机械地生成全组合。笛卡尔积的真正威力必须在与选择和投影结合使用时才会显现。事实上，SQL中FROM子句后列出多个表产生的恰恰是这些表的笛卡尔积（或其近似），随后通过WHERE条件从中筛选出有意义的组合。从笛卡尔积到有意义查询的蜕变，正是选择与连接运算的职责。

三、专门的关系运算之一：选择与投影

专门的关系运算不是从集合论借用的，而是为关系模型专门设计的。它们赋予了关系代数数据检索的能力。

选择运算（Selection）记作σ_P(R)，其中P是一个命题公式（谓词），R是一个关系。选择运算从R中筛选出所有使得P为真的元组。形式化定义：σ_P(R) = { t | t ∈ R ∧ P(t) = true }。结果关系的模式与R完全相同——选择运算只过滤行，不改变列结构。

命题公式P由一系列比较表达式通过逻辑连接词（∧与、∨或、¬非）组合而成。每个比较表达式的形式为“A θ B”或“A θ c”，其中A和B是属性名，c是常量，θ是比较运算符（=、≠、<、≤、>、≥）。例如，σ_{年龄≥18 ∧ 性别='女'}(学生) 表示从学生关系中筛选出所有成年女性学生的元组。

选择运算的几个关键性质在查询优化中极为重要。其一，交换律——多个选择条件的先后顺序不影响结果，σ_P₁(σ_P₂(R)) = σ_P₂(σ_P₁(R)) = σ_P₁∧P₂(R)。其二，级联性——选择运算可以分解或合并，这在代价估算中提供了灵活调度。其三，下推性——选择运算应尽早执行，以减少中间结果的规模，这是查询优化器最核心的优化策略之一。

投影运算（Projection）记作Π_{A₁, A₂, ..., Aₖ}(R)，其中A₁到Aₖ是R中的属性名。投影运算从R中仅保留指定的属性列，并去除结果中可能出现的重复元组。形式化定义：Π_L(R) = { t[L] | t ∈ R }，其中t[L]表示从元组t中抽取属性列表L对应的分量。

投影运算的去重（去除重复元组）是关系代数理论层面的规定——因为关系是集合，集合中不允许重复元素。但在SQL的实践中，SELECT子句默认不去重，必须显式使用DISTINCT关键字。这一SQL与理论之间的偏差是出于工程效率的考量——去重需要排序或哈希操作，代价较高，而许多实际场景中用户并不需要去重。

选择与投影的组合可以完成简单的单表查询。例如，“查询年龄大于18岁的学生的姓名和学号”可以表达为：Π_{姓名, 学号}(σ_年龄>18(学生))。表达式树从内向外读：先对学生关系施加选择条件，再对筛选结果施加投影。

四、专门的关系运算之二：连接

连接运算（Join）是关系代数中最具表现力的运算符，它将来自两个关系的元组按照某种条件配对组合。其最一般的形式是θ-连接。

θ-连接记作R⋈_AθBS，其中θ是比较运算符，A是R的属性，B是S的属性。其语义可以理解为：先对R和S求笛卡尔积，再对积的结果施加选择运算。形式化地：R⋈_AθBS = σ_AθB(R × S)。连接运算的结果模式包含R的全部属性和S的全部属性，结果关系中的每条元组由R的一个元组与S的一个元组拼接而成，且拼接后的元组必须满足连接条件AθB。

当连接条件中的θ是等号时，这种连接称为等值连接（Equi-Join）。等值连接是实践中最常见、最重要的连接形式——SQL中的INNER JOIN ... ON条件绝大多数情况下都是等值条件。等值连接的结果中，连接属性A和B的取值在每个结果元组中相同，因此会形成两列取值相同的属性。

自然连接（Natural Join）记作R⋈S，是等值连接的一种重要特例。它不需要显式指定连接条件——系统自动找出R和S中所有同名的属性，以这些属性上的等值条件作为连接条件，并在结果中去掉重复列（只保留一列同名的连接属性）。自然连接优雅地处理了一种极常见的数据关联场景：外码参照主码的连接。如果“选课”关系的外码“学号”参照“学生”关系的主码“学号”，那么选课⋈学生的自然连接会基于“学号”列进行等值匹配，并将匹配成功的元组串联起来。自然连接的简洁语法使得它成为理论分析中的首选工具，但在工程实现中，由于隐式基于列名的特性可能导致意外连接，SQL未直接采用这种语法。

外连接家族——左外连接、右外连接、全外连接——突破了内连接“必须在两方都找到匹配”的限制，允许保留未能匹配的元组并以空值填充缺失侧的数据。将在后续文章中专门论述。

五、专门的关系运算之三：除法

除法运算是关系代数中最不直观、却最具有理论深度的运算符。它专门用来处理“全部”语义的查询——即“找出满足某个条件集合中所有条件的实体”。

除法运算记作R ÷ S。设R是二元关系（包含属性A和B），S是一元关系（包含属性B，与R的B属性基于相同域）。R ÷ S的结果是一个一元关系（仅包含属性A），其内容为：所有在R中与S中的每一个B值都有关联的A值。

形式化地：R ÷ S = { t[A] | t ∈ R ∧ ∀s ∈ S, (t[A], s[B]) ∈ R }。也就是说，一个A值要出现在除法结果中，它必须与S中的每一个B值都在R中存在配对。

例如，设R为“选课(学生, 课程)”，S为{数学, 英语, 物理}——即一个包含三门课程的集合。则R ÷ S的结果是“同时选修了数学、英语和物理这三门课程的学生名单”。这个查询要求的是“全部”的语义——不是选了其中一两门，而是三门都选。

除法运算也可以用基本运算表达：R ÷ S = Π_A(R) - Π_A((Π_A(R) × S) - R)。这个表达式的逻辑值得拆解：先从R中取出所有A值，与S做笛卡尔积得到“所有A值与所有B值的全组合”，减去R中实际存在的配对，得到“缺失的配对”，再取这些缺失配对中的A值，最后用全体A值减去这些有缺失的A值——剩下的就是“一个不缺”的A值。这个推导过程直观地展示了关系代数的封闭性：除运算可以用差运算、笛卡尔积和投影来表达。

SQL语言中没有直接对应除法的运算符，实现“全部”语义通常需要巧用NOT EXISTS嵌套子查询来完成——这恰好是除法运算通过基本运算表达式的思路。

六、关系代数的完备性与结语

一个查询语言如果能够表达所有的关系代数运算，则称其具有关系完备性。科德在1972年的论文中证明，关系代数的基本运算符集合（{并、差、笛卡尔积、选择、投影}）已经构成一个最小完备集——其他所有运算（交、各种连接、除）都可以用这五种基本运算表达。SQL是关系完备的——它可以表达关系代数能够表达的一切查询。

关系代数的意义并不在于让用户直接书写它，而在于它为查询优化器提供了一个可进行代数推导的数学结构。当你书写一条SQL查询时，系统首先将其编译为关系代数表达式树，然后应用一系列代数等价变换——选择下推、投影下推、连接重排——在保留语义不变的前提下，将表达式树变形为执行代价更低的等价形式。这个过程之所以可行，全赖关系代数的严格代数性质。

下一篇，我们将沿着关系代数的阶梯上行，深入那些复杂连接操作与除法的查询实践，并开始触及SQL语言的表层——看看声明性查询语言是如何从这套代数引擎中生发出来的。