数据库-关系代数
关系代数是一种抽象的查询语言，它用于对关系的运算来表达查询。
关系代数的运算按运算符的不同分为传统的集合运算和专门的关系运算两类。
- 集合运算和关系运算的不同
- 传统的集合运算将关系看成元组的集合，其运算是从关系的“水平”方向进行，即行的角度来进行。而专门的关系运算不仅涉及行而且涉及列。
- 比较运算符和逻辑运算符专门辅助关系运算。
- 笛卡尔积定义不同
- 集合论中的笛卡儿积定义：
$${\displaystyle X\times Y=\left{\left(x,y\right)\mid x\in X\land y\in Y\right}}$$ - 关系运算中的笛卡儿积定义：
$$R \times S ={r \cup s| r \in R, s \in S }$$
或者
$$R \times S ={ \mathop{t_rt_s}^{ \frown} | t_r \in R, t_s \in S }$$(课本定义)
- 集合论中的笛卡儿积定义：
- 关系运算
包括选择、投影、连接、除等。- 选择：在关系R中选出满足规定条件的诸元组（即从行的角度进行的运算 ）。记作：
$$\sigma_F(R)={ t | t \in R \wedge F(t)=’true’ }$$
( /ˈsɪɡmə/)
F是一个逻辑表达式。 - 投影：从R中选出若干属性列组成新的关系（即从列的角度进行的运算）。记作：
$$ \Pi_A(R) ={t[A] | t \in R}$$
投影之后不仅取消原关系中的某些列而且会取消某些元组，因为取消某些列后可能出现重复的行，应取消在这些行。 - 连接($\theta 连接$)，从连个关系的笛卡儿积中选择属性间满足一定条件的元组。记作:
$$\mathop{ R \bowtie S}_{a \theta b} = { \mathop{t_rt_s}^{ \frown} | t_r \in R \wedge t \in S \wedge t_r[A] \theta t_s[B]}$$
A 和 B 为 R 和 S 上可比较的属性组，$\theta$为比较运算符。
连接运算从R和S的笛卡儿积 R $\times$ S 中选取 R 关系在 A 属性组上的值和 S 关系在 B 属性组上的值满足比较关系 $\theta$ 的元组。- 自然连接和等值连接
等值连接即$\theta$为 =的连接。两者的区别在于自然连接取消重复列。
两个关系R和S在做自然连接时，取公共属性上值相等的元组构成新的关系，可能产生悬浮元组（双方公共属性不相等的元组）。由此引出外连接、左外连接和右外连接。顾名思义，外连接(R ⟗ S )保留双方的悬浮元组，左外连接(R ⟕ S)保留 R 的，右外连接(R ⟖ S)保留 S 的。
- 自然连接和等值连接
- 除运算(同时从行和列角度进行的运算)
设关系 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 的象集 $Y_x$ 包含 S 在 Y 上投影的集合。记作：
$$R \div S= {t_r[X]|t_r \in R \wedge \Pi_y(S) \subseteq Y_x}$$
其中 $Y_x$ 为 x 在 R 中的象集，$x=t_r[X]$。
[例子]查询选修了所有课程的学生学号和姓名。
$$\Pi_{Sno,Cno}(SC) \div \Pi_{Cno}(Course)\bowtie \Pi_{Sno,Sname}(Student)$$
- 选择：在关系R中选出满足规定条件的诸元组（即从行的角度进行的运算 ）。记作：
关系代数表达式等价替换规则。
设 E 是关系代数表达式。
(1)交换律- 连接、笛卡儿积的交换律
$$E_1 \times E_2 \equiv E_2 \times E_1$$
$$E_1 \bowtie E_2 \equiv E_2 \bowtie E_1$$
$$E_1 \mathop{\bowtie}_{F} E_2 \equiv E_2 \mathop{\bowtie}_{F}E_1 $$
F 是连接运算的条件。 - 选择与投影操作的交换律
$$\sigma_{F}(\Pi_{A_1,A_2,\dotsb,A_n}(E)) \equiv \Pi_{A_1,A_2,\dotsb,A_n}(\sigma_{F}(E))$$
条件 F 里只涉及 属性$ {A_1,A_2,\dotsb,A_n}$时，上式成立。否则有下更一般的结论。
$$\Pi_{A_1,A_2,\dotsb,A_n}(\sigma_{F}(E)) \equiv \Pi_{A_1,A_2,\dotsb,A_n}(\sigma_{F} (\Pi_{A_1,A_2,\dotsb,A_n,B_1,B_2,\dotsb,B_n}(E)))$$ - 选择与笛卡儿积的交换律
如果 F 中涉及的属性都是 $E_1$ 中的属性，则
$$\sigma_{F}(E_1 \times E_2) \equiv \sigma_{F}(E_1) \times E_2$$
如果 $F=F_1 \wedge F_2$, 并且 $F_1$ 只涉及 $E_1$ 中的属性，$F_2$ 只涉及 $E_2$ 中的属性，则由等价变换l连接的交换律、选择的串接定律以及上式可推出
$$\sigma_{F}(E_1 \times E_2) \equiv \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2)$$
若$F_1$ 只涉及 $E_1$ 中的属性，$F_2$ 涉及 $E_1$ 和 $E_2$的属性，则仍有
$$\sigma_{F}(E_1 \times E_2) \equiv \sigma_{F_2}(\sigma_{F_1}(E_1) \times E_2)$$
它是部分选择在笛卡儿积前先做。
(2)结合律
- 连接、笛卡儿积的结合律
(3)分配律
- 选择与并的分配律
设 $E=E_1 \cup E_2$ ，$E_1$、$E_2$有相同的属性名，则
$$\sigma_{F}(E_1 \cup E_2) \equiv \sigma_{F}(E_1) \cup\sigma_{F}(E_2)$$ - 选择与差运算的分配律
$E_1$、$E_2$有相同的属性名，则
$$\sigma_{F}(E_1 - E_2) \equiv \sigma_{F}(E_1) - \sigma_{F}(E_2)$$ - 选择对自然连接的分配律
$$\sigma_{F}(E_1 \bowtie E_2) \equiv \sigma_{F}(E_1) \bowtie \sigma_{F}(E_2)$$
F 只涉及 $E_1$、$E_2$的公共属性。 - 投影与笛卡儿积的分配律
A 是 $E_1$ 的属性， B 是 $E_2$ 的属性。
$$\Pi_{A_1,A_2,\dotsb,A_n,B_1,B_2,\dotsb,B_n}(E_1 \times E_2) \equiv \Pi_{A_1,A_2,\dotsb,A_n}(E_1) \times \Pi_{B_1,B_2,\dotsb,B_n}(E_2)$$ - 投影与并的分配律
$E_1$、$E_2$有相同的属性名，则
$$\Pi_{A_1,A_2,\dotsb,A_n}(E_1 \cup E_2) \equiv \Pi_{A_1,A_2,\dotsb,A_n}(E_1) \cup \Pi_{A_1,A_2,\dotsb,A_n}(E_2 )$$
(4)串接定律
- 投影的串接定律
$$\Pi_{A_1,A_2,\dotsb,A_n}(\Pi_{B_1,B_2,\dotsb,B_n}(E)) \equiv \Pi_{A_1,A_2,\dotsb,A_n}(E)$$
${A_1,A_2,\dotsb,A_n}$ 是 ${B_1,B_2,\dotsb,B_n}$ 的子集。 - 选择的串接定律
$$\sigma_{F_1}(\sigma_{F_2}(E)) \equiv \sigma_{F_1\wedge F_2}(E)$$
- 连接、笛卡儿积的交换律
几个约定：
(1) 设关系模式$R(A_1,A_2,\dotsb,A_n)$,它的一个关系为R。t $\in$ R 表示 t 是R的一个元组。$t[A_i]$则表示元组 t 中相应于属性$A_i$的一个分量。
(2) $t[A] =( t[A_{i1}],t[A_{i2}],\dotsb,t[A_{ik}]) $ 表示元组 t 在属性列 A 上诸分量的集合，$\overline{A} $ 表示剩余的属性组。
(3) R 为 n 目关系，S 为 m 目关系。$t_r \in R $,$t_s \in S $, $ \mathop{t_rt_s}^{ \frown} $ 称为元组的连接。它是一个n + m 的元组。
(4) 给定一个关系为 R(X,Z) ,X 和Z为属性组。当 t[X]=x 时，x 在 R 上的象集定义为
$$ Z_x={ t[Z] | t \in R,t[X]=x}$$
它表示R中属性组X上的值为 x 的诸元组在 Z 上分量的集合。