###### tags: `Data Base`
# 第十二章: Transactions

## Transaction Processing
- Single-User System:
- 在同一時間最多一個 user 可以使用 system

- Multiuser System:
- 在同一時間可有很多 user 進入 system concurrently

- Concurrency
- Interleaved processing
- processes 競爭一個 CPU
- Parallel processing
- processes 競爭數個 CPUs

## Transactions
- 一連串的 operations
- Transaction boundaries
- Begin and End transaction

## Read and Write Operations
- read_item(X)
- 找到 address of the disk block item X
- Copy disk bkock into a buffer in main memory
- Copy item X 給 program variable named X

- write_item(X)
- 找到 address of the disk block contain X
- Copy disk block into a buffer in main memory
- Copy item X from program variable named X 到正確的 location in the buffer
- 儲存 updated block from buffer 給 disk

## Why Concurrency Control
- Lost Update Problem
(T1 的 X = X - N 白做)

- Temporary Update Problem
(T1 失敗需要轉回原本的 X，但T2先讀取 temporary 的值)

- Incorrect Summary Problem
(T3 在 X -N 後讀取 X, 在 Y + N 之前讀取 Y, 造成 X + Y 錯誤)

## Why Recovery?
- 系統崩潰
- 系統錯誤或 transaction error
- Local errors 或 exception conditions
- Concurrency control
- Disk failure
- Physical problem and catastrophes

## Transaction Concepts
- 為了達到 recovery 必須時時刻刻盯著 transaction
- Transaction states:
- Active state
- Partially commited stated
- Failed state
- Terminated State


- begin_transaction: 標記 transaction 執行開始
- read or write: 定義 read and write operation on the database items
- end_transaction: 標記 transaction 執行結束
- commit_transaction: 表示 transaction 執行安全，可以放心確認 database 不會被 undone
- rollback(or abort): 表示 transaction 執行不成功，要將之前被 transation 改變的 effects undone

- Recovery techniques 用下列 operators:
- undo:撤回之前的動作
- redo:某些 transation operations 要重做確保成功應用於 database

## System Log
- Log or Journal: log 會追蹤 transaction operations 影響了那些 database items
- log 會用在 recovery 時
- log 會存在 disk 所以不會受到 transcation 失敗影響
- 定期備份到暫存 storage 確保不會有物理傷害

## Log Records
- T 是 transaction-id
- Type of log record:
- [start_transation, T]: transaction 開始標記
- [Write_item, T, X, old_value, new_value]: 更改 log

- [read_item, T, X]: 讀取 log
- [commit, T]: transaction 執行成功 log
- [abort, T]: transaction 失敗 log

## Transaction Redo
- Redoing transactions:
- 當 commit entry 已經在 log 時， 其他 write operators 也已經在 Log, 除此之外可以從 log entries 啟動 redone
- 當系統 crash 時，只有 log entries 被寫回 disk，可以用於 recovery process，因為 main memory 可能丟失資料

## Force Write
- 有任何 transaction log 沒有被寫入 disk 時，必須在 committing transaction 之前啟動 force write process 來寫入 log。

## ACID Properties
- Atomicity:
- 全完成或全不完成(不可分割性)
- Consistency preservation:
- transaction 正確執行會將 db state 轉移到另一個
- Isolation:
- transaction 在 commit 前都不會看到其他 transaction，解決 temporary update problem
- Durability or permanency:
- 一旦 commit ，這些改變不會因為後面的失敗而被刪除

## Schedules
- Transaction 所組成，解決 concurrency ，排順序決定 transaction 執行

## Characterizing Schedules
- Recoverable schedule:
- 當 T' 有對 item A 做 write 時，必須在 item A 被其他 transaction read 之前先做 commit，這樣符合 recovery schedule

- Cascadeless schedule:
- 所有 transaction 只有 read the 被 committed 的 item ，稱作 Cascadeless schedule

- Schedules requiromg cascaded rollback:
- 當讀 failed transaction 改動的值時，必須一起 rollback

- Strict Schedules:
- 每個 transaction 都只讀寫已 commited 的 item

## Serializability
- Serial schedule:
- 每個 transacion 出現的順序等於執行的順序

- Serializable schedule:
- 如果 schedule S 等價於其他有 n 個 transaction 的serial schedule, 稱為 serializable scheudule

## Result Equivalent
- Result equivalent:
- 兩個 schedules 結果一樣稱為等價

## Conflict Serializability
- 衝突:
- 定義:
- 屬於不同 transactions
- access 一樣的 item
- 至少一個是 write

- Conflict equivalent:
- 兩個排程間有 order 一樣的任兩個 conflicting operations，稱 Conflict equvalent

- Conflict serializable:
- 若發生 conflict equivalent，則兩 schedules 稱為 conflict serializable

## Serializability
- 定義: schedule 是 **correct** schedule
- 執行過後 database 是 consistent state
- 適當交錯且 result 是 serially executed，並且有效率執行 concurrent execution
- 使用 locks with two phase locking(2PL)

## Testing Conflict Serializability
1. 只看 read_item and write_item operations
2. 建構 precedence graph(serialization graph)
3. 當 Ti 跟 Tj 有 conflitct operator 時，畫箭頭
- 只往下對應
- 當 read(x) 時，對應其他 transaction 的 write(x) 畫箭頭
- 當 write(x) 時，對應其他 transaction 的 write(x) 與 read(x)
4. 當 precedence graph 沒有 cycles 時，則 schedule is serializable


## Transaction Support in SQL2
SQL 有一個 SET TRANSACTION statement in SQL2
- Isolation level \<isolation\>
- 可以做到:
- READ UNCOMMITTED
- READ COMMITTED
- REPEATABLE READ
- SERIALIZABLE

Potential problems with lower isolation levels:
- Dirty Read:
- 讀到 failed transaction 寫入的值

- Nonrepeatable Read:
- T1 裡有 read_item(x) ,之後 T2 wrrite_item(x)完，T1 再 read_item(x) 一次，得到兩個不一樣的值

- Phantoms:
- A transaction T1 may read a set of rows from a table,perhaps based on some condition specified in the SQL WHERE clause.
- Now suppose that a transaction T2 inserts a new row that also satisfies the WHERE clause condition of T1, into the table used by T1.
- If T1 is repeated, then T1 will see a row that previously did not exist, called a phantom .

## Possible Violation of Serializability

# Reference
http://debussy.im.nuu.edu.tw/sjchen/Database/Final/Ch09.pdf