关系代数

1.概念：

​ 关系代数是一种抽象的查询语言，它用对关系的运算来表达查询。

​ 按运算符的不同分为传统的集合运算和专门的关系运算两类：
传统的集合运算包括：并（∪）、差（−）、交（∩）、笛卡尔积（×）。
专门的关系运算包括：选择（σ）、投影（π）、连接（⋈）、除运算（÷）。

关系代数

2.传统的集合运算：

传统的集合运算是二目运算，并（∪）、差（−）、交（∩）、笛卡尔积（×）四种运算。
设关系 R 和关系 S 具有相同的目 n（即两个关系都有 n 个属性），且相应的的属性取自同一个域，t 是元组变量，t∈R 表示 t 是 R 的一个元组。
下图分别是具有三个属性列的关系 R、S ：

R S

可以定义并、差、交、笛卡尔积运算如下：

2.1 并（union）

关系 R 与关系 S 的并由属于 R 且属于 S 的元组组成。其结果关系仍为 n 目关系。记作：

并公式

下图为关系 R 与关系 S 的并：

并数据集

2.2 差（except）

关系R与关系S的差由属于R而不属于S的所有元组组成。其结果关系仍为n目关系。记作：：

差公式

下图为关系 R 与关系 S 的差：

差数据集

2.3 交（intersection）

关系R与关系S的交由既属于R又属于S的元组组成。其结果关系仍为n目关系。记作：

交公式

下图为关系 R 与关系 S 的交：

交数据集

2.4 笛卡尔积（cartesian product）

这里的笛卡尔积严格地讲是广义笛卡尔积(Extended Cartesian Product)。在不会出现混淆的情况下广义笛卡尔积也称为笛卡尔积。
两个分别为n目和m目的关系R和S的广义笛卡尔积是一个(n+m)列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若R有k1个元组，S有k2个元组，则关系R和关系S的广义笛卡尔积有k1×k2个元组。
记作：

笛卡尔积公式

下图为关系 R 与关系 S 的笛卡尔积：

笛卡尔积数据集

3.专门的关系运算：

为了叙述上的方便，我们先引入几个记号。

1、设关系模式为R(A1, A2, …, An)。它的一个关系设为R。t∈R表示t是R的一个元组。t[Ai]则表示元组t中相应于属性Ai的一个分量 。
2、若A={Ai1, Ai2, …, Aik}，其中Ai1, Ai2, …, Aik是A1, A2, …, An中的一部分，则A称为属性列或域列。フA则表示{A1, A2, …, An}中去掉{Ai1, Ai2, …, Aik}后剩余的属性组。t[A]=(t[Ai1], t[Ai2], …, t[Aik])表示元组t在属性列A上诸分量的集合。
3、R为n目关系，S为m目关系。设tr∈R(r为下标)，ts∈S(s为下标)，则trts(整个式子上方加一个半弧，r和s为下标) 称为元组的连接（Concatenation）。它是一个(n+m)列的元组，前n个分量为R中的一个n元组，后m个分量为S中的一个m元组。
4、给定一个关系R(X,Z)，X和Z为属性组。我们定义，当t[X]=x时，x在R中的象集（Images Set）为：

笛卡尔积数据集

3.1 选择（selection）

选择又称为限制（Restriction）。它是在关系R中选择满足给定条件的诸元组，记作：

选择公式
其中F表示选择条件，它是一个逻辑表达式，取逻辑值‘真’或‘假’。
逻辑表达式F的基本形式为：
选择公式
θ表示比较运算符，它可以是>、≥、<、≤、=或<>。X1、Y1等是属性名或常量或简单函数。属性名也可以用它的序号来代替。φ表示逻辑运算符，它可以是非（┓）、与（∧）、或（∨）。[ ]表示任选项，即[ ]中的部分可以要也可以不要，...表示上述格式可以重复下去。
选择运算实际上是从关系R中选取使得逻辑表达是F为真的组。这是从行的角度进行的运算。
条件表达式中的运算符如表所示：
选择公式


【例】设有一个学生-课程数据库，包括学生关系Student、课程关系Course和选修关系SC。如图所示：
选择公式


【例】查询信息系（IS系）全体学生：

select * from Student where Sdept = 'IS'

选择公式


【例】查询年龄小于20岁的学生：

select  * from Student where Sage > 20

选择公式

3.2 投影（projection）

关系R上的投影是从R中选择出若干属性列组成新的关系。记作：

选择公式

其中A为R中的属性列。投影操作是从列的角度进行运算。
【例】 查询学生的姓名和所在系，即求Student关系上学生姓名和所在系两个属性上的投影：

选择公式

select  Student.Sname,Student.Sdept from Student

结果如下图所示，投影之后不仅取消了原关系的某些列，而且还可能取消某些元祖，因为取消了某些属性之后，就可能出现重复行，应取消这些完全相同的行。

选择公式


【例】查询学生关系Student中都有那些系，即查询关系Student上所在系属性上的投影：

select Student.Sdept from Student

结果如下图所示，Student关系原来有4个元组，而投影结果取消了重复的CS元组，因此只有三个元组：

选择公式

3.3 除（division）

除法运算是一个复合的二目运算。如果把笛卡尔积看作“乘法”运算，则除法运算可以看作这个“乘法”的逆运算。
给定关系R(X，Y)和S(Y，Z)，其中X、Y、Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除运算得到一个新的关系P(X)，P是R中满足下列条件的元组在X属性列上的投影：元组在X上的分量值x的像集YX包含S在Y上投影的集合。记作：

选择公式
其中，为x在R中的像集，x= [X]。显然，除操作是同时从行和列的角度进行运算。
根据关系运算的除法定义，可以得出它的运算步骤。
(1) 将被除关系的属性分为像集属性和结果属性两部分；与除关系相同的属性属于像集属性；不相同的属性属于结果属性。
(2) 在除关系中，对像集属性投影，得到除目标数据集。
(3) 将被除关系分组。分组原则是：结果属性值一样的元组分为一组。
(4) 逐一考察每个组，如果它的像集属性值中包括目标数据集，则对应的结果属性应属于该除法运算结果集。

【例】在关系R中，A可以去4个值{a1，a2，a3，a4}，其中：
a1的象集为{（b1，c2），（b2，c3），（b2，c1）}；
a2的象集为{（b3，c7），（b2，c3）}；
a3的象集为{（b4，c6）}；
a4的象集为{（b6，c6）}；
S在（B，C）上的投影为{（b1，c2），（b2，c1），（b2，c3）}；
显然只有a1的象集包含了S在（B，C）属性组上的投影，所以 R÷S = { a1 }。

选择公式

3.4 连接（join）

连接也称为θ连接，关系R与关系S的连接运算是从两个关系的广义笛卡尔积中选取属性间满足一定条件的元组形成一个新的连接：

选择公式
其中：
A为包含R中的属性的表达式；
B为包含S中的属性的表达式；
θ通常为关系比较符。

3.4.1 等值连接（equi join）

θ在“=”时的连接为等值连接。它是从关系R和S的广义笛卡尔积中选取A、B属性值相等的那些元组，即等值连接为：

选择公式

3.4.2 自然连接（natural join）

自然连接是一种特殊的等值链接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把属性重复的列去掉。即若R和S中具有相同的属性组B，U为R和S的全体属性集合，则自然连接可记作：

选择公式


一般的连接操作是从行的角度进行运算，但自然连接还需取消重复列，所以是同时从行和列的角度进行运算。


【例】设图中（a）和（b）分别是关系R和关系S，图中（c）为非等值连接的结果，图（d）为等值连接的结果，图（e）为自然连接的结果：
选择公式

3.4.3 左连接（left join）

在自然连接的基础上加上左边表上不包含自然连接中所含元组（行）的元组。

select * from R left join S

选择公式

3.4.4 右连接（right join）

在自然连接的基础上加上右边表上不包含自然连接中所含元组（行）的元组。

select * from R right join S

选择公式

3.4.5 外连接（outer join）

外连接=左连接 并 右连接；

select * from R outer join S

选择公式

4.MySQL中实现关系除法

哪个司机会开所有类型的车？这便是一个关系除法问题。

表drivers有两个字段，司机的名字和司机会开的车的id：

CREATE TABLE `drivers` (
  `driver_name` char(10) DEFAULT NULL,
  `vehicle_id` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

表vehicles只有一个字段，即车的id：

CREATE TABLE `vehicles` (
  `id` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

使用关系除法的方案，sql为：

SELECT DISTINCT D1.driver_name
    FROM drivers AS D1
WHERE NOT EXISTS
            (SELECT * FROM vehicles AS V1
                WHERE NOT EXISTS
                (
                    SELECT * FROM drivers AS D2
                    WHERE D1.driver_name = D2.driver_name
                        AND D2.vehicle_id = V1.id
                )
            );

参考：

MySQL：关系除法
MySQL基础 -- 关系代数