# 資料庫管理修課筆記

[Database Transaction & ACID](https://oldmo860617.medium.com/database-transaction-acid-156a3b75845e)
[lossless-decomposition-vs-dependency-preservation](https://stackoverflow.com/questions/39464758/lossless-decomposition-vs-dependency-preservation)

# Transaction

## Conflict

## Schedule的類型

### Serializable Schedule
* 定義：一個具有n筆交易的schedule是可序列化的，若此schedule與相同的n筆交易之某個序列schedule是衝突等價(Conflict Equivalent)。
* 判斷方法：畫優先順序圖(Precedence Graph)，若最後結果無迴圈，代表n筆交易可以以某種排列順序完成，則稱此schedule為serializable。
* **重要性：可提供交易的並行性(Concurrency)，紓解序列排程的缺點，且保証交易的正確性。**

### Recoverable Schedule
- 定義：S中有T1與T2，其中T2有read到T1先前write過的資料，若T1比T2先commit或rollback，則S為recoverable。
- 舉例，S: w1(x) -> r2(x) -> c1 -> c2
- 上述排程S為可復原排程。但若改為交易T2先被Commit的話(S: w1(x) -> r2(x) **-> c2 -> c1**)，則當交易 T1被Rollback或Abort時，交易T2的結果會不正確，且無法復原 (因Commit的交易不得再被取消)。
- **Recoverable 下可能會發生的問題：連鎖性撤回/連鎖性終止**（Cascading Rollback/Abort）想像T1因為某些原因abort了需要rollback，則T2也跟著被連帶rollback。因此我們需要更嚴格的Schedule，也就是下方要介紹的「Cascadeless Schedule」。

### Cascadeless Schedule
- 定義：S中有T1與T2，其中T2**只讀取**已commit過的資料（即在T2讀取前，T1已經先commit過了），則此Schedule為Cascadeless
- 舉例，S: w1(x) → **c1 → r2(x)** →c2
- 上述排程S為非連鎖性撤回排程。雖然會延遲交易T2的執行，但可以確保如果交易T1中止時，不會發生連鎖性撤回的現象，使得交易的確定性較高。此範例同時也合乎可復原排程的要求 (∵交易T2 讀取到交易T1寫入的 資料項目，且交易T1比交易T2先結束)。

### Strict Schedule
- 定義：S中有T1與T2，其中T2**只讀取或寫入**已commit過的資料（即在T2讀取前，T1已經先commit過了），則排程S可被認為是Strict Schedule。
- 舉例，S: w1(x) → **c1 → w2(x)** →c2

### 練習題：

**Sa: cascadeless**
- 無read到其它交易write過的資料項目，故為Recoverable、 Cascadeless Schedule。
- T1 write到T2寫過的資料項目x，且T2未Commit，故不為Strict Schedule。

**Sb: strict**
- T2在read 被T1寫過的y之前，T1已經commit過了，因此為casacadeless，而又因為T2沒有write過y，所以T2也符合strict。

**Sc: not revoverable**
- T1 read 到交T2寫過的資料項目y，但T1 commit時，T2未 Commit ; T2讀到T3寫過的z，但是T2比T3先commit，若T3後來發生abort或rollback則T2已經改不了了，就會是錯誤的z。

**總結判斷訣竅：先找出T write發生的點，看後面有沒有其他T' read或write到T先前write的資料，再去看commit發生的時間點。**
- 若T比T'早commit：recoverable
- 若T比T'早commit 且 T commit在T'read之前：cascadeless
- 若T比T'早commit 且 T commit在T'read或write之前：strict

Which of the following schedules are recoverable, cascadeless or strict? Which of them are serializable?
(1) r1(x), **w2(z)**, r1(z), r3(x), c2, r3(z), **w1(x)**, c1, **w3(x)**, c3
(2) **w1(x)**, r2(z), c1, **w2(y)**, r3(x), **w3(y)**, r2(x), c2, c3
(3) **w1(x), w2(z), w3(x), w1(z), w2(y), w3(y)**, c1, c3, c2

- (1) recoverable，衝突有：{w2(z),r1(z)} {w1(x),w3(x)}，而2比1早commit，1比3早commit。
- (2) cascadeless，衝突有：{w1(x),r3(x)} {w2(y),w3(y)}，而1比3早commit，2比3早commmit。此外1在3 read之前就commit，但是2在3 write之後才commit，因此符合 cascadeless 但不符合 strict。
- (3) cascadeless，衝突有：{w1(x),w3(x)} {w2(z),w1(z)} {w2(y),w3(y)}，由於沒有先write後read，故一定為cascadeless，但因為2沒有在1之前先commit，故不為strict。