第7章事務(wù)管理

1、第第7 7章章 事務(wù)管理事務(wù)管理事務(wù)管理（事務(wù)管理（transaction management）：）： 故障的可能性總是存在的。解決故障的措施有二：故障的可能性總是存在的。解決故障的措施有二：一是盡可能一是盡可能提高可靠性提高可靠性；二是；二是恢復(fù)恢復(fù)。 這里主要討論發(fā)生故障后，恢復(fù)數(shù)據(jù)庫至一致狀這里主要討論發(fā)生故障后，恢復(fù)數(shù)據(jù)庫至一致狀態(tài)的技術(shù)，即態(tài)的技術(shù)，即恢復(fù)技術(shù)恢復(fù)技術(shù)。 系統(tǒng)發(fā)生故障時(shí)，可能會(huì)導(dǎo)致數(shù)據(jù)的丟失系統(tǒng)發(fā)生故障時(shí)，可能會(huì)導(dǎo)致數(shù)據(jù)的丟失(loss)，要恢復(fù)丟失的數(shù)據(jù)，必須有后備副本。要恢復(fù)丟失的數(shù)據(jù)，必須有后備副本。 對于恢復(fù)，數(shù)據(jù)冗余是必需的！對于恢復(fù)，數(shù)據(jù)冗余是必需的！一

2、致一致狀狀態(tài)態(tài)n從文件系統(tǒng)繼承而來，周期性的把磁盤上的數(shù)據(jù)庫轉(zhuǎn)從文件系統(tǒng)繼承而來，周期性的把磁盤上的數(shù)據(jù)庫轉(zhuǎn)儲（儲（dumpdump）到脫機(jī)存放的磁帶上。到脫機(jī)存放的磁帶上。失效失效取后備副本取后備副本取后備副本取后備副本取后備副本取后備副本更新丟失更新丟失更新丟失更新丟失取后備副本取后備副本取后備副本取后備副本idididid取后備副本取后備副本id失效失效n 增量轉(zhuǎn)儲（增量轉(zhuǎn)儲（idid） 單純以后備副本為基礎(chǔ)的恢復(fù)技術(shù)：單純以后備副本為基礎(chǔ)的恢復(fù)技術(shù)： 優(yōu)點(diǎn)：優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，不增加數(shù)據(jù)庫正常運(yùn)行實(shí)現(xiàn)簡單，不增加數(shù)據(jù)庫正常運(yùn)行時(shí)的開銷。時(shí)的開銷。 缺點(diǎn)：缺點(diǎn)：不能恢復(fù)到數(shù)據(jù)庫的最近一致的狀

3、不能恢復(fù)到數(shù)據(jù)庫的最近一致的狀態(tài)。態(tài)。 多用于文件系統(tǒng)以及小型的不重要的數(shù)據(jù)多用于文件系統(tǒng)以及小型的不重要的數(shù)據(jù)庫系統(tǒng)。庫系統(tǒng)。 運(yùn)行記錄（運(yùn)行記錄（log或或journal）由系統(tǒng)維護(hù)，一般包由系統(tǒng)維護(hù)，一般包括下列內(nèi)容：括下列內(nèi)容： （1 1）前像（）前像（before image,bibefore image,bi） 當(dāng)數(shù)據(jù)庫被一個(gè)事務(wù)更新時(shí)，所涉及的物理塊更當(dāng)數(shù)據(jù)庫被一個(gè)事務(wù)更新時(shí)，所涉及的物理塊更新前的映像（新前的映像（imageimage）稱為該事務(wù)的稱為該事務(wù)的前像（前像（bibi），前前像以物理塊為單位；有了前像可以使數(shù)據(jù)庫恢復(fù)到像以物理塊為單位；有了前像可以使數(shù)據(jù)庫恢復(fù)到更新

4、前狀態(tài)，對應(yīng)操作更新前狀態(tài)，對應(yīng)操作undoundo( (撤銷撤銷) )。（2 2）后像）后像( (after image,ai)after image,ai) 當(dāng)數(shù)據(jù)庫被一個(gè)事務(wù)更新時(shí)，所涉及的物理塊更新當(dāng)數(shù)據(jù)庫被一個(gè)事務(wù)更新時(shí)，所涉及的物理塊更新后的映像（后的映像（imageimage）稱為該事務(wù)的稱為該事務(wù)的后像（后像（aiai），后像也后像也以物理塊為單位；有了后像，即便更新的數(shù)據(jù)丟失了，以物理塊為單位；有了后像，即便更新的數(shù)據(jù)丟失了，仍然可以使數(shù)據(jù)庫恢復(fù)到更新后的狀態(tài)，相當(dāng)于重做一仍然可以使數(shù)據(jù)庫恢復(fù)到更新后的狀態(tài)，相當(dāng)于重做一次更新，對應(yīng)操作次更新，對應(yīng)操作redoredo( (重

5、做重做) ) 。 問題：前像問題：前像( (bi)bi)、后像后像( (ai)ai)和事務(wù)操作的關(guān)系？和事務(wù)操作的關(guān)系？ 修改修改有有前像前像 有有后像后像插入插入沒沒前像前像 有有后像后像刪除刪除有有前像前像 沒沒后像后像（3 3）事務(wù)狀態(tài)）事務(wù)狀態(tài) 記錄每個(gè)事務(wù)的狀態(tài)，以便在恢復(fù)時(shí)作不同的處理記錄每個(gè)事務(wù)的狀態(tài)，以便在恢復(fù)時(shí)作不同的處理（commitcommit和和not commitnot commit）。）。事務(wù)失敗事務(wù)失敗事務(wù)開始事務(wù)開始活動(dòng)狀態(tài)活動(dòng)狀態(tài)操作結(jié)束操作結(jié)束事務(wù)提交事務(wù)提交回卷回卷事務(wù)結(jié)束事務(wù)結(jié)束 提交提交( (commit)commit)成功執(zhí)行成功執(zhí)行( (do al

6、l)do all)。 回卷回卷( (rollbackrollback或或abort)abort)消除事務(wù)對數(shù)據(jù)庫的影消除事務(wù)對數(shù)據(jù)庫的影響響( (do nothing)do nothing)。 對恢復(fù)而言，至少要區(qū)分一個(gè)對恢復(fù)而言，至少要區(qū)分一個(gè)事務(wù)是否提交事務(wù)是否提交！ 實(shí)現(xiàn)方法實(shí)現(xiàn)方法最近后備副本最近后備副本 運(yùn)運(yùn) 行行 記記 錄錄失效失效最近后備副本最近后備副本 運(yùn)運(yùn) 行行 記記 錄錄 基于后備副本與運(yùn)行記錄的恢復(fù)如上圖所示，當(dāng)數(shù)基于后備副本與運(yùn)行記錄的恢復(fù)如上圖所示，當(dāng)數(shù)據(jù)庫失效時(shí)，取出據(jù)庫失效時(shí)，取出最近后備副本最近后備副本，然后根據(jù)，然后根據(jù)運(yùn)行記錄運(yùn)行記錄，對未提交的事務(wù)用前像卷

7、回對未提交的事務(wù)用前像卷回向后恢復(fù)向后恢復(fù)( (backward backward recovery)recovery)；對已提交的事務(wù)，必要時(shí)用后像重做對已提交的事務(wù)，必要時(shí)用后像重做向前恢復(fù)向前恢復(fù)( (forward recovery)forward recovery)。 這種恢復(fù)技術(shù)，需保持運(yùn)行記錄，這將會(huì)影響數(shù)據(jù)這種恢復(fù)技術(shù)，需保持運(yùn)行記錄，這將會(huì)影響數(shù)據(jù)庫的正常工作速度，但可以使數(shù)據(jù)庫恢復(fù)到最近一致狀庫的正常工作速度，但可以使數(shù)據(jù)庫恢復(fù)到最近一致狀態(tài)。大多數(shù)商品化態(tài)。大多數(shù)商品化dbmsdbms采用這種恢復(fù)技術(shù)。采用這種恢復(fù)技術(shù)。 如果系統(tǒng)中有多個(gè)如果系統(tǒng)中有多個(gè)dbdb副本，且這

8、些副本具有副本，且這些副本具有獨(dú)立獨(dú)立的失效模式的失效模式( (independent failure mode)independent failure mode)，則可利用則可利用這些副本互為備份，用于恢復(fù)。這些副本互為備份，用于恢復(fù)。 此技術(shù)在分布式數(shù)據(jù)庫系統(tǒng)中應(yīng)用的較多。此技術(shù)在分布式數(shù)據(jù)庫系統(tǒng)中應(yīng)用的較多。 近年來，由于硬件價(jià)格的下降，也采用鏡像磁盤近年來，由于硬件價(jià)格的下降，也采用鏡像磁盤( (mirrored disks)mirrored disks)技術(shù)。技術(shù)。 寫數(shù)據(jù)時(shí)，兩個(gè)磁盤寫數(shù)據(jù)時(shí)，兩個(gè)磁盤都寫入同樣的內(nèi)容。都寫入同樣的內(nèi)容。 當(dāng)一個(gè)磁盤的數(shù)據(jù)丟當(dāng)一個(gè)磁盤的數(shù)據(jù)丟失時(shí)，可

9、以用另一個(gè)磁盤失時(shí)，可以用另一個(gè)磁盤的數(shù)據(jù)來恢復(fù)。（的數(shù)據(jù)來恢復(fù)。（兩盤同兩盤同時(shí)故障的概率可以假設(shè)為時(shí)故障的概率可以假設(shè)為零！零！）磁盤磁盤1 1磁盤磁盤2 2控制器控制器1 1控制器控制器2 2cpu1cpu1cpu2cpu2 鏡像磁盤系統(tǒng)鏡像磁盤系統(tǒng) 下面主要討論第二種恢下面主要討論第二種恢復(fù)技術(shù)。復(fù)技術(shù)。3.3.前像文件前像文件 可以看成一個(gè)堆文件。每個(gè)物理塊有個(gè)塊標(biāo)識符可以看成一個(gè)堆文件。每個(gè)物理塊有個(gè)塊標(biāo)識符bidbid（block identifierblock identifier）。）。bidbid由由tidtid、關(guān)系名和邏輯關(guān)系名和邏輯塊號組成。塊號組成。邏輯塊號在關(guān)系中

10、是唯一的。邏輯塊號在關(guān)系中是唯一的。如果一個(gè)事如果一個(gè)事務(wù)需要卷回，可以在前像文件中找出該事務(wù)的所有前務(wù)需要卷回，可以在前像文件中找出該事務(wù)的所有前像塊，按照邏輯塊號寫入到關(guān)系的對應(yīng)塊，從而消除像塊，按照邏輯塊號寫入到關(guān)系的對應(yīng)塊，從而消除該事務(wù)對數(shù)據(jù)庫的影響。該事務(wù)對數(shù)據(jù)庫的影響。 undo undo滿足冪等性滿足冪等性: : undo(undo(undo undo(undo(undoundo(x)=undo(x)undo(x)=undo(x)因此，因此，undoundo失敗可以再失敗可以再undo!undo! 4. 4.后像文件后像文件 結(jié)構(gòu)與前像文件相仿，不過記的是后像。在恢復(fù)結(jié)構(gòu)與前像

11、文件相仿，不過記的是后像。在恢復(fù)時(shí)，可按提交事務(wù)表中的事務(wù)次序，按邏輯塊號，時(shí)，可按提交事務(wù)表中的事務(wù)次序，按邏輯塊號，寫入其后像。這相當(dāng)于按提交的次序重做各個(gè)事務(wù)。寫入其后像。這相當(dāng)于按提交的次序重做各個(gè)事務(wù)。redoredo滿足冪等性滿足冪等性: :redo(redo(redoredo(redo(redoredo(x)=redo(x)redo(x)=redo(x) 問題：問題：undoundo操作需要按照事務(wù)的次序嗎？為什么？操作需要按照事務(wù)的次序嗎？為什么？ 取后備復(fù)本后，之前的運(yùn)行記錄就失去了價(jià)值，對取后備復(fù)本后，之前的運(yùn)行記錄就失去了價(jià)值，對恢復(fù)來說，只要保留最近后備復(fù)本以后的運(yùn)行記

12、錄。但恢復(fù)來說，只要保留最近后備復(fù)本以后的運(yùn)行記錄。但運(yùn)行記錄仍可能很大?？刹捎孟铝写胧p小運(yùn)行記錄規(guī)運(yùn)行記錄仍可能很大?？刹捎孟铝写胧p小運(yùn)行記錄規(guī)模。模。1.1.不保留已提交事務(wù)的前像不保留已提交事務(wù)的前像2.2.有選擇性的保留后像有選擇性的保留后像3.3.合并后像（對給定邏輯塊號的物理塊，如多次更新，合并后像（對給定邏輯塊號的物理塊，如多次更新，可只保留最近的后像）可只保留最近的后像） 如何判斷該做如何判斷該做undoundo還是還是redoredo呢？下一節(jié)，將解決這呢？下一節(jié)，將解決這個(gè)問題。個(gè)問題。 1 提交規(guī)則（提交規(guī)則（commit rule） 后像必須在事務(wù)提交前，寫入非易失

13、性存儲器（后像必須在事務(wù)提交前，寫入非易失性存儲器（db或或log）。）。 更新事務(wù)執(zhí)行時(shí)，應(yīng)遵守下兩條規(guī)則：更新事務(wù)執(zhí)行時(shí)，應(yīng)遵守下兩條規(guī)則：2 先記后寫規(guī)則（先記后寫規(guī)則（log ahead rule） 如果后像在事務(wù)提交前寫入數(shù)據(jù)庫，則必須把前像如果后像在事務(wù)提交前寫入數(shù)據(jù)庫，則必須把前像先寫入先寫入log。 在執(zhí)行一個(gè)更新事務(wù)時(shí)，按后像寫入在執(zhí)行一個(gè)更新事務(wù)時(shí)，按后像寫入dbdb的時(shí)間，有的時(shí)間，有三種可能的方案。三種可能的方案。即后像不能僅留在內(nèi)存中！即后像不能僅留在內(nèi)存中！a) 后像在事務(wù)提交前完全寫入后像在事務(wù)提交前完全寫入dbtid active listb.i log(按按l

14、og ahead rule)a.i dbtid commit listdelete tid from active list在這種情況下，如果出現(xiàn)故障，如何恢復(fù)？在這種情況下，如果出現(xiàn)故障，如何恢復(fù)？restartrestart時(shí)，對每個(gè)時(shí)，對每個(gè)tidtid，查兩個(gè)查兩個(gè)listlist：commit listactive list undo delete tid from active list nothing to dob) 后像在事務(wù)提交后寫入數(shù)據(jù)庫后像在事務(wù)提交后寫入數(shù)據(jù)庫tid active lista.i log (按按commit rule)tid commit lista.i

15、 db delete tid from active listrestartrestart時(shí)，對每個(gè)時(shí)，對每個(gè)tidtid，查兩個(gè)查兩個(gè)listlist：commit listactive list delete tid from active list redo, delete tid from active list nothing to doc) 后像在事務(wù)提交前后寫入數(shù)據(jù)庫后像在事務(wù)提交前后寫入數(shù)據(jù)庫tid active lista.i, b.i log(按按2 rules)a.i db (partially done)tid commit lista.i db (completed)

16、delete tid from active list在這種情況下，如果出現(xiàn)故障，如何恢復(fù)？在這種情況下，如果出現(xiàn)故障，如何恢復(fù)？commit listactive list undo redo, delete tid from active list nothing to do思考：方案思考：方案3均勻的將寫入均勻的將寫入db的的i/o操作分散在事務(wù)操作分散在事務(wù)提交前后，有什么優(yōu)點(diǎn)？提交前后，有什么優(yōu)點(diǎn)？ 有利于磁盤均衡負(fù)載有利于磁盤均衡負(fù)載 一個(gè)事務(wù)常常要給用戶發(fā)送有影響的消息一個(gè)事務(wù)常常要給用戶發(fā)送有影響的消息(message)，不是指需要用戶輸入的指示消息不是指需要用戶輸入的指示消息

17、。 例如：例如：“付款付款2000元元”以及以及“立即執(zhí)行下一步處理立即執(zhí)行下一步處理”等。等。 發(fā)送消息也是事務(wù)執(zhí)行結(jié)果的一部分，應(yīng)該遵循發(fā)送消息也是事務(wù)執(zhí)行結(jié)果的一部分，應(yīng)該遵循“要么不做，要么全做要么不做，要么全做”的原則。的原則。但是，消息往往難但是，消息往往難以用以用“undo”操作來消除其影響。操作來消除其影響。 因此，在事務(wù)結(jié)束前，消息不能發(fā)出，只有等事務(wù)因此，在事務(wù)結(jié)束前，消息不能發(fā)出，只有等事務(wù)結(jié)束后才能發(fā)出。結(jié)束后才能發(fā)出。帶來什么問題？帶來什么問題？mmtiti消息消息1 1消息消息2 2mmmm終端終端消息（消息（msgmsg）確認(rèn)（確認(rèn)（ackack）思考：系統(tǒng)失效時(shí)

18、，要做思考：系統(tǒng)失效時(shí)，要做undoundo和和redoredo操作；然而操作；然而atlatl長度有限，長度有限，ctlctl可能較長?？赡茌^長。這將導(dǎo)致什么結(jié)果？這將導(dǎo)致什么結(jié)果？ 由于事務(wù)可以在提交前和提交后將數(shù)據(jù)的后像分別寫入數(shù)據(jù)庫，由于事務(wù)可以在提交前和提交后將數(shù)據(jù)的后像分別寫入數(shù)據(jù)庫，因而對因而對ctlctl中的事務(wù)只能全部做中的事務(wù)只能全部做redoredo，很費(fèi)時(shí)（可能很費(fèi)時(shí)（可能ctlctl中的很中的很多事務(wù)已經(jīng)完成將后像寫入數(shù)據(jù)庫，但鑒別代價(jià)很大）。多事務(wù)已經(jīng)完成將后像寫入數(shù)據(jù)庫，但鑒別代價(jià)很大）。最近后備副本最近后備副本失效失效運(yùn)行記錄運(yùn)行記錄最近后備副本最近后備副本cp

19、cpcpcpcp運(yùn)行記錄運(yùn)行記錄失效失效 顯然，在最近檢查點(diǎn)以前提交的顯然，在最近檢查點(diǎn)以前提交的事務(wù)，恢復(fù)時(shí)，不用事務(wù)，恢復(fù)時(shí)，不用redo。 取取cpcp過程一般如下：過程一般如下： 暫停事務(wù)的執(zhí)行；暫停事務(wù)的執(zhí)行； 寫入上一個(gè)寫入上一個(gè)cpcp以后所提交事務(wù)的后像；以后所提交事務(wù)的后像； 在在loglog的的ctlctl中記下檢查點(diǎn)；中記下檢查點(diǎn)； 恢復(fù)事務(wù)的執(zhí)行?；謴?fù)事務(wù)的執(zhí)行。 取取cpcp很影響系統(tǒng)的正常運(yùn)行，而只有在發(fā)生系統(tǒng)失很影響系統(tǒng)的正常運(yùn)行，而只有在發(fā)生系統(tǒng)失效時(shí)，才有其減少效時(shí)，才有其減少redoredo工作量的效益。工作量的效益。 修復(fù)系統(tǒng)，必要時(shí)更新磁盤；修復(fù)系統(tǒng)，必

20、要時(shí)更新磁盤； 如果系統(tǒng)（如果系統(tǒng)（osos和和dbmsdbms）崩潰，重新啟動(dòng)系統(tǒng)；崩潰，重新啟動(dòng)系統(tǒng)； 加載最近后備副本加載最近后備副本； 用用loglog中的后像重做取最近后備副本后提交的所有事務(wù)。中的后像重做取最近后備副本后提交的所有事務(wù)。 恢復(fù)措施：恢復(fù)措施：1.1.串行訪問串行訪問( (serial access)serial access)事務(wù)順序執(zhí)行。事務(wù)順序執(zhí)行。dbmst3t2t1時(shí)時(shí) 間間t1t2t32.2.并發(fā)訪問并發(fā)訪問( (concurrent access)concurrent access)dbmsdbms可同時(shí)接納可同時(shí)接納多個(gè)事務(wù)，事務(wù)可在時(shí)間上重疊執(zhí)行。多

21、個(gè)事務(wù)，事務(wù)可在時(shí)間上重疊執(zhí)行。dbmst1t2t3時(shí)時(shí) 間間t1t2t31.1.提高系統(tǒng)資源利用率；提高系統(tǒng)資源利用率；2.2.改善短事務(wù)響應(yīng)時(shí)間。改善短事務(wù)響應(yīng)時(shí)間。 例如，兩個(gè)事務(wù)例如，兩個(gè)事務(wù)t t1 1和和t t2 2， t t1 1長，先交付；長，先交付； t t2 2短，稍短，稍后交付，如果串行執(zhí)行，則后交付，如果串行執(zhí)行，則t t2 2必須等必須等t t1 1，響應(yīng)時(shí)間很長。響應(yīng)時(shí)間很長。丟失丟失 事務(wù)若不加控制的并發(fā)執(zhí)行，會(huì)產(chǎn)生什么問題？事務(wù)若不加控制的并發(fā)執(zhí)行，會(huì)產(chǎn)生什么問題？ 1. 1.丟失更新（丟失更新（lost updatelost update） t1read(x)

22、x:=x+1write(x) t2read(x)x:=2*xwrite(x)時(shí)時(shí)間間t1t2read(x)read(x)x:=x+1write(x)x:=2*xwrite(x)問題：為什么會(huì)發(fā)生丟失更新？問題：為什么會(huì)發(fā)生丟失更新？ 由兩個(gè)事務(wù)對同一數(shù)據(jù)并發(fā)寫入引起，由兩個(gè)事務(wù)對同一數(shù)據(jù)并發(fā)寫入引起，稱為稱為“寫寫- -寫沖突寫沖突”( (write-write write-write conflict)conflict)臟數(shù)據(jù)臟數(shù)據(jù) 2. 2.讀臟數(shù)據(jù)（讀臟數(shù)據(jù)（dirty readdirty read） t1write(t)rollback t2read(tx)read(ty)時(shí)時(shí)間間t1

23、t2read(tx)write(t)read(ty)rollback問題：為什么會(huì)發(fā)生讀臟數(shù)據(jù)？問題：為什么會(huì)發(fā)生讀臟數(shù)據(jù)？ 由于一個(gè)事務(wù)讀取另一個(gè)更新事務(wù)尚未由于一個(gè)事務(wù)讀取另一個(gè)更新事務(wù)尚未提交的數(shù)據(jù)引起，稱為提交的數(shù)據(jù)引起，稱為“讀讀- -寫沖寫沖突突”( (read-write conflict)read-write conflict)x已改變已改變 3. 3. 讀值不可復(fù)現(xiàn)讀值不可復(fù)現(xiàn)（unrepeatable read) unrepeatable read) t1read(x)read(x) t2write(x)時(shí)時(shí)間間t1t2read(x)write(x)read(x)問題：為什

24、么會(huì)發(fā)生讀值不可重現(xiàn)？問題：為什么會(huì)發(fā)生讀值不可重現(xiàn)？ 由兩個(gè)事務(wù)對同一數(shù)據(jù)并發(fā)讀寫引起，由兩個(gè)事務(wù)對同一數(shù)據(jù)并發(fā)讀寫引起，問題出在問題出在“寫寫”操作上操作上 事務(wù)并發(fā)執(zhí)行時(shí)可能會(huì)有兩種沖突：事務(wù)并發(fā)執(zhí)行時(shí)可能會(huì)有兩種沖突： 寫寫、讀寫；寫寫、讀寫； 寫寫寫寫沖突在任何情況下都應(yīng)避免，沖突在任何情況下都應(yīng)避免，讀寫讀寫沖突一沖突一般情況下應(yīng)避免，但某些應(yīng)用場合可以容忍。般情況下應(yīng)避免，但某些應(yīng)用場合可以容忍。 思考：多個(gè)事務(wù)并發(fā)執(zhí)行，結(jié)果怎么估計(jì)？思考：多個(gè)事務(wù)并發(fā)執(zhí)行，結(jié)果怎么估計(jì)？ 設(shè)設(shè)writewrite簡寫為簡寫為w w，readread為為r r，r r和和w w用其所屬事務(wù)號為用

25、其所屬事務(wù)號為下標(biāo)，上圖的調(diào)度可表示為：下標(biāo)，上圖的調(diào)度可表示為： s=s=r r1 1(x)(x)w2(x)w2(x)r r1 1(x)(x) 對同一事務(wù)集對同一事務(wù)集, ,可能有很多種調(diào)度?？赡苡泻芏喾N調(diào)度。 如果其中兩個(gè)調(diào)度如果其中兩個(gè)調(diào)度s1s1和和s2s2，在數(shù)據(jù)庫的任何初始狀在數(shù)據(jù)庫的任何初始狀態(tài)下，所有讀出的數(shù)據(jù)都一樣，留給數(shù)據(jù)庫的最終狀態(tài)態(tài)下，所有讀出的數(shù)據(jù)都一樣，留給數(shù)據(jù)庫的最終狀態(tài)也一樣，則稱也一樣，則稱s1s1和和s2s2是等價(jià)的，又稱為是等價(jià)的，又稱為目標(biāo)等價(jià)目標(biāo)等價(jià)( (view view equivalence)equivalence)。偏重語義，難以判斷！偏重語義

26、，難以判斷！ 還有一種更實(shí)用的等價(jià)定義，稱為還有一種更實(shí)用的等價(jià)定義，稱為沖突等價(jià)沖突等價(jià)( (conflictconflictequivalence)equivalence)。 容易實(shí)現(xiàn)！容易實(shí)現(xiàn)！ 沖突操作有讀沖突操作有讀- -寫沖突和寫寫沖突和寫- -寫沖突兩種，可表示為：寫沖突兩種，可表示為： ri(x)和和wj(x) wi(x)和和wj(x) (i j) 沖突操作的執(zhí)行次序會(huì)影響執(zhí)行結(jié)果，不沖突操?zèng)_突操作的執(zhí)行次序會(huì)影響執(zhí)行結(jié)果，不沖突操作的次序可以互換，不致影響執(zhí)行結(jié)果。作的次序可以互換，不致影響執(zhí)行結(jié)果。 凡是通過調(diào)換凡是通過調(diào)換s s中不沖突操作得到的新的調(diào)度，稱中不沖突操作得

27、到的新的調(diào)度，稱為為s s的沖突等價(jià)調(diào)度的沖突等價(jià)調(diào)度。 如果兩個(gè)調(diào)度是沖突等價(jià)的，一定是目標(biāo)等價(jià)的；如果兩個(gè)調(diào)度是沖突等價(jià)的，一定是目標(biāo)等價(jià)的；反之未必！反之未必！ 若調(diào)度若調(diào)度s s在數(shù)據(jù)庫中產(chǎn)生的效果，與這組事務(wù)的某個(gè)在數(shù)據(jù)庫中產(chǎn)生的效果，與這組事務(wù)的某個(gè)串行執(zhí)行序列的結(jié)果相同，則稱這個(gè)串行執(zhí)行序列的結(jié)果相同，則稱這個(gè)調(diào)度調(diào)度s s是可串行化的是可串行化的（serializableserializable）。 例如，對事務(wù)集例如，對事務(wù)集t1,t2,t3的一個(gè)調(diào)度：的一個(gè)調(diào)度： s = r2(x) w3(x) r1(y) w2(y)s= r1(y) r2(x) w2(y) w3(x) s

28、是串行調(diào)度，故是串行調(diào)度，故s是沖突可串行化的，也是目標(biāo)可串是沖突可串行化的，也是目標(biāo)可串行化的！行化的！沖突可串行化的調(diào)度一定是目標(biāo)可串行化的嗎？沖突可串行化的調(diào)度一定是目標(biāo)可串行化的嗎？目標(biāo)可串行化的調(diào)度一定是沖突可串行化的嗎？目標(biāo)可串行化的調(diào)度一定是沖突可串行化的嗎？目標(biāo)可串行化的調(diào)度未必是沖突可串行化！目標(biāo)可串行化的調(diào)度未必是沖突可串行化！ 例如，調(diào)度例如，調(diào)度s=r1(x)w2(x)w1(x)w3(x)無沖突等價(jià)調(diào)度，但卻可以找到一個(gè)調(diào)度無沖突等價(jià)調(diào)度，但卻可以找到一個(gè)調(diào)度s： s=r1(x)w1(x)w2(x)w3(x)與與s目標(biāo)等價(jià)。目標(biāo)等價(jià)。目標(biāo)可串行化目標(biāo)可串行化沖突可串行化

29、沖突可串行化 多個(gè)事務(wù)串行執(zhí)行后，多個(gè)事務(wù)串行執(zhí)行后，db仍保持一致狀態(tài)?？纱腥员３忠恢聽顟B(tài)。可串行化調(diào)度與事務(wù)的某個(gè)串行執(zhí)行等價(jià)。當(dāng)然也保持?jǐn)?shù)據(jù)庫化調(diào)度與事務(wù)的某個(gè)串行執(zhí)行等價(jià)。當(dāng)然也保持?jǐn)?shù)據(jù)庫的一致狀態(tài)，因此，在一般的的一致狀態(tài)，因此，在一般的dbms中，都是以中，都是以可串行可串行化作為并發(fā)控制的正確性準(zhǔn)則！化作為并發(fā)控制的正確性準(zhǔn)則！s= w3(y)r1(x)r2(y)w3(x)w2(x)w3(z)r4(z)w4(x)t1t2t3t4t t4 4隊(duì)列隊(duì)列: :t t1 1,t,t3 3,t,t2 2 封鎖法是最基本的并發(fā)控制方法之一，它可封鎖法是最基本的并發(fā)控制方法之一，它可以有多種

30、實(shí)現(xiàn)方式。以有多種實(shí)現(xiàn)方式。 x locksx locks：only one type of lock, for both only one type of lock, for both read and writeread and write*two phase lockingndef1: in a transaction, if all locks precede all unlocks, then the transaction is called two phase transaction. this restriction is called two phase locking pr

31、otocol.ndef2: in a transaction, if it first acquires a lock on the object before operating on it, it is called well-formed. t1lock alock block cunlock aunlock bunlock c t2lock alock bunlock aunlock block cunlock c2plnot 2plgrowing phaseshrinking phasentheorem: if s is any schedule of well-formed and

32、 2pl transactions, then s is serializable.(王書p151證明)1)well-formed+2pl: serializable2)well-formed+2pl+unlock update at eot: serializable and recoverable.(不會(huì)有多米諾現(xiàn)象)3)well-formed+2pl+holding all locks to eot: strict two phase locking transaction.(s,x) s lockif read access is intended.x lockif update access is intended. 待加待加 已有已有nlsxnlyyysyynxynn( (s,u,x)