データベーススペシャリスト試験 2015年午前2 問17

関係データベースにおいて, タプル数

n

の表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。

ア：

O(2n)

イ：

O(\log n)

ウ：

O(n^2)

（正解）

エ：

O(n \log n)

解説

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

要点まとめ

結論：入れ子ループ法による結合操作の計算量は $O(n^2)$ です。
根拠：表二つのタプル数がそれぞれ $n$ の場合、外側ループで $n$ 回、内側ループで $n$ 回の比較が必要になるためです。
差がつくポイント：結合アルゴリズムの計算量の違いを理解し、特に入れ子ループ法の非効率さを押さえることが重要です。

正解の理由

入れ子ループ法は、外側の表の各タプルに対して内側の表の全タプルを順に比較します。
したがって、タプル数

n

の表が二つある場合、比較回数は

n \times n = n^2

となり、計算量は

O(n^2)

です。
このため、選択肢の中で

O(n^2)

を示す「ウ」が正解となります。

よくある誤解

入れ子ループ法は単純なアルゴリズムのため、計算量が

O(n)

や

O(\log n)

と誤解されやすいです。
また、結合操作全体の計算量をインデックス利用時の高速化と混同することもあります。

解法ステップ

入れ子ループ法の動作をイメージする（外側ループと内側ループの二重ループ）。
外側の表のタプル数を $n$ とし、内側の表のタプル数も $n$ と設定。
外側ループは $n$ 回繰り返し、内側ループも $n$ 回繰り返すため、比較回数は $n \times n = n^2$ 。
よって計算量は $O(n^2)$ と判断する。
選択肢の中から $O(n^2)$ を示すものを選ぶ。

選択肢別の誤答解説

ア: $O(2n)$
→ $2n$ は $O(n)$ と同義であり、入れ子ループ法の二重ループ構造を考慮していません。
イ: $O(\log n)$
→ ログ計算量は主に二分探索やインデックス検索に関連し、入れ子ループ法には該当しません。
ウ: $O(n^2)$
→ 正解。二重ループのため計算量は二乗オーダーです。
エ: $O(n \log n)$
→ ソートやマージソートの計算量であり、入れ子ループ法の結合には適用されません。

補足コラム

関係データベースの結合アルゴリズムには、入れ子ループ法の他にソートマージ結合やハッシュ結合があります。
これらは効率的に結合を行うため、計算量を

O(n \log n)

や

O(n)

に抑えることが可能です。
入れ子ループ法は単純ですが、大規模データには不向きであるため、実務では他のアルゴリズムが多用されます。

FAQ

Q: 入れ子ループ法はなぜ計算量が

O(n^2)

になるのですか？
A: 外側の表の各タプルに対し、内側の表の全タプルを比較するため、比較回数が

n \times n

となるからです。

Q: インデックスを使えば入れ子ループ法の計算量は改善しますか？
A: インデックスを利用すると検索が高速化され、計算量は

O(n \log n)

程度に改善されることがありますが、純粋な入れ子ループ法は

O(n^2)

のままです。

関連キーワード: 関係データベース, 結合アルゴリズム, 入れ子ループ法, 計算量, ビッグオーダー

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

データベーススペシャリスト試験 2015年 午前2 問17

解説