関係データベースにおいて、タプル数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年度 春期 午前Ⅱ 問16
- 関係データベースにおいて、タプル数nの表二つに対する結合操作を、入れ子ループ法によって実行する場合の計算量はどれか。2017年度 春期 午前Ⅱ 問19
- 表の結合演算アルゴリズムのうち、等結合だけに適用できるものはどれか。2016年度 春期 午前Ⅱ 問11
出典・参考
最終更新：2026-10-06／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。