データベーススペシャリスト 2011年 午前2 問10

属性ドメインの直積要素数【午前2解説】

正解の理由

解法ステップ

1. 属性 A, B のドメインを集合 $A,B$ として、要素数をそれぞれ $m,n$ と定義する。
2. 関係 R(A, B) の可能なタプルは $(a,b)$ の形の順序対で、これは $A\times B$（直積）の要素であると認識する。
3. 直積 $A\times B$ の要素数は、各 $a\in A$ に対して $B$ の全 $n$ 個の要素と組になれるため、$m\times n$ となる。
4. よって R の最大タプル数は $mn$。

選択肢別の誤答解説

• ア: $2^m{2}^n$
  これは $2^m$ が集合 $A$ の部分集合の個数、$2^n$ が集合 $B$ の部分集合の個数であり、部分集合の組合せの数を表す。タプル（順序対）の数とは無関係で、誤りです。また $2^m{2}^n=2^{m+n}$ となり、意味が全く異なります。
• イ: $(m+n{)}^2$
  要素数を単純に足して二乗する根拠が無く、直積や順序対の組合せを正しく表していません。例えば $m=1,n=1$ のとき $(m+n{)}^2=4$ ですが、直積の要素は1個しかありません。
• ウ: $m+n$
  単に要素数を足すと、各ペアの組合せ（掛け算）を表さないため不足します。例えば $m=2,n=3$ の場合、$m+n=5$ ですが実際の最大タプル数は $6$ です。
• エ: $mn$（正答）
  それぞれの $A$ の要素に対して $B$ の全要素が組合せとなるため、全組合せは $m$ 個が $n$ 個ずつ、合計 $mn$ 個となります。

よくある誤解

• 「$2^m$ や $2^n$ を使うのは正しいのでは？」
  $2^m$ は集合の部分集合の個数を表すため、タプル（順序対）の個数を求める問題では適用できません。
• 「属性の組合せだから足し算で良い」は誤り
  組合せの総数は各要素の“全組み合わせ”を考えるので掛け算で求めます（独立な選択の基本原理）。

補足コラム

• 最小値：関係 R は空集合（タプル0個）であり得るため、タプル数の下限は $0$ です。
• 最大値：前述の通り直積全体を含む場合は $mn$。
• 実務面：実際のデータベースでは主キー制約や外部キー制約、NULL 値の扱い、ドメインに特殊値が含まれるかどうかにより実際の行数はこの最大値より小さくなることが一般的です。
• 記法：直積は $A\times B$、関係の要素は順序対 $(a,b)$ と表記します。

FAQ