データベーススペシャリスト試験 令和3年度 秋期 午前II 問9

【正解】エ

射影とは、関係から必要な属性、すなわち列を選び出す演算です。n個の各属性について、射影に「含める」か「含めない」かの2通りを独立に選べます。したがって、選び方の総数は、2をn回掛けた2ⁿ通りです。

例えば、属性がA、B、Cの3個であれば、属性集合の選び方は、空集合、｛A｝、｛B｝、｛C｝、｛A、B｝、｛A、C｝、｛B、C｝、｛A、B、C｝の8通りです。計算すると2³＝8です。問題では属性を全く含まない射影も数えるので空集合を除かず、全属性を含み元の関係と同じ結果になる射影も数えるので、2ⁿから何も差し引きません。

アのlog₂nは誤りです。これは「2を何乗すればnになるか」を表す対数であり、属性の部分集合の個数ではありません。

イのnは誤りです。これはn個の属性から一つだけを選ぶ場合、すなわち｛A｝、｛B｝など、属性数が1の射影だけを数えた個数です。複数の属性を同時に選ぶ場合や空集合を含んでいません。

ウの2nは誤りです。各属性に二つの選択肢があることを加算で数えた式です。属性ごとの選択は互いに組み合わされるので、2をn倍するのではなく、2をn回乗算します。

【ポイント】 n要素の集合がもつ部分集合の総数は2ⁿです。 空集合を除く場合は2ⁿ－1、空集合と全体集合の両方を除く場合は2ⁿ－2となります。