(Centralized) Relational Database Management Systems (RDBMS): Theories and Concepts

1. RDBMS overview

Latest trend（db-engines.com ranking）：RDBMS dominates the market! 重要 RDBMS：Oracle、MySQL / MariaDB、Microsoft MS SQL、PostgreSQL、IBM DB2、SQLite；Microsoft Access（Not a real powerful RDBMS）。

RDBMS 用 tables 管理 data，Table is called "relation"。Slide 3 例子有三個 tables：

Student				Result				Module
Student ID	Name	Major		Student ID	Module Code	Grade		Module Code	Module Name
101101	Amy	BBA		101101	COM2006	B		COM2103	Database Design and Management
101103	Bob	CS		101101	COM2103	A		COM2006	Database Management Systems
101106	Cathy	CS		101103	COM2103	A
				101106	COM2103	B

Search & Join

Q：What are the names of students who get A in the module "Database Design and Management"? 資料散落三個 table，所以要 "join" the tables together（用 Student ID 同 Module Code 配對）：

Student ID	Name	Major	Module Code	Module Name	Grade
101101	Amy	BBA	COM2006	Database Management Systems	B
101101	Amy	BBA	COM2103	Database Design and Management	A
101103	Bob	CS	COM2103	Database Design and Management	A
101106	Cathy	CS	COM2103	Database Design and Management	B

答案：Amy、Bob。（Week 4 會寫成 SQL。）

2. Efficient search 與 Big O notation

Slide 6 問題：IG 有 3 billion MAU (2026)，你的程式每秒可以 loop 100M records，login 時逐個搵要幾耐？

Login 要等 15–30 秒明顯唔接受得 → 需要 index。

2.1 Big O notation

In computer science, we usually use complexity：Big O notation measures the order of the running cost (time / space etc.)。

Worked example（Example 3）：$n = 16$ players → round 1: 8 games, round 2: 4, round 3: 2, round 4: 1 → 4 rounds = $\lg 16$；games = $8+4+2+1 = 15 = n-1$。

2.2 Big O rules

3. Index on RDBMS：B tree

Common method：B tree (and its variants)（Bayer et al., 1972）。不同版本概念相近，細節有別；本科講 B tree 同 B+ tree。ExamCost complexity of search：$O(\lg n)$。

以 IG 為例：$\log_{10}(3\times10^9) = 9.38$（slide 數字）；用 binary log，$\lg(3\times 10^9) \approx 31.5$。即係由 30 秒 linear scan 變成大約幾十步——幾乎即時。

3.1 Structure of B tree（slide 13）

                    [ 11 ]                      ← Root node
             /                 \
        [ 5 | 8 ]           [ 15 | 20 ]         ← Non-leaf nodes
       /    |    \          /    |    \
   [1 3] [6 7] [9 10]  [12 14] [17 19] [21 23]  ← Leaf nodes

Key properties：Items on the left are all smaller；items on the right are all larger。Note：There could be multiple records for each value。喺 B tree，每個 node（包括 root 同 non-leaf）的值本身都係 data。

Example: Finding 15：15 > 11 → go right → 喺 [15 | 20] 搵到，Bingo!（未去到 leaf 已經搵到）
Example: Finding 22：22 > 11 → right；22 > 20 → right；leaf [21 23] 冇 22 → 22 does not exist。

Cost analysis：Best scenario $O(1)$（例如搵 11，root 就係）；Worst scenario $O(\lg n)$（slide 寫 $O(\ln(n))$，同一個 order）——n 係 distinct values 數目（≤ records 數）。

4. B+ tree

                    [ 13 ]
             /                 \
        [ 5 | 9 ]           [ 17 | 20 ]          ← separators only
       /    |    \          /    |    \
   [1 3]→[5 7]→[9 11]→[13 15]→[17 19]→[21 23]    ← leaf level, → = sibling pointer

Finding 15：15 ≥ 13 → right；15 < 17 → left → leaf [13 15]，Bingo。（B+ tree 一定要去到 leaf，因為 pointer 只喺 leaf。）

4.1 Range query：find 10–16

1. Step 1：search the smaller value (10)：10 < 13 → left；10 ≥ 9 → right → leaf [9 11]，由 11 開始（9 < 10 唔要）
2. Step 2：Go to siblings：沿 sibling pointer 去 [13 15] → 13、15 都喺範圍；最大值係 16，可能仲有 >15 且 ≤16 的值，所以再去下一個 sibling [17 19]；最細已經係 17 > 16 → 停

結果：11, 13, 15。Total number of nodes visited: 5（root, [5|9], [9 11], [13 15], [17 19]）。

4.2 Other key characteristics

• ExamThe update cost is also $O(\lg n)$。對比：Binary tree（a well-known data structure）has a linear update cost（樹可以變得唔平衡，worst case 似一條 linked list）
• Balanced tree：由 root 去任何 leaf 的 path length 都一樣
• B / B+ tree is for one-dimensional search；可以將多個 attributes 合成一個 attribute（composite key）再用 B+ tree
• 可以用 USFCA 的 B+ tree visualization 睇 maintenance 同 search 動畫

5. Index design & Query plan

Discussion：要 list 喺某 module 攞 A 的 student IDs，index 應該點建？用 slide 23 的 Result table：

Record	Student ID	Module Code	Grade
R1	101101	COM6002	B
R2	101101	COM6104	A
R3	101103	COM6104	A
R4	101106	COM6104	B

Index	Leaf entries (key → record pointers)
On module code	COM6002 → R1；COM6104 → R2, R4, R3（同一 key 下的 pointers 次序不受控制；但 leaf 的 keys 係有序的）
On grade	A → R2, R3；B → R4, R1
On (module code, grade)	(COM6002, B) → R1；(COM6104, A) → R2, R3；(COM6104, B) → R4

Yes! We can have multiple indices on the same table!

5.1 The overhead of indexing

• Index requires additional space and maintenance effort
• Additional space < space of records，因為 index 只存 pointers；record 內容永遠只有一份
• Is the maintenance effort worth it? Depends on your usage! How often is your index used? Is it necessary?（每次 INSERT/UPDATE/DELETE 都要更新所有相關 index）

5.2 Query plans（Query: Students who get A in COM6104）

5.3 Query optimizer

• RDBMS 會嘗試搵 optimal query plan：keeps statistics about the database（例如 number of records），automatically pick the "best" plan
• Note：Don't rely on query optimizer。佢識 rewrite 簡單 pattern（e.g., filter-join query），但 complex queries 好難 rewrite
• Recommendations：Try to write efficient SQL queries；Build index! Based on your usage

6. Other indices

Index	用途	重點
R-tree (Guttman, SIGMOD 1984)	Multi-dimensional spatial query：Find the object closest to me；objects within 1km	Worst case：Search $O(n)$、Update $O(n)$
HNSW (Hierarchical Navigable Small World, Malkov et al. 2016)	Top-k cosine similarity search on a vector database（approximate nearest neighbor）	Example application：RAG in LLM
Inverted index	Full-text (keyword-based) search	The reverse of a document-to-term mapping

Inverted index 例子：D1 = "He wins"，D2 = "She wins"，D3 = "I lose"：

Term	Document
He	D1
Win	D1, D2
She	D2
I	D3
Lose	D3

搜尋 "win" → 直接得 D1, D2，唔使逐份文件睇。（留意 wins → Win：做咗 stemming / normalization。）

7. Database transaction

Transaction = the basic unit in RDBMS，each transaction may contain several commands。例子：轉帳——(1) Deduct $5,000 from your account；(2) Add $5,000 to your friend's account。Both actions 1 and 2 are done or none is — All or nothing。試想部電腦喺 step 1 後、step 2 前 hang 機：錢就憑空消失。

Transaction structure：Transaction begins → … (all actions) → Commit。Once committed，DBMS 確保 transaction 真係完整做咗；否則 transaction should have no effect to the database。

Challenges：Concurrency control（多個 users 同時用同一 data items，要避免出錯）同 Recovery（系統 fail，例如 power outage，要 recover database contents）。

8. Concurrency control

8.1 Why concurrent execution?

多部 ATM 同時 access central database。如果唔支援 concurrent execution：電腦一次只做一個 transaction → 所有人排隊用一部 ATM，連銀行職員都要等。

8.2 The ATM example（slides 37–47）

Initial：$X = 100$，$Y = 100$。ATM 1 的 transaction：$X = X + 100$, $Y = Y - 100$。ATM 2：$Y = Y + 100$, $X = X - 100$。（每次 update 要等 database 回 "OK"，因為 network 可能 drop message；長時間收唔到 OK 就 resend。）

Step	Action	X	Y
1	ATM 2 reads Y → 100；ATM 1 reads X → 100	100	100
2	ATM 1: Update X to 200	200	100
3	ATM 1 reads Y → 100	200	100
4	ATM 2: Update Y to 200	200	200
5	ATM 1: Update Y to 0（用舊值 100 − 100）	200	0
6	ATM 2 reads X → 200	200	0
7	ATM 2: Update X to 100	100	0

Something wrong? Final $X = 100$, $Y = 0$。正確應該係兩個轉帳互相抵銷：$X = 100$, $Y = 100$。ATM 2 對 Y 的 +100 被 ATM 1 覆蓋咗（lost update），總金額由 200 變 100。

8.3 Correct execution = Serial execution

點樣確保 correct execution？Two phase locking（Eswaran et al., 1976）：ensure multiple transactions executing simultaneously do not corrupt shared data。Other methods：Timestamp ordering、Multi-Version Concurrency Control (MVCC)、Raft algorithm。

8.4 Locking

Make sure no other (active) transaction has a conflict action at the same time。兩種 lock：Readlock（read 之前要攞）同 Writelock（write 之前要攞）。

Transaction 1 (ATM 1):          加 lock 後：
Read(x)                          Readlock(x)  Read(x)
Write(x)                         Writelock(x) Write(x)
Read(y)                          Readlock(y)  Read(y)
Write(y)                         Writelock(y) Write(y)
                                 Releaselocks()

Q：做完 Write(x) 之後已經冇 x 的 action，可唔可以即刻 release x 的 lock？
A（lecturer notes）：No. Another transaction may be done between Write(x) and Read(y). If this transaction also has actions on x and y, the result will be incorrect.（佢會見到「X 已轉、Y 未轉」的中間狀態。）

8.5 Two-phase locking (2PL)

8.6 2PL example → Deadlock

T1：Read(x), Write(x), Read(y), Write(y)。T2：Read(y), Read(x), Write(x), Write(y)。

Step	Request	Result	Locks held
1	T1 已攞 Writelock(x)、Readlock(y)	—	W(x) by T1, R(y) by T1
2	T2 Readlock(y)	OK — readlock does not conflict with another readlock	+ R(y) by T2
3	T2 Readlock(x)	No — readlock conflicts with writelock → T2 waiting
4	T1 Writelock(y)（upgrade）	No — writelock conflicts with T2's readlock(y) → T1 waiting

T1 等 T2 放 y，T2 等 T1 放 x → 永遠完唔到：呢個就係 deadlock。

有 conflict 時點做？Option 1: wait（等其他 transaction 放 lock）；Option 2: rollback（Undo what the transaction has done；declare it failed；retry later）。

9. Database recovery

點解要 recovery？Cancelled transaction（user 撳 cancel）、System failure（disk failure, system crash, system errors）。

ExamLog-based recovery is the mainstream method。Core principle：Save to the log before writing to the database system（write-ahead）。

Challenges：How to perform backup without stopping the database? How to make sure all contents before the crash can be recovered?

9.1 What do we put in the log?

Log 成個 database？（唔理 efficiency 都）唔得——the snapshot of a database may be inconsistent：snapshot 嗰刻可能有 T1、T2 的 partial updates。

Failure 發生時：所有 working transactions 同 database 斷聯 → stop processing、rollback、report failure。Slide 65 例子中只有已 commit 的 T3 的效果應該留喺 database。

9.2 Example logs（slide 67–69）

Log entry 意思：T3 = start of T3；T3, X, 12 = T3 sets X to 12；T3 commit = end of T3 (commit)。

T3
T3, X, 12
T1
T3, Y, 10
T2
T1, A, 60
T1, B, 30
T3, Z, 8
T2, M, 100
T3 commit
--- Crash ---
Initial database: A=0 B=0 C=0 M=0 N=0 P=0 X=0 Y=0 Z=0

Crash 嗰刻：memory 入面係 A60 B30 M100 X12 Y10 Z8，但 disk 上可能只有 X12 Y10（其他仲喺 memory 未寫落 disk）。

9.3 Recovery algorithm

由 log 尾開始，scan the log backwards 搵出 incomplete 同 completed transactions。Q：When do we stop? 要確保所有 completed transactions 都搵到 → scan until the starting point of the log——即成個 log！（如果 log 由 30 年前開始？！）→ 需要 checkpoints。

10. Database checkpoints

10.1 Fuzzy checkpoint example（slides 73–77）

Checkpoint 101 記錄 running：T1, T2；Checkpoint 102：T2, T3, T4；Checkpoint 103：T2, T5；之後 Failure。

• Scan backwards until Checkpoint 103；All committed transactions before Checkpoint 103 are already in the checkpoint image
• Only need to chase further for T2 and T5（checkpoint 103 時仍 running）
• 去到 checkpoint 102：要唔要追 T2 / T3 / T4？T2：Maybe yes；T3: No! T4: No!（佢哋喺 checkpoint 103 已經唔喺 running list，即已完成，效果喺 image 入面）
• T5 喺邊度開始？喺 checkpoint 102 同 103 之間（102 冇 T5，103 有）
• T2 / T5 有冇 commit？Depends on whether we see "T2 / T5 commit" in the latest log（checkpoint 103 之後）

10.2 Full example（slides 78–79）

T1
T1, X, 10
T2
            ← Checkpoint 101 (running: T1, T2)
T1 commit
T3
T4
T2, X, 15
T3, Y, 5
T4, Z, 70
            ← Checkpoint 102 (running: T2, T3, T4)
T3 commit
T5
T2, A, 10
T4 commit
T5, Z, 30
            ← Checkpoint 103 (running: T2, T5)
T6
T6, Z, 50
T2, B, 30
T2 commit
T5, X, 10
--- crash ---

分析：

• T1、T3、T4 喺 checkpoint 103 前 commit → 已在 checkpoint image，唔使理
• T2：checkpoint 103 後見到 "T2 commit" → committed → redo T2, B, 30。T2 喺 checkpoint 前的 action（T2, X, 15；T2, A, 10）本應 redo，但 as this action is before the checkpoint, the update is always on the harddisk，唔需要真係 redo
• T5、T6：冇 commit → undo（T5, X, 10；T6, Z, 50；T5, Z, 30）。T5 喺 checkpoint 102–103 之間開始，所以要 scan 返去 T5 的 start 先可以停（slide 79 "We stop here"）

Recovery 後（假設 undo 有 before values 可用）：$X = 15$（T2），$Y = 5$（T3），$Z = 70$（T4），$A = 10$，$B = 30$。

11. ACID property of database

自我測驗 Self-test

Q1. 一個演算法成本係 $5n^3 + 2n^2\log n + 1000$，Big O 係乜？Knock-out tournament 有 64 個 players，要幾多 rounds、幾多 games？

$O(n^3)$（只取最高次項、忽略係數）。Rounds = $\lg 64 = 6$；Games = $n - 1 = 63$（$O(n)$）。

Q2. 用 slide 17 的 B+ tree（root 13；[5|9]、[17|20]；leaves 1 3 / 5 7 / 9 11 / 13 15 / 17 19 / 21 23），寫出 range query 6–14 的步驟同 visit 了幾多個 nodes。

6 < 13 → left；5 ≤ 6 < 9 → middle child → leaf [5 7]，攞 7。Sibling → [9 11]：9, 11；sibling → [13 15]：13（15 > 14，停）。結果 7, 9, 11, 13。Visited：root, [5|9], [5 7], [9 11], [13 15] = 5 nodes（喺 [13 15] 已見到 15 > 14，唔使再去下一個 sibling）。

Q3. B tree 同 B+ tree 有咩分別？點解 B+ tree 更適合 range query？

B+ tree：record pointers 只喺 leaf level；non-leaf values 只係 separators（左 <，右 ≥，可以唔存在於 DB）；leaf 之間有 sibling pointers。B tree 每個 node 的值都係 data，搜尋可以喺 non-leaf 停（best case $O(1)$）。Range query 用 B+ tree 只要搵到起點 leaf，再沿 sibling pointers 向右掃，唔使上落 traverse。兩者 search 同 update 都係 $O(\lg n)$，都係 balanced。

Q4. 要搵「COM6104 攞 A 的學生」，列出四個 query plan，邊個最有效率？Index 有咩代價？

(1) 全表 scan；(2) 用 module code index 再 check grade；(3) 用 grade index 再 check module；(4) 用 composite index (module code, grade) 直接搵——最有效率，冇多餘 records。代價：額外空間（只存 pointers，比 records 細）同每次更新資料的 maintenance effort；值唔值得視乎 usage。Query optimizer 會根據 statistics 揀 plan，但複雜 query 唔好倚賴佢。

Q5. 喺 2PL 下，T1 持有 Writelock(x)。T2 申請 Readlock(x)、T3 申請 Readlock(y)（冇人持有 y 的 lock），結果點？一個 transaction 放咗 lock 之後可唔可以再攞新 lock？

T2 被拒（readlock 同 writelock conflict）→ wait 或 rollback。T3 成功。2PL 下一旦開始 release（shrinking phase）就唔可以再攞新 lock。

Q6. Wait-for graph 有 edges：T1→T2、T2→T3、T3→T1、T4→T1。有冇 deadlock？點解決？

有，T1→T2→T3→T1 形成 cycle。解決：揀 cycle 入面一個 transaction（例如 T3）rollback、undo 佢的 actions、稍後 retry；如有其他 transaction 讀過佢寫的值，要 cascading rollback。T4 只係等緊，唔喺 cycle。

Q7. Log：T1 / T1,A,5 / T2 / T2,B,7 / T1 commit / T3 / T3,A,9 / T2,C,4 / crash。Initial 全部係 0。Recovery 後 A、B、C 係幾多？

T1 committed → redo $A = 5$。T2、T3 冇 commit → undo：$B = 0$、$C = 0$、A 嘅 T3 update 撤回 → $A = 5$（T1 的值）。結果 $A = 5, B = 0, C = 0$。

Q8. Fuzzy checkpoint 103 記錄 running：T2, T5。Scan backwards 時，喺 checkpoint 102（running: T2, T3, T4）需唔需要追 T3、T4？Worst-case recovery cost 係幾多？

唔使追 T3、T4：佢哋喺 checkpoint 103 已唔喺 running list，即已完成並包含喺 checkpoint image。只需追 T2、T5（T2 視乎有冇見到 commit）。Worst case $O(n)$（scan 到第一條 log），但實際極少發生。

Q9. 解釋 ACID，並說明 ATM lost-update 例子違反咗邊個 property。

Atomicity（all-or-nothing）、Consistency（valid state → valid state）、Isolation（好似獨立執行）、Durability（commit 後永久）。ATM 例子 interleaving 令 Y 的 +100 被覆蓋，結果唔等於任何 serial execution → 違反 Isolation（亦令 Consistency 破壞：總額由 200 變 100）。

一頁總結 Cheat sheet