数据库-关系代数

1.域

域是一组具有相同数据类型的值的集合, 也就是这列属性能取的值, 通常用 $D_i$ 来表示

域不是"某个实体实际取到的值", 而是"某个属性允许取值的集合", 描述了属性的取值范围.

就比如 $D_{性别}=\{男,女\}$, 即使一个部门都是男人, 也是 $D_{性别}=\{男,女\}$

而例如: $D_{姓名}$ 则是一个近乎无穷大的集合

若 $D_i$ 是有限集, 且其基数为 $m_i$, 基数表示域所有可能的取值的个数.

基数会在不同语境有不同意思, 但总归指的是元素的个数, 比如:

• 域的基数 = 域中值的个数 (因为域表示的就是取值范围);
• 关系的基数 = 关系中元组的个数, 也就是行数 (因为关系就是由元组组成的);

2.笛卡尔积

$$D_1\times D_2\times \cdot\cdot\cdot\times D_n=\{ (d_1,d_2\cdot \cdot \cdot d_n)\mid d_i\in D_i,\ i=1,2,\cdot\cdot\cdot ,n\}$$

可以看到, 笛卡尔积是所有域的组合后的集合, 或者看做一张二维表.

其中每个元素 $(d_1,d_2\cdot \cdot \cdot d_n)$ 是元组, 也可用 $t$ 表示, 元组中的值 $d_j$ 是分量.

• 元组是元素组合的意思, 对应数据表的一行
• 分量指的是元组里的元素, 对应数据表中的一个单元格
• 分量应该是原子级的, 也就是不允许有表中表

若 $D_i (i=1,2,...,n)$ 是有限集, 且其基数为 $m_i (i=1,2,...,n)$
那么 $D_1 \times D_2 \times ... D_n$ 的基数 $M$ 为所有基数相乘:$M = {\prod_{i=1}^{n}m_i}$

$\prod_{i=1}^{n}$ 表示连乘, 类比 $\sum_{i=1}^{n}$ 表示连加

笛卡尔积本身就对应一张二维表, 比如:

姓名:$D_1={史丹妮,周冬元,李晓辉,...}$
性别:$D_2={男,女}$
专业:$D_3={人工智能,数据科学,...}$

$D_1\times D_2\times D_3$:

$$\begin{array}{|c|c|c|} \hline 姓名 & 性别 & 专业 \\ \hline 史丹妮 & 男 & 人工智能 \\ 史丹妮 & 男 & 数据科学 \\ 史丹妮 & 女 & 人工智能 \\ 史丹妮 & 女 & 数据科学 \\ 周冬元 & 男 & 人工智能 \\ 周冬元 & 男 & 数据科学 \\ 周冬元 & 女 & 人工智能 \\ 周冬元 & 女 & 数据科学 \\ 李晓辉 & 男 & 人工智能 \\ 李晓辉 & 男 & 数据科学 \\ 李晓辉 & 女 & 人工智能 \\ 李晓辉 & 女 & 数据科学 \\ ... & ... & ... \\ \hline \end{array}$$

3.关系

笛卡尔积 $D_1\times D_2\times ...\times D_n$ 的子集 叫作在域 $D_1,D_2,...,D_n$ 上的关系, 表示为 $R (D_1,D_2,...,D_n)$

• 关系是集合, 因此天然不允许重复元组
• 当 $n=1$ 叫单目关系, $n=2$ 叫二目关系.
• 关系是笛卡尔积的有限子集, 所以关系本身也是二维表.

目数指的是列的个数

笛卡尔积 = 所有理论上可能的元组
关系 = 从这些可能元组中实际存在的那些元组组成的集合

域是"可能的值", 笛卡尔积是"可能的组合", 关系是"实际存在的组合".

4.传统的集合运算

R:

$$\begin{array}{|c|c|c|c|c|} \hline 职工号 & 姓名 & 性别 & 科室号 & 科室 \\ \hline 01 & 张三 & 男 & 01 & 办公室 \\ 02 & 李四 & 女 & 01 & 办公室 \\ \hline \end{array}$$

S:

$$\begin{array}{|c|c|c|c|c|} \hline 职工号 & 姓名 & 性别 & 科室号 & 科室 \\ \hline 02 & 李四 & 女 & 01 & 办公室 \\ 03 & 王五 & 男 & 02 & 门岗 \\ \hline \end{array}$$

4.1 并

$$R \cup S=\{t\mid t \in R \vee t\in S\}$$

$$R \cup S = \begin{array}{|c|c|c|c|c|} \hline 职工号 & 姓名 & 性别 & 科室号 & 科室 \\ \hline 01 & 张三 & 男 & 01 & 办公室 \\ 02 & 李四 & 女 & 01 & 办公室 \\ 03 & 王五 & 男 & 02 & 门岗 \\ \hline \end{array}$$

4.2 交

$$R \cap S=\{t\mid t \in R \land t\in S\}$$

$$R \cap S = \begin{array}{|c|c|c|c|c|} \hline 职工号 & 姓名 & 性别 & 科室号 & 科室 \\ \hline 02 & 李四 & 女 & 01 & 办公室 \\ \hline \end{array}$$

4.3 差

$$R - S=\{t\mid t \in R \land t\notin S\}$$

$$R - S = \begin{array}{|c|c|c|c|c|} \hline 职工号 & 姓名 & 性别 & 科室号 & 科室 \\ \hline 01 & 张三 & 男 & 01 & 办公室 \\ \hline \end{array}$$

并、交、差要求两个关系具有相同的目数, 且对应属性的域相容.
相容指的是两个关系对应的列, 必须来自同一个"域", 也就是取值范围/数据类型相同, 能够放在一起比较和合并.

广义笛卡尔积

$n$ 目的关系 $R$ 和 $m$ 目的关系 $S$ 的广义笛卡尔积是一个 $n+m$ 列的元组集合.
每个元组的前 $n$ 列是关系 $R$ 的元组, 后 $m$ 列是关系 $S$ 的元组.

若 $R$ 有 $k_1$ 个元组, S 有 $k_2$ 个元组, 则关系 $R$ 和关系 $S$ 的广义笛卡尔积有 $k_1 \times k_2$ 个元组, 记作:

$$R \times S = \{ (r_1,...,r_n,S_1,...,S_m)\mid (r_1,...,r_n)\in R\land (S_1,...,S_m)\in S\}$$

$$\begin{array}{|c|c|c|} \hline 职工号& 姓名 & 性别 \\ \hline 01 & 张三 & 男 \\ 02 & 李四 & 女 \\ 03 & 王五 & 男 \\ \hline \end{array}$$

$$\begin{array}{|c|c|} \hline 科室号 & 科室名\\ \hline 01 & 办公室\\ 02 & 门岗 \\ \hline \end{array}$$

以上两个表的广义笛卡尔积是:

$$\begin{array}{|c|c|c|c|c|} \hline 职工号 & 姓名 & 性别 & 科室号 & 科室 \\ \hline 01 & 张三 & 男 & 01 & 办公室 \\ 01 & 张三 & 男 & 02 & 门岗 \\ 02 & 李四 & 女 & 01 & 办公室 \\ 02 & 李四 & 女 & 02 & 门岗 \\ 03 & 王五 & 男 & 01 & 办公室 \\ 03 & 王五 & 男 & 02 & 门岗 \\ \hline \end{array}$$

5.专门的关系运算

专门的关系运算包括选择、投影、连接、除等.

5.1 选择

选择又称为限制, 它是在关系 R 中选择出满足给定条件的元组, 记作:

$$\sigma_F (R)=\{t \mid t \in R \land F (t)='真'\}$$

其中 $F (t)$ 表示选择条件, 它是一个逻辑表达式, 取逻辑值"真"或"假", 基本形式为:

$$X_1\theta Y_1[\phi X_2\theta Y_2...]$$

$\theta$ 是比较运算符, 它可以是 $\gt,\lt,\geq,\leq,=,\neq$ ; $X_1、Y_1$ 是字段名、常量或简单函数

字段名也可以用它的序号 (如1、2、…)代替.

$\phi$ 表示逻辑运算符, 它可以是 $\land (与),\vee (或), \neg (非)$

$[\ ]$ 表示任选项, 即 $[\ ]$ 中的部分可要可不要

$...$ 表示上述格式可以重复下去.

$$\begin{array}{|c|c|c|c|c|} \hline Sno & Sname & Ssex & Sage & Sdept \\ \hline 101 & 李晨 & 男 & 18 & 信息系 \\ 102 & 王博 & 女 & 19 & 数学系 \\ 103 & 刘思思 & 女 & 18 & 信息系 \\ 104 & 王国美 & 女 & 19 & 物理系 \\ 105 & 范伟 & 男 & 19 & 数学系 \\ \hline \end{array}$$

查询数学系的学生:

$\sigma_{Sdept='数学系'} (Student)$ 或 $\sigma_{5='数学系'} (Student)$

$$\begin{array}{|c|c|c|c|c|} \hline Sno & Sname & Ssex & Sage & Sdept \\ \hline 102 & 王博 & 女 & 19 & 数学系 \\ 105 & 范伟 & 男 & 19 & 数学系 \\ \hline \end{array}$$

可以看到, 选择并不会减少列数, 只会减少行数

5.2 投影

关系 $R$ 上的投影是指从 $R$ 中选择出若干字段名以组成新的关系, 记作:
$\pi_A (R)=\{t[A]\mid t\in R\}$ , 也可以用 $\Pi_A (R)$ 表示, 叫作关系 $R$ 在属性 $A$ 上的投影

括号里 $(R)$ 也可以是复杂的条件, 但这就不是单纯的投影了, 而是先选择, 再投影, 甚至还可以先连接再选择或者先选择再连接, 最后再投影, 我们这里只提最纯粹的投影

查询学生的性别和年龄:

$\pi_{Ssex,Sage} (Student)$ 或 $\pi_{3,4} (Student)$

$$\begin{array}{|c|c|} \hline Ssex & Sage \\ \hline 男 & 18 \\ 女 & 19 \\ 女 & 18 \\ 男 & 19 \\ \hline \end{array}$$

可以看到投影的核心思路是减少列数.

切记在进行手动投影计算的时候要进行去重操作.
关系代数中的关系是集合, 因此投影后产生的重复元组会被系统自动去除, 所以投影后的行数可能减少.

5.3 连接

5.3.1 连接条件

按连接条件分, 连接也叫条件连接 或者 $\theta$ 连接, 它是指从两个关系的笛卡尔积中选取属性间满足一定条件的元组, 记作:

$$R \underset{A\theta B} \bowtie S=\{t_r t_s\mid t_r \in R\land t_s \in S \land t_r[A]\theta t_s[B]\}$$

$t_r t_s$ 就是连接的元组, 也就是将两个元组并排放在一起
$\theta$ 就是运算符

$$R =\ \begin{array}{|c|c|c|} \hline A & B & C\\ \hline a1 & b1 & 5 \\ a1 & b2 & 6 \\ a2 & b3 & 8 \\ a2 & b4 & 12 \\ \hline \end{array}$$

$$S =\ \begin{array}{|c|c|} \hline B & E \\ \hline b1 & 3 \\ b2 & 6 \\ b3 & 10 \\ b3 & 12 \\ b5 & 2 \\ \hline \end{array}$$

(1) 等值连接

等值连接就是将运算符 $\theta$ 换成 $=$, 记作:

$$R \underset{A=B} \bowtie S=\{t_r t_s\mid t_r \in R\land t_s \in S \land t_r[A]=t_s[B]\}$$

等值连接的比较条件里可以是不同名的属性列, 也可以是同名的.

也就是求 $R$ 中的属性 $A$ 等于 $S$ 中的属性 $B$ 的连接

比如:

$$R \underset{R.B=S.B} \bowtie S = \ \begin{array}{|c|c|c|c|c|} \hline A & R.B & C & S.B & E\\ \hline a1 & b1 & 5 & b1 & 3\\ a1 & b2 & 6 & b2 & 6\\ a2 & b3 & 8 & b3 & 10\\ a2 & b3 & 8 & b3 & 12\\ \hline \end{array}$$

(2) 自然连接

自然连接是一种特殊的等值连接, 它要求两个关系中有同名属性列, 并自动按所有同名属性列进行等值比较, 最后在结果中把重复的同名属性列只保留一份.

如果存在多列同名属性列, 则进行要保证所有同名属性列的值都相等

$$R \bowtie S=\{t_r t_s\mid t_r \in R\land t_s \in S \land (t_r[A]=t_s[A]\land t_r[B]=t_s[B])\land...\}$$

计算下

$$R \bowtie S =\ \begin{array}{|c|c|c|c|} \hline A & B & C & E \\ \hline a1 & b1 & 5 & 3 \\ a1 & b2 & 6 & 6 \\ a2 & b3 & 8 & 10 \\ a2 & b3 & 8 & 12 \\ \hline \end{array}$$

相同的属性 $B$ 只有 $b1,b2,b3$ 这三个相同的值

(3) 一般连接

就是非等值连接

比如求:$R \underset{A>B} \bowtie S=\{t_r t_s\mid t_r \in R\land t_s \in S \land t_r[A]>t_s[B]\}$

$$R \underset{C>E}{\bowtie} S = \ \begin{array}{|c|c|c|c|c|} \hline A & R.B & C & S.B & E \\ \hline a1 & b1 & 5 & b1 & 3 \\ a1 & b1 & 5 & b5 & 2 \\ a1 & b2 & 6 & b1 & 3 \\ a1 & b2 & 6 & b5 & 2 \\ a2 & b3 & 8 & b1 & 3 \\ a2 & b3 & 8 & b2 & 6 \\ a2 & b3 & 8 & b5 & 2 \\ a2 & b4 & 12 & b1 & 3 \\ a2 & b4 & 12 & b2 & 6 \\ a2 & b4 & 12 & b3 & 10 \\ a2 & b4 & 12 & b5 & 2 \\ \hline \end{array}$$

5.3.2 是否保留不匹配元组

按保留哪些元组来分, 可分为内连接和外连接, 外连接又分为左外连接和右外连接

• 内连接指的是只保留符合条件元组的连接
• 外连接指的是额外保留不匹配元组的连接, 不匹配的一侧用 NULL 填充
  • 左外连接指的是额外保留左侧不匹配元组的连接
  • 右外连接指的是额外保留右侧不匹配元组的连接
  • 全外连接指的是额外保留两侧不匹配元组的连接

5.4 象集

关系 $R (X,Y)$, $X$ 和 $Y$ 为属性组.

对 $X$ 上的取值 $x$ 来说, $x$ 在 $R$ 中的象集 (images set)为:

$$Y_{X=x}=\{t[Y] \mid t\in R, t[X]=x\}=\pi_Y (\sigma_{X=x} (R))$$

$Y_{X=x}$ 通常简写为 $Y_x$, 但我更喜欢写全

象集就是"选择 + 投影"的组合
$Y_{X=x}$ 先选择出 $X=x$ 的元组, 再求在 $Y$ 上的投影
就是 $X=x$ 时候的 $Y$ 列

$$\begin{array}{|c|c|} \hline X & Y \\ \hline 1 & 2 \\ 2 & 2 \\ 3 & 6 \\ \hline \end{array}$$

下面是 $Y=2$ 时的象集 $X_{Y=2}$:

$$\begin{array}{|c|} \hline X \\ \hline 1 \\ 2 \\ \hline \end{array}$$

5.5 除

给定关系 $R (X,Y)$ 和 $S (Y,Z)$, 其中 $X、Y、Z$ 为属性组.

$R$ 中的 $Y$ 和 $S$ 中的 $Y$ 不要求字段名 (属性名)一样, 域一样就行.

$$\begin{aligned} T&=R (X,Y)\div S (Y) \\ &=\{x \mid x \in \pi_X (R) \land \pi_{Y} (S) \subseteq Y_x\} \end{aligned}$$

$\pi_{Y} (S) \subseteq Y_x$ 可以理解为 $\forall y\in \pi_Y (S), (x,y)\in R$
通俗一点说:除的本质是在 $R$ 中找出所有满足条件的 $x$, 每个 $x$ 对应的 $y$ 包含所有 $S$ 中的 $y$

除运算的除数位置, 在有多余列时, 需要先做投影

那么如果R中找出一个 $x$ 对应的 $y$ 值不仅包含了 $S$ 中的 $y$, 还多出来了怎么办?

无所谓啦, 包含全部 $y$ 就可以

除运算在带有"选修了全部课程"“供应了所有零件”"拥有所有权限"这类语义的运算中有大作用.

除运算有些复杂

1. 先挑出来满足条件的 $Y$ 列
2. 然后看对应 $X$ 列的值有哪些
3. 再挨个验证 $X$ 值.

例:
R (学生,课程,教师):

$$\begin{array}{|c|c|c|} \hline 学生 & 课程 & 教师 \\ \hline 张三 & 数据库 & 王老师 \\ 张三 & 操作系统 & 李老师 \\ 张三 & 网络 & 张老师 \\ 李四 & 数据库 & 王老师 \\ 李四 & 操作系统 & 李老师 \\ 王五 & 数据库 & 王老师 \\ 王五 & 操作系统 & 李老师 \\ 王五 & 网络 & 张老师 \\ 赵六 & 数据库 & 王老师 \\ 赵六 & 网络 & 张老师 \\ \hline \end{array}$$

S (课程,教师,学期):

$$\begin{array}{|c|c|c|} \hline 课程 & 教师 & 学期 \\ \hline 数据库 & 王老师 & 2023春 \\ 操作系统 & 李老师 & 2023秋 \\ 网络 & 张老师 & 2024春 \\ \hline \end{array}$$

$$R \div S = \{张三,王五\}$$

6.实践

$$\begin{aligned} &S\{Sno,Sname,Ssex,Sage,Sdept\}\\ &C\{Cno,Cname\}\\ &SC\{Sno,Cno,Degree\} \end{aligned}$$

• 查询选修 $C3$ 号课程的学生的学号和成绩.
  $\pi_{Sno,Degree} (\sigma_{Cno='C3'} (SC))$

• 查询选修 $C4$ 号课程号的学生学号和姓名.
  $\pi_{Sno,Sname} (\sigma_{Cno='C4'} (S\bowtie SC))$

• 查询选修课程名为 $数据结构$ 的学生学号和姓名.
  $\pi_{Sno,Sname} (\sigma_{Cname='数据结构'} (S\bowtie SC\bowtie C))$

• 查询选修 $C1$ 或 $C4$ 号课程的学生学号.
  $\pi_{Sno} (\sigma_{Cno='C1'\vee Cno='C4'} (SC))$