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

選択肢

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

正解と解説

正解：ウ O(n^2)

入れ子ループ法は外側の表の各行について内側の表を全件走査して突き合わせる方式である。どちらの表もタプル数がnなら、比較回数はn×nに比例するので計算量はO(n^2)となる。索引が使える場合は内側の走査を減らせるが、単純な入れ子ループでは総当たりになる。

選択肢ごとの解説

• アO(2n)は表を1回ずつ走査する程度の量で、総当たりの比較を表していない。
• イ対数オーダは索引探索1回分に相当し、結合全体の計算量にはならない。
• ウ正しい。外側n件×内側n件の総当たりでO(n^2)になる。
• エO(n log n)は整列を伴うソートマージ法に近い見積りである。

同じ分野の他の問題

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