数据库关系代数

1. 传统的关系运算

传统的关系运算起源于数学的集合论

  1. 笛卡尔积运算
  2. 差运算
  3. 交运算

  4. 并运算

    2. 专门的关系运算

    数据库中特有的运算规则

  5. 选择

  6. 投影
  7. 连接
  8. 除运算

    2.1 关系运算中的基础概念

    在学习关系代数的时候，脑海中要时刻拥有一张表格，还有表格的一些参数，表格如下：
    image.png

    比如说我们每个人都见过成绩单，牢记以下的比喻

    • R（关系模式）就是一张表格（成绩单）。
    • R[A1, A2, A3,…Ai] = R[语文，英语，数学……学科]
    • t 为某个同学
    • t [Ai] 就可以当作某个同学的某一门成绩

例如：R为期中考试全班的成绩单，R[A1, A2, A2…Ai]为考试所有科目，t 代表了张三这个人，t[Ai]代表了张三某门课程的考试成绩。

image.png

  • A不再是单独的一个属性，A可以代表一个或者多个属性
  • t[A]也不再是单独的某个属性分量，A代表多少个属性，t[A]就可以代表多少个属性分量
  • 做一个比喻，A再也不单独是某个学科，而是可以代表一科或者多科学科
  • t[A]也就不当作某个同学的一门成绩，而是可以当成某个同学的多门成绩，具体看A代表了多少学科
  • A（头上一横……）就代表了除了A代表的学科以外的所有学科

2.2 元组的连接

image.png
通过连接得到的这个元组有以下属性

  • 前 m 个分量来自于 R 表中的一个 m 元组

  • 后 n 个分量来自于 S 表中的一个 n 元组

    2.3 象集(除法运算重要工具)

    给了我们一个关系R（X，Y），X和Y都代表了一个属性组，也就是X和Y都是属性的数量都是一列到多列

  • 从上面的比喻来说，X是成绩单一门课程的成绩或者多门课程成绩，Y也是一门课程的成绩或者多门课程的成绩；

  • 当t[X] = x时: x在R中的象集为:Yx = {t[Y] | t ∈ R, t[X] = x}；
  • 公式比较难懂，但是其实本身很简单，也十分容易寻找。

例如：
image.png

3. 数学上的运算

3.1 并运算

能够使用并运算的两个前提：

  1. 两张表格的元一样； (解释：两张表格列数一样)
  2. 相同的属性取自同一个域。（解释：属性都一样）

image.png
如图，在合并了之后呢，两个原始的表格和合并之后的新表格元数一样（列数一样）

  • 如果两个表之间有重复的元组，并运算会做去重处理，类似于集合的之间的并集

    3.2 差运算

    能够使用差运算的两个前提：
  1. 两个表格列数一样；
  2. 两个表格的属性都相同。

两个表进行了差运算之后，都仍然是n列。
S-R表：S表中有任意一个元组和R表的一样，S表就去掉这个元组
R-S表：R表中有任意一个元组和S表的一样，R表就去掉这个元组
简言之：就是一张表，嫌弃另外一张表，我身上有那里和你一样，我改还不行嘛！
image.png

3.3 交运算

交运算能够使用的两个前提：

  1. 表格的列数相同
  2. 表格的属性都相同

简言之：两个表格进行并运算，就是把两个表格中一样的元素找出来，找出两张表格的共性
image.png

3.4 笛卡尔积（万能运算）

没有任何使用限制，万物皆可笛卡尔积。
R表：n元关系，k1个元组(k1行，n列)
S表：m元关系，k2个元组(k2行，m列)
R表和S表进行笛卡尔积
得到一个(k1 k2)元，(n + m)列的新表，如下：
image.png
→ 两个表进行了*笛卡尔积运算之后
image.png
以上就是所有的数学关系代数运算。

4. 关系运算

4.1 表格简介

整个关系代数的学习需要使用学生课程选课数据库，需要熟悉以下表格：
image.png
image.png
image.png

4.2 选择（Selection）

  • 选择也称之为限制；
  • 选择是针对的元组进行选择，选择出满足条件的元组。

选出来的结果是一行行的
关系代数 - 图13

4.2.1 选择查询（例1）

查询全体信息系(IS)的学生所有信息

  1. 信息系在Student表格中有，所有我们的R表的位置是Student表格的属性集合为{“Sno”, “Sname”, “Ssex”, “Sage”, “Sdept”}；
  2. 我们需要的条件是F（Sdept = IS）。

→ 所以题目的答案为：
关系代数 - 图14
→ 查询出来的结果为：
image.png

4.2.2 选择查询（例2）

查询年龄小于20岁的学生所有信息

  1. 年龄在Student表格中存在，所以我们现需要查询的表格为Student表格；
  2. 我们需要的条件是年龄小于20岁 F(Sage < 20)。

→ 所以题目的答案为：
关系代数 - 图16
→ 查询出来的结果为：
image.png
总结：选择运算是查询符合条件的行。

4.3 投影(Projection)

我们可以看见，使用选择运算的时候，一行的所有全部信息我们都获取了，比如我查询了小于20岁的学生信息，我连学生的名字，学号，性别所有的信息都知道了，因为选择是选择出一行一行的结果，那么如果我只想知道小于20岁的学生名字，其他学号，学院等等的信息我都不想知道该怎么办呢？这里就需要投影运算。
投影运算是针对属性进行选择的运算，也就是投影是选择出符合条件的一列，并且会自动取消某些行（后面会举例说明）。
关系代数 - 图18

4.3.1 投影查询（例1）

查询学生的姓名和学生的系，从需要查询的这个条件可以看出来我们需要查询的是姓名列和学生所在系列。

  1. 学生的姓名和所在系在Student表格中，所以我们需要在Student表格中进行查询；
  2. 需要查询的属性为学生的姓名和学生的系。

→ 题目的答案为：(Sname 和 Sdept之间用逗号分隔)
关系代数 - 图19
→ 最终我们查询获取的答案如下：
image.png

4.3.2 投影查询（例2）

查询学生表Student中有那些系

  1. 首先，我们需要在Student表中进行查询；
  2. 我们需要查询的属性为系。

关系代数 - 图21
可是我们最终查询出来的答案应该是什么样子的呢？
图中演示的就是选择运算的自动去重功能。
image.png
总结：投影查询得到的是一列

4.3.3 选择和投影配合使用（重点）

选择查询是挑选出符合条件的行，投影查询是选择想要的列，那么如果想定位到一个具体的属性，就需要两种查询方式一起使用。

如图：
image.png
当我们需要全体数学学院的学生姓名，注意，只需要学生的姓名，其他的信息都不需要。

  • 先用选择运算将所有的数学学院的学生挑选出来

image.png
→ 在选择运算的基础上，把需要符合条件的姓名通过投影运算查询出来。

image.png
→ 全体数学学院的学生的姓名（交叉区域）：言小白，李白。

4.4 连接（Join）

连接的含义：从两个关系的笛卡尔积中选择属性之间满足一定关系的元组
解释：在两张表的笛卡尔积后得到的那张大表中再次选取一些符合我们条件的元组
多种符号：不同的连接方式对应的符号也有一些细微的差别
关系代数 - 图26

4.4.1 非等值连接

非等值连接就是条件连接，需要将两个表格按照条件连接起来
第一步：
image.png
第二步：
image.png
第三步：
image.png
因为所有需要挑选的元组都挑选完毕，所以最终的结果如下图：
image.png

4.4.2 等值连接

等值连接是一种特殊的一般连接

  • 两个表需要有相同的属性列

下面通过具体的题目来进行了解
image.png
第三步：
image.png
最终的结果为：
image.png

4.4.3 自然连接（特殊的等值连接）

自然连接是一种特殊的等值连接

这里我们发现了等值连接的一个缺点，R.B和S.B属性是相等的，而我们只需要其中一列就可以，所以R.B和S.B属性只需要保留任意一列就可以了。
换句话说，等值连接因为属性重复而造成了额外的空间浪费，所以我们需要使用自然连接来解决这个问题（去掉重复的列）。
image.png

4.4.4 外连接

我们从自然连接中又发现了一个问题，如下图：
image.png
图中标记为红色的地方：
在做等值连接时由于彼此之间没有对应的元组（彼此之间特有的元组，我有的你没有，或者你有的我没有，这种情况肯定不会相等），在自然连接和等值连接的时候都会被丢弃，这种连接叫做内连接。
而有时候我们需要保留一张表中这种特有的元组，这些元组不能被丢弃，所以需要使用与内连接相反的连接——外连接来解决特有的元组被丢弃的问题。
外连接：把R表和S表被丢弃的元组捡了回来，并且在最终连接的表中没有的值用NULL替代，最终结果如下
image.png

  • 左外连接：因为R表在左边，所以最终的结果只保留R表中被丢弃的特有元组，S表的特有元组仍然丢弃
  • 右外连接：因为S表在右边，所以最终的结果只保留S表中被丢弃的特有元组，R表的特有元组仍然丢弃

    4.4.5 例题

    很多时候需要查询的数据分布在两个表格甚至多个表格中，使用连接将表格连接在一起进行查询是十分常用的操作

有表格信息如下：
关系代数 - 图37
一、查询所有学生的学号，姓名，课程号以及成绩

  • 需要查询的信息分布 S 表和 SC 表中
  • 两张表拥有相同的属性，即Sno，所以连接条件就是 S.sno = SC.sno

答案：
image.png
上面用的是等值连接，当然，使用自然连接也是正确的，自然连接会自动找到相同的属性，并且默认条件就是相同属性的值相同，自然连接就是特殊的等值连接
二、查询CS系的学生的学号，课程号，以及成绩

  • 需要查询的信息分布在 S 表和 SC 表中
  • 两张表相同的属性是 Sno，所以依靠 Sno 将两张表连接
  • 需要对连接后的表格进行选择，条件是 Sdept = ‘CS’

答案：
image.png
其实这道题可以再优化一下
因为我们只需要 S 表中属于CS系的，没必要将 S 表的所有系的学生都和 SC 表连接起来
所以可以先把 S 表中 CS 系的学生挑选出来，然后再进行连接操作。
优化后的答案：
image.png
很明显优化后的结果挑选速度更快，占用空间更小。

4.5 除运算

一些学习上的感悟：除运算在关系代数中是一个十分强大的工具，但是除法运算的定义看起来十分的晦涩难懂，可定义又是十分重要的，相信很多人在看教科书的过程中，每次看定义这块的时候都会很懵，然后看了例子之后就会理解定义的意思，但是懂了定义的大意之后很少就会有人再回头去理解定义，例子固然是用来让我们可以清晰的理解定义的大意的，但是我们通过例子理解定义的大意之后，我们仍然要回归定义，只有这样我们才能学得深入（个人对于学习上的一些理解，欢迎一起交流）

4.5.1 除运算基本概念

假设我们手里面有一张数据库如下：
image.png
现在我们有一个问题，就是我们想要找出学习最积极的那位学生，也就是选修了所有课程的那个学生，先暂时放弃除法运算，以我们最朴素的情感，用自己的逻辑来解决这道题目，按照自己的想法，就像设计一个程序一样，需要几步做出这个问题。
以下是按照我自己的想法：

  • 首先，把SC表拆了，把每个学生单独做成一个表，如下：

image.png
然后问题就变成了拆开之后的表格和C表一一比对，找出拆开之后的三个表格中的Course属性和C表一模一样（也就是拆开之后包含了所有课程的表），然后找出那个人是谁，然后问题就解决了。
image.png
实际上，我们的除法运算就是这个逻辑，但是除法运算的更为严谨，以下是除法运算的的步骤（SC ÷ C），这里我们仍然采用我们上面使用的数据库，直接说结论(SC ➗ C)能找出答案

  • 第一步：找出C表中和SC表中相同的属性，也就是C属性，对C属性做投影操作（也就是找出总的课程有多少门）
  • 第二步：找出SC表中和C表不相同的属性，也就是S属性，也对S属性做投影操作（找出一共有几个学生）
  • 第三步：找出SC表中S的象集（每个学生分别都选了些什么课）

image.png

  • 最后一步就是进行比对，只有张三的象集包含了所有C表中的所有课程，所以(SC ➗ C = 张三）

简单的总结，当需要查询选取所有课程的学生的名单时

  • 需要获取所有的课程到底是那些课程，所以对C表进行投影；
  • 需要获取选课的学生有那些，所以需要对SC表的S进行投影；
  • 需要知道每个学生都选择哪些课程才能知道那个学生全选了课程，所以还需要的数据是SC表中，S的象集；
  • 最后，需要进行比对操作，看看那个学生的象集包含了C表的投影。

除法运算像一个函数，封装了以上的所有功能，我们调用这个函数的时候，把正确的参数放进去，就可以得到我们想要的答案。

4.5.2 例题

S表 ：
image.png
C 表：
image.png
SC 表：
image.png
题目如下：
查询选修了所有课程的学生姓名，年龄

  1. 对 C 表进行投影，找出所有的课程编号
  2. 用 SC 表 除 C表，找出选了C表中所有课程的学生
  3. 将符合条件的学生的姓名和年龄找出来

答案：
image.png
其中，第2步的除法运算详细过程如下：
image.pngimage.png
image.png
当我们看完结论，做完题目，再回头看定义，除法运算的定义如下：
image.png

关系代数经典题目

题目一

设数据库中有三个基本表：
S（SNo(学号)，SName(姓名)，SSex(性别)，SPro(专业方向)）
SC（SNo(学号)，CNo(课程号)，Grade(成绩)）
C（CNo(课程号)，CName(课程名)，CPre(先行课)，CCredit(学分)）
试用关系代数表达式表示下列查询语句：
1.找出选修网络方向女同学名单
σSPro =”网络”∧ SSex =”女”(S)
2.求选修 15164 课程的学生姓名和专业方向
∏SName, SPro(σCNo=”15164”(S⋈SC))
3.求选修数据库原理与应用课程的学生姓名
∏SName(σCName=”数据库原理与应用”(C)⋈SC⋈S)
4.同时选修人工智能及编译技术的学生名单
S⋈(∏SName, CNo(SC)÷∏CNo(σCName =”人工智能”∨ CName=”编译技术”(C)))
或
∏Smame,CNo(S⋈SC)÷∏CNo(σCName =”人工智能”∨ CName=”编译技术”(c))
5.没有被任何人选修的课程名
∏CName(C⋈(∏CNo(C)-∏CNo(SC)))
或
∏cname(C)-∏cname(C⋈SC)
6.没有选修任何课程的学生性别和姓名
∏SName, SSex(S⋈(∏SNo(S)-∏SNo(SC)))
或
∏SName, SSex(S)-∏SName, SSex(S⋈SC)
7.至少选修了 002 号学生选修的全部课程的学生学号
∏SNo,CNo(SC)÷∏CNo(σSno=”002”(SC))
或
∏Sno((∏Sname,CNo(S⋈SC)÷∏CNo(σSNo=”002”(SC))⋈S))
8.求所有课程被选修的情况，列出课程号、课程名、先行课、学分、学号和成绩
C⋊SC
9.求每个学生没有选修的课程，列出学号、课程号
∏SNo, Cno(S×SC)-∏SNo, Cno(SC)

题目二

设学生参加科研训练项目的数据库包含如下关系模式:
学院(D)(学院代码 Dno，学院名称 Dname)
学生(S)(学号 Sno，姓名 Sname，性别 Sex，联系方式 Tel，学院代码 Dno)
项目(P)(项目编号 Pno，项目名 Pname，立项年份 Year，负责人 Sno，级别 level， 资助金额 Funding，学院代码 Dno)
参与(S_P)(学号 Sno，项目编号 Pno，承担任务 task)
其中，项目负责人是负责该项目的学生学号。
1.查询参与过“旅行足记”项目的学生学号和姓名；
∏S.SNo,S.SName(σP.PName=”旅行足迹”(S⋈S_P⋈P))
2.查询没有参与过任何项目的学生学号和姓名；
∏S.SNo,S.SName(S)-∏S.SNo,S.SName(S⋈S_P)
3.查询参与过计算机学院 2016年立项的所有国家级项目的学生姓名和联系方
式；
∏S.SName,S.Tel((∏S_P.SNo,S_P.PNo(S_P)÷∏P.PNo(σP.level=”国家级”ᴧP.year=”2016”ᴧD.Dname=”计算机”(P⋈D)))⋈S)