• 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,SCWHERE 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,CourseWHERE Cname='datebase' AND Ssex='女';

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

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

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

查问树优化

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


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


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

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


④：对内结点进行分组