平成24年度 春期 データベーススペシャリスト試験 午前Ⅱ 問18

解説

入れ子ループ法（nested loop join）は，一方の表（外側の表）の各タプルについて，もう一方の表（内側の表）の全てのタプルを走査して結合条件を照合する結合アルゴリズムである。外側の表のタプル数がn，内側の表のタプル数もnである場合，外側の各タプルに対して内側のn個のタプルを走査する処理をn回繰り返すことになるため，比較回数（計算量）はn×n＝n²のオーダーになる。

選択肢ごとの解説

• ア誤り。2nは，二つの表をそれぞれ1回ずつ走査する程度の線形の計算量であり，全ての組合せを総当たりで照合する入れ子ループ法の計算量としては小さすぎる。
• イ誤り。log nのオーダーは，索引を使った二分探索のような対数時間の処理に相当し，全件を総当たりで照合する入れ子ループ法の計算量には当てはまらない。
• ウ正しい。入れ子ループ法では，一方の表のn個のタプルそれぞれについて，他方の表のn個のタプルを走査するため，計算量はn×n＝n²のオーダーになる。
• エ誤り。n log nのオーダーは，各表をあらかじめソートしてから結合するマージジョイン法などに近い計算量であり，ソートを行わず総当たりで照合する入れ子ループ法の計算量とは異なる。