查询树的启发式优化

典型的启发式规则：
1. 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条
2. 把投影运算和选择运算同时进行（pipelining技术）
如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系，也避免存储中间关系
3. 把投影同其前或其后的双目运算结合起来执行（pipelining技术）
4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算
5. 找出公共子表达式
如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的
当查询的是视图时，定义视图的表达式就是公共子表达式的情况
遵循这些启发式规则，应用9.3.1的等价变换公式来优化关系表达式的算法。
算法：关系表达式的优化
输入：一个关系表达式的查询树
输出：优化的查询树
方法：
(1) 利用等价变换规则4把形如σF1∧F2∧…∧Fn(E)变换为σF1(σF2(…(σFn(E))…))。
(2) 对每一个选择，利用等价变换规则4～9尽可能把它移到树的叶端。
(3) 对每一个投影利用等价变换规则3，5，10，11中的一般形式尽可能把它移向树的叶端。
注意：
等价变换规则3使一些投影消失
规则5把一个投影分裂为两个，其中一个有可能被移向树的叶端
(4) 利用等价变换规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成
(5) 把上述得到的语法树的内节点分组。每一双目运算(×， ，∪，-)和它所有的直接祖先为一组(这些直接祖先是(σ，π运算)。
如果其后代直到叶子全是单目运算，则也将它们并入该组
但当双目运算是笛卡尔积(×)，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组成同一组，把这些单目运算单独分为一组

例[5] 查询语句：检索学习课程名为MATH的女学生学号和姓名。
该查询语句的关系代数表达式如下：
   πS#，SNAME(σCNAME=’MATH’∧SEX=’F’(C   SC   S))
上式中， 符号用π、σ、×操作表示，可得下式
 πS#，SNAME(σCNAME=’MATH’∧SEX=’F’(πL
          (σC.C# = SC.C#∧SC.S# = S.S#(C×SC×S))))
此处L是C、SC、S中全部属性,去除重复属性。