数据库系统2-7：关系代数表达式的优化算法

文章作者 100test 发表时间 2007:03:10 16:59:50
来源 100Test.Com百考试题网

计算机等级考试训练软件《百宝箱》

　　 关系表达式的优化过程：输入一个关系表达式的语法树；输出一个计算该表达式的程序。
　　方法：
　　1． 利用关系代数等价变换规则4（选择串接定理）把形如
σ-F1ùF2。。。ùFn ( E ) 等价变换为σ-F1(σ-F2( …. σ-Fn ( E ) …..) 使选择操作可以灵活方便地沿查询树移动。
　　2． 对每个选择，利用关系代数等价变换规则4~8，尽可能把它移到树的叶端。
　　3． 对每个投影利用关系代数等价变换规则3、5、9、10中的一般形式尽可能把它移至树的叶端。其中规则3可使一些投影消失；规则5可把投影推到叶端；规则9可先做投影后做笛卡儿积；规则10是投影对并的分配，可以利用它将投影推向叶端。若投影针对表达式的全部属性，则可消去这一投影运算。
　　4． 利用关系代数等价变换规则3、4、5对选择和投影进行串接和合并，将其合并成单选择、单投影或单选择后跟一个投影等三种情况。使多选择或多投影能同时执行或在一次扫描过程中同时完成。
　　5． 把上述得到的语法树的内结点分组，每一双目运算（∪、-、X、>< ）与其直接祖先的一目运算结点（不超过别的二目运算结点）分在同一组；如果它的子孙结点一直通到叶结点都是一目运算（σ-、?），则将它归入该组中。但当二目运算是笛卡儿积（X），且其后的选择不能与它结合为等值连接时，其后的单目运算就单独分为一组。
　　6． 生成一个程序，每个结点的计算为程序的一步。