一、概述

1. **优化器（Optimizer）：**结合统计数据，在关系代数的若干等价形式中选择最优的等价形式，确定关系代数的执行算法，输出执行方案

   • 在关系代数的层级：在关系代数的若干等价形式中选择最优的等价形式
   • 在实现层级：确定详细的查询执行方案，例如选取执行某个操作的算法、选取要使用的特定索引等

2. **执行方案（Evaluation Strategy）：**可以用一棵自底向上的树表示

   

二、关系代数的转化 Transformation of Relational Expressions

1. 等价关系代数式的定义

• 称两个关系代数式是等价的，如果两个代数式在任意一个合法的数据库实例上产生相同的元组
• 元组的顺序无关紧要
• 不考虑因数据库实例不满足约束条件而导致关系代数式执行结果不同的情况

2. 等价规则

1. R1：与关系的选择运算可以拆解为一系列选择运算

   $\sigma_{\theta_1\land\theta_2}=\sigma_{\theta_1}(\sigma_{\theta_2}(E))$

2. R2：选择运算满足交换律（Commutative）

   $\sigma_{\theta_1}(\sigma_{\theta_2}(E))=\sigma_{\theta_2}(\sigma_{\theta_1}(E))$

3. R3：在一系列投影运算中，只有最后一个投影运算起作用，其它投影运算可以忽略

   $\Pi_{L_1}(\Pi_{L_2}(\Pi…E))=\Pi_{L_1}(E)$ ，where $L_1\subseteq L_2\subseteq …$

4. R4：选择运算可以和笛卡尔乘积、Theta 连接相结合

   • $\sigma_\theta(E_1\times E_2)=E_1\bowtie_\theta E_2$
   • $\sigma_{\theta_1}(E_1\bowtie_{\theta_2}E_2)=E_1\bowtie_{\theta_1\land\theta_2}E_2$

5. R5：Theta 连接和自然连接满足交换律

   $E_1\bowtie_\theta E_2=E_2\bowtie_\theta E_1$

6. R6A：自然连接满足结合律（Associative）

   $(E_1\bowtie E_2)\bowtie E_3=E_1\bowtie (E_2\bowtie E_3)$

   R6B：Theta 连接在下述条件下满足结合律，其中 $\theta_2$ 只包含来自 $E_2$ 和 $E_3$ 的属性

   $(E_1\bowtie_{\theta_1} E_2)\bowtie_{\theta_2\land\theta_3} E_3=E_1\bowtie_{\theta_1\land\theta_3} (E_2\bowtie_{\theta_2} E_3)$

7. R7：选择运算在以下情形对连接运算具有分配律

   （先连接后选择 $\rightarrow$ 先选择后连接）

   • 情形一：当 $\theta_1$ 只包含来自 $E_1$ 的属性时

     $\sigma_{\theta_1}(E_1\bowtie_\theta E_2)=(\sigma_{\theta_1}(E_1))\bowtie_{\theta}E_2$

   • 情形二：当 $\theta_1$ 只包含来自 $E_1$ 的属性， $\theta_2$ 只包含来自 $E_2$ 的属性时

     $\sigma_{\theta_1\land\theta_2}(E_1\bowtie_\theta E_2)=(\sigma_{\theta_1}(E_1))\bowtie_{\theta}(\sigma_{\theta_2}(E_2))$

8. R8：投影运算在以下情形对连接运算具有分配律

   （先连接后投影 $\rightarrow$ 先投影后连接）

   • 情形一：当 $\theta$ 只包含来自 $L_1\cup L_2$ 的属性时

     $\Pi_{L_1\cup L_2}(E_1\bowtie_\theta E_2)=(\Pi_{L_1}(E_1))\bowtie_\theta (\Pi_{L_2}(E_2))$

   • 情形二：

     • 令 $L_1$ 和 $L_2$ 分别是来自 $E_1$ 和 $E_2$ 的属性集合
     • 令 $L_3$ 是 $E_1$ 的属性中包含在连接条件 $\theta$，但不包含在 $L_1\cup L_2$ 的属性集合
     • 令 $L_4$ 是 $E_2$ 的属性中包含在连接条件 $\theta$，但不包含在 $L_1\cup L_2$ 的属性集合

     $\Pi_{L_1\cup L_2}(E_1\bowtie_\theta E_2)=(\Pi_{L_1\cup L_3}(E_1))\bowtie_\theta (\Pi_{L_2\cup L_4}(E_2))$

9. R9：集合的交运算和并运算满足交换律

   • $E_1\cup E_2=E_2\cup E_1$
   • $E_1\cap E_2=E_2\cap E_1$

10. R10：集合的交运算和并运算满足结合律

    • $(E_1\cup E_2)\cup E_3=E_1\cup (E_2\cup E_3)$
    • $(E_1\cap E_2)\cap E_3=E_1\cap (E_2\cap E_3)$