《雲數據管理：挑戰與機遇》2.3.1　預備知識

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第3節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

預備知識

數據庫由對象的集合組成，如x、y、z。假設每個對象都有一個值，所有對象的值構成了數據庫的狀態。通常情況下，這些狀態必須滿足數據庫的一致性約束。數據庫對象支持兩種原子操作：針對x的讀和針對x的寫，或者r[x]和w[x]。事務的概念在數據庫係統中至關重要。一個事務是按照一定偏序執行的操作的集合。事務ti執行的操作記作ri[x]和wi[x]。如果一個事務是正確的，即，如果一個事務在一致數據庫上單獨執行，那麼該事務可以將數據庫轉換成另外一個一致狀態。

事務的執行必須是原子的，即必須滿足如下兩個屬性：

1. 事務之間互不幹擾。

2. 事務中的操作要麼全部執行，要麼都不執行。

事務ti以commit(ci)或abort(ai)操作結束。並發控製協議可以確保並發執行的事務彼此之間互不影響。恢複協議可以確保all-or-nothing屬性。

如果兩個操作的執行順序對結果有影響，即，如果其中一個是寫操作，那麼這兩個操作是衝突的。給定一個事務集合T，T上的一個曆史H是針對所有事務操作的偏序，該順序反映了操作執行的順序（事務順序和衝突操作順序）。

數據庫管理係統必須滿足ACID特性，即

原子性（atomicity）：每個事務要麼全部執行，要麼都不執行，即all-or-none屬性。

一致性（consistency）：每個事務是一個一致的執行單位。

隔離型（isolation）：事務之間互不影響。

持久性（durability）：事務的效果是永久的。

當一個並發事務集合執行時，事務的正確性概念必須以每一個事務都是一致的（ACID中的C）為前提，因此，如果事務是隔離執行的，數據庫將從一個一致狀態轉換成另外一個一致狀態。因此，如果事務集合串行執行，那麼可以保證其正確性。特別是，對於一個調度H中的任意兩個事務ti和tj，如果ti的所有操作在H中都位於tj的所有操作之前，或者相反，那麼H是串行的。

為了允許事務之間在一定程度上並發執行，產生了可串行化的概念。如果一個曆史的執行結果與一個串行曆史的執行結果等價，那麼該曆史是可串行化的。如果兩個曆史產生相同的結果，即所有的事務寫入相同的值，我們認為這兩個曆史是等價的。由於我們不知道哪些事務執行寫操作，事務就需要從相同的事務中讀數據，最終寫入的值也相同。不幸的是，識別可串行化的曆史是NP完全問題[Papadimitriou, 1979]。因此，產生了一個更強的可串行性概念，稱之為衝突可串行性。

回想一下，如果針對相同對象的兩個操作中，至少有一個是寫操作，那麼這兩個操作是衝突的。如果兩個曆史H1和H2定義在相同的操作集合之上（相應的事務集合也相同），並且這兩個曆史中所有的衝突操作的順序都一致，那麼H1和H2是衝突等價的。如果一個曆史H和某一個串行曆史Hs是衝突等價的，那麼H就是衝突可串行化的。既然串行執行是正確的，那麼就可以保證衝突可串行化曆史也是正確的