第2章 关系数据库——2.4关系代数

2.4  关系代数

 

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

     运算对象、运算符、运算结果是运算的三大要素。

     关系代数的运算对象是关系，运算结果亦是关系。关系代数用到的运算符包括两类：集合运算符和专门的关系运算符，如下表所示。

表1  关系代数运算符

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

2.4.1  传统的集合运算

传统的集合运算是二目运算，包括并、差、交、笛卡儿积4种运算。

设关系R和关系S具有相同的目n（即两个关系都有n个属性），且相应的属性取自同一个域，t是元组变量，t∈R表示t是R的一个元组。

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

1、并（union）

2、差（except）

3、交（intersection）

4、笛卡儿积（cartesian product）

2.4.2  专门的关系运算

      专门的关系运算包括选择、投影、连接、除运算等。

01 选择（selection）

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

   其中F表示选择条件，它是一个逻辑表达式，取逻辑值“真”或“假”。

设有一个学生-课程数据库，包括学生关系Student、课程关系Course和选修关系SC，如下图3所示。下面的多个例子将对这三个关系进行运算。

图4  学生-课程数据库

例2.1  查询信息系（IS系）全体学生。

例2.2  查询年龄小于20岁的学生。

02 投影（projection）

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

     其中A是R中的属性列。

例2.3  查询学生的姓名和所在系，即求Student关系上学生姓名和所在系两个属性上的投影。

结果如图5所示。

图5  例2.3结果

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

结果如图6所示。

图6  例2.4结果

03 连接（join）

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

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

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

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

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

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

例2.5  设图7分别为关系R和关系S，图8为非等值连接 的结果，图9为等值连接 的结果，图10为自然连接 的结果。

图7  关系R和关系S

图8   的结果

图9  等值连接

图10  自然连接

     两个关系R和S在做自然连接时，选择两个关系在公共属性上值相等的元组构成新的关系。此时，关系R中某些元组有可能在S中不存在公共属性上值相等的元组，从而造成R中这些元组在操作时被舍弃了，同样，S中某些元组也可能被舍弃。这些被舍弃的元组称为悬浮元组（dangling tuple）。

     如果把悬浮元组也保存在结果关系中，也在其他属性上填空值（NULL），那么这种连接就叫作外连接（outer join）；如果只保留左边关系R中的悬浮元组就叫作左外连接（left outer join或left join）；如果只保留右边关系S中的悬浮元组就叫作右外连接（right outer join或right join）；

在下图11中，图（a）是图7中的关系R和关系S的外连接，图（b）是左外连接，图（c）是右外连接。

图11

04 除运算（division）

     设关系R除以关系S的结果为关系T，则T包含所有在R但不在S中的属性及其值，且T的元组与S的元组的所有组合都在R中。

下面用象集来定义除法：

    给定关系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中的象集， 。

例2.6  设关系R、S分别为图12中的(a)和(b)，R÷S的结果为图12中的(c)。

图12

例2.7  查询至少选修1号课程和3号课程的学生号码。

首先建立一个临时关系K：

然后求 ，最终结果为{201215121}。

例2.8查询选修了2号课程的学生的学号。

例2.9  查询至少选修了一门其直接先行课为5号课程的学生姓名。

或者：

例2.10  查询选修了全部课程的学生号码和姓名。

     本节介绍了8种关系代数运算，其中并、差、笛卡儿积、选择和投影这5种运算为基本的运算。其他三种运算，即交、连接和除，均可以用这5种基本运算来表达。

     关系代数中，这些运算经有限次复合后形成的表达式称为关系代数表达式。