データベーススペシャリスト 2017年午前2 問13

問題文

属性がn個ある関係の異なる射影は幾つあるか。ここで、射影の個数には、元の関係と同じ結果となる射影、及び属性を全く含まない射影を含めるものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：

2 n

イ：

2^{n}

（正解）

ウ：

lo g_{2} n

エ：

n

🔒 解説は解答すると表示されます

関係の射影の総数【午前2解説】

正解の理由

射影は「どの属性を残すか」を選ぶ操作であり、各属性ごとに「残す／残さない」の2通りの選択が独立にあるため、全体で選べる射影の通り数は

2^{n}

です。問題文で「元の関係と同じ結果となる射影、及び属性を全く含まない射影を含める」と明記されているため、空集合（属性を全く含まない射影）や全属性を残す射影もカウントに入ります。したがって射影の個数は

2^{n}

で、イが正解です。

（補足）各射影は属性の部分集合に一対一対応します。部分集合の総数はべき集合の要素数

2^{n}

で与えられます。

解法ステップ

射影操作は「属性集合の部分集合を選ぶ」ことと同値と認識する。
各属性について「含める／含めない」の2通りの選択が独立にあるため、通り数は $2 \times 2 \times \dots \times 2$ （n個）で $2^{n}$ 。
組合せ的に書くと、全ての $k$ 個選ぶ場合の和で表せる： $\sum_{k = 0}^{n} (k n) = 2^{n} .$
例： $n = 3$ のとき、選べる射影は空集合、{A}、{B}、{C}、{A,B}、{A,C}、{B,C}、{A,B,C} の計8通り。

選択肢別の誤答解説

ア: $2 n$
- 各属性について2通りあることを「単純に2×n」と誤解した形。属性ごとの独立な選択は掛け合わせて（累乗で）数える必要があるため不適切。
イ: $2^{n}$ （正解）
- 属性の部分集合の数で、空の射影と元の関係と同じ射影も含みます。
ウ: $lo g_{2} n$
- 対数は成長の尺度であり、選択肢数を表すには不適合。属性数が増えると通り数は指数的に増える（ $2^{n}$ ）のに対し、 $lo g_{2} n$ は非常に小さい値になる。
エ: $n$
- 「1つだけ属性を選ぶ場合」のみを数えている誤り。空集合や複数属性を残す場合も含める必要があるため不適切。

よくある誤解

射影の「結果として得られる関係の件数」を数えると解釈してしまう誤り：実データによっては異なる属性集合が同一の結果（同じタプル集合）を返すことがあり得ますが、本問は「射影操作の種類（選ぶ属性の組）」を数える設問である点を見落としやすいです。
空の射影（属性を全く含まないもの）を忘れるミス：設問で明示しているため含める必要があります。
「組み合わせ」と「順列」を混同する：属性の選択は順序を持たない部分集合の問題です（順序を考えると別問題になる）。

補足コラム

リレーショナル代数の射影（π）は、属性（列）の選択を行い、通常は重複タプルを排除して結果の「関係」を返します。したがって実際のデータ次第では、異なる属性集合が同一の結果関係を生むことがあります。試験問題のように「射影の個数」を理論的に問う場合は属性集合の取り得る部分集合の数＝べき集合の大きさ

2^{n}

を用いるのが標準的です。

また、計算上は2進表現で直感的に理解できます。各属性をビットに対応させ、1なら含む、0なら含まないとすると、nビットで表せるパターン数は

2^{n}

です。

FAQ

Q1: 「異なる射影」って属性の組み合わせを指しますか？
A1: はい。本問は射影操作そのもの（どの属性を選ぶか）を数える設問であり、属性集合ごとに1つとして数えます。

Q2: 実データによっては

2^{n}

より少なくならないですか？
A2: 実データで結果が重複する場合、得られる異なる「結果関係」の数は

2^{n}

以下になります。しかし本問は理論的な射影の種類を問うもので、データ依存性は考慮しません。

関連キーワード: 関係代数、射影、部分集合、べき集合

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

データベーススペシャリストを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！