リレーションの演算と述語論理

• 各種リレーションの演算を述語論理の側面から見る

  • リレーションは集合
  • 集合と述語は1対1対応

制限(Restrict)

• 対象のリレーションに対して新たな述語を導入

P(t)∧Q(t)

• where

  • P(t): リレーションRの述語
  • Q(t): 制限を表現する述語

直積(Product)

• R1とR2という2つの前提となる事実(の集合)から、どのような新たな事実(の集合)が導き出されるか

P(t1)∧Q(t2)

結合(Join)

• 直積は結合の特殊なパターン

P(t1)∧Q(t2)

• 共通の属性が存在

  • zは自由変項なので、P(x, z)のzとQ(y, z)のzとは同じ意味

P(x, y)∧Q(x, z)

R1

R2

R3

• 他のタプルはP(x, y)またはQ(x, y)を真にしない
• 結合後の述語は1つの意味を持つため、次のようにも表現できる

F(x, y, z)

積(Intersect)

• 結合の特殊なケース
• タプルの属性が完全に一致する

P(t)∧Q(t)

コラム: 結合と制限

• 積と制限は同じ形

P(t)∧Q(t)

• 本質的に同じもの
• 制限: ドメインのすべての組み合わせのうち、Q(t)に適合するものの集合との積

和(Union)

P(t)∨Q(t)

差(Difference)

• ベン図省略

P(t)∧¬Q(t)

• NOT EXISTSで代用できることがひと目でわかる

射影(Projection)

• 述語の変数が落ちる

「xはyという学校に通っている」

• 射影をとると

「xは学校に通っている」

• 「射影」

  • タプルの属性が減る = 次元が低くなる感じ

属性名変更(Rename)

• 論理式としての構造に変化はない

拡張(Extend)

• 論理演算以外の何らかの法則で新たな事実を導き出す

  • 身長と体重からBMIとか

コラム: 外部結合について

• 外部結合はリレーショナルモデルの観点でいう「結合」ではない

• むしろ集合和

  • 【補】ただし、タプルの属性にNULLを含むので集合ですらない説

SELECT t1.x, t2.y
  FROM t1
  LEFT OUTER JOIN t2
    ON t1.z = t2.z;

• 意味的に同じクエリ

SELECT t1.x, t2.y
  FROM t1
 INNER JOIN t2
    ON t1.z = t2.z
 UNION
SELECT t1.x, NULL
  FROM t1
 WHERE t1.z NOT IN (SELECT z
                      FROM t2);