实验 08：结果子数据库（Result Subdatabase）

> 一个多表连接查询，能不能不算出庞大的完整连接结果，只把"每个表里真正参与连接的那些元组"分别挑出来？

一、实验目标

完成本实验后，你应该能够：

1. 说出**半连接**（semi-join）的定义，并区分它与普通连接（join）在输出上的差别。
2. 解释什么是**悬挂元组**（dangling tuple），并说明半连接为什么能删掉它。
3. 读懂连接图（join graph），判断一个查询的连接图是否**无环**（acyclic）。
4. 复述 Yannakakis 算法的三步，并能手工在一份小数据上执行它。
5. 用 SQL 写出两种改写方法（动态 `SELECT DISTINCT`、物化 `SELECT DISTINCT`），并说清各自的代价。
6. 用纯 Python 实现半连接归约，得到**结果子数据库**（每个关系只保留参与连接的元组），并与完整连接结果对拍验证。

二、预备知识

2.1 关系与元组

本实验用字典表示元组（tuple），用列表表示关系（relation）。

```python
persons = [
{"name": "Alice", "birthday": "1990-01-01"},
{"name": "Bob", "birthday": "1985-05-05"},
]
```

字典的键是属性名，值是该属性上的取值。一列（attribute）就是字典的一个键。

2.2 连接（join）与半连接（semi-join）

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

**连接**（此处指等值连接）：

```
R ⋈_{A=B} S = { (t, s) | t ∈ R, s ∈ S, t[A] = s[B] }
```

输出的是元组**对**，列数是两者之和。若一个 `t` 在 `S` 中有 3 个匹配，输出里就有 3 行。

**半连接**（左半连接）：

```
R ⋉_{A=B} S = { t ∈ R | ∃ s ∈ S, t[A] = s[B] }
```

只输出左关系 `R` 的元组，**列数不变**，且每个 `t` 最多出现一次（不复制）。

```
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
+-------+ +-------+
| a | x | b | y | | a | x |
+-------+ +-------+
| 1 | p | 1 | u | | 1 | p | ← 只出现一次
| 1 | p | 1 | v | | 3 | r |
| 3 | r | 3 | w | +-------+
+-------+
```

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

2.3 悬挂元组（dangling tuple）

在多表连接中，某个关系 `R` 里的一条元组 `t`，如果在完整连接结果里**一次都不出现**，就称 `t` 是 `R` 的一条悬挂元组。

它之所以"悬挂"，是因为它在自己的表里存在，但在连接链的下游找不到配对，白白占用了计算。

半连接的作用就是**删除悬挂元组**：`R ⋉ S` 恰好保留 `R` 中所有能在 `S` 里找到匹配的元组。

2.4 连接图（join graph）

把查询的连接结构画成一张无向图：

• 每个**节点**是一个参与连接的关系；

• 每条**边**是一个连接谓词（等值条件）。

本实验的示例查询：

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

连接图：

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

这是一条链，**没有环**，所以该查询是无环合取查询（acyclic conjunctive query）。

若再加上 `books.author = persons.name`，图上会多出一条 `books — persons` 的边，形成三角形，即出现环：

```
persons ────── orders
│ │
└──── books ───┘ ← 有环，Yannakakis 算法不再直接适用
```

2.5 结果子数据库（result subdatabase）

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

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

答案是一组关系 `Rᵢ' ⊆ Rᵢ`，每个 `Rᵢ'` 只保留参与连接的元组。它满足：

```
R₁' ⋈ R₂' ⋈ ... ⋈ Rₖ' == R₁ ⋈ R₂ ⋈ ... ⋈ Rₖ
```

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

本实验用扩展 SQL 语法表达这个语义：

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

`SELECT RESULTDB *` 表示"不要返回连接结果，返回参与连接的那部分数据"。

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

2.6 分布式场景下的动机

在分布式/并行数据库中，半连接还有一个经典用途：先把悬挂元组删掉，再跨网络传输数据，可以显著减少传输量。

> 本实验不给出具体的传输量数字。分布式半连接归约的实测数据在配套的实验 15（分布式连接）中测量，可自行实测确认。

三、实验原理

3.1 方法一：动态 SELECT DISTINCT

把一条 `SELECT RESULTDB` 查询改写成 **k 条**普通 SQL（k 是参与连接的关系数），第 i 条只把 `SELECT` 子句换成"第 i 个关系的全部列 + `DISTINCT`"：

```sql
SELECT DISTINCT persons.* FROM persons JOIN orders ON ... JOIN books ON ... WHERE price < 10;
SELECT DISTINCT orders.* FROM persons JOIN orders ON ... JOIN books ON ... WHERE price < 10;
SELECT DISTINCT books.* FROM persons JOIN orders ON ... JOIN books ON ... WHERE price < 10;
```

`DISTINCT` 是必需的：连接会给左关系的元组做复制，`DISTINCT` 把副本消掉，正好对应半连接"不复制"的性质。

**缺点**：本质上同一个查询被**重复执行了 k 次**，除了 `SELECT` 子句之外完全一样。k 个关系就要把整套连接算 k 遍。

3.2 方法二：物化 SELECT DISTINCT

先把完整连接结果**物化**（materialize）成一张临时表，再从这张临时表上对各个关系做 `SELECT DISTINCT`：

```sql
CREATE TABLE mv AS
SELECT * FROM persons JOIN orders ON ... JOIN books ON ... WHERE price < 10;

SELECT DISTINCT name, birthday FROM mv; -- persons 部分
SELECT DISTINCT person_name, book_title FROM mv; -- orders 部分
SELECT DISTINCT title, author, price FROM mv; -- books 部分

DROP TABLE mv;
```

**优点**：避免了重复计算，整套连接只算一次。
**缺点**：要把一个**可能很大**的连接结果完整物化下来，代价可能是巨大的磁盘/内存占用与写入开销。

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

3.3 方法三：原生算法——Yannakakis 算法

前两种方法是"拿 SQL 凑出来的"，它们都要先算出完整连接结果。原生算法则完全不碰完整连接结果。

Yannakakis 算法出自 Yannakakis, *Algorithms for Acyclic Database Schemes*, VLDB 1981（pp. 82–94）。它用于求解**无环**的连接查询（select-project-join、acyclic conjunctive queries），核心是三步：

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

图示（以 `orders` 为根，本实验的三表链）：

```
第 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)

第 3 步：最终连接
persons' ⋈ orders' ⋈ books'
```

为什么必须做**两遍**？

• 自底向上（叶→根）：把"下游有没有匹配"的信息传到上游，删掉叶一侧的悬挂元组。

• 自顶向下（根→叶）：把"上游还剩下什么"的信息传回下游。这一步是必需的，因为上游归约后，原本在下游有匹配的元组可能因为上游的配对全部被删而变成新的悬挂元组。

只做一遍是不够的——这是本实验最重要的考点之一。

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

3.4 从 Yannakakis 到结果子数据库

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

```
ResultDB_semi-join:
1. 选根
2. 自底向上半连接归约 + 自顶向下半连接归约
3. 返回 { R₁', R₂', ..., Rₖ' } ← 不做最终连接
```

这正是本实验步骤 7 要实现的 `resultDB()` 函数。

3.5 参考图件

| 图件 | 内容 |
| --- | --- |
| `../figures/fig_push_pipeline.png` | 基于 push 模型的算子流水线，本实验中 `SemiJ`、`SHJ` 等算子按此方式组合 |

四、实验环境与准备

4.1 环境要求

| 项目 | 要求 |
| --- | --- |
| Python | 3.10 及以上 |
| 核心步骤（5–9） | 只用标准库，`collections`、`queue` |
| 可选步骤（3–4，SQL 改写） | `duckdb`（`pip install duckdb`） |
| 参考实现 | `notebooks/Result-DB.ipynb` |
| 参考模块 | `system/query_processing/operators.py`（`Relation`、`Filter`、`SHJ`、`SemiJ`、`Print`、`Collect`）、`system/query_optimization/join_graph.py`（`JoinGraph`） |

```bash
pip install duckdb
```

4.2 数据准备

为了让所有人的输出完全一致，本实验**手写一份固定的小数据集**，不使用随机生成器。三个关系如下：

**persons**

| name | birthday |
| --- | --- |
| Alice | 1990-01-01 |
| Bob | 1985-05-05 |
| Carol | 2000-09-09 |
| Dave | 1978-03-20 |

**books**

| title | author | price |
| --- | --- | --- |
| DB101 | Alice | 8.50 |
| OS101 | Bob | 55.00 |
| AI101 | Alice | 9.90 |
| CG101 | Carol | 7.20 |

**orders**

| person_name | book_title |
| --- | --- |
| Alice | DB101 |
| Bob | OS101 |
| Carol | AI101 |
| Alice | AI101 |

这份数据故意造了四类悬挂元组，后面逐一验证：

| 悬挂元组 | 属于哪个关系 | 为什么悬挂 |
| --- | --- | --- |
| Dave | persons | 没有任何订单 |
| Bob | persons | 只有一条订单，但订的是 `OS101`（价格 55.00 ≥ 10），被过滤掉了 |
| CG101 | books | 价格 7.20 < 10，通过了过滤，但没有任何订单引用它 |
| (Bob, OS101) | orders | 引用的书 `OS101` 被 `price < 10` 过滤掉了 |

五、实验步骤

步骤 1：定义数据

```python
persons = [
{"name": "Alice", "birthday": "1990-01-01"},
{"name": "Bob", "birthday": "1985-05-05"},
{"name": "Carol", "birthday": "2000-09-09"},
{"name": "Dave", "birthday": "1978-03-20"},
]

books = [
{"title": "DB101", "author": "Alice", "price": 8.50},
{"title": "OS101", "author": "Bob", "price": 55.00},
{"title": "AI101", "author": "Alice", "price": 9.90},
{"title": "CG101", "author": "Carol", "price": 7.20},
]

orders = [
{"person_name": "Alice", "book_title": "DB101"},
{"person_name": "Bob", "book_title": "OS101"},
{"person_name": "Carol", "book_title": "AI101"},
{"person_name": "Alice", "book_title": "AI101"},
]
```

步骤 2：先算出"标准答案"——完整连接结果

用最朴素的两重循环实现哈希连接，作为后续所有方法的对照基准。

```python
def hash_join(left, right, left_attr, right_attr):
"""等值哈希连接，输出左右元组的合并（后者的同名键覆盖前者）。"""
ht = {}
for t in right:
ht.setdefault(t[right_attr], []).append(t)
out = []
for t in left:
for s in ht.get(t[left_attr], []):
out.append(t | s)
return out

def full_join_result():
b = [t for t in books if t["price"] < 10] # 先过滤
ob = hash_join(orders, b, "book_title", "title") # orders ⋈ books
return hash_join(persons, ob, "name", "person_name") # persons ⋈ (…)

for row in full_join_result():
print(row)
```

预期输出（3 行）：

```
{'name': 'Alice', 'birthday': '1990-01-01', 'person_name': 'Alice', 'book_title': 'DB101', 'title': 'DB101', 'author': 'Alice', 'price': 8.5}
{'name': 'Carol', 'birthday': '2000-09-09', 'person_name': 'Carol', 'book_title': 'AI101', 'title': 'AI101', 'author': 'Alice', 'price': 9.9}
{'name': 'Alice', 'birthday': '1990-01-01', 'person_name': 'Alice', 'book_title': 'AI101', 'title': 'AI101', 'author': 'Alice', 'price': 9.9}
```

请数一下：完整连接结果有 **3 行**，其中 `Alice` 出现了 2 次。而"参与连接的 persons"只有 **2 个不同的人**。这个差距就是结果子数据库想省掉的东西。

步骤 3（可选）：动态 SELECT DISTINCT

需要 `duckdb`。

```python
import duckdb

con = duckdb.connect(database=":memory:")
con.execute("CREATE TABLE persons(name VARCHAR, birthday VARCHAR)")
con.execute("CREATE TABLE books(title VARCHAR, author VARCHAR, price DOUBLE)")
con.execute("CREATE TABLE orders(person_name VARCHAR, book_title VARCHAR)")
con.executemany("INSERT INTO persons VALUES (?, ?)",
[(p["name"], p["birthday"]) for p in persons])
con.executemany("INSERT INTO books VALUES (?, ?, ?)",
[(b["title"], b["author"], b["price"]) for b in books])
con.executemany("INSERT INTO orders VALUES (?, ?)",
[(o["person_name"], o["book_title"]) for o in orders])

body = """
FROM persons
JOIN orders ON name = person_name
JOIN books ON book_title = title
WHERE price < 10
"""

for sel in ["persons.*", "orders.*", "books.*"]:
print(f"--- SELECT DISTINCT {sel}")
print(con.execute(f"SELECT DISTINCT {sel} {body}").fetchall())
```

观察：三条 SQL 跑出来的行数分别是 2、3、2，正好对应后面步骤 7 的结果子数据库。但为此**整套连接被执行了 3 次**。

步骤 4（可选）：物化 SELECT DISTINCT

```python
con.execute(f"CREATE TABLE mv AS SELECT * {body}")

print("persons 部分:", con.execute(
"SELECT DISTINCT name, birthday FROM mv").fetchall())
print("orders 部分:", con.execute(
"SELECT DISTINCT person_name, book_title FROM mv").fetchall())
print("books 部分:", con.execute(
"SELECT DISTINCT title, author, price FROM mv").fetchall())

con.execute("DROP TABLE mv")
```

观察：结果与步骤 3 完全一致，但整套连接只执行了 1 次，代价是要把 `SELECT *` 的完整连接结果写进 `mv`。本例中 `mv` 只有 3 行；真实场景下它可能高达数十亿行。

步骤 5：两个原语——过滤与半连接

```python
def filter_rel(relation, pred):
"""按谓词过滤。pred 是字符串形式的 Python 表达式，变量即属性名。"""
out = []
for tup in relation:
if eval(pred, {}, tup):
out.append(tup)
return out

def semi_join(left_relation, right_relation, left_attribute, right_attribute):
"""左半连接：保留 left 中能在 right 里找到匹配的元组，列不变、不复制。"""
ht = set()
for tup in right_relation:
ht.add(tup[right_attribute])
out = []
for tup in left_relation:
if tup[left_attribute] in ht:
out.append(tup)
return out

print("price<10 的 books:", filter_rel(books, "price < 10"))
print("persons ⋉ orders :", semi_join(persons, orders, "name", "person_name"))
```

复杂度：半连接只对右关系建一次哈希集合 `O(|S|)`，再扫一遍左关系 `O(|R|)`，总计 `O(|R| + |S|)`，且**不产生元组复制**。这是它比连接便宜的根本原因。

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

步骤 6：连接图与半连接顺序

用邻接表表示连接图，用 BFS（广度优先搜索）从根出发确定半连接顺序。

```python
import queue

class JoinGraph:
"""无向连接图：节点是关系编号，边是连接谓词。"""

def __init__(self, n):
self.n = n
self.adj = {i: set() for i in range(n)}

def add_join(self, a, b):
self.adj[a].add(b)
self.adj[b].add(a)

def get_neighbors(self, x):
return sorted(self.adj[x]) # 排序保证顺序确定

def compute_semi_join_order(join_graph, root):
"""从 root 出发做 BFS，返回半连接顺序 [(父, 子), ...]。"""
order = []
visited = set()
q = queue.Queue()
q.put(root)
visited.add(root)
while not q.empty():
x = q.get()
for nb in join_graph.get_neighbors(x):
if nb in visited:
continue
visited.add(nb)
order.append((x, nb))
q.put(nb)
return order

jg = JoinGraph(3)
jg.add_join(0, 1) # persons — orders
jg.add_join(1, 2) # orders — books

for r in (0, 1, 2):
print(f"以节点 {r} 为根:", compute_semi_join_order(jg, r))
```

预期输出：

```
以节点 0 为根: [(0, 1), (1, 2)]
以节点 1 为根: [(1, 0), (1, 2)]
以节点 2 为根: [(2, 1), (1, 0)]
```

语义：`(a, b)` 表示"用 b 去归约 a"，即执行 `R_a ⋉ R_b`。`reversed(order)` 就是自底向上（叶→根），`order` 反过来用就是自顶向下（根→叶）。

步骤 7：两遍半连接归约（Yannakakis 第 2 步）

```python
def build_context():
"""构造连接图、关系字典、连接属性字典。"""
jg = JoinGraph(3)
jg.add_join(0, 1)
jg.add_join(1, 2)
id_to_relation = {
0: ("persons", [dict(t) for t in persons]),
1: ("orders", [dict(t) for t in orders]),
2: ("books", filter_rel(books, "price < 10")), # 谓词下推，先过滤
}
ids_to_join = {
(0, 1): ("name", "person_name"),
(1, 0): ("person_name", "name"),
(1, 2): ("book_title", "title"),
(2, 1): ("title", "book_title"),
}
return jg, id_to_relation, ids_to_join

def semi_join_reduction(order, id_to_relation, ids_to_join, passes="both"):
"""按 order 做半连接归约，直接修改 id_to_relation。

passes='up' 只做自底向上；'down' 只做自顶向下；'both' 两遍都做。
"""
def one_pass(pairs):
for left_id, right_id in pairs:
name, left_tuples = id_to_relation[left_id]
_, right_tuples = id_to_relation[right_id]
l_attr, r_attr = ids_to_join[(left_id, right_id)]
reduced = semi_join(left_tuples, right_tuples, l_attr, r_attr)
id_to_relation[left_id] = (name, reduced)

if passes in ("up", "both"):
one_pass(reversed(order)) # 叶 → 根
if passes in ("down", "both"):
one_pass((b, a) for a, b in order) # 根 → 叶（方向反转）

jg, ctx, joins = build_context()
order = compute_semi_join_order(jg, 1) # 以 orders 为根
semi_join_reduction(order, ctx, joins, passes="both")

for rid, (name, tuples_) in sorted(ctx.items()):
print(f"{name}: {len(tuples_)} 条")
for t in tuples_:
print(" ", t)
```

预期输出：

```
persons: 2 条
{'name': 'Alice', 'birthday': '1990-01-01'}
{'name': 'Carol', 'birthday': '2000-09-09'}
orders: 3 条
{'person_name': 'Alice', 'book_title': 'DB101'}
{'person_name': 'Carol', 'book_title': 'AI101'}
{'person_name': 'Alice', 'book_title': 'AI101'}
books: 2 条
{'title': 'DB101', 'author': 'Alice', 'price': 8.5}
{'title': 'AI101', 'author': 'Alice', 'price': 9.9}
```

对照 4.2 节的悬挂元组表：`Dave`、`Bob`、`CG101`、`(Bob, OS101)` 全部被删掉了。

步骤 8：只做一遍会怎样（关键对照）

```python
for passes in ("up", "down", "both"):
jg2, ctx2, joins2 = build_context()
semi_join_reduction(compute_semi_join_order(jg2, 1), ctx2, joins2, passes=passes)
sizes = {name: len(t) for _, (name, t) in sorted(ctx2.items())}
print(f"passes={passes:<5} -> {sizes}")
```

预期输出：

```
passes=up -> {'persons': 4, 'orders': 3, 'books': 3}
passes=down -> {'persons': 3, 'orders': 4, 'books': 2}
passes=both -> {'persons': 2, 'orders': 3, 'books': 2}
```

作为参照：原始（未归约）时三个关系是 `persons=4, orders=4, books=3`（`books` 已按 `price<10` 过滤）。

读这张表：

• 只做自底向上：被归约的只有 `orders`（`4 → 3`，删掉了 `(Bob, OS101)`）。`persons` 与 `books` 在这一遍里根本没被动过，`Dave`、`Bob`、`CG101` 全都还在。

• 只做自顶向下：`persons` 从 4 降到 3（删掉了 `Dave`，但 `Bob` 还在，因为此时用的是**未归约**的 `orders`）；`books` 从 3 降到 2（删掉了 `CG101`）；`orders` 没被动过，`(Bob, OS101)` 还在。

• 两遍都做：三个关系全部归约到位，`persons=2, orders=3, books=2`。

一句话总结：**每一遍只归约"箭头头部"那一侧的关系**。自底向上的箭头指向根（`orders`），所以只有 `orders` 变小；自顶向下的箭头指向叶，所以只有 `persons` 和 `books` 变小。两遍合起来才能覆盖所有关系。

步骤 9：结果子数据库函数 + 正确性验证

把前两步封装成一个函数，并验证"归约后再连接 == 原关系直接连接"。

```python
def resultDB(join_graph, id_to_relation, ids_to_join, root=1):
"""计算结果子数据库：Yannakakis 算法的前两步。"""
order = compute_semi_join_order(join_graph, root)
semi_join_reduction(order, id_to_relation, ids_to_join, passes="both")
return id_to_relation

jg, ctx, joins = build_context()
sub = resultDB(jg, ctx, joins, root=1)

用归约后的关系做最终连接

final = hash_join(
hash_join(sub[0][1], sub[1][1], "name", "person_name"),
sub[2][1], "book_title", "title",
)

def normalize(rows):
return sorted(tuple(sorted(r.items())) for r in rows)

print("归约后连接的结果 == 原连接结果:",
normalize(final) == normalize(full_join_result()))
print("归约后连接行数:", len(final), " 原连接行数:", len(full_join_result()))
```

预期输出：

```
归约后连接的结果 == 原连接结果: True
归约后连接行数: 3 原连接行数: 3
```

步骤 10：换一个根，验证结果与根无关

```python
for root in (0, 1, 2):
jg3, ctx3, joins3 = build_context()
s = resultDB(jg3, ctx3, joins3, root=root)
print(f"root={root}: " + ", ".join(
f"{s[i][0]}={len(s[i][1])}" for i in sorted(s)))
```

预期输出三条完全一样的 `persons=2, orders=3, books=2`。

步骤 11（可选）：用 system 模块重跑一遍

若你在本仓库根目录下运行，可以直接用教学 DBMS 的算子：

```python
import sys, pathlib
for p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
if (p / "system").is_dir():
sys.path.insert(0, str(p))
break

from system.query_processing.operators import Relation, Filter, SHJ, SemiJ, Print

rel_persons = Relation("persons", persons)
rel_orders = Relation("orders", orders)
rel_books = Relation("books", books)
filter_books = Filter(rel_books, "price < 10")
join_orders_books = SHJ(rel_orders, filter_books, "book_title", "title")
filtered_persons = SemiJ(rel_persons, join_orders_books, "name", "person_name")
plan = Print(filtered_persons)
plan.dump()
plan.interpret_open()
```

`dump()` 打印出的算子树：

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

注意这里的 `SemiJ` 只解决了 `persons` 一个关系——这正是 2.5 节说的：单独的半连接拿不到其他关系的归约结果，必须上 Yannakakis 的两遍归约。

六、观测记录表

6.1 完整连接结果

| 项目 | 值 |
| --- | --- |
| `persons` 行数 | 4 |
| `orders` 行数 | 4 |
| `books` 行数（过滤后） | |
| 完整连接结果行数 | |
| 完整连接结果中不同的 `name` 个数 | |
| 完整连接结果中不同的 `book_title` 个数 | |

6.2 结果子数据库（三种方法对照）

| 方法 | persons | orders | books | 整套连接被执行几次 | 是否物化中间结果 |
| --- | ---: | ---: | ---: | ---: | --- |
| 动态 `SELECT DISTINCT` | | | | | 否 |
| 物化 `SELECT DISTINCT` | | | | | 是 |
| Yannakakis 前两步 | | | | | 否 |

6.3 半连接归约的遍数对照

| 遍数 | persons 剩余 | orders 剩余 | books 剩余 | 说明 |
| --- | ---: | ---: | ---: | --- |
| 0 遍（原始） | 4 | 4 | 3 | books 已按 `price<10` 过滤 |
| 只自底向上 | | | | |
| 只自顶向下 | | | | |
| 两遍（完整） | | | | |

6.4 根的选择

| 根 | persons | orders | books | 是否与根无关 |
| --- | ---: | ---: | ---: | --- |
| 0（persons） | | | | |
| 1（orders） | | | | |
| 2（books） | | | | |

6.5 悬挂元组核对

| 元组 | 是否在归约后保留 | 你判断它是悬挂元组的理由 |
| --- | --- | --- |
| Dave（persons） | | |
| Bob（persons） | | |
| CG101（books） | | |
| (Bob, OS101)（orders） | | |

七、思考题

1. 半连接 `R ⋉ S` 与连接 `R ⋈ S` 之后再对 `R` 的列做投影去重，结果是否总是相同？给出理由或反例。
2. 本实验的 persons 有 4 条、完整连接结果有 3 行。请计算：完整连接结果中 `Alice` 出现了几次？如果 `Alice` 有 100 个订单且都满足条件，完整连接结果会有多少行，而结果子数据库里的 `persons` 部分有多少行？这说明结果子数据库省掉了什么？
3. 为什么 Yannakakis 算法要做**两遍**半连接归约？用本实验的数据举一个"只做自底向上会漏删"的具体元组。
4. 半连接 `R ⋉_{A=B} S` 的时间复杂度是多少？若用哈希实现，空间复杂度是多少？与完整连接 `R ⋈_{A=B} S` 相比，差别在哪？
5. `SELECT DISTINCT` 里的 `DISTINCT` 能不能去掉？去掉之后会发生什么？
6. 物化 `SELECT DISTINCT` 在什么情况下比动态 `SELECT DISTINCT` 更差？给出具体的判断条件。
7. Yannakakis 算法要求连接图无环。如果连接图有环（例如三角形），两遍半连接归约还能保证删掉所有悬挂元组吗？举例说明。
8. 本实验中"选根"不影响最终结果，那实际系统为什么还要挑根？挑根影响的是什么？
9. 半连接不是对称的：`R ⋉ S` 与 `S ⋉ R` 一般不同。请用本实验的数据算出 `persons ⋉ orders` 和 `orders ⋉ persons` 的行数。

八、思考题答案与解析

8.1 题 1

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

左边（半连接）：

```
R ⋉_{A=B} S = { t ∈ R | ∃ s ∈ S : t[A] = s[B] }
```

右边（连接后投影去重）：

```
π_R-cols( R ⋈_{A=B} S ) = { t | ∃ s ∈ S : t[A] = s[B] }
```

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

反例只可能出现在**非等值连接**或**投影列包含 S 的列**时。例如 `θ` 连接条件是非等值的，或投影里带了 `S` 的属性，此时右边的结果列数不同，集合自然也不同。

这正是步骤 3 里 `SELECT DISTINCT persons.*` 能等价于 `persons ⋉ (orders ⋈ books)` 的原因。

8.2 题 2

• 本实验完整连接结果中 `Alice` 出现 **2 次**（`DB101` 一次、`AI101` 一次）。

• 若 `Alice` 有 100 个满足条件的订单：完整连接结果中 `Alice` 出现 **100 行**；而结果子数据库里 `persons` 部分**只有 1 行**（就是 `Alice` 这一条）。

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

用代码验证：

```python
fanout = 100
persons_big = [{"name": "Alice", "birthday": "1990-01-01"}]
books_big = [{"title": f"B{i}", "author": "Alice", "price": 1.0} for i in range(fanout)]
orders_big = [{"person_name": "Alice", "book_title": f"B{i}"} for i in range(fanout)]

jb = hash_join(orders_big, books_big, "book_title", "title")
full = hash_join(persons_big, jb, "name", "person_name")
print("完整连接行数:", len(full))
sub_persons = semi_join(persons_big, jb, "name", "person_name")
print("子数据库 persons 行数:", len(sub_persons))
```

预期：`完整连接行数: 100`，`子数据库 persons 行数: 1`。

8.3 题 3

两个原因，缺一不可。

**原因一：每一遍只归约箭头头部那一侧。**

半连接 `R_a ⋉ R_b` 只改变 `R_a`。以 `orders` 为根时，半连接顺序是 `[(1,0), (1,2)]`：

• 自底向上用 `reversed`，即按 `(1,2)`、`(1,0)` 执行，被改写的关系**只有 `orders`**。`persons`（4 条）与 `books`（3 条）一行都没动。

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

所以只做一遍，必然有关系的元组从未被检查过。

**原因二：归约会制造新的悬挂元组。**

这是更本质的一点。以 `persons` 里的 `Bob` 为例：

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

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

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

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

本实验数据里可以逐一指认：

| 元组 | 哪一遍删掉它 | 说明 |
| --- | --- | --- |
| `(Bob, OS101)` ∈ orders | 自底向上（`orders ⋉ books'`） | 引用的书被 `price<10` 过滤掉 |
| `Dave` ∈ persons | 自顶向下（`persons ⋉ orders'`） | 从来没有订单 |
| `Bob` ∈ persons | 自顶向下（`persons ⋉ orders'`） | 唯一的订单在前一遍被删了 → 新产生的悬挂元组 |
| `CG101` ∈ books | 自顶向下（`books ⋉ orders'`） | 通过了价格过滤，但没有订单引用它 |

只做自底向上会漏掉后三个；只做自顶向下会漏掉 `Bob` 和 `(Bob, OS101)`（`orders` 在那一遍里没被改写）。两遍合起来才是完整的。

8.4 题 4

哈希实现的半连接：

• 建阶段：扫一遍 `S`，把 `S[B]` 的所有取值放进哈希集合，代价 `O(|S|)`。

• 探阶段：扫一遍 `R`，对每个 `t` 查一次集合，代价 `O(|R|)`。

• **时间复杂度**：`O(|R| + |S|)`。

• **空间复杂度**：`O(min(|S|, |π_B(S)|))`，实际上哈希集合的大小等于 `S` 在 `B` 上不同取值的个数，最坏 `O(|S|)`。

完整哈希连接：

• 时间同样是 `O(|R| + |S|)`，但要**再乘一个输出因子**：每个匹配的 `(t, s)` 对都要物化一次。记输出大小为 `OUT`，时间是 `O(|R| + |S| + OUT)`。

• 空间：哈希表存的是 `S` 的**整条元组**，不只是连接键，所以空间是 `O(|S|)` 的常数倍（比只存键的集合大得多）。

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

8.5 题 5

不能去掉。

`SELECT persons.* FROM persons JOIN orders ... JOIN books ...` 会为 `persons` 的每个匹配输出一行。`Alice` 有 2 个匹配，就会输出 2 行 `Alice`。

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

验证（需要 duckdb）：

```python
print(con.execute("SELECT persons.* " + body).fetchall()) # Alice 出现 2 次
print(con.execute("SELECT DISTINCT persons.* " + body).fetchall()) # Alice 出现 1 次
```

8.6 题 6

设：

• `OUT` = 完整连接结果的行数

• `C` = 执行一次完整连接的代价

• `k` = 参与连接的关系数

动态方法总代价 ≈ `k · C`；物化方法总代价 ≈ `C + Write(OUT) + k · Read(OUT)`。

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

1. **`OUT` 很大**，`Write(OUT)` 与 `k · Read(OUT)` 之和超过 `(k−1) · C`。当连接结果远大于输入关系之和（高扇出连接）时必然发生。
2. **磁盘/内存放不下** `OUT`，必须落盘甚至溢写到外部存储，I/O 代价急剧上升。
3. **`k` 很小**（例如 `k = 2`）：此时动态方法只多算 1 次连接，而物化要多付一整轮写入与读出。
4. **`C` 很便宜**（例如各关系都很小、有索引可用）：重复计算的代价本来就不高。

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

8.7 题 7

不能保证。

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

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

具体例子：三个关系 `A(x,y)`、`B(y,z)`、`C(z,x)`，连接图是三角形。

```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)

完整连接结果

full = []
for a in A:
for b in B:
if a["y"] != b["y"]:
continue
for c in C:
if b["z"] == c["z"] and a["x"] == c["x"]:
full.append((a, b, c))
print("完整连接行数:", len(full)) # 只有 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` 的两条元组都留下了，`{"x":2,"y":2}` 没被删掉。原因是它是否悬挂取决于 `C` 里有没有 `(z=2, x=2)`，而这条约束在生成树里对应的边 `C—A` 被丢掉了。

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

8.8 题 8

结果的**内容**与根无关（无环条件下的理论保证，本实验步骤 10 已验证），但归约的**中间结果大小**和**执行顺序**与根有关。

挑根影响的是性能：

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

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

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

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

本实验步骤 10 显示三种根的最终结果相同，但可用 `print` 把每步归约后的行数打出来，观察中间大小确实不同。

8.9 题 9

```python
print("persons ⋉ orders :", len(semi_join(persons, orders, "name", "person_name")))
print("orders ⋉ persons:", len(semi_join(orders, persons, "person_name", "name")))
```

预期输出：

```
persons ⋉ orders : 3
orders ⋉ persons: 4
```

• `persons ⋉ orders`：`persons` 中 `name` 出现在 `orders.person_name` 里的有 `Alice`、`Bob`、`Carol`，共 3 条（`Dave` 被删）。

• `orders ⋉ persons`：`orders` 中 `person_name` 出现在 `persons.name` 里的有全部 4 条（`Alice`、`Bob`、`Carol` 都在 `persons` 里）。

**半连接不对称**：左边的行数是上限，右边只起"过滤器"作用。这与普通连接 `R ⋈ S == S ⋈ R`（列顺序不同但行数相同）不同。

九、扩展任务（选做）

9.1 把链扩展到 5 个关系

构造 `A—B—C—D—E` 的链，重复步骤 7–9，观察归约的传播过程。思考：链长为 `k` 时，一条悬挂元组要多少步才能被删掉？

9.2 星型连接图

构造事实表 `F` 与维表 `D1, D2, D3` 的星型连接图（`D1—F`、`D2—F`、`D3—F`）。以 `F` 为根和以 `D1` 为根，比较中间结果大小。

9.3 比较三种方法的实测代价

```python
import time

def timeit(fn, repeat=20):
t0 = time.perf_counter()
for _ in range(repeat):
fn()
return (time.perf_counter() - t0) / repeat * 1000 # ms
```

分别给"完整连接 + 逐关系去重"、"两遍半连接归约"计时，在自造的较大数据（例如 persons 10,000、orders 50,000、books 10,000）上对比。**注意**：具体数字取决于你的机器，需自行实测确认。

9.4 与 `system` 模块的差异测试

阅读 `system/tests/` 中关于结果子数据库的测试文件，理解"差异测试"（differential testing）的思路：同一个查询用两种不同实现跑，结果必须一致。为本实验的三个方法写一组差异测试。

9.5 阅读

Yannakakis, *Algorithms for Acyclic Database Schemes*, VLDB 1981, pp. 82–94。重点看定理部分：为什么无环性（acyclicity）是该算法正确性的充要条件级别的前提。

十、常见错误与排查

| 现象 | 原因 | 处理 |
| --- | --- | --- |
| 归约后 `books` 仍有 4 条（含 `CG101`） | 只做了自底向上一遍 | 必须做两遍；检查 `passes` 参数 |
| 归约后 `persons` 仍有 4 条（含 `Dave`） | 只做了自顶向下一遍 | 同上 |
| 自顶向下方向写错，`KeyError` 或结果不对 | 自顶向下要把 `(父, 子)` 反转成 `(子, 父)` | 用 `(b, a) for a, b in order` |
| `KeyError: (2, 0)` | 连接图里没有这条边，但归约顺序生成了它 | 检查 `add_join` 是否把所有连接谓词都加进去了，且 `ids_to_join` 要包含**两个方向** |
| `eval()` 报 `NameError` | 谓词字符串里的属性名与字典的键不一致 | 核对 `price < 10` 中的 `price` 是否确为 `books` 的键 |
| 半连接结果出现重复元组 | 把半连接写成了连接（在探阶段做了嵌套循环 `append`） | 探阶段对每个 `t` 最多 `append` 一次 |
| 结果子数据库与完整连接结果对不上 | 忘了把 `price < 10` 过滤下推到 `books`，或过滤顺序不对 | 在 `build_context()` 里对 `books` 先过滤 |
| 换根后结果不同 | 连接图有环，或 `get_neighbors` 未排序导致 BFS 顺序不稳定 | 确认连接图无环；`get_neighbors` 返回 `sorted(...)` |
| duckdb 报 `Catalog Error: Table with name mv already exists` | 上一次运行没有 `DROP TABLE mv` | 先执行 `DROP TABLE IF EXISTS mv` |
| duckdb 建表后插入的元组顺序与 Python 列表不一致 | 关系是无序集合，SQL 不保证顺序 | 比较结果时先排序，不要依赖行顺序 |
| `import system` 失败 | 工作目录不在仓库根，或根不在 `sys.path` | 用步骤 11 里的 `pathlib` 片段把仓库根加入 `sys.path` |
| 用 `eval()` 处理了来自用户的字符串 | 代码注入风险 | 教学环境可接受；工程代码改用白名单解析或预编译谓词对象 |

附：本实验引用的文献与术语

| 条目 | 出处 / 说明 |
| --- | --- |
| Yannakakis 算法 | Yannakakis, *Algorithms for Acyclic Database Schemes*, VLDB 1981, pp. 82–94 |
| 半连接定义 | `R ⋉_{A=B} S = { t ∈ R : ∃ s ∈ S, t[A] = s[B] }`，只保留左关系列，用于删除悬挂元组 |
| 悬挂元组 | 关系中存在、但在完整连接结果中不出现的元组 |
| 无环合取查询 | 连接图中不存在环的 select-project-join 查询，Yannakakis 算法的适用前提 |
| 结果子数据库 | 每个参与关系只保留参与连接的元组所构成的一组关系；满足 `R₁' ⋈ ... ⋈ Rₖ' == R₁ ⋈ ... ⋈ Rₖ` |