ホーム > データベーススペシャリスト試験 > 2019年
データベーススペシャリスト試験 2019年 午前2 問16
関係データベースにおいて, タプル数nの表二つに対する結合操作を, 入れ子ループ法によって実行する場合の計算量はどれか。
ア：
イ：
ウ：（正解）
エ：
解説
関係データベースにおける入れ子ループ結合の計算量について
問題の背景
関係データベースでの**結合操作（Join）**は、2つの表（関係）を指定した条件に基づいて組み合わせ、新しい表を作り出す操作です。結合はSQLにおいて非常に基本的かつ重要な操作であり、効率的な実装が求められます。
今回は、タプル数がそれぞれ ( n ) の2つの表（関係）に対し、入れ子ループ（nested loop）法で結合を行ったときの計算量について考えます。
入れ子ループ法（Nested Loop Join）とは？
入れ子ループ法は結合の中で最も単純なアルゴリズムの一つです。
- 表1の各タプルを順に取り出す。
- そのタプルと結合条件に合致するかどうか、表2のすべてのタプルと順に比較する。
- 条件に合えば、結合されたタプルを出力する。
この手順を簡単な擬似コードで表すと、
for each tuple t1 in table1:
for each tuple t2 in table2:
if (t1, t2) satisfy join condition:
output combined tuple
計算量の解析
- 表1に ( n ) 個のタプルがある。
- 表2にも ( n ) 個のタプルがある。
入れ子ループなので、
- 外側ループは ( n ) 回実行。
- 内側ループも各回で ( n ) 回実行。
よって、全体での比較回数は、
となります。つまり、計算量は**二乗時間（( O(n^2) )）**です。
他の選択肢との比較
- ( O(2n) ) はリニア（線形）ですが、ループが二重なので考えにくいです。
- ( O(\log n) ) は高速すぎて不適切。二分探索などを使う場合の時間計算量ですが、単純な入れ子ループではありません。
- ( O(n \log n) ) はソート結合など、ソート操作が絡む場合に該当しますが、単純なループ結合ではありません。
まとめ
本問題の入れ子ループ法の場合、正解は
となります。
参考文献
- 「データベースシステム概論」 石田晴久 著
- 「Database System Concepts」 Silberschatz et al.
以上より、問題の正解「ウ: ( O(n^2) )」が妥当であることが理解できるでしょう。