平成22年春期試験問題 午前Ⅱ 問19

分散型データベースで結合演算を行うとき,通信負荷を最も小さくすることができる手法はどれか。ここで,データベースは異なるコンピュータ上に格納されて,かつ結合演算を行う表の行数が,双方で大きく異ならないものとする。

  • 入れ子ループ法
  • インデックスジョイン法
  • セミジョイン法
  • マージジョイン法
正解 問題へ
分野:テクノロジ系
中分類:データベース
小分類:トランザクション処理
解説
セミジョイン法(準結合演算法)は、分散型演算に特有の転送コストを少なくするための結合手法です。サイト1上の表Rとサイト2上の表Sをセミジョイン法で結合する手順は以下のようになります。
  • サイト1は、表Rのうち結合する属性の射影だけをサイト2に転送する
  • サイト2は、転送されてきた結合属性の射影と表Sの結合演算を行う
  • サイト2は、(2)の結合演算結果をサイト1に転送する
  • サイト1は、転送されてきた結果と表Rの結合演算を行う
最初に結合属性の射影を転送するコストは余分に掛かりますが、(2)の操作によって結合に必要な最小限のレコードが抽出されるため、どちらかの表の全てを他方のサイトに転送する場合と比較して通信負荷の低減が期待できます。
19.png
  • 入れ子ループ法(ネストループ法)は、両方のテーブルをフルスキャンすることによって結合演算を行う手法です。分散データベースでは1行分のデータを相手に送り、その演算結果すべてを送り返してもらうので、セミジョイン法に比べて通信負荷は大きくなります。
    //入れ子ループ法による表Rと表Sの結合処理
    for (t in R)
      for (t' in S)
        if (t['A'] == t'['A'])
          結合(t, t');
      end
    end
  • インデックスジョイン法(索引結合法)は、結合先のテーブルをフルスキャンするのではなく、結合属性のインデックスを探索することで入れ子ループ法の結合演算を高速化する手法です。
  • 正しい。セミジョイン法は、結合属性の値を相手に送り、相手から必要な演算結果のみを送り返してもらうことで、分散データベースにおける結合演算の通信負荷を抑える手法です。
  • マージジョイン法(ソートマージ法)は、結合前にテーブルを結合属性の値でソートし、先頭から突き合わせていくことで無駄な照合をなくし、結合演算を高速化する手法です。分散データベースでは相手からソート済みのテーブルを送ってもらう必要があるので、通信負荷の軽減とは無関係です。

この問題の出題歴


Pagetop