输入关系
先从保存选课记录的 SC 开始
- 01对一个查询指出输入关系、运算符、输出中的行与列，以及回答了什么问题
- 02判断并、差、交的相容条件，并预测笛卡儿积的结果规模
- 03用选择、投影和连接表达行筛选、列筛选与跨关系组合
- 04（可选）用象集覆盖解释“满足全部指定条件”的除运算
- 05用 \(R_1,R_2,\ldots\) 构造综合表达式，并检查每张结果表的列和行
DBPA · 2.4
关系代数
输入、处理、输出
VER. 2608
Built with impress.js
DBPA | CH02 | 2.4
学习目标
选择运算，并说清每个中间结果有哪些列、每行代表什么
2/21
LEARNING OBJECTIVES
DBPA | CH02 | 2.4 | 2.4.1
追踪一次查询
筛选 SC 得到 \(R_1\)，保留 Sno 得到 \(R_2\)；如果结果非空则继续连接 Student
SC→筛 81002→取 Sno→连 Student→取 Sname运算步骤
筛选课程号、保留学号、匹配学生姓名
输出关系
每一步都产生一个关系，能够交给下一步
Takeaway
\(R_1\) 作为投影的输入，\(R_2\) 作为连接的输入
3/21
ALGEBRA ELEMENTS
DBPA | CH02 | 2.4 | 2.4.1
同一个关系运算，两个分类标签
是集合运算还是关系运算？是基本运算还是导出运算
集合运算与关系运算
并、差、交、笛卡儿积从元组集合出发；选择、投影、连接、除还会使用条件或属性
基本运算与可导出运算
并、差、笛卡儿积、选择、投影是基本运算；交、连接、除可由它们表达
Takeaway
选择是“专门且基本”，连接是“专门且可导出”；两条分类轴彼此独立
4/21
OPERATION CLASSIFICATION
DBPA | CH02 | 2.4 | 2.4.1
并、差、交运算需要先检查是否相容
并、差、交的两个输入必须属性数相同、对应位置同域
相同的目
两个关系具有相同的属性数
对应位置同域
相应位置的属性来自同一个域
结果结构一致
保留相应属性结构；不要求属性名相同
5/21
SET COMPATIBILITY
DBPA | CH02 | 2.4 | 2.4.1
用并、差和交回答三个问题
合并两份名单、找只在第一份的人、找两份都出现的人
| 运算 | 表达式 | 结果含义 |
|---|---|---|
| 并 | \(R \cup S\) | 属于 \(R\) 或属于 \(S\) 的元组 |
| 差 | \(R - S\) | 属于 \(R\) 而不属于 \(S\) 的元组 |
| 交 | \(R \cap S\) | 同时属于 \(R\) 和 \(S\) 的元组 |
Takeaway
差运算有方向；并、差和交的结果都不改变元组的属性结构
6/21
SET OPERATIONS
DBPA | CH02 | 2.4 | 2.4.1
笛卡儿积：组合两个关系的所有元组
笛卡儿积不要求两个关系相容，\(R\) 的每个元组都与 \(S\) 的每个元组组合
$$R \times S$$
结果规模与结构
若 \(R\) 有 \(k_1\) 个元组，\(S\) 有 \(k_2\) 个元组，结果有 \(k_1 \times k_2\) 个元组；结果属性数为 \(R\) 与 \(S\) 的属性数之和，同名属性用关系名区分
业务意义
结果先包含匹配与不匹配的所有行对，通常还要用条件筛掉不需要的配对
7/21
CARTESIAN PRODUCT
DBPA | CH02 | 2.4 | 2.4.2
选择 Selection：找出信息管理专业学生
选择判断 \(R\) 中每个元组，只保留使 \(F(t)\) 为真的元组
$$\sigma_F(R)$$
结构变化
结果保留 \(R\) 的全部属性，只减少元组
Student 关系
\(\sigma_{\mathrm{Smajor}=\text{信息管理与信息系统}}(\mathrm{Student})\) 找出符合专业条件的学生
8/21
SELECTION
DBPA | CH02 | 2.4 | 2.4.2
投影 Projection：列出学生主修专业
投影只保留指定属性列；取消部分列后，完全相同的元组只保留一次
$$\Pi_A(R)$$
Student 关系
\(\Pi_{\mathrm{Sno},\mathrm{Smajor}}(\mathrm{Student})\) 只保留学号和主修专业
\(\Pi_{\mathrm{Smajor}}(\mathrm{Student})\) 只保留不同的主修专业
9/21
PROJECTION
DBPA | CH02 | 2.4 | 2.4.2
选择与投影
先判断要减少行还是减少列
| 运算 | 保留什么 | 典型问题 |
|---|---|---|
| 选择 | 满足条件的元组 | 哪些学生属于信息管理专业 |
| 投影 | 指定的属性列 | 需要显示学生的哪些信息 |
| 选择后投影 | 满足条件的行中的指定列 | 这些学生的学号和姓名是什么 |
10/21
SELECTION AND PROJECTION
DBPA | CH02 | 2.4 | 2.4.2
找出学号相同的 Student 与 SC 元组
连接从候选组合中保留学号匹配的元组
关系与元组
\(t_{\mathrm{Student}} \in \mathrm{Student}\)、\(t_{\mathrm{SC}} \in \mathrm{SC}\) 分别表示两个输入关系中的一行
属性组
\(t_{\mathrm{Student}}[\mathrm{Sno}]\)、\(t_{\mathrm{SC}}[\mathrm{Sno}]\) 取出两行中用来比较的学号分量
元组连接
学号匹配时，把两行的属性串接为更长的结果元组
11/21
OPERATION NOTATION
DBPA | CH02 | 2.4 | 2.4.2
匹配学号，再组合两边属性
\(A\)、\(B\) 分别是 \(R\)、\(S\) 中列数相等且值可比较的属性组，\(\theta\) 是比较运算符
$$R \underset{A \,\theta\, B}{\bowtie} S$$
θ 与等值连接
\(\theta\) 连接从 \(R \times S\) 中保留满足 \(t_R[A] \,\theta\, t_S[B]\) 的元组；\(\theta\) 为等号时是等值连接
自然连接
同名属性等值匹配，并删除重复的连接列
12/21
JOIN
DBPA | CH02 | 2.4 | 2.4.2
SC 连接后取得学生姓名和课程名
某个关系中不存在的属性，往往需要从其他关系取得
没有选课的 Student 或没有学生选修的 Course 成为悬浮元组
| 连接 | 匹配条件 | 结果关注 |
|---|---|---|
Student 与 SC | \(\mathrm{Student}.\mathrm{Sno}=\mathrm{SC}.\mathrm{Sno}\) | 补出 \(\mathrm{Sname}\) |
| 悬浮元组 | 连接条件属性上没有匹配 | 普通自然连接中舍弃 |
| 外连接 | 保留悬浮元组 | 未匹配的属性填入 \(\mathrm{NULL}\) |
Takeaway
无匹配元组是悬浮元组，普通自然连接会舍弃它们；外连接保留悬浮元组
13/21
JOIN RESULT
DBPA | CH02 | 2.4 | 2.4.2
等值连接与自然连接的差异在结果结构
两者都按相等条件匹配，但自然连接还处理重复属性列
| 类型 | 匹配条件 | 结果列结构 |
|---|---|---|
| \(\theta\) 连接 | \(A \,\theta\, B\)，\(\theta \in \{>,\ge,<,\le,=,\ne\}\) | 保留两个输入关系的属性列 |
| 等值连接 | \(A = B\) | 保留两个输入关系的属性列 |
| 自然连接 | 同名属性等值匹配 | 删除重复的同名连接列 |
Takeaway
等值连接只按相等匹配；自然连接还删除重复的同名连接列
14/21
JOIN VARIANTS
DBPA | CH02 | 2.4 | 2.4.2
除 Division：检查课程集合是否覆盖要求
学生的已修课程象集覆盖全部指定课程时，该学生进入结果
$$R(X,Y) \div S(Y,Z) = P(X)$$
\(R\) 与 \(S\) 中参与比较的属性组列数相等、对应位置同域；属性名可以不同
象集
固定 \(x\)，\(Y_x = \{t[Y] \mid t \in R \land t[X] = x\}\)
覆盖
若 \(\Pi_Y(S) \subseteq Y_x\)，则 \(x\) 进入结果 \(P\)。例如目标集合为 \(\{y_1,y_2\}\) 时，只有象集同时包含 \(y_1\) 和 \(y_2\) 的 \(x\) 入选
15/21
DIVISION
DBPA | CH02 | 2.4 | 2.4.2
案例：找出选修全部指定课程的学生
“全部”决定了查询不能只筛选其中一门课程
01
指定集合
\(K(\mathrm{Cno}) = \{81001,81003\}\)
02
输入关系
\(R(\mathrm{Sno},\mathrm{Cno}) = \Pi_{\mathrm{Sno},\mathrm{Cno}}(\mathrm{SC})\)
03
除运算
\(R \div K \to P(\mathrm{Sno})\)
04
结果
只保留同时拥有 \(K\) 中两门课程的 \(\mathrm{Sno}\)；\(P(\mathrm{Sno}) = \{20180001,20180002\}\)
16/21
DIVISION CASE
DBPA | CH02 | 2.4 | 2.4.2
示例：逐步构造选修 81002 的学生姓名
每一步先给结果命名，再写清它保留哪些列以及其中一行代表什么
01筛选
筛选 SC
\(R_1 = \sigma_{\mathrm{Cno}=81002}(\mathrm{SC})\)，模式与 SC 相同，表示选修 81002 的记录
02
只留学号
\(R_2(\mathrm{Sno}) = \Pi_{\mathrm{Sno}}(R_1)\)，表示这些记录中的学生学号
03连接
连接 Student
\(R_3 = R_2 \Join \mathrm{Student}\)，按同名 Sno 匹配，模式与 Student 相同
04
只留姓名
\(R_4(\mathrm{Sname}) = \Pi_{\mathrm{Sname}}(R_3)\)，得到最终姓名关系
17/21
COMPOSITE QUERY
DBPA | CH02 | 2.4 | 2.4.2
示例：为业务问题选择最小关系运算
只要学号不连 Student；需要姓名按 Sno 连接；要求“全部”再检查象集覆盖
| 业务问题 | 核心运算 | 结果说明 |
|---|---|---|
| 选修 81002 的学生学号 | 选择、投影 | 只保留满足条件的 \(\mathrm{Sno}\) |
| 选修 81002 的学生姓名 | 选择、投影、连接 | 将 \(\mathrm{Sno}\) 与 \(\mathrm{Student}\) 组合 |
| 同时选修 81001 和 81003 | 分别选择并投影两门课程的 \(\mathrm{Sno}\)，再求交 | 只保留两次结果共有的 \(\mathrm{Sno}\) |
| 选修全部指定课程 | 投影、除；若要姓名再连接 | 除先得到象集覆盖全部课程的 \(\mathrm{Sno}\) |
18/21
QUERY JUDGMENT
DBPA | CH02 | 2.4
练习：为一个新查询画出中间关系
任选“集齐道具的玩家”或“买齐指定商品的用户”，画中间表并合成表达式
写出输入与条件
列出需要的关系和属性，判断是否需要相容关系、匹配条件或目标集合
逐步命名结果
用 \(R_1,R_2,\ldots\) 记录每一步保留的行、列或组合，并写出结果模式
解释业务语义
写出中间结果的一行代表哪个玩家、用户、道具或商品；遇到“全部”时，明确谁拥有的集合必须包含哪份要求清单
Takeaway
给中间结果表命名，写列和行的含义，把 \(R_1,R_2,\ldots\) 合成关系代数表达式
19/21
SECTION REVIEW
DBPA | CH02 | 2.4
本节思维导图
20/21
KNOWLEDGE MAP
DBPA | CH02 | 2.4
本节问题
- 01并、差、交为什么要求相容？笛卡儿积的输入条件和结果规模有何不同？
- 02选择与投影分别怎样改变行和列？为什么投影
Smajor后要去重？ - 03自然连接怎样处理同名列？普通连接与外连接怎样处理悬浮元组？
- 04除运算中参与比较的属性组需满足什么条件？为什么检查 \(\Pi_Y(S) \subseteq Y_x\)？
- 05把“选修 81002”改成“选修全部指定课程并返回姓名”，怎样重组选择、投影、连接和除？请写出各中间关系的模式与语义
21/21
SECTION QUESTIONS