概念

关系

在离散数学中已经定义过关系：若干个集合 D_1, D_2, \dots, D_n 的 Descarte 乘积的任意子集，是一个 n 元关系，即

R \subset D_1 \times \cdots \times D_n.

由于关系是 Descarte 乘积的子集，关系里的元素也称为元组（tuple）。这其实给出了关系的另一种更形象的定义：一个关系就是储存了若干元组的集合。

关系型数据库中的关系还会引入属性（attribute），它是给关系中每个列起的名字，可以类比 named tuple 或者 C/C++ 里面 struct 的变量名。

候选码（candidate key）也叫候选键，指的是能唯一标识关系中元组的属性集。其形式化定义为：

设关系 R 有属性 a_1, \dots, a_n，若某个属性集 K = \{a_{i_1}, \dots, a_{i_m}\} 满足：

唯一性：对任意两个不同的元组，其在属性集上的取值也一定不同：\forall t_1, t_2 \in R, t_1 \neq t_2 \implies \Pi_{K} t_1 \neq \Pi_{K} t_2
极小性：删除 K 中任意一个属性，上述唯一性不再成立

一个关系的候选码一版不唯一，从候选码中可以任意选取一个主码（primary key）。选取主码后，属性也分为主属性和非主属性。

外码（foreign key）则说明了多个关系之间的联系，如果关系 R_1 的部分属性 X 是关系 R_1 的主码，则称 X 是关系 R_1 的外码，R_2 则成为被参照关系。

选取：从关系中选择满足一定条件的元组，使用 \sigma 表示

\sigma_{p}(R) = \{t \in R: p(t)\}

投影：选择若干属性列组成新的关系

\Pi_{X} (R) = \{t[A]: t \in R \}.

连接（join）是关系中非常重要的一个运算，它沟通了两个关系。连接的基本定义为：

R \bowtie_{\theta} S := \sigma_{\theta} (R \times S).

即先做 Descarte 积，再选择出满足某条件 \theta 的元组。

从操作上，也可以直接理解为，遍历 R 中的元素 t_r，一旦 S 中有 t_s 能满足 \theta，就生成一个新元组 (t_r, t_s)。

自然连接是特殊的连接，若 R 和 S 有相同属性组 Y = \{a_1, \dots, a_m\}，我们可以设条件 \theta 为两边的属性组是否相同，得到：

R \bowtie S := \{(t_r, t_s): t_r \in R, t_s \in S, t_r[Y] = t_s[Y]\}.

注意自然连接还多了一步去重，去掉重复的属性组。

从操作上，自然连接可以看作，在 R 和 S 上把属性 Y 的取值完全相同的元组做拼接。

关系代数的除法询问的是某关系 R 中是否有元素已覆盖 S 的所有取值。

这一名称来自 Descarte 积的逆运算：若 R = A \times B，那么 A = R \div B。除法 R \div S 的一种定义是：找到最大的关系集合 X，使得

X \times S \subset R.