数据库系统(4):关系代数

        关系代数 ( $Relational\ \ Algebra$ ) 可以看成一种过程式语言,可用于构造新关系。关系代数是一种纯理论语言,它定义了一些操作,运用这些操作可以从一个或多个关系中得到另一个关系而不改变原关系。关系代数的一个表达式可以嵌套另一个表达式,这种性质称为闭包 ( $closure$ ),即关系在关系代数下是封闭的。
        关系代数是一种每次一关系/集合的语言,即用一条不带循环的语句处理,结果也是由所有元组组成的整个关系。关系代数中包含了许多运算,其中五个基本运算是选择 ( $Selection$ ) 、投影 ( $Projection$ ) 、笛卡尔乘积 ( $Cartesian\ \ product$ ) 、集合并 ( $Union$ ) 、集合差 ( $Set\ \ difference$ ) 。选择和投影都是一元运算,其他的运算则是二元运算。除此之外,还有连接 ( $Join$ ) 、集合交 ( $Intersection$ ) 、 ( $Division$ ) 等,它们都能通过五个基本运算表示。

1. 一元运算

1.1 选择

$$ \sigma_{predicate}(R) $$

        作用于单个关系 $R$ ,得到一个新关系,该关系由满足谓词 $predicate$ 的元组组成。可以理解为从表中选出符合条件的行构成一个新表。

1.2 投影

$$ \prod\nolimits_{a_1,a_2,...,a_n}(R) $$

        作用于单个关系 $R$ ,得到一个由 $R$ 的垂直子集构成的新关系,该子集抽取 $R$ 中指定属性上的值并去掉重复元组。可以理解为从表中选出指定的列构成一个新表。

2. 集合运算

2.1 并

$$ R \cup S $$

        作用于两个关系 $R$ 和 $S$,定义了一个包含了 $R$ 和 $S$ 中所有不同元组的新关系,其中 $R$ 和 $S$ 具有并相容性,即具有同样多的属性,并且对应属性具有相同的域。

2.2 差

$$ R - S $$

        作用于两个关系 $R$ 和 $S$,定义了一个由所有属于 $R$ 但不属于 $S$ 的元组组成的新关系,$R$ 和 $S$ 必须具有并相容性。

2.3 交

$$ R \cap S $$

也可以用差运算表示交运算

$$ R \cap S = R - (R - S) $$

        作用于两个关系 $R$ 和 $S$,定义了一个由所有既属于 $R$ 又属于 $S$ 的元组组成的新关系, $R$ 和 $S$ 必须具有并相容性。

2.4 笛卡尔乘积

$$ R \times S $$

        定义了一个新关系,由 $R$ 和 $S$ 中的每个元组并联得到。如果关系 $R$ 具有 $I$ 个元组和 $N$ 个属性,而 $S$ 具有 $J$ 个元组,$M$ 个属性,那么 $R \times S$ 将具有 $I \times J$ 个元组,$N + M$ 个属性。如果 $R$ 和 $S$ 中具有同名属性,可以使用关系名作为前缀,从而保证属性名的唯一性。

2.5 表达式重命名

$$ \rho_{S_{(a_1,a_2,...,a_n)}}(E) $$

为表达式 $E$ 提供一个新名称 $S$,并将 $S$ 中的属性名替换为 $a_1$, $a_2$,…, $a_n$。

3. 连接

        在大部分时候,我们只需要满足特定条件的笛卡尔乘积的结合,因此一般采用连接代替笛卡尔乘积。连接是关系代数中一种重要的运算,由笛卡尔乘积导出,相当于把连接谓词看成条件,对笛卡尔乘积进行一次选择运算。

3.1 theta 连接

$$ R \Join_F S $$

        $\theta$ 连接定义了一个包含 $R$ 和 $S$ 的笛卡尔乘积中所有满足谓词 $F$ 的元组组成的关系。其中 $\theta$ 为 $<, \le, >, \ge, =, \ne$ 中的一个,$F$ 的格式为 $R.a_i\ \ \theta\ \ S.b_i$。当 $F$ 仅包含等号的情况下,可以称 $\theta$ 连接为等接 ( $Equijoin$ )。

3.2 自然连接

$$ R \Join S $$

        自然连接是 $R$ 和 $S$ 在所有公共属性上的等接,但是每个公共属性只保留一个。即将两个表连接起来,但删去所有重复的属性。

3.3 外连接

        左外连接可以表示为 $R$ ⟕ $S$ 。
        (左)外连接将 $R$ 中所有元组都保留在新关系中,包括 $S$ 中不存在属性,这些属性会在新关系中取空。除了左外连接之外,还有右外连接,保留所有右边关系的元组。以及全外连接,保留左右关系的元组。

3.4 半连接

$$ R \rhd_F S $$

        可以用投影和连接表示为( $A$ 为 $R$ 中所有属性的集合 )

$$ R \rhd_F S = \prod\nolimits_A(R\Join_FS) $$

        半连接在执行了两个关系的连接之后,将结果投影到 $R$ 的所有属性上。

4. 除

$$ R \div S $$

        可以将其用基本运算表示为

$$ T_1 \leftarrow \prod\nolimits_c(R)\\ T_2 \leftarrow \prod\nolimits_c((T_1 \times S) - R)\\ T \leftarrow T_1 - T_2 $$

        除定义了一个关系,该关系中的元组与 $S$ 的每个元组的组合都能在 $R$ 中找到匹配元组。

5. 聚合运算和分组运算

5.1 聚合运算

        聚合运算用于将数据进行汇总。常用的聚合函数有:

5.2 分组运算

        分组运算用于将数据进行分组。分组运算要与聚合函数结合,得到的结果包含分组属性和每个聚合函数的结果。

数据库系统(4):关系代数