DBS note5：Relational Algebra（关系代数）

一、关系代数简介

二、Projection ()

三、Selection ()

四、Union ()

五、Set Difference (-)

六、Intersection ()

七、Cross Product ()

八、Joins ()

九、Rename ()

十、Group By / Aggregation ()

一、关系代数简介

关系代数中的所有运算符都接受一个关系并输出一个关系。一个基本的查询看起来像这样：

$\pi_{name}(dogs)$

π 运算符选择它希望传递给下一个运算符的列（就像 SQL 的 SELECT）。在这种情况下，该运算符将 dogs 关系作为参数，并返回仅具有 dogs 关系的 name 列的关系。关于关系代数的一个重要事实是，关系是元组的集合，这意味着它们不能包含重复项。如果 dogs 关系最初是：

上面的查询将返回：

一开始，两个“Buster”是不同的，因为它们有不同的年龄，但是一旦去掉“age”列，它们就成了重复的，所以输出关系中只剩下一个。下面正式介绍关系代数运算符。

二、Projection ( $\pi$ )

我们已经接触过投影运算符，该运算符接受一个关系作为输入，并仅选择指定的列。列是在运算符的下标中指定的，就像几乎所有运算符的参数一样。投影的输出模式由列列表的模式确定。投影运算符是关系代数中对应 SQL SELECT 子句的运算符。

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

 SELECT name FROM dogs;

可以表示为：

$\pi_{name}(dogs)$

请注意，关系代数中没有与 FROM 运算符等效的运算符，因为这些运算符的参数指定我们从哪些表中提取数据。

三、Selection ( $\sigma$ )

选择运算符接收一个关系，并根据特定条件筛选行。输出模式将与输入模式相同，且选择运算符不需要进行重复消除。不要让名称混淆你 —— 这个运算符相当于 SQL 的 WHERE 子句，而不是它的 SELECT 子句。让我们尝试用关系代数来表达以下查询：

SELECT name, age FROM dogs WHERE age = 12;

等价的关系代数表达式是：

$\sigma_{age=12}(\pi_{name,age}(dogs))$

另外一个正确的表达查询是：

$\pi_{name,age}(\sigma_{age=12}(dogs))$

这展示了关系代数的美妙之处。对于查询尝试实现的目标，编写 SQL 只有一种（合理的）方式，但是我们可以提出多个在关系代数中得到相同结果的不同表达式。

在第一个表达式中，我们首先选择我们想要的列，然后过滤掉我们不想要的行。

在第二个表达式中，我们首先过滤行，然后选择列。

选择运算符还支持复合谓词。符号 $\wedge$ 对应于 SQL 中的 AND 关键字，符号 $\vee$ 对应于 OR 关键字。例如，

SELECT name, age FROM dogs WHERE age = 12 AND name = 'Timmy';

等价于：

$\pi_{name,age}(\sigma_{age=12 \wedge name='Timmy'}(dogs))$

四、Union ( $\cup$ )

我们将学习如何使用并运算符将不同关系的数据合并在一起的第一种方式是使用并运算符。就像 SQL 中的 UNION 子句一样，我们从每个元组中取出所有行并将它们组合在一起，同时去除重复项。例如，假设我们有一个 dogs 表：

一个如下所示的 cats 表：

表达式如下：

$\pi_{name}(dogs) \cup \pi_{name}(cats)$

其会返回：

注意 Garfield 只出现了一次，因为关系是元组的集合，因此会去重。此外，需要注意的是，所有这些集合运算符的一个规则是它们必须在具有相同数量的属性（列）的关系上进行操作，并且相应位置上的属性必须具有相同的类型。不能对具有两列的关系进行联合操作，而只有一个列的关系，也不能对一个包含字符串列的关系进行联合操作，而另一个只包含整数列。

五、Set Difference (-)

另一个集合运算符是集合差运算符。与联合操作一样，输入的两个关系必须是兼容的（列必须以相同的顺序和相同的类型排列）。集合差运算等同于 SQL 子句 EXCEPT。它返回第一个表中的每一行，除了也出现在第二个表中的行。与选择类似，对于集合差运算，不需要去重。如果运行：

$\pi_{name}(dogs)-\pi_{name}(cats)$

在前一部分介绍的 dogs 和 cats 表上运行的表达式将得到：

Garfield 没有出现，因为他在 cats 表中，并且输出中只有在第一个关系（dogs）的行才有可能出现。

六、Intersection ( $\cap$ )

Intersection 与 INTERSECT SQL 操作符相似，它仅保留在交集中同时出现在两个表中的行。如果运行：

$\pi_{name}(dogs) \cap \pi_{name}(cats)$

在第 5 节介绍的表上运行，你将得到：

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

七、Cross Product ( $\times$ )

交叉乘积运算符就像在 SQL 中执行笛卡尔积一样。输出是来自两个关系的每对元组的一个元组。两个输入关系的模式不必兼容，因为交叉乘积直接将它们连接起来。不需要消除重复项，因为不会生成重复项。例如，假设我们有一个 dogs 表：

和一个 parks 表：

这个查询的关系代数等价表达式是：

SELECT * FROM dogs, parks;

$dogs \times parks$

输出为：

事实上，直积（×）是内连接的基础。

八、Joins ( $\bowtie$ )

要将两个表进行内连接，将左表写在运算符的左侧，将连接条件放在下标中，然后将右表放在右侧。要在名字列上将 cats 表与 dogs 表连接在一起，可以这样写：

$cats \bowtie_{cats.name=dogs.name} dogs$

如果你不指定连接条件，它将成为一个自然连接。回顾一下 SQL 的笔记，自然连接将每个具有相同名称的表的所有列连接在一起。因此，你也可以这样写相同的查询：

$cats \bowtie dogs$

从形式上讲，我们将内连接运算符称为 Theta Join（ $\bowtie_\theta$ ）。 $\theta$ 是指连接条件，因此对于上面的表达式，连接条件是：

cats.name=dogs.name

$\bowtie$ 运算符执行内连接，至于派生出的右连接、左连接和全外连接的方法，超出了我们基础学习的范畴。

就像选择运算符 $\sigma$ 一样，连接运算符 $\bowtie$ 也支持复合谓词运算符 $\wedge$ （AND）和 $\vee$ （OR）。

Theta 连接和自然连接实际上可以从交叉乘积（ $\times$ ）和选择的合取（ $\sigma$ ）派生出来。例如，

$cats \bowtie_\theta dogs$

可以被写成：

$\sigma_\theta(cats \times dogs)$

而自然连接：

$cats \bowtie dogs$

可以被写成：

$\sigma_{cats.col1=dogs.col1 \wedge ... \wedge cats.colN=dogs.colN }(cats \times dogs)$

九、Rename ( $\rho$ )

重命名运算符本质上实现了 SQL 中的别名。它用于通过重命名关系和/或它们的属性来更改模式。例如，如果我们想避免在表达式的其余部分中包含表名，就像在连接部分的表达式中一样，可以改为编写：

$cats \bowtie_{name=dname\ \rho_{name->dname}} dogs$

此表达式将 dogs 关系的名称列首先重命名为 dname，因此列名称不再冲突。

我们不能再使用自然连接，因为列不再具有相同的名称，但如果要包含其他运算符，则无需指定列来自哪个关系。

十、Group By / Aggregation ( $\gamma$ )

最后一个关系代数运算符是 group by / aggregation 运算符，它基本上相当于在 SQL 中使用 GROUP BY 和 HAVING 子句。例如，SQL 查询:

SELECT age FROM dogs GROUP BY age HAVING COUNT(*) > 5;

可以被表示为关系代数：

$\gamma_{age,COUNT(*)>5}(dogs)$

此外， $\gamma$ 运算符可用于从 SQL 中选择聚合列，如 MAX、MIN、SUM、COUNT 等。这是前面的修改后的查询：

SELECT age, SUM(weight) FROM dogs GROUP BY age HAVING COUNT(*) > 5;

可以被表示为关系代数：

$\gamma_{age,SUM(weight),COUNT(*)>5}(dogs)$

以上，DBS note5：Relational Algebra（关系代数）

祝好。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/186043.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！