关系演算与关系代数

1) 关系代数 vs 关系演算：本质区别（考试常考一句话）

• **关系代数（RA）更“操作式”：你要写出怎么做（先选、再连、再投影……），强调运算顺序。
• **关系演算（RC）更“声明式”：你只描述答案需要满足什么逻辑条件，不强调计算步骤。课件明确说：RA 需要指定操作顺序，而 RC 只需给出结果满足的逻辑条件。

关系演算分两种：

• TRC：变量取值是“元组”（tuple）。
• DRC：变量取值是“域值/属性值”（domain elements）。

2) 域关系演算 DRC 的语法骨架（课件给的“标准模板”）

DRC 查询形如：

$\{⟨x_1,\dots ,x_n⟩\mid P(x_1,\dots ,x_n,x_{n+1},\dots )\}$

其中左边出现的是输出变量，右边是逻辑公式 P。

公式（formula）由原子公式递归构造：

• 原子：<…> ∈ R 或 X op Y / X op 常量

• 连接：¬, ∧, ∨

• 量词：∃、∀

  并且课件强调：‘|’左侧出现的变量必须是公式里唯一的自由变量（其它变量必须被量词绑定）。

3) 从关系代数推导等价关系演算：最常用的“翻译规则”

课件在“Relational Algebra vs. Relational Calculus”页直接给了 RA→RC 的核心对应（以 tuple 变量 t 表示结果元组的一种写法）：投影、选择、并、差、连接。

我把它整理成可直接套用的“推导模板”（同时给 TRC 与 DRC 的写法）。你复习时可以把它当成“翻译字典”。

3.1 选择 Selection：${\sigma }_F(E)$

直觉：答案来自 E，并且满足条件 F。

• TRC（元组变量）：

  $\{t\mid t\in E\wedge F(t)\}$

• DRC（域变量）：如果 E 的模式是 (A_1,\dots,A_k)，写成

  $\{⟨a_1,\dots ,a_k⟩\mid ⟨a_1,\dots ,a_k⟩\in E\wedge F(a_1,\dots ,a_k)\}$

课件例子（DRC）：找 rating>7 的水手：

$\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge T>7\}$

3.2 投影 Projection：${\pi }_L(E)$

直觉：输出只保留 L 这些列；因此需要“存在某个完整元组来自 E，并且输出列等于它在这些列上的取值”。

• TRC：设输出元组为 u，输入元组为 t：

  $\{u\mid \exists t(t\in E\wedge u[L]=t[L])\}$

• DRC：如果要投影出 $⟨x_1,\dots ,x_m⟩$，就让“其余列”用 ∃ 隐去：

  $\{⟨x_1,\dots ,x_m⟩\mid \exists y_1,\dots (⟨x_1,\dots ,x_m,y_1,\dots ⟩\in E)\}$

课件的“投影对应”写法是：

${\pi }_{AB}=\{t[AB]\mid t\in r\}$

（你可以把它理解为：输出元组就是输入元组在 AB 两列上的“截取”。）

3.3 并 Union：$E_1\cup E_2$

直觉：来自任一边即可。

• TRC：$\{t\mid t\in E_1\vee t\in E_2\}$
• DRC：同理，右侧用 “∨”。

课件对应：$r\cup s=\{t\mid t\in r\vee t\in s\}$

3.4 差 Set Difference：$E_1-E_2$

直觉：在 E_1 中且不在 E_2 中。

• TRC：$\{t\mid t\in E_1\wedge \neg (t\in E_2)\}$
• DRC：同理。

课件对应：$r-s=\{t\mid t\in r\wedge \neg (t\in s)\}$

3.5 连接 Join：$E_1\bowtie E_2$ 或 $E_1{\bowtie }_{\theta }{E}_2$

直觉：结果元组的“左半部分”来自 E_1，右半部分来自 E_2，并满足连接条件（或自然连接条件）。

课件给的一个总括写法（把结果视为拥有合并后的属性 ABCDE）：

$r\bowtie s=\{t(ABCDE)\mid t[ABC]\in r\wedge t[CDE]\in s\}$

更“可操作”的写法（方便你考试推导）：

• TRC（θ-join）：

  $\{t\mid \exists t_1\exists t_2(t_1\in E_1\wedge t_2\in E_2\wedge \theta (t_1,t_2)\wedge t=\text{merge}(t_1,t_2))\}$

• DRC：把两个关系的域变量列出来，并用等式把“连接列”绑在一起。

4) 课件核心例子：用 DRC 写出来（并给出等价 RA / TRC）

下面的例子几乎就是你考试最可能遇到的“推导题”模板。

为统一，沿用课件三张表：Sailors(sid,sname,rating,age), Reserves(sid,bid,day), Boats(bid,bname,color)。

例1：找 rating > 7 的水手（Selection）

• RA：${\sigma }_{rating>7}(Sailors)$（若只要输出全部列就不用投影）

• DRC（课件原式）：

  $\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge T>7\}$

• TRC（常见写法）：$\{s\mid s\in Sailors\wedge s.rating>7\}$

例2：rating > 7 且预订过 103 号船（Join + Selection）

• RA（一个标准写法）：

  ${\pi }_{S.sid,S.sname,S.rating,S.age}\left({\sigma }_{S.rating>7\wedge R.bid=103}(SailorsS{\bowtie }_{S.sid=R.sid}ReservesR)\right)$

• DRC（课件原式）：

  $\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge T>7\wedge \exists Ir,Br,D(⟨Ir,Br,D⟩\in Reserves\wedge Ir=I\wedge Br=103)\}$

  你可以把它读成：

  “输出一个 Sailors 元组，并且存在一条 Reserves 元组跟它 sid 相等，且 bid=103。”

• TRC（等价写法）：

  $\{s\mid s\in Sailors\wedge s.rating>7\wedge \exists r(r\in Reserves\wedge r.sid=s.sid\wedge r.bid=103)\}$

例3：rating > 7 且预订过红船（Join 三表 + Selection）

• RA（标准写法）：

  ${\pi }_{S.sid,S.sname,S.rating,S.age}\left({\sigma }_{S.rating>7\wedge B.color{=}^{\prime }re{d}^{\prime }}(S{\bowtie }_{S.sid=R.sid}R{\bowtie }_{R.bid=B.bid}B)\right)$

• DRC（课件原式）（注意量词作用域由括号控制）：

  其含义就是：存在一条 Reserves 元组与水手匹配，且存在一条 Boats 元组与该预订匹配，并且颜色为 red。

• TRC（等价写法）：

  $\{s\mid s\in Sailors\wedge s.rating>7\wedge \exists r\exists b(r\in Reserves\wedge b\in Boats\wedge r.sid=s.sid\wedge r.bid=b.bid\wedge b.color{=}^{\prime }re{d}^{\prime })\}$

例4：预订了所有船的水手（Division / 全称量词）

A) TRC（元组关系演算）——最标准写法

如果你想输出“水手元组”本身（即整行 Sailors）：

$\{s\mid s\in Sailors\wedge \forall b(b\in Boats\to \exists r(r\in Reserves\wedge r.sid=s.sid\wedge r.bid=b.bid))\}$

读法：

“取一个水手 s；对每一条船 b，只要 b 是 Boats 里的船，就必须存在一条预订记录 r，使得 r 的 sid 等于 s.sid 且 r 的 bid 等于 b.bid。”

如果你只想输出水手的 sid（而不是整行），可以写成：

$\{⟨s.sid⟩\mid s\in Sailors\wedge \forall b(b\in Boats\to \exists r(r\in Reserves\wedge r.sid=s.sid\wedge r.bid=b.bid))\}$

B) DRC（域关系演算）——把元组拆成域变量

版本1：输出整行水手 $⟨I,N,T,A⟩$

$\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge \forall B,BN,C(⟨B,BN,C⟩\in Boats\to \exists D(⟨I,B,D⟩\in Reserves))\}$

解释：

• I,N,T,A 是水手的 sid/sname/rating/age
• (B,BN,C) 是船的 bid/bname/color
• D 是预订日期 day
• “对每个 Boats 的 bid=B，都存在 Reserves 里一条 sid=I, bid=B 的记录”

版本2：只输出 sid（更像除法的结果）

$\{⟨I⟩\mid \exists N,T,A(⟨I,N,T,A⟩\in Sailors)\wedge \forall B,BN,C(⟨B,BN,C⟩\in Boats\to \exists D(⟨I,B,D⟩\in Reserves))\}$

---

这是“除法/全称量词”最典型的题。

• RA（用除法表达）：

  令 $A={\pi }_{sid,bid}(Reserves)，B={\pi }_{bid}(Boats)$，则答案 sid 集合是

  $A÷B$

  然后再和 Sailors 连接拿到姓名等信息。

• DRC（课件写法 1：显式 ∀）：

  逻辑读法：对每一条 Boats 元组（每条船），都存在一条 Reserves 元组证明该水手预订过它。

• DRC（课件写法 2：更简洁版本）：

• “所有红船”的变体（课件提示）：

  把“对所有船”改成“对所有非红船放行、对红船必须存在预订”，其典型结构是

  $(C{\ne }^{\prime }re{d}^{\prime }\vee \exists \text{Reserves}(\cdots ))$

你在做推导题时，可以把“除法”直接翻译成：∀（目标集合中的每个 y）→ ∃（证明 x 和 y 的关联存在）。这正是课件中“reserved all boats”用 ∀/∃ 表达的核心。

5) 再补一组“全面覆盖运算”的自造例子（RA ↔ DRC ↔ TRC）

这些例子用来把课件那张对应表（投影/选择/并/差/连）真正练熟。对应关系本身在课件页已给出。

例5：并（Union）

题意：找“rating>8 的水手”或“age<30 的水手”。

• RA：${\sigma }_{rating>8}(Sailors)\cup {\sigma }_{age<30}(Sailors)$
• DRC：$\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge (T>8\vee A<30)\}$
• TRC：$\{s\mid s\in Sailors\wedge (s.rating>8\vee s.age<30)\}$

例6：差（Set difference）

题意：找“订了 103 但没订 101”的水手 sid。

• RA：${\pi }_{sid}({\sigma }_{bid=103}(Reserves))-{\pi }_{sid}({\sigma }_{bid=101}(Reserves))$

• DRC：

  $\{⟨I⟩\mid \exists D(⟨I,103,D⟩\in Reserves)\wedge \neg \exists D^{\prime }(⟨I,101,D^{\prime }⟩\in Reserves)\}$

• TRC：

  $\{⟨r.sid⟩\mid r\in Reserves\wedge r.bid=103\wedge \neg \exists r^{\prime }(r^{\prime }\in Reserves\wedge r^{\prime }.sid=r.sid\wedge r^{\prime }.bid=101)\}$

例7：连接（Join）+ 投影（Projection）

题意：列出所有预订记录对应的 (sname, bid, day)。

• RA：${\pi }_{sname,bid,day}(Sailors{\bowtie }_{S.sid=R.sid}Reserves)$

• DRC：

  $\{⟨N,B,D⟩\mid \exists I,T,A(⟨I,N,T,A⟩\in Sailors\wedge ⟨I,B,D⟩\in Reserves)\}$

• TRC：

  $\{⟨s.sname,r.bid,r.day⟩\mid s\in Sailors\wedge r\in Reserves\wedge s.sid=r.sid\}$

例8：笛卡尔积（×）+ 选择（σ）实现“配对”

题意：找所有不同的水手对 (s1,s2)，要求 s1.sid < s2.sid。

• RA：${\sigma }_{S1.sid<S2.sid}({\rho }_{S1}(Sailors)\times {\rho }_{S2}(Sailors))$

• DRC（示意）：

  $\{⟨I_1,N_1,I_2,N_2⟩\mid ⟨I_1,N_1,T_1,A_1⟩\in Sailors\wedge ⟨I_2,N_2,T_2,A_2⟩\in Sailors\wedge I_1<I_2\}$

• TRC：同理，用两个元组变量 s1,s2。

6) “安全性（unsafe）”与“关系完备性”：为什么强调“从 RA 推 RC”不会跑飞

课件提醒：有些演算式子虽然语法对，但会产生无限答案（unsafe），例如$\{S\mid \neg (S\in Sailors)\}$。

同时课件也给了结论：RA 能表达的查询，都能写成 DRC/TRC 的安全查询；反之亦然，并称为“关系完备性”。

这对你做题的意义是：

• 你按上面的“逐算子翻译模板”从 RA 推出来的 RC，通常天然是“安全”的（因为每个变量都被某个关系的成员关系绑定，符合课件对自由/约束变量的要求）。

变体：预订了“所有红船”的水手（常考）

A) TRC

$\{s\mid s\in Sailors\wedge \forall b((b\in Boats\wedge b.color{=}^{\prime }re{d}^{\prime })\to \exists r(r\in Reserves\wedge r.sid=s.sid\wedge r.bid=b.bid))\}$

B) DRC（两种等价写法，你背一种就行）

写法1（用蕴含）：

$\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge \forall B,BN,C((⟨B,BN,C⟩\in Boats\wedge C{=}^{\prime }re{d}^{\prime })\to \exists D(⟨I,B,D⟩\in Reserves))\}$

写法2（用“非红船放行”形式，更贴近课件那句 C\neq ‘red’ \lor \exists…）：

$\{⟨I,N,T,A⟩\mid ⟨I,N,T,A⟩\in Sailors\wedge \forall B,BN,C(⟨B,BN,C⟩\in Boats\to (C{\ne }^{\prime }re{d}^{\prime }\vee \exists D(⟨I,B,D⟩\in Reserves)))\}$

一句话把“除法 → 演算”记牢

RA 的 A \div B（“对 B 中每个 y，都能在 A 中找到与之匹配的 (x,y)”）

翻译成 RC 就是：

$\forall y(y\in B\to \exists (x,y)\in A)$