关系代数表达式是进行数据库查询前的理论部分，在简单的查询中一般不会想到这个，直接上sql语句就行。

但是一旦涉及大范围或者超多表查询，关系代数表达式能够组织逻辑并且基于关系代数表达式的优化，能够很大程度上优化最后的查询语句，从而提高查询效率。

当然先写出sql语句，在对sql语句进行优化实际上一样的。

查询优化的目标：

1. 选择有效的策略
2. 求给定关系表达式的值
3. 使查询代价最小（实际上只能是较小）

优化的部分：

并不是所有的部分都可以进行优化的，而我们知道在关系代数的运算中最消耗时间的两个操作：

笛卡尔积 和 连接运算

优化策略：

1. 代数优化

   即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化.
   

2. 物理优化

   选择操作算法有**全表扫描**和**索引扫描**2种方法，<font color="red">索引扫描方法较优</font>
   对于AB表的连接，利用A表上的索引，<font color="red">采用index join代价也较小</font>
   

代数优化策略:

主要说一下代数优化：

通过对关系代数表达式的等价变换来提高查询效率

代数等价概念：

1. 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
2. 两个关系表达式E1和E2是等价的，可记为E1≡E2

关系代数等价变换规则：

1. 连接、笛卡尔积交换律

   
   E1 x E2 ≡ E2 x E1
   E1 ⋈ E2 ≡ E2 ⋈ E1
   E1 ⋈ E2 <sub>F</sub>≡ E2 ⋈ E1 <sub>F</sub>
   

2. 连接、笛卡尔积结合律

1. 投影的串接定律

1. 选择的串接定律

1. 选择与投影的交换律

1. 选择与笛卡尔积交换律

2. 选择与并的交换
3. 选择与差运算的交换
4. 投影与笛卡尔积的交换
5. 投影与并的交换

表达式转换的启发式规则：

• 尽可能早地执行选择操作
• 尽可能早地执行投影操作
• 避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做

关系代数表达式的启发式优化算法：

1. 利用规则4进行选择条件分解
2. 对每一个选择，利用规则4-8尽量把它移到树的叶端
3. 对每一个投影，利用规则3，9，10，5中的一般形式尽可能把它移到树的叶端
4. 利用规则3-5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影
5. 把上述得到的语法树的内结点分组
6. 生成一个程序，每组结点的计算是程序中的一步

示例：

设有三个关系 A（a1,a2,a3,…）、B（b1,b2,b3, … ）、C（a1,b1,c1,c2, … ）

有一个查询请求如下：

SELECT A.a1 FROM A，B，C WHERE A. a1 =C. a1 AND B. b1 =C. b1 AND f(c1)

优化如下：

1. 将查询语言转换成语法树

2. 选择条件分解（规则4）

3. 选择操作下移

4. 投影操作下移

5. 选择和投影的串接合并（规则5）

6. 内结点分组

内结点分组算法：

内结点分组其实比较简单

1. 从一个笛卡尔积（也就是 X ）出发，往上（父节点）全部囊括进去，直到遇见另一个笛卡尔积（x）
2. 从一个笛卡尔积出发，找子节点，当发现子节点连着一个笛卡尔积（x）时，这条线上的所有的选择和投影均去掉（属于下面连接的笛卡尔积，因为规则1说明了，从一个笛卡尔积往上的父节点全部囊括除非遇到了另一个笛卡尔积）

3.从一个笛卡尔积出发，当发现某条线上的子节点一直连接到叶子节点，那么这条线的连接和投影操作均属于该笛卡尔积的内结点分组。

可以参照步骤6中的图

经过优化后的查询操作，比起一开始的语句，已经优化的太多了。