| 关系系统的查询优化是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为，用户只要提出“干什么”，不必指出“怎么干”。在关系代数表达式中需要指出若干关系的操作步骤，问题是怎样做才能保证省时、省空间、效率高，这就是查询优化的问题。
|
|
|
| 需要注意的是，在关系代数运算中，笛卡儿积、连接运算最费时间和空间，究竟应采用什么样的策略，节省时间空间。这就是优化的准则。
|
|
|
|
|
|
|
| （1）提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量和从外存读块的次数。
|
|
|
| （2）合并乘积与其后的选择运算为连接运算。在表达式中，当乘积运算后面是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以避免做完乘积后，需再扫描一个大的乘积关系进行选择运算。
|
|
|
| （3）将投影运算与其后的其他运算同时进行，以避免重复扫描关系。
|
|
|
| （4）将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。
|
|
|
| （5）在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、排序合并连接法。
|
|
|
| （6）存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。
|
|
|
|
|
| 优化的策略均涉及关系代数表达式，所以讨论关系代数表达式的等价变换规则显得十分重要。常用的等价变换规则有如下10种。
|
|
|
|
|
| 设E1和E2是关系代数表达式，F是连接运算的条件，则有：
|
|
|
|
|
|
|
| 设E1、E2、E3是关系代数表达式，F1、F2是连接运算的条件，则有：
|
|
|
|
|
|
|
| 设E是关系代数表达式，A1，…，An和B1，…，Bm是属性名，且B1，…，Bm是A1，…，An的子集。则有：
|
|
|
|
|
|
|
|
|
| 设E是关系代数表达式，F1、F2是选取条件表达式，选择的串接定律说明选择条件可以合并，则有：
|
|
|
|
|
|
|
| 设E是关系代数表达式，F是选取条件表达式，并且只涉及A1，…，An属性，则有：
|
|
|
|
|
| 若F中有不属于A1，…，An属性，B1，…，Bm，那么有更一般的规则：
|
|
|
|
|
| 该规则可将投影分裂为两个，使得其中的一个可能被移到树的叶端。
|
|
|
|
|
|
|
|
|
| 如果F=F1∧F2，并且，F1只涉及E1中的属性，F2只涉及E2中的属性，则有：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 设E1、E2是两个关系表达式，A1，…，An是E1中的属性，B1，…，Bm是E2中的属性，则：
|
|
|
|
|
|
|
|
|
|
|
|
|
| 利用上述的等价变换规则可以对关系代数表达式进行优化，使得优化后的关系代数表达式符合上述的6条基本优化的准则。
|
|
|
|
|
|
|
|
|
|
|
（1）利用规则4将形如 变换为：
|
|
|
|
|
| （2）对每一个选择，利用规则4~8尽可能将它移到树的叶端。
|
|
|
| （3）对每一个投影，利用规则3、9、10，5中的一般形式尽可能将它移到树的叶端。
|
|
|
| （4）利用规则3~5将选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时进行，或在一次扫描中全部完成。
|
|
|
（5）将上述得到的语法树的内节点分组。每一双目运算（×，∪， ，-）和它所有的直接祖先为一组（这些直接祖先是σ，π运算）。如果其后代直到叶子全部是单目运算，则将它并入该组。
|
|
|
| （6）生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。
|
|
|
