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

選択肢

• アO(log n)
• イO(n)
• ウO(n log n)
• エO(n^2)

正解と解説

正解：エ O(n^2)

入れ子ループ法は、外側の表の1行ごとに内側の表を全走査して結合条件を確かめる方式である。どちらもn行なら比較回数はn×nに比例するので、計算量はnの2乗のオーダーになる。よってエが正しい。

選択肢ごとの解説

• ア対数オーダーは索引による1件検索などの計算量で、全行の突合せには当てはまらない。
• イ片方の表を1回走査するだけの処理量であり、二重ループの実態と合わない。
• ウソートを伴うマージジョインなどの計算量に近く、入れ子ループの見積りではない。
• エ正解。外側n行それぞれについて内側n行を走査するため、nの2乗に比例する。

同じ分野の他の問題

• 関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。2019年度 春期 午前II 問16
• 関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。2017年度 春期 午前II 問19
• 表の結合演算アルゴリズムのうち、等結合だけに適用できるものはどれか。2016年度 春期 午前II 問11