关系代数
关系数据库语言的分类
- 关系代数语言
- 关系演算语言:用谓词来表达查询要求
- 元组关系演算语言
- 谓词变元的基本对象是元组变量
- 代表:APLHA, QUEL
- 域关系演算语言
- 具有关系代数和关系演算双重特点的语言
- 代表:SQL(Structured Query Language)
关系代数的定义
- 关系代数是一种抽象的查询语言,它用对关系的运算来表达查询
- 运算对象是关系
- 运算结果亦为关系
- 关系代数的运算符有两类:集合运算符和专门的关系运算符
关系代数--传统的集合运算
符号约定
设关系模式为:
- 它们的一个关系设为
- 表示 是 的一个元组
- 表示元组 中相应于属性 的一个分量
- ,,,,其中 ,,, 是 中的一部分, 称为属性列或属性组
- 表示元组 在属性列 上的诸分量的集合
- 表示 中去掉 后剩余的属性组
为目关系,为目关系
,, 称为元组的连接
是一个 列的元组,前 个分量为 中的一个 元组,后 个分量为中的一个元组
象集
给定一个关系(,),和为属性组。
当时,在中的象集(Images Set)为:
$$
Z_x = { t[Z]|t \in R, t[X]=x}
$$
表示 $ R $ 中属性组 $ X $ 上值为 $ x $ 的诸元组在 $ Z $ 上分量的集合
并 (Union)
和
- 具有相同的目(即两个关系都有个属性)
- 相应的属性取自同一个域
- 仍为目关系,由属于或属于的元组组成
$$
R∪S = { t|t ∈ R∨t ∈S }
$$
例 2.1
A | B | C |
a1 | b1 | c1 |
a1 | b2 | c2 |
a2 | b2 | c1 |
A | B | C |
a1 | b2 | c2 |
a1 | b3 | c2 |
a2 | b2 | c1 |
A | B | C |
a1 | b1 | c1 |
a1 | b2 | c2 |
a2 | b2 | c1 |
a1 | b3 | c2 |
一般会去除重复的元素
差
和
- 具有相同的目(即两个关系都有个属性)
- 相应的属性取自同一个域
- 仍为 目关系,由属于而不属于的所有元组组成
$$
R -S = { t|t∈R∧t∉S }
$$
例 2.2
:
A | B | C |
a1 | b1 | c1 |
a1 | b2 | c2 |
a2 | b2 | c1 |
:
A | B | C |
a1 | b2 | c2 |
a1 | b3 | c2 |
a2 | b2 | c1 |
:
交(Intersection)
和
- 仍为目关系,由既属于又属于的元组组成
$$
R∩S = { t|t ∈ R∧t ∈S } \
R∩S = R -(R-S)
$$
例 2.3
:
A | B | C |
a1 | b1 | c1 |
a1 | b2 | c2 |
a2 | b2 | c1 |
:
A | B | C |
a1 | b2 | c2 |
a1 | b3 | c2 |
a2 | b2 | c1 |
笛卡尔积(Cartesian Product)
- 目关系,个元组; 目关系,个元组
-
- 列:列元组的集合
- 元组的前列是关系的一个元组
- 后列是关系的一个元组
- 行:个元组
$$
R×S = {\overset{\frown}{t_rt_s} |tr ∈R ∧ ts∈S }
$$
例 2.4
:
A | B | C |
a1 | b1 | c1 |
a1 | b2 | c2 |
a2 | b2 | c1 |
:
A | B | C |
a1 | b2 | c2 |
a1 | b3 | c2 |
a2 | b2 | c1 |
R.A | R.B | R.C | S.A | S.B | S.C |
a1 | b1 | c1 | a1 | b2 | c2 |
a1 | b1 | c1 | a1 | b3 | c2 |
a1 | b1 | c1 | a2 | b2 | c1 |
a1 | b2 | c2 | a1 | b2 | c2 |
a1 | b2 | c2 | a1 | b3 | c2 |
a1 | b2 | c2 | a2 | b2 | c1 |
a2 | b2 | c1 | a1 | b2 | c2 |
a2 | b2 | c1 | a1 | b3 | c2 |
a2 | b2 | c1 | a2 | b2 | c1 |
关系代数--专门的集合运算
例: 学生课程数据库
学生关系Student、课程关系Course和选修关系SC
学号(Sno) | 姓名(Sname) | 性别(Ssex) | 年龄(Sage) | 所在系(Sdept) |
201215121 | 李勇 | 男 | 20 | CS |
201215122 | 刘晨 | 女 | 19 | CS |
201215123 | 王敏 | 女 | 18 | MA |
201215125 | 张立 | 男 | 19 | IS |
课程号(Cno) | 课程名(Cname) | 先行课(Cpno) | 学分(Ccredit) |
1 | 数据库 | 5 | 4 |
2 | 数学 | | 2 |
3 | 信息系统 | 1 | 4 |
4 | 操作系统 | 6 | 3 |
5 | 数据结构 | 7 | 4 |
6 | 数据处理 | | 2 |
7 | PASCAL语言 | 6 | 4 |
学号(Sno) | 课程号(Cno) | 成绩(Grade) |
201215121 | 1 | 92 |
201215121 | 2 | 85 |
201215121 | 3 | 88 |
201215122 | 2 | 90 |
201215122 | 3 | 80 |
选择
例 2.4 查询信息系(IS系)全体学生
$$
σ_{Sdept = 'IS'}(Student)
$$
结果:
Sno | Sname | Ssex | Sage | Sdept |
201215125 | 张立 | 男 | 19 | IS |
例 2.5 查询年龄小于 20 岁的学生
$$
σ_{Sage < 20}(Student)
$$
结果:
Sno | Sname | Ssex | Sage | Sdept |
201215122 | 刘晨 | 女 | 19 | IS |
201215123 | 王敏 | 女 | 18 | MA |
201215125 | 张立 | 男 | 19 | IS |
投影(Projection)
从中选择出若干属性列组成新的关系
$$
\pi_A(R) = { t[A]|t \in R}, A: R 中的属性列
$$
- 投影操作主要是从列的角度进行运算
- 投影之后不仅取消了原关系中的某些列,而且还可能取消某些元组(避免重复行)
例2.6 查询学生的姓名和所在系
即求关系上学生姓名和所在系两个属性上的投影
$$
\pi_{Sname, Sdept}(Student)
$$
结果:
Sname | Sdept |
李勇 | CS |
刘晨 | CS |
王敏 | MA |
张立 | IS |
例2.7 查询学生关系 Student中都有哪些系
$$
π_{Sdept}(Student)
$$
结果:
连接(Join)
- 连接也称为连接
- 连接运算的含义
- 从两个关系的笛卡尔积中选取属性间满足一定条件的元组
$$
R \mathop{\bowtie}\limits_{A \theta B} S= {\overset\frown{t_r t_s}|t_r \in R \wedge t_s \in S \wedge t_r[A] \theta t_s[B]}
$$
- 和:分别为和上度数相等且可比的属性组
- :比较运算符
- 连接运算从和的广义笛卡尔积中选取关系在属性组上的值与关系在属性组上的值满足比较关系的元组
等值连接(equijion) 和自然连接(Natural join)
等值连接
- 为“=”的连接运算称为等值连接
- 从关系 $ R $ 与 $ S $ 的广义笛卡尔积中选取 $ A $ 、 $ B $ 属性值相等的那些元组,即等值连接为:
$$
R \mathop{\bowtie}\limits_{A \theta B} S= {\overset\frown{t_r t_s}|t_r \in R \wedge t_s \in S \wedge t_r[A] = t_s[B]}
$$
自然连接
- 自然连接是一种特殊的等值连接
- 两个关系中进行比较的分量必须是相同的属性组
- 在结果中把重复的属性列去掉
- 自然连接的含义
- R和S具有相同的属性组B,其自然连接为
$$
R \bowtie S= {\overset\frown{t_r t_s}[U-B]|t_r \in R \wedge t_s \in S \wedge t_r[B] = t_s[B]}
$$
- 即自然连接需要取消重复列,因此跟一般的连接操作是从行的角度进行运算不同,其同时从行和列的角度进行运算
例2.8
关系和关系如下所示
A | B | C |
a1 | b1 | 5 |
a1 | b2 | 6 |
a2 | b3 | 8 |
a2 | b4 | 12 |
B | E |
b1 | 3 |
b2 | 7 |
b3 | 10 |
b3 | 2 |
b5 | 2 |
A | R.B | C | S.B | E |
a1 | b1 | 5 | b2 | 7 |
a1 | b1 | 5 | b3 | 10 |
a1 | b2 | 6 | b2 | 7 |
a1 | b2 | 6 | b3 | 10 |
a2 | b3 | 8 | b3 | 10 |
A | R.B | C | S.B | E |
a1 | b1 | 5 | b1 | 3 |
a1 | b2 | 6 | b2 | 7 |
a2 | b3 | 8 | b3 | 10 |
a2 | b3 | 8 | b3 | 2 |
A | B | C | E |
a1 | b1 | 5 | 3 |
a1 | b2 | 6 | 7 |
a2 | b3 | 8 | 10 |
a2 | b3 | 8 | 2 |
悬浮元组(Dangling tuple)
两个关系 $ R $ 和 $ S $ 在做自然连接时,关系 $ R $ 中某些元组有可能在 $ S $ 中不存在公共属性上值相等的元组,从而造成 $ R $ 中这些元组在操作时被舍弃了,这些被舍弃的元组称为悬浮元组
外连接
- 如果把悬浮元组也保存在结果关系中,而在其他属性上填空值(Null),就叫做外连接
- 由悬浮元组的定义,可知外连接是在自然连接的基础上保留悬浮元组
- 左外连接(LEFT OUTER JOIN或LEFT JOIN)
- 右外连接(RIGHT OUTER JOIN或RIGHT JOIN)
A | B | C | E |
a1 | b1 | 5 | 3 |
a1 | b2 | 6 | 7 |
a2 | b3 | 8 | 10 |
a2 | b3 | 8 | 2 |
a2 | b4 | 12 | NULL |
NULL | b5 | NULL | 2 |
A | B | C | E |
a1 | b1 | 5 | 3 |
a1 | b2 | 6 | 7 |
a2 | b3 | 8 | 10 |
a2 | b3 | 8 | 2 |
a2 | b4 | 12 | NULL |
A | B | C | E |
a1 | b1 | 5 | 3 |
a1 | b2 | 6 | 7 |
a2 | b3 | 8 | 10 |
a2 | b3 | 8 | 2 |
NULL | b5 | NULL | 2 |
除运算(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 \div S = {t_r[X]|t_r \in R \wedge \pi_Y(S) \subseteq Y_x}
$$
- : $ x $ 在 $ R $ 中的象集, $ x=t_r[X] $
- 除操作是同时从行和列的角度进行运算
例2.9
A | B | C |
a1 | b1 | c2 |
a2 | b3 | c7 |
a3 | b4 | c6 |
a1 | b2 | c3 |
a4 | b6 | c6 |
a2 | b2 | c3 |
a1 | b2 | c1 |
B | C | D |
b1 | c2 | d1 |
b2 | c1 | d1 |
b2 | c3 | d2 |
具体的运算过程
- 在关系中,可以取四个值
- $ S $ 在 $ (B,C) $ 上的投影为
- 只有 $ a1 $ 的象集包含了 $ S $ 在 $ (B,C) $ 属性组上的投影
- 所以 $R÷S ={a1} $
综合训练
[例2.10] 查询至少选修1号课程和3号课程的学生号码
[例2.11] 查询选修了2号课程的学生的学号
$$
π_{Sno}(σ_{Cno=‘2’}(SC))={201215121,201215122}
$$
[例2.12] 查询至少选修了一门其直接先行课为5号课程的学生姓名
- 由输入输出分析法可知,为了从输入获得输出,需要将三张表连接起来
- 可采用自然连接来完成
- 有多种查询方法,不同查询方法的效率不同,但是结果一致
$$
\begin{aligned}
&π_{Sname}(σ_{Cpno=‘5’}(Course \bowtie SC \bowtie Student))\
&π_{Sname}(π_{Sno}(σ_{Cpno='5'}(Course) \bowtie SC) \bowtie π_{Sno,Sname}(Student))
\end{aligned}
$$
[例2.13] 查询选修了全部课程的学生号码和姓名
- 第一步:求出选修了全部课程的学生的学生号码
$$
P(Sno) = \pi_{Sno, Cno}(SC) \div \pi_{Cno}(Course)
$$
- 第二步:通过学号求学生姓名(对两个关系进行操作,借助自然连接来完成)
$$
π_{Sno}(P \bowtie Student )
$$
- 最终求解公式
$$
π_{Sno,Cno}(SC)÷π_{Cno}(Course) \bowtie π_{Sno,Sname}(Student)
$$