3DRX■
GitHub RSS

// post

Relational Algebra

关系代数

Updated

集合运算

  • 参与运算的关系具有相同的目
  • 相应的属性取自同一个域

并 Union ∪\cup

R∪S={t∣t∈R∨t∈S}R \cup S = \{t | t \isin R \vee t \isin S\}

差 Difference −-

R−S={t∣t∈R∧t∉S}R - S = \{t | t \isin R \wedge t \notin S\}

交 Intersection ∩\cap

R∩S={t∣t∈R∧t∈S}R∩S=R−(R−S)\begin{aligned} R \cap S &= \{t | t \isin R \wedge t \isin S\} \\ R \cap S &= R - (R - S) \end{aligned}

笛卡尔积 Cartesian Product ×\times

  • R: n 目关系，k1k_1 个元组
  • S: m 目关系，k2k_2 个元组
R×S={trts⌢∣tr∈R∧ts∈S}R \times S = \{ \mathop{t_r t_s}\limits^{\frown} | t_r \isin R \wedge t_s \isin S \}

结果有 m+nm + n 列和 k1×k2k_1 \times k_2 行。

关系运算

结果仍是表

记号

  • RR
  • t∈Rt \isin R
  • t[Ai]t[A_i]

设关系模式为 R(A1,A2,...,An)R(A_1, A_2, ..., A_n)，它的一个关系设为 RR， t∈Rt \isin R 表示 tt 是 RR 的一个元组，t[Ai]t[A_i] 则表示元组 tt 中相应对于属性 AiA_i 的一个分量。

  • AA
  • t[A]t[A]
  • A‾\overline{A}

AA 是属性列（属性组），t[A]t[A] 是元素 tt 在 AA 上各个分量的集合， A‾\overline{A} 是去掉某一列以外其他的列组成的属性组。

  • trts⌢\mathop{t_r t_s}\limits^{\frown}

原组的连接。

  • 象集 Images Set ZxZ_x

给定一个关系 R(X,Z)R(X, Z)，XX 和 ZZ 为属性组， 当 t[X]=xt[X] = x 时，xx 在 RR 中的象集为

Zx={t[Z]∣t∈R,t[X]=x}Z_x = \{t[Z] | t \isin R, t[X] = x\}

表示 RR 中属性组 XX 上值为 xx 的各个原组在 ZZ 上分量的集合。

选择 σ\sigma

σSdept=′IS′(Student)\sigma_{Sdept='IS'}(Student)

投影 Π\Pi

ΠSname,Sdept(Student)\Pi_{Sname, Sdept}(Student)

连接 ⋈\Join

R⋈AθBS={trts⌢∣tr∈R∧ts∈S∧tr[A]θts[B]}\begin{aligned} &R \underset{A \theta B}\Join S =\\ &\{ \mathop{t_r t_s}\limits^{\frown} | t_r \isin R \wedge t_s \isin S \wedge t_r[A] \theta t_s[B] \} \end{aligned}

常用的连接运算

  • 等值连接：上面 θ\theta 定义为 ==
  • 自然连接：特殊的等值连接，在结果中把重复的属性列去掉
  • 外连接：对于关系 RR 中有而关系 SS 中没有的元素， 外连接会创建对应的原组，将空缺设置为 NULL， 外连接分为左外连接、右外连接。

除 ÷\div

R÷S={tr[X]∣tr∈R∧ΠY(S)⊆Yx}R \div S = \{t_r[X] | t_r \isin R \wedge \Pi_Y(S) \subseteq Y_x\}

其中 YxY_x 是 xx 在 RR 中的象集，x=tr[X]x = t_r[X]。

例子

RR：

ABC
a1b1c2
a2b3c7
a3b4c6
a1b2c3
a4b6c6
a2b2c3
a1b2c1

SS：

BCD
b1c2d1
b2c1d1
b2c3d2

R÷SR \div S：

A
a1

步骤：

  1. 关系 RR 中 AA 可以取 4 个值
    • a1a1 在 RR 上的象集是 {(b1,c2),(b2,c3),(b2,c1)}\{(b1, c2), (b2, c3), (b2, c1)\}
    • a2a2 在 RR 上的象集是 {(b3,c7),(b2,c3)}\{(b3, c7), (b2, c3)\}
    • a3a3 在 RR 上的象集是 {(b4,c6)}\{(b4, c6)\}
    • a4a4 在 RR 上的象集是 {(b6,c6)}\{(b6, c6)\}
  2. SS 在 (B,C)(B, C) 上的投影为 {(b1c2),(b2,c1),(b2,c3)}\{(b1 c2), (b2, c1), (b2, c3)\} 只有 a1a1 的象集包含在了这之中，所以 R÷S={a1}R \div S = \{a1\}

思想：包含