Software Systems Atlas

中文

English

中文

English

主题

第 5 卷 / 第 2 章 / 第 1 课

2.1 关系代数：用 relation 组合查询 ​

SQL 让人写“要什么”，关系代数则提供一组可以组合、改写和推理的 operators。查询优化器不会把 SQL 文本逐字执行；它先形成某种 logical plan，再在保持语义的前提下寻找物理执行方案。

本课目标 ​

  • 定义 relation、tuple、attribute 与 schema；
  • 使用 selection、projection、rename、union、difference 和 product；
  • 从 product + selection 推导 join；
  • 解释 set semantics 与 SQL bag/NULL semantics 的差异；
  • 把简单 SQL 表达成关系代数树。

Relation 的最小模型 ​

给定 schema：

text
Items(item_id, type_id, name, value_cents)
Types(type_id, code)

经典关系模型中：

  • relation 是一组具有相同 attributes 的 tuples；
  • tuple 没有内在顺序；
  • relation 也没有内在行顺序；
  • 作为 set，相同 tuple 不重复；
  • attribute 的值来自相应 domain。

SQL table 与这个数学模型并不完全相同。SQL 查询默认使用 bag/multiset semantics，结果可以重复；NULL 引入三值逻辑；某些类型和表达式还有实现定义行为。因此从关系代数推理 SQL 时，要明确采用 classical set algebra，还是含 duplicate/NULL 的扩展语义。

本课先学习经典算子，再标出 SQL 差异。SQL 示例沿用 1.1、1.2 已创建的 SQLite 表；代数中的 Items.type_id 对应实际列 catalog_items.item_type_id，Types.type_id 对应 item_types.item_type_id。

Selection σ ​

selection 按 predicate 选择 tuples，不改变 schema：

text
σ value_cents >= 50000 (Items)

对应 SQL：

sql
SELECT item_id, item_type_id AS type_id, name, value_cents
FROM catalog_items
WHERE value_cents >= 50000;

输入 n 行，selection 输出在 0 到 n 行之间。输出顺序不受保证。

多个 conjunction 可连续选择：

text
σ type_id = 1 AND value_cents >= 50000 (Items)

= σ type_id = 1 (σ value_cents >= 50000 (Items))

在 classical two-valued predicate 下这项等价直接成立。SQL 中 predicate 为 UNKNOWN 的行和 FALSE 一样被 WHERE 丢弃，但涉及 NULL、error-producing expression 或 volatile function 时，实际改写需由 optimizer 遵守目标数据库语义。

Projection π ​

projection 选择 attributes：

text
π type_id (Items)

classical relational algebra 的结果是 set，因此重复的 type_id 会消除。对应 SQL 需要显式 DISTINCT：

sql
SELECT DISTINCT item_type_id
FROM catalog_items;

普通 SQL：

sql
SELECT item_type_id
FROM catalog_items;

保留 duplicate，不能直接当作 classical π。

projection 还可以在扩展代数中计算 expression，例如把 cents 换算成 major unit；但计算、类型转换和 rounding 要在语义中明确。

Rename ρ ​

同一 relation 与自己 join 时，必须区分两个实例：

text
ρ I1 (Items)
ρ I2 (Items)

SQL alias 承担类似角色：

sql
SELECT left_item.name, right_item.name
FROM catalog_items AS left_item
JOIN catalog_items AS right_item
  ON left_item.item_type_id = right_item.item_type_id
 AND left_item.item_id < right_item.item_id;

最后一个 inequality 防止一对 item 以相反顺序出现两次，也排除自己与自己配对。

Union ∪ ​

union 需要 union-compatible inputs：对应 attributes 的数量和 domain/类型兼容。

text
π item_id (ActiveTaskItems)
∪
π item_id (CompletedTaskItems)

SQL UNION 消除 duplicate，更接近 set union；UNION ALL 保留 duplicate，通常也避免 duplicate elimination 的代价。

sql
SELECT qi.item_id
FROM task_items AS qi JOIN tasks AS q ON q.task_id = qi.task_id
WHERE q.status = 'active'
UNION
SELECT qi.item_id
FROM task_items AS qi JOIN tasks AS q ON q.task_id = qi.task_id
WHERE q.status = 'completed';

结果 column name 通常由第一支决定，类型兼容与 coercion 由具体数据库规则决定。

Set difference − ​

text
AllItemIds − ReferencedItemIds

SQL 标准 operator 是 EXCEPT，不同产品支持情况和 duplicate 规则有差异：

sql
SELECT item_id FROM catalog_items
EXCEPT
SELECT item_id FROM task_items;

也可用 NOT EXISTS 表达 anti-join，常能更明确处理 correlation 与 NULL：

sql
SELECT v.item_id
FROM catalog_items AS v
WHERE NOT EXISTS (
    SELECT 1
    FROM task_items AS qi
    WHERE qi.item_id = v.item_id
);

不要机械用 NOT IN (subquery) 替代；subquery 产生 NULL 时，三值逻辑可能让结果全部变为非 TRUE。

Cartesian product × ​

R × S 把 R 的每个 tuple 与 S 的每个 tuple 配对。若基数分别为 m 与 n，输出恰好为 m × n；只有后续筛选才会减少数量。

sql
SELECT *
FROM catalog_items
CROSS JOIN item_types;

product 本身很少是业务最终目标，但它是 theta join 的构造基础。遗漏 join predicate 导致意外 product，会迅速放大 rows 和成本。

Join 是 product + selection ​

theta join：

text
Items ⋈ Items.type_id = Types.type_id Types

= σ Items.type_id = Types.type_id (Items × Types)

SQL：

sql
SELECT
    i.item_id,
    i.name,
    t.code
FROM catalog_items AS i
JOIN item_types AS t
  ON t.item_type_id = i.item_type_id;

logical equivalence 不表示引擎必须真的 materialize product。物理 plan 可以使用 nested-loop、hash join、merge join 或 index lookup，只要保持结果语义。

Natural join 的风险 ​

natural join 根据同名 columns 自动形成 equality predicates。schema 将来增加同名 column 时，查询语义可能悄悄改变，因此生产 SQL 通常显式写 JOIN ... ON ... 或 USING (...)。

Relational expression tree ​

查询：找出 device 中价值至少 50000 cents 的名称。

sql
SELECT i.name
FROM catalog_items AS i
JOIN item_types AS t
  ON t.item_type_id = i.item_type_id
WHERE t.code = 'device'
  AND i.value_cents >= 50000;

一种 logical expression：

text
π i.name
  (
    σ t.code = 'device' AND i.value_cents >= 50000
      (
        ρ i(Items)
        ⋈ i.type_id = t.type_id
        ρ t(Types)
      )
  )

树形理解：

text
projection: i.name
└─ selection: t.code='device' AND i.value_cents>=50000
   └─ inner join: i.type_id=t.type_id
      ├─ Items as i
      └─ Types as t

这棵树说明逻辑关系，没有指定 hash table、index 或 scan 顺序。

Derived operators ​

Intersection ​

text
R ∩ S = R − (R − S)

SQL 可使用 INTERSECT，同样要检查产品支持与 duplicate semantics。

Semijoin ​

left semijoin 只返回左侧匹配 tuples，不附加右侧 attributes：

sql
SELECT i.item_id, i.name
FROM catalog_items AS i
WHERE EXISTS (
    SELECT 1
    FROM task_items AS qi
    WHERE qi.item_id = i.item_id
);

用普通 inner join 再 SELECT 左表 columns 可能产生 duplicate；EXISTS 更直接表达“是否存在”。

Division ​

division 适合“满足所有要求”的查询：找出完成了 required set 中每一种 task 的对象。SQL 通常用 double NOT EXISTS、grouping + count 或 set difference 表达，必须处理 required set 为空时的 vacuous truth。

自检 ​

  1. 为什么 SELECT item_type_id 不是 classical projection？
  2. R × S 在两边各 1000 tuples 时有多少 tuples？
  3. 为什么 inner join 的 logical definition 不要求数据库生成完整 product？
  4. NOT EXISTS 与 NOT IN 在 NULL 存在时可能有什么差别？
  5. 写出“所有被 active task 引用的 item”的 semijoin SQL。

本课小结 ​

关系代数用少量可组合 operators 表达复杂查询。SQL 的 bag、NULL 和类型规则让它不完全等同于 classical algebra；优化和推理时必须先确定语义。下一课讨论哪些改写安全、哪些会因 outer join、duplicate 或 NULL 改变答案。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang