資料庫7個必學基礎知識
本篇將回顧進入資料庫領域前，必須要知道的基本常識。
Content
- History of Database
- The Big O notation
- B-Trees
- Database
- Database Design
- Normalization
- Relationships
1. History of Database
打從有了電腦出現於現代後，我們就開始有了資料庫。我們從石板、文本、計算機中，無不資料的存在，特別是在計算機大量普及以後，資料庫的應用更是所有Apps的開發根基，因為有了資料傳遞，才得以進行各種服務，如金融、運輸、國防、政治、醫療、百貨、汽車、工業等各種產業。
但資料庫概念，其實就是將資料給組織化，更可以溯及到古代石板的文字記載。
從古埃及時代來看當時就有了透過牆面紀載各種祭祀、人口、奴隸的紀載。
到了工業革命後，針對如汽車訂單更要透過文本記錄顧客、生廠零件、員工、廠房等各項資料進行紀錄。
近代則有了硬碟、軟體(如excel)，讓資料維護成為low-code, no-code應用。且人人都可以從資料中提煉價值、洞察，並加值到個人工作上。
而資料庫的演進更與資料結構、演算法緊密結合，從而發展出各大廠牌的資料庫開發工具。
進入到近代時，我們不免面對到計算機中運算的效能與效率。
其中用來解釋的就如經典的Big-O，也更必須知道資料如何被擺放的資料庫中(如b-tree結構)，並透過index查詢，了解DB有哪些種類，以及入門的設計邏輯。
2. The Big O notation
用以標註演算法的時間(time)或空間(space)複雜度，代表要運算的內容，隨著input size增長的速度。在此以時間複雜度來說：
O(1): 表示兩常數，只需要計算一次(只跑1次)
O(N): linear time，表示隨著帶入的資料大小(data size)，而線性拉長時間。(共跑n次)
O(N²): 而經典的nested loop就是Quadratic，因為每次帶入一個x值，就會跑所有y值。(共跑n * n = n²次)
而面對不同的問題，通常都不只一種解法，不同的解法也對應著不同的計算複雜度。
3. B-Trees
b-tree是一種自我平衡(self-balancing)的樹狀資料結構，用來把資料進行排序、搜尋、增刪修改的過程，轉換為logarithmic time。廣泛應用於資料庫與文件系統。
舉例來說，一個序列1~7的b-tree建構過程就如:
要如何找到數字7? 找尋的做法基本上就是比大小，
比對前一層數值，小放左邊，大放右邊。因只找到數字7，會經過4->6->7
我們稱這裡的Number of reads = 3。
就會比單純放成一排來搜尋要走過7個數值快 !
4. Database
而資料庫索引(index)本身就是一個b-tree結構的最佳範例，因為透過b-tree的儲存方式，我們進行搜尋資料的過程，只需要針對index進行搜尋，而不需要跑過每一個first name字元進行比對，在大型資料庫中，節省了大量的時間。
Types of Databases: Relational, NoSQL
Relational DB
關聯式資料庫(Relational DB)是目前最常見的資料庫類型，因為每一張表(table)都被其他表關聯起來(例如透過PK, FK)，而被稱為關聯式資料庫。
而把所有關聯的表(Tables)組合起來就是一個Schema，
在一個資料庫當中，可以包含多個Schema。
Rules of RMDBS
- 每一張table必須有unique name
- 每一張table包含多列資料(multiple rows)
- 每一筆資料(row)在table中是unique
- 每一張table有key可以識別rows並用來參照其他表
- 每一欄(attribute)名稱皆為unique
NoSQL = Not Only SQL
NoSQL資料庫則被廣泛應用於需要進行巨量資料即時應用的場景，
例如像facebook的post，twitter的個人頁面等，其背後都是以user個體為單位，直接獨立出來存放與user有關的各種資料。
5. Database Design
資料庫設計是規劃DB更詳細內容的過程，其過程有幾項要遵守的目標
- Database用來支撐基本軟體需求、特別用途或臨時(ad hoc)的資訊取得。
- Tables應該被適當(properly)且有效(efficiently)建構。
- Data Integrity 資料一致性，規範了每一欄(field)、表(table)、關聯層級。
- Database應該建立在business rules之上，並可以隨著規模成長，配合開發人員進行工作。
而是為了資料格式、資料本身可以容易調整與維運，開發人員與終端使用者(end-user)在操作Apps也可以更快取得應有資訊。
傳統上定義的步驟可能如：
但實際上就是(1)定義DB用途 (2)把需要的資訊蒐集起來 (3)拆分資訊到表中 (4) 定義key (5)建立表關聯 (6)進行正規化(normalization)
(7) 新需求進來，重新檢視設計(refine design)
三個層級的Database Design
如傳統定義，我們會有Step2 ~Step4的過程，稱之為data modeling。
以學校選課系統為例，
1. 最初只討論要有哪些資料，要怎分拆分到表中(Conceptual Design)，
2. 接著規劃每一張表應該要有那些資訊，並如何參照(Logical Design)，
3. 最後把完整資料、資料格式與其關聯方式繪製出來(Physical Design)。
6. Normalization
是database design的一種技術，目的是降低資料redundancy與dependency。
Redundancy Data 就是資料庫中無用的資料，通常是相同的資料存放在多張表中，而這就會導致資料進行增刪查改(CRUD)效率降低。
而正規化又分為First Normal Form, Second Normal Form, Third Normal Form, Boyce-Codd Normal Form。在實務應用上第三正規化是最被廣泛應用。
First Normal Form
Rules:
1. 每一張表的cell只包含單一不可切割(atomic)值。
2. 每一筆資料(record)必須是unique。如果有多個value必須存在一筆資料中，就建立新表。
最常發生在的欄位就是地址、姓名，或是使用者進行多選的欄位，
例如姓名->姓氏與名字。地址->縣市、鄉鎮市區、路、巷弄…等等。
Second Normal Form
Rules:
1. 符合1NF。
2. 每一非key欄位，必須dependent on PK，也就是把部分相依的欄位再分割。
例如把學號、課程代碼這兩欄分割出來。
Third Normal Form
Rules:
1. 符合2NF。
2. 每一個non-prime欄位與key之間沒有遞移相依(non-transitively dependent)關係。
於課程表中，[課程名稱、學分數、必選修、老師編號]直接相依於PK(課程代碼)，
但[老師姓名]是直接相依於老師編號，接著才間接相依於PK(課程代碼)。在此範例中就稱之為遞移相依。
因此再將老師資料拆分一表獨立出來。
Boyce-Codd Normal Form (BCNF)
Rules:
1. 符合3NF
2. PK中各欄位不可相依於其他非PK欄位 (當PK為多欄位組合的複合主鍵時再進行拆分)
7. Relationships
一對一、一對多、多對多，這些不同的資料關係分別代表什麼意思?
這邊採用FileMaker中介紹working with related tables的範例。
One to one
顧名思義，就是一筆資料中的key關聯到的table也只會有一筆資料
One to many
一對多關係就如訂單資訊，一位顧客可以下多筆訂單，因此Customer中的其中一筆資料customer_id關聯到Order的customer_id時可以有多筆order_id(代表多筆訂單)。
Many to Many
多對多如上舉例學校選課資料，每一學年註冊關聯到多位學生，也關聯到多門課程。
以上就是基礎資料庫的先修知識，感謝閱讀至此^^。
