3.2 关系代数
关系代数是一种抽象的查询语言，是关系数据操作语言的一种传统表达方式，它是用对关系的运算来表达查询的。由于关系代数是建立在集合代数的基础上，下面先定义几个关系术语中的数学定义。
3.2.1 关系的数学定义
1.域（Domain）
域是一组具有相同数据类型的值的集合。
例如，自然数、整数、实数、一个字符串、{男，女}、大于10小于等于90的正整数等都可以是域。
2.笛卡儿积（Certesian Product）
给定一组域D1，D2，…，Dn，这些域中可以有相同的。则D1，D2，…，Dn的笛卡儿积为
D1×D2×…×Dn={（d1，d2，…，dn）|di∈Dj，j=1，2，…，n}
其中，每一个元素（d1，d2，…，dn）叫作一个n元组或简称元组，元素中的每一个值di叫作一个分量。若Di（i=1，2，…，n）为有限集，其基数为mi（i=1，2，…，n），则D1×D2×…× Dn的基数为M：
笛卡儿积可以表示成一个二维表，表中的每行对应一个元组，表中的每列对应一个域。例如，给出三个域：
D1=姓名集合={欧阳宝贝，孙凯，唐晓}
D2=性别集合={男，女}
D3=专业集合={工商，商务}
D1×D2×D3={（欧阳宝贝，男，工商），（欧阳宝贝，男，商务），（欧阳宝贝，女，工商），（欧阳宝贝，女，商务），（孙凯，男，工商），（孙凯，男，商务），（孙凯，女，工商），（孙凯，女，商务），（唐晓，男，工商），（唐晓，男，商务），（唐晓，女，工商），（唐晓，女，商务）}，这12个元组可列成一张二维表，如表3-3所示。
表3-3 D1、D2、D3的笛卡儿积结果表
3.关系（Relation）
D1×D2×…×Dn的子集叫作在域D1，D2，…，Dn上的关系，表示为R（D1，D2，…，Dn）
这里R表示关系的名字，n是关系的目或度（Degree）。当n=1时，称该关系为单目关系（Unary relation）。当n=2时，称该关系为二目关系（Binary relation）。关系是笛卡儿积的有限子集，所以，关系也是一个二维表。
例如，可以在表3-3的笛卡儿积中取出一个子集来构造一个学生关系。由于一个学生只有一个专业和性别，所以，笛卡儿积中的许多元组在实际中是无意义的，仅仅挑出有实际意义的元组构建一个关系，该关系名为Student，字段名取域名：姓名，性别和专业，如表3-4所示。
表3-4 Student关系
3.2.2 关系代数概述
关系代数是一种抽象的查询语言，是关系数据操纵语言的一种传统表达方式，它是用对关系的运算来表达查询的。任何一种运算都是将一定的运算符作用于一定的运算对象上，得到预期的运算结果，所以，运算对象、运算符、运算结果是运算的三大要素。
关系代数的运算对象是关系，运算结果也是关系。
关系代数中使用的运算符包括四类：集合运算符、专门的关系运算符、比较运算符和逻辑运算符，如表3-5所示。
表3-5 关系代数运算符
关系代数的运算按运算符的不同可分为传统的集合运算和专门的关系运算两类。
传统的集合运算将关系看成元组的集合，其运算是从关系的“水平”方向即行的角度进行的。
专门的关系运算不仅涉及行而且涉及列。比较运算符和逻辑运算符是用来辅助专门的关系运算进行操作的。
3.2.3 传统的集合运算
传统的集合运算是二目运算，包括并、交、差、广义笛卡儿积4种运算。
设关系R和关系S具有相同的目n（即两个关系都具有n个属性），且相应的属性取自同一个域，则可以定义并、差、交、广义笛卡儿积运算如下。
1.并（Union）
关系R与关系S的并记作
R∪S={t|t∈R∨t∈S}，t是元组变量
其结果关系仍为n目关系，由属于R或属于S的元组组成。
2.差（Difference）
关系R与关系S的差记作
R-S={t|t∈R∧t∉S}，t是元组变量
其结果关系仍为n目关系，由属于R而不属于S的所有元组组成。
3.交（Intersection）
关系R与关系S的交记作
R∩S={t|t∈R∧t∈S}，t是元组变量
其结果关系仍为n目关系，由既属于R又属于S的元组组成。关系的交可以用差来表示，即R∩S=R-（R-S）
4.广义笛卡儿积（Extended Cartesian Product）
两个分别为n目和m目的关系R和S的广义笛卡儿积是一个（n+m）列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若R有k1个元组，S有k2个元组，则关系R和关系S的广义笛卡儿积有kl×k2个元组。记作：R×S={trts|Tr∈R∧Ts∈S}
3.2.4 专门的关系运算
专门的关系运算包括选择、投影、连接、除等。为了叙述上的方便，先引入几个记号。
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称为字段名或域列。t[A]=（t[Ai1]，t[Ai2]，…，t[Aik]）表示元组t在字段名A上诸分量的集合。A表示{A1，A2，…，An）中去掉{Ai1，Ai2，…，Aik}后剩余的属性组。
3）R为n目关系，S为m目关系。tr∈R，ts∈S，trts称为元组的连接，它是一个n+m列的元组，前n个分量为R中的一个n元组，后m个分量为S中的一个m元组。
4）给定一个关系R（X，Z），X和Z为属性组。定义当t[X]=x时，x在R中的象集为
Zx={t[Z]|t∈R，t[X]=x}
它表示R中属性组X上值为x的诸元组在Z上分量的集合。
下面给出这些关系运算的定义。
1.选择（Selection）
选择又称为限制（Restriction），它是在关系R中选择满足给定条件的诸元组，记作：σF（R）={t|t∈R∧F（t）=′真′}
其中，F表示选择条件，它是一个逻辑表达式，取逻辑值“真”或“假”。逻辑表达式F的基本形式为
X1θY1[ΦX2θY2…]
其中，θ表示比较运算符，它可以是＞、≥、＜、≤、=或≠；X1，Y1是字段名、常量或简单函数，字段名也可以用它的序号（如1，2，…）来代替；Φ表示逻辑运算符，它可以是┐（非）、∧（与）或∨（或）；[]表示任选项，即[]中的部分可要可不要；…表示上述格式可以重复下去。选择运算实际上是从关系R中选取使逻辑表达式F为真的元组，这是从行的角度进行的运算。
设有一个学生—课程数据库，如表3-6所示，它包括以下内容。
学生关系Student（说明：Sno表示学号，Sname表示姓名，Ssex表示性别，Sage表示年龄，Sdept表示所在系）
课程关系Course（说明：Cno表示课程号，Cname表示课程名）
选修关系Score（说明：Sno表示学号，Cno表示课程号，Degree表示成绩）
其关系模式如下：
Student（Sno，Sname，Ssex，Sage，Sdept）
Course（Cno，Cname）
Score（Sno，Cno，Degree）
表3-6 学生—课程关系数据库
【例3-4】查询数学系学生的信息。
σSdept=′数学系′（Student）或σ5=′数学系′（Student）
结果如表3-7所示。
表3-7 查询数学系学生的信息结果
【例3-5】查询年龄小于20岁的学生的信息。
σSage＜20（Student）或σ4＜20（Student）
结果如表3-8所示。
表3-8 查询年龄小于20岁的学生的信息结果
2.投影（Projection）
关系R上的投影是从R中选择若干字段名组成新的关系。记作：
πA（R）={t[A]|t∈R}
其中，A为R中的字段名。
投影操作是从列的角度进行的运算。投影之后不仅取消了原关系中的某些列，而且还可取消某些元组。因为取消了某些字段名后，就可能出现重复行，应取消这些完全相同的行。
【例3-6】查询学生的学号和姓名。
πSno，Sname（Student）或π1，2（Student）
结果如表3-9所示。
表3-9 查询学生的学号和姓名结果
【例3-7】查询学生关系Student中都有哪些系，即查询学生关系Student在所在系属性上的投影。
πSdept（Student）或π5（Student）
结果如表3-10所示。
表3-10 查询学生所在系结果
3.连接（Join）
连接也称为θ连接，它是从两个关系的笛卡儿积中选取属性间满足一定条件的元组。记作：
其中，A和B分别为R和S上度数相等且可比的属性组。θ是比较运算符。连接运算从R和S的笛卡儿积R×S中选取R关系在A属性组上的值与S关系在B属性组上值满足比较关系的θ元组。
连接运算中有两类最为重要也是最为常用连接运算。一种是等值连接（Equijoin），另一种是自然连接。
θ为“=”的连接运算称为等值连接。它是从关系R与S的广义笛卡儿积中选取A、B属性值相等的那些元组，即等值连接为
自然连接（Natural join）是一种特殊的等值连接。它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的字段名去掉。若R和S具有相同的属性组B，则自然连接可记作
一般的连接操作是从行的角度进行运算。但是自然连接还需要取消重复列，所以，是同时从行和列的角度进行运算。
如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值Null，那么这种连接就叫作外连接（Outer join）。如果只把左边关系R中要舍弃的元组保留就叫作左外连接（Left outer join或Left join），如果只把右边关系S中要舍弃的元组保留就叫作右外连接（Right outer join或Right join）。
【例3-8】设关系R、S分别为表3-11中的（a）和（b），一般连接C＜E的结果见表3-11（c），等值连接R.B=S.B的结果见表3-11（d），自然连接的结果见表3-11（e）。
表3-11 连接运算举例
4.除运算（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上投影的集合。
R÷S={tr[X]|tr∈R∧πY（S）⊆YS}
其中Yx为x在R中的象集，x=tr[X]。
除操作是同时从行和列角度进行运算的。
【例3-9】设关系R，S分别见表3-10（a）、（b），R÷S的结果见表3-10（c）。在关系R中，A可以取四个值{a1，a2，a3，a4}。其中：
a1的象集为{（b1，c2），（b2，c3），（b2，c1）}；
a2的象集为{（b3，c5），（b2，c3）}；
a3的象集为{（b4，c4）}；
a4的象集为{（b6，c4）}；
S在（B，C）上的投影为{（b1，c2），（b2，c3），（b2，c1）}。
显然只有a1的象集（B，C）a1包含S在（B，C）属性组上的投影，所以R÷S={a1}。
表3-12 除运算举例
在关系代数中，关系代数运算经过有限次复合后形成的式子称为关系代数表达式。对关系数据库中数据的查询操作可以写成一个关系代数表达式，或者说，写成一个关系代数表达式就表示已经完成了查询操作。以下给出利用关系代数进行查询的例子。
设学生—课程数据库中有三个关系。
学生关系：S（Sno，Sname，SSex，Sage）
课程关系：C（Cno，Cname，Teacher）
学习关系：SC（Sno，Cno，Degree）
1）查询学习课程号为C3号课程的学生学号和成绩。
πSno，Degree（σCno=′C3′（SC））
2）查询学习课程号为C4课程的学生学号和姓名。
πSno，Sname（σCno=′C4′（S▷◁SC））
3）查询学习课程名为maths的学生学号和姓名。
πSno，Sname（σCname=′maths′（S▷◁SC▷◁C））
4）查询学习课程号为C1或C3课程的学生学号。
πSno（σCno=′C1′∧Cno=′C2′（SC））
5）查询不学习课程号为C2的学生的姓名和年龄。
πSname，Sage（S）-πSname，Sage（σCno=′C2′′（S▷◁SC））