关系代数表达式优化步骤

本篇主要讲解怎么画查询语法树并对其优化，因为我在学关系代数的语法树的时候，在网上找不到比较详细的教法或者技巧，最后通过答案反推原理，所以想写一篇技巧来描述一下这类题的解题方法。

先上书内讲解

1、构造查询树

第一步：把用高级语言定义的查询转换为关系代数表达式
★ 以 SELECT子向对应投影操作，以FROM字向对应笛卡尔积以 WHERE子句对应选择操作，生成原始查询树
★ SQL语句转化为原始查询树
第二步：把关系代数表达式转换为查询树。

注： 查询树是一种表示关系代数表达式的树形结构。在一个查询树中，叶子结点表示关系，内结点表示关系代数操作。查询树以自底向上的方式执行：当一个内结点的操作分量可用时，这个内结点所表示的操作启动执行，执行结束后用结果关系代替这个内结点。

2、利用等价转换规则反复地对查询表达式进行尝试性转换，将原始的语法树转換成“优化”的形式（方式的等价变换规则查书）

1. 对每一个选择，利用等价变换规则4~9尽可能把它移到树的叶端。目的是使选择操作尽早执行
2. 对每一个投影利用等价变换规则3,9等的一般形式尽可能把它移向树的叶端。目的是使投影操作尽早执行
3. 对每个叶节点加必要的投影操作，以消除对查询无用的属性。
4. 如果笛卡尔乘积后还须按连接条件进行选择操作,可将两者组合成连接操作
   选择下沉，投影随后

---

题目举例

对学生-课程数据库，查询信息系学生选修了的所有课程名称。

​ SELECT Cname FROM Student,Course,SC WHERE Student.Sno=SC.Sno AND SC.Cno=Course.Cno AND Student.Sdept=’IS’;

​ 试画出查询树图、关系代数语法树图、优化后的查询树。

具体的技巧就是 先选择，后投影，按照查询语句的顺序 先写Project(Cname)，也就是最终查询结果，然后按照条件语句where从后面往前写，遇到两个表相关联的字段时，可以看看是否这个表后面还有查询，如果没有，则表作为叶端，有的话，就继续连接(join)条件，直到所有的查询条件都连接完毕，剩下的叶端就是表了。
例如下图的查询树，到join(SC.Cno=Course.Cno)的时候，条件的Course从后往前都没有下一个查询条件了，也就是说这是最后一个关于Course的查询条件，那表名就出来了。
进行优化语法树的时候，要全部都转为选择σ和投影∏来表示，σ一般表示除了父节点以外的结点，∏ 表示父节点。遇到两个表相关联的情况，下面要用X表示，比查询多这一步而已，读者看图应该能看懂。下一步就是变成优化后的语法树，做法也很简单，就是把那些单表的查询语句移到下面来，移到等值运算后面作为新的查询条件，然后再出结果的表。

1.构造查询树
查询语句转关系代数表达式为：∏Cname(σStudent.Sdept=’IS’(Student ⋈ Course ⋈ SC))

2.利用等价代换原则进行优化