玩DB前必知的關聯式代數 Relational Algebra

關聯式代數是提供定義資料庫結構與查詢的表達方式。藉由理解關聯式代數，我們可以更快溝通、瞭解如何查詢，甚至進行優化。

Content

• 誰發明了 Relational Algebra?
• 透過範例理解 Relational Algebra
• 關聯式代數 Relational Algebra 特性

誰發明了 Relational Algebra?

Edgar F. Codd(1923–2003) 是英國電腦科學家，他在IBM工作期間發明了關聯式資料庫 (Relational Database)，與一套關聯式資料庫管理系統(RDBMS)，其中也包含了提出 Relational Algebra。

Source: Pinterest

Relational Algebra 主要應用在SQL查詢時，協助我們明確定義要進行query的資料結構。而Codd代數的基本運算包含：

1. 選擇 σ (Selection)
2. 投影 Π (Project)
3. 聯集 U (Union)
4. 差集－ (Difference)
5. 笛卡爾積 ×(Cartesian Product)

而我們所熟知的還有如
． 交集 ∩ (Intersection)
． 連接 ⋈ (Join)
． 除法 ÷ (Divide)
． 重命名 ρ (Rename)

舉例來說，SQL基本題目如
Q 獲得所有朋友或商業夥伴的地址清單

SELECT address
FROM   table
WHERE  isFriend = 'TRUE'
OR     isBusinessContact = 'TRUE'

用在關係代數就可以用下圖表示query

Edgar F. Codd? 以前上課有印象的名字…
Yes，在資料庫正規化中最嚴謹的形式，
Boyce-Codd 規範形式 (3NF加強版) 就是以他的名字命名。

透過範例理解 Relational Algebra

選擇 σ (Selection)

就是最簡單的 SQL 中的SELECT
其中可以夾帶任何的condition，是SQL中的 WHERE

σ (Cond)(Relation Name)

投影 Π (Project)

選出需要的欄位，或將欄位進行投影

∏(Column 1,Column 2….Column n)(Relation Name)

例如，從Books這個表格，投影出書名、價格：

或是將其中Ｂ欄位投影到Ｃ欄位，
通常Default的投影效果就會是移除重複項 (duplicate data)

聯集 U (Union)

資料聯集 或稱並集，就是將欄位上下進行拼接，
在不同的ETL或SQL工具中，也可能會使用其他別名。

兩張表必須欄位一致。

Relation1 U Relation2

例如我們將 STUDENT表 聯集 EMPLOYEE表 (STUDENT U EMPLOYEE)

差集－ (Difference or Minus)

就是將前表減去後表，若有前表有與後表相同的資料，就會移除。

兩張表必須欄位一致。

Relation1 - Relation2

例如我們將 STUDENT表 找與 EMPLOYEE表的差集
(STUDENT － EMPLOYEE)

笛卡爾積 × (Cartesian Product)

將所有表的欄位進行交叉配對。
每一個從表 A的 row，對到每一個表 B的 row。
若表 A有 3列資料，表 B有 5列資料，A X B就會有15列資料。

Relation1 X Relation2

例如我們將RAM與所有學生運動做笛卡爾積
σ (NAME = RAM)(STUDENT) X STUDENT_SPORTS

當然以上都是最入門的關聯式代數必須知道的，也是Codd最初提出的概念。
但我們都知道，實際用SQL的時候，也有JOIN阿，怎麼沒看到JOIN?

連接 (或稱 自然合併, Natural Join)

執行join 我們若沒有額外選擇欄位，被連接起來的欄位，
其選定為連接的欄位key必定會有相同的資料。

SQL中就像

SELECT *
FROM 雇員 a
JOIN 部門 b 
ON a.DeptName= b.DeptName

當然 JOIN我們還有很多不同變化，如left, right, full outer等等。

以及除法 ÷ (Divide)

要額外注意的是，除法事實上是非常耗時的運算方法!

反之我們更可以透過笛卡爾積回推

還有更多我們需要知道的嗎? Sure!

關聯式運算 Relational Algebra 特性

曾經玩過SQL的人都知道，要撈取正確的資料，不會只有一種方法，多的是透過不同的條件運算，進而query出正確的資料。

而不同的方法來query，就會遇到效能的問題。就如Oracle中可以透過Explain Plans來查看query中有那些object被使用，如何使用會以Cardinality 與Cost計算。

瞭解特性存在的目的，就是可以幫助我們轉換不同的query方法，進而找到定性最佳化查詢 (Qualitative Query Optimization)。

三大特性，結合、交換、分配律：

• 結合律 (Associativity)
  聯集、笛卡爾積、交集、連接基本上都符合結合律。
  但注意差集與除法不適用。

• 交換律 (Commutativity)
  如同數學中交換律，就是前後互換以後，仍能得出一樣的結果。
  回想基礎數學中，加法與乘法就符合此一特性。

• 分配律 (Distributivity)

其他最佳化小 Tips

• 二元運算(Binary Relational Operations)，
  如JOIN, Divide放越後面效能越好。
• 一元運算(Unary Relational Operations)，
  如Select, Project, Rename往前提效能越好。

Reference:
1. Wikipedia: Relational Algebra / 中文維基百科: 關係代數
2. Geeks for Geeks: Introduction of Relational Algebra in DBMS
3. Geeks for Geeks: Basic Operators in Relational Algebra
4. Guru99: Relational Algebra in DBMS: Operations with Examples

感謝閱讀至此，能夠看到這裡，

就是我寫文章最大的動力了 !

一起努力成為資料領域中的佼佼者吧 !