令和5年度 秋期 データベーススペシャリスト 午前Ⅱ 問1 関係代数
本問題は、関係代数の基本演算の組み合わせが、どの演算の定義と一致するかを問うています。直積・選択・射影の合成による「結合」の成立過程を理解することが肝要です。
【問題】 関係 R と関係 S に対して、次の手順で行う演算の結果はどれか。
① R と S の直積（デカルト積）を求める。 ② ①の結果から、R の属性 A と S の属性 B の値が等しいという条件で選択（選択）を行う。 ③ ②の結果から、R と S の全属性（重複する属性は除く）を抽出（射影）する。
ア：差 イ：結合 ウ：交わり エ：和
【解説】 関係データベースの理論的基礎である関係代数において、複数の基本演算を組み合わせることで、より高度な操作を定義できます。本問の手順は、リレーショナルデータベースで最も多用される「等結合（Equi-join）」の定義そのものです。
直積 ($R \times S$): 2つの関係のすべてのタプルの組み合わせを作成します。
選択 ($\sigma_{C}$): 直積の結果から、特定の条件（$R.A = S.B$ など）に合致する行のみを抽出します。
射影 ($\pi_{L}$): 抽出された行から、必要な列（属性）のみを取り出します。
これら一連の流れは、数学的に以下の等式で表されます。
$$ R \bowtie_{R.A=S.B} S = \pi_{L}(\sigma_{R.A=S.B}(R \times S)) $$
graph TD
R["関係R"] --> Product["直積 R × S"]
S["関係S"] --> Product
Product --> Selection{"選択 σ R.A=S.B"}
Selection --> Projection["射影 π"]
Projection --> Result["結合結果 R ⨝ S"]
【選択肢の吟味】
| 選択肢 | 判定 | 解説 |
|---|---|---|
| ア | 誤り | 差（$R – S$）は、Rに含まれSに含まれないタプルを抽出する演算であり、直積は使用しません。 |
| イ | 正解 | 直積、選択、射影をこの順で行う演算は、内部結合（特に等結合）の定義に合致した操作です。 |
| ウ | 誤り | 交わり（$R \cap S$）は、RとSの両方に共通するタプルを抽出する演算です。 |
| エ | 誤り | 和（$R \cup S$）は、RまたはSに含まれるすべてのタプル（重複除外）を抽出する演算です。 |
【ポイント】
結合（Join）の本質: 直積集合から条件に合うものをフィルタリングする操作である。
和・差・交わりの前提: これらの集合演算を行うには、属性数とドメインが一致する「型適合（Union-compatibility）」が必要。
直積の計算量: タプル数が $n, m$ の場合、直積の結果は $n \times m$ となり、大規模データでは選択を先に行う最適化が重要。
