关于后端:数据库系统概论王珊第九章关系查询处理和关系优化第三节查询优化之代数优化

• pdf 下载：明码 7281
• 专栏目录首页：【专栏必读】（考研复试）数据库系统概论第五版（王珊）专栏学习笔记目录导航及课后习题答案详解

留神：

• 关系代数无关符号，大家可能又不相熟了，点击跳转：（数据库系统概论 | 王珊）第二章关系数据库 - 第四节：关系代数

在（数据库系统概论 | 王珊）第九章关系查询处理和关系优化 - 第一节：查询处理中讲到过：SQL 语句通过查问剖析，查问查看后变换为查问树，它是关系代数表达式的外部示意 。本节介绍查问优化之代数优化， 它是基于关系代数等价变换规定的优化办法

• 两个关系表达式 $R_{1}$ 和 $R_{2}$ 是等价的，能够记为 $R_{1} \equiv R_{2}$

一：关系代数表达式等价变换规定

• 为了能不便浏览，就没用截图。手都麻了🤮（动动手点个赞吧🥳）

（1）连贯、笛卡尔积、并、交的交换律

笛卡尔积

$$R×S \equiv S×R$$

并
$$R \cup S \equiv S \cup R$$

交

$$R \cap S \equiv S \cap R$$

连贯

$$R \underset{F}{\bowtie} S \equiv S \underset{F}{\bowtie} R、
R\bowtie S \equiv S\bowtie R$$

（2）连贯、笛卡尔积、并、交的结合律

笛卡尔积

$$(R×S) ×T\equiv R×(S×T)$$

并
$$(R \cup S)\cup T \equiv R \cup (S\cup T)$$

交

$$(R \cap S)\cap T \equiv R \cap (S\cap T)$$

连贯

$$(R \underset{F}{\bowtie} S) \underset{F}{\bowtie} T \equiv R \underset{F}{\bowtie} (S \underset{F}{\bowtie} T) $$
$$(R\bowtie S) \bowtie T \equiv R\bowtie (S \bowtie T)$$

（3）投影的串接定律

关系的两次投影操作能够合并为一次实现（反过来就是合成）

$$\Pi_{A_{1},A_{2},…,A_{n}}(\Pi_{B_{1},B_{2},…,B_{m}}(E)) \equiv \Pi_{A_{1},A_{2},…,A_{n}}(E)$$

• $E$ 是关系代数表达式
• $A_{i}(i=1,2,..,n)，B_{j}(j=1,2,..,m)$ 是属性名。并且 $\{{A_{1},A_{2},…,A_{n}} \}$ 形成 $\{{B_{1},B_{2},…,B_{m}} \}$ 的子集

（4）抉择的串接定律

抉择的两次投影操作能够合并为一次实现（反过来就是合成）

$$\sigma_{F1}(\sigma_{F2}(E)) \equiv \sigma_{F1\land F2}(E)$$

（5）抉择与投影的交换律

$$\sigma_{F}(\Pi_{A_{1},A_{2},…,A_{n}}(E)) \equiv \Pi_{A_{1},A_{2},…,A_{n}}(\sigma_{F}(E))$$

• 假如：抉择条件 $F$ 只波及属性 ${A_{1},A_{2},…,A_{n}}$

$$\Pi_{A_{1},A_{2},…,A_{n}}(\sigma_{F}(E)) \equiv \Pi_{A_{1},A_{2},…,A_{n}}(\sigma_{F}(\Pi_{A_{1},A_{2},…,A_{n},B_{1},B_{2},…,B_{m}}(E)))$$

• 假如：$F$ 中有不属于 ${A_{1},A_{2},…,A_{n}}$ 的属性 ${B_{1},B_{2},…,B_{m}}$

（6）抉择与笛卡尔积的交换律

对于 $\sigma_{F}(E_{1}×E_{2})$，有如下等价

①

$$\sigma_{F}(E_{1}×E_{2}) \equiv \sigma_{F}(E_{1})×E_{2}$$

• 假如 ： 抉择条件只与其中的一个关系无关，应该对那个关系先做抉择，而后再做笛卡尔积。例如下面 $F$ 中波及的属性都是 $E_{1}$ 中的属性

②

$$\sigma_{F}(E_{1}×E_{2}) \equiv \sigma_{F_{1}}(E_{1})×\sigma_{F_{2}}(E_{2})$$

• 假如 ： 抉择条件与两个关系都无关，应该先别离做抉择，而后再做笛卡尔积。例如下面 $F=F_{1} \land F_{2}$，并且 $F_{1}$ 中只波及 $E_{1}$ 中的属性，$F_{2}$ 中只波及 $E_{2}$ 中的属性

③

$$\sigma_{F}(E_{1}×E_{2}) \equiv \sigma_{F_{2}}(\sigma_{F_{1}}(E_{1})×E_{2})$$

• 假如：如果抉择条件与某一部分关系无关，那么也应该先对那个关系做局部抉择，而后做笛卡尔积，最初做抉择。例如下面 $F=F_{1} \land F_{2}$，并且 $F_{1}$ 中只波及 $E_{1}$ 中的属性，$F_{2}$ 中波及 $E_{1}$ 和 $E_{2}$ 中的属性

（7）抉择与并的分配律

$$\sigma(E_{1} \cup E_{2}) \equiv \sigma_{F}(E_{1}) \cup \sigma_{F}(E_{2})$$

• 假如：$E=E_{1} \cup E_{2}$，$E_{1}$ 和 $E_{2}$ 有雷同的属性名

（8）抉择与差运算的分配律

$$\sigma(E_{1} – E_{2}) \equiv \sigma_{F}(E_{1}) – \sigma_{F}(E_{2})$$

（9）抉择对天然连贯的分配律

$$\sigma_{F}(E_{1} \bowtie E_{2}) \equiv \sigma_{F}(E_{1}) \bowtie \sigma_{F}(E_{2})$$

• $F$ 只波及 $E_{1}$ 和 $E_{2}$ 的 公共属性

（10）投影与笛卡尔积的分配律

$$\Pi_{A_{1},A_{2},…,A_{n},B_{1},B_{2},…,B_{m}}(E_{1}×E_{2}) \equiv \Pi_{A_{1},A_{2},…,A_{n}}(E_{1}) × \Pi_{B_{1},B_{2},…,B_{m}}(E_{2})$$

• $A_{1},A_{2},…,A_{n}$ 是 $E_{1}$ 的属性
• $B_{1},B_{2},…,B_{m}$ 是 $E_{2}$ 的属性

（11）投影与并的分配律

$$\Pi_{A_{1},A_{2},…,A_{n}}(E_{1} \cup E_{2}) \equiv \Pi_{A_{1},A_{2},…,A_{n}}(E_{1}) \cup \Pi_{A_{1},A_{2},…,A_{n}}(E_{2})$$

二：查问树的启发式优化

• 这是对关系代数示意的查问树进行优化的办法

（1）典型的启发式规定

典型的启发式规定

• 【规定 1】抉择运算应尽可能先做 ：这是为了 缩小两头后果的规模
• 【规定 2】投影和抉择运算同时进行 ：这是为了 防止反复扫描
• 【规定 3】将投影运算与其前后的双目运算联合起来 ：这是为了 防止反复扫描
• 【规定 4】把某些抉择运算和其后面的笛卡尔积联合起来成为一个连贯运算 ：这是为了 缩小两头后果的规模
• 【规定 5】提取公共子表达式（公因子）：这是为了 保留计算结果，防止反复计算

（2）实现算法

• 该算在遵循启发式规定，并利用关系代数表达式等价变换规定来优化关系表达式
• 该算法的输出和输入都是查问树（别离对应待优化和优化的关系表达式）

算法步骤

• 【步骤 1】合成抉择运算 ：这是为了 便于不同的抉择运算沿树的不同分枝向树叶挪动，始终挪动到与这个抉择条件相干的关系处，使抉择尽可能先做。$\sigma_{F_{1} \land F_{2} \land … \land F_{n}} (E)\Rightarrow \sigma_{F_{1}}(\sigma_{F_{2}}(…(\sigma_{F_{n}}(E))…))$
• 【步骤 2】通过替换抉择运算，将每个抉择运算尽可能挪动到叶端 ：利用 规定 4~9尽可能把抉择挪动到树的叶端
• 【步骤 3】通过替换投影运算，将每个投影运算尽可能挪动到叶端 ：利用 规定 3、11、10、5尽可能把投影挪动到树的叶端
• 【步骤 4】合并抉择和投影的串接 ：利用 规定 3~5 把抉择和投影的串接合并成单个抉择、单个投影或一个抉择前面跟一个投影 。这是为了 使多个抉择或投影能同时进行，或在一次扫描中全副实现
• 【步骤 5】对内结点分组 ：每一 双目运算 （$×$、$\bowtie$、$\cup$、$-$）和它 所有的间接先人的一元运算结点 （$\sigma$ 或 $\Pi$）分为一组（如果其 后辈直到叶子全是单目运算 ，则也将他们并入该组）；留神当双目运算是 笛卡尔积 （$×$），而且 其后的抉择不能与它联合为等值连贯 时，则 不能 将抉择与这个 $×$ 并为一组

（3）实例演示

• 留神这是一个很重要的考点

【例】如下给出了一个 SQL 语句

SELECT Student.Sname FROM Student,SC
WHERE Student.Sno=SC.Sno AND SC.Sno='2';

将 SQL 语句转为关系代数表达式

• 先对 Student 和SC做笛卡尔积
• 再对两头后果做抉择（条件为 Student.Sno=SC.Sno）
• 再对两头后果做抉择（条件为SC.Sno='2'）
• 最初投影

后果为

$$\Pi_{Sname}(\sigma_{Student.Sno=sc.Cno \land sc.cno=2}(student × sc))$$

将关系代数表达式转为查问树

查问树优化

①首先抉择条件尽可能下移：

• SC.Sno='2'只和 SC 无关，所以它会沿着分支失当的分支下移到 SC 的上方
• Student.Sno=SC.Sno同时波及 Student 和 SC，所以只能待在那里

②：把抉择和其之前的笛卡尔积合并为等值连贯，或者罗唆变为天然连贯

【例】查问选修了数据库课程的女生学号与姓名，如下是 SQL 语句

SELECT Student.Sno,Sname FROM Student,SC,Course
WHERE Cname='datebase' AND Ssex='女';

将 SQL 语句转为关系代数表达式

$$\Pi_{Sno,Sname}(\sigma_{Cname=’ 数据库 ’ \land Ssex=’ 女 ’}(SC \bowtie Course \bowtie Student))$$

将关系代数表达式转为查问树

查问树优化

①：抉择条件简单，先合成抉择条件

②：将抉择运算尽可能挪动到树的叶端

③：波及了投影运算，所以也把它尽可能挪动到树的叶端

• 投影运算下移时要保留连贯属性

④：对内结点进行分组