目录一、关系代数为何重要声明性查询的代数引擎二、传统的集合运算朴素集合论的四则操作三、专门的关系运算之一选择与投影四、专门的关系运算之二连接五、专门的关系运算之三除法六、关系代数的完备性与结语一、关系代数为何重要声明性查询的代数引擎在层次模型和网状模型的时代查询是一种过程性活动程序员编写代码指定从哪个入口记录出发沿哪条指针链路遍历在哪个节点截取数据。这一模式要求程序员掌握物理存储结构查询逻辑与存取路径紧密耦合任何存储结构的调整都可能导致查询程序重写。科德在设计关系模型时提出了一种截然不同的范式声明性查询——用户只需描述想要什么数据系统自行决定如何获取。这一设想的实现需要一个中间层它能够将用户的声明性需求表达为一个可被系统分析、等价变换和执行规划的数学对象。这个中间层就是关系代数。关系代数是一种过程性的形式化语言——它用基本运算的组合来表达一个查询的步骤。但用户通常不直接书写关系代数表达式他们使用的是声明性的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记作σsubP/sub(R)其中P是一个命题公式谓词R是一个关系。选择运算从R中筛选出所有使得P为真的元组。形式化定义σsubP/sub(R) { t | t ∈ R ∧ P(t) true }。结果关系的模式与R完全相同——选择运算只过滤行不改变列结构。命题公式P由一系列比较表达式通过逻辑连接词∧与、∨或、¬非组合而成。每个比较表达式的形式为“A θ B”或“A θ c”其中A和B是属性名c是常量θ是比较运算符、≠、、≤、、≥。例如σsub年龄≥18 ∧ 性别女/sub(学生) 表示从学生关系中筛选出所有成年女性学生的元组。选择运算的几个关键性质在查询优化中极为重要。其一交换律——多个选择条件的先后顺序不影响结果σsubP₁/sub(σsubP₂/sub(R)) σsubP₂/sub(σsubP₁/sub(R)) σsubP₁∧P₂/sub(R)。其二级联性——选择运算可以分解或合并这在代价估算中提供了灵活调度。其三下推性——选择运算应尽早执行以减少中间结果的规模这是查询优化器最核心的优化策略之一。投影运算Projection记作ΠsubA₁, A₂, ..., Aₖ/sub(R)其中A₁到Aₖ是R中的属性名。投影运算从R中仅保留指定的属性列并去除结果中可能出现的重复元组。形式化定义ΠsubL/sub(R) { t[L] | t ∈ R }其中t[L]表示从元组t中抽取属性列表L对应的分量。投影运算的去重去除重复元组是关系代数理论层面的规定——因为关系是集合集合中不允许重复元素。但在SQL的实践中SELECT子句默认不去重必须显式使用DISTINCT关键字。这一SQL与理论之间的偏差是出于工程效率的考量——去重需要排序或哈希操作代价较高而许多实际场景中用户并不需要去重。选择与投影的组合可以完成简单的单表查询。例如“查询年龄大于18岁的学生的姓名和学号”可以表达为Πsub姓名, 学号/sub(σsub年龄18/sub(学生))。表达式树从内向外读先对学生关系施加选择条件再对筛选结果施加投影。四、专门的关系运算之二连接连接运算Join是关系代数中最具表现力的运算符它将来自两个关系的元组按照某种条件配对组合。其最一般的形式是θ-连接。θ-连接记作R⋈subAθB/subS其中θ是比较运算符A是R的属性B是S的属性。其语义可以理解为先对R和S求笛卡尔积再对积的结果施加选择运算。形式化地R⋈subAθB/subS σsubAθB/sub(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和BS是一元关系包含属性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 ΠsubA/sub(R) - ΠsubA/sub((ΠsubA/sub(R) × S) - R)。这个表达式的逻辑值得拆解先从R中取出所有A值与S做笛卡尔积得到“所有A值与所有B值的全组合”减去R中实际存在的配对得到“缺失的配对”再取这些缺失配对中的A值最后用全体A值减去这些有缺失的A值——剩下的就是“一个不缺”的A值。这个推导过程直观地展示了关系代数的封闭性除运算可以用差运算、笛卡尔积和投影来表达。SQL语言中没有直接对应除法的运算符实现“全部”语义通常需要巧用NOT EXISTS嵌套子查询来完成——这恰好是除法运算通过基本运算表达式的思路。六、关系代数的完备性与结语一个查询语言如果能够表达所有的关系代数运算则称其具有关系完备性。科德在1972年的论文中证明关系代数的基本运算符集合{并、差、笛卡尔积、选择、投影}已经构成一个最小完备集——其他所有运算交、各种连接、除都可以用这五种基本运算表达。SQL是关系完备的——它可以表达关系代数能够表达的一切查询。关系代数的意义并不在于让用户直接书写它而在于它为查询优化器提供了一个可进行代数推导的数学结构。当你书写一条SQL查询时系统首先将其编译为关系代数表达式树然后应用一系列代数等价变换——选择下推、投影下推、连接重排——在保留语义不变的前提下将表达式树变形为执行代价更低的等价形式。这个过程之所以可行全赖关系代数的严格代数性质。下一篇我们将沿着关系代数的阶梯上行深入那些复杂连接操作与除法的查询实践并开始触及SQL语言的表层——看看声明性查询语言是如何从这套代数引擎中生发出来的。