第五章事務(wù)教學(xué)材料

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

這些屬性通常稱為ACID特性

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

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

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

提交狀態(tài)部分提交活動狀態(tài)失敗狀態(tài)中止?fàn)顟B(tài)事務(wù)狀態(tài)圖：中止事務(wù):必須對數(shù)據(jù)庫的狀態(tài)不造成影

響,回滾成功完成:提交

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

b)更新后

db-pointer

db-pointer

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

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

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

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

行序列。調(diào)度數(shù)：n個事務(wù)有n！個有效的串行調(diào)度。例：設(shè)T1是從帳戶A過戶$50到帳戶B的事

務(wù),事務(wù)T1T1:read(A);A:=A-50;Write(A);Read(B);B:=B+50;Write(B).設(shè)T2是從帳戶A過戶10%的存款余額到帳戶B的事務(wù),事務(wù)T2T2:read(A);temp=A*0.1A:=A-temp;Write(A);Read(B);B:=B+temp;Write(B).調(diào)度1——T1執(zhí)行完執(zhí)行T2，如圖：調(diào)度3、調(diào)度4調(diào)度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)

調(diào)度3、調(diào)度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)調(diào)度3----等價與調(diào)度1的一個并發(fā)調(diào)度調(diào)度4----一個并發(fā)調(diào)度（數(shù)據(jù)不一致）

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

read(A)

write(A)read(A)

write(A)read(B)

write(B)read(B)

write(B)

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

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

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

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

讀取由Tj的指令I(lǐng)j寫入的Q值；若Ij先于Ii，則Ti

讀到由Tj的指令I(lǐng)j寫入的Q值。因此Ii與Ij的次序

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

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

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

受到影響，因為數(shù)據(jù)庫里只保留了兩條write指

令中后一條的結(jié)果。如果在調(diào)度S中的指令I(lǐng)i與

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

序直接影響調(diào)度S產(chǎn)生的數(shù)據(jù)庫狀態(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*調(diào)度等價：設(shè)Ii與Ij是調(diào)度S的兩條連續(xù)指

令，若Ii與Ij屬于不同事務(wù)且

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

順序得到一個新的調(diào)度S’，則

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

如圖：調(diào)度6－－與調(diào)度3等價的一個串行調(diào)度，如圖：

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)調(diào)度5----交換調(diào)度3的一對指令得到調(diào)度6---與調(diào)度3等價的串行調(diào)度

T3T4

read(Q)

write(Q)write(Q)

調(diào)度7----不可串行化的調(diào)度沖突等價：若調(diào)度S可以經(jīng)過一系列非沖

突指令交換轉(zhuǎn)換成S’，稱S與S’是沖突等價。沖突可串行化：若S與一個串行調(diào)度沖突

等價，則稱S為沖突可串

行化的。

有可能存在兩個調(diào)度,它們產(chǎn)生相同的結(jié)果,但它們不是沖突等價的

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

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

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

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

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

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

read(A)

write(A)read(A)

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

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

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

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

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

設(shè)S是一個調(diào)度，由S構(gòu)造一個有向圖，稱為優(yōu)先圖。

事務(wù)---頂點(diǎn)，邊由滿足下列三條之一的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的串行調(diào)度S’中，Ti都必須在Tj之前。

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

化的，用拓?fù)渑判蚩梢耘卸▓D中是否

有環(huán)。拓?fù)湫蛄屑礊榇谢樞颉?/p>

T1T1T1T1T2T2調(diào)度1調(diào)度2調(diào)度4

TiTkTjTiTmTkTmTjTiTkTjTm

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

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

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

T3T4T6

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

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

設(shè)S是一個調(diào)度，假定事務(wù)Tj讀取Ti寫入的數(shù)據(jù)項Q。如果S是視圖可串行化的，則在任何與S等價的