# DBMS Test 4 (4/1)

<style>
.markdown-body li + li
{
padding-top: 0 !important;
}
</style>

---

[TOC]

---

## 11. 關聯式代數與計算
### 關聯式代數的基礎
- E. F. Codd 提出兩種存取關聯式資料庫的基礎查詢語言
- 關聯式代數（Relational Algebra）：低階運算子導向語言（Operator-oriented Language）
- 使用關聯式運算子和關聯表建立的運算式進行資料操作或運算
- 關聯式計算（Relational Calculus）：高階宣告式語言（Declarative Language）
- 建立的運算式主要是在描述所需結果
- 關聯式代數運算子：
- 傳統集合論的運算子：
- $\cap$：交集（Intersection）
- $\cup$：聯集（Union）
- $-$：差集（Difference）
- $\times$：卡笛生乘積（Cartesian Production）
- 特殊關聯式運算子：
- $\sigma$：選取（Selection）==*（WTF 投影片後半一直用 $\delta$）*==
- $\pi$：投影（Projection）
- $\bowtie$：合併（Join）
- $\div$：除法（Division）
- 資料庫系統的查詢處理模組（Query Processor）：
- （SQL 指令敘述）$\rightarrow$【查詢處理模組】$\rightarrow$（關聯式代數）$\rightarrow$【執行查詢】

### 關聯式代數的基本運算
- 符號：
- $R,\ S$：關聯表（Relation）
- $P$：謂詞（Predicate）
- $t$：元組（Tuple）、值組、記錄
- $a,\ b$：屬性（Attribute）
- $\omega$：空值（Null）
- **選取（Selection）**：在關聯表選取指定條件的值組，預設包含所有屬性
- 單運算元（Unary）運算子
- 即：限制（Restriction）運算子、選擇運算子
- $$\sigma_P(R) = \{\ t \mid t \in R \land P(t)\ \}$$
- **投影（Projection）**：只取出部分關聯表的屬性，且刪除重複值組
- 單運算元（Unary）運算子
- $$\pi_{a_1,...,a_n}(R) = \{\ t[a_1,...,a_n] \mid t \in R\ \}$$
- **聯集（Union）**：將兩個關聯表的所有值組合併成一個關聯表，且刪除重複值組
- 二運算元（Binary）運算子
- 兩個關聯表的必須要有相同關聯表綱要：
- 擁有相同屬性個數，即相同維度
- 對應屬性必須擁有相同的定義域
- $$R \cup S = \{\ t \mid t \in R \lor t \in S\ \}$$
- **差集（Difference）**：值組只在第一個關聯表，而不在第二個關聯表
- 二運算元（Binary）運算子
- 兩個關聯表的必須要有相同關聯表綱要：
- 擁有相同屬性個數，即相同維度
- 對應屬性必須擁有相同的定義域
- $$R - S = \{\ t \mid t \in R \land t \notin S\ \}$$
- **卡笛生乘積（Cartesian Product）**：第一個關聯表值組結合第二個關聯表的所有值組
- 二運算元（Binary）運算子
- 即：交叉運算（`CROSS JOIN`）、廣義笛卡爾乘積
- $$\begin{aligned} R \times S = \{\ & (a_1,...,a_n,b_1,...,b_m)\ \\ & \mid (a_1,...,a_n)\in R \land (b_1,...,b_m)\in S\ \} \end{aligned}$$

### 關聯式代數的非基本運算
- **交集（Intersection）**：將兩個關聯表的相同值組取出成一個關聯表
- 二運算元（Binary）運算子
- 兩個關聯表的必須要有相同關聯表綱要：
- 擁有相同屬性個數，即相同維度
- 對應屬性必須擁有相同的定義域
- $$\begin{aligned} R \cap S & = \{\ t \mid t \in R \land t \in S\ \} \\ & = R - (R - S) \end{aligned}$$
- **合併（Join）**：在兩個關聯表使用相同定義域的屬性為條件合併兩個關聯表
- 二運算元（Binary）運算子
- 相當先執行卡笛生乘積運算，再配合選擇運算取出所需值組的關聯表
- **$\theta$ 合併（$\theta$ Join）**：使用比較運算子的謂詞
- 謂詞 $P := A\ \theta\ B$ 使用比較運算子 $\theta \in \{=,>,<,\ge,\le,\ne\}$
- $$R \bowtie_P S = \sigma_P(R \times S)$$
- **等位合併（Equijoin）**：使用相等運算子的謂詞
- 謂詞 $P := A = B$
- $$R \bowtie_{a=b} S = \sigma_{a=b}(R \times S)$$
- **自然合併（Natural Join）**：使用主鍵和外來鍵相等的謂詞，且刪除多餘鍵欄位
- 無謂詞表示預設使用主鍵和外來鍵對應的條件，即所有共通屬性值（All Common Attributes）都需要相等
- 共通屬性部分在運算結果中只會顯示一次
- （投影片後半使用自然合併時，常用 $∗$ 代替 $\bowtie$）
- $$R \bowtie S = \pi_{a \cup b}(R \bowtie_{a=b} S)$$
- **外部合併（Outer Join）**：使用關聯表主鍵和其關聯性（Relationship）關聯表的外來鍵為條件執行合併
- 是一種完全的值組合併，運算元的關聯表需要貢獻全部值組
- **左外部合併（Left Outer Join）**：取回左邊所有值組
- $$R \sideset{_{left}}{}\bowtie S = (R \bowtie S) \cup ((R - \pi_{a_1,...,a_n}(R \bowtie S)) \times \{\omega_1,...,\omega_m\})$$
- *(https://latex.org/forum/viewtopic.php?t=455/#p43968)*
- **右外部合併（Right Outer Join）**：取回右邊所有值組
- $$R \bowtie_{right} S = (R \bowtie S) \cup (\{\omega_1,...,\omega_n\} \times ((S - \pi_{b_1,...,b_m}(R \bowtie S)))$$
- **完全外部合併（Full Outer Join）**：取回兩邊的所有值組
- $$R \sideset{_{left}}{_{right}}\bowtie S = (R \sideset{_{left}}{}\bowtie S) \cup (R \bowtie_{right} S)$$
- **除法（Division）**：找出除關聯表在被除關聯表中的所有值組，且刪除多餘除關聯表欄位
- 二運算元（Binary）運算子
- $$A := \{a_1,...,a_n\} - \{b_1,...,b_m\} \\ R \div S = \pi_A(R) - \pi_A((\pi_A(R) \times S) - R)$$

### 關聯式代數運算式範例
==（全略）==

### 關聯式代數的資料庫更新運算
- 關聯式代數主要用途：
- 資料庫值組的增刪改等等
- 在資料庫定義視界（Views）、資料安全（所需保護資料）和完整性限制條件的範圍
- **指定運算子（Assignment Operator）**：在更新運算式中更改資料庫內容
- 可以將關連式代數的運算結果指定成一個暫存關聯表代數
- $$R \leftarrow S$$
- 新增運算範例
- 新增一筆值組：$R \leftarrow R \cup \{\ t\ \}$
- 新增多筆值組：$R \leftarrow R \cup S$
- 刪除運算範例
- 刪除符合條件之值組：$R \leftarrow R - \sigma_P(R)$
- 更新運算範例
- 更新一筆值組：$R \leftarrow R - (\sigma_P(R)) \cup \{\ t\ \}$

## 12. 關聯式代數範例
==（全略，部分合併至上面）==