リレーショナル代数

これは大学の講義内容をまとめたものです。

リレーショナル「代数」とは

• 単一または複数のリレーションに対して定義された演算の体系
  • 線形「代数」: 線形空間の元（ベクトル）に対する和, 内積などの演算の体系
• SQL言語の基礎
  • 集合演算
  • 関係演算(リレーショナル演算)

集合演算

• 和集合(union): \( R \cup S = \{t|t\in R \vee t \in S \} \)

• 共通集合, 積集合(intersection): \( R \cap S = \{t|t\in R \wedge t \in S \} \)

和両立(union compatible)

• リレーションスキーマ\( R(A_1, A_2, …, A_n) \)と\( S(B_1, B_2, …, B_n) \)が次の2つの条件を満たすとき, リレーションRとSは和両立である.
  1. RとSの次元が等しい(つまりn=m)
  2. 各\( i(1 \leq i \leq n)\) に対して, 属性\( A_i \) と \( B_i \)のドメインが等しい(つまり\( dom(A_i)=dom(B_i)\))
• 必ずしも属性名は同じでなくてよい

直積演算

• 直積, デカルト積(Curtesiun product): \( R \times S = \{ (u, v) | u \in R \wedge v \in S \)

集合演算の演習

(1) 下記に示すリレーションRaとRbに対して、和集合、共通集合、差集合の各演算結果を求めよ

• A店舗取り扱い商品リスト Ra

• B店舗取り扱い商品リスト Rb

結果

• 和集合 Ra\( \cup \)Rb

• 共通集合 Ra\( \cap \)Rb

• 差集合 Ra-Rb

(2)下記に示すリレーションR1, R2に対して直積集合R1\(\times\)R2を求めなさい

• R1

• R2

結果

• R1 \( \times \) R2

関係演算

選択演算(selection)

リレーションRの中から条件式Fを満たすタプルを抽出する演算 $$ \sigma_F(R) = \{ t | t \in R \wedge P_F(t) = true \} $$

• 条件式Fの例
  • \( A_1 = ’文字列’, A_2 > 30, A_1 = A_2 \)
  • \( (年齢 > 20) \wedge (所属=’情報工学科’) \)

射影演算(projection)

リレーションRから, 指定した属性集合βのみを持つリレーションを抽出する演算 $$ \pi_\beta(R) = { t[\beta] | t \in R } $$

結合演算(join)

二つのリレーションRとSを条件Fに従って一つのリレーションに結合する. 内部結合(inner join)とも呼ぶ. $$ R ⋈_F S = { (u, v) | u \in R \wedge v \in S \wedge P_F ((u, v) = true) } $$

等結合(equi-join)

結合演算の条件Fとして, 二つのリレーションの対応する属性が等しいことを用いるもの.

自然結合演算(natural join)

等結合で得られるリレーションから重複する属性を射影により取り除いたもの

• 交換法則と結合法則が成り立つ $$ R ⋈ S = S ⋈ (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T) $$

外部結合演算(outer join)

一方のリレーションRのタプルのうち, もう一方のリレーションSに対応するタプルがないものは, 対応するSの属性値をNULLにする

• 左外部結合(left outer join) 左側のタプルを残す
• 右外部結合(right outer join) 右側のタプルを残す
• 完全外部結合(complete outer join) 両方のタプルを残す

集合演算の演習

(1)下記に示すリレーションRとSに対して, 結合条件を両リレーションにおける属性Bが等しいとした場合の内部結合, 自然結合, 左外部結合, 右外部結合, 完全外部結合の各演算結果を求めよ

• リレーションR

• リレーションS

結果

• 内部結合

• 自然結合

• 左外部結合

• 右外部結合

• 完全外部結合

以下のリレーションRについて与えられた演算結果を求めよ

$$ \pi_{日付,}{}_{商品名}(\sigma_{日付=2013/10/3}(R)) $$

• リレーションR

結果

商演算(division)

• \( R \div S = { t | t \in \pi_{X-Y}(R) \wedge \forall_u \in S: (t, u) \in R } \)
  1. Sの各タプルに対して同じ値を持つRのタプルを選択
  2. Rの属性集合XからSの属性集合Yを除いた上で同じ値を持つタプルを集約
  3. Sのすべてのタプルを含んでいる場合に対応するタプルを選択

商演算は直積演算の逆演算

• 整数などの商演算と同じように\( (R \times S) \div S = R \)が成立
• \( (R \div S) \times S = R \)は成立しない(整数演算と同じ)

商演算の演習

次のリレーション、サークル活動、サークルに対して与えられた演算結果を求めなさい

$$ サークル活動 \div サークル $$

• サークル活動

• サークル

結果