平成23年度秋期 情報処理安全確保支援士 午前Ⅱ 問21

データベースのテーブルから列（属性）を切り出す「射影」のパターンの数を、部分集合の考え方で数える

データベース（関係モデル）の「射影」に関する数学的な問題だよ。射影とは、テーブルの中から特定の「列（属性）」だけを選んで抜き出す操作のこと。もしテーブルに n 個の列がある時、それぞれの列を「抜き出すか（1）」「抜き出さないか（0）」の2択を n 回繰り返すことになるよね。これは数学でいう「部分集合の総数」と同じなので、列をまったく選ばない（0個）ケースも含めると、異なる射影の組み合わせパターンは全部で 2^n 個になるんだよ。

この問題で問われていること

データベースの「射影（列選択）」操作が、属性集合の部分集合を求める行為であると理解し、要素数 n の集合が持つ部分集合の総数を求める公式 2^n を用いて解答を導き出そう。

射影数の考え方

各属性について「選ぶ」「選ばない」の 2 通りがあるため、n 属性全体では 2 を n 回掛けて 2^n 通りになります。

各属性: 選ぶ / 選ばない\n-> 2^n 通り

確認ポイント

• 属性なしも含めるので、1 つ増えることを忘れないでください。
• n 個や n^2 個ではありません。
• 2^n を選びます。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

nは不正解だよ。n個の属性から1個だけ選ぶならn通りだけど、射影では「名前と住所を選ぶ」みたいに複数の属性をまとめて選べるんだ。窓口で書類を1枚だけしか取れないわけじゃなく、必要な書類を組み合わせて取れるので、n通りでは足りないよ。

選択肢イ

2nは不正解だよ。各属性に「使う／使わない」の2択があるのは合っているけど、それを単に2×nと足し算っぽく数えるのは違うんだ。鍵がn本あって、それぞれ持つか置くかを組み合わせるので、2通りがn回重なって2^n通りになるよ。

選択肢ウ

n^2は不正解だよ。n^2は『1つ目をn通り、2つ目もn通り』のようなペアを作る数え方に近いんだ。でも射影は属性の順番付きペアを作る話ではなく、どの属性セットを取り出すかの話だよ。買い物かごに商品を入れる／入れないを決める感じなので、n^2ではなく2^n通りになるよ。

選択肢エ（正解）

これは正解だよ。属性がn個ある表で射影する列の選び方は、各列ごとに「使う／使わない」の2択になるんだ。合鍵をn本並べて、1本ずつ「持っていく／置いていく」を決める感じだね。属性なしφも「全部置いていく」パターンとして数えるので、全部で2^n通りになるよ。