关系代数表达式算法-数据库技术应用教程

2025-09-30 理论教育版权反馈

【摘要】：下面给出关系表达式的优化算法。利用等价变换规则把代数式变换为σF1（σF2（…对每一个选择，利用等价变换规则～尽可能地移到树的叶端。尽管这种变换似乎违背“投影尽可能先做”的原则，但这样做效率更高。把上述得到的语法树的内节点分组。也可以把这些单目运算单独分为一组。生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，但要保证任何一组的计算不会在它的后代组之前计算。

下面给出关系表达式的优化算法。

（1）利用等价变换规则（4）把代数式变换为σF1（σF2（…（σFn（E））…））。

（2）对每一个选择，利用等价变换规则（4）～（8）尽可能地移到树的叶端。

（3）对每一个投影利用等价变换规则（3）（9）（10）和（5）中的一般形式，尽可能地移向树的叶端。值得注意的是，规则（3）会使一些投影消失，而一般形式的规则（5）会把一个投影分裂为两个，其中一个有可能被移向树的叶端。(https://www.chuimin.cn)

（4）利用规则（3）～（5）把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影，会使多个选择和投影能同时执行或在一次扫描中全部完成。尽管这种变换似乎违背“投影尽可能先做”的原则，但这样做效率更高。

（5）把上述得到的语法树的内节点分组。每一双目运算（×，▷◁，∪，－）和它所有的直接祖先为一组（这些直接祖先是σ，π运算），如果其后代直到叶子全部是单目运算，也可将它们并入该组。但当双目运算是笛卡儿积（×），而且其后的选择不能与它结合为等值连接时除外。也可以把这些单目运算单独分为一组。

（6）生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，但要保证任何一组的计算不会在它的后代组之前计算。

关系代数表达式算法-数据库技术应用教程

相关推荐