Skip to content

4 、关系代数

一、基础🧀

flowchart TB
    A["SQL 客户端"] --> B["查询解析与优化"]
    B --> C["关系算子"]
    C --> D["文件与索引管理"]
    D --> E["缓冲区管理"]
    E --> F["磁盘空间管理"]
    F --> G[("数据库")]

    classDef orange fill:#fff2e6,stroke:#e67e22,stroke-width:1.5px,color:#222;
    classDef blue fill:#eef0ff,stroke:#1f3bd8,stroke-width:1.5px,color:#222;
    classDef green fill:#e8ffe8,stroke:#139b28,stroke-width:1.5px,color:#222;
    classDef red fill:#ffe8e8,stroke:#b00000,stroke-width:1.5px,color:#222;
    classDef gray fill:#f5f5f5,stroke:#999,stroke-width:1.5px,color:#222;

    class A orange;
    class B,C blue;
    class D,E green;
    class F red;
    class G gray;

  • SQL 是声明式语言，不用管数据库怎么执行。

  • 关系代数是操作式语言，它把查询拆成一系列算子：

    • 选择

    • 投影

    • 连接

    • 并

    • 差

    • 笛卡尔积

    • 重命名

数据库优化器会把 SQL 翻译成关系代数，再进一步变成物理执行计划。

flowchart LR
    SQL --> 关系代数

二、算子🧀

1、一元算子🧀

一元算子只作用在一个关系上。

（1）选择 \(\sigma\)🧀

选择对应 SQL 里的 WHERE，挑出满足条件的行。

  • 形式：\(\sigma_{condition}(R)\)
  • \(\sigma_{rating>8}(Sailors)\) → 从 Sailors 中选出 rating 大于 8 的行。
  • 特点：
  • 只减少行
  • 不改变列
  • 输出模式和输入模式相同

（2）投影 \(\pi\)🧀

投影对应 SQL 里的 SELECT 列表，作用是保留指定列，丢掉其他列。

  • 形式：\(\pi_{columns}(R)\)
  • \(\pi_{sname, age}(Sailors)\) → 只保留水手名字和年龄两列。

  • 特点：

    • 只减少列
    • 在集合语义下，可能会去重，例如原来有两个人 age 都是 20，投影 age 后只剩一个 20。

（3）重命名 \(\rho\)🧀

重命名用于修改关系名或属性名。

  • 形式：\(\rho(R') (R)\) ,或者重命名列：\(\rho_{Temp(a,b,c)}(R)\)

  • 它常用于：

    • 自连接

    • 避免列名冲突

    • 给中间结果命名

2、二元算子🧀

二元算子作用在两个关系上。

（1）并 \(\cup\)🧀

并对应 SQL 里的 UNION。

  • 形式：\(R \cup S\)

  • 含义：返回在 \(R\) 中或在 \(S\) 中的元组。

  • 要求：两个关系必须兼容。

    • 列数相同

    • 对应列的类型相同

（2）差 \(-\)🧀

差对应 SQL 里的 EXCEPT。

  • 形式：\(R - S\)

  • 含义：返回在 \(R\) 中但不在 \(S\) 中的元组；同样要求两个关系兼容。

（3）笛卡尔积 \(\times\)🧀

  • 形式：\(R \times S\)

  • 含义：把 \(R\) 的每一行和 \(S\) 的每一行配对。

    • 如果：\(|R| = m\) ，\(|S| = n\)

    • 那么：\(|R \times S| = mn\)

  • 笛卡尔积本身通常会产生很多无意义组合，所以经常和选择一起使用，形成连接。

3、复合算子🧀

复合算子可以由基本算子组合出来，但因为太常用，所以单独命名。

（1）交 \(\cap\)🧀

  • 形式：\(R \cap S\)

  • 含义：返回同时在 \(R\) 和 \(S\) 中的元组。

    • 交可以用差表示：\(R \cap S = R - (R - S)\)

（2）条件连接 \(\bowtie_{\theta}\)🧀

  • 形式：\(R \bowtie_{\theta} S\)

  • 含义：先做笛卡尔积，再选出满足条件的组合。

  • 等价于：\(\sigma_{\theta}(R \times S)\)

    • \(Sailors \bowtie_{Sailors.sid=Reserves.sid} Reserves\) ，把水手和预约记录按照 sid 匹配起来。

（3）自然连接 \(\bowtie\)🧀

  • 形式：\(R \bowtie S\)

  • 含义：自动按照两个关系中同名属性做相等连接，并且结果中同名列只保留一份。

例如两个表都有 sid，自然连接默认用 sid 匹配。

注意：自然连接虽然写起来方便，但如果同名列不是你想连接的列，可能出错。

找 rating 大于 \(8\) 的水手名字

关系代数 \(\pi_{sname}(\sigma_{rating>8}(Sailors))\)

执行顺序是：

  1. 先用 \(\sigma\) 选出 rating 大于 8 的行
  2. 再用 \(\pi\) 保留 sname 列

不能反过来，因为如果先投影 sname，就没有 rating 列了，后面无法判断 rating 是否大于 8。

三、计算方法🧀

对于 SQL：

1
2
3
SELECT A
FROM R, S
WHERE condition

可以转成 \(\pi_A(\sigma_{condition}(R \times S))\)

如果 WHERE 里是连接条件，也可以写成连接 \(\pi_A(R \bowtie_{condition} S)\)

查询预约了 100 号船且 rating 大于 5 的水手名字

1
2
3
4
5
SELECT S.name
FROM Reserves R, Sailors S
WHERE R.sid = S.sid
AND R.bid = 100
AND S.rating > 5

关系代数 \(\pi_{S.name}(\sigma_{R.bid=100 \land S.rating>5}(Reserves \bowtie_{R.sid=S.sid} Sailors))\)

也可以把选择提前 \(\pi_{S.name}((\sigma_{R.bid=100}(Reserves)) \bowtie_{R.sid=S.sid} (\sigma_{S.rating>5}(Sailors)))\)

第二种通常更好，因为先过滤再连接，中间结果更小。

1、查询优化🧀

关系代数很重要，因为优化器可以利用等价规则改写表达式。

\(\pi_{S.name}(\sigma_{R.bid=100 \land S.rating>5}(Reserves \bowtie Sailors))\)

可以优化为 \(\pi_{S.name}((\sigma_{R.bid=100}(Reserves)) \bowtie (\sigma_{S.rating>5}(Sailors)))\)

这个优化叫选择下推，核心思想是越早过滤无用数据，后面的操作越便宜

2、常见等价规则🧀

规则 等价式 含义
选择拆分 \(\sigma_{c_1 \land c_2}(R) \equiv \sigma_{c_1}(\sigma_{c_2}(R))\) 多个选择条件可以拆开，分别执行
选择交换 \(\sigma_{c_1}(\sigma_{c_2}(R)) \equiv \sigma_{c_2}(\sigma_{c_1}(R))\) 选择条件的执行顺序可以交换
投影级联 \(\pi_{A}(\pi_{A,B}(R)) \equiv \pi_A(R)\) 连续投影可以合并，最终只保留最后需要的列
笛卡尔积交换 \(R \times S \equiv S \times R\) 两个关系做笛卡尔积时，左右顺序可以交换
笛卡尔积结合 \(R \times (S \times T) \equiv (R \times S) \times T\) 多个关系做笛卡尔积时，分组方式可以改变

四、迭代器🧀

1
2
3
4
5
SELECT  S.name
FROM Reserves R,  Sailors S
WHERE R.sid = S.sid
AND R.bid = 100
AND S.rating > 5

逻辑上可以写成 \(\pi_{S.name}(\sigma_{bid=100 \land rating>5}(Reserves \bowtie Sailors))\)

但物理执行时优化器会选择具体算法，比如：对 Reserves/Sailors 做扫描或索引扫描；使用某种连接算法；使用投影算子输出目标列

dataflow.svg