平成31年度 春期 データベーススペシャリスト試験 午前II 問16

【解説】

入れ子ループ法（Nested Loop Join） は、以下の手順で結合を行います：

1. 外側のテーブル（外部ループ）の各タプルについて、内側のテーブル（内部ループ）の全タプルを順番に比較します。
2. 結合条件を満たすペアを出力します。

このアルゴリズムでは、外側のテーブルのタプル数を n1、内側のテーブルのタプル数を n2 とすると、計算量は次のようになります：
n1 × n2

特に、両方のテーブルのタプル数が n である場合、計算量は n × n となり、結果として O(n^2) となります。

ア: O(n)
誤り。これは単純な線形探索の計算量であり、入れ子ループ法では計算量が小さすぎます。

イ: O(log n)
誤り。これは効率的な検索アルゴリズム（例: 二分探索など）の計算量であり、入れ子ループ法ではありません。

ウ: O(n^2)
正しい。入れ子ループ法は、外側ループで n 回、内側ループで n 回の操作が必要となるため、計算量は O(n^2) です。

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