实验 08：结果子数据库——半连接与 Yannakakis 算法

为什么做这个实验

• **要验证的现象**：一个多表连接查询，能不能**不算出庞大的完整连接结果**，只把"每个表里真正参与连接的那些元组"分别挑出来？这就是**结果子数据库（result subdatabase）**。

• **反直觉之处一**：半连接 $R \ltimes S$ 只输出**左关系**的元组，列数不变、不复制。它是"过滤器"而不是"组合器"。它恰好能删掉**悬挂元组**（dangling tuple）——在自己表里存在、但在完整连接结果里一次都不出现的元组。

• **反直觉之处二**：删悬挂元组要**归约两遍**（自底向上 + 自顶向下）才够。只做一遍必然漏删，因为**归约本身会制造新的悬挂元组**：上游被删掉之后，原本在下游有配对的元组可能变成新的悬挂元组。这是本实验最重要的考点。

• **反直觉之处三**：完整连接结果常常比"参与连接的实体"大得多。一个客户有 100 个订单，连接结果里他就重复 100 次，而结果子数据库里他只出现 1 次。省掉的是连接的**乘法效应**。

• **学完能回答**：Yannakakis 算法成立的前提是什么（连接图**无环**）？两种 SQL 改写各自付出了什么代价？为什么根的选择不影响结果却影响性能？

运行前准备

```bash
python -m pip install duckdb pandas faker
```

另外全局需要 `numpy` `matplotlib` `seaborn`。验证：

```python
import duckdb, pandas, faker
print("环境就绪")
```

| 依赖 | 用在哪 | 是否必须 |
|---|---|---|
| `duckdb` | "Rewrite Methods" 两节的 SQL 改写 | 可选（跳过这两节不影响后半部分） |
| `pandas` | 把对象列表转成 DataFrame 灌进 duckdb | 可选 |
| `faker` | 生成示例数据 | 必须（造数据那一步要用） |
| 仓库 `system/` | `JoinGraph`、`Relation`、`Filter`、`SHJ`、`SemiJ`、`Collect` 等算子 | 必须 |

> 如果 `import system` 失败，先运行第一个代码格——它会把仓库根目录（含 `system/` 的那一层）加入 `sys.path`。

How would we execute a query like this?

``` sql
SELECT persons.*
FROM persons
JOIN orders ON name = person_name
JOIN books ON book_title = title
WHERE price < 10
```

这条查询要回答什么？先看它的连接图

把查询的连接结构画成一张无向图：**每个节点是一个关系，每条边是一个连接谓词**。

```text
persons ────── orders ────── books
(0) (1) (2)
name = person_name book_title = title
```

这是一条**链，没有环**，所以该查询是**无环合取查询**（acyclic conjunctive query）——这正是 Yannakakis 算法的适用前提。

如果再加上一个条件 `books.author = persons.name`，图上就会多出一条 `books — persons` 的边，形成一个三角形（有环），此时 Yannakakis 算法不再直接适用。

**另外注意 `WHERE price < 10`**：它是单表谓词，不属于连接图，但在后面会被**下推**到 `books` 上先执行（过滤越早越好）。

Create fake data

造数据：为什么固定随机种子

数据用 `faker` 生成，并且**固定了两处种子**：

```python
random.seed(21) # 控制 orders 里随机挑人、挑书
Faker.seed(15) # 控制 fake.name() / fake.sentence() 等
```

固定种子是为了让**所有人的输出完全一致**，便于对照讲义里的数字，也便于单元测试。

规模：`persons` 3 条、`books` 3 条、`orders` 约 `1.5 × 3` 条（去重用 `if o in orders: continue`）。三个关系都很小，正好可以**手工核对每一步**。

**预期看到什么**：`display(persons, books, orders)` 打印出三组对象。请特别留意 `books` 里哪些书的 `price < 10`——只有这些书能通过过滤，后面整条归约链都由它们决定。

Semi-join

半连接：只过滤，不组合

给定关系 $R$（属性 $A$）和 $S$（属性 $B$）：

| 运算 | 定义 | 输出 |
|---|---|---|
| 连接 $R \bowtie_{A=B} S$ | $\{\,(t, s) \mid t \in R,\ s \in S,\ t[A] = s[B]\,\}$ | 元组**对**，列数是两者之和；一个 $t$ 有 3 个匹配就出现 3 次 |
| 半连接 $R \ltimes_{A=B} S$ | $\{\,t \in R \mid \exists s \in S,\ t[A] = s[B]\,\}$ | 只输出左关系的元组，**列数不变**，每个 $t$ 最多一次 |

```text
R (左) S (右)
+-------+ +-------+
| a | x | | b | y |
+-------+ +-------+
| 1 | p | | 1 | u |
| 2 | q | | 1 | v |
| 3 | r | | 3 | w |
+-------+ +-------+

R ⋈_{a=b} S R ⋉_{a=b} S
| 1 | p | 1 | u | | 1 | p | ← 只出现一次
| 1 | p | 1 | v | | 3 | r |
| 3 | r | 3 | w |
```

`a=2` 这一行在 $S$ 中没有匹配，两种结果里都不出现。

**复杂度**：哈希实现只需对 $S$ 建一次哈希集合 $O(|S|)$，再扫一遍 $R$ 做探测 $O(|R|)$，总计 $O(|R| + |S|)$，且**不产生元组复制**。这是它比连接便宜的根本原因——完整连接还要再乘一个输出因子 $OUT$。

**半连接不是对称的**：$R \ltimes S$ 与 $S \ltimes R$ 一般不同——输出规模由"左边是谁"决定（$|R|$ 是前者的上限，$|S|$ 是后者的上限）。而普通连接 $R \bowtie S$ 与 $S \bowtie R$ 只是列顺序不同，**行数相同**。这也是半连接能用于分布式场景的原因：把小的一方作为右关系传过去做过滤，可以避免传输大表。

**悬挂元组**：某个关系中"在完整连接结果里一次都不出现"的元组。半连接的作用就是**删掉悬挂元组**。

下面这段代码用仓库的算子搭了一条流水线（`Filter` → `SHJ` → `SemiJ` → `Print`），`dump()` 会把它打印成一棵算子树：

```text
Print
SemiJ on `name=person_name`
Relation(persons)
SHJ on `book_title=title`
Relation(orders)
Filter on `price < 10`
Relation(books)
```

**预期看到什么**：`interpret_open()` 打印出**通过了过滤的 persons 元组**。

**但请立刻注意一件事**：这条流水线里的 `SemiJ` 只归约了 `persons` **一个**关系。`orders` 和 `books` 各自还有多少条参与连接？不知道——一次半连接只能回答"左边这个关系里哪些元组留下了"。

这正是本节要引出的核心问题：

> 只关心单个关系时用半连接很方便；要拿到**多个关系**各自的归约结果，就必须上 Yannakakis 的**两遍归约**。

（教学实现里 `Filter` 用 `eval()` 把谓词写成字符串，方便演示。工程代码中不要用 `eval()` 处理不可信输入。）

Since we're only interested in the qualifying tuples of a single relation, we can conveniently use a semi-join to filter the `persons` table based on the join result.
But how can we retrieve just the qualifying tuples from multiple relations *without* computing the full join result?

Extend SQL: `SELECT RESULTDB`

Consider the database tables with sample data from above.

<div style="display: flex; gap: 20px;">

<!-- Customers Table -->
<table>
<caption>persons</caption>
<tr><th>name</th><th>birthday</th></tr>
<tr><td>Alexandra Fitzgerald</td><td>1978-09-02</td></tr>
<tr><td>Mrs. Sherry Maldonado</td><td>2017-01-14</td></tr>
<tr><td>Mrs. Gina Erickson MD</td><td>1984-06-12</td></tr>
</table>

<!-- Orders Table -->
<table>
<caption>orders</caption>
<tr><th>person_name</th><th>book_title</th></tr>
<tr><td>Alexandra Fitzgerald</td><td>Leave sometimes keep firm.</td></tr>
<tr><td>Mrs. Gina Erickson MD</td><td>Leave sometimes keep firm.</td></tr>
<tr><td>Mrs. Sherry Maldonado</td><td>Various deal great finish figure.</td></tr>
<tr><td>Mrs. Sherry Maldonado</td><td>Cultural move pass.</td></tr>
<tr><td>Alexandra Fitzgerald</td><td>Cultural move pass.</td></tr>
</table>

<!-- Books Table -->
<table>
<caption>books</caption>
<tr><th>title</th><th>author</th><th>price</th></tr>
<tr><td>Various deal great finish figure.</td><td>Jennifer Ray</td><td>53.62</td></tr>
<tr><td>Leave sometimes keep firm.</td><td>Joanne Frank</td><td>8.62</td></tr>
<tr><td>Cultural move pass.</td><td>Sarah Smith</td><td>67.63</td></tr>
</table>

</div>

Executing the following query:
``` sql
SELECT RESULTDB *
FROM persons
JOIN orders ON name = person_name
JOIN books ON book_title = title
WHERE price < 10
```
would result in the following reduced relations:

<div style="display: flex; gap: 20px;">

<!-- Customers Table -->
<table>
<caption>persons (reduced)</caption>
<tr><th>name</th><th>birthday</th></tr>
<tr><td>Alexandra Fitzgerald</td><td>1978-09-02</td></tr>
<tr><td>Mrs. Gina Erickson MD</td><td>1984-06-12</td></tr>
</table>

<!-- Orders Table -->
<table>
<caption>orders (reduced)</caption>
<tr><th>person_name</th><th>book_title</th></tr>
<tr><td>Alexandra Fitzgerald</td><td>Leave sometimes keep firm.</td></tr>
<tr><td>Mrs. Sherry Maldonado</td><td>Leave sometimes keep firm.</td></tr>
</table>

<!-- Books Table -->
<table>
<caption>books (reduced)</caption>
<tr><th>title</th><th>author</th><th>price</th></tr>
<tr><td>Leave sometimes keep firm.</td><td>Joanne Frank</td><td>8.62</td></tr>
</table>

</div>

In the following, we are going to discuss two possibilities to compute this result *subdatabase*.

`SELECT RESULTDB *`：换一种问法

传统的查询结果是**一个关系**（一张新表）。结果子数据库换了个问法：

> 对于查询 $Q$ 涉及的每一个关系 $R_i$，$R_i$ 中哪些元组真正参与了 $Q$ 的连接结果？

答案是一组关系 $R_i' \subseteq R_i$，每个只保留参与连接的元组，并且满足

$$R_1' \bowtie R_2' \bowtie \dots \bowtie R_k' \;=\; R_1 \bowtie R_2 \bowtie \dots \bowtie R_k$$

即：**用归约后的关系做最终连接，完整连接结果与用原关系完全一致**；同时每个关系里的悬挂元组都被删掉了。

上面那张对照表就是本笔记本这份数据的答案：persons 从 3 条降到 2 条，orders 从若干条降到 2 条，books 从 3 条降到 1 条。

**为什么要这个东西**：很多分析任务（图分析、机器学习特征抽取、可视化）真正需要的不是连接结果的宽表，而是"这张大图里到底涉及哪些实体和哪些边"。完整连接结果往往比子数据库大得多——**一个客户有 100 个订单，连接结果里这个客户就重复 100 次，而子数据库里只有 1 次**。

**分布式场景下的另一个动机**：先把悬挂元组删掉再跨网络传输，可以显著减少传输量。本笔记本不给出传输量的具体数字，分布式半连接归约的实测在配套课程的"分布式连接"实验中，需自行实测确认。

Rewrite Methods

In this section, we demonstrate two SQL-based rewrite methods that can be used to compute a result subdatabase.

Note: In the [paper](https://arxiv.org/pdf/2312.00638), we discuss two additional rewrite methods that use SQL subqueries to hint the query compiler to use semi-joins internally. However, this "[semi-join optimization](https://dev.mysql.com/doc/refman/8.0/en/semijoins.html)" depends on various factors and may not always be guaranteed.

1. Dynamic `SELECT DISTINCT`

This rewrite method transform a single `SELECT RESULTDB` query into multiple `SELECT DISTINCT` queries, one for each relation that is part of the query.

**动态 `SELECT DISTINCT` 的代价**：$k$ 个关系就要把整套连接算 **$k$ 遍**（本例 $k = 3$），而且除了 `SELECT` 子句之外，这 $k$ 条 SQL 完全一样。总代价约 $k \cdot C$（$C$ 为执行一次完整连接的代价）。

**`DISTINCT` 是必需的，不能去掉**：连接会给左关系的元组做复制，`DISTINCT` 把副本消掉，正好对应半连接"不复制"的性质。去掉之后，某个人有 2 个匹配就会输出 2 行，得到的是**多重集**而不是**集合**，与半连接语义不符。

2. Materialized `SELECT DISTINCT`

This rewrite method first materializes the necessary attributes of the single-table result in a temporary and unmaintained materialized view (MV) once.
Afterward, this MV is queried to obtain the individual result sets, and the MV is dropped again.

**物化 `SELECT DISTINCT` 的取舍**

• **优点**：整套连接只算一次，避免了 $k$ 次重复计算。

• **缺点**：要把一个**可能很大**的连接结果完整物化下来，代价是巨大的磁盘/内存占用与写入开销。

设 $OUT$ = 完整连接结果行数，$C$ = 执行一次完整连接的代价，$k$ = 关系数：

$$\text{动态方法} \approx k \cdot C, \qquad \text{物化方法} \approx C + Write(OUT) + k \cdot Read(OUT)$$

**物化方法更差的条件**（满足其一即可）：

1. $OUT$ 很大，$Write(OUT) + k \cdot Read(OUT)$ 超过 $(k-1) \cdot C$——高扇出连接时必然发生；
2. $OUT$ 放不下内存，必须落盘甚至溢写，I/O 代价急剧上升；
3. $k$ 很小（例如 $k = 2$）：动态方法只多算 1 次，物化却要多付一整轮写入与读出；
4. $C$ 本身很便宜（各关系很小、有索引可用）。

**本笔记本的数据下 $OUT = 2$、$k = 3$**，两种方法都很快，看不出差别。要在真实规模上观察，需自行构造高扇出数据集实测。

一句话概括两者的取舍：**物化方法用"一次性的物化开销"换取"避免 $k$ 次重复计算"。**

Native Algorithm to Compute a Result Subdatabase

In this section, we show how we can leverage semi-joins to implement a native $\text{ResultDB}_{\text{semi-join}}$ algorithm in order to compute a result subdatabase.

For this, we are going to make use of [Yannakakis' algorithm](https://www.researchgate.net/profile/Mihalis-Yannakakis/publication/200034379_Algorithms_for_Acyclic_Database_Schemes/links/5745c2a708ae9f741b430b62/Algorithms-for-Acyclic-Database-Schemes.pdf).
Yannakakis' algorithm provides an efficient way for solving **acyclic** conjunctive queries, i.e., select-project-join queries with an acyclic join graph. The algorithm essentially works in three main steps.

```
1. Choose an arbitrary node in the join graph as root.
2. Perform bottom-up semi-joins from leaves to root. Perform top-down semi-joins from root to leaves.
3. Compute the final join result by joining the reduced relations.
```

Yannakakis 算法：三步，以及"为什么要两遍"

Yannakakis 算法出自 Yannakakis, *Algorithms for Acyclic Database Schemes*, VLDB 1981（pp. 82–94），用于求解**无环**的连接查询。三步：

```text
1. 任选连接图中的一个节点作为根（root）。
2. 自底向上做半连接归约（叶 → 根）；再自顶向下做半连接归约（根 → 叶）。
3. 用归约后的关系做最终连接。
```

以 `orders` 为根，图示如下：

```text
第 1 步：定根
persons ───── orders ───── books
(0) (1)★ (2)
root

第 2a 步：自底向上（叶 → 根）
persons ───── orders ←──── books
(1)⋉(2)
persons ───── orders
(0) ──► (1)⋉(0)

第 2b 步：自顶向下（根 → 叶）
persons ←──── orders
(0)⋉(1)
persons ───── orders ────► books
(2)⋉(1)
```

**为什么必须做两遍？** 两个原因，缺一不可：

1. **每一遍只归约"箭头头部"那一侧的关系**。半连接 $R_a \ltimes R_b$ 只改变 $R_a$。以 `orders` 为根，自底向上只改写 `orders`，`persons` 与 `books` 一行都没动；自顶向下只改写 `persons` 与 `books`，`orders` 一行没动。所以只做一遍，必然有关系的元组从未被检查过。
2. **归约会制造新的悬挂元组**（更本质）。一条 `persons` 元组在自顶向下时用的是**未归约的** `orders`，找到了匹配被保留；但自底向上已经把 `orders` 归约掉了，它的配对可能已经被删——于是它**变成了新的悬挂元组**。这种效应只有在信息从根传回叶（自顶向下）时才能被发现，而自顶向下又必须在自底向上之后执行。

**根的选择**：任选一个节点即可，**正确性不受影响**（无环条件下两遍归约的结果与根无关，本笔记本后面可以换根验证）。但归约的**中间结果大小**与顺序有关，实际系统会估算代价来选根。

**从 Yannakakis 到结果子数据库**：只要前两步，做完两遍归约后**直接返回归约后的各关系**，不做第 3 步的最终连接。

步骤 1：两个原语——`filter()` 与 `semi_join()`

```python
def semi_join(left_relation, right_relation, left_attribute, right_attribute):
ht = set()
for tup in right_relation: # 建阶段：只对右关系的连接键建集合
ht.add(tup[right_attribute])
result = []
for tup in left_relation: # 探阶段：每个左元组最多 append 一次
if tup[left_attribute] in ht:
result.append(tup)
return result
```

两个易错点：

• **`ht` 里存的是连接键的集合，不是整条元组**——这是半连接比连接省空间的直接原因。

• **探阶段对每个 `t` 最多 `append` 一次**。如果写成嵌套循环（对每个匹配都 `append`），那就变成连接了，结果会出现重复元组。

`filter()` 用字符串谓词 + `eval()` 实现（`eval(pred, {}, tup)`，变量即属性名），教学上方便；工程代码不要用 `eval()` 处理不可信输入。

步骤 2：把查询结构记下来——连接图与两个方向的连接属性

```python
join_graph.add_join(0, 1) # persons — orders
join_graph.add_join(1, 2) # orders — books
```

`create_join_graph()` 返回三样东西：

| 变量 | 内容 |
|---|---|
| `join_graph` | 无向连接图：节点 0/1/2 分别是 persons / orders / books |
| `id_to_relation` | `{id: (关系名, 元组列表)}`；注意 `books` 在这里**已经**被 `price < 10` 过滤（谓词下推） |
| `ids_to_join` | `{(左id, 右id): (左属性, 右属性)}` |

**为什么 `ids_to_join` 要把两个方向都写进去**：归约的方向会被反转（自顶向下用 `(子, 父)`），查表时键必须存在。漏写一个方向就会 `KeyError`。

**为什么 `books` 要先过滤**：`price < 10` 是单表谓词，越早执行越好。如果留到归约之后再过滤，前面所有半连接都白做一些元组。

步骤 3：用 BFS 决定半连接的执行顺序

从根出发做**广度优先搜索（BFS）**，每遇到一条未访问的边就记下一个二元组 `(父, 子)`。

**语义**：`(a, b)` 表示"用 $R_b$ 去归约 $R_a$"，即执行 $R_a \ltimes R_b$。

• `reversed(order)` 就是**自底向上**（叶 → 根）；

• 反过来用（把 `(父, 子)` 换成 `(子, 父)`）就是**自顶向下**（根 → 叶）。

**预期看到什么**（本笔记本已打印）：

```text
以 persons 为根: [(0, 1), (1, 2)]
以 orders 为根: [(1, 0), (1, 2)]
以 books 为根: [(2, 1), (1, 0)]
```

三个顺序不同，但**归约完的最终结果相同**。

步骤 4：两遍归约，以及"只做一遍会漏掉什么"

`reduction()` 里的两个循环：

```python
for left_rel_id, right_rel_id in reversed(semi_join_order): # 自底向上
...
for (right_rel_id, left_rel_id) in semi_join_order: # 自顶向下（方向反转）
...
```

注意第二个循环的写法：它把 `semi_join_order` 里的 `(父, 子)` **按反序解包**成 `(right, left)`，于是被归约的一方变成了子（叶）那一侧。**写错方向是这里最常见的 bug**：结果是某些关系一条都没变小，或者 `KeyError`。

**预期看到什么**（本笔记本的 faker 数据，3 人 / 3 书）：归约后 persons 2 条、orders 2 条、books 1 条（`books` 里只剩 `price < 10` 且被订单引用的那一本）。

**只做一遍的对照**（配套实验指导书手写数据集上的实测，原始关系：persons 4 / orders 4 / books 3，books 已按 `price < 10` 过滤）：

| 遍数 | persons 剩余 | orders 剩余 | books 剩余 | 说明 |
|---|---:|---:|---:|---|
| 0 遍（原始） | 4 | 4 | 3 | books 已过滤 |
| 只自底向上 | **4** | **3** | **3** | 只有 `orders` 变小；`Dave`、`Bob`、`CG101` 全都还在 |
| 只自顶向下 | **3** | **4** | **2** | `persons`、`books` 变小，但 `Bob` 还在（用的是未归约的 orders）；`orders` 没被动过 |
| 两遍（完整） | **2** | **3** | **2** | 三个关系全部归约到位 |

**一句话总结**：每一遍只归约箭头头部那一侧的关系。两遍合起来才能覆盖所有关系，并揪出"因别人被删而新产生的悬挂元组"。

> 本笔记本用的是 faker 生成的数据，具体条数与上表不同，但"只做一遍必然漏删"的结论完全一致。

步骤 5：完整的 Yannakakis——加上第 3 步的最终连接

`yannakakis()` 比 `resultDB()` 多了第 3 步：用归约后的三个关系构造查询计划并执行，得到**传统意义上的完整连接结果**。

**预期看到什么**：本笔记本的数据下得到 **2 行**（即两个"人—订单—书"的完整配对）。

这 2 行就是"标准答案"。可以拿它做**差异测试（differential testing）**：

1. 直接用原关系做完整连接；
2. 先做两遍半连接归约，再连接；

两条路径的结果必须完全一致。这正是"结果子数据库"的定义所保证的：$R_1' \bowtie \dots \bowtie R_k' = R_1 \bowtie \dots \bowtie R_k$。

注意这里 `root` 是用 `random.seed(42)` + `random.choice()` 随机选的——**故意的**：它演示"任选根都不影响正确性"。

步骤 6：`resultDB()`——只取前两步

```python
def resultDB(join_graph, id_to_relation, ids_to_join):
root = random.choice(list(id_to_relation.keys())) # 1. 任选根
semi_join_order = compute_semi_join_order(join_graph, root)
semi_join_reduction(semi_join_order, id_to_relation, ids_to_join) # 2. 两遍归约
return id_to_relation # 3. 不做最终连接，直接返回
```

**预期看到什么**：一个字典，三个关系各自只剩"参与连接"的元组——这就是**结果子数据库**。把它与步骤 5 的完整连接结果对照：完整连接是 2 行宽表，子数据库是"2 个人 + 2 条订单 + 1 本书"。

**这就是本实验的落点**：同样的查询语义，一种表示会放大（每个客户的订单数倍），另一种不会。

Unit Tests

单元测试：这份实现在验什么

最后一格用 `unittest` 跑了 4 个测试，分别覆盖：

| 测试 | 验证什么 |
|---|---|
| `test_filter` | 字符串谓词过滤是否正确 |
| `test_semi_join` | 半连接是否**只保留左关系、不复制**（`books ⋉ orders` 应返回在 orders 中出现过的 3 本书） |
| `test_compute_semi_join_order` | 星型连接图（4 个节点、0 为中心）下 BFS 顺序是否正确 |
| `test_semi_join_reduction` | 两遍归约后的结果是否与预期一致 |

**为什么要写这些测试**：半连接的实现里最容易犯的错是"探阶段多 append 一次"（变成连接）和"归约方向写反"。这两个 bug 都不会报错，只会**静默地给出偏大的结果**——只有对拍才能发现。

**建议自己加一个**：换不同的根跑 `resultDB()`，断言结果相同（无环条件下必须成立）。

思考题与详解

> 建议先自己写一遍答案，再展开对照。

**1. 半连接 $R \ltimes S$ 与"先做 $R \bowtie S$、再对 $R$ 的列做投影去重"，结果是否总是相同？给出理由或反例。**

<details><summary>答案要点</summary>

**相同**（在等值连接条件下）。

• 半连接：$R \ltimes_{A=B} S = \{\,t \in R \mid \exists s \in S,\ t[A] = s[B]\,\}$

• 连接后投影去重：$\pi_{R\text{-cols}}(R \bowtie_{A=B} S) = \{\,t \mid \exists s \in S,\ t[A] = s[B]\,\}$

两者都收集"在 $S$ 中至少有一个匹配的 $R$ 元组"。连接后投影去重之所以丢掉了重复次数，正是因为它做了去重。所以二者是同一个集合。

反例只可能出现在**非等值连接**或**投影列包含 $S$ 的列**时：此时右边的结果列数不同，集合自然也不同。

这也正是"动态 `SELECT DISTINCT persons.*`"能等价于 `persons ⋉ (orders ⋈ books)` 的原因。

</details>

**2. 若某人有 100 个订单且都满足条件，完整连接结果会有多少行？结果子数据库里的 `persons` 部分有多少行？这说明结果子数据库省掉了什么？**

<details><summary>答案要点</summary>

• 完整连接结果中这个人出现 **100 行**（每个订单一行）。

• 结果子数据库里 `persons` 部分**只有 1 行**（就是这个人这一条）。

**省掉的是连接的乘法效应**：完整连接结果的大小约等于各"实体对"匹配数的总和，在**高扇出（fan-out）**的实体上会被放大成百上千倍；结果子数据库只保存每个实体一次。

本笔记本的数据下：完整连接 2 行，而结果子数据库是 2 个人 + 2 条订单 + 1 本书——`persons` 部分没有重复。

</details>

**3. 为什么 Yannakakis 算法要做两遍半连接归约？举一个"只做自底向上会漏删"的具体元组。**

<details><summary>答案要点</summary>

两个原因：

**（一）每一遍只归约箭头头部那一侧。** 半连接 $R_a \ltimes R_b$ 只改变 $R_a$。以 `orders` 为根时顺序是 `[(1,0), (1,2)]`：

• 自底向上用 `reversed`，按 `(1,2)`、`(1,0)` 执行，被改写的**只有 `orders`**；

• 自顶向下按反方向 `(0,1)`、`(2,1)` 执行，被改写的是 `persons` 与 `books`。

所以只做一遍，必然有关系的元组从未被检查过——配套指导书实测：只自底向上时 persons 仍为 4 条（`Dave`、`Bob` 都还在）。

**（二）归约会制造新的悬挂元组**（更本质）。以 `persons` 里的 `Bob` 为例：

• 自顶向下这一遍里，`persons ⋉ orders` 用的是**未归约的** orders（4 条，含 `(Bob, OS101)`），`Bob` 找到了匹配被保留；

• 但自底向上已经把 orders 归约到 3 条，`(Bob, OS101)` 被删掉了（`OS101` 不满足 `price<10`）；

• 于是 `Bob` 在归约后的 orders' 里已没有任何配对——它**变成了新的悬挂元组**。

这种"因为别人被删而导致自己变成悬挂"的效应，只有信息从根传回叶时才能被发现；而自顶向下又必须在自底向上之后执行，否则它用的还是旧的 orders。

</details>

**4. 半连接 $R \ltimes_{A=B} S$ 的时间复杂度是多少？哈希实现的空间复杂度是多少？与完整连接相比差别在哪？**

<details><summary>答案要点</summary>

哈希实现的半连接：

• 建阶段：扫一遍 $S$，把 $S[B]$ 的取值放进哈希集合，$O(|S|)$；

• 探阶段：扫一遍 $R$，每个元组查一次集合，$O(|R|)$；

• **时间复杂度 $O(|R| + |S|)$**；

• **空间复杂度**等于 $S$ 在 $B$ 上不同取值的个数，最坏 $O(|S|)$。

完整哈希连接：

• 时间同样是 $O(|R| + |S|)$，但**要再乘一个输出因子**：每个匹配的 $(t,s)$ 都要物化一次，即 $O(|R| + |S| + OUT)$；

• 空间：哈希表存的是 $S$ 的**整条元组**，不只是连接键，常数比只存键大得多。

**核心差别**：半连接的输出不超过 $|R|$，且不复制；连接的输出可能远大于 $|R| + |S|$。这就是"半连接便宜"的全部理由。

</details>

**5. `SELECT DISTINCT` 里的 `DISTINCT` 能不能去掉？去掉之后会发生什么？**

<details><summary>答案要点</summary>

**不能去掉。**

`SELECT persons.* FROM persons JOIN orders ... JOIN books ...` 会为 `persons` 的每个匹配输出一行。某个人有 2 个匹配，就会输出 2 行同名的 persons 元组。

结果子数据库的定义要求每个关系只保留"参与连接的元组"，是一个**集合（set）**，不是**多重集（multiset）**。不加 `DISTINCT` 得到的是多重集，与半连接语义不符。

用 duckdb 可以一行验证（需自行实测确认）：

```python
print(con.execute("SELECT persons.* " + body).fetchall()) # 同一人可能出现多次
print(con.execute("SELECT DISTINCT persons.* " + body).fetchall()) # 每人一次
```

</details>

**6. 物化 `SELECT DISTINCT` 在什么情况下比动态 `SELECT DISTINCT` 更差？给出判断条件。**

<details><summary>答案要点</summary>

设 $OUT$ = 完整连接结果的行数，$C$ = 执行一次完整连接的代价，$k$ = 参与连接的关系数。

• 动态方法总代价 $\approx k \cdot C$；

• 物化方法总代价 $\approx C + Write(OUT) + k \cdot Read(OUT)$。

**物化更差的条件**（满足其一即可）：

1. $OUT$ 很大，$Write(OUT) + k \cdot Read(OUT) > (k-1) \cdot C$。高扇出连接时必然发生。
2. 磁盘/内存放不下 $OUT$，必须落盘甚至溢写，I/O 代价急剧上升。
3. $k$ 很小（例如 $k = 2$）：动态方法只多算 1 次连接，而物化要多付一整轮写入与读出。
4. $C$ 本身很便宜（各关系都很小、有索引可用）：重复计算本来就不高。

本笔记本的数据下 $OUT = 2$、$k = 3$，两种方法都很快，看不出差别。要在真实规模上观察需自行构造高扇出数据集实测。

</details>

**7. Yannakakis 算法要求连接图无环。如果连接图有环（例如三角形），两遍归约还能保证删掉所有悬挂元组吗？举例说明。**

<details><summary>答案要点</summary>

**不能保证。**

两遍归约的正确性依赖连接图的**树结构**：树上任意两节点之间路径唯一，自底向上把叶的信息汇聚到根，自顶向下再从根发散回叶，恰好覆盖每条边两个方向各一次，这就足以把"某条元组在整棵树上还有没有完整配对"这个全局条件传导到每个节点。

有环时，一条元组是否悬挂取决于环上**所有边**的联合约束；沿着一棵生成树做两遍传递只能保证"沿树边都有邻居"，无法保证"跨树边的那条边也有邻居"。

**具体例子**（三个关系构成三角形）：

```python
A = [{"x": 1, "y": 1}, {"x": 2, "y": 2}]
B = [{"y": 1, "z": 1}, {"y": 2, "z": 2}]
C = [{"z": 1, "x": 1}, {"z": 2, "x": 1}] # C 中没有 (z=2, x=2)
```

完整连接只有 1 行（`x=1, y=1, z=1`），所以 `A` 中的 `{"x": 2, "y": 2}` 是悬挂元组。但以 `A` 为根对生成树 `A—B—C` 做两遍归约：

• 自底向上：`C ⋉ B` 保留全部（两条都在 `B` 里有 `z` 匹配）；`B ⋉ A` 保留全部；

• 自顶向下：`A ⋉ B'` 保留全部；`B ⋉ C'` 保留全部。

`A` 的两条都留下了。原因是它是否悬挂取决于 `C` 里有没有 `(z=2, x=2)`，而这条约束对应的边 `C—A` 在生成树里被丢掉了。

有环查询需要先用**树宽**相关的算法（GYO 归约、连接树构造）分解成无环结构，代价通常随环的数量指数增长。

</details>

**8. 本实验中"选根"不影响最终结果，那实际系统为什么还要挑根？挑根影响的是什么？**

<details><summary>答案要点</summary>

结果的**内容**与根无关（无环条件下的理论保证），但归约的**中间结果大小**和**执行顺序**与根有关。**挑根影响的是性能**：

• 不同的根决定不同的 BFS 顺序，从而决定每个半连接"什么时候执行、用哪个已归约的关系去归约"；

• 若先归约掉一个很大的关系，后续所有半连接的输入都会变小，总代价显著下降；

• 反之，若先执行一个选择性很差的半连接（几乎不删元组），就白白付了一次扫描代价。

**实际系统的做法**：枚举每个候选根，用基数估计估算每种顺序下各中间关系的大小，选代价最小的。这是查询优化器的标准职责之一。

可以在本笔记本里把每步归约后的行数打印出来，换不同的根观察中间大小确实不同（需自行实测确认）。

</details>