Database System（四）

type

status

date

slug

summary

动机（Motivation）

在前面的笔记中，我们讨论了 SQL 是一种声明式编程语言。这意味着你只需要指定你想要什么，而不需要指定如何去做。从用户的角度来看，这非常好，因为它让查询编写变得更加简单。

然而，作为数据库工程师，我们通常希望使用一种更具表现力的语言。当我们在几周后学习查询优化时，我们会希望有一种方式来表达数据库执行查询时可能采用的多种有效执行计划。为此，我们将使用关系代数（Relational Algebra），这是一种过程式编程语言，也就是说，查询会明确指定要使用哪些操作符以及它们的执行顺序。

关系代数简介（Relational Algebra Introduction）

关系代数中的所有操作符都接受一个关系作为输入，并输出一个关系。一个基本查询如下所示：

π（投影）操作符只选择要传递给下一个操作符的列（就像 SQL 中的 SELECT）。在这个例子中，操作符将 dogs 关系作为参数，并返回一个只包含 name 列的新关系。

一个关于关系代数的重要事实是：关系是元组的集合，不能包含重复项。如果最初的 dogs 关系是：

name	age
Scooby	10
Buster	15
Buster	20

上面的查询将返回：

name

Scooby

Buster

虽然两个 Buster 原本因年龄不同而被认为是不同的元组，但一旦去除了 age 列，它们就变成了重复项，因此在输出关系中只保留一个。

最后一句：

让我们正式介绍关系代数的操作符。

投影（π）

我们已经介绍过 投影操作符，它接受一个关系作为输入，并仅选择指定的列。要选择的列写在操作符的下标中，就像大多数操作符的参数一样。投影的输出模式（schema）由所列出的列的结构决定。

投影操作符是关系代数中对应于 SQL 的 SELECT 子句的部分。

现在我们可以用关系代数来表达仅包含 SELECT 和 FROM 子句的 SQL 查询。例如，以下 SQL 查询：

可以用我们在第 2 节介绍的表达式表示为：

请注意：关系代数中并没有一个专门对应 SQL 中 FROM 的操作符，因为这些操作符的参数本身就已经指定了要从哪个表中取数据。

选择（σ）

选择操作符 作用于一个关系中，用来根据某个条件筛选行（元组）。输出的结构（schema）与输入相同，不需要去重。

不要被这个名字“Selection”误导了 —— 它其实是对应于 SQL 中的 WHERE 子句，而不是 SELECT 子句。

我们来看一个 SQL 查询，并尝试用关系代数表达它：

对应的关系代数表达式有两种写法，都是正确的：

先做投影，再选择：

先选择，再做投影：

这两种表达方式体现了关系代数的灵活性。在 SQL 中通常只有一种方式来表达查询目的，但在关系代数中可以用多种不同的表达式来实现相同的功能。

第一种方式：先选出想要的列，再筛掉不符合条件的行。

第二种方式：先筛掉不符合条件的行，再选择需要的列。

我们很快会学习如何评估哪种执行计划更好

另外，选择操作符支持复合条件（compound predicates）：

∧ 表示 SQL 中的 AND；

∨ 表示 SQL 中的 OR。

例如以下 SQL：

对应的关系代数表达式为：

并（Union，∪）

我们学习的第一种将不同关系中的数据组合起来的方法是 并操作符（union operator）。

就像 SQL 中的 UNION 一样，我们会取出每个关系中的所有元组并进行合并，同时移除重复项。

举个例子，假设我们有一个 dogs 表，如下所示：

name	age
Scooby	10
Buster	15
Garfield	20

还有一个 cats 表，如下所示：

name	age
Tom	8
Garfield	10

以下关系代数表达式：

将返回：

name

Scooby

Buster

Tom

Garfield

注意事项：

Garfield 只出现一次，因为关系是元组的集合，自动去重。

并操作符的要求：

参与并运算的两个关系，必须拥有相同数量的属性（列）；
并且在对应位置上的属性类型必须相同。

因此，不允许以下情况：

把一个有两列的关系与一个只有一列的关系进行并运算；

把一个字符串列与一个整型列合并。

差集（Set Difference，−）

另一个集合操作是 差集操作符，用来从第一个关系中移除所有在第二个关系中也存在的行。这类似于 SQL 中的 EXCEPT 子句。

和并集一样，两个输入关系必须是兼容的：也就是说，它们要有相同数量的列，且对应列的数据类型一致。

如果你运行以下关系代数表达式：

在之前章节中的 dogs 和 cats 表上，会得到结果：

name

Scooby

Buster

原因是 Garfield 同时出现在了 cats 表中，因此被排除了。而 cats 表中的名字不会出现在结果中，因为差集只保留第一个关系中存在但第二个关系中不存在的元组。

交集（Intersection，∩）

交集操作与 SQL 中的 INTERSECT 操作类似：只保留同时出现在两个表中的元组。

如果你运行：

结果是：

name

Garfield

因为 Garfield 是唯一同时出现在两个表中的名字。

这两种操作都和并集一样需要满足“列数相同、类型一致”的前提。

笛卡尔积（×）

笛卡尔积操作符 类似于 SQL 中的 笛卡尔积（Cartesian product）。

输出结果是：两个关系中每一对可能的元组组合。

两个关系的结构（schema）不需要兼容，因为笛卡尔积只是直接拼接它们的列。

不需要去重，因为不会自动产生重复项。

示例

假设有一个 dogs 表：

name	age
Scooby	10
Buster	15
Garfield	20

还有一个 parks 表：

park	city
Golden Gate Park	San Francisco
Central Park	New York City

SQL 查询：

对应的关系代数表达式为：

输出结果将是：

name	age	park	city
Scooby	10	Golden Gate Park	San Francisco
Scooby	10	Central Park	New York City
Buster	15	Golden Gate Park	San Francisco
Buster	15	Central Park	New York City
Garfield	20	Golden Gate Park	San Francisco
Garfield	20	Central Park	New York City

连接（⋈）

我们之前还没有讨论如何在关系代数中表示连接操作，现在来补上！

要在关系代数中进行内连接（inner join），语法是：

例如，要按 name 列连接 cats 和 dogs 表，可以写作：

如果不指定连接条件，则默认进行的是自然连接（natural join），会基于两个表中所有相同名称的列自动连接。所以上面的连接也可以简写为：

正式来说，这种内连接被称为 θ连接（Theta Join），即：

其中 θ 表示连接条件，比如上例中的：

连接操作符（⋈） 像选择操作符（σ）一样，支持复合条件：

∧ 表示 AND

∨ 表示 OR

其实，θ连接和自然连接都可以用笛卡尔积（×）加上选择（σ）来实现：

θ连接：

自然连接：

本节只涉及关系代数中的内连接。虽然也可以通过组合已有操作推导出右连接、左连接、全外连接等内容，但超出了本课程范围。

重命名（ρ）

重命名操作符（ρ） 实质上与 SQL 中的 别名（alias） 功能相同。它用于更改关系或其属性的名称（也就是更改模式 schema）。

示例：

如果你想避免在连接表达式中反复写出表名，可以使用重命名。如下所示：

这个表达式首先将 dogs 表的 name 列重命名为 dname，然后再与 cats 表进行连接。

优点：避免列名冲突。

缺点：因为两个表现在不再有相同列名了，不能使用自然连接，但你也不再需要指定列来自哪个表。

分组 / 聚合（γ）

关系代数中最后一个操作符是 分组 / 聚合操作符（groupby / aggregation operator），等价于 SQL 中的 GROUP BY 和 HAVING。

示例 1：

关系代数表示为：

示例 2（带聚合输出）：

关系代数表示为：

聚合操作符 γ 可以用于表达 SQL 中的 SUM、COUNT、MAX、MIN 等函数，同时支持 GROUP BY 和 HAVING 条件。