南大mse復(fù)試課件數(shù)據(jù)庫

1、Chapter 10 Update Transaction2022/7/10Update Transaction2ch10 Update TransactionDef. 10.1 TransactionA transaction is a means to package together a number of database operations performed by a process, so the database system can provide several guarantees, called the ACID properties.BEGIN TRANSACTIO

2、Nop1; op2; opN;END TRANSACTION2022/7/10Update Transaction3ch10 Update TransactionBegin a transactionfirst database operationEnd a transaction by executingexec sql commit work;orexec sql rollback work;BEGIN TRANSACTIONop1; op2; opN;END TRANSACTION2022/7/10Update Transaction4ch10 Update TransactionExa

3、mple: banking applications with file systemproblemsCreating an inconsistent resultOur application is transferring money from one account to another (different pages). One account balance gets out to disk (run out of buffer space) and then the computer crashes.Errors of concurrent executionTeller 1 t

4、ransfers money from Acct A to Acct B of the same customer, while Teller 2 is performing a credit check by adding balances of A and B. Teller 2 can see A after transfer subtracted, B before transfer added.Uncertainty as to when changes e permanentAt the very least, we want to know when it is safe to

5、hand out money: dont want to forget we did it if system crashes, then only data on disk is safe.2022/7/10Update Transaction5ch10 Update TransactionACID guaranteesAtomicityThe set of record updates that are part of a transaction are indivisible (either they all happen or none happen). This is true ev

6、en in presence of a crash.ConsistencyIf all the individual processes follow certain rules (money is neither created nor destroyed) and use transactions right, then the rules wont be broken by any set of transactions acting together.IsolationMeans that operations of different transactions seem not to

7、 be interleaved in time - as if ALL operations of one Tx before or after all operations of any other Tx.DurabilityWhen the system returns to the logic after a Commit Work statement, it guarantees that all Tx Updates are on disk. Now ATM machine can hand out money.2022/7/10Update Transaction610.1 Tra

8、nsactional HistoriesActions in the databaseReads and Writes of data itemsRi(A)transaction with identification number i (Ti) reads data item A.Wj(B)transaction Tj writes B.A Update Statement will result in a lot of operations:Rj(B1) Wj(B1) Rj(B2) Wj(B2) . . . Rj(Bn) Wj(Bn)2022/7/10Update Transaction7

9、10.1 Transactional Histories10.1.2 history or schedule（調(diào)度）Figure 10.1 The job of the Schedulerlook at the history of operations as it comes in andprovide the Isolation guarantee, by sometimes delaying some operations, and occasionally insisting that some transactions be aborted. . . R2(A) W2(A) R1(A

10、) R1(B) R2(B) W2(B) C1 C2 . . .2022/7/10Update Transaction810.1 Transactional Historiesserial schedule（串行調(diào)度）all operations of a Tx are performed in sequence with no interleaving with other transactions.Scheduler assures that the sequence of operations in history is equivalent in effect to some seria

11、l schedule.2022/7/10Update Transaction910.1 Transactional HistoriesExample 10.1.1The two elements A and B in (10.1.2) are account records with each having balance 50 to begin with.T1 is adding up balances of two accountsT2 is transferring 30 units from A to Bresult of transaction (schedule 10.1.2)T1

12、: A+B = 70(fails the credit check)T2: A = 20, B = 80. . . R2(A,50) W2(A,20) R1(A,20) R1(B,50) R2(B,50) W2(B,80) C1 C2 . . .2022/7/10Update Transaction1010.1 Transactional HistoriesExample 10.1.1 (cont.)schedule 10.1.2data itemT2T1account Aaccount B1R2(A, 50);50502W2(A, 20);20503R1(A, 20);20504R1(B,

13、50);20505R2(B, 50);20506W2(B, 80);20807C120808C220802022/7/10Update Transaction1110.1 Transactional HistoriesExample 10.1.1 (cont.)But this could never have happened in a serial schedule, where all operation of T1 occurred before or after all operations of T2. (following). . . R1(A,50) R1(B,50) C1 R

14、2(A,50) W2(A,20) R2(B,50) W2(B,80) C2 . . . . . R2(A,50) W2(A,20) R2(B,50) W2(B,80) C2 R1(A,20) R1(B,80) C1 . . .2022/7/10Update Transaction1210.1 Transactional HistoriesAtomicThe set of updates contained in a transaction must succeed or fail as a unit.ConsistentComplete transactional transformation

15、s on data elements bring the database from one consistent state to another.IsolatedEven though transactions execute concurrently, it appears to each successful transaction that it has executed in a serial schedule with the others.DurableOnce a transaction commits, the changes it has made to the data

16、 will survive any machine or system failures.2022/7/10Update Transaction1310.2 Interleaved Read/Write OperationsIf a serial history is always consistent, why dont we just enforce serial histories?PerformanceFigure 10.3Tx has relatively small CPU bursts and then I/O during which CPU has nothing to do

17、.What do we want to do?Figure 10.4: Let another Ty run during slack CPU time.2022/7/10Update Transaction1410.2 Interleaved Read/Write OperationsFigure 10.5 6If we have many disks in use, we can keep the CPU 100% occupied.When one thread does an I/O, want to find another thread with completed I/O rea

18、dy to run again.2022/7/10Update Transaction1510.3 Serializability and the Precedence GraphSerializability Schedule（可串行化調(diào)度）The series of operations is EQUIVALENT to a Serial scheduleScheduler（調(diào)度器）find a set of rules for the Scheduler to allow operations by interleaved transactions and guarantee Seria

19、lizability.How can we guarantee this?2022/7/10Update Transaction1610.3 Serializability and the Precedence GraphFirstIf two transactions never access the same data items, so We can commute operations in the history of requests permitted by the scheduler until all operations of one Tx are together (se

20、rial history).The operations dont affect each other, and order doesnt matter.2022/7/10Update Transaction1710.3 Serializability and the Precedence GraphIf we have operations by two different transactions that do affect the same data item, what then?There are only four possibilities. R1(A) R2(A) .This

21、 can be commuted.If there is a third transaction T3, where:. R1(A) . W3(A) . R2(A) .then the reads (R1 and R2) cannot be commuted. R1(A) W2(A) . W1(A) R2(A) . W1(A) W2(A) .These two operations cannot commute.2022/7/10Update Transaction1810.3 Serializability and the Precedence GraphDef. 10.3.1 Confli

22、cting Operations（沖突動(dòng)作）Two operations Xi(A) and Yj(B) in a history are said to conflict (i.e., the order matters) if and only if the following three conditions hold:A BOperations on distinct data items never conflict.i jOperations conflict only if they are performed by different transactions.Two oper

23、ations of the SAME transaction also cannot be commuted in a history, why ?One of the two operations X or Y is a write (W).Other can be R or W.2022/7/10Update Transaction1910.3 Serializability and the Precedence GraphFigure 10.7 The Three TypesRi(A) Wj(A)meaning, in a history, Ri(A) followed by Wj(A)

24、Wi(A) Rj(A)Wi(A) Wj(A)2022/7/10Update Transaction2010.3 Serializability and the Precedence GraphDef. 10.3.2 An interpretation of an arbitrary history H consists of 3 parts.A description of the purpose of the logic being performed.Specification of precise values for data items being read and written

25、in the history.A consistency rule, a property that is obviously preserved by isolated transactions of the logic defined in 1).2022/7/10Update Transaction2110.3 Serializability and the Precedence GraphExample 10.3.1 Here is an interpretationT1 is doing a credit check, adding up the balances of A and

26、B.T2 is transferring money from A to B.The Consistency Rule: Neither transaction creates or destroys money.2022/7/10Update Transaction2210.3 Serializability and the Precedence GraphExample 10.3.1 (cont.)H1: R2(A) W2(A) R1(A) R1(B) R2(B) W2(B) C1 C2The schedule H1 is not serializability (SR) becauseI

27、f schedule H1 is equivalent to serializability schedule S(H1), thenW2(A) & R1(A) is conflicting operations, andW2(A) H1 R1(A), so W2(A) S(H1) R1(A)It means that T2 S(H1) T1R1(B) & W2(B) is conflicting operations, andR1(B) H1 W2(B), so R1(B) S(H1) W2(B)It means that T1 S(H1) T2so, schedule H1 is not

28、serializability.is non-SR2022/7/10Update Transaction2310.3 Serializability and the Precedence GraphExample 10.3.2 lost update ( dirty write )H2: R1(A) R2(A) W1(A) W2(A) C1 C2operations 1 and 4 imply that T1 S(H2) T2operations 2 and 3 imply that T2 S(H2) T1so, H2 is non-SRan example of H2R1(A, 100) R

29、2(A, 100) W1(A, 140) W2(A, 150) C1 C2scheduleH2T1 & T2T2 & T1value of A1501901902022/7/10Update Transaction2410.3 Serializability and the Precedence GraphExample 10.3.3 Blind WritesH3: W1(A) W2(A) W2(B) W1(B) C1 C2operations 1 and 2 imply that T1 S(H3) T2operations 3 and 4 imply that T2 S(H3) T1so,

30、H3 is non-SRan example of H3W1(A, 50) W2(A, 80) W2(B, 20) W1(B, 50) C1 C2scheduleH3T1 & T2T2 & T1value of A808050value of B5020502022/7/10Update Transaction2510.3 Serializability and the Precedence GraphDef. 10.3.3. The Precedence GraphA precedence graph for a history H is a directed graph denoted b

31、y PG(H).The vertices of PG(H) correspond to the transactions that have COMMITTED in H mitted transactions dont count.An edge Ti Tj exists in PG(H) whenever two conflicting operations Xi and Yj occur in that order in H.Thus, Ti Tj should be interpreted to mean that Ti must precede Tj in any equivalen

32、t serial history S(H).2022/7/10Update Transaction26Theorem 10.3.4 The Serializability TheoremA history H has an equivalent serial execution S(H) iff the precedence graph PG(H) contains no circuit.Proof.Assume there are m transactions involved, and label them T1, T2, . . ., Tm. Because In any directe

33、d graph with no circuit there is always a vertex with no edge entering it, thus there is a vertex, or transaction Tk, with no edge entering it. We choose Tk to be Ti(1).Note that since Ti(1) has no edge entering it, there is no conflict in H that forces some other transaction to come earlier.Now rem

34、ove this vertex, Ti(1), from PG(H) and all edges leaving it. Call the resulting graph PG1(H) with no circuit.Continue in this fashion, removing Ti(2) and all its edges from PG1(H), and so on, choosing Ti(3) from PG2(H), . . ., Ti(m) from PGm-1(H).2022/7/10Update Transaction2710.4 Locking Ensures Ser

35、ializabilityTwo-Phase Locking ( 2PL )封鎖（lock）封鎖類型常用的兩種類型封鎖鎖相容矩陣2022/7/10Update Transaction282810.4 Locking Ensures Serializability封鎖（lock）使用封鎖技術(shù)的前提在一個(gè)事務(wù)訪問數(shù)據(jù)庫中的數(shù)據(jù)時(shí)，必須先獲得被訪問的數(shù)據(jù)對象上的封鎖，以保證數(shù)據(jù)訪問操作的正確性和一致性。封鎖的作用在一段時(shí)間內(nèi)禁止其它事務(wù)在被封鎖的數(shù)據(jù)對象上執(zhí)行某些類型的操作（由封鎖的類型決定）同時(shí)也表明：持有該封鎖的事務(wù)在被封鎖的數(shù)據(jù)對象上將要執(zhí)行什么類型的操作（由系統(tǒng)所采用的封鎖協(xié)議來決定）封鎖是多

36、用戶環(huán)境中最常采用的一種并發(fā)控制技術(shù) 2022/7/10Update Transaction2910.4 Locking Ensures Serializability封鎖類型常用的封鎖類型有兩種排它鎖 (eXclusive lock，簡稱X鎖)又被稱為 寫封鎖 (WL Write Lock)共享鎖 (Sharing lock，簡稱S鎖)又被稱為 讀封鎖 (RL Read Lock)2022/7/10Update Transaction30排它鎖（X鎖）特性只有當(dāng)數(shù)據(jù)對象A沒有被其它事務(wù)封鎖時(shí)，事務(wù)T才能在數(shù)據(jù)對象A上施加X鎖；如果事務(wù)T對數(shù)據(jù)對象A施加了X鎖，則其它任何事務(wù)都不能在數(shù)據(jù)對象A

37、上再施加任何類型的封鎖。10.4 Locking Ensures Serializability2022/7/10Update Transaction31排它鎖（X鎖）作用如果一個(gè)事務(wù)T申請?jiān)跀?shù)據(jù)對象A上施加X鎖并得到滿足，則：事務(wù)T自身可以對數(shù)據(jù)對象A作讀、寫操作，而其它事務(wù)則被禁止訪問數(shù)據(jù)對象A這樣可以讓事務(wù)T獨(dú)占該數(shù)據(jù)對象A，從而保證了事務(wù)T對數(shù)據(jù)對象A的訪問操作的正確性和一致性。缺點(diǎn)：降低了整個(gè)系統(tǒng)的并行性10.4 Locking Ensures SerializabilityX鎖必須維持到事務(wù)T的執(zhí)行結(jié)束2022/7/10Update Transaction32共享鎖（S鎖）特性如果

38、數(shù)據(jù)對象A沒有被其它事務(wù)封鎖，或者其它事務(wù)僅僅以 S鎖 的方式來封鎖數(shù)據(jù)對象A時(shí)，事務(wù)T才能在數(shù)據(jù)對象A上施加 S鎖；10.4 Locking Ensures Serializability2022/7/10Update Transaction33共享鎖（S鎖）作用如果一個(gè)事務(wù)T申請?jiān)跀?shù)據(jù)對象A上施加 S鎖 并得到滿足，則：事務(wù)T可以對讀數(shù)據(jù)對象A，但不能寫數(shù)據(jù)對象A不同事務(wù)所申請的S鎖可以共存于同一個(gè)數(shù)據(jù)對象A上，從而保證了多個(gè)事務(wù)可以同時(shí)讀數(shù)據(jù)對象A，有利于提高整個(gè)系統(tǒng)的并發(fā)性在持有封鎖的事務(wù)釋放數(shù)據(jù)對象A上的所有S鎖之前，任何事務(wù)都不能寫數(shù)據(jù)對象AS鎖不必維持到事務(wù)T的執(zhí)行結(jié)束(依封鎖協(xié)

39、議而定)10.4 Locking Ensures Serializability2022/7/10Update Transaction34排它鎖與共享鎖的相互關(guān)系可以用如下圖所示的鎖相容矩陣來表示。當(dāng)前事務(wù)申請的鎖其它事務(wù)已持有的鎖YesYesNoS鎖YesNoNoX鎖-S鎖X鎖鎖相容矩陣10.4 Locking Ensures Serializability2022/7/10Update Transaction35合適(well formed)事務(wù)如果一個(gè)事務(wù)在訪問數(shù)據(jù)庫中的數(shù)據(jù)對象A之前按照要求申請對A的封鎖，在操作結(jié)束后釋放A上的封鎖，這種事務(wù)被稱為合適事務(wù)。合適事務(wù)是保證并發(fā)事務(wù)的正確

40、執(zhí)行的基本條件。10.4 Locking Ensures Serializability2022/7/10Update Transaction3610.4 Locking Ensures SerializabilityDef. 10.4.1 Two-Phase Locking ( 2PL )Locks taken in released following three rules.Before Ti can read a data item, Ri(A), scheduler attempts to Read Lock the item on its behalf, RLi(A); befor

41、e Wi(A), try Write Lock, WLi(A).If conflicting lock on item exists, requesting Tx must WAIT. Conflicting locks corresponding to conflicting operations:two locks on a data item conflict if they are attempted by different Txs and at least one of them is a WL.2022/7/10Update Transaction3710.4 Locking E

42、nsures SerializabilityThere are two phases to lockingthe growing phasethe shrinking phasewhen locks are released: RUi(A);The scheduler must ensure that cant shrink (drop a lock) and then grow again (take a new lock).Rule 3) implies can release locks before Commit; More usual to release all locks at

43、once on Commit, and we shall assume this in what follows.2022/7/10Update Transaction3810.4 Locking Ensures SerializabilityNote that a transaction can never conflict with its own locks!If Ti holds RL on A, can get WL on A so long as no other Tx holds a lock on A (must be RL).a Tx with a WL doesnt nee

44、d a RL (WL more powerful than RL).2022/7/10Update Transaction3910.4 Locking Ensures SerializabilityClearly locking is defined to guarantee that a circuit in the Precedence Graph can never occur.The first Tx to lock an item forces any other Tx that gets to it second to come later in any SG.But what i

45、f other Tx already holds a lock the first one now needs?This would mean a circuit, but in the WAIT rules of locking it means NEITHER Tx CAN EVER GO FORWARD AGAIN. This is a DEADLOCK. Example shortly.Deadlock2022/7/10Update Transaction40Example 10.4.1ScheduleExplanationABRL1(A)50501R1(A, 50)5050RL2(A

46、)50502R2(A, 50)5050WL2(A)T2 WAIT5050RL1(B)50506R1(B, 50)50507C1T2 can get WL2(A)50503W2(A, 20)2050RL2(B)20504R2(B, 50)2050WL2(B)20 505W2(B, 80)20808C22080H41R1(A)2R2(A)3W2(A)4R2(B)5W2(B)6R1(B)7C18C2non-SRSerializability2022/7/10Update Transaction41Example 10.4.2ScheduleABT1T2RL1(A)50501R1(A, 50)5050

47、RL2(B)50502R2(B, 50)5050WL2(B)50503W2(B, 80)5080RL2(A)50804R2(A, 50)5080WL2(A)5080T2 waitingRL1(B)T1 waitingH51R1(A)2R2(B)3W2(B)4R2(A)5W2(A)6R1(B)7C18C2non-SRDeadlock2022/7/10Update Transaction4210.4 Locking Ensures SerializabilityTheorem. 10.4.2 Locking TheoremA history of transactional operations

48、that follows the 2PL discipline is SR (Serializability).short-term locksA lock is taken prior to the operation (R or W) and released IMMEDIATELY AFTERWARD.long-term locksA lock are held until EOT (End Of Transaction).2022/7/10Update Transaction4310.5 Levels of Isolation定義當(dāng)前用戶的事務(wù)與其它并發(fā)執(zhí)行事務(wù)之間的隔離級(jí)別(leve

49、l of isolation)事務(wù)的隔離級(jí)別與所采用的封鎖策略緊密相關(guān)SET TRANSACTION ISOLATION LEVEL MITTED | MITTED |READREPEATABLE |SERIALIZABLE2022/7/10Update Transaction4410.5 Levels of Isolation MITTED：未提交讀在該方式下，當(dāng)前事務(wù)不需要申請任何類型的封鎖，因而可能會(huì)讀到未提交的修改結(jié)果禁止一個(gè)事務(wù)以該方式去執(zhí)行對數(shù)據(jù)的寫操作，以避免寫沖突現(xiàn)象。 MITTED：提交讀在讀數(shù)據(jù)對象A之前需要先申請對數(shù)據(jù)對象A的共享性封鎖，在讀操作執(zhí)行結(jié)束之后立即釋放該封鎖

50、。以避免讀取未提交的修改結(jié)果。2022/7/10Update Transaction4510.5 Levels of IsolationREADREPEATABLE：可重復(fù)讀在讀數(shù)據(jù)對象A之前需要先申請對數(shù)據(jù)對象A的共享性封鎖，并將該封鎖維持到當(dāng)前事務(wù)的結(jié)束。可以避免其它的并發(fā)事務(wù)對當(dāng)前事務(wù)正在使用的數(shù)據(jù)對象的修改。SERIALIZABLE：可序列化(可串行化)并發(fā)事務(wù)以一種可串行化的調(diào)度策略實(shí)現(xiàn)其并發(fā)執(zhí)行，以避免它們相互之間的干擾現(xiàn)象。2022/7/10Update Transaction4610.5 Levels of Isolation不管采用何種隔離級(jí)別，在事務(wù) 寫 數(shù)據(jù)對象 A 之前

51、需要先申請對數(shù)據(jù)對象 A 的 排它性 封鎖(write-lock)，并將該封鎖維持到當(dāng)前事務(wù)的結(jié)束。2022/7/10Update Transaction4710.5 Levels of Isolationlong-termshort-termshort-termNoRead Locks(Predicates)Nolong-termYesSerializableUpdate Anomalylong-termYesRepeatable ReadLost Updateshort-termYesRead CommittedDirty ReadsNoNo(Read Only)Read mittedPr

52、oblemRead Locks( row ) Write locksLevels of IsolationTypes of Locks2022/7/10Update Transaction4810.6 Transactional RecoveryLogsThe log entries contain Before Images and After Images of every update made by a Transaction.Before ImageIn recovery, we can back up an update that shouldnt have gotten to d

53、isk (the transaction didnt commit) by applying a Before Image.After ImageIn recovery, we can apply After Images to correct for disk pages that should have gotten to disk (the transaction did commit) but never made it.2022/7/10Update Transaction4910.6 Transactional RecoveryThree types of LogsUNDO Log

54、s only Before ImageRecovery for the transaction didnt commit.REDO Logsonly After ImageRecovery for the transaction did commit.UNDO/REDO LogsBefore Image & After ImageRecovery for all transactions.2022/7/10Update Transaction5010.7 Recovery in Detail: Log FormatsFigure 10.13 ( pg. 673 )OperationLog en

55、tryExplanationR1(A, 50)(S, 1)Start transaction T1 - no log entry is written for a Read operation.W1(A, 20)(W,1,A,50,20)T1 Write log for update of A.balance. The value 50 is the Before Image (BI) for A.balance column in row A, 20 is the After Image (AI) for A.balanceR2(C, 100)(S, 2)Another start tran

56、saction log entry.W2(C, 50)(W,2,C,100,50)Another Write log entry.C2(C, 2)Commit T2 log entry. (Write Log Buffer to Log File)R1(B, 50)No log entryW1(B, 80)(W,1,B,50,80)C1(C, 1)Commit T1 (Write Log Buffer to Log File)2022/7/10Update Transaction5110.7 Recovery in Detail: Log FormatsAssume that a System

57、 Crash occurred immediately after the W1(B,80) operation.2022/7/10Update Transaction52Log entry5(S, 1)4(W,1,A,50,20)3(S, 2)2(W,2,C,100,50)1(C, 2)FailureROLL BACK ACTION PERFORMEDMake a note that T1 is no longer Active. Now that no transactions were active, we can end the ROLL BACK phase.Transaction

58、T1 has never committed (its last operation was a Write). Therefore, the system performs UNDO of this update by Writing the Before Image value (50) into data item A. Put T1 into mitted List“.Make a note that T2 is no longer ActiveSince T2 is on Committed List, we do nothing.Put T2 into Committed List

59、2022/7/10Update Transaction53Log entryROLL FORWARD ACTION PERFORMED6(S, 1)No action required.7(W,1,A,50,20)T1 is mitted No action required.8(S, 2)No action required.9(W,2,C,100,50)Since T2 is on Committed List, we REDO this update by writing After Image value (50) into data item C.10(C, 2)No action

60、required.11We note that we have rolled forward through all log entries and terminate Recovery.2022/7/10Update Transaction5410.8 Checkpoints ( 檢查點(diǎn) )Def. 10.8.1: The Commit-Consistent CheckpointNo new transactions can start until the checkpoint is complete.Database operation processing continues until