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

選択肢

• アO(n)
• イO(log n)
• ウO(n²)
• エO(n log n)

正解と解説

正解：ウ O(n²)

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

選択肢ごとの解説

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

同じ分野の他の問題

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