3.1 关系代数及其运算

关系代数是一种抽象的查询语言，是关系数据操作语言的一种传统表达方式，它是用关系的运算来表达查询的。

关系数据库的数据操作分为查询和更新两类。查询用于各种检索操作，更新用于插入、删除和修改等操作。关系操作的特点是集合操作方式，即操作的对象和结构都是集合。关系模型中常用的关系操作包括选择（SELECT）、投影（PROJECT）、连接（JOIN）、除（DIVIDE）、并（UNION）、交（INTERSECTION）、差（DIFFERENCE）等。

早期的关系操作能力通常用代数方式或逻辑方式来表示，关系查询语言根据其理论基础的不同分成两大类。

1）关系代数语言：用关系的运算来表达查询要求的方式，查询操作是以集合操作为基础运算的DML语言。

2）关系演算语言：用谓词来表达查询要求的方式，查询操作是以谓词演算为基础运算的DML语言。关系演算又可按谓词变元的基本对象是元组变量还是域变量分为元组关系演算和域关系演算。

关系代数、元组关系演算和域关系演算三种语言在表达能力方面是完全等价的。

由于关系代数是建立在集合代数的基础上，下面先定义几个关系术语中的数学定义。

3.1.1 关系的数学定义

1．域（Domain）

域是一组具有相同数据类型值的集合。在关系模型中，使用域来表示实体属性的取值范围，通常用D_i表示某个域。

例如，自然数、整数、实数、一个字符串、{男，女}，大于10小于等于90的正整数等都可以是域。

2．笛卡儿积（Cartesian Product）

给定一组域D_l，D₂，…，D_n，这些域中可以有相同的，则D_l，D₂，…，D_n的笛卡儿积为：

D_l×D₂×…×D_n={（d₁，d₂，…，d_n）|d_i∈D_j，j=1，2，…，n}

其中每一个元素（d₁，d₂，…，d_n）叫作一个n元组或简称元组，元素中的每一个值d_i叫作一个分量。若D_i（i=1，2，…，n）为有限集，其基数（基数是指一个域中可以取值的个数。）为m_i（i=1，2，…，n），则D_l×D₂×…×D_n的基数为：

笛卡儿积可以表示成一个二维表，表中的每行对应一个元组，表中的每列对应一个域。例如，给出3个域：

姓名集合：D₁={史丹妮，周冬元，李晓辉}

性别集合：D₂={男，女}

专业集合：D₃={会计，商务}

D₁×D₂×D₃={（史丹妮，男，会计），（史丹妮，男，商务），（史丹妮，女，会计），（史丹妮，女，商务），（周冬元，男，会计），（周冬元，男，商务），（周冬元，女，会计），（周冬元，女，商务），（李晓辉，男，会计），（李晓辉，男，商务），（李晓辉，女，会计），（李晓辉，女，商务）}，这12个元组可列成一张二维表，如表3-1所示。

3．关系（Relation）

D_l×D₂×…×D_n的子集叫作在域D_l，D₂，…，D_n上的关系，表示为R（D_l，D₂，…，D_n）。

这里R表示关系的名字，n是关系属性的个数，称为目数或度数（Degree）；

当n=1时，称该关系为单目关系（Unary relation）；

当n=2时，称该关系为二目关系（Binary relation）。

关系是笛卡儿积的有限子集，所以关系也是一个二维表。

例如，可以在表3-1的笛卡儿积中取出一个子集来构造一个学生关系。由于一个学生只有一个专业和性别，所以笛卡儿积中的许多元组在实际中是无意义的，仅仅挑出有实际意义的元组构建一个关系，该关系名为Student，字段名取域名：姓名、性别和专业，如表3-2所示。

3.1.2 关系代数概述

关系代数是一种抽象的查询语言，是关系数据操纵语言的一种传统表达方式，它是用对关系的运算来表达查询的。任何一种运算都是将一定的运算符作用于一定的运算对象上，得到预期的运算结果，所以运算对象、运算符、运算结果是运算的三大要素。

关系代数的运算对象是关系，运算结果亦为关系。

关系代数中使用的运算符包括4类：集合运算符、专门的关系运算符、比较运算符和逻辑运算符，如表3-3所示。

关系代数的运算按运算符的不同可分为传统的集合运算和专门的关系运算两类。

传统的集合运算将关系看成元组的集合，其运算是从关系的“水平”方向即行的角度进行的。

专门的关系运算不仅涉及行而且涉及列。比较运算符和逻辑运算符是用来辅助专门的关系运算进行操作的。

3.1.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有k₁个元组，S有k₂个元组，则关系R和关系S的广义笛卡儿积有k_l×k₂个元组。记作：R×S={t_r⌒∩t_s|T_r∈R∧T_s∈S}

假定现在有两个关系R与S是关系模式学生的实例，R和S如表3-4所示。

【例3-1】关系R∪S的结果如表3-5所示。

【例3-2】关系R-S的结果如表3-6所示。

【例3-3】关系R∩S的结果如表3-7所示。

【例3-4】关系R与关系S做广义笛卡尔积的结果如表3-8所示。

3.1.4 专门的关系运算

专门的关系运算包括选择、投影、连接、除等。为了叙述上的方便，先引入几个符号。

1）设关系模式为R（A₁，A₂，…，A_n），它的一个关系设为R，t∈R表示t是R的一个元组，t[A_i]表示元组t中相应于属性A_i上的一个分量。

2）若A={A_i1，A_i2，…，A_ik}，其中A_i1，A_i2，…，A_ik是A₁，A₂，…，A_n中的一部分，则A称为字段名或域列。t[A]=（t[A_i1]，t[A_i2]，…，t[A_ik]）表示元组t在字段名A上诸分量的集合。A表示{A₁，A₂，…，An）中去掉{A_i1，A_i2，…，A_ik}后剩余的属性组。

3）R为n目关系，S为m目关系。t_r∈R，t_s∈S，t_r⌒t_s称为元组的连接，它是一个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的基本形式为：

X₁θY₁[ΦX₂θY₂…]

其中，θ表示比较运算符，它可以是＞、≥、＜、≤、=或≠；X1，Y1是字段名、常量或简单函数，字段名也可以用它的序号（如1，2，…）来代替；Φ表示逻辑运算符，它可以是¬（非）、∧（与）或∨（或）；[ ]表示任选项，即[ ]中的部分可要可不要；…表示上述格式可以重复下去。选择运算实际上是从关系R中选取使逻辑表达式F为真的元组，这是从行的角度进行的运算。

设有一个学生-课程数据库如表3-9所示，它包括以下内容。

学生关系Student（说明：Sno表示学号，Sname表示姓名，Ssex表示性别，Sage表示年龄，Sdept表示所在系）

课程关系Course（说明：Cno表示课程号，Cname表示课程名）

选修关系Score（说明：Sno表示学号，Cno表示课程号，Degree表示成绩）

其关系模式如下。

【例3-5】查询数学系学生的信息。

σ_{Sdept=′数学系′}（Student）或σ_{5=′数学系′}（Student）

结果如表3-10所示。

【例3-6】查询年龄小于20岁的学生的信息。

σ_Sage＜20（Student）或σ_4＜20（Student）

结果如表3-11所示。

2．投影（Projection）

关系R上的投影是从R中选择出若干字段名组成新的关系。记作：

π_A（R）={t[A]|t∈R}

其中A为R中的字段名。

投影操作是从列的角度进行的运算。投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组。因为取消了某些字段名后，就可能出现重复行，应取消这些完全相同的行。

【例3-7】查询学生的学号和姓名。

π_Sno,Sname（Student）或π_1,2（Student）

结果如表3-12所示。

【例3-8】查询学生关系Student中都有哪些系，即查询学生关系Student在所在系属性上的投影。

π_Sdept（Student）或π₅（Student）

结果如表3-13所示。

3．连接（Join）

连接也称为θ连接，它是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。记作：

其中A和B分别为R和S上度数相等且可比的属性组。θ是比较运算符。连接运算从R和S的笛卡尔积R×S中选取R关系在A属性组上的值与S关系在B属性组上值满足比较关系的θ元组。

连接运算中有两类最为重要，也是最为常用连接运算。一种是等值连接（Equijoin），另一种是自然连接。

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

自然连接（Natural join）是一种特殊的等值连接。它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的字段名去掉。若R和S具有相同的属性组B，则自然连接可记作

R▷◁S{t_r⌒t_s|t_r∈R∧t_s∈S∧t_r[A]θt_s[B]}

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

如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值Null，那么这种连接就叫作外连接（Outer join）。如果只把左边关系R中要舍弃的元组保留就叫作左外连接（Left outer join或Left join），如果只把右边关系S中要舍弃的元组保留就叫作右外连接（Right outer join或Right join）。

【例3-9】设关系R、S分别为表3-14中的（a）和（b），一般连接C＞D的结果如表3-15（a）所示，等值连接R. B=S. B的结果如表3-15（b）所示，自然连接的结果如表3-15（c）所示。

4．除运算（Division）

给定关系R（X，Y）和S（Y，Z），其中X，Y，Z为属性组。R中的Y与S中的Y可以有不同的字段名，但必须出自相同的域集。R与S的除运算得到一个新的关系P（X），P是R中满足下列条件的元组在X字段名上的投影：元组在X上分量值x的象集Y_x包含S在Y上投影的集合。

R÷S={t_r[X]t_r∈R∧π_Y（S）⊆Y_X}

其中Y_x为x在R中的象集，x=t_r[X]。

除操作是同时从行和列角度进行运算的。

关系除法运算分下面4步进行。

1）将被除关系的属性分为象集属性和结果属性：与除关系相同的属性属于象集属性，不相同的属性属于结果属性。

2）在除关系中，对与被除关系相同的属性（象集属性）进行投影，得到除目标数据集。

3）将被除关系分组，原则是，结果属性值一样的元组分为一组。

4）逐一考察每个组，如果它的象集属性值中包括除目标数据集，则对应的结果属性值应属于该除法运算结果集。

说明：象集的本质是一次选择运算和一次投影运算。

例如关系模式R（X，Y），X和Y表示互为补集的两个属性集，对于遵循模式R的某个关系A，当t[X]=x时，x在A中的象集（Images Set）为：

Zx={t[Z]|t∈ A，t[X]=x}

它表示：A中X分量等于x的元组集合在属性集Z上的投影，如表3-16所示。

a1在A中的象集为{（b1，c2），（b2，c3），（b2，c1）}。

【例3-10】设关系R，S分别如表3-17（a）、（b）所示，求R÷S的结果。

关系除的运算过程如下。

1）找出关系R和关系S中的相同属性，即B属性和C属性。在关系S中对B属性和C属性做投影，所得的结果为{（b1，c2），（b2，c3），（b2，c1）}。

2）被除关系R中与S中不相同的属性列是A，在关系R在属性A上做取消重复值的投影为{a1，a2，a3，a4}。

3）求关系R中A属性对应的象集对应的象集B和C，根据关系R的数据，可以得到A属性各分量值的象集。

其中：

a1的象集为{（b1，c2），（b2，c3），（b2，c1）}；

a2的象集为{（b3，c5），（b2，c3）}；

a3的象集为{（b4，c4）}；

a4的象集为{（b6，c4）}。

4）判断包含关系，对比可以发现：a2、a3和a3的象集都不能包含关系S中的B属性和C属性的所有值，所以排除掉a2、a3和a3；而a1的象集包括了关系S中B属性和C属性的所有值，所以R÷S的最终结果就是{a1}。

在关系代数中，关系代数运算经过有限次复合后形成的式子称为关系代数表达式。对关系数据库中数据的查询操作可以写成一个关系代数表达式，或者说，写成一个关系代数表达式就表示已经完成了查询操作。

【例3-11】假设有两个关系：学生学习成绩与课程成绩，如表3-18所示，则学生学习成绩与课程成绩除运算的结果是满足一定课程成绩条件的学生的表，结果如表3-19所示。

【例3-12】设学生-课程数据库中有3个关系：S、C和SC，三个关系的关系实例分别如表3-20所示。利用关系代数进行查询。

学生关系：S（sno，sname，ssex，sage，sdept）

课程关系：C（cno，cname，teacher）

选修关系：SC（sno，cno，degree）

属性sno、sname、ssex、sage和sdept分别表示学号、姓名、性别、年龄和所在系，sno为主码，属性cno、cname、Teacher分别表示课程号、课程名、授课教师，cno为主码，属性sno、cno、degree分别表示学号、课程号和成绩，（sno，cno）属性组为主码。

1）查询选修课程号为C3号课程的学生学号和成绩。

π_Sno,Degree（σ_Cno=′C3′（SC））

2）查询学习课程号为C4课程的学生学号和姓名。

π_Sno,Sname（σ_Cno=′C4′（S∞SC））

3）查询选修课程名为数据结构的学生学号和姓名。

π_sno,sname（σ_{cname=′数据结构′}（S▷◁SC▷◁C））

4）查询选修课程号为C1或C3课程的学生学号。

π_Sno（σ_{Cno=′C1′∨Cno=′C3′}（SC））

5）查询不选修课程号为C2的学生的姓名和年龄。

π_{Sname,Sage（S）}-π_Sname,Sage（σ_Cno=′C2′（S▷◁SC））

6）查询年龄在18～23岁之间的女生的学号、姓名和年龄。

π_{sno,sname,sage}（σ_{sage＞=18∧sage＜=23∧ssex=′女′}（S））

7）查询至少选修课程号为C1与C5的学生的学号。

π_sno（σ_{1=4∧3=′C1′∧5=′C5′}（SC×SC））

8）查询选修全部课程的学生的学号。

π_sno,cno（SC）÷π_cno（C）

9）查询全部学生都选修的课程的课程号。

π_sno,cno（SC）÷π_sno（S）

10）查询选修课程包含学生李飞所学课程的学生的姓名。

π_sname（S▷◁（π_sno,cno（SC）÷π_cno（σ_{sname=′李飞′}（S）▷◁SC）））

11）查询选修了操作系统或软件工程的学生学号和姓名。

π_sno,sname（σ_{cname=′操作系统′∨cname=′软件工程′}（C▷◁SC▷◁S））