平成27年春期試験問題 午前Ⅱ 問17

平成27年春期試験問題　午前Ⅱ 問17

問17解説へ

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

O(2n)
O(log n)
O(n²)
O(n log n)

正解　ウ問題へ

分野：テクノロジ系
中分類：データベース
小分類：データ操作

解説

入れ子ループ法(ネストループ法)は、2つの表に含まれる行を1つずつ比較しながら結合を行っていく手法です。入れ子ループ法の処理の流れは以下のプログラムで表すことができます。

〔入れ子ループ法による表Rと表Sの結合処理〕
for (t in R)
　　for (t' in S)
　　　　if (t['A'] == t'['A'])
　　　　　　結合(t, t');
　　end
end

このプログラムを走らせると、R表の1行目に対してS表の全件を比較、R行の2行目に対してS表の全件を比較、…、R行のn行目に対してS表の全件を比較というように処理が行われていきます。

〔入れ子ループ法の流れ〕
R表の1行目とS表の1行目を比較する
R表の1行目とS表の2行目を比較する
：
R表の1行目とS表のn行目を比較する
R表の2行目とS表の1行目を比較する
R表の2行目とS表の2行目を比較する
：
R表の2行目とS表のn行目を比較する
：
：
R表のn行目とS表の1行目を比較する
R表のn行目とS表の2行目を比較する
：
R表のn行目とS表のn行目を比較する

入れ子ループ法における比較回数はR表のタプル数(行数)とS表のタプル数の積になるため、2つの表に存在するタプルがともにn個であれば、計算量は「n×n＝n²回」に比例することになります。

したがって「ウ」が正解です。