3.5 关系代数
关系模型源于数学。关系是由元组构成的集合，可以通过关系的运算来表达查询要求，而关系代数恰恰是关系操作语言的一种传统的表示方式，它是一种抽象的查询语言。
关系代数的运算对象是关系，运算结果也是关系。与一般的运算一样，运算对象、运算符和运算结果是关系代数的三大要素。
关系代数的运算可分为两大类：
传统的集合运算。这类运算完全把关系看成元组的集合。传统的集合运算包括集合的广义笛卡儿积运算、并运算、交运算和差运算。
专门的关系运算。这类运算除了把关系看成元组的集合外，还通过运算表达了查询的要求。专门的关系运算包括选择、投影、连接和除运算。
关系代数中的运算符可以分为四类：传统的集合运算符、专门的关系运算符、比较运算符和逻辑运算符。表3-9列出了这些运算符，其中比较运算符和逻辑运算符是配合专门的关系运算符来构造表达式的。
3.5.1 传统的集合运算
传统的集合运算是二目运算，设关系R和S均是n元关系，且相应的属性值取自同一个值域，则可以定义三种运算：并运算（∪）、交运算（∩）和差运算（-），但广义笛卡儿积并不要求参与运算的两个关系的对应属性取自相同的域。并、交、差运算的功能示意图如图3-5所示。
现在我们以图3-6a和图3-6b所示的两个关系为例，说明这三种传统的集合运算功能。
1.?并运算
关系R与关系S的并记为：
R∪S = {t | t∈R ∨ t∈S}
其结果仍是n目关系，由属于R或属于S的元组组成。
图3-7a显示了图3-6a和图3-6b两个关系的并运算结果。
2.?交运算
关系R与关系S的交记为：
R∩S = {t | t∈R ∧ t∈S }
其结果仍是n目关系，由属于R并且也属于S的元组组成。
图3-7b显示了图3-6a和图3-6b两个关系的交运算结果。
3.?差运算
关系R与关系S的差记为：
R - S = {t | t∈R ∧ t∈S }
其结果仍是n目关系，由属于R并且也属于S的元组组成。
图3-7c显示了图3-6a和图3-6b两个关系的交运算结果。
4.?广义笛卡儿积
广义笛卡儿积不要求参加运算的两个关系具有相同的目。
两个分别为m目和n目的关系R和关系S的广义笛卡儿积是一个（m＋n）目的元组的集合。元组的前m个列是关系R的一个元组，后n个列是关系S的一个元组。若R有K1个元组，S有K2个元组，则关系R和关系S的广义笛卡儿积有K1×K2个元组，记作：
R×S = { tr ^ ts | tr∈R ∧ ts∈S }
tr ^ ts表示由两个元组tr和ts前后有序连接而成的一个元组。
任取元组tr和ts，当且仅当tr属于R且ts属于S时，tr和ts的有序连接即为R×S的一个元组。
实际操作时，可从R的第一个元组开始，依次与S的每一个元组组合，然后，对R的下一个元组进行同样的操作，直至R的最后一个元组也进行同样的操作为止，即可得到R×S的全部元组。
图3-8所示为广义笛卡儿积的操作示意。
3.5.2 专门的关系运算
专门的关系运算包括投影、选择、连接和除等操作，其中选择和投影为一元操作，连接和除为二元操作。
下面我们以表3-10～表3-12所示的三个关系为例，介绍专门的关系运算。各关系包含的属性含义如下。
Student：Sno（学号），Sname（姓名），Ssex（性别），Sage（年龄），Sdept（所在系）。
Course：Cno（课程号），Cname（课程名），Credit（学分），Semester（开课学期）。
SC：Sno（学号），Cno（课程号），Grade（成绩）。
1.?选择
选择（selection）运算是最简单的运算，它从指定的关系中选择某些元组形成一个新的关系，被选择的元组是满足指定的逻辑条件的。
选择运算表示为：
σF (R) ={ t | t∈R ∧ F（t）= ‘真’ }
其中，σ是选择运算符，R是关系名，t是元组，F是逻辑表达式，取逻辑“真”值或“假”值。
例3-4 查询计算机系的学生信息。
σSdept = ‘计算机系’（Student）
结果如图3-9所示。
2.?投影
投影（projection）运算是对指定的关系进行垂直方向的选择，并形成一个新的关系。该操作包括如下两个过程：
1）选择指定的属性，形成一个可能含有重复行的关系。
2）删除重复行，形成新的关系。
投影运算表示为：
∏ A （R） = { t.A | t∈R }
其中，∏是投影运算符，R是关系名，A是被投影的属性或属性组。t.A表示t这个元组中对应属性（集）A的分量，也可以表示为t [A]。
例3-5 查询学生的姓名和所在系。
∏Sname, Sdept（Student）
结果如图3-10所示。
3.?连接
连接运算用来连接相互之间有联系的两个关系，从而产生一个新的关系。这个过程由连接属性（字段）来实现。一般情况下这个连接属性是出现在不同关系中的语义相同的属性。
连接运算也称为θ运算。连接运算一般表示为：
其中A和B分别是关系R和S上语义相同的属性或属性组，θ是比较运算符。连接运算从R和S的广义笛卡儿积R×S中选择（R关系）在A属性组上的值与（S关系）在B属性组上值满足比较运算符θ的元组。
连接运算中最重要也是最常用的连接有两个，一个是等值连接，一个是自然连接。
当θ为“=”时的连接为等值连接，它是从关系R与关系S的广义笛卡儿积中选取A、B属性值相等的那些元组，即：
自然连接是一种特殊的连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中要去掉重复的属性列。即，若关系R和S具有相同的属性组B，则自然连接可记作：
一般的连接运算是从行的角度进行运算，但自然连接还需要去掉重复的列，所以是同时从行和列的角度进行运算。
自然连接与等值连接的差别为：
自然连接要求相等的分量必须有共同的属性名，等值连接则不要求。
自然连接要求把重复的属性名去掉，等值连接却不这样做。
例3-6 对表3-10和表3-12所示的Student和SC关系，分别进行如下的等值连接和自然连接运算。
等值连接：
自然连接：
等值连接的结果如图3-11所示，自然连接的结果如图3-12所示。
4.?除
1）除（division）运算的简单描述。
设关系S的属性是关系R的属性的一部分，则R÷S为这样一个关系：
此关系的属性是由属于R但不属于S的所有属性组成。
R÷S的任一元组都是R中某元组的一部分。但必须符合下列要求，即任取属于R÷S的一个元组t，则t与S的任一元组连接后，都为R中原有的一个元组。
除运算的示意图如图3-13所示。
2）除运算的一般形式。设有关系R（X，Y）和S（Y，Z），其中X、Y、Z为关系的属性组，则：
R（X，Y） ÷S（Y，Z） = R（X，Y） ÷ ∏Y （S）
3）关系的除运算是关系运算中最复杂的一种，关系R与S的除运算的以上叙述解决了R÷S关系的属性组成及其元组应满足的条件要求，但怎样确定R÷S的元组仍然没有说清楚。为了说清楚这个问题，首先引入象集的概念。
象集（image set）：给定一个关系R（X，Y），X和Y为属性组。定义，当t［X］ = x时，x在R中的象集为：
Yx ={t[Y] | t∈R∧t[X] = x}
上式中：t [Y]和t [X]分别表示R中的元组t在属性组Y和X上的分量的集合。
例如在表3-10所示的Student关系中，有一个元组值为：
（0521101，张立，男，22，信息系）
假设X = ｛Sdept，Ssex｝，Y = ｛Sno，Sname，Sage｝，则上式中的t[X]的一个值
x = （信息系，男）
此时，Yx为t［X］ = x = （信息系，男）时所有t[Y]的值，即：
Yx = { （0521101，张立，22），（0521103，张海，20） }
也就是由信息系全体男生的学号、姓名、年龄所构成的集合。
又例如，对于表3-12所示的SC关系，如果设X = {Sno}，Y = {Cno，Grade}，则当X取“0512101”时，Y的象集为：
Yx = { （C01，90），（C02，86） }
当X取“0521102”时，Y的象集为：
Yx = {（C01，82），（C02，75），（C04，92），（C05，50）}
现在，我们再回过头来讨论除法的一般形式。
设有关系R （X，Y）和S （Y，Z），其中X、Y、Z为关系的属性组，则：
R÷S = {tr [X] | tr∈R ∧ ∏Y （S） Yx}
图3-14给出了一个除运算的示例。
图3-14所示的除结果为至少选了“C01”和“C02”两门课程的学生的学号。
下面以表3-10～表3-12所示的Student、Course和SC关系为例，给出一些关系代数运算的综合例子。
例3-7 查询选了C02号课程的学生的学号和成绩。
∏Sno, Grade （σCno=‘C02’ （SC））
运算结果如图3-15所示。
例3-8 查询信息系选了C04号课程的学生的姓名和成绩。
由于学生姓名信息在Student关系中，而成绩信息在SC关系中，因此这个查询同时涉及Student和SC两个关系。因此首先应对这两个关系进行自然连接，得到同一位学生的有关信息，然后再对连接的结果执行选择和投影操作。具体如下：
∏Sname, Grade（σCno=‘C04’∧Sdept=‘信息系’（SC Student））
也可以写成：
∏Sname, Grade（σCno=‘C04‘（SC） σSdept=‘信息系‘（Student））
后一种实现形式是首先在SC关系中查询出选了“C04”课程的集合，然后从Student关系中查询出“信息系”学生的集合，最后再对这个集合进行自然连接运算（Sno相等），这种查询的执行效率会比第一种形式高。
运算结果如图3-16所示。
例3-9 查询选了第2学期开设的课程的学生的姓名、所在系和所选的课程号。
这个查询的查询条件和查询列与两个关系有关：Student（包含姓名和所在系信息）以及Course（包含课程号和开课学期信息）。但由于Student关系和Course关系之间没有可以进行连接的属性（要求必须语义相同），因此，如果要让Student关系和Course关系进行连接，则必须要借助于SC关系，通过SC关系中的Sno与Student关系中的Sno进行自然连接，并通过SC关系中的Cno与Course关系中的Cno进行自然连接，可实现Student关系和Course关系之间的关联关系。
该示例的关系代数表达式如下：
∏Sname, Sdept, Cno（σSemester=2（Course SC Student））
也可以写成：
∏Sname, Sdept, Cno（σSemester=2（Course） SC Student）
运算结果如图3-17所示。
例3-10 查询选了“VB”课程且考试成绩大于等于80的学生姓名、所在系和成绩。
这个查询涉及Student、SC和Course三个关系，在Course关系中可以指定课程名，从Student关系中可以得到姓名、所在系，从SC关系中可以得到成绩。
该示例的关系代数表达式如下：
∏Sname, Sdept, Grade（σCname=‘VB’ ∧ Grade>=80（Course SC Student））
也可以写成：
∏Sname, Sdept, Grade（σCname=‘VB’（Course） σGrade>=80（SC） Student）
运算结果如图3-18所示。
例3-11 在全体学生中查询未选“计算机文化学”的学生姓名和所在系。
实现这个查询的关系代数表达式的基本思路是：从全体学生中去掉选了“计算机文化学”课程的学生，因此需要用到差运算。这个查询同样涉及Student、SC和Course三个关系。
该示例的关系代数表达式如下：
∏Sname, Sdept（Student）- ∏Sname, Sdept（σCname=‘计算机文化学’（Course SC Student））
也可以写成：
∏Sname, Sdept（Student）- ∏Sname, Sdept（σCname=‘计算机文化学’（Course） SC Student）
运算结果如图3-19所示。
图3-12 查询选了全部课程的学生的姓名和所在系。
编写实现这个查询的关系代数表达式的思考过程如下：
1）学生选课情况可用∏Sno,Cno(SC)表示。
2）全部课程可用∏Cno(Course)表示。
3）查询选了全部课程的学生的学号，可用除法运算得到，即：
∏Sno,Ono (SC) ÷∏Cno (Course)
4）从得到的Sno集合再在Student关系中找到对应的学生姓名（Sname）和所在系（Sdept），可用自然连接和投影操作组合实现。最终的关系代数表达式如下：
∏Sname, Sdept(Student (∏Sno,Cno (SC) ÷∏Cno (Course)))
运算结果为空集合。
例3-13 查询信息系选了第2学期开设的全部课程的学生的学号和姓名。
编写实现这个查询的关系代数表达式的思考过程与例3-12类似，只是将2）改为“查询第2学期开设的全部课程”，这可用下列表达式表达：
∏Cno (σSemester=2(Course)
最终的关系代数表达式为：
∏Sno, Sname（σSdept=‘信息系’（Student） （∏ Sno,Cno (SC) ÷ ∏Cno（σSemester=2（Course））））
运算结果如图3-20所示。
3.5.3 关系代数操作总结
表3-13对关系代数操作进行了总结。
关系运算的优先级按从高到低的顺序为：投影、选择、笛卡儿乘积、连接和除（同级）、交、并和差（同级）。