解説

表の結合演算アルゴリズムにおける「等結合」について

問題の概要

---

選択肢の概要

---

等結合（Equi-join）とは？

• 「等結合」とは、主に2つの表の指定した属性（カラム）が 等しい 場合にのみ行を結合するタイプの結合です。
• 例えば、
  $R.A = S.B$
  のように、ある属性の値が完全に一致する行だけを結合します。

---

各アルゴリズムの適用可能性

1. 入れ子ループ法（Nested Loop Join）

• どんな結合条件でも可能。
• 2つの表のすべての行を一つずつ比較するので、非等結合も可能です。
• しかし、時間計算量が大きい（$O(n \times m)$）ので効率は悪い。

2. 索引結合法（Index Join）

• 片方の表が索引を持っている場合、等結合で効果的に利用できる。
• 索引の検索性を利用して効率アップ。
• 索引がなければ難しい。

3. ソートマージ法（Sort-Merge Join）

• 両表を結合キーでソートし、ソート済みのデータをマージする形で等結合を行う。
• 基本的には等結合向けだが、結合条件が等号以外の場合は適用困難。
• 一度ソートする必要があり、コストがかかる場合もある。

4. ハッシュ法（Hash Join）

• 結合キーの値を元にハッシュテーブルを作る。
• 等結合専用の手法で、等しい値の行をすぐに見つけられる。
• 大量データでも効率的に処理可能。
• 非等結合（大小比較など）には適用できない。

---

なぜ「エ: ハッシュ法」が正解なのか？

• ハッシュ結合法は「等結合のみ」に限定して適用できるアルゴリズムです。
• なぜなら、キーの「値の等しいもの」をハッシュ関数で分類し、それをもとに高速に結合を行う設計だからです。
• 例えば、結合条件が「$R.A > S.B$」などの大小比較であれば、ハッシュ関数の利用は成立せず使えません。

---

まとめ

---

結論

---

参考文献

• データベース実践入門（結合アルゴリズムの基礎・応用）
• 「Database System Concepts」 by Silberschatz et al. (ハッシュ結合法の解説)

---