データベーススペシャリスト 平成27年春期 午前U 問17

午前U 問17

関係データベースにおいて,タプル数nの表二つに対する結合操作を,入れ子ループ法によって実行する場合の計算量はどれか。
  • [この問題の出題歴]
  • データベース H14春期 問43
  • データベース H24春期 問18
  • データベース H29春期 問19

分類

テクノロジ系 » データベース » データ操作

正解

解説

入れ子ループ法(ネストループ法)は、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表のタプル数の積になるため、各表に存在するタプルが共にn個であれば、計算量はn×n=n2に比例することになります。

したがって「ウ」が正解です。
© 2016-2018 データベーススペシャリストドットコム All Rights Reserved.

Pagetop