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

【解説】

入れ子ループ法（Nested Loop Join）の特徴
入れ子ループ法は、結合操作を行う際に次のような処理を行います：

1. 外側のループで、1つ目の表の各タプルを順に取り出します。
2. 内側のループで、2つ目の表の各タプルと比較して結合条件を評価します。

これにより、各タプルに対して全てのタプルを比較するため、全体の計算量はO(n × n) = O(n²)になります。
したがって、入れ子ループ法の計算量は2つの表のタプル数の積に比例します。

ア: O(log n)
これは一般的に二分探索などの計算量であり、入れ子ループ法には該当しません。

イ: O(n)
線形計算量ですが、入れ子ループ法では全てのタプルを比較するため、これも該当しません。

ウ: O(n log n)
これはソートを伴う結合方法（ソートマージ結合など）の計算量であり、入れ子ループ法には該当しません。