关系代数
一. 概述
关系代数特点
- 基于集合，提供一系列关系代数操作：并，差，笛卡尔积（广义积），选择，投影，更名等操作
- 以及交，连接和关系除等扩展操作，是一种集合思维的操作语言
- 关系代数操作以一个或多个关系为输入，结果是一个新的关系
- 一种抽象的语言，是学习其他数据库语言的，如SQL的基础
关系代数操作
集合操作
纯关系操作
二. 基本操作
0. 并相容性
- 参与运算的两个关系及其相关属性间有一定的对应性和可比性或意义关联性
定义：关系R与关系S存在相容性，当且仅当：
- 关系R与关系S的属性数目必须相同
- 对于任意 i，关系 R 的第 i 个属性的域必须和关系 S 的第 i 个属性的域相同
1. 并
R与S是并相容的，
t
t
t
是元组
数学描述：
R
∪
S
=
{
t
∣
t
∈
R
∨
t
∈
S
}
R∪S=\{ t | t ∈ R \vee t ∈ S\}
R
∪
S
=
{
t
∣
t
∈
R
∨
t
∈
S
}
并运算是将两个关系的元组合并成一个关系，在合并时去掉重复元组
2. 差
R与S是并相容的，
t
t
t
是元组
数学描述：
R
−
S
=
{
t
∣
t
∈
R
∧
t
∉
S
}
R – S=\{ t | t ∈ R \wedge t \notin S\}
R
−
S
=
{
t
∣
t
∈
R
∧
t
∈
/
S
}
3. 广义笛卡尔积
R
(
<
a
1
,
a
2
,
.
.
.
,
a
n
>
)
,
S
(
<
b
1
,
b
2
,
.
.
.
,
b
n
>
)
R(<a_1, a_2,…, a_n>), S(<b_1, b_2,…, b_n>)
R
(
<
a
1
,
a
2
,
.
.
.
,
a
n
>
)
,
S
(
<
b
1
,
b
2
,
.
.
.
,
b
n
>
)
数学描述：
R
×
S
=
{
<
a
1
,
a
2
,
.
.
.
,
a
n
,
b
1
,
b
2
,
.
.
.
,
b
n
>
∣
<
a
1
,
a
2
,
.
.
.
,
a
n
>
∈
R
∧
<
b
1
,
b
2
,
.
.
.
,
b
n
>
∈
S
}
R×S=\{<a_1, a_2,…, a_n, b_1, b_2,…, b_n> | <a_1, a_2,…, a_n> ∈ R \wedge <b_1, b_2,…, b_n> ∈ S\}
R
×
S
=
{
<
a
1
,
a
2
,
.
.
.
,
a
n
,
b
1
,
b
2
,
.
.
.
,
b
n
>
∣
<
a
1
,
a
2
,
.
.
.
,
a
n
>
∈
R
∧
<
b
1
,
b
2
,
.
.
.
,
b
n
>
∈
S
}
R 与 S，属性个数（度数）分别为 n 和 m，元组个数（基数）分别为 x 和 y，则：
-
R×
S
R×S
R
×
S
属性个数为
n+
m
n+m
n
+
m
-
R×
S
R×S
R
×
S
元组个数为
x×
y
x×y
x
×
y
例子：若 R 元组数目为 3，度数为 3；S 元组数目为 4，度数为 3，则
R
×
S
R×S
R
×
S
的元组数目为
3
×
4
=
12
3×4=12
3
×
4
=
1
2
，度数为
3
+
3
=
6
3+3=6
3
+
3
=
6
4. 选择
给定一个关系 R 和选择的条件 condition（简写con）
R
(
A
1
,
A
2
,
.
.
.
,
A
n
)
R(A_1, A_2,…, A_n)
R
(
A
1
,
A
2
,
.
.
.
,
A
n
)
，t 是 R 的元组，t 的分量记为
t
[
A
i
]
t[A_i]
t
[
A
i
]
或简写为
A
i
A_i
A
i
数学描述：
δ
c
o
n
(
R
)
=
{
t
∣
t
∈
R
∧
c
o
n
(
t
)
=
t
r
u
e
}
\delta_{con}(R)=\{t | t∈R \wedge con(t)=true\}
δ
c
o
n
(
R
)
=
{
t
∣
t
∈
R
∧
c
o
n
(
t
)
=
t
r
u
e
}
条件运算符优先次序从高到低：
{
(
)
,
θ
,
﹁
,
∧
,
∨
}
\{(), \theta, ﹁, \wedge, \vee \}
{
(
)
,
θ
,
﹁
,
∧
,
∨
}
5. 投影
给定一个关系 R，从关系 R 中选出属性包含在 A 中的列构成
投影操作从给定关系中选出某些列组成新的关系，而选择操作是从给定关系中选出某些行组成新的关系
数学描述：
∏
A
i
1
,
A
i
2
,
.
.
.
,
A
i
k
(
R
)
=
{
<
t
[
A
i
1
]
,
t
[
A
i
2
]
,
.
.
.
,
t
[
A
i
k
]
>
∣
t
∈
R
}
\prod_{A_{i1}, A_{i2},…,A_{ik}}(R)=\{<t[A_{i1}], t[A_{i2}],…,t[A_{ik}]> | t ∈R \}
∏
A
i
1
,
A
i
2
,
.
.
.
,
A
i
k
(
R
)
=
{
<
t
[
A
i
1
]
,
t
[
A
i
2
]
,
.
.
.
,
t
[
A
i
k
]
>
∣
t
∈
R
}
如果投影后有重复元组，则应去掉
三. 扩展操作
1. 交
R 与 S 并相容，t 是元组
数学描述：
R
∩
S
=
{
t
∣
t
∈
R
∧
t
∈
S
}
R∩S=\{t | t ∈ R \wedge t ∈ S \}
R
∩
S
=
{
t
∣
t
∈
R
∧
t
∈
S
}
2.
θ
\theta
θ
-连接操作
投影与选择操作都只是对单个关系进行操作，而实际应用往往涉及多个表之间的操作， 这就需要
θ
\theta
θ
-连接操作
t 是 R 中的元组，s 是 S 中的元组，
θ
\theta
θ
为比较运算符，属性 A 和 属性 B 具有可比性
数学描述：
δ
t
[
A
]
θ
s
[
B
]
(
R
×
S
)
\delta_{t[A] \theta s[B]}(R×S)
δ
t
[
A
]
θ
s
[
B
]
(
R
×
S
)
由关系 R 和关系 S 的笛卡尔积中选取 R 中的属性 A 与 S 中的属性 B 之间满足
θ
\theta
θ
条件的元组构成
例子1：
例子2：
查询至少1号同学和2号同学学过的所有课程
∏
S
C
.
C
(
δ
S
C
.
S
=
”
1
”
∧
S
C
1.
S
=
”
2
”
(
S
C
⋈
S
C
.
C
=
S
C
1.
C
ρ
S
C
1
(
S
C
)
)
)
\prod_{SC.C}(\delta_{SC.S=”1″ \wedge SC1.S=”2″}(SC⋈_{SC.C=SC1.C} \rho_{SC1}(SC)))
∏
S
C
.
C
(
δ
S
C
.
S
=
”
1
”
∧
S
C
1
.
S
=
”
2
”
(
S
C
⋈
S
C
.
C
=
S
C
1
.
C
ρ
S
C
1
(
S
C
)
)
)
-
其中
ρS
C
1
(
S
C
)
\rho_{SC1}(SC)
ρ
S
C
1
(
S
C
)
为更名操作，将 SC 表更名为 SC1，用于一个表与自身连接运算时使用
3. 等值连接操作
当
θ
\theta
θ
-连接操作中
θ
\theta
θ
为
=
=
=
时的特殊情况
4. 自然连接
R 与 S 的笛卡尔积中选取相同属性组 B 上值相等的元组构成
数学描述：
R
⋈
S
=
δ
t
[
B
]
=
s
[
B
]
(
R
×
S
)
R⋈S=\delta_{t[B]=s[B]}(R×S)
R
⋈
S
=
δ
t
[
B
]
=
s
[
B
]
(
R
×
S
)
要求 R 与 S 必须有相同的属性组 B，结果中需要去掉重复的属性列
四. 书写关系代数表达式思路
-
检索是否涉及多个表，若不涉及，则可直接采用并，差，交，选择，与投影，只要注意条件书写正确与否即可
-
如设计多个表，则检查
- 能否使用自然连接，将多个表连接起来
-
如不能，能否使用等值或不等值连接（
θ\theta
θ
-连接） - 还不能，则使用广义笛卡尔积，注意相关条件书写
-
连接完后，可以继续使用选择投影等运算，即所谓数据库的“选投联”操作
五. 复杂扩展操作
1. 除
除法运算常用于求解 “查询… 全部/所有的…” 问题
给定
R
(
A
1
,
A
2
,
.
.
.
,
A
n
)
R(A_1, A_2,…,A_n)
R
(
A
1
,
A
2
,
.
.
.
,
A
n
)
为 n 度关系，
S
(
B
1
,
B
2
,
.
.
.
,
B
m
)
S(B_1, B_2,…,B_m)
S
(
B
1
,
B
2
,
.
.
.
,
B
m
)
为 m 度关系，若可以进行 R 与 S 的除运算，则必须满足属性集
{
B
1
,
B
2
,
.
.
.
,
B
m
}
\{B_1, B_2,…,B_m\}
{
B
1
,
B
2
,
.
.
.
,
B
m
}
是属性集
{
A
1
,
A
2
,
.
.
.
,
A
n
}
\{A_1, A_2,…,A_n\}
{
A
1
,
A
2
,
.
.
.
,
A
n
}
的真子集，即
m
＜
n
m ＜ n
m
＜
n
设
{
C
1
,
C
2
,
.
.
.
C
k
}
=
{
A
1
,
A
2
,
.
.
.
,
A
n
}
−
{
B
1
,
B
2
,
.
.
.
,
B
m
}
\{C_1, C_2,…C_k\} = \{A_1, A_2,…,A_n\} – \{B_1, B_2,…,B_m\}
{
C
1
,
C
2
,
.
.
.
C
k
}
=
{
A
1
,
A
2
,
.
.
.
,
A
n
}
−
{
B
1
,
B
2
,
.
.
.
,
B
m
}
数学描述：
R
÷
S
=
{
t
∣
t
∈
∏
R
−
S
(
R
)
∧
∀
u
∈
S
(
t
u
∈
R
)
}
R ÷ S=\{t | t ∈ \prod_{R-S}(R) \wedge \forall u ∈ S(tu∈R)\}
R
÷
S
=
{
t
∣
t
∈
∏
R
−
S
(
R
)
∧
∀
u
∈
S
(
t
u
∈
R
)
}
或
∏
R
−
S
(
R
)
−
∏
R
−
S
(
(
∏
R
−
S
(
R
)
×
S
)
−
R
)
\prod_{R-S}(R)-\prod_{R-S}((\prod_{R-S}(R)×S)-R)
∏
R
−
S
(
R
)
−
∏
R
−
S
(
(
∏
R
−
S
(
R
)
×
S
)
−
R
)
结果是一个
n
−
m
=
k
n-m=k
n
−
m
=
k
度关系，由
{
C
1
,
C
2
,
.
.
.
C
k
}
\{C_1, C_2,…C_k\}
{
C
1
,
C
2
,
.
.
.
C
k
}
属性组成
例子：
2. 外连接
查询所有老师的有关信息，包括姓名，工资，所教课程等
可以发现元组中 003 号教师姓名和工资信息丢失了，可能 003 教师没有讲课，这就需要外连接
若 R 与 S 连接时，R 在 S 中找不到相匹配的元组，为了避免该元组信息丢失，从而将该元组与 S 中假定存在的全为空值得元组形成连接，放置在结果关系中，这种连接称之为
外连接
例子1：
