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

問題文

属性が

n

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

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

選択肢

ア：

2 n

イ：

2^{n}

（正解）

ウ：

lo g_{2} n

エ：

n

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

射影の個数【午前2解説】

正解の理由

関係の各属性について「射影に含める／含めない」の2通りが独立に選べるため、属性の組み合わせ（部分集合）の総数は

2^{n}

となります。したがって選択肢の中ではイが正解です。

補足して重要な点を明示します。問題文は「元の関係と同じ結果となる射影」や「属性を全く含まない射影」も個数に含めるとしています。これは「属性の選択（＝属性集合の部分集合）」を数える問題であり、結果の重複（異なる属性集合が同じ出力を生む場合）があっても個々の射影は別物として数えることを意味します。また、射影は集合意味論（重複除去）を前提とするため、属性を全く含まない射影の出力は「属性数0の関係（スキーマが空）」になります。このとき元の関係が非空なら重複除去の結果として1つの空タプルを持ち、元が空なら空関係となる点に注意してください。

解法ステップ

射影で何を決めるかを確認する：射影は選ぶ属性の集合（どの属性を残すか）で決まる。
各属性について「残す／残さない」の2通りがあり、全属性で独立に選べる。
よって総数は $2^{n}$ （全ての部分集合の個数）。別の表現として $k = 0 \sum n (k n) = 2^{n}$ が成立する。
例： $n = 3$ のとき、選べる射影は $2^{3} = 8$ 通り（空集合から全属性集合まで）。

選択肢別の誤答解説

ア: $2 n$
属性ごとに2通りを掛け合わせるべきところを、単に2と $n$ を掛けた線形増加で表しており、組合せの総数を誤って評価しています。
ウ: $lo g_{2} n$
対数は今回の選択肢数の性質にそぐわず、根拠がありません。属性数が増えると選択肢数は指数的に増えるため対数は不適切です。
エ: $n$
これは「1つだけ属性を選ぶ場合」のみを数えた値で、空集合や複数属性を選ぶ場合を含めていません。

よくある誤解

属性を全く含まない射影は常に「空関係」になる、という誤解。実際にはスキーマ（属性）が空の関係となり、元データが非空なら1つの空タプルが残ります。元が空なら空関係です。
射影の個数を「異なる結果（出力関係）の個数」と混同する誤解。問題は属性選択の組合せを数えるため、出力が同じでも属性集合が異なれば別の射影として数えます。
SQL の SELECT と混同して、重複が残る（bag semantics）前提で考える誤り。関係代数の射影は集合意味論で重複を除去します（設問の数え方自体は属性集合の数なので影響は限定的ですが、出力の議論では重要です）。

補足コラム

この問題は組合せ論の基礎である冪集合（べきしゅうごう、power set）と直接対応します。属性集合の全ての部分集合が射影の取りうる通りで、冪集合の大きさは

2^{n}

です。実務面では、SQLで複数の列をSELECTする操作が射影に相当しますが、SQLでは明示的に DISTINCT を付けて重複排除を行わない限り、出力に重複が残る（bag semantics）点に注意してください。関係代数の射影は重複を除く点がモデル上の違いです。

FAQ

Q1: n=0（属性が0個）のときはどうなる？
A1:

2^{0} = 1

で射影は1通り（空集合のみ）。出力は属性数0の関係で、元の関係が非空なら1つの空タプル、元が空なら空関係になります。

Q2: 「元の関係と同じ結果となる射影」も数えるとあるが、同じ結果ならまとめて良いのでは？
A2: 問題文が「射影そのもの（どの属性を選ぶか）」を数える設問なので、たとえ結果が同じでも属性集合が異なれば別個の射影として数えます。

Q3: 重複除去をしない（bag semantics）の場合、答えは変わるか？
A3: 問題は射影の「種類」（属性選択の数）を数えるため、答えは属性数に依存して

2^{n}

のままです。ただし、実際の出力の個数（異なる関係の数）はデータによって小さくなる可能性があります。

関連キーワード: 関係代数、射影、冪集合、組合せ、属性選択、重複除去、部分集合、冪乗数

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！