令和3年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問15

関係データベース における表の結合操作の一つである 入れ子ループ法 （ネステッドループジョイン）についての問題です。

入れ子ループ法は、一方の表（外部表）の各タプルに対して、もう一方の表（内部表）の全タプルを順番に走査して結合条件に一致するかどうかを判定する手法です。

タプル数がともに $n$ の表二つを結合する場合、外部表の $n$ 個のタプル一つ一つに対して、内部表の $n$ 個のタプルとの比較が行われます。
したがって、比較回数は $n \times n = n^2$ 回となります。
計算量をオーダ記法（$O$ 記法）で表すと $O(n^2)$ となります。

よって、正解は「エ」です。

各選択肢の解説

• ア $O(\log n)$
  二分探索など、探索範囲を半分ずつ狭めていくアルゴリズムの計算量です。入れ子ループ結合の計算量ではありません。
• イ $O(n)$
  表の全タプルを1回だけ走査するような処理の計算量です。入れ子ループ結合では内部表を何度も走査するため誤りです。
• ウ $O(n \log n)$
  マージソートなどの効率的なソートアルゴリズムの計算量です。結合アルゴリズムの一つであるソートマージ結合において、事前に表をソートする際などに現れる計算量ですが、入れ子ループ法の計算量ではありません。
• エ $O(n^2)$
  正解です。2重のループによる全探索となるため、計算量はこのようになります。