リレーショナル代数

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

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

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

集合演算

• 和集合(union): R∪S={t|t∈R∨t∈S}

• 共通集合, 積集合(intersection): R∩S={t|t∈R∧t∈S}

和両立(union compatible)

• リレーションスキーマR(A1,A2,…,An)とS(B1,B2,…,Bn)が次の2つの条件を満たすとき, リレーションRとSは和両立である.
  1. RとSの次元が等しい(つまりn=m)
  2. 各i(1≤i≤n) に対して, 属性Ai と Biのドメインが等しい(つまりdom(Ai)=dom(Bi))
• 必ずしも属性名は同じでなくてよい

直積演算

• 直積, デカルト積(Curtesiun product): R×S={(u,v)|u∈R∧v∈S

集合演算の演習

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

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

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

結果

• 和集合 Ra∪Rb

• 共通集合 Ra∩Rb

• 差集合 Ra-Rb

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

• R1

• R2

結果

• R1 × R2

関係演算

選択演算(selection)

リレーションRの中から条件式Fを満たすタプルを抽出する演算 σF(R)={t|t∈R∧PF(t)=true}

• 条件式Fの例
  • A1=′文字列′,A2>30,A1=A2
  • (年齢>20)∧(所属=′情報工学科′)

射影演算(projection)

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

結合演算(join)

二つのリレーションRとSを条件Fに従って一つのリレーションに結合する. 内部結合(inner join)とも呼ぶ. R⋈FS=(u,v)|u∈R∧v∈S∧PF((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について与えられた演算結果を求めよ

π日付,商品名(σ日付=2013/10/3(R))

• リレーションR

結果

商演算(division)

• R÷S=t|t∈πX−Y(R)∧∀u∈S:(t,u)∈R
  1. Sの各タプルに対して同じ値を持つRのタプルを選択
  2. Rの属性集合XからSの属性集合Yを除いた上で同じ値を持つタプルを集約
  3. Sのすべてのタプルを含んでいる場合に対応するタプルを選択

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

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

商演算の演習

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

サークル活動÷サークル

• サークル活動

• サークル

結果