数据库原理-关系代数
数据库原理-关系代数
什么是关系代数？
关系代数是数据库查询的理论基础，数据库中所有的查询语句都能够用相对应的关系代数运算来表达
关系代数操作的对象就是关系，它通过对关系进行组合和分割来生成一个新的关系。也就是说，该运算的域没有发生变化，这和我们常用的实数运算是类似的。
离散数学回顾-关系的概念
关系在数据库中对应的是一张张表格，而关系中的元组对应的是表格中的行。从数学定义上来看，数据库中的关系和离散数学中的关系有相同的概念，即笛卡尔积的子集。在离散数学中，关系定义如下：
设$$n\in I_{+}，A_1, A_2, …, A_n$$是$n$个集合，$R\subseteq \times_{i=1}^{n} A_i$, 称$R$是集合$A_1, A_2, …, A_n$ 上的n元关系
从定义中可以看出关系有如下性质：
- 关系是集合
- 关系中的元素是有序n重组
数学上的关系和现实中常用的关系的概念是有区别的，因为数学上不是所有的关系都有意义，比如把汽车种类和食物种类做笛卡尔积后得到的关系基本毫无用处，除非你生活在汽车人的世界里:)
下面是一个关系的例子：
假设我们想要记录一车苹果的质量，但我们只关心它的两个属性：
color: in (green, red)
size: in (large, little)
则所有可能出现的苹果种类构成了笛卡尔积，这个集合有2x2=4个元素：
{<green, large>, <green, little>, <red, large>, <red, little>}
我们可以确定这车苹果所包含的种类一定在这个笛卡尔积中，因此可以为这些苹果建立一个关系：
color size green large red little 这表明这车苹果中只有绿色大苹果和红色小苹果
集合运算
包括并、差、交和广义的笛卡尔积，注意，集合运算操作的对象是关系中的元素，即元组，因此，除了笛卡尔积之外，其它运算中两个关系必须有相同的属性
每种运算的定义如下：
并(Union):
$$
R \bigcup S = {t | t \in R \vee t \in S}
$$
差(Difference):
$$
R - S = {t | t \in R \wedge t \notin S}
$$
交(Intersection):
$$
R \bigcap S = {t | t \in R \wedge t \in S}
$$
积(Cartesian Product):
$$
R \times S = {t_r t_s | (t_r \in R) \wedge (t_s \in S)}
$$
前3种十分易于理解，对于广义笛卡尔积，新生成的关系的属性由R和S的属性拼接而成，而该关系是R和S中元素的所有组合的集合。在数据库中，广义笛卡尔积常用于多表查询，对应语句from table1, table2
关系运算
关系运算包括选择、投影、连接、除，广义上还有外连接
选择(Selection):
$$
{\sigma}_{F}(R) = {t | (t \in R) \wedge F(t) = True}
$$
其中$F$为条件表达式
只有满足条件的元组被留下来，形成新的关系，对应于SQL语句里的where
投影(Projection):
$$
{\Pi}_A (R) = {t[A] | (t \in R)}
$$
只选择原关系中的部分属性组成新的关系，对应于SQL语句里的select（碰巧是上一个运算的名字，容易弄混）
连接(Join):
$$
R \underset{A\theta B}{\bowtie} S = {\sigma}_{R.A \theta S.B}(R \times S)
$$
常见的连接运算：
等值连接：即 $\theta$ 为 = 的连接
自然连接。特殊的等值连接，要求两个关系中有相同的属性组，表示其属性和域都得相同，结果会把重复的属性去掉。自然连接是内连接的一种，如果一个关系中该属性的某个取值在另一个关系中找不到，则忽略这个取值对应的元组。
自然连接可以分解为3个步骤：求$R \times S$， 选择满足等值条件的元组($ R.B_1 = S.B_1 \wedge R.B_2 = S.B_2 …$)，去掉重复的属性
($B_1, B_2,…$)
除(Division):
$$
R \div S = {t[X] | t \in R \wedge {\Pi}_Y (S) \subseteq Y_X }
$$
其中R(X, Y), S(Y, Z)
求除运算的4个步骤：
- 求${\Pi}_X (R)$
- 求${\Pi}_Y (S)$
- 求$Y_X$ ($X$在 $R$ 中的像集(Image Set))，类似于SQL语句中的GROUP BY X，将关系 $R$ 中的元组根据 $X$ 的取值划分成了一个个小组
- $R \div S$ 的计算结果为像集 $Y_X$ 包含了 ${\Pi}_Y(S)$ 的 $x_i$，即，如果上一步所求的小组中包含S投影在Y上的关系，则将该小组对应的 $X$ 的取值放到结果关系中
还是拿苹果关系作为例子:
假设现在给每个苹果编号
id color size 1 green large 2 red little 3 red large 4 green little 然后从中筛选出又大又红的苹果，则可以把除数设置为要筛选的属性
color size red large 把两个关系做除运算后，就可以得到质量又大又红的苹果的编号
id 3
外连接:
同样要进行等值连接，但是会根据连接的方式决定是否把某些属性置空，最后再去掉重复的属性
假设关系R和S有公共属性Y，如果R中的某些元组在S中没有与Y上值相等的元组，或者相反，则
全外连接：都不去掉，相应属性以null填充
左外连接：保留关系R上的元组，S上的其他属性用null填充
右外连接：保留关系S上的元组，R上的其他属性用null填充