關聯模型與關聯代數

從檔案到關聯模型

1970 年 E. F. Codd 在〈A Relational Model of Data for Large Shared Data Banks〉中提出： 應用程式不應該知道資料在機器內部怎麼排列。當時主流的階層式（IMS）與網狀式（CODASYL）資料庫， 程式必須沿著指標「導航」才能取得資料，一旦實體佈局改變，程式就得重寫。 Codd 的答案是把資料抽象成數學上的關聯（集合論中的 relation）， 讓使用者只描述「要什麼」，由系統決定「怎麼拿」——這個分離正是今天查詢最佳化器存在的理由。

關聯模型的基本元素

關聯、元組與屬性

• ：在數學上是若干定義域（domain）笛卡兒積的一個子集， \(r \subseteq D_1 \times D_2 \times \cdots \times D_n\)；在 SQL 中對應表（table）。

• ：關聯中的一個元素 \((v_1, \ldots, v_n)\)；對應列（row）。

• ：關聯綱要中的一個命名欄位及其定義域；對應欄（column）。

• ：\(R(A_1\!:\!D_1, \ldots, A_n\!:\!D_n)\)，是「型別」； 是某一時刻的實際內容，是「值」。

• ：屬性個數；：元組個數——後者是最佳化器估算成本的核心數字。

純數學的關聯是集合：沒有重複元組、沒有順序。SQL 的表則是多重集合（bag），允許重複、 且 不加 時順序未定義。這個差異在第 6 章討論等價規則時很重要： 集合代數的某些等價式在 bag 語意下並不成立。

鍵

• ：能唯一識別元組的屬性集合。

• ：極小的超鍵（拿掉任何屬性就不再唯一）。

• ：從候選鍵中選出的一個，作為預設識別方式；在實務上常是人工代理鍵（surrogate key，如 ）。

• ：關聯 \(R\) 的屬性集合，其值必須出現在關聯 \(S\) 的候選鍵中——這就是參照完整性。

完整性限制

CREATE TABLE departments (
  dept_id   SERIAL PRIMARY KEY,
  name      TEXT NOT NULL UNIQUE
);
CREATE TABLE employees (
  emp_id    BIGSERIAL PRIMARY KEY,
  name      TEXT NOT NULL,
  age       INT  CHECK (age BETWEEN 16 AND 100),
  salary    NUMERIC(12,2) NOT NULL,
  dept_id   INT  NOT NULL REFERENCES departments(dept_id) ON DELETE RESTRICT
);

函數相依與正規化

函數相依

屬性集合 \(X\) 函數決定 \(Y\)（記作 \(X \to Y\)），意思是：在任何合法實例中， 兩個元組若在 \(X\) 上相等，則在 \(Y\) 上也相等。候選鍵 \(K\) 的定義就是 \(K \to R\)（\(K\) 決定所有屬性）且極小。

Armstrong 公理（完備且正確）：

• 自反律（reflexivity）：若 \(Y \subseteq X\)，則 \(X \to Y\)。

• 增廣律（augmentation）：若 \(X \to Y\)，則 \(XZ \to YZ\)。

• 遞移律（transitivity）：若 \(X \to Y\) 且 \(Y \to Z\)，則 \(X \to Z\)。

屬性集合 \(X\) 的閉包 \(X^+\) 是由 \(F\) 推得、所有 \(X\) 能決定的屬性。計算閉包是判斷鍵與正規式的基本工具：

closure(X, F):
  result = X
  repeat
    for each (A -> B) in F:
      if A ⊆ result then result = result ∪ B
  until result 不再改變
  return result

正規式

正規化的目的，是消除因冗餘造成的更新異常（update / insertion / deletion anomaly）。

分解一個關聯 \(R\) 為 \(R_1, R_2\) 時要檢查兩件事：

1. 無損連接（lossless join）：\(R_1 \bowtie R_2 = R\)。充分條件：\((R_1 \cap R_2) \to R_1\) 或 \((R_1 \cap R_2) \to R_2\)。

2. 相依保持（dependency preserving）：原本的每個 FD 都能在單一分解後的表上檢查，不必 join。

關聯代數

關聯代數是一組以關聯為輸入、關聯為輸出的運算子。它是程序式的——運算的順序就是執行的順序—— 因此查詢最佳化器實際上就是在「同一個關聯代數表達式的所有等價寫法中，挑最便宜的那個」。

基本運算子

擴充運算子

• 外部連接：\(R \lojoin S\)（左）、\(R \rojoin S\)（右）、\(R \fojoin S\)（全），無配對的一側補 NULL。

• 半連接 \(R \sjoin S\)：保留 \(R\) 中「在 \(S\) 有配對」的元組（對應 ）； 反連接（anti-join）對應 。分散式查詢常用半連接減少資料搬移（第 14 章）。

• 分組與聚合 \(\gamma_{G;\,f(A)}(R)\)：對應 搭配 。

• 排序 \(\tau_{A}(R)\) 與 去重 \(\delta(R)\)：在 bag 代數中才需要。

• 賦值 \(T \leftarrow E\)：把子表達式存成暫存關聯，對應 CTE（）。

從 SQL 到關聯代數

SELECT e.name, d.name AS dept
FROM   employees e JOIN departments d ON e.dept_id = d.dept_id
WHERE  e.age > 30 AND d.name = 'Engineering';

直接翻譯（先積再選再投影）： \[\pi_{e.name,\, d.name}\Big(\sigma_{e.age>30 \,\wedge\, d.name='Engineering' \,\wedge\, e.dept\_id=d.dept\_id}(E \times D)\Big)\] 最佳化器會改寫成「先把選擇推到各表、再連接」的等價形式（述詞下推，第 6 章）： \[\pi_{e.name,\, d.name}\Big(\sigma_{age>30}(E) \;\bowtie_{dept\_id}\; \sigma_{name='Engineering'}(D)\Big)\] 兩者結果相同，但第二式在連接前就把 \(D\) 縮到可能只剩一列——這就是為什麼學好關聯代數對理解最佳化器至關重要。

常用等價規則（最佳化器的工具箱）

1. 選擇可拆分、可交換：\(\sigma_{p_1 \wedge p_2}(R) = \sigma_{p_1}(\sigma_{p_2}(R)) = \sigma_{p_2}(\sigma_{p_1}(R))\)。

2. 投影串接只留最外層：\(\pi_{A}(\pi_{B}(R)) = \pi_{A}(R)\)，若 \(A \subseteq B\)。

3. 選擇與連接交換（述詞只涉及一側時）：\(\sigma_{p_R}(R \bowtie S) = \sigma_{p_R}(R) \bowtie S\)。

4. 連接的交換律與結合律：\(R \bowtie S = S \bowtie R\)；\((R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)\) ——這讓 \(n\) 個表有 \(O(n!)\) 種以上的連接順序，是第 6 章「連接重排」的搜尋空間。

5. 投影下推：\(\pi_{A}(R \bowtie_{\theta} S) = \pi_{A}(\pi_{A_R \cup \theta_R}(R) \bowtie_{\theta} \pi_{A_S \cup \theta_S}(S))\)，提早丟掉不需要的欄位。

6. 外部連接不滿足一般的交換與結合律；選擇只有在「NULL 拒絕」（null-rejecting）述詞下才能推過外部連接。

關聯計算

關聯計算（relational calculus）是宣告式的：只描述結果元組必須滿足的條件。

• 元組關聯計算（TRC）：\(\{\, t \mid \exists e \in \mathit{Employees}\ (e.age > 30 \wedge t.name = e.name) \,\}\)。

• 定義域關聯計算（DRC）：變數代表屬性值而非元組：\(\{\, \langle n \rangle \mid \exists a, s, d\ (\langle \_, n, a, s, d\rangle \in \mathit{Employees} \wedge a > 30) \,\}\)。

Codd 定理：安全的（結果有限的）關聯計算與關聯代數表達能力相同。 SQL 在語法上更接近 TRC（ 就是 \(\exists\)）， 而資料庫內部先把 SQL 轉成關聯代數樹（邏輯計畫），再做最佳化——這正是第 5 章的起點。

SQL 的執行模型

雖然 寫在最前面，SQL 的邏輯處理順序其實是：

這解釋了幾個常見困惑：為什麼 不能用聚合函數（還沒分組）、 為什麼 的別名不能在 使用（還沒投影）， 以及為什麼 可以用別名（已經投影）。注意這只是邏輯順序； 實體執行順序由最佳化器決定，只要結果等價即可。

OLTP 與 OLAP

兩種工作負載對儲存引擎的要求幾乎相反：OLTP 需要快速找到並修改單一列（第 2–4 章）， OLAP 需要以最少 I/O 掃過單一欄位（第 13 章）。試圖同時服務兩者的系統稱為 HTAP（Hybrid Transactional/Analytical Processing），通常以「列式主儲存＋行式副本」實現（如 TiDB 的 TiFlash、SingleStore）。

SELECT c.relname, c.relkind, c.relpages, c.reltuples
FROM   pg_class c JOIN pg_namespace n ON n.oid = c.relnamespace
WHERE  n.nspname = 'public';