データベーススペシャリスト 2012年午前2 問18

問題文

関係データベースにおいて、タプル数nの表二つに対する結合操作を入れ子ループ法によって実行する場合の計算量は幾らか。

選択肢

ア：

2 n

イ：

l o g n

ウ：

n^{2}

（正解）

エ：

n l o g n

関係データベースの結合操作における入れ子ループ法の計算量【午前2 解説】

要点まとめ

結論：入れ子ループ法による結合操作の計算量は $n^{2}$ となる。
根拠：表がそれぞれ $n$ 個のタプルを持つ場合、外側ループで $n$ 回、内側ループでも $n$ 回の比較が必要だから。
差がつくポイント：結合アルゴリズムの計算量を理解し、効率的な方法との違いを押さえることが重要。

正解の理由

入れ子ループ法は、外側の表の各タプルに対して内側の表の全タプルを順に比較する単純な結合方法です。両方の表のタプル数が

n

であれば、比較回数は

n \times n = n^{2}

となり、計算量は二次関数的に増加します。したがって、正解はウ:

n^{2}

です。

よくある誤解

入れ子ループ法の計算量を

2 n

や

n lo g n

と誤解しやすいですが、これはソートやインデックスを利用した場合の計算量です。単純な入れ子ループは全組み合わせを比較するため二次的に増加します。

解法ステップ

表のタプル数をそれぞれ $n$ と設定する。
外側ループで表1の $n$ タプルを順に処理する。
内側ループで表2の $n$ タプルを全て比較する。
比較回数は $n \times n = n^{2}$ となることを確認する。
選択肢の中から $n^{2}$ に該当するものを選ぶ。

選択肢別の誤答解説

ア: $2 n$
単純に両表のタプル数を足しただけで、結合の比較回数を表していません。
イ: $lo g n$
これは二分探索などの探索アルゴリズムの計算量であり、入れ子ループ法には当てはまりません。
ウ: $n^{2}$
正解。入れ子ループ法の計算量は二つの表のタプル数の積に比例します。
エ: $n lo g n$
ソート結合など効率的な結合方法の計算量であり、単純な入れ子ループ法ではありません。

補足コラム

入れ子ループ法は実装が簡単ですが、大量データには非効率です。効率化のためには、ソート結合やハッシュ結合が用いられ、これらは計算量を

O (n lo g n)

や

O (n)

に削減できます。データベースのパフォーマンスチューニングでは、結合アルゴリズムの選択が重要なポイントです。

FAQ

Q: 入れ子ループ法はどんな場合に使われますか？
A: 小規模データやインデックスがない場合に使われますが、大規模データでは非効率です。

Q: ソート結合と入れ子ループ法の違いは何ですか？
A: ソート結合は両表をソートしてから結合するため計算量が

O (n lo g n)

で、入れ子ループ法より高速です。

関連キーワード: 関係データベース、結合操作、入れ子ループ法、計算量、データベースアルゴリズム

← 前の問題へ次の問題へ →

\ せっかくなら /

データベーススペシャリストを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！