分野：テクノロジ系
中分類：データベース
小分類：データベース応用

データベースがサイトごとに分散されて配置されている分散データベースシステムでは、サイト間にまたがる結合演算を行う際にどちらかの表のデータを他方へネットワーク経由で送ることになります。

例えば東京サイトにある表Rと、大阪サイトにある表Sの結合演算を伴うクエリを名古屋サイトが発行した場合だけを見ても、以下のように処理方法には多様性があります。

• 東京サイト上の表Rを大阪サイトに送り、大阪サイトが表Sとの結合演算を行い、結果を名古屋サイトに送る
• 大阪サイト上の表Sを東京サイトに送り、東京サイトが表Rとの結合演算を行い、結果を名古屋サイトに送る
• 表R，Sをともに名古屋サイトに送り、名古屋サイトが結合演算を行い、結果を受け取る

このとき集中型データベースのクエリ最適化と最も異なる点は、表のデータを他のサイトに転送する通信コストを考慮しなくてはならない点です。

セミジョイン法(準結合演算)は、この分散型演算に特有の転送コストを少なくするための結合手法です。サイト1上の表Rとサイト2上の表Sをセミジョイン法で結合する手順は以下のようになります。

• サイト1は表Rのうち結合する属性の射影だけをサイト2に転送する
• サイト2は転送されてきた結合属性の射影と表Sの結合演算を行う
• サイト2は(2)の結合演算結果をサイト1に転送する
• サイト1は転送されてきた結果と表Rの結合演算を行う

最初に結合属性の射影を転送するコストは余分に掛かりますが(2)の操作によって結合に必要な最小限のレコードが抽出されるため、どちらかの表の全てを他方のサイトに転送する場合と比較して通信負荷の低減が期待できます。

• LRU法は、置換え対象を決定するためのアルゴリズムで結合演算とは関係ありません。
• 正しい。セミジョイン法は、分散データベースシステムにおける結合演算の転送コストを少なくするための手法です。
• ソートマージ法は、結合演算のコストを最適化するための手法です。結合キーを値でソート(整列)した2つの表を突き合わせ処理によって結合していくことで、不必要な行同士の結合処理を省きます。転送コストを低減させる手法ではないため分散型結合演算の最適化手法としては不適切です。
• 楽観的方法はトランザクションの排他制御手法の1つです。データの参照時にはロックせず、データ更新直前に値をチェックし変更されていなければロックして更新、変更されていれば更新キャンセルをします。結合演算とは関係がないため誤りです。