最適化の第一の目標は、関係代数式を、木構造内の部分木により与えられる部分関係代数式が生成する関係の平均的な大きさを、最適化前の関係代数式が生成する関係の平均的な大きさより小さくする、同等な関係代数式に変換することである。
第二の目標は、一つの問い合わせ内において複数回出現する共通の部分関係代数式を同定することであり、また同時に複数の問い合わせが評価される際、それら全ての問い合わせにおいて複数回出現する共通の部分関係代数式を同定することである。
第二の目標で複数回出現する共通の部分関係代数式を同定することにより、一度その部分関係代数式を計算すれば、その計算結果を同じ部分関係代数式が出現し評価する際に再利用すれば良く、問い合わせにおいて再度同じ部分関係代数式を計算する必要は無くなる。
次に木構造のこうした変換における法則群を説明する。
参考: クエリ最適化
最適化における制限演算.
制限演算に関する法則は、問い合わせ最適化において大きな役割を果たす。
制限演算は、演算対象の関係の組の数を大幅に減らす。
そのため最適化においては、制限演算を問い合わせ木構造の葉の方向へ移動することで、部分関係代数式により生成される関係群の大きさを小さくすることができるであろう。
複合した制限演算の分解.
いくつかの情況においては、制限演算を結合することは有効である。
別の情況においては、複合した制限演算を分割することが有効である。
このときは、複合した制限演算を木構造内で移動できない場合に、個々の制限演算に分割することで、移動できるようになる。
制限と直積.
直積は評価に最もコストを要する演算である。
結合の定義を考えると、最適化をとりわけ効果的に行うことができる。
もし制限演算の後に直積演算が続くのであれば、他の制限の法則を使うことで、制限演算を問い合わせの木構造の高い位置から葉の方向へ押し下げるよう試みることができる。
以上の変換は次のように示される。
制限と集合演算.
注意: 差演算もしくは交わり演算の場合は、木構造を変換することで、制限演算を演算対象の関係群のうちただ一つの関係に対して適用することが可能である。