# Database Systems: The Complete Book- P11

Chia sẻ: Thanh Cong | Ngày: | Loại File: PDF | Số trang:50

0
82
lượt xem
7

## Database Systems: The Complete Book- P11

Mô tả tài liệu

Database Systems: The Complete Book- P11: Database Systems and Database Design and Application courses offered at the junior, senior and graduate levels in Computer Science departments. Written by well-known computer scientists, this introduction to database systems offers a comprehensive approach, focusing on database design, database use, and implementation of database applications and database management systems

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Database Systems: The Complete Book- P11

1. 1. START thc scLtof transactio~~s have started. but not yet completed that (c) R S ( T )n n l s ( U ) is not empty; in particular, let it contain database va!idation. For each transaction T in this set. the scheduler maintains elenlent S. ST.4R-1 (T). tilnc at which T started. the Then it is possible that U wrote S after T read S.In fact. I/' may not 2. K4L; the set of transactions that have been validated hut not yet finished even have written A yet. -2 situatiorl where LTwrote X, but not in time ' tlie n-riting of phase 3. For each transaction T in this set, the scheduler is shown in Fig, 18.43. To interpret the figure. note that the dotted lines niairitains both srr.-\nr(T)and \:-\L(T),the time a t which T valiciated. connrct the eyents in real time ~ v i t h time a t which they xvould have the Sote that \ ~ L ( T is also thc time a t which T is irnagined to execute ill ) occurred had transactions bee11 executed a t the molnent they validated. the hypotlirtical serial order of esccutioi~. Since n.e don't kno~vn-hether or not T got t o read li's value, \ve must rollback T to avoid a risk that the actions of T and U will not be consistent 3. FIIV: the set of trai~sactio~is that have corripletcd phase 3. For thesc tra~isactions , the scheduler records START(T),\'.-\I.(T), and F I S ( T ) the T : ~vitli assumed serial order the time at which T finished. In principle this set grows, but as a-e shall see. 2. Suppose there is a transaction U such that: n-e do not havc to remember transaction T if ~ l n ( T< ST.~KT(C-) any ) for actir~ctransaction U (i.e.. for any U in START or VAL). The scheduler (a) U is in VAL: i.e., U has successfully validated. may thus periodically purge the FIN set to keep its size from growing beyond bounds. (h) F I S ( U ) > \:-\L(T); that is, U did not finish before T entered its validation phase. 18.9.2 The Validation Rules (c) \ v s ( T ) n \\.s(U) # 0: in particular. let S be in both \\-rite sets. If rnaintaincd by the scheduler. the information of Section 18.9.1 is cnotigh for Thcn the potential probleni is as sho~vn Fig. 18.44. T and li must both ill it to detect any potential violation of the assulned serial order of the transac- \\rite values of S , if \vc let T validate. it is possible that it will wiite and tions - the order in which the trai~sactionsvalidate. To understand tlie rules. S before I - does. Since \ve cannot be sure. n e rollback T t o make sure it Irt us first consider what can be I\-long ~ v h e w\-rtry to validate a transaction ~i C'. does not violate the assumed serial order in which it f o l l o ~ s T. T writes X T reads X I U writes X / U writes X D. validated T validating U finish U stalt T start U validated T validating Figure 18.43: T cannot ~ a l i d a t e an earlier transaction is nolv ~viiting if some- Figure 18.41: T cannot validate if it co~ildt l ~ e n i t e something ahead of an m thing tlrat T slioulci have rcati earlier transaction Tile two descrillpd above are the only situations in I\-hich a write 1. Supposcxtlir~rc,is ;I transaction L7 sur.11t11;it: T could I,e pl~~sically ullrcalizablt. In Fig. 15.43. if C finished before 7' starred. tlle~lsure]!. T lv0~~ltl tlic va111c of S that either c- or sollle later read (a) C is in 1/;-lLor FLV: that is. C- has vnlid;~tcd. trallsaction n.roce. In Fig. 18.44. if C finished hefore T validated. then surely . C' lvrote . before T did. \Ye may tli~ls y sunllnarize these observations with the (b) F I S ( C ) > s'I-~\RT(T): is, C tiid not finish beforc T started.'" that - - follon-ing rule for validating a transaction T : '"ore tlrat if 1: is in VAL. then C has not yet firris11c.d when ?. validates. In that case. FIX((.')is trclirricall?. l~ndefined. Holvever. we lirlon. it mrlst he largpr than ST;\KT(T) in this Check that R S ( T )n \\.s(U) = 0 for any previously validated C' that did case. not finish before T startcd, i.e.. if F I S ( ~ > S T A R T ( T ) . ) Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
2. 982 CHAPTER 18. COAiCURRENCY C'OXTROL 18.9. C04CL7RRE~1'CY CONTROL B Y VALID-4T10hT 983 Check that wS(T)n W S ( U )= 0 for any previously validated U that did not finish before T validated, i.e., if F I S ( U> v.%L(T). ) I Just a Moment I Example 18.29 : Figure 18.45 shows a time line during which four transactiorls lrou may have been concelned xvith a tacit notion that validation takes T, U , V , and IV attempt to execute and validate. The read and write sets for place in a moment, or indivisible instant of time. For example, we i~nagine each transaction are indicated on the diagram. T starts first, although U is the that vie can decide whether a transaction U has already validated before first to validate. we start to validate transaction T. Could U perhaps finish validating while n-e are xalidating T? If we are running on a uniprocessor system, and there is only one scheduler process, we can indeed think of validation and other actions of the scheduler as taking place in a n instant of time. The reason is that if the scheduler is validating T, then it cannot also be validating U , so all during the validation of T , the validation status of U cannot change. If I\-e are running on a multiprocessor, and there are several sched- uler processes, then it might be that one is validating T while the other is validating U. If so, then we need to rely on whatever synchroniza- tion mechanism the ~nultiprocessorsystem provides to make validation an atomic action. 4. Iralidation of 15': \'i;hen \ I T validates, ~\-efind that U finished bcfore Ili started. so no co~nparison e t w e n IV and U is performed. T is finished b before 11. validates but did not finish before Ti7 started, so [ve compare Figure 18.45: Four transactiorls and their validation onl\- R S ( T V ) \j's(T). I. is validated but not finished. so x e need to with cornpale both ~s(T1') arid I\ ~ ( 1 1 with ws(T). These tests are: ~) 1. \'alidation of U: When U validates there are no other validated transac- ~ s ( r l /n w s ( ~ ){A4. ) n {..l;C) = {.A). ) = D tions, so there is nothing to check. U validates successfully and writes a ~s(rv)ws(l') = {.4. D ) n { D . E } = { D l . n value for database element D. \vs(11-) n ws(17)= {.-I. C ) n {D; E ) = 0. 2. \lidation of T : When T validates, L is validated but not finished. Thus. T Since the i~ltersectionsare not all empty. Ti7 IS not validated. Rather, T I T lve must check that neither the read nor write set of T has anything is rolled back and does not write values for . or C . - I in common with W S ( U = { D ) . Since RS(T) {.4. B ) . and m ( T ) = ) = {.-I, C ) , both checks are successfiil. and T validates. 3. \%lidation of IT: \lilien 17 validates. li is validated and finished. and T is validated but not finishtd Also. I ' started hefore C finished 711~5. ne n~ust compare bath R S ( I ' ) and n ~ ( 1 against w s ( T ) Lilt onlv RS(I .) 3 18.9.3 Comparison of Three Concurrency-Control nerds to be compared against \\.s(l*). \\e find: Mechanisms Tile tllrce approaches to serializabllity that n-e have collsidered -- locks. times- . . RS(~-n ) n u s ( T )= { B ) n {-4.C) = 0. ns(17) ~ z s ( T= { D ,E ) n {-4.C) = 0 n RS(~*) ) ~ ( u {)B ) n { D ) = 0. = tamps. and validation - each have their advantages. First. they can be corn- pared for their storage utilization: Locks: Space in the lock table is proportional to the number of database Thus, I - also validates successfully. elements locked. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
3. Tzmestamps: In a naive implementation, space is needed for read- and b) R1(-4.B): R2(B,C): Vl; Rs(C,D), t:; fT-1(~4); 11'2(A4);1 i 7 3 ( ~ ) : 15: write-times with every database element, nhether or not it is currently accessed. However, a more careful implenlentation \%-ill treat all times- C) R1(.4.B); Rr(I3.C); 15; R3(C. D): 15; II7l(c): 1; 11'2(-+1):1ir3(D); : tamps that are prior to the earliest active transaction as "minus infinity.' d) R1(-4.B); R2(B.C): R3(C); V1:i5; If3; llTl(-4):Ilr2(B); fv3(c): and not record them. In that case. we can store read- and write-times in a table analogous to a lock table, in which only those database elements e) Rl(.-I.B); R2(B.C); R3(C); 1;: 1 V3; ll'-l(C): 11-z(B);1i73(>4): : ; that have been accessed recently are mentioned at all. f ) Rl(-4.B): R 2 ( B , ) ; R3(C); 11: 1 C : ; 1; Ll-1(-4) I17z(C): 1$-3(B): Validation: Space is used for timestamps and read/\vrite sets for each currently active transaction, plus a few more transactions that finished after some currently active transaction began. 18.10 Summary of Chapter 18 Thus, the amounts of space used by each approach is approximately propor- + Conszstent Database States: Database states that obey xhatever i~nplied tional to the sum over all active transactions of the number of database elenle~lts or declared constraints the designers inte~ldedare called consistent. It the transaction accesses. Timesta~npingand validation may use slightly more is essential that operations on the database preserve consiste~lcy. that is. space because they keep track of certain accesses by recently committed trans- they turn one consistent database state into anothel. actions that a lock table ~vould record. X poter~tial not problem with validation is that the w ~ i t e for a transaction must be known before the xrites occur set + C o n s ~ s t e n c ~ Concurrent Transacttons: I t is normal for several trans- of actions to have access to a database a t the same time. Trarisactions, run (but after the transaction's local cornputation has been conlpleteti). 111 isolation, are assumed to preserve consistency of the database. It is the It'e can also conipare the methods for their effect on the ability of transac- job of the scheduler to assure that concurrently operating transactions tions to complete tvithout delay. The performance of the three methotfs depends also preserxe the consistency of the database. on whether interaction among transactions (the likelihood that a tra~lractioci will access an elenlent that is also being accessed by a concurrent transaction) + Schedrrles: Tra~lsactionsare brokcn into actions, lnaillly reading and writ- is high or low. i~lgfrom the database. X sequcnce of these actions from one or more tra~lsactiollsis called a schedule. Locking delays transactions but avoids rollbaclts. even ~vheninteractio~l + Serial Schedules: If trallsactio~lsesecutc ollf ar a time, the s~ht!du!C is is high. Tiniestamps and validation do not delay transactions. but call said t o be serial. cause them to rollback, which is a niore serious form of delay and also ~ ~ a s t resources. es + Serializable Schedules: - i that is equivalent in its effect on the - schcdnle database t o sollle serial schedule is said to bc serializable. 111terlcat-i11gof If interference is lo\v. then neither timestamps nor validation ~villcause actions from transactions is I~ossible a serializable schedule that in many rollbacks. and may be preferable to locking because they generally I is not itself serial, but \ye 1llust ver?- careful what sequences of actions I have lolver overhead than a locking scheduler. I m-e allol3-. or all interlea\-ing \vill I e a ~ e the database in an inconsistent i \\-hen a rollback is necessary, tinlestamps catch some proble~nsearlier state. than validation, which altx-ays lets a transactioll do all its i ~ i t e r ~ l n-ork al + Conflict-se~alirabi~ity: -1ii~nple-to-te~t.sufficient condition for serializ- before considering whether the transaction niust rollback. ability is that the schedule can be made serial by a sequellce of stvaps of adjacellt actiolls \vithout conflicts. Such a schedule is called conflict- 18.9.4 Exercises for Section 18.9 sPrialixa]lle. ;\ collflicr occurs if ~ v c t o s n a p tn-o actions of the same try transaction. or to sXvap tXyo ac.tio~~s acccss the same datalxsr elenlent. that Exercise 18.9.1 : In the follo~vi~lg scquc.nccs of events. \\e IISP R,(.\-) to mcnn a t least one of ~vhichactions is ~vritc. S."=\lqo. "transaction T, starts, and its read set IS the list of d a t a b a ~ elc~nents e I/, lrieans .'T, attempts to talidate." and II;(.Y) lneans that ..T, finishes. and + PVecedenceGmyhs: .in easy tcst for cullflirt-serializal~ilityis to construct its write set was S."Tell n h a t happens n-lien each sequence is piocessect b j a a precedellce graph for the schedule. Sodes correspond to transactions. validation-based scheduler. and there is an arc T + C if some action of T in the schedule conflicts n-itIl a later action of c..\ schedule is conflict-serializable if and onl> if * a) R1(.4.B); Rr(B,C); 1;; R3(C. D): 15: II;(.4): I > : TI:L(,4): 11;(B): the precedence graph is ac\-clic. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 4. CH.-IPTER 18. CONCURRESCY C O S T R O L REFERESCES FOR CII.4PTER 18 + Locking: The most common approach to assuring serializable schedules is + Timestamp-Based Schedulers: Tliis type of scheduler assigns tirnesta~ilps to lock database elernents before accessillg them, and to release the lock to transactio~lsas they begin. Database elements have associated read- after finishing access to the element. Locks on an eleluent prevent otlier and write-times, \\.!lich are the tiniestanlps of the transactions that most transactions from accessing the element. recently 1;erformed those actions. If a n irnpossible situation, such as a read by one transaction of a value that s a s written in that transaction's + TWO-PhaseLockzng: Lorking by itself does not assure serializability. How- future is detected. the violating transaction is rolled back, i.e., aborted ever, two-phase locking, in which all transactions first enter a phase ~vhere and restarted. they only acquire locks, and then enter a phase d i e r e they only release locks. will guarantee serializability. + Val2dntfon-Based Schedrrlers: These schedlilers validate transactions after tliey haye read pverything they need, but before they write Trar~sactions + Lock Modes: To a\-oitl locking out transactions unnecessarily, systems that have wad. or \v111 nritc, an elenient that some other transaction is in usually use several lock modes, with different rules for each lriode about the ploccss of xvriting. nil1 have an ambiguous result, so the transaction when a lock can be granted. Most common is the system with shared is not val~dated.A transaction that fails t o validate is rolled back. locks for read-only access and esclusive locks for accesses that include writing. + Mr~ltiverszon Timestamps: A common technique in practice is for read- only transactiolls t o l ~ scheduled by timestamps. but with multiple ver- e + Compatzbzlzty Matrzces: A compatibility matrix is a useful summaiy of . sio~is, rvhere a !\-rite of an element does not overwrite earlier values of that xhen it is legal to grant a lock in a certain lock mode, given that there ele~nentuntil all transactions that could possibly need the earlier value may be other locks, in the same or other rnocles, on the same elelnent. have finished. IYriting transactions are scheduled by conventional locks. + Update Locks: A scheduler can allow a transactiori that plans to read and then write an element first to take an update lock, and later t o upgrade 18.11 References for Chapter 18 the lock to esclusive. Update locks call be granted hen there are already shared locks on the elcmerit: but once there, an update lock prevents vtlier The book [GI is a n important source for niaterial on scheduling, as well as locks from being granted on tliat element. locking. [3] is another important source. Two recent surveys of concurrency control are [I21 alid [Ill. + Increment L o c h : For the common case where a transaction n a n t i only t o Probably tlie most significant paper in the field of transaction processing is add or subtract a constant from an element, an increment lock is suitable. [4] on two-phase locking. Tlle ~varningprotocol for hierarchies of granularity Increnlent locks on the sanie elelne~ltdo not conflict n-it11 each other. is from [3]. Son-tx-o-phase locking for trees is from [lo]. The compatibility although they conflict bit11 shared and esclusi~elocks. matrix was introduced t o study behavior of lock modes ill [7]. Timestaiups as a concurrency control rilethod appeared in [2] and [I]. Sched- + Locking Elements Li'zth a GI-u~zularfty Hzerarchy: \\-hell both large and uling by ~alidation from [a]. The use of riiultiple versions was studied by [9]. is srnall elenients - relations, disk; blorks. and tuples, perhaps - may need to be locked, a ~ v a ~ l l i n g system of locks enforces serializability. Tra~lsac- 1. P. .\. Brln>tein arid 1.Goodman. ..Ti~nestamp-basedalgorithms for con- tions place intention locks on large elements to warn other transactions currency control ill distributed database systems." Proc. Intl. C O I L ~ . on that tliey plan to access one or more of its subelements. l'ery Large Databnses (1980). pp. 28.3-300. + Locking Elemen,ts .irmnged in a Tree: If database elements are only ac- 2. P. ;\. Benlstein. S . Goodman. J . 13. Rothnie, Jr.. and C. H. Papadirn- itriou. -Anal\-4s of sprializabiIity in SDD-1: a system of distributed data- cessed by moving dolvn a tree. as in a 13-tree index, then a non-tn-o-phase locking strategy call enforce serializability. The rules require a lock to 11e bases (the f u l l rcdlrrlda~ltcase)." IEEE Tra11,s. on Software En,g~:neering held on the parent n-llilt, obtaining a lock on tlic child. altliough the lock SE-4:3 (197S). pp. 1.54-168. on the parent c;111 then be rtlleasrd anti adtlitiorial locks taken latcr. 3 P. .A. Bclnitein. \.. Hadlilncoi. ant1 S Goodman. Concu~rencyCorltrol + Optimistic Concurrency Control: Instead of locking, a scheduler can as- and Recocery 171 Datrrbnsr: Sgstems. Iddlson-IYesley. Reading \IX, 1987. sume transactions d l be scrializahle. and abort a transactiori if some 1. K. P. Esn-amn. J . S. Gray. R. -1. Lorie, and I. L. Traiger. "The notions potentially nonserializable behavior is seen. This approach, called opti- of consistency and pledicate locks in a database system." Comm. iiCM mistic, is divided into timestamp-based, and validation-based scheduling. 1 9 : l l (1976). pp. 624-633. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 5. 988 CII.4PTER IS. CONCURRENCY CONTROL 5. J. N. Gray, F. Putzolo. and I. L. Traiger. "Granularity of locks and degrees of consistency in a shared data base," in G. AI. Sijssen (ed.), JJodelzng zn Duta Base 121anngen~ent Systems, North Holland, Amsterdam. 19iG. 6. J. X. Gray and A. Reuter, 'II-nnsaction Processing: Concepts and Tech- nzques, Morgan-Kaufrnann. San Francisco, 1993. 7. H. F. Korth, "Locking primitives in a database system," J. ACM 30:l Chapter 19 (19831, pp. 55-79. 8. H.-T. Kung and J. T. Robinson, "Optimistic concurrency control,.' ACM Trans. on Database Systems 6:2 (1981), pp. 312-326. More About Transaction 9. C. H. Papadimitriou and P. C. Kanellakis, "On concurrency control by multiple versions," ACM Trans. on Database Systems 9:l (1984), pp. 89- 99. Management 10. A. Silberschatz and 2 . Kedem, "Consistency in hierarchical database sys- ' terns," J. ACM 2 7 3 (1980). pp. 72-80. 111 this chapter we cover several issues about transaction managelllent that 11. A. Thomasian, "Concurrency control: methods, performance: and analy- were not addressed in Chapters 17 or 18. If7ebegin by reconciling the points of sis," Computing Surveys 30:l (1998), pp. 70-119. vien- of these two chapters: how do the needs t o recover from errors, t o allow 12. B. Thuraisingham and H.-P. KO, "Concurrency control in trusted data- transactions to abort: and to maintain serializability interact? Then, we discuss base managelner~t systems: a survey," SIGMOD Record 22:4 (1993), the management of deadlocks aillong transactions: which typically result from pp. 52-60. several transactio~ls each having to wait for a resource, such as a lock, that is held by another transaction. This chapter also incllldes an introduction to distributed databases. IVe focus on ho1v to lock elements that are distributed among several sites, perhaps with replicated copies. K e also consider how the decision to co~nmit abort a or transaction can be rnade ~vhen transaction itself involves actions at several the sites. Finally, consider the problems that arise due to ''long transactions." There are applications, such as CAD syste~lls "workflow" systems, in which or llumaii and conlputer processes interact, perhaps over a period of days. These systelns. like short-transaction systems such as banking or airline reservations, need to preserl-e consistency of the database state. Ho\T-ever,the concurrexlcy- control methods discussed in Chapter 18 do not rvork reasonably when locks are held for days, or decisions to validate are based on events that 'happened days in the past. 19.1 Serializability and Recoverability In Chapter 17 Xe discussed the creation of a log and its use to recover the v database state when a system crash occurs. \Ye introduced the vie\\- of database cornputatio~lin which values move bet\\-ecn nonvolatile disk, volatile ~nain- menlor?-. and the local address space of transactions. The guarantee the various Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 6. 090 CHAPTER 19. AIORE ABOUT TRAj\'SACTION JIALVL4GE-IIEIVT logging methods give is that, should a crash occur, it ~57ill able to reconstruct be lock on B that TI obtained; that step is essential, or else the lock on B would tlie actions of the committed transactions (and only the committed transac- be unavailable to any other transaction, forever. tions) on the disk copy of the database. A logging system makes no attempt T2 Ho~i-ever, has now read data that does not represent a consistent state to support serializabil~ty; w ~ l l it blindly reconstruct a database state, even if of the database. That is, ?r2 read the value of -4 that TI changed, but read it is the result of a noriserializable schedule of actions. In fact, commercial the value of B that existed prior to Ti's actions. I t doesn't matter in this casc database systems do not always insist on serializabilit~; and in sorne systems. whether or not the value 125 for il that TI created n-as m i t t e n to disk or not; ?? ' serializability is enforced only on explicit request of the user. gets that value from a buffer, regardless. As a result of reading an incorlsistcr~t On the othcr hand, Chapter 18 talked about serializability only. Scliedulels state, T2 leaves the database (on disk) with an inconsistent state, where -4 # B. designed according to the principles of that chapter may do things that the log The problem in Fig. 19.1 is that -4 ~vrittenby TI is dirty data, whether manager cannot tolerate. For instance, there is nothlng in the serializability it is in a buffer or on disk. The fact that 1; read -4 and used it in its on-n definition that forbids a transaction with a lock on an element A from writing calculation makes z ' s actions questionable. -1s we shall see in Section 19.1.2. a new value of A into the database before committing, and thus violating a rule it is necessary, if such a situation is allowed to occur, to abort and roll back T2 of the logging policy. \Verse, a transaction might write into the database and as \\-ell as TI. then abort without undoing the Ivnte, which could easily result in a n incon- sistent database state, even though there is no system crash and the scheduler theoretically maintains serializability. . 19.1.1 The Dirty-Data Problem Recall from Section 8.6.5 that data is "dirty" if it has been written by a trans- action tliat is not yet committed. The dirty data could appear either in the buffers, or on disk, or both; either can cause trouble. A := A+100; wl(d); Il(B);ul(:l); 125 Figure 19.2: TI has read dirty data from T2 and nlust abort n-hen Tl docs 12 (.A); 7'2 (.A); A := A*2; wq (.A) ; 250 Example 19.2 : Sow, consider Fig. 19.2.1~11ich sho~vs sequellce of actions i ~ n - a 1 (B) Denied 2 der a timestamp-based scheduler as in Section 18.8. Ho~vever: ilnagille that lye this sclleduler does not use the colnrnit bit that \\-as introduced in Section 18.8.1. ~1(B); Abort; ul(B); Recall that, the purpose of this bit is to prevent a value that !\-as n-ritten b>- /2(B): 112 (24); ( B ) : r2 an uncommitted transaction to be read by anot,her transaction. T h ~ swhen TI , B := B*2: reads B a t the second step, there is no co~nmit-bitcheck to tell T I to delay. TI can pr.oceed and could eve11 write to disk and commit; we haye not shoiv11 tc,,(B): 112(O); .50 further details of 1v11at Tl dors. Eyei~tually. 7; tries to ~i-ritcC in a ph!.sically unrealizable \\-a?. and T2 Figure 19.1: TI writes dirty data and then aborts aborts. The effecr of fi's prior write of B is cancelled: the value and \\-rite-ti~np of B is reset to 1~11at was before T2 wrote. I-et TI has been allo~i-?ti use this it to cancelled value of B and can do anything ~ i t it: such as using it to conlpute h Example 19.1 : Let us rcconsider the serializable schedule from Fig. 18.13. n e x values of .A. B , and/or C and ~vriting them to disk. Thus. T I ? ha\-ing read but suppose that after reading B, TI has to abolt for sonic reason. Then tlie a dirty value of B, can cause an inconsistellt database state. Xote that. had sequence of events is as in Fig. 19.1. After Tl aborts, the sclieduler releases the the commit bit been recorded and used, the read rl(13) at step (2) would have Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 7. 992 C'H-4l'TER 19. MORE ABOUT TRA.VSS-iCTIONAI-A-YilGElIEST been delayed, and not allowed to occur until after T2 aborted and the value of I 19.1, SERI.~LIZ.-~BILITY D RECOVERABI~~ITI- 1S In schedule S2,T2 must precede TI in a serial order because of the writing of 993 B had been restored to its previous (presumably committed) value. -4. but T I ~liustprecede T2 because of the n-ritirlg and readillg of B. Fillally. observe the follotving variation on S1. \vllich is serializable but not 19.1.2 Cascading Rollback rccoveiable: AS x e see from the exam~~les above, if dirty data is available to transactions, then \ve so~netilneshave to perform a cascading rollback. That is, when a In sclledule S3:TI precedes T2:but their cornrnitrne~lts occur in the wrong order. transaction T aborts, we must determine ~vhichtralisactions have read data If before a crash. the corlllllit record for T'2 reachcd disk, but the conllnit record written by T, abort thein: and recursively abort any tralisactions that have read for Ti did 11ot. then regardless of whether u ~ l d o ,redo, or urldo/redo logging data written by an a.borted transaction. That is, we must find each transaction ,$-ere used: 6 ~votild committed after recovery, but Tl would not. fJ be L that read dirty data written by T , abort C': find any transaction 5- that ' read dirty data from li, abort V : and so on. To cancel the effect of an aborted Irl order fc,r schpclules t o be truly recoverable under ally of the transaction, we can use the log, if it is one of the types (undo or undo/redo) three loggilrg methods, there is one additional assiiniption a c nlust make re- that provides former ~ralalues. We may also be able to restore the data from the garding schedules: disk copy of the database, if the effect of the dirty data has not migrated to disk. These approaches are considered in the next section. The log's colllmit records reach disk in the order in which they are written. As Jve have noted, a ti~ncstamp-basedscheduler witti a conlrnit bit pre- As 15-cobserved in Example 19.3 concerning sclirdule Sg.should it be possible fol vents a transaction that rnay Ilax-e read dirty data from proceeding, so there is coniniit records to reach di4k in the wrong order. then consistent lecovery might no possibility of cascading rollbaclc xvith such a scheduler. -4 validation-based be iInllossible, \ye return to a ~ i d exploit this prillciple in Section 19.1.6. sclieduler avoids cascading rollback, because ~vritingto the database (el-en in buffers) occurs only after it is determined that the transaction JX-ill colnmit. 19.1.4 Schedules That Avoid Cascading Rollback 19.1.3 Recoverable Schedules Recoverable sclletiules solnetimes require cascading rollback. For instance, if after first four steps of ~clicduleS1 in Esnl~iple19.3 TI had t o roll back, In order for any of the logging metllods ~ v e Ilave discussed in Chapter 17 to ailon- it n-ould be lleccssary to roll back TL,as n-ell. To guar:lntec the absence of 1-ecovery. the set of transactions that are regarded as committed after recol-el?- cascadillg rollback, lleed a stronger co~lditiolltlian rccowrabilit~. 11'~ Siiy must be consistent. That is. if a transaction TI is, after recovery. r e g a ~ d r d that : as committed, and Tl used a value written by G, the11 T2 must also remain committed. after recovei 5 Thus, n e define: . - schedule olioids cascarlzng rollback (or -is an .4CR schedfile") if trans- 1 actions ma! lead only values written 11.1. co~lnnittedtiansactions. -1schedule is rccove~able earh tra~lsaction if coinmits only after each tians- Put allotller \v\-a\-. XCR schedule forbids the rcadi~ig dirty data. As for re- a11 of action from n-hlcli it lias read lias committed. col-erablc sclledules. \ye assume that "comlnitted" ~ n e a n s that the log's comn~it Example 19.3: 1 1this and several subsequent exa~nplesof schedules n-it11 1 record has reaclled disk. read- and n-rite-actions, we shall use c, for the action .'transaction T, commits." Exalllple 19.4 : 5clicdules of Exalnple 19.3 are not -1CR. 111 each case. T2 Here is an example of a recoverable schedule: reads B frolll the uncomniitted transaction TI. Hon-ever. consider: Sl: IC, (A): I C I (B): w2 (-4): r2 (B): cl : r2: Sote that 2'2 reacts a value ( B ) \nitten by TI. so T2 must rol~imitaftcr TI for son., rends B ollly after T I . thc transaction that T? last n.rotc B. has colnlnit- the sclledr~lcto l ~ e rccovcrable. red. alld its log record n-rittc~i disk. Thus. sc,hcdnle S1 is .ACR. as 'vell as to Scliedule S above is evidently serial (and tllerefore sc~ializablc)as n-ell as 1 rcco\.crablc. recoverable, but the two concepts are orthogonal. For instance, the following sotice tllat sllould a transaction such as T2 read a value m i t t e n 11)- T I after variation on SI is still recoverable, but not serializable. TI conrmits. then surely fi either co~nnlits a1)orts after T1 commits. Thus: or Ever>-;\CR schedule is recotwable. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
12. 1002 CH.4PTER 19 NORE ABOUT TR-I*\SACTION JIANIGEJIEYT 19.2. I'IEIV SEXI,-LLIZ..IBILITI- 1003 a ) Two-phase locked, and strict. 19.2 View Serializability b) Two-phase locked, but not strict. Recall our discussion in Section 18.1.4 of how our true goal in tlie design of a scheduler is t o allow only schedules that are serializable. We also saw how tiif- Exercise 19.1.2: Suppose that each of the sequences of actions below IS fol- ferences in what operations transactions apply to the data call affect whether or lolved by an abort action for transactio~l Tell whicli transactions need to be TI. not a given schedule is serializable. lye also learned in Section 18.2 that sched- rolled back. uler~ nor~nally ellforce "conflict serializability," which guarantees serializability regardless of what tlie transactiolls do with their data. * a) r1(24); rz(B); wl(B); ~ 2 ( C ) rj(B); r3(C); 703(D); j However, there are weaker conditions than conflict-serializability that also guarantee serializability. In this sectiorl we shall consider one such condition, b) r l (A): ml (B); rz(B); 102(C); r3(C); w3(D); called .'vie\v-serializability:' Intuitively, view-serializability considers all the connectio~isbetween transactions T and li such that T writes a database el- c) r2(A); r3(A); rl(A); w ( B ) ; r2(B): rz(B); m2(C); r3(C); ement ~vhosevalue U reads. The key difference between view- and conflict- serializability appears when a transaction T writes a value A that no other d) 72(-4); r3(A); rl(A); wl(B); rd(B); IUL(C); r3(C); transaction reads (because some other transaction later writes its om11 value for .A). In that case, the KT(-4) action can be placed in certain other povitiolls Exercise 19.1.3: Consider each of the sequences of actions in Exercise 19.1.2. of the schedule (where A is like~visenever read) that ~vouldnot be permitted but now suppose that all three transactions cornrnit and write their cornillit under the definition of conflict-serializability. In this section, 11-e shall define record on the log immediately after their last action. Hon-ever, a crash occurs. vie~v-serializabilityprecisely and give a test for it. and a tail of the log mas not writtcn to disk before the crash and is therefore lost. Tell, depending on where the lost tail of the log begins: 19.2.1 View Equivalence 2. f hat transactions could be consideled uncomnlitted9 Suppose we have two scheduIcs S1 and S2 of the same set of transactions. Imagine that there is a hypothetical transaction To that wrote initial \alu?s for ii. ilre any dirty reads created during the recovery process? If so. n-hat each database element read by any transaction in the schedules, and another transactions need to he rolled back? hypothetical transaction T j that reads every element written by one or more tra~isactions after each schedule ends. Then for every read action ri(*.I) in one zii. \$-hat additional dirty reads could have been created if the portion of tlie of the schedules. 17c can find the write action l u j ( ; l ) that most closely preceded log lost was not a tail. but rather solne potions in the middle? the read in question.' We say T,is the source of the read action ri(=l). S o t e that transaction Tj could be the lippothetical initial tra~isactiollTo, and Ti ! Exercise 19.1.4 : Consider the folloa-ing tn-o transactions. could be Tf . If for every read action ill one of the schedules, its source is the same in TI: WI (-4): (B); r~(C): cl; the other schedule, we say that S1 and Sg are view-equivalent. Surely, view- T2: WZ(-4): TZ(B): U ~ ( CCZ; ? ) equivalent schedules are truly equivalent; they each do the same when executed on any one database state. If a scliedille S is vie~v-equivalent a serial schedule. to * a) HOWnnany schedules of Tl and T2 are rccovcrable? we say S is view-serializable. b) Of these. how many are .ICR sclietlules? c) How many are both rccoveral~lc and scrializnble? 1 E x a m p l e 19.9 : Consider the \chetlulr TI : rl(-J) S defined by: 1L-1(B) T?: r2(B) ~"(~4) w2(B) d) How many are both .iCR and serializable? 73 : r3(-4) (B) 1 ~ ' ~ Exercise 19.1.5: Give an example of an .ICR schedule wit11 shared and es- '~Vhile we ha\e not previously prevented a transaction from writing an element twice. there is generally no need for it t o do so. and in this study it is useful to assume t h a t a clusive locks that is not strict. f transaction only jvrites a given element once. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 13. 1004 CH-APTER 19. AiORE ABOUT TR.AXSACTION .lIA4LY-4GE-\1EST 19.2. SERIALIZ-4BILITY Sotice that vie have separated the actions of each transaction vertically: to 3. Suppose Tj is the source of a read ri(X), and Tk is another ~vriter X. of indicate better which transaction does what; you should read the schcd~lle from It is not allowed for Tk to intervene between T, and Ti, it must appear so left-to-right, as usual. either before T, or after Ti. n T erepresent this condition by a n arc pair In S , both TI and T2 write values of B that are lost; only tbe value of (sho~r-n dashed) from Tk t o Ti and froni Ti to T k . Intuitively: one or the B written by T3 survives to the elid of the schedule and is "read.' by the other of an arc pair is .'real," but lve don't care which, and when x e try hypothetical transaction Tf. S is not conflict-serializable. To see rvhi, first note to make the polygraph acyclic, we can pick whichever of the pair helps to that T2 writes A before TI reads A: so l must precede TI in a hypothetical ' ? make it acyclic. Honever? there are important special cases where the arc conflict-equivalent serial schedule. TIie fact that the action ,lnl (Bj precedes pair becomes a single arc: I C ~ ( B also forces TI to precede T2 ill any co~iflict-equivalentserial schedulc. ) Yet neither a l ( B ) nor l(i2(B) has any long-term affect on tlie database. It is (a) If T j is To, then it is not possible for Tk t o appear before T', so we these sorts of irrelevant \\,rites that vien.-serializability is able to ignore, when use an arc Ti + Tk in place of the arc pair. determining the true constraints on an equivalent serial schedule. hIore precisely, let us consider the sources of all the reads in S: (b) If Ti is T f ; then Tk cannot follow Ti, so we use an arc Tk + Tj in place of the arc pair. 1. The source of rz(B) is To,since there is no prior write of B in S . 2. The source of rl(A) is T2,since T.l most recently wrote -4 before the read. 3. Likewise, the source of r3 (-4) is T2. 4. The source of the hypothetical read of =I by Tf is T2. B A 5. Thc source of thc hypothetical read of B by T f is TJ,the last w i t e r of B. Figure 19.4: Beginxling of polygraph for Esample 19.10 Of course, To appears before all real transactions iri any schrtiule, arid Ij ap- pears after all transactions. If we order the real transactions (T.L: T I .T3). then Example 19.10: Consider the schedule S from Example 19.9. \Ire show in the sources of all reads are the same as in schedulc S . That is, T2 reads B, and Fig. 19.4 the beginning of the polygraph f o ~ , where only the nodes and the S surely TOis the previous "15-riter." Tl reads -4; Tz already wrote .-l. so the but arcs fi-om rule (2) have hcen placed. \Ye have also indicated the database source of rl(.4) is T2, as in S . T3 also reads . :but since the prior T.2 \{-rote -4. 4 elemcnt causing each arc. That is, -4 passed from T2to TI. T3.and T f ,while is that is the source of r3(.-l), as in S . Finally, the hypot,hctical Tf reads -4 and B is passed fro111 To to T2 and from T3 to Tf. B j but the last writers of d and B in the sched~le TI, T3) are T2 and T3 rc- (T2: ?;o\v, n.e lllust considel n-hat transactioils might interfere with each of these spectivel!; also as in S . K e conclude that S is a view-serializable scliedule, and five connections by n-~iting same clen~cntbet~vecnthem. These potential the the schedule represented by the order ( f i , I : 3 ) a vien.-cquivaleiit schedule. T T is interferences are ruled out by the arc pairs from rule (3). although as n-e shall see, in this example each of the arc pairs inrolves a special case and becomes a single arc. 19.2.2 Consider the arc & -+ Ti based on eleliler~t The only writers of A are To d. Polygraphs and the Test for View-Serializability and T2.and ncitller of rllem can get in tlie iniddle of this arc: since To cannot Therc is a gcneralization of the precedence graph. ivhicll n-c, iiscd to tcst co11- move its posirioll. and T2 is already an a i d of the arc. Thus. 110 additional arcs flict scri;ilixal~ility Section 18.2.2. that reflects all thc prcc.odcncc, constrai~lts in are needed. ;\ sinlilar argurntnt tells us no additional arcs are needed to keep required 1))- thc dc~finitionof vicn- scl.ializability. \Ye tl(+i~lr) pol!/grclpli for ;i ill(, writers of .-I outside the arcs T2 -+ 7; and T? -t Tf. schedule to consist of the follo~ving: S o ~ rcollsider the arcs based on B. Xote that To. TI. T?. and T3 all n-rite - B. Consider the arc To -+ T2 first. TI and T3 are otlier writers of B: To and T2 1. - node for cach transaction and additional rlodcs for tlic hypothetical 1 B; also ~yrite but as sav,-. the arc ends cannot cause interfererlce. so we need transactions To arid Tf. not consider them. -1s we cannot place TI bet\\-een To and T2,in principle \re need tlic arc pair (TI -+ To T.r -+ T I ) . Honever. nothing can precede To, so 2. For each action r , ( S ) with source T,. place an arc froni T, to T,. the optioll TI -+ To is not possible. \Ye may in this special case just add the Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 14. 1006 CHAPTER 19. AIORE ABOUT TRANS24CTION AM-TAGEJIENT arc T2 -+ Ti to the polygraph. But this arc is already there because of .4,so in 1" 19.2. 1-IETV SERI-4LIZdBILITY 1007 that need be considered as Tk (the transaction that cannot be in the middle) effect, we make no change to the polygraph to keep Ti outside the arc To -+ T2. are: We also cannot place T3 between To and T2. Similar reasoning tells us to add the arc Tz -+ T3,rather than an arc pair. However, this arc too is already \Vriters of a n e!ement that caused this arc T, -+ T,. in the polygraph because of A, so we make no change. ivext, consider the arc T3 -+ T f . Since To, T I ,and Tz are other writers of But not To or T f ,15-hich can never be Tn.. and B, we must keep them each outside the arc. To cannot be moved between T3 S o t Ti or T,, the ends of the arc itself. and T f : but TI or Tz could. Since neither could be moved after T f . r e must constrain Ti and T.L to appear before T3. There is already an arc Tz -+ T3, but \\*it11 these rules in mind. let us co~lsiderthe arcs due to database element .4. we must add t o the polygraph the arc Tl -+ T3. This change is the only arc we \\-l-hich is xritten by To. T3. and T4. \Ye need nut consider To a t all. T3 must must add to the polygraph, whose final set of arcs is shown in Fig. 19.5. not get between T4 -+ T f . so \ve add arc T3 -+ T4; remember that the other arc in the pair, T f + T3 is not an optiotl. Likewise, T3 must not get between To -+ Tl or To -+ T 2 ,tvhich results in the arcs TI -+ T3 and T2 -+ T3. Figure 19.5: Complete polygraph for Example 19.10 Example 19.11 : In Example 19.10, all the arc pairs turned out to be single arcs as a special case. Figure 19.6 is an example of a schedule of four transac- tions where there is a true arc pair in the polygraph. Figure 19.7: Beginning of pol\-graph for Example 19.11 Sou-, coilsider the fact that T4 also must not get in the middle of an alc due to -4.It is all end of T4 -+ T f . so that alc is irrelevant. TI must not get b e t ~ ~ e e n -+ TI or To -+ T? n-hicli ~ e s u l t s the arcs TI T4 and ir?2 4 T4. To in S e s t . let us consider the arcs due to B. nhich is w i t t e n by To,T1,and T4. 7-3(C); .igain we need not consider To. The only arcs due to B are T I -+ T?, T I -+ T4, wl ( B ) ; and T4 -t T f . Tl cannot get in the middle of the first t ~ obut the third requires , 7-4 (B): arc Tl -t T4. U'3 (A) : T4 can get in the middle of TI -+ fi only. This arc has neither end a t To T4 (C); or Tf: SO it really requires an arc pair: (7.1 -+ T I , Tz -+ T4). We show this arc w (0): ( B ) ; 2 7-2 pair, as well as all the other arcs added, in Fig. 19.8. w4(.4);u:4(B); Test. consider the writers of C: To and Ti. -1s before, To cannot present a problem. -41~0, I is par[ of el-ery arc due to C'. 50 it cannot get in the middle. T Similarl\-. D is ~ ~ r i t t e n by To and f i . so n-c can dctcrmine that no Inore only Figure 19.6: Esample of transactions whose polygrapl~requires an arc pair arcs are nccessar): The final j ~ o l ~ g r a p h thus the one in Fig. 19.8. is Figuie 19.7 sho\vs the polygraph, with only the arcs that conle fiolil the source-to-reader connections. .As in Fig. 19.4 we label each arc by the element (s) that require it. We must then consider the possible ways that arc pairs could i 19.2.3 Testing for View-Serializability Since we must choose only one of each arc pair. we can find an equivalent serial be added. As we saw in Example 19.10, there are several silnplifications Ive can order for schedule S if and onl? if there is son-he selection from each arc pair make. \Then avoiding interference with the arc T, -t T,, the only transactiol~s that turns S's polygraph into an acyclic graph. TO see why, notice that if there Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 15. 1008 CHAPTER 19. MORE ABOUT TRAA'SACTION ~fAX.4GEJ1EAJT C) r1(.-l):) : L -(B): rd(B): u3(B); r3(D Z ~ r4(B): 1 b ( C ) : rs(C): w 4 ( ~ ) r j ( ~ ) ; ; 1LV5(B): ! Exercise 19.2.2 : Below are solne serial schedules. Tell 1io1v many schedules are (i) coilflict-eqlli\.alcnt and (zi) vie\-;-equivalent to thcse yerial ~ ~ I i ~ d u l ~ s . * a) (-4); (ul(B); ~ ~ ( ~lcq(B); r3('A) w3(B); that is, three transactions 1-1 4 ) ; each read .4 and then write B. b) r l (.A); u)l ( B ) : (C): r3(-4): ulr ( B ) .1r2(C); lC1 that is. t ~ trailsactioris each o read -4 and then write B and C. Figure 19.8: Complete polygraph for Example 19.11 19.3 Resolving Deadlocks is such an acyclic graph, then any topological sort of the graph gives an order in which no writer may appear between a reader and its source, arid every n-riter Several tinles \\-e have obscr\.ed that concurri.ntly e s ~ c u t i n gtransactiorls can appears before its readers. Thus, the reader-source connections in the serial compete for resources and thereby reach a state \\-here there is a dearflock: each order are exactly the same as in S ; the two schedules are view-equivalent, and of several transactions is waiting for a resource held by one of the otllcrs, and therefore S is view-serializable. none call make progress. Conversely, if S is view-serializable. then there is a view-equivalent serial order S' E ~ e r y pair (Tk + T,. T, -t Tk) in S's polygraph niust have arc In Section 18 3.4 \ve saw how ordinaly operation of t~vo-pht~se-locked Tk either before T, or after T, in S': otherw~sethe writing by Tk breaks the transactions can still lead to a deadlock, because each has lockcd sonie- connection from T, to T,, which means that S and Sf are not view-equivalent thing that an0thc.r tral~sactio~i needs to lock. also Likewise every arc in the polygraph must be respected by the transaction order e I11 Scc.tlun 15.-1.3 n e saw how the ab11it)-to 11pgr.idt. loclcs from illarc~rl to of S f . Ke conclude that there is a choice of arcs from each arc pair tliat makes esclusiTe can cause a deadlock because each trdnsaction holds a shared the polygraph into a graph for which the serial order S' is consistent with each lock on the same elerneilt aiid lvarlts to upgrade the lock. arc of the graph. Thus, this graph is acyclic. broad ap1,roaches to dealing u-it11 deadlock. \IF car1 detect There are t ~ v o Example 19.12: Consider the polygraph of Fig. 19.5. It is already a graph. deadlocks and fix tlle~n.or we call manage traiisactio~lsin such a way that and it is acyclic. The only topological order is (T2, TI, T3), which is therefore a deadlocks are never able to form. view-equivalent serial order for the schedule of Example 19.10. Sow consider the polygraph of Fig. 19.8. We must consider each choice from the one arc pair. If we choose T4 -t TI. then there is a cycle. Honever, if we 19.3.1 Deadlock Detection by Timeout choose Tz + T4,the result is an acyclic graph. The sole topological order for \\-hen a deadlock exists, it is genclrally iulpossible to repair the situation so tliat this graph is (Tl.T2, T3, T4). This order yields a view-equivalent serial order all transactions involved can proceed. Thus. at least one of the traiisactio~ls \\-ill and shon-s that the original schedule is vie\\--serializable. C I have t o he rolled back - al~ortcd and rcstartcd. The silllplcsr 1 t - a ~ detect ant1 resolve deadlocks is \\.it11 a tinleo~rt. Pllt to 19.2.4 Exercises for Section 19.2 a limit on lion- long zi tr;rnsac.tio~~ he active. and if a trilnsaction excectls may this tinle. roll it 1,ac.k. For csamplc. in a si~npletransaction q s t c i n . IV\I 16. transactions involved in the deadlock will complete before reaching their timeout limits. However. since transactions involved in a deadlock are likely to have started at approximately the same time (or else, one would have completed before another started), it is also possible that spurious timeouts of transactions that are no longer involved in a deadlock will occur. \Ye use a simple locking system \\-it11 only one lock mode, although the same 19.3.2 The Waits-For Graph effect nould be noted if we were to use a shared/exclusive system and took Deadlocks that are caused by transactions waiting for locks held by another can locks in thc appropriate niode: sharcd for a read and exclusive for a write. be addressed by a waits-forgraph, indicating which transactions are waiting for locks held by another transaction. This graph can be used either to detect deadlocks after they have formed or to prevent deadlocks from ever forming. We shall assume the latter, which requires us to maintain the waits-for graph at all times, refusing to allow an action that creates a cycle in the graph. Recall from Section 18.5.2 that a lock table maintains for each database elenlent X a list of the transactions that are ~i-aitingfor locks on X,as nell as transactions that currently holtl locks on X. The waits-for graph has a node 5) 12(.4): Denied 6) l3 (C); Denied for each transaction that currently holds a lock or is waiting for one. There is /4(z4);Denied an arc from node (transaction) T to node U if there is some database elenleiit 7) 3) ll(B): Denied d such that: 1. li holds a lock on A, Figure 19.9: Beginning of a schedule mith a deadlock 2. T is waiting for a lock on A, and In Fig. 19.9 is the beginning of a scliedule of these four transactions. In the 3. T cannot get a lock on A in its desired mode unless U first releases its first four steps. each transaction obtains a lock on the elenlent it wants to read. lock on .L3 --It step (3), T2 tries to lock .4: but the request is denied because TI already has a lock on -4. Thus: T._, waits for TI: and we draw an arc from the node for T.2 If theie are no cycles in the waits-for graph, then each tiansactioii can to the node for T I . evenrually complete. There will be at least one transactiori u-aiting for no other transaction, arid this transaction snrely can complete. At that tlme. t l i e ~ e will be at least one other transaction that is not waiting, which can complete. and FO 011. Hon-ever. if there is a cycle. then no transaction in the cycle can ever make progress. so there is a deadlock. Thus. a strategy for deadlock avoidance is to roll back any transaction that makes a request that ~vouldcause a cycle in the waits-for graph. Figure 19.10: \Yaits-for graph after step (7) of Fig. 19.9 Example 19.13: Suppose n-e have the following four transactions. each of n-hich reads one element and n-rites another: Similar1)-. at step (6) T3 is denicd a lock on C because of T2. and at step (7). T4 is de~iieti lock on .f because of TI. The waits-for graph a t this point is as a sho\\-n in Fig. 19.10. There is 110 cycle in this graph, 31n common sitnations, such as shared and exclusive locks; every waiting transacrion rvill At step (8). TI nus st wait for the lock on B held by T3. If \re allon-ed TI to have to w i t until all current lock holders release their locks; but there are examples of systems wait. then there ~ o u l d a cycle in the waits-for graph involving Ti. Tz, and be of lock ]nodes where a transaction can get its lock after only some of t h e c~lrrentlocks are T3.as suggested by Fig. 19.11. Since they are each waiting for allother to finish, released: see Exercise 19.3.6. none can iilake progress. and therefore there is a deadlock involving these three Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 17. 1012 CHAPTER 19. 310RE ABOUT TRAArSACTION AIA:\'ilGElIEST 4 19.3. RESOLVIA-G DEADLOCKS 1013 since Tl has a lock on ,A1 while it is waiting for A,, it also f o l l o ~ that ill < A,. s \\re noly have .Al < An < -An-1 < . . . < -42 < .-I1, which is impossible, since it implies A1 < :I1. Example 19.14: Let us suppose elenlents are ordered alphabetically. Then if the four transactions of Examplel9.13 are to lock elelllents in alphabetical order, ?il and T4 must be ren-ritten to lock elements in the opposite order. Thus, the four transactions are noxr: Figure 19.11: Waits-for graph with a cycle caused by step (8) of Fig. 19.9 8- Figure 19.13 shows what happens if the transactions execute ~ v i t h same the timing as Fig. 19.9. TI begins and gets a lock on A. T2 tries t o begin next by Figure 19.12: 1I'aits-for graph after TI is rolled back g e t t ~ n g lock on -4, but must ~vait TI. Then. T3 begills by getting a lock a for on B. but T4 is unable to begin because it too needs a lock on A, for \vhich it transactions. Incidentally, T4 could not finish either, although it is not in the must wait . cycle. because T4's progress depends on TI making progress. Since we roll back any transaction that would cause a cycle, then TI must T4 TI Tl T3 be rolled back, yielding thc waits-for graph of Fig. 19.12. TI relinquishc~sits 1) il(&4):rl(-4): lock on A, which may be given to either T2 or Ti. Suppose it is given to T2. Then T2 can complete. n-hereupon it relinquishes its locks on .4 and C. Tow T3. 2 l2 (A): Denied 13(B):r3(B): which needs a lock on C, and T4, which needs a lock on 21, call both complete. 3) 14(d); Denied At solne time, Tl is restarted, but it cannot get locks on .4 and B until T2. T 3 . and T4 have completed. 19.3.3 Deadlock Prevention by Ordering Elements Sow. let us consider several more methods for deadlock prevention. The first requires us to order database elements in some arbitrary but fixed order. For instance, if database elements are blocks, Ive could order them lexicographically by their physical address. Recall from Section 8.3.4 that the physical address of a block is normally represented by a sequence of bytes describing its locntioll trithin the storage sl-stem. If cvcry transaction is required to request locks on elenicnts in order ( a con- dition that is not realistic in no st applications), then there can be no deadlock Figure 19.13: Locking elenlentc in al~llnleticalorder prevents deadlock due to transactions waiting for locks. For suppose T2 is waiting for a lock on .-I1 held by T I ;T3 is waiting for a lock on -42 held by T 2 ,and so on, while T,, Since r.) is stalled, it cannot proceed, and follo\ving the order of events in is waiting for a lock on An-1 held by Tn-l, and Tl is xvaiting for a lock on .4, Fig. 109. T3 gets a turn next. It is able to get its lock on C. whereupon it held by T,,. Since 2'2 11% a lock on -42 but is waiting for .AI, it nlust be that conipletes at step (6). Soi\-. iviilr T3's locks on B and C released. TI is able .-I2 < -41 in t'lie order of eleulents. Similarly, < for i = 3 , 4 , . . . ;n. But to co~nplete.which it does a t step (8). At this point. the lock on -4 becomes Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. 18. 1014 CHAPTER 19. XORE ABOUT TR.4ArSACT10i\' JIANAGEJIEYT available, and we suppose that it is given on a first-conie-first-served basis t o T2. Then, T2 can get both locks that it needs and completes a t step (11). Finally. T4 can get its locks and completes. 19.3.4 Detecting Deadlocks by Timestamps 2 l?(.A); Dies \re can detect deadlocks by maintaining the waits-for graph, as we discussed 3) 13(B): r3(B): 14(-4): D i e s in Section 19.3.2. Ho~vever,this graph can be large, and analyzing it for cj-cles 4) each time a transaction has to wait for a lock can be time-co~isuming.An alter- 5) 13(C): w3(C): native to maintaining the waits-for graph is to associate with each transaction 6) US(B):1~3(C); a timestamp. This timestamp: Is for deadlock detection only; it is not the same as the timestamp used for concurrency control in Section 18.8,even if timestamp-based concurrency 12(=1);Waits control is in use. r4(D): 7c4(.4); T14(*4):11.,(D); In particular, if a transaction is rolled back, it restarts with a new, later 12 (-4);1 (c); 2 concurrency timestamp, but its timestamp for deadlock detection never T . (C); ~ t~'2(.4); changes. ~1 : t f 2 (C) (--I) ; The timestamp is used when a transaction T has to wait for a lock that is held by another transaction U.Two different things happen. depending on Figure 19.14: .Ictions of transactions detecting deadlock under the wait-(lie whether T or U is older (has the earlier timestamp). There are two different schenie policies that can be used to Inanage transactions and detect deadlocks. 1. The Wait-Die Scheme: TI T2 T3 T4 1) 11(-4): rl(-4): (a) If T is older than U (i.e.. the timestamp of T is smaller than L*'s timestamp), then T is allo~ved xait for the lock(s) held by U. to 2) l2(A); Waits 3) 13(B): r ~ ( B 1 ; (I)) If li is older than T , then T .'dies": it is rolled back. 1/\ - l4(-4): Waits 5) l1 (B): (B): Wounded 2. The iifound- Wait Scheme: 6) TL (-4): u 1(B): (a) If T is older than CT, it .'wounds" C . Usually. the "wound" is fatal: 7) 1*(.4): 1 (C): 2 C' must roll back and relinquish to T the lock(s) that T needs from 8) r2(C): lC2 (-4); U. There is an csception if, by the time the "nound" takes effect. C u2(:l): 112 ( C ) : 1 (-4): 1, ( D l : 4 has already finished and lcleased its locks. In that case. C' survives r4( D ) : 1 1 ' (-4): ~ and need riot be rolled back. u4(-4): u , ( D ) : (b) If C' is older than T. then T waits for the lotk(s) held by IT I i ( B ) :r < ( D ) : I : ( C ) :u.i(C): E x a m p l e 19.15 : Let us consider the wait-die schcmc. using the transactions T.$. of Esalnple 19.14. \Ye shall assume that T17T2: T4 is the order of times: i.e.: 11,3(B): ~(c): Tl is the oldest transaction. lye also assume that ~vhen transaction rolls back. a it does not restart soon enough to become active before the other transactions Figure 19.15: Actions of transactions detecting ticadlock tnldcr the I\-ound-wait finish. sclle~ile Figure 19.14 sho\x-s a possible sequence of events under the wait-die schcme. TI gets the lock on .4 first. \Yhen T2 asks for a lock on 4, it dies; because TI Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.