{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实验 08：结果子数据库——半连接与 Yannakakis 算法\n",
    "\n",
    "## 为什么做这个实验\n",
    "\n",
    "- **要验证的现象**：一个多表连接查询，能不能**不算出庞大的完整连接结果**，只把\"每个表里真正参与连接的那些元组\"分别挑出来？这就是**结果子数据库（result subdatabase）**。\n",
    "- **反直觉之处一**：半连接 $R \\ltimes S$ 只输出**左关系**的元组，列数不变、不复制。它是\"过滤器\"而不是\"组合器\"。它恰好能删掉**悬挂元组**（dangling tuple）——在自己表里存在、但在完整连接结果里一次都不出现的元组。\n",
    "- **反直觉之处二**：删悬挂元组要**归约两遍**（自底向上 + 自顶向下）才够。只做一遍必然漏删，因为**归约本身会制造新的悬挂元组**：上游被删掉之后，原本在下游有配对的元组可能变成新的悬挂元组。这是本实验最重要的考点。\n",
    "- **反直觉之处三**：完整连接结果常常比\"参与连接的实体\"大得多。一个客户有 100 个订单，连接结果里他就重复 100 次，而结果子数据库里他只出现 1 次。省掉的是连接的**乘法效应**。\n",
    "- **学完能回答**：Yannakakis 算法成立的前提是什么（连接图**无环**）？两种 SQL 改写各自付出了什么代价？为什么根的选择不影响结果却影响性能？\n",
    "\n",
    "## 运行前准备\n",
    "\n",
    "```bash\n",
    "python -m pip install duckdb pandas faker\n",
    "```\n",
    "\n",
    "另外全局需要 `numpy` `matplotlib` `seaborn`。验证：\n",
    "\n",
    "```python\n",
    "import duckdb, pandas, faker\n",
    "print(\"环境就绪\")\n",
    "```\n",
    "\n",
    "| 依赖 | 用在哪 | 是否必须 |\n",
    "|---|---|---|\n",
    "| `duckdb` | \"Rewrite Methods\" 两节的 SQL 改写 | 可选（跳过这两节不影响后半部分） |\n",
    "| `pandas` | 把对象列表转成 DataFrame 灌进 duckdb | 可选 |\n",
    "| `faker` | 生成示例数据 | 必须（造数据那一步要用） |\n",
    "| 仓库 `system/` | `JoinGraph`、`Relation`、`Filter`、`SHJ`、`SemiJ`、`Collect` 等算子 | 必须 |\n",
    "\n",
    "> 如果 `import system` 失败，先运行第一个代码格——它会把仓库根目录（含 `system/` 的那一层）加入 `sys.path`。\n"
   ],
   "id": "57febb5b"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys, pathlib\n",
    "\n",
    "# Put the repo root (the directory containing `system/`) on sys.path so\n",
    "# `from system...` works whether this notebook is opened from its own\n",
    "# folder or from the repo root.\n",
    "for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):\n",
    "    if (_p / \"system\").is_dir():\n",
    "        if str(_p) not in sys.path:\n",
    "            sys.path.insert(0, str(_p))\n",
    "        break"
   ],
   "id": "091c90c1-17b6-4f09-80b9-f0fd416cfc24"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## How would we execute a query like this?\n",
    "\n",
    "``` sql\n",
    "SELECT persons.*\n",
    "FROM persons\n",
    "    JOIN orders ON name = person_name\n",
    "    JOIN books ON book_title = title\n",
    "WHERE price < 10\n",
    "```"
   ],
   "id": "e0942db1e1cbd9ec"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 这条查询要回答什么？先看它的连接图\n",
    "\n",
    "把查询的连接结构画成一张无向图：**每个节点是一个关系，每条边是一个连接谓词**。\n",
    "\n",
    "```text\n",
    "  persons ────── orders ────── books\n",
    "    (0)           (1)           (2)\n",
    "     name = person_name    book_title = title\n",
    "```\n",
    "\n",
    "这是一条**链，没有环**，所以该查询是**无环合取查询**（acyclic conjunctive query）——这正是 Yannakakis 算法的适用前提。\n",
    "\n",
    "如果再加上一个条件 `books.author = persons.name`，图上就会多出一条 `books — persons` 的边，形成一个三角形（有环），此时 Yannakakis 算法不再直接适用。\n",
    "\n",
    "**另外注意 `WHERE price < 10`**：它是单表谓词，不属于连接图，但在后面会被**下推**到 `books` 上先执行（过滤越早越好）。\n"
   ],
   "id": "24f34353"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.309051Z",
     "start_time": "2025-01-06T20:49:05.910547Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import duckdb\n",
    "import pandas as pd\n",
    "import random\n",
    "import queue\n",
    "\n",
    "random.seed(21)\n",
    "\n",
    "from faker import Faker"
   ],
   "id": "9d1f082ba9ef9520",
   "outputs": [],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "\n",
    "\n",
    "## Create fake data"
   ],
   "id": "3c3ef89c9fd1396"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 造数据：为什么固定随机种子\n",
    "\n",
    "数据用 `faker` 生成，并且**固定了两处种子**：\n",
    "\n",
    "```python\n",
    "random.seed(21)     # 控制 orders 里随机挑人、挑书\n",
    "Faker.seed(15)      # 控制 fake.name() / fake.sentence() 等\n",
    "```\n",
    "\n",
    "固定种子是为了让**所有人的输出完全一致**，便于对照讲义里的数字，也便于单元测试。\n",
    "\n",
    "规模：`persons` 3 条、`books` 3 条、`orders` 约 `1.5 × 3` 条（去重用 `if o in orders: continue`）。三个关系都很小，正好可以**手工核对每一步**。\n",
    "\n",
    "**预期看到什么**：`display(persons, books, orders)` 打印出三组对象。请特别留意 `books` 里哪些书的 `price < 10`——只有这些书能通过过滤，后面整条归约链都由它们决定。\n"
   ],
   "id": "9cd92c3e"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.333886Z",
     "start_time": "2025-01-06T20:49:06.310008Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from system.data_classes import Person, Book, Order\n",
    "\n",
    "Faker.seed(15)\n",
    "fake = Faker()\n",
    "\n",
    "number_of_tuples = 3\n",
    "\n",
    "# create some fake data mimicking tuples in a relation\n",
    "persons = [Person(fake.name(), fake.date()) for _ in range(number_of_tuples)]\n",
    "books = [\n",
    "    Book(\n",
    "        fake.sentence(),\n",
    "        fake.name(),\n",
    "        fake.pyfloat(min_value=0, max_value=100, right_digits=2),\n",
    "    )\n",
    "    for _ in range(number_of_tuples)\n",
    "]\n",
    "orders = []\n",
    "i = 0\n",
    "num_orders = 1.5 * number_of_tuples\n",
    "assert number_of_tuples > 0\n",
    "assert num_orders <= number_of_tuples * number_of_tuples\n",
    "while i < num_orders:\n",
    "    o = Order(\n",
    "        persons[random.randint(0, number_of_tuples - 1)].name,\n",
    "        books[random.randint(0, number_of_tuples - 1)].title,\n",
    "    )\n",
    "    if o in orders:\n",
    "        continue\n",
    "    orders.append(o)\n",
    "    i += 1\n",
    "\n",
    "display(persons, books, orders)"
   ],
   "id": "c856711123477933",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Person(name='Alexandra Fitzgerald', birthday='1978-09-11'),\n",
       " Person(name='Mrs. Sherry Maldonado', birthday='2017-03-03'),\n",
       " Person(name='Mrs. Gina Erickson MD', birthday='1984-06-27')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[Book(title='Various deal great finish figure.', author='Jennifer Ray', price=53.62),\n",
       " Book(title='Leave sometimes keep firm.', author='Joanne Frank', price=8.62),\n",
       " Book(title='Cultural move pass.', author='Sarah Smith', price=67.63)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[Order(person_name='Alexandra Fitzgerald', book_title='Leave sometimes keep firm.'),\n",
       " Order(person_name='Mrs. Gina Erickson MD', book_title='Leave sometimes keep firm.'),\n",
       " Order(person_name='Mrs. Sherry Maldonado', book_title='Various deal great finish figure.'),\n",
       " Order(person_name='Mrs. Sherry Maldonado', book_title='Cultural move pass.'),\n",
       " Order(person_name='Alexandra Fitzgerald', book_title='Cultural move pass.')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 2
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## Semi-join",
   "id": "55c07c431dc19bd8"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 半连接：只过滤，不组合\n",
    "\n",
    "给定关系 $R$（属性 $A$）和 $S$（属性 $B$）：\n",
    "\n",
    "| 运算 | 定义 | 输出 |\n",
    "|---|---|---|\n",
    "| 连接 $R \\bowtie_{A=B} S$ | $\\{\\,(t, s) \\mid t \\in R,\\ s \\in S,\\ t[A] = s[B]\\,\\}$ | 元组**对**，列数是两者之和；一个 $t$ 有 3 个匹配就出现 3 次 |\n",
    "| 半连接 $R \\ltimes_{A=B} S$ | $\\{\\,t \\in R \\mid \\exists s \\in S,\\ t[A] = s[B]\\,\\}$ | 只输出左关系的元组，**列数不变**，每个 $t$ 最多一次 |\n",
    "\n",
    "```text\n",
    "R (左)                    S (右)\n",
    "+-------+                +-------+\n",
    "| a | x |                | b | y |\n",
    "+-------+                +-------+\n",
    "| 1 | p |                | 1 | u |\n",
    "| 2 | q |                | 1 | v |\n",
    "| 3 | r |                | 3 | w |\n",
    "+-------+                +-------+\n",
    "\n",
    "R ⋈_{a=b} S                    R ⋉_{a=b} S\n",
    "| 1 | p | 1 | u |              | 1 | p |     ← 只出现一次\n",
    "| 1 | p | 1 | v |              | 3 | r |\n",
    "| 3 | r | 3 | w |\n",
    "```\n",
    "\n",
    "`a=2` 这一行在 $S$ 中没有匹配，两种结果里都不出现。\n",
    "\n",
    "**复杂度**：哈希实现只需对 $S$ 建一次哈希集合 $O(|S|)$，再扫一遍 $R$ 做探测 $O(|R|)$，总计 $O(|R| + |S|)$，且**不产生元组复制**。这是它比连接便宜的根本原因——完整连接还要再乘一个输出因子 $OUT$。\n",
    "\n",
    "**半连接不是对称的**：$R \\ltimes S$ 与 $S \\ltimes R$ 一般不同——输出规模由\"左边是谁\"决定（$|R|$ 是前者的上限，$|S|$ 是后者的上限）。而普通连接 $R \\bowtie S$ 与 $S \\bowtie R$ 只是列顺序不同，**行数相同**。这也是半连接能用于分布式场景的原因：把小的一方作为右关系传过去做过滤，可以避免传输大表。\n",
    "\n",
    "**悬挂元组**：某个关系中\"在完整连接结果里一次都不出现\"的元组。半连接的作用就是**删掉悬挂元组**。\n",
    "\n",
    "下面这段代码用仓库的算子搭了一条流水线（`Filter` → `SHJ` → `SemiJ` → `Print`），`dump()` 会把它打印成一棵算子树：\n",
    "\n",
    "```text\n",
    "Print\n",
    "  SemiJ on `name=person_name`\n",
    "    Relation(persons)\n",
    "    SHJ on `book_title=title`\n",
    "      Relation(orders)\n",
    "      Filter on `price < 10`\n",
    "        Relation(books)\n",
    "```\n"
   ],
   "id": "f12bf5fa"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.340441Z",
     "start_time": "2025-01-06T20:49:06.334427Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from system.query_processing.operators import Relation, Filter, SHJ, SemiJ, Print\n",
    "\n",
    "rel_persons = Relation(\"persons\", [vars(e) for e in persons])\n",
    "rel_orders = Relation(\"orders\", [vars(e) for e in orders])\n",
    "rel_books = Relation(\"books\", [vars(e) for e in books])\n",
    "filter_books = Filter(rel_books, \"price < 10\")\n",
    "join_orders_books = SHJ(rel_orders, filter_books, \"book_title\", \"title\")\n",
    "filtered_persons = SemiJ(rel_persons, join_orders_books, \"name\", \"person_name\")\n",
    "query_plan = Print(filtered_persons)\n",
    "query_plan.dump()"
   ],
   "id": "5b38ca8bfb488349",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Print\n",
      "  SemiJ on `name=person_name`\n",
      "    Relation(persons)\n",
      "    SHJ on `book_title=title`\n",
      "      Relation(orders)\n",
      "      Filter on `price < 10`\n",
      "        Relation(books)\n"
     ]
    }
   ],
   "execution_count": 3
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.361566Z",
     "start_time": "2025-01-06T20:49:06.341178Z"
    }
   },
   "cell_type": "code",
   "source": "query_plan.interpret_open()",
   "id": "1604a70c2bea4cbd",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Alexandra Fitzgerald', '1978-09-11')\n",
      "('Mrs. Gina Erickson MD', '1984-06-27')\n"
     ]
    }
   ],
   "execution_count": 4
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**预期看到什么**：`interpret_open()` 打印出**通过了过滤的 persons 元组**。\n",
    "\n",
    "**但请立刻注意一件事**：这条流水线里的 `SemiJ` 只归约了 `persons` **一个**关系。`orders` 和 `books` 各自还有多少条参与连接？不知道——一次半连接只能回答\"左边这个关系里哪些元组留下了\"。\n",
    "\n",
    "这正是本节要引出的核心问题：\n",
    "\n",
    "> 只关心单个关系时用半连接很方便；要拿到**多个关系**各自的归约结果，就必须上 Yannakakis 的**两遍归约**。\n",
    "\n",
    "（教学实现里 `Filter` 用 `eval()` 把谓词写成字符串，方便演示。工程代码中不要用 `eval()` 处理不可信输入。）\n"
   ],
   "id": "1b6b9a25"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "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.\n",
    "But how can we retrieve just the qualifying tuples from multiple relations *without* computing the full join result?"
   ],
   "id": "e0619c8ca25f546e"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Extend SQL: `SELECT RESULTDB`\n",
    "Consider the database tables with sample data from above.\n",
    "\n",
    "<div style=\"display: flex; gap: 20px;\">\n",
    "\n",
    "<!-- Customers Table -->\n",
    "<table>\n",
    "  <caption>persons</caption>\n",
    "  <tr><th>name</th><th>birthday</th></tr>\n",
    "  <tr><td>Alexandra Fitzgerald</td><td>1978-09-02</td></tr>\n",
    "  <tr><td>Mrs. Sherry Maldonado</td><td>2017-01-14</td></tr>\n",
    "  <tr><td>Mrs. Gina Erickson MD</td><td>1984-06-12</td></tr>\n",
    "</table>\n",
    "\n",
    "<!-- Orders Table -->\n",
    "<table>\n",
    "  <caption>orders</caption>\n",
    "  <tr><th>person_name</th><th>book_title</th></tr>\n",
    "  <tr><td>Alexandra Fitzgerald</td><td>Leave sometimes keep firm.</td></tr>\n",
    "  <tr><td>Mrs. Gina Erickson MD</td><td>Leave sometimes keep firm.</td></tr>\n",
    "  <tr><td>Mrs. Sherry Maldonado</td><td>Various deal great finish figure.</td></tr>\n",
    "  <tr><td>Mrs. Sherry Maldonado</td><td>Cultural move pass.</td></tr>\n",
    "  <tr><td>Alexandra Fitzgerald</td><td>Cultural move pass.</td></tr>\n",
    "</table>\n",
    "\n",
    "<!-- Books Table -->\n",
    "<table>\n",
    "  <caption>books</caption>\n",
    "  <tr><th>title</th><th>author</th><th>price</th></tr>\n",
    "  <tr><td>Various deal great finish figure.</td><td>Jennifer Ray</td><td>53.62</td></tr>\n",
    "  <tr><td>Leave sometimes keep firm.</td><td>Joanne Frank</td><td>8.62</td></tr>\n",
    "  <tr><td>Cultural move pass.</td><td>Sarah Smith</td><td>67.63</td></tr>\n",
    "</table>\n",
    "\n",
    "</div>\n",
    "\n",
    "\n",
    "Executing the following query:\n",
    "``` sql\n",
    "SELECT RESULTDB *\n",
    "FROM persons\n",
    "    JOIN orders ON name = person_name\n",
    "    JOIN books ON book_title = title\n",
    "WHERE price < 10\n",
    "```\n",
    "would result in the following reduced relations:\n",
    "\n",
    "<div style=\"display: flex; gap: 20px;\">\n",
    "\n",
    "<!-- Customers Table -->\n",
    "<table>\n",
    "  <caption>persons (reduced)</caption>\n",
    "  <tr><th>name</th><th>birthday</th></tr>\n",
    "  <tr><td>Alexandra Fitzgerald</td><td>1978-09-02</td></tr>\n",
    "  <tr><td>Mrs. Gina Erickson MD</td><td>1984-06-12</td></tr>\n",
    "</table>\n",
    "\n",
    "<!-- Orders Table -->\n",
    "<table>\n",
    "  <caption>orders (reduced)</caption>\n",
    "  <tr><th>person_name</th><th>book_title</th></tr>\n",
    "  <tr><td>Alexandra Fitzgerald</td><td>Leave sometimes keep firm.</td></tr>\n",
    "  <tr><td>Mrs. Sherry Maldonado</td><td>Leave sometimes keep firm.</td></tr>\n",
    "</table>\n",
    "\n",
    "<!-- Books Table -->\n",
    "<table>\n",
    "  <caption>books (reduced)</caption>\n",
    "   <tr><th>title</th><th>author</th><th>price</th></tr>\n",
    "  <tr><td>Leave sometimes keep firm.</td><td>Joanne Frank</td><td>8.62</td></tr>\n",
    "</table>\n",
    "\n",
    "</div>\n",
    "\n",
    "In the following, we are going to discuss two possibilities to compute this result *subdatabase*."
   ],
   "id": "81793bdbf2f83604"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `SELECT RESULTDB *`：换一种问法\n",
    "\n",
    "传统的查询结果是**一个关系**（一张新表）。结果子数据库换了个问法：\n",
    "\n",
    "> 对于查询 $Q$ 涉及的每一个关系 $R_i$，$R_i$ 中哪些元组真正参与了 $Q$ 的连接结果？\n",
    "\n",
    "答案是一组关系 $R_i' \\subseteq R_i$，每个只保留参与连接的元组，并且满足\n",
    "\n",
    "$$R_1' \\bowtie R_2' \\bowtie \\dots \\bowtie R_k' \\;=\\; R_1 \\bowtie R_2 \\bowtie \\dots \\bowtie R_k$$\n",
    "\n",
    "即：**用归约后的关系做最终连接，完整连接结果与用原关系完全一致**；同时每个关系里的悬挂元组都被删掉了。\n",
    "\n",
    "上面那张对照表就是本笔记本这份数据的答案：persons 从 3 条降到 2 条，orders 从若干条降到 2 条，books 从 3 条降到 1 条。\n",
    "\n",
    "**为什么要这个东西**：很多分析任务（图分析、机器学习特征抽取、可视化）真正需要的不是连接结果的宽表，而是\"这张大图里到底涉及哪些实体和哪些边\"。完整连接结果往往比子数据库大得多——**一个客户有 100 个订单，连接结果里这个客户就重复 100 次，而子数据库里只有 1 次**。\n",
    "\n",
    "**分布式场景下的另一个动机**：先把悬挂元组删掉再跨网络传输，可以显著减少传输量。本笔记本不给出传输量的具体数字，分布式半连接归约的实测在配套课程的\"分布式连接\"实验中，需自行实测确认。\n"
   ],
   "id": "a47ddbf0"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "\n",
    "## Rewrite Methods\n",
    "In this section, we demonstrate two SQL-based rewrite methods that can be used to compute a result subdatabase.\n",
    "\n",
    "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."
   ],
   "id": "bf8e832e18e5b984"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.391023Z",
     "start_time": "2025-01-06T20:49:06.362724Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# setup duckdb database\n",
    "con = duckdb.connect(database=\":memory:\")\n",
    "\n",
    "# convert to Pandas DataFrame\n",
    "persons_df = pd.DataFrame(persons)\n",
    "orders_df = pd.DataFrame(orders)\n",
    "books_df = pd.DataFrame(books)\n",
    "\n",
    "# import data\n",
    "con.execute(\"CREATE TABLE persons AS SELECT * FROM persons_df\")\n",
    "con.execute(\"CREATE TABLE orders AS SELECT * FROM orders_df\")\n",
    "con.execute(\"CREATE TABLE books AS SELECT * FROM books_df\")"
   ],
   "id": "a2907d1c5c2b232b",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<duckdb.duckdb.DuckDBPyConnection at 0x7cd9b618f330>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "execution_count": 5
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 1. Dynamic `SELECT DISTINCT`\n",
    "This rewrite method transform a single `SELECT RESULTDB` query into multiple `SELECT DISTINCT` queries, one for each relation that is part of the query."
   ],
   "id": "1e7861c7a254619f"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.411921Z",
     "start_time": "2025-01-06T20:49:06.391614Z"
    }
   },
   "cell_type": "code",
   "source": [
    "filtered_persons_dynamic = con.execute(\"\"\"\n",
    "    SELECT DISTINCT persons.*\n",
    "    FROM persons\n",
    "        JOIN orders ON name = person_name\n",
    "        JOIN books ON book_title = title\n",
    "    WHERE price < 10;\n",
    "    \"\"\")\n",
    "display(filtered_persons_dynamic.fetch_df())\n",
    "filtered_orders_dynamic = con.execute(\"\"\"\n",
    "    SELECT DISTINCT orders.*\n",
    "    FROM persons\n",
    "        JOIN orders ON name = person_name\n",
    "        JOIN books ON book_title = title\n",
    "    WHERE price < 10;\n",
    "    \"\"\")\n",
    "display(filtered_orders_dynamic.fetch_df())\n",
    "filtered_books_dynamic = con.execute(\"\"\"\n",
    "    SELECT DISTINCT books.*\n",
    "    FROM persons\n",
    "        JOIN orders ON name = person_name\n",
    "        JOIN books ON book_title = title\n",
    "    WHERE price < 10;\n",
    "    \"\"\")\n",
    "display(filtered_books_dynamic.fetch_df())"
   ],
   "id": "d2731851ce5abd71",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "                    name    birthday\n",
       "0   Alexandra Fitzgerald  1978-09-11\n",
       "1  Mrs. Gina Erickson MD  1984-06-27"
      ],
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>name</th>\n",
       "      <th>birthday</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Alexandra Fitzgerald</td>\n",
       "      <td>1978-09-11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Mrs. Gina Erickson MD</td>\n",
       "      <td>1984-06-27</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "             person_name                  book_title\n",
       "0   Alexandra Fitzgerald  Leave sometimes keep firm.\n",
       "1  Mrs. Gina Erickson MD  Leave sometimes keep firm."
      ],
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>person_name</th>\n",
       "      <th>book_title</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Alexandra Fitzgerald</td>\n",
       "      <td>Leave sometimes keep firm.</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Mrs. Gina Erickson MD</td>\n",
       "      <td>Leave sometimes keep firm.</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "                        title        author  price\n",
       "0  Leave sometimes keep firm.  Joanne Frank   8.62"
      ],
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>title</th>\n",
       "      <th>author</th>\n",
       "      <th>price</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Leave sometimes keep firm.</td>\n",
       "      <td>Joanne Frank</td>\n",
       "      <td>8.62</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 6
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**动态 `SELECT DISTINCT` 的代价**：$k$ 个关系就要把整套连接算 **$k$ 遍**（本例 $k = 3$），而且除了 `SELECT` 子句之外，这 $k$ 条 SQL 完全一样。总代价约 $k \\cdot C$（$C$ 为执行一次完整连接的代价）。\n",
    "\n",
    "**`DISTINCT` 是必需的，不能去掉**：连接会给左关系的元组做复制，`DISTINCT` 把副本消掉，正好对应半连接\"不复制\"的性质。去掉之后，某个人有 2 个匹配就会输出 2 行，得到的是**多重集**而不是**集合**，与半连接语义不符。\n"
   ],
   "id": "26a8448e"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 2. Materialized `SELECT DISTINCT`\n",
    "This rewrite method first materializes the necessary attributes of the single-table result in a temporary and unmaintained materialized view (MV) once.\n",
    "Afterward, this MV is queried to obtain the individual result sets, and the MV is dropped again."
   ],
   "id": "cc4b33c828ddd061"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.428067Z",
     "start_time": "2025-01-06T20:49:06.412516Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# duckdb does not support `CREATE MATERIALIZED VIEW`s, therefore simulate the MV\n",
    "con.execute(\"\"\"\n",
    "    CREATE TABLE IF NOT EXISTS materialized_view AS\n",
    "    SELECT *\n",
    "    FROM persons\n",
    "        JOIN orders ON name = person_name\n",
    "        JOIN books ON book_title = title\n",
    "    WHERE price < 10;\n",
    "    \"\"\")\n",
    "filtered_persons_mat = con.execute(\n",
    "    \"SELECT DISTINCT name, birthday FROM materialized_view\"\n",
    ")\n",
    "display(filtered_persons_mat.fetch_df())\n",
    "\n",
    "filtered_orders_mat = con.execute(\n",
    "    \"SELECT DISTINCT person_name, book_title FROM materialized_view\"\n",
    ")\n",
    "display(filtered_orders_mat.fetch_df())\n",
    "\n",
    "filtered_books_mat = con.execute(\n",
    "    \"SELECT DISTINCT title, author, price FROM materialized_view\"\n",
    ")\n",
    "display(filtered_books_mat.fetch_df())"
   ],
   "id": "911b2dce69bcf7d7",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "                    name    birthday\n",
       "0   Alexandra Fitzgerald  1978-09-11\n",
       "1  Mrs. Gina Erickson MD  1984-06-27"
      ],
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>name</th>\n",
       "      <th>birthday</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Alexandra Fitzgerald</td>\n",
       "      <td>1978-09-11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Mrs. Gina Erickson MD</td>\n",
       "      <td>1984-06-27</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "             person_name                  book_title\n",
       "0   Alexandra Fitzgerald  Leave sometimes keep firm.\n",
       "1  Mrs. Gina Erickson MD  Leave sometimes keep firm."
      ],
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>person_name</th>\n",
       "      <th>book_title</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Alexandra Fitzgerald</td>\n",
       "      <td>Leave sometimes keep firm.</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Mrs. Gina Erickson MD</td>\n",
       "      <td>Leave sometimes keep firm.</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "                        title        author  price\n",
       "0  Leave sometimes keep firm.  Joanne Frank   8.62"
      ],
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>title</th>\n",
       "      <th>author</th>\n",
       "      <th>price</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Leave sometimes keep firm.</td>\n",
       "      <td>Joanne Frank</td>\n",
       "      <td>8.62</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 7
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**物化 `SELECT DISTINCT` 的取舍**\n",
    "\n",
    "- **优点**：整套连接只算一次，避免了 $k$ 次重复计算。\n",
    "- **缺点**：要把一个**可能很大**的连接结果完整物化下来，代价是巨大的磁盘/内存占用与写入开销。\n",
    "\n",
    "设 $OUT$ = 完整连接结果行数，$C$ = 执行一次完整连接的代价，$k$ = 关系数：\n",
    "\n",
    "$$\\text{动态方法} \\approx k \\cdot C, \\qquad \\text{物化方法} \\approx C + Write(OUT) + k \\cdot Read(OUT)$$\n",
    "\n",
    "**物化方法更差的条件**（满足其一即可）：\n",
    "\n",
    "1. $OUT$ 很大，$Write(OUT) + k \\cdot Read(OUT)$ 超过 $(k-1) \\cdot C$——高扇出连接时必然发生；\n",
    "2. $OUT$ 放不下内存，必须落盘甚至溢写，I/O 代价急剧上升；\n",
    "3. $k$ 很小（例如 $k = 2$）：动态方法只多算 1 次，物化却要多付一整轮写入与读出；\n",
    "4. $C$ 本身很便宜（各关系很小、有索引可用）。\n",
    "\n",
    "**本笔记本的数据下 $OUT = 2$、$k = 3$**，两种方法都很快，看不出差别。要在真实规模上观察，需自行构造高扇出数据集实测。\n",
    "\n",
    "一句话概括两者的取舍：**物化方法用\"一次性的物化开销\"换取\"避免 $k$ 次重复计算\"。**\n"
   ],
   "id": "75c246d5"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Native Algorithm to Compute a Result Subdatabase\n",
    "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.\n",
    "\n",
    "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).\n",
    " 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.\n",
    "\n",
    "```\n",
    "1. Choose an arbitrary node in the join graph as root.\n",
    "2. Perform bottom-up semi-joins from leaves to root. Perform top-down semi-joins from root to leaves.\n",
    "3. Compute the final join result by joining the reduced relations.\n",
    "```"
   ],
   "id": "26e4a0567db993ca"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Yannakakis 算法：三步，以及\"为什么要两遍\"\n",
    "\n",
    "Yannakakis 算法出自 Yannakakis, *Algorithms for Acyclic Database Schemes*, VLDB 1981（pp. 82–94），用于求解**无环**的连接查询。三步：\n",
    "\n",
    "```text\n",
    "1. 任选连接图中的一个节点作为根（root）。\n",
    "2. 自底向上做半连接归约（叶 → 根）；再自顶向下做半连接归约（根 → 叶）。\n",
    "3. 用归约后的关系做最终连接。\n",
    "```\n",
    "\n",
    "以 `orders` 为根，图示如下：\n",
    "\n",
    "```text\n",
    "   第 1 步：定根\n",
    "         persons ───── orders ───── books\n",
    "           (0)         (1)★         (2)\n",
    "                      root\n",
    "\n",
    "   第 2a 步：自底向上（叶 → 根）\n",
    "         persons ───── orders ←──── books\n",
    "                      (1)⋉(2)\n",
    "         persons ───── orders\n",
    "           (0)  ──►  (1)⋉(0)\n",
    "\n",
    "   第 2b 步：自顶向下（根 → 叶）\n",
    "         persons ←──── orders\n",
    "           (0)⋉(1)\n",
    "         persons ───── orders ────► books\n",
    "                                  (2)⋉(1)\n",
    "```\n",
    "\n",
    "**为什么必须做两遍？** 两个原因，缺一不可：\n",
    "\n",
    "1. **每一遍只归约\"箭头头部\"那一侧的关系**。半连接 $R_a \\ltimes R_b$ 只改变 $R_a$。以 `orders` 为根，自底向上只改写 `orders`，`persons` 与 `books` 一行都没动；自顶向下只改写 `persons` 与 `books`，`orders` 一行没动。所以只做一遍，必然有关系的元组从未被检查过。\n",
    "2. **归约会制造新的悬挂元组**（更本质）。一条 `persons` 元组在自顶向下时用的是**未归约的** `orders`，找到了匹配被保留；但自底向上已经把 `orders` 归约掉了，它的配对可能已经被删——于是它**变成了新的悬挂元组**。这种效应只有在信息从根传回叶（自顶向下）时才能被发现，而自顶向下又必须在自底向上之后执行。\n",
    "\n",
    "**根的选择**：任选一个节点即可，**正确性不受影响**（无环条件下两遍归约的结果与根无关，本笔记本后面可以换根验证）。但归约的**中间结果大小**与顺序有关，实际系统会估算代价来选根。\n",
    "\n",
    "**从 Yannakakis 到结果子数据库**：只要前两步，做完两遍归约后**直接返回归约后的各关系**，不做第 3 步的最终连接。\n"
   ],
   "id": "40ecb701"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 1：两个原语——`filter()` 与 `semi_join()`\n",
    "\n",
    "```python\n",
    "def semi_join(left_relation, right_relation, left_attribute, right_attribute):\n",
    "    ht = set()\n",
    "    for tup in right_relation:          # 建阶段：只对右关系的连接键建集合\n",
    "        ht.add(tup[right_attribute])\n",
    "    result = []\n",
    "    for tup in left_relation:           # 探阶段：每个左元组最多 append 一次\n",
    "        if tup[left_attribute] in ht:\n",
    "            result.append(tup)\n",
    "    return result\n",
    "```\n",
    "\n",
    "两个易错点：\n",
    "\n",
    "- **`ht` 里存的是连接键的集合，不是整条元组**——这是半连接比连接省空间的直接原因。\n",
    "- **探阶段对每个 `t` 最多 `append` 一次**。如果写成嵌套循环（对每个匹配都 `append`），那就变成连接了，结果会出现重复元组。\n",
    "\n",
    "`filter()` 用字符串谓词 + `eval()` 实现（`eval(pred, {}, tup)`，变量即属性名），教学上方便；工程代码不要用 `eval()` 处理不可信输入。\n"
   ],
   "id": "629353be"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.433158Z",
     "start_time": "2025-01-06T20:49:06.428639Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def filter(relation: list[dict], pred: str) -> list[dict]:\n",
    "    \"\"\"Filter the given `relation` based on the predicate `pred`.\n",
    "    :param relation: The relation to filter.\n",
    "    :param pred: The predicate.\n",
    "    :return: A list of tuples representing the filtered relation.\n",
    "    \"\"\"\n",
    "    result: list[dict] = []\n",
    "    for tup in relation:\n",
    "        if eval(pred, {}, tup):\n",
    "            result.append(tup)\n",
    "    return result\n",
    "\n",
    "\n",
    "def semi_join(\n",
    "    left_relation: list[dict],\n",
    "    right_relation: list[dict],\n",
    "    left_attribute: str,\n",
    "    right_attribute: str,\n",
    ") -> list[dict]:\n",
    "    \"\"\"Compute the left semi-join between the given relations, i.e., filter `left_relation` based on the join results with `right_relation`.\n",
    "    :param left_relation: The relation to filter.\n",
    "    :param right_relation: The relation on which `left_relation` gets filtered.\n",
    "    :param left_attribute: The attribute of the left relation on which to filter.\n",
    "    :param right_attribute: The attribute of the right relation on which to filter.\n",
    "    :return: A list of tuples representing the filtered left relation.\n",
    "    \"\"\"\n",
    "    result: list[dict] = []\n",
    "    # build hashtable\n",
    "    ht = set()\n",
    "    for tup in right_relation:\n",
    "        ht.add(tup[right_attribute])\n",
    "    # probe hashtable\n",
    "    for tup in left_relation:\n",
    "        if tup[left_attribute] in ht:\n",
    "            result.append(tup)\n",
    "    return result"
   ],
   "id": "ab8080b72a7af773",
   "outputs": [],
   "execution_count": 8
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 2：把查询结构记下来——连接图与两个方向的连接属性\n",
    "\n",
    "```python\n",
    "join_graph.add_join(0, 1)     # persons — orders\n",
    "join_graph.add_join(1, 2)     # orders  — books\n",
    "```\n",
    "\n",
    "`create_join_graph()` 返回三样东西：\n",
    "\n",
    "| 变量 | 内容 |\n",
    "|---|---|\n",
    "| `join_graph` | 无向连接图：节点 0/1/2 分别是 persons / orders / books |\n",
    "| `id_to_relation` | `{id: (关系名, 元组列表)}`；注意 `books` 在这里**已经**被 `price < 10` 过滤（谓词下推） |\n",
    "| `ids_to_join` | `{(左id, 右id): (左属性, 右属性)}` |\n",
    "\n",
    "**为什么 `ids_to_join` 要把两个方向都写进去**：归约的方向会被反转（自顶向下用 `(子, 父)`），查表时键必须存在。漏写一个方向就会 `KeyError`。\n",
    "\n",
    "**为什么 `books` 要先过滤**：`price < 10` 是单表谓词，越早执行越好。如果留到归约之后再过滤，前面所有半连接都白做一些元组。\n"
   ],
   "id": "1941cff4"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.454844Z",
     "start_time": "2025-01-06T20:49:06.433985Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from system.query_optimization.join_graph import JoinGraph\n",
    "\n",
    "\n",
    "def create_join_graph():\n",
    "    \"\"\"Create the join graph and necessary helper data structures for the running example.\n",
    "    :return: The join graph, a mapping of relation id to relation name and tuples, and a mapping of relation ids to join attributes.\n",
    "    \"\"\"\n",
    "    # create join graph\n",
    "    join_graph = JoinGraph(3)\n",
    "\n",
    "    # add relations\n",
    "    persons_tuples = [vars(e) for e in persons]\n",
    "    orders_tuples = [vars(e) for e in orders]\n",
    "    books_tuples = [vars(e) for e in books]\n",
    "    id_to_relation = {\n",
    "        0: (\"persons\", persons_tuples),\n",
    "        1: (\"orders\", orders_tuples),\n",
    "        2: (\"books\", filter(books_tuples, \"price < 10\")),\n",
    "    }\n",
    "\n",
    "    # add joins\n",
    "    join_graph.add_join(0, 1)\n",
    "    join_graph.add_join(1, 2)\n",
    "    ids_to_join = {\n",
    "        (0, 1): (\"name\", \"person_name\"),\n",
    "        (1, 0): (\"person_name\", \"name\"),\n",
    "        (1, 2): (\"book_title\", \"title\"),\n",
    "        (2, 1): (\"title\", \"book_title\"),\n",
    "    }\n",
    "\n",
    "    return join_graph, id_to_relation, ids_to_join"
   ],
   "id": "eda68289d3e42df0",
   "outputs": [],
   "execution_count": 9
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 3：用 BFS 决定半连接的执行顺序\n",
    "\n",
    "从根出发做**广度优先搜索（BFS）**，每遇到一条未访问的边就记下一个二元组 `(父, 子)`。\n",
    "\n",
    "**语义**：`(a, b)` 表示\"用 $R_b$ 去归约 $R_a$\"，即执行 $R_a \\ltimes R_b$。\n",
    "\n",
    "- `reversed(order)` 就是**自底向上**（叶 → 根）；\n",
    "- 反过来用（把 `(父, 子)` 换成 `(子, 父)`）就是**自顶向下**（根 → 叶）。\n",
    "\n",
    "**预期看到什么**（本笔记本已打印）：\n",
    "\n",
    "```text\n",
    "以 persons 为根: [(0, 1), (1, 2)]\n",
    "以 orders  为根: [(1, 0), (1, 2)]\n",
    "以 books   为根: [(2, 1), (1, 0)]\n",
    "```\n",
    "\n",
    "三个顺序不同，但**归约完的最终结果相同**。\n"
   ],
   "id": "6d91b9bc"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.477323Z",
     "start_time": "2025-01-06T20:49:06.455636Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from system.query_optimization.problems import Problem\n",
    "\n",
    "\n",
    "def compute_semi_join_order(join_graph: JoinGraph, root: int) -> list[tuple]:\n",
    "    \"\"\"Compute the semi join reduction order starting from the root.\n",
    "    :param join_graph: The join graph representing the joins.\n",
    "    :param root: The root node.\n",
    "    :return: A list of tuples containing the relation ids in the order in which the semi-joins are to be executed.\n",
    "    \"\"\"\n",
    "    # Compute BFS ordering starting at the root node\n",
    "    semi_join_order: list[tuple] = []\n",
    "    visited = set()\n",
    "    Q = queue.Queue(len(join_graph))\n",
    "    Q.put(root)\n",
    "\n",
    "    while not Q.empty():\n",
    "        x = Q.get()\n",
    "        visited.add(x)\n",
    "        neighbors = join_graph.get_neighbors(\n",
    "            Problem.get_problem_for_relation(x, len(join_graph))\n",
    "        ).as_set()\n",
    "        for n in neighbors:\n",
    "            if n in visited:\n",
    "                continue\n",
    "            semi_join_order.append((x, n))\n",
    "            Q.put(n)\n",
    "\n",
    "    return semi_join_order\n",
    "\n",
    "\n",
    "join_graph, _, _ = create_join_graph()\n",
    "print(\n",
    "    \"Order of semi-joins with `persons` as root: \",\n",
    "    compute_semi_join_order(join_graph, 0),\n",
    ")\n",
    "print(\n",
    "    \"Order of semi-joins with `orders` as root: \",\n",
    "    compute_semi_join_order(join_graph, 1),\n",
    ")\n",
    "print(\n",
    "    \"Order of semi-joins with `books` as root: \", compute_semi_join_order(join_graph, 2)\n",
    ")"
   ],
   "id": "5a34e45c1f15ad7b",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Order of semi-joins with `persons` as root:  [(0, 1), (1, 2)]\n",
      "Order of semi-joins with `orders` as root:  [(1, 0), (1, 2)]\n",
      "Order of semi-joins with `books` as root:  [(2, 1), (1, 0)]\n"
     ]
    }
   ],
   "execution_count": 10
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 4：两遍归约，以及\"只做一遍会漏掉什么\"\n",
    "\n",
    "`reduction()` 里的两个循环：\n",
    "\n",
    "```python\n",
    "for left_rel_id, right_rel_id in reversed(semi_join_order):   # 自底向上\n",
    "    ...\n",
    "for (right_rel_id, left_rel_id) in semi_join_order:           # 自顶向下（方向反转）\n",
    "    ...\n",
    "```\n",
    "\n",
    "注意第二个循环的写法：它把 `semi_join_order` 里的 `(父, 子)` **按反序解包**成 `(right, left)`，于是被归约的一方变成了子（叶）那一侧。**写错方向是这里最常见的 bug**：结果是某些关系一条都没变小，或者 `KeyError`。\n",
    "\n",
    "**预期看到什么**（本笔记本的 faker 数据，3 人 / 3 书）：归约后 persons 2 条、orders 2 条、books 1 条（`books` 里只剩 `price < 10` 且被订单引用的那一本）。\n",
    "\n",
    "**只做一遍的对照**（配套实验指导书手写数据集上的实测，原始关系：persons 4 / orders 4 / books 3，books 已按 `price < 10` 过滤）：\n",
    "\n",
    "| 遍数 | persons 剩余 | orders 剩余 | books 剩余 | 说明 |\n",
    "|---|---:|---:|---:|---|\n",
    "| 0 遍（原始） | 4 | 4 | 3 | books 已过滤 |\n",
    "| 只自底向上 | **4** | **3** | **3** | 只有 `orders` 变小；`Dave`、`Bob`、`CG101` 全都还在 |\n",
    "| 只自顶向下 | **3** | **4** | **2** | `persons`、`books` 变小，但 `Bob` 还在（用的是未归约的 orders）；`orders` 没被动过 |\n",
    "| 两遍（完整） | **2** | **3** | **2** | 三个关系全部归约到位 |\n",
    "\n",
    "**一句话总结**：每一遍只归约箭头头部那一侧的关系。两遍合起来才能覆盖所有关系，并揪出\"因别人被删而新产生的悬挂元组\"。\n",
    "\n",
    "> 本笔记本用的是 faker 生成的数据，具体条数与上表不同，但\"只做一遍必然漏删\"的结论完全一致。\n"
   ],
   "id": "56d40736"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.495492Z",
     "start_time": "2025-01-06T20:49:06.477987Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def semi_join_reduction(\n",
    "    semi_join_order: list[tuple],\n",
    "    id_to_relation: dict[int, tuple],\n",
    "    ids_to_join: dict[tuple, tuple],\n",
    ") -> None:\n",
    "    \"\"\"Perform the semi-joins based on the given order. The reduced relations are stored in `id_to_relation`.\n",
    "    :param semi_join_order: The semi-join reduction order.\n",
    "    :param id_to_relation: A dictionary mapping each relation id to a tuple containing the relation name and the corresponding tuples.\n",
    "    :param ids_to_join: A dictionary mapping a tuple of relation ids representing a join to the corresponding attributes.\n",
    "    \"\"\"\n",
    "    # bottom-up pass\n",
    "    for left_rel_id, right_rel_id in reversed(semi_join_order):\n",
    "        left_relation_name, left_relation_tuples = id_to_relation[left_rel_id]\n",
    "        _, right_relation_tuples = id_to_relation[right_rel_id]\n",
    "        join_attributes = ids_to_join[(left_rel_id, right_rel_id)]\n",
    "        semi_join_result = semi_join(\n",
    "            left_relation_tuples, right_relation_tuples, *join_attributes\n",
    "        )\n",
    "        id_to_relation[left_rel_id] = (\n",
    "            left_relation_name,\n",
    "            semi_join_result,\n",
    "        )  # replace left relation with filtered result\n",
    "\n",
    "    # top-down pass\n",
    "    for (\n",
    "        right_rel_id,\n",
    "        left_rel_id,\n",
    "    ) in semi_join_order:  # switch left and right to ensure correct semi-join direction\n",
    "        left_relation_name, left_relation_tuples = id_to_relation[left_rel_id]\n",
    "        _, right_relation_tuples = id_to_relation[right_rel_id]\n",
    "        join_attributes = ids_to_join[(left_rel_id, right_rel_id)]\n",
    "        semi_join_result = semi_join(\n",
    "            left_relation_tuples, right_relation_tuples, *join_attributes\n",
    "        )\n",
    "        id_to_relation[left_rel_id] = (\n",
    "            left_relation_name,\n",
    "            semi_join_result,\n",
    "        )  # replace left relation with filtered result\n",
    "\n",
    "\n",
    "join_graph, id_to_relation, ids_to_join = create_join_graph()\n",
    "\n",
    "print(\"State of relations before the semi-join reduction:\")\n",
    "display(id_to_relation)\n",
    "\n",
    "print(\"State of relations after the semi-join reduction:\")\n",
    "semi_join_reduction(compute_semi_join_order(join_graph, 0), id_to_relation, ids_to_join)\n",
    "display(id_to_relation)"
   ],
   "id": "84581086f3e10b05",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "State of relations before the semi-join reduction:\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{0: ('persons',\n",
       "  [{'name': 'Alexandra Fitzgerald', 'birthday': '1978-09-11'},\n",
       "   {'name': 'Mrs. Sherry Maldonado', 'birthday': '2017-03-03'},\n",
       "   {'name': 'Mrs. Gina Erickson MD', 'birthday': '1984-06-27'}]),\n",
       " 1: ('orders',\n",
       "  [{'person_name': 'Alexandra Fitzgerald',\n",
       "    'book_title': 'Leave sometimes keep firm.'},\n",
       "   {'person_name': 'Mrs. Gina Erickson MD',\n",
       "    'book_title': 'Leave sometimes keep firm.'},\n",
       "   {'person_name': 'Mrs. Sherry Maldonado',\n",
       "    'book_title': 'Various deal great finish figure.'},\n",
       "   {'person_name': 'Mrs. Sherry Maldonado',\n",
       "    'book_title': 'Cultural move pass.'},\n",
       "   {'person_name': 'Alexandra Fitzgerald',\n",
       "    'book_title': 'Cultural move pass.'}]),\n",
       " 2: ('books',\n",
       "  [{'title': 'Leave sometimes keep firm.',\n",
       "    'author': 'Joanne Frank',\n",
       "    'price': 8.62}])}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "State of relations after the semi-join reduction:\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{0: ('persons',\n",
       "  [{'name': 'Alexandra Fitzgerald', 'birthday': '1978-09-11'},\n",
       "   {'name': 'Mrs. Gina Erickson MD', 'birthday': '1984-06-27'}]),\n",
       " 1: ('orders',\n",
       "  [{'person_name': 'Alexandra Fitzgerald',\n",
       "    'book_title': 'Leave sometimes keep firm.'},\n",
       "   {'person_name': 'Mrs. Gina Erickson MD',\n",
       "    'book_title': 'Leave sometimes keep firm.'}]),\n",
       " 2: ('books',\n",
       "  [{'title': 'Leave sometimes keep firm.',\n",
       "    'author': 'Joanne Frank',\n",
       "    'price': 8.62}])}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 11
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 5：完整的 Yannakakis——加上第 3 步的最终连接\n",
    "\n",
    "`yannakakis()` 比 `resultDB()` 多了第 3 步：用归约后的三个关系构造查询计划并执行，得到**传统意义上的完整连接结果**。\n",
    "\n",
    "**预期看到什么**：本笔记本的数据下得到 **2 行**（即两个\"人—订单—书\"的完整配对）。\n",
    "\n",
    "这 2 行就是\"标准答案\"。可以拿它做**差异测试（differential testing）**：\n",
    "\n",
    "1. 直接用原关系做完整连接；\n",
    "2. 先做两遍半连接归约，再连接；\n",
    "\n",
    "两条路径的结果必须完全一致。这正是\"结果子数据库\"的定义所保证的：$R_1' \\bowtie \\dots \\bowtie R_k' = R_1 \\bowtie \\dots \\bowtie R_k$。\n",
    "\n",
    "注意这里 `root` 是用 `random.seed(42)` + `random.choice()` 随机选的——**故意的**：它演示\"任选根都不影响正确性\"。\n"
   ],
   "id": "f35cc2d8"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.511509Z",
     "start_time": "2025-01-06T20:49:06.496228Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from system.query_processing.operators import Collect\n",
    "\n",
    "\n",
    "def yannakakis(\n",
    "    join_graph: JoinGraph,\n",
    "    id_to_relation: dict[int, tuple],\n",
    "    ids_to_join: dict[tuple, tuple],\n",
    ") -> list[tuple]:\n",
    "    \"\"\"Perform Yannakakis algorithm. The third and last step of this algorithm, as outlined above, joins the reduced relations to obtain the traditional result.\n",
    "       Since we want to compute the result for our example query, we specifically construct the corresponding query execution plan in step three.\n",
    "       Note, that normally the query optimizer would decide on the best join order which would then be executed by the query execution engine.\n",
    "    :param join_graph: The join graph.\n",
    "    :param id_to_relation: A dictionary mapping each relation id to a tuple containing the relation name and the corresponding tuples.\n",
    "    :param ids_to_join: A dictionary mapping a tuple of relation ids representing a join to the corresponding attributes.\n",
    "    \"\"\"\n",
    "    # 1. Choose arbitrary root node\n",
    "    random.seed(42)\n",
    "    root = random.choice(list(id_to_relation.keys()))\n",
    "\n",
    "    # 2. Perform semi-joins\n",
    "    semi_join_order = compute_semi_join_order(join_graph, root)\n",
    "    semi_join_reduction(semi_join_order, id_to_relation, ids_to_join)\n",
    "\n",
    "    # 3. Perform joins to obtain a\n",
    "    persons_reduced = Relation(*id_to_relation[0])\n",
    "    orders_reduced = Relation(*id_to_relation[1])\n",
    "    books_reduced = Relation(\n",
    "        *id_to_relation[2]\n",
    "    )  # note that the filter on books was already applied\n",
    "    join_orders_books = SHJ(orders_reduced, books_reduced, *ids_to_join[(1, 2)])\n",
    "    join_persons_orders_books = SHJ(\n",
    "        persons_reduced, join_orders_books, *ids_to_join[(0, 1)]\n",
    "    )\n",
    "    query_plan = Collect(join_persons_orders_books)\n",
    "    query_plan.interpret_open()\n",
    "\n",
    "    return query_plan.result\n",
    "\n",
    "\n",
    "join_graph, id_to_relation, ids_to_join = create_join_graph()\n",
    "result = yannakakis(join_graph, id_to_relation, ids_to_join)\n",
    "display(result)"
   ],
   "id": "d002e03c27cc0349",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('Leave sometimes keep firm.',\n",
       "  'Joanne Frank',\n",
       "  8.62,\n",
       "  'Alexandra Fitzgerald',\n",
       "  'Leave sometimes keep firm.',\n",
       "  'Alexandra Fitzgerald',\n",
       "  '1978-09-11'),\n",
       " ('Leave sometimes keep firm.',\n",
       "  'Joanne Frank',\n",
       "  8.62,\n",
       "  'Mrs. Gina Erickson MD',\n",
       "  'Leave sometimes keep firm.',\n",
       "  'Mrs. Gina Erickson MD',\n",
       "  '1984-06-27')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 12
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 步骤 6：`resultDB()`——只取前两步\n",
    "\n",
    "```python\n",
    "def resultDB(join_graph, id_to_relation, ids_to_join):\n",
    "    root = random.choice(list(id_to_relation.keys()))   # 1. 任选根\n",
    "    semi_join_order = compute_semi_join_order(join_graph, root)\n",
    "    semi_join_reduction(semi_join_order, id_to_relation, ids_to_join)   # 2. 两遍归约\n",
    "    return id_to_relation                                # 3. 不做最终连接，直接返回\n",
    "```\n",
    "\n",
    "**预期看到什么**：一个字典，三个关系各自只剩\"参与连接\"的元组——这就是**结果子数据库**。把它与步骤 5 的完整连接结果对照：完整连接是 2 行宽表，子数据库是\"2 个人 + 2 条订单 + 1 本书\"。\n",
    "\n",
    "**这就是本实验的落点**：同样的查询语义，一种表示会放大（每个客户的订单数倍），另一种不会。\n"
   ],
   "id": "fba52629"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.531593Z",
     "start_time": "2025-01-06T20:49:06.512404Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# The implementation just uses the first two steps of the Yannakakis algorithm\n",
    "def resultDB(\n",
    "    join_graph: JoinGraph,\n",
    "    id_to_relation: dict[int, tuple],\n",
    "    ids_to_join: dict[tuple, tuple],\n",
    ") -> dict[int, tuple]:\n",
    "    \"\"\"Compute a result subdatabase.\n",
    "    :param join_graph: The join graph.\n",
    "    :param id_to_relation: A dictionary mapping each relation id to a tuple containing the relation name and the corresponding tuples.\n",
    "    :param ids_to_join: A dictionary mapping a tuple of relation ids representing a join to the corresponding attributes.\n",
    "    :return: A dictionary mapping each relation id to a tuple containing the relation name and the reduced tuples.\n",
    "    \"\"\"\n",
    "    # 1. Choose arbitrary root node\n",
    "    random.seed(42)\n",
    "    root = random.choice(list(id_to_relation.keys()))\n",
    "\n",
    "    # 2. Perform semi-joins\n",
    "    semi_join_order = compute_semi_join_order(join_graph, root)\n",
    "    semi_join_reduction(semi_join_order, id_to_relation, ids_to_join)\n",
    "\n",
    "    return id_to_relation\n",
    "\n",
    "\n",
    "join_graph, id_to_relation, ids_to_join = create_join_graph()\n",
    "result = resultDB(join_graph, id_to_relation, ids_to_join)\n",
    "display(result)"
   ],
   "id": "d0fbc7e03adc1924",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: ('persons',\n",
       "  [{'name': 'Alexandra Fitzgerald', 'birthday': '1978-09-11'},\n",
       "   {'name': 'Mrs. Gina Erickson MD', 'birthday': '1984-06-27'}]),\n",
       " 1: ('orders',\n",
       "  [{'person_name': 'Alexandra Fitzgerald',\n",
       "    'book_title': 'Leave sometimes keep firm.'},\n",
       "   {'person_name': 'Mrs. Gina Erickson MD',\n",
       "    'book_title': 'Leave sometimes keep firm.'}]),\n",
       " 2: ('books',\n",
       "  [{'title': 'Leave sometimes keep firm.',\n",
       "    'author': 'Joanne Frank',\n",
       "    'price': 8.62}])}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "execution_count": 13
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## Unit Tests",
   "id": "30c4b12cf1a6fa7e"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单元测试：这份实现在验什么\n",
    "\n",
    "最后一格用 `unittest` 跑了 4 个测试，分别覆盖：\n",
    "\n",
    "| 测试 | 验证什么 |\n",
    "|---|---|\n",
    "| `test_filter` | 字符串谓词过滤是否正确 |\n",
    "| `test_semi_join` | 半连接是否**只保留左关系、不复制**（`books ⋉ orders` 应返回在 orders 中出现过的 3 本书） |\n",
    "| `test_compute_semi_join_order` | 星型连接图（4 个节点、0 为中心）下 BFS 顺序是否正确 |\n",
    "| `test_semi_join_reduction` | 两遍归约后的结果是否与预期一致 |\n",
    "\n",
    "**为什么要写这些测试**：半连接的实现里最容易犯的错是\"探阶段多 append 一次\"（变成连接）和\"归约方向写反\"。这两个 bug 都不会报错，只会**静默地给出偏大的结果**——只有对拍才能发现。\n",
    "\n",
    "**建议自己加一个**：换不同的根跑 `resultDB()`，断言结果相同（无环条件下必须成立）。\n"
   ],
   "id": "df6e88a1"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-01-06T20:49:06.558359Z",
     "start_time": "2025-01-06T20:49:06.533325Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import unittest\n",
    "\n",
    "\n",
    "class ResultDBTest(unittest.TestCase):\n",
    "    @staticmethod\n",
    "    def create_data():\n",
    "        persons = [\n",
    "            Person(\"John\", \"1992-17-03\"),\n",
    "            Person(\"Bob\", \"1987-08-05\"),\n",
    "            Person(\"Jane\", \"1968-12-12\"),\n",
    "        ]\n",
    "        orders = [\n",
    "            Order(\"John\", \"Echoes of Time\"),\n",
    "            Order(\"Jane\", \"Echoes of Time\"),\n",
    "            Order(\"Bob\", \"Shadows of Dawn\"),\n",
    "            Order(\"Bob\", \"Echoes of Time\"),\n",
    "            Order(\"John\", \"Shadows of Dawn\"),\n",
    "            Order(\"Jane\", \"Beneath the Stars\"),\n",
    "        ]\n",
    "        books = [\n",
    "            Book(\"Forgotten Dreams\", \"Alice\", 54.92),\n",
    "            Book(\"Echoes of Time\", \"Marie\", 44.09),\n",
    "            Book(\"Shadows of Dawn\", \"Alan\", 32.99),\n",
    "            Book(\"Beneath the Stars\", \"Ted\", 78.21),\n",
    "        ]\n",
    "        return (\n",
    "            [vars(e) for e in persons],\n",
    "            [vars(e) for e in orders],\n",
    "            [vars(e) for e in books],\n",
    "        )\n",
    "\n",
    "    def test_filter(self):\n",
    "        persons, _, _ = self.create_data()\n",
    "        filtered_persons = filter(persons, \"birthday < '1990-08-12'\")\n",
    "        result = [\n",
    "            {\"name\": \"Bob\", \"birthday\": \"1987-08-05\"},\n",
    "            {\"name\": \"Jane\", \"birthday\": \"1968-12-12\"},\n",
    "        ]\n",
    "        self.assertListEqual(filtered_persons, result)\n",
    "\n",
    "    def test_semi_join(self):\n",
    "        _, orders, books = self.create_data()\n",
    "        semi_join_result = semi_join(books, orders, \"title\", \"book_title\")\n",
    "        result = [\n",
    "            {\"title\": \"Echoes of Time\", \"author\": \"Marie\", \"price\": 44.09},\n",
    "            {\"title\": \"Shadows of Dawn\", \"author\": \"Alan\", \"price\": 32.99},\n",
    "            {\"title\": \"Beneath the Stars\", \"author\": \"Ted\", \"price\": 78.21},\n",
    "        ]\n",
    "        self.assertListEqual(semi_join_result, result)\n",
    "\n",
    "    def test_compute_semi_join_order(self):\n",
    "        join_graph = JoinGraph(4)\n",
    "        join_graph.add_join(0, 1)\n",
    "        join_graph.add_join(0, 2)\n",
    "        join_graph.add_join(0, 3)\n",
    "        semi_join_order = compute_semi_join_order(join_graph, 3)\n",
    "        result = [(3, 0), (0, 1), (0, 2)]\n",
    "        self.assertListEqual(semi_join_order, result)\n",
    "\n",
    "    def test_semi_join_reduction(self):\n",
    "        persons, orders, books = self.create_data()\n",
    "\n",
    "        # create join graph\n",
    "        join_graph = JoinGraph(3)\n",
    "        id_to_relation = {\n",
    "            0: (\"persons\", persons),\n",
    "            1: (\"orders\", orders),\n",
    "            2: (\"books\", filter(books, \"price < 50\")),\n",
    "        }\n",
    "\n",
    "        join_graph.add_join(0, 1)\n",
    "        join_graph.add_join(1, 2)\n",
    "        ids_to_join = {\n",
    "            (0, 1): (\"name\", \"person_name\"),\n",
    "            (1, 0): (\"person_name\", \"name\"),\n",
    "            (1, 2): (\"book_title\", \"title\"),\n",
    "            (2, 1): (\"title\", \"book_title\"),\n",
    "        }\n",
    "\n",
    "        # compute semi-join order\n",
    "        semi_join_order = compute_semi_join_order(join_graph, 0)\n",
    "\n",
    "        # execute semi-joins\n",
    "        semi_join_reduction(semi_join_order, id_to_relation, ids_to_join)\n",
    "\n",
    "        persons_expected = [\n",
    "            {\"name\": \"John\", \"birthday\": \"1992-17-03\"},\n",
    "            {\"name\": \"Bob\", \"birthday\": \"1987-08-05\"},\n",
    "            {\"name\": \"Jane\", \"birthday\": \"1968-12-12\"},\n",
    "        ]\n",
    "        orders_expected = [\n",
    "            {\"person_name\": \"John\", \"book_title\": \"Echoes of Time\"},\n",
    "            {\"person_name\": \"Jane\", \"book_title\": \"Echoes of Time\"},\n",
    "            {\"person_name\": \"Bob\", \"book_title\": \"Shadows of Dawn\"},\n",
    "            {\"person_name\": \"Bob\", \"book_title\": \"Echoes of Time\"},\n",
    "            {\"person_name\": \"John\", \"book_title\": \"Shadows of Dawn\"},\n",
    "        ]\n",
    "        books_expected = [\n",
    "            {\"title\": \"Echoes of Time\", \"author\": \"Marie\", \"price\": 44.09},\n",
    "            {\"title\": \"Shadows of Dawn\", \"author\": \"Alan\", \"price\": 32.99},\n",
    "        ]\n",
    "        persons_result = id_to_relation[0][1]\n",
    "        orders_result = id_to_relation[1][1]\n",
    "        books_result = id_to_relation[2][1]\n",
    "\n",
    "        self.assertListEqual(persons_expected, persons_result)\n",
    "        self.assertListEqual(orders_expected, orders_result)\n",
    "        self.assertListEqual(books_expected, books_result)\n",
    "\n",
    "\n",
    "# Run unit tests\n",
    "unittest.main(argv=[\"ignored\", \"-v\"], verbosity=2, exit=False)"
   ],
   "id": "eb1bda17f19460ec",
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_compute_semi_join_order (__main__.ResultDBTest.test_compute_semi_join_order) ... ok\n",
      "test_filter (__main__.ResultDBTest.test_filter) ... ok\n",
      "test_semi_join (__main__.ResultDBTest.test_semi_join) ... ok\n",
      "test_semi_join_reduction (__main__.ResultDBTest.test_semi_join_reduction) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 4 tests in 0.002s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7cd9b61ab470>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "execution_count": 14
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 思考题与详解\n",
    "\n",
    "> 建议先自己写一遍答案，再展开对照。\n",
    "\n",
    "**1. 半连接 $R \\ltimes S$ 与\"先做 $R \\bowtie S$、再对 $R$ 的列做投影去重\"，结果是否总是相同？给出理由或反例。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "**相同**（在等值连接条件下）。\n",
    "\n",
    "- 半连接：$R \\ltimes_{A=B} S = \\{\\,t \\in R \\mid \\exists s \\in S,\\ t[A] = s[B]\\,\\}$\n",
    "- 连接后投影去重：$\\pi_{R\\text{-cols}}(R \\bowtie_{A=B} S) = \\{\\,t \\mid \\exists s \\in S,\\ t[A] = s[B]\\,\\}$\n",
    "\n",
    "两者都收集\"在 $S$ 中至少有一个匹配的 $R$ 元组\"。连接后投影去重之所以丢掉了重复次数，正是因为它做了去重。所以二者是同一个集合。\n",
    "\n",
    "反例只可能出现在**非等值连接**或**投影列包含 $S$ 的列**时：此时右边的结果列数不同，集合自然也不同。\n",
    "\n",
    "这也正是\"动态 `SELECT DISTINCT persons.*`\"能等价于 `persons ⋉ (orders ⋈ books)` 的原因。\n",
    "\n",
    "</details>\n",
    "\n",
    "**2. 若某人有 100 个订单且都满足条件，完整连接结果会有多少行？结果子数据库里的 `persons` 部分有多少行？这说明结果子数据库省掉了什么？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "- 完整连接结果中这个人出现 **100 行**（每个订单一行）。\n",
    "- 结果子数据库里 `persons` 部分**只有 1 行**（就是这个人这一条）。\n",
    "\n",
    "**省掉的是连接的乘法效应**：完整连接结果的大小约等于各\"实体对\"匹配数的总和，在**高扇出（fan-out）**的实体上会被放大成百上千倍；结果子数据库只保存每个实体一次。\n",
    "\n",
    "本笔记本的数据下：完整连接 2 行，而结果子数据库是 2 个人 + 2 条订单 + 1 本书——`persons` 部分没有重复。\n",
    "\n",
    "</details>\n",
    "\n",
    "**3. 为什么 Yannakakis 算法要做两遍半连接归约？举一个\"只做自底向上会漏删\"的具体元组。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "两个原因：\n",
    "\n",
    "**（一）每一遍只归约箭头头部那一侧。** 半连接 $R_a \\ltimes R_b$ 只改变 $R_a$。以 `orders` 为根时顺序是 `[(1,0), (1,2)]`：\n",
    "\n",
    "- 自底向上用 `reversed`，按 `(1,2)`、`(1,0)` 执行，被改写的**只有 `orders`**；\n",
    "- 自顶向下按反方向 `(0,1)`、`(2,1)` 执行，被改写的是 `persons` 与 `books`。\n",
    "\n",
    "所以只做一遍，必然有关系的元组从未被检查过——配套指导书实测：只自底向上时 persons 仍为 4 条（`Dave`、`Bob` 都还在）。\n",
    "\n",
    "**（二）归约会制造新的悬挂元组**（更本质）。以 `persons` 里的 `Bob` 为例：\n",
    "\n",
    "- 自顶向下这一遍里，`persons ⋉ orders` 用的是**未归约的** orders（4 条，含 `(Bob, OS101)`），`Bob` 找到了匹配被保留；\n",
    "- 但自底向上已经把 orders 归约到 3 条，`(Bob, OS101)` 被删掉了（`OS101` 不满足 `price<10`）；\n",
    "- 于是 `Bob` 在归约后的 orders' 里已没有任何配对——它**变成了新的悬挂元组**。\n",
    "\n",
    "这种\"因为别人被删而导致自己变成悬挂\"的效应，只有信息从根传回叶时才能被发现；而自顶向下又必须在自底向上之后执行，否则它用的还是旧的 orders。\n",
    "\n",
    "</details>\n",
    "\n",
    "**4. 半连接 $R \\ltimes_{A=B} S$ 的时间复杂度是多少？哈希实现的空间复杂度是多少？与完整连接相比差别在哪？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "哈希实现的半连接：\n",
    "\n",
    "- 建阶段：扫一遍 $S$，把 $S[B]$ 的取值放进哈希集合，$O(|S|)$；\n",
    "- 探阶段：扫一遍 $R$，每个元组查一次集合，$O(|R|)$；\n",
    "- **时间复杂度 $O(|R| + |S|)$**；\n",
    "- **空间复杂度**等于 $S$ 在 $B$ 上不同取值的个数，最坏 $O(|S|)$。\n",
    "\n",
    "完整哈希连接：\n",
    "\n",
    "- 时间同样是 $O(|R| + |S|)$，但**要再乘一个输出因子**：每个匹配的 $(t,s)$ 都要物化一次，即 $O(|R| + |S| + OUT)$；\n",
    "- 空间：哈希表存的是 $S$ 的**整条元组**，不只是连接键，常数比只存键大得多。\n",
    "\n",
    "**核心差别**：半连接的输出不超过 $|R|$，且不复制；连接的输出可能远大于 $|R| + |S|$。这就是\"半连接便宜\"的全部理由。\n",
    "\n",
    "</details>\n",
    "\n",
    "**5. `SELECT DISTINCT` 里的 `DISTINCT` 能不能去掉？去掉之后会发生什么？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "**不能去掉。**\n",
    "\n",
    "`SELECT persons.* FROM persons JOIN orders ... JOIN books ...` 会为 `persons` 的每个匹配输出一行。某个人有 2 个匹配，就会输出 2 行同名的 persons 元组。\n",
    "\n",
    "结果子数据库的定义要求每个关系只保留\"参与连接的元组\"，是一个**集合（set）**，不是**多重集（multiset）**。不加 `DISTINCT` 得到的是多重集，与半连接语义不符。\n",
    "\n",
    "用 duckdb 可以一行验证（需自行实测确认）：\n",
    "\n",
    "```python\n",
    "print(con.execute(\"SELECT persons.* \" + body).fetchall())          # 同一人可能出现多次\n",
    "print(con.execute(\"SELECT DISTINCT persons.* \" + body).fetchall())  # 每人一次\n",
    "```\n",
    "\n",
    "</details>\n",
    "\n",
    "**6. 物化 `SELECT DISTINCT` 在什么情况下比动态 `SELECT DISTINCT` 更差？给出判断条件。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "设 $OUT$ = 完整连接结果的行数，$C$ = 执行一次完整连接的代价，$k$ = 参与连接的关系数。\n",
    "\n",
    "- 动态方法总代价 $\\approx k \\cdot C$；\n",
    "- 物化方法总代价 $\\approx C + Write(OUT) + k \\cdot Read(OUT)$。\n",
    "\n",
    "**物化更差的条件**（满足其一即可）：\n",
    "\n",
    "1. $OUT$ 很大，$Write(OUT) + k \\cdot Read(OUT) > (k-1) \\cdot C$。高扇出连接时必然发生。\n",
    "2. 磁盘/内存放不下 $OUT$，必须落盘甚至溢写，I/O 代价急剧上升。\n",
    "3. $k$ 很小（例如 $k = 2$）：动态方法只多算 1 次连接，而物化要多付一整轮写入与读出。\n",
    "4. $C$ 本身很便宜（各关系都很小、有索引可用）：重复计算本来就不高。\n",
    "\n",
    "本笔记本的数据下 $OUT = 2$、$k = 3$，两种方法都很快，看不出差别。要在真实规模上观察需自行构造高扇出数据集实测。\n",
    "\n",
    "</details>\n",
    "\n",
    "**7. Yannakakis 算法要求连接图无环。如果连接图有环（例如三角形），两遍归约还能保证删掉所有悬挂元组吗？举例说明。**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "**不能保证。**\n",
    "\n",
    "两遍归约的正确性依赖连接图的**树结构**：树上任意两节点之间路径唯一，自底向上把叶的信息汇聚到根，自顶向下再从根发散回叶，恰好覆盖每条边两个方向各一次，这就足以把\"某条元组在整棵树上还有没有完整配对\"这个全局条件传导到每个节点。\n",
    "\n",
    "有环时，一条元组是否悬挂取决于环上**所有边**的联合约束；沿着一棵生成树做两遍传递只能保证\"沿树边都有邻居\"，无法保证\"跨树边的那条边也有邻居\"。\n",
    "\n",
    "**具体例子**（三个关系构成三角形）：\n",
    "\n",
    "```python\n",
    "A = [{\"x\": 1, \"y\": 1}, {\"x\": 2, \"y\": 2}]\n",
    "B = [{\"y\": 1, \"z\": 1}, {\"y\": 2, \"z\": 2}]\n",
    "C = [{\"z\": 1, \"x\": 1}, {\"z\": 2, \"x\": 1}]   # C 中没有 (z=2, x=2)\n",
    "```\n",
    "\n",
    "完整连接只有 1 行（`x=1, y=1, z=1`），所以 `A` 中的 `{\"x\": 2, \"y\": 2}` 是悬挂元组。但以 `A` 为根对生成树 `A—B—C` 做两遍归约：\n",
    "\n",
    "- 自底向上：`C ⋉ B` 保留全部（两条都在 `B` 里有 `z` 匹配）；`B ⋉ A` 保留全部；\n",
    "- 自顶向下：`A ⋉ B'` 保留全部；`B ⋉ C'` 保留全部。\n",
    "\n",
    "`A` 的两条都留下了。原因是它是否悬挂取决于 `C` 里有没有 `(z=2, x=2)`，而这条约束对应的边 `C—A` 在生成树里被丢掉了。\n",
    "\n",
    "有环查询需要先用**树宽**相关的算法（GYO 归约、连接树构造）分解成无环结构，代价通常随环的数量指数增长。\n",
    "\n",
    "</details>\n",
    "\n",
    "**8. 本实验中\"选根\"不影响最终结果，那实际系统为什么还要挑根？挑根影响的是什么？**\n",
    "\n",
    "<details><summary>答案要点</summary>\n",
    "\n",
    "结果的**内容**与根无关（无环条件下的理论保证），但归约的**中间结果大小**和**执行顺序**与根有关。**挑根影响的是性能**：\n",
    "\n",
    "- 不同的根决定不同的 BFS 顺序，从而决定每个半连接\"什么时候执行、用哪个已归约的关系去归约\"；\n",
    "- 若先归约掉一个很大的关系，后续所有半连接的输入都会变小，总代价显著下降；\n",
    "- 反之，若先执行一个选择性很差的半连接（几乎不删元组），就白白付了一次扫描代价。\n",
    "\n",
    "**实际系统的做法**：枚举每个候选根，用基数估计估算每种顺序下各中间关系的大小，选代价最小的。这是查询优化器的标准职责之一。\n",
    "\n",
    "可以在本笔记本里把每步归约后的行数打印出来，换不同的根观察中间大小确实不同（需自行实测确认）。\n",
    "\n",
    "</details>\n",
    "\n"
   ],
   "id": "689ee617"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}