第五章事務教學材料

第五章事務事務:是構成單一邏輯工作單元的操作集合。如：從支票帳戶到儲蓄帳戶的資金轉帳是一次顧客看到的單獨操作。數據庫系統(tǒng)的角度,這是由幾個操作完成的。5．1事務概念5．2事務狀態(tài)5．3原子性和持久性的實現(xiàn)5．4并發(fā)執(zhí)行5．5可串行化5．6可恢復性5．7隔離性實現(xiàn)5．8可串行化的判定事務是訪問并可能更新各種數據項的一個程序執(zhí)行單元,由高級數據操作語言或編程語言(如SQLCOBOLC等)的用戶程序的執(zhí)行引起,用begintransaction和endtransaction來界定,由事務開始與結束之間執(zhí)行的全體操作組成。為了保證數據完整性,數據庫系統(tǒng)必須做到:原子性(atomicity)：事務的所有操作在數據庫中要么全部正確反映出來要么全部不反映。一致性（consistency）：事務隔離執(zhí)行時（即沒有并發(fā)執(zhí)行的其他事務）保持數據庫的一致性。隔離性(isolation)：盡管多個事務可以并發(fā)執(zhí)行,但系統(tǒng)必須保證對任一事務對Ti和Tj，在Tj看來，Tj或者在Ti開始之前已經停止執(zhí)行，或者在Ti完成之后開始執(zhí)行。這樣，每個事務都感覺不到系統(tǒng)中有其他事務在并發(fā)的執(zhí)行。持久性(durability)：一個事務成功完成后，它對數據庫的改變必須是永久的，即使系統(tǒng)可能出現(xiàn)故障。

這些屬性通常稱為ACID特性

例：設Ti是從帳戶A過戶$50到帳戶B的事

務,事務Ti。Ti:read(A);A:=A-50;Write(A);Read(B);B:=B+50;Write(B).一致性原子性持久性隔離性

5．2事務狀態(tài)

提交狀態(tài)部分提交活動狀態(tài)失敗狀態(tài)中止狀態(tài)事務狀態(tài)圖：中止事務:必須對數據庫的狀態(tài)不造成影

響,回滾成功完成:提交

5．3原子性和持久性的實現(xiàn)數據庫舊拷貝數據庫舊拷貝（將被刪除）數據庫新拷貝a)更新前

b)更新后

db-pointer

db-pointer

1．保證原子性和持久性的影子拷貝技術，如圖：

(1)如果事務故障在db-pointer指針修改之前發(fā)生，數據庫的原始內容未受影響，通過刪除數據庫的新拷貝來中止事務。一旦事務已提交，所有更新都在db-pointer指針所指向的數據庫中，這樣更新事務或全部反映或全不反映。(2)db-point寫到磁盤之前出現(xiàn)故障,系統(tǒng)重啟，得到舊值。db-point寫到磁盤之后出現(xiàn)故障系統(tǒng)故障不破壞盤上的內容得到新值。(3)寫操作是原子性的，要么全寫，要么不寫。2．文本編輯的事務

5．4并發(fā)執(zhí)行數據的并發(fā)執(zhí)行與操作系統(tǒng)中使用的多道程序動機一樣。(1)可以減少不可預測的事務執(zhí)行時延(2)減少平均響應時間事務并發(fā)執(zhí)行的可行性：（1）I/O和CPU（2）各事務針對數據庫的不同部分進行

操作。例：定義兩個事務T1，T2T1過戶￥50T210%從A到B事務調度：用于確定那些可以保證一致性的執(zhí)

行序列。調度數：n個事務有n！個有效的串行調度。例：設T1是從帳戶A過戶$50到帳戶B的事

務,事務T1T1:read(A);A:=A-50;Write(A);Read(B);B:=B+50;Write(B).設T2是從帳戶A過戶10%的存款余額到帳戶B的事務,事務T2T2:read(A);temp=A*0.1A:=A-temp;Write(A);Read(B);B:=B+temp;Write(B).調度1——T1執(zhí)行完執(zhí)行T2，如圖：調度3、調度4調度2——T2執(zhí)行完執(zhí)行T1，如圖：read(A)A：=A-50write(A)read(B)B：=B+50write(B)read(A)temp：=A*0.1；A：=A-tempwrite(A)read(B)B：=B+tempwrite(B)

T1T2

T1T2

read(A)temp：=A*0.1A：=A-tempwrite(A)read(B)B：=B+tempwrite(B)read(A)A：=A-50read(B)B：=B+50write(B)

調度3、調度4read(A)A：=A-50write(A)read(A)temp：=A*0.1；A：=A-tempwrite(A)read(B)B：=B+50write(B)read(B)B：=B+tempwrite(B)

T1T2

T1T2

read(A)A：=A-50

read(A)temp：=A*0.1A：=A-tempwrite(A)read(B)write(A)read(B)B：=B+50write(B)B：=B+tempwrite(B)調度3----等價與調度1的一個并發(fā)調度調度4----一個并發(fā)調度（數據不一致）

5．5可串行化數據庫系統(tǒng)必須控制事務的并發(fā)執(zhí)行，保證數據庫處于一致的狀態(tài)?？紤]事務中的read與write操作。1．沖突可串行化2．視圖可串行化

read(A)

write(A)read(A)

write(A)read(B)

write(B)read(B)

write(B)

T1T2調度3----只顯示read與write指令5．5.1沖突可串行化

考慮調度S，其中含有分別屬于Ti與Tj的兩條連讀指令Ii與Ij（i≠j）。如果Ii與Ij處理不同數據項，則交換Ii與Ij不會影響調度中任何指令的結果。下面考慮Ii與Ij處理相同的數據項Q，read（Q），write（Q）有下面四種情形：(1)Ii=read(Q),Ij=read(Q)。Ii與Ij的次序無關緊

要，因為不論其次序如何，Ti與Tj讀取的Q值總

是相同的。(2)Ii=read(Q),Ij=write(Q)。若Ii先于Ij，則Ti不會

讀取由Tj的指令Ij寫入的Q值；若Ij先于Ii，則Ti

讀到由Tj的指令Ij寫入的Q值。因此Ii與Ij的次序

是重要的。(3)Ii=write(Q),Ij=read(Q)。Ii與Ij的次序是重要

的，原因類似前一情形。(4)Ii=write(Q),Ij=write(Q)。由于兩條指令均為write指令，指令的順序對Ti與Tj沒什么影響。

然而，調度S的下一條read(Q)指令讀取的值將

受到影響，因為數據庫里只保留了兩條write指

令中后一條的結果。如果在調度S中的指令Ii與

Ij之后沒有其他的write(Q)指令，則Ii與Ij的順

序直接影響調度S產生的數據庫狀態(tài)中Q的最終

值。*沖突：如圖：T1的write(A)與T2的read(A)指令沖突。T2的write(A)與T1的read(B)不沖突。

read(A)write(A)read(A)write(A)read(B)write(B)read(B)write(B)

T1T2*調度等價：設Ii與Ij是調度S的兩條連續(xù)指

令，若Ii與Ij屬于不同事務且

不沖突，則可以交換Ii與Ij的

順序得到一個新的調度S’，則

S與S’等價。調度5－－交換調度3的一對指令得到的調度，

如圖：調度6－－與調度3等價的一個串行調度，如圖：

T1T2

read(A)write(A)read(A)read(B)write(A)write(B)read(B)write(B)

T1T2

read(A)write(A)read(B)write(B)read(A)write(A)read(B)write(B)調度5----交換調度3的一對指令得到調度6---與調度3等價的串行調度

T3T4

read(Q)

write(Q)write(Q)

調度7----不可串行化的調度沖突等價：若調度S可以經過一系列非沖

突指令交換轉換成S’，稱S與S’是沖突等價。沖突可串行化：若S與一個串行調度沖突

等價，則稱S為沖突可串

行化的。

有可能存在兩個調度,它們產生相同的結果,但它們不是沖突等價的

read(A)

A：=A-50write(A)

read(B)

B：=B-10

write(B)

read(B)

B：=B+50

write(B)

read(A)

A：=A+10

write(A)T1T5

事務T5,從帳戶B過戶10元到帳戶A,如圖的調度不與串行調度<T1,T5>沖突等價,因為T5的write(B)指令與T1的read(B)指令沖突因此不能通過交換連續(xù)的非沖突指令將T1的所有指令移到T5之前.但是執(zhí)行調度8或串行調度<T1,T5>后,帳戶A與B的最終值相同.調度85．5.2視圖可串行化

視圖等價：S與S’滿足三條:對于每個數據項Q，若事務Ti在調度S中讀取了Q的初始值，那么Ti在S’中也必須讀取Q的初始值。對于每個數據項Q，若事務Ti在調度S中執(zhí)行了read(Q)，并且讀取的值是由Tj產生的，那么Ti在S’中讀取的值也必須由Tj產生。對于每個數據項Q，若在調度S中有事務執(zhí)行了最后的write(Q)操作，那么在S’中該事務也必須執(zhí)行最后的write(Q)操作。視圖可串行化：如果某個調度視圖等價于一個串行調度，則說這個調度是視圖可串行化的。

例：圖：調度9——一個視圖可串行化調度，等價于，<T3,T4,T6>T3T4T6

read(Q)write(Q)write(Q)write(Q)調度9----一個視圖可串行化調度沖突可串行化的調度是視圖可串行化的。視圖可串行化的調度不一定是沖突可串行化的。

5．6可恢復性前面我們討論的那些可接受的調度是假定無故障的情況下，從如何保持數據庫一致性出發(fā)的。下面討論在并發(fā)執(zhí)行過程中事務故障所產生的影響，以撤消它。如果事務Ti失敗了，系統(tǒng)必須撤消Ti的影響以保持事務的原子性。如有并發(fā)執(zhí)行的事務，還必須保證依賴于Ti的任何事務Tj也中止。為此系統(tǒng)還將限制一些調度類型。1．可恢復調度，如圖：若T9執(zhí)行完read(A)后立即提交，圖中的調度為不可恢復調度。T8T9

read(A)

write(A)read(A)

read(B)數據庫系統(tǒng)要求調度是可恢復的，即：對于每對事務Ti和Tj，如果Tj讀取了Ti所寫的數據項，則Ti先于Tj提交。2．無級聯(lián)調度，如圖：如果T10失敗了，T10回滾，T11依賴于T10，T11也要回滾，T12依賴于T11，T12必須回滾。一個事務的回滾導致一系列事務的回滾的現(xiàn)象稱為級聯(lián)回滾。T10T11T12

read(A)read(A)write(A)read(A)write(A)read(A)無級聯(lián)調度：對于每個事務Ti和Tj，如果Tj讀取了由Ti所寫的數據項，則Ti必須在Tj讀取前提交。無級聯(lián)的調度總是可恢復的。

5．7隔離性實現(xiàn)具有沖突可串行化或視圖可串行化并且無級聯(lián)的調度，才能保證數據庫的一致性，同時保證事務出現(xiàn)故障時的安全處理。并發(fā)控制機制的目標是獲得最高的并發(fā)性。同時保證所產生的調度是沖突可串行化或視圖可串行化并且無級聯(lián)的。

5．8可串行化的判定由前面的討論，調度是否可串行化顯得非常重要。因此我們必須知道如何確定一個調度S是否可串行化。

對于沖突可串行化的判定，存在一個簡單有效的算法，而判斷視圖可串行化的簡單有效的算法是不存在的。1．沖突可串行化的判定

設S是一個調度，由S構造一個有向圖，稱為優(yōu)先圖。

事務---頂點，邊由滿足下列三條之一的Ti->Tj組成：在Tj執(zhí)行read(Q)之前，Ti執(zhí)行write(Q)。在Tj執(zhí)行write(Q)之前，Tiread(Q)執(zhí)行。在Tj執(zhí)行write(Q)之前，Ti執(zhí)行write(Q)。

如果圖中存在邊Ti->Tj，則在任何等價于S的串行調度S’中，Ti都必須在Tj之前。

優(yōu)先圖中無環(huán)，則S是沖突可沖行

化的，用拓撲排序可以判定圖中是否

有環(huán)。拓撲序列即為串行化順序。

T1T1T1T1T2T2調度1調度2調度4

TiTkTjTiTmTkTmTjTiTkTjTm

2．視圖可串行化判定：是一個NP完全問

題，因此不存在有效的判定算法。

這節(jié)介紹一個判定視圖可串行化的方法，該方法對判定沖突可串行化的優(yōu)先圖進行修改，通過在圖的邊上加標記，確定哪些邊必須加入到優(yōu)先圖中，稱這樣的圖為帶標記的優(yōu)先圖。即使這樣我們會看到判定視圖可串行化的計算代價是很高的。

T3T4T6

read(Q)write(Q)write(Q)write(Q)調度9，視圖可串行化的調度，視圖等價于串行調度<T3,T4,T6>。

調度9的優(yōu)先圖，圖中有環(huán)，因此調度9不是沖突可串行化的。T3,T4的寫操作稱為無用的寫操作，它們產生的值沒有被其他的數據項引用。T3->T4不應該加入到圖中。需要一種方法判定一條邊是否加到優(yōu)先圖中。T3T4T6

設S是一個調度，假定事務Tj讀取Ti寫入的數據項Q。如果S是視圖可串行化的，則在任何與S等價的