関係代数 (関係モデル)
次の3つの法則は、問い合わせの木構造において制限演算を集合演算 (差・和・交わり) よりも葉に近い方向に押し下げる。
注意: 差演算もしくは交わり演算の場合は、木構造を変換することで、制限演算を演算対象の関係群のうちただ一つの関係に対して適用することが可能である。 この適用による最適化が有効なのは、演算対象の関係群のうち一つが小さく、小さな関係を演算対象として使うことによる利益に対して、制限演算を行うことに伴うオーバーヘッドが大きい場合である。
σ A ( R ∖ P ) = σ A ( R ) ∖ σ A ( P ) = σ A ( R ) ∖ P {\displaystyle \sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P}
σ A ( R ∪ P ) = σ A ( R ) ∪ σ A ( P ) {\displaystyle \sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)}
σ A ( R ∩ P ) = σ A ( R ) ∩ σ A ( P ) = σ A ( R ) ∩ P = R ∩ σ A ( P ) {\displaystyle \sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)}
R MINUS S
なし。
例
従業員と部署の共通の属性は部署名であり、従業員⋈部署には部署名が同じになる組み合わせが含まれている。 従業員の(メアリー,1257,人事)と部署の(生産,チャールズ)は部署名が同じになる組み合わせがないため従業員⋈部署には含まれず、部署の(ファイナンス,ジョージ)と(販売,ハリエット)は部署名が同じになる組み合わせが複数あるため従業員⋈部署に複数回登場する。
定義
関係 R ( A 1 , . . . , A n , B 1 , . . . , B n ) {\displaystyle R(A_{1},...,A_{n},B_{1},...,B_{n})} と関係 S ( B 1 , . . . , B n , C 1 , . . . , C n ) {\displaystyle S(B_{1},...,B_{n},C_{1},...,C_{n})} の自然結合は次のように定義される。
SQL
R NATURAL JOIN S
Tutorial D
R JOIN S
どの条件式の要素も比較可能であり、比較演算子θを使って条件式が記述されていること。
関係代数と関係群に対する問い合わせの最適化について説明する。
関係群に対する問い合わせは木構造として表現される。 その木構造において、
節は関係代数演算子である。
葉は関係である。
部分木は部分関係代数式である。
最適化の第一の目標は、関係代数式を、木構造内の部分木により与えられる部分関係代数式が生成する関係の平均的な大きさを、最適化前の関係代数式が生成する関係の平均的な大きさより小さくする、同等な関係代数式に変換することである。 第二の目標は、一つの問い合わせ内において複数回出現する共通の部分関係代数式を同定することであり、また同時に複数の問い合わせが評価される際、それら全ての問い合わせにおいて複数回出現する共通の部分関係代数式を同定することである。 第二の目標で複数回出現する共通の部分関係代数式を同定することにより、一度その部分関係代数式を計算すれば、その計算結果を同じ部分関係代数式が出現し評価する際に再利用すれば良く、問い合わせにおいて再度同じ部分関係代数式を計算する必要は無くなる。
次に木構造のこうした変換における法則群を説明する。
参考: クエリ最適化