关系代数

本文并非原创，而是自己整理老师课件所得。

概述

关系代数是关系数据库的数学基础，在关系数据库中的查询常常通过关系的运算来表示。因此关系代数就是一种抽象的查询语言。

对于关系代数，运算的三要素是：

运算对象：关系
运算符：
- 集合运算符
  
  交、并、差、广义笛卡尔积
- 专门的关系运算符
  
  选择、投影、连接、除
- 算术比较符
  
  大于、小于、等于
- 逻辑运算符
  
  与、或、非
分为基本运算和导出运算
运算结果：关系

记号

设关系模式为\(R(A_1,A_2,\cdots,A_n)\)（R是Relationship，A是Attribute），它的一个关系设为R（关系模式和关系，型和值，这个R相当于一个实例）。

\(t\in R\)表示\(t\)是\(R\)的一个元组。（把关系看做一张表，这就是表的一行）

\(t[A_i]\)表示元组\(t\)中相应于属性\(A_i\)的一个分量。（表中这一行对应的一个单元格）

若\(A=\{A_{i1},A_{i2},\cdots, A_{ik}\}\)，其中\(A_{i1},A_{i2},\cdots, A_{ik}\)是\(A_i,A_2,\cdots,A_n\)的一部分，则A称为属性组或域组。\(t[A]\)表示元组\(t\)在属性组上分量的集合。

\(\bar A\)表示所有属性去掉属性组\(A\)剩余的属性组。

\(R\)是n目关系，\(S\)是m目关系，\(t_r\in R\)，\(t_s\in S\)，\(\mathop{t_rt_s}\limits^{\frown}\)称为元组的拼接，是一个n+m列的元组。感觉n目关系就可以理解为列数为n的表。

给定一个关系\(R(X,Z)\)，\(X\)和\(Z\)为属性组。当\(t[X]=x\)时，\(x\)在\(R\)中的象集为：

\[Z_x=\{t[Z]|t\in R, t[X]=x\} \]

表示\(R\)中属性组\(X\)上值为\(x\)的所有元组在\(Z\)属性的值的集合。

比如关系为（性别，这个班同学的名字），那么“女”在[班上所有名字]中的象集为班上所有女生的名字。

运算符

先看基本运算。

选择

格式：\(\sigma_{selection-condition}(R)\)

选择关系\(R\)中所有符合条件的元组（行）。

选择条件：分为三类

记A、B是属性组，op是算术运算符，v是常数。

A op v：比如age < 20
A op B：比如birthplace=residence
前两种情况用and/or/not混合起来

投影

格式：\(\pi_{attribute-list}(R)\)

返回所有元组中，列出的属性组中的值（选择列）。

投影会自动去除重复的元组。

同时使用选择和投影即可从表中选择行列。

笛卡尔积

格式：\(R_1\times R_2\)

返回\(R_1\)和\(R_2\)中所有通过拼接可以得到的元组组成的新关系。如果原表分别m行、n行，则新表有\(m\times n\)行，因此这个操作的空间开销很大。

如果\(R_1\)和\(R_2\)有同名的属性\(A\)，则应该写全名\(R_1.A\)和\(R_2.A\)。为了防止属性名重复，不允许\(R\times R\)，但是如果经过重命名操作\(\rho\)，重命名为\(S\)，允许\(R\times\rho_S(R)\)。

满足交换律，\(R_1\times R_2=R_2\times R_1\)。因为元组是无序的。

并

格式：\(R_1\cup R_2\)

选择要么属于\(R_1\)要么属于\(R_2\)的所有元组。但是要求\(R_1\)和\(R_2\)必须union compatible。

即，它们必须有相同数量的属性，对应的属性要有同样的域和名字。

并也会自动去除重复的元组。

差

格式：\(R_1-R_2\)

返回所有属于\(R_1\)而不属于\(R_2\)的所有元组。

再看导出运算，会注明是如何由基本运算导出的。

交

格式：\(R_1\cap R_2\)

返回同时属于\(R_1\)和\(R_2\)的所有元组。

\(R_1\cap R_2=R_1-(R_1-R_2)=R_2-(R_2-R_1)\)

连接

格式：\(R_1\bowtie_{join-condition}R_2\)

返回\(R_1\times R_2\)中所有符合条件的元组。

\(R_1\bowtie_{join-condition}R_2=\sigma_{join-condition}(R_1\times R_2)\)

等值连接：当且仅当连接条件中使用等号。

自然连接：直接用\(\bowtie\)符号，无需显式指明连接条件。需要满足

两个关系中所有同名属性都用等式条件
所有同名属性最后只留一个

很像把两张纸粘起来，相同的那一列就是用来粘贴的边缘，粘完之后边缘重叠（只留一列）。

外连接：\(R_1\bowtie_o R_2\)

在自然连接中，两个关系中没有被选的（同名属性的值不相等的）元组叫做dangling tuples。

外连接保留了这些元组，并且用NULL填充空值。

左/右外连接分别为\(\rtimes\)和\(\ltimes\)，分别只保留来自左侧/右侧的dangling tuples。

除

格式：\(R_1\div R_2\)

需要满足所有在\(R_2\)中的属性都在\(R_1\)中。

考虑\(R_1(A_1,\cdots,A_n,B_1,\cdots,B_m)\div R_2(B_1,\cdots, B_m)\)

令\(T=\pi_{A_1,\cdots, A_n}(R_1)\)，也就是选择\(R_1\)中\(R_2\)没有的那些列。

这个除会返回\(T\)中所有“使得\(t\)和\(R_2\)的每个元组连接所得元组都在\(R_1\)中”的元组\(t\)。

\(R_1\div R_2=T-\pi_{A_1,\cdots,A_n}(T\times R_2-R_1)\)

上式也就是从\(T\)中去掉“和\(R_2\)连接后不在\(R_1\)中的”那些元组。

另一种定义

\(t\in R_1\div R_2\)当且仅当

\(t\in \pi_{R_1-R_2}(R_1)\)（也就是前面的\(T\)）
对\(R_2\)中的每一个元组\(t_{R_2}\)，在\(R_1\)中都有元组\(t_{R_1}\)同时满足以下两式：

\(t_{R_1}[R_2]=t_{R_2}[R_2]\) （总有\(R_1\)中的元组，在\(R_2\)属性的那部分上，和\(R_2\)的元组是一样的值）

\(t_{R_1}[R_1-R_2]=t\) （且，不在\(R_2\)属性的那部分，是一个符合上一点定义的\(t\)）

例题

找出修过的课包含“学号123456的学生修过的所有课”的所有名字和GPA。

\[Students(Sno,Name,GPA) \]

\[Takes(Sno,Course) \]

找到学号123456的学生修过的所有课

\(SELECTED\_COURSE:=\pi_{Course}(\sigma_{Sno=123456}(Takes))\)

先在Takes中选择学号为123456对应的行，再选Course列，得到一个单元格。
找到所有上过SELECTED COURSE的学生学号

\(SNOs:=Takes\div SELECTED\_COURSE\)

从Takes中选择Course=SELECTED_COURSE的行，保留除Course以外的列，此处即Sno。
得到对应这些Sno的名字和GPA

\(RESULT:=\pi_{Name,GPA}(Students\bowtie SNOs)\)

这里的连接其实相当于选择Students的行，这些行和SNOs中Sno一样，然后再选择列，Name和GPA。

找出参与了每一个项目的员工的名字。

\[Employees(Sno,Name,Department) \]

\[Projects(Proj,Name,Budget) \]

\[Participation(Sno,Proj) \]

从Projects中找到Proj列，这就是所有项目

\(PROJs:=\pi_{Proj}(Projects)\)
从Participation中找到对应Proj取值的行，再取不要Proj列的列，即Sno列

\(SNOs:=Participation\div PROJs\)
从Employees中找到对应Sno取值的行，再取Name列

\(RESULT:=\pi_{Name}(Employees\bowtie SNOs)\)