Database Systems: The Complete Book- P11

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

0
67
lượt xem
7
download

Database Systems: The Complete Book- P11

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ủ đề:
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.
  8. 19.1. SERI.4LIZABILITY AJ-D R E C O \ ~ E R . ~ ~ ~ L ~ ~ - 9% 9914 CYL4PTER 19. AfORE ABOUT TIZAh-SACTION h I I A 1 7 . ~ ~ ~ ~ f ~ h r ~ 19.1.5 Managing Rollbacks Using Locking Rollback for Blocks Our prior discussion applies to schedules that are generated by any kind of If the lockable database elements are blocks. then there is a simple rollback scheduler. In the common case that the scheduler is lock-based, there is a simple method that never requires us to use tile log. Suppose that a transaction T has and commonly used way to guarantee that there are no cascading rollbacks: obtained an esc1usi~-e lock on block A. written a new value for A in a buffer, and then had to abort. Since -4has been locked since T xvrote its value, 110 Strict Locking: % transaction must not release any exclusive Iocks (or . other transaction has lead -4. I t 1s easy to restore the old value of -4 provided other locks, such as increment locks that allo~irvalues to he changed) the folloning rule is follo~ved until the transaction has either con~mitted aborted, and the commit or or abort log record has been flushed to disk. Blocks ~vritten uilcominittcd transactiolls are pinned in main memory; by that is. their buffers are not alloxved to be written t o disk. A schedule of transactions that follow the strict-locking rule is called a strict schedule. Two important properties of these schedules are: I11 this case. n e ..roll back.' T when it aborts by telling the buffer manager to ignore the value of A. That is, the buffer occupied by -4 not written anywhere, is 1. Every strict schedule is ACR. The reason is that a transaction T2 cannot and its buffer is added to the pool of available buffers. \Ve call be sure that the read a value of element X written by TI until Ti releases any exclusive value of A on disk is the most recent value written by a committed transaction, lock (or similar lock that allolvs X to be changed). Under strict locking, which is c ~ a c t l y value we want A to have. the the release does not occur until after commit. Tllele 1s also a sinlple rollback method if we are using a multiversion system 2. Every strict schedule is serialzzable. To see why, ohscrve that a strict as in Sections 18.8.5 and 18.8.6. \Ye niust again assume that blocks written by schedule is equivalent to the serial schedule in which each tra~isaction ~incomniittedtransactions are pinned 111 memory. Then, we simply renlove the runs instantaneously at the time it commits. value of A that was m i t t e n by T from the list of available values of A. S o t e that because T was a i\iiting transaction, its value of . ~ v a s I locked from the IVith these observations, we can now picture the relationships among the dif- time the lalue n.as \vritten to the time it aborted (assuming the timestamp/lock ferent kinds of schedules we have seen so far. The containments are suggested scheme of Section 18.8.6 is used). in Fig.19.3. Rollback f o r Small D a t a b a s e E1ement.s When lockable database elenlcnts are fractions of a block (e.g., tuples or oh- ~ e c t s )then the sinlple appioach to restori~lg . buffels that have been ~nod~fied hl- aborted transactions nil1 not uoik The p ~ o h l e ~ nthat a buffer may contain is data changed by t ~ v o more transactions: if one of them aboits, Tve still nlust or plesesve tlie changes made by the other \ l e have several choices \vhen we must restore thc old value of a small database element A that n-as written by the tlansaction that has a11ortt.d. 1. We can read the original value of .-I the database stored on disk and from modify the buffer contents appropriately. Figure 19.3: Containments an noncontai~lments among classes of schetlules 2. If the log is an undo or untlo/redo log. then we can obtain the former value from the log itself. The same code used t o recover frorn crashes Clearly. in a strict schedule. it is not possihle for a transaction to rcad dirty ma?. be used for ..\-oll~ntary" rolll~acksas \~-cll. data. since data written to a huffer by an unconilnitted transaction re~nairls 3. \IF can keep a separare ~nair~-l~lclr~ory the changes n ~ a d e car11 log of by locked until the transaction commits. Ho~vever:we still have tlie prohleni of transaction, preserved for only the tinlc that transactio~l active. The is fising the data in buffers when a transaction aborts, since these cllallges must I old value call be fouxid fro111 this "log." have their effects cancelled. How difficult it is to fix buffered data depellds on i ~vhether database elements are blocks or sornethi~lgsmaller. \Ye shall consider Sone of these approaches is ideal. The first s ~ ~ r e l y il~rolvesa disk access. each. The second (examining the log) might not involve a disk access. if the relevant Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
  9. 996 CHAPTER 19. MORE ABOUT TRAATSACTION JlilA-~lGE:lIEXT When is a Transaction Really Committed? 2. TI is comnlitted. but T2 is not. There is no problerri for two reasons: T2 The subtlety of group commit reminds us that a completed transaction can did not read S from an uncomlnitted transaction, and it aborted anyway. be in several different states between when it finishes its xvork and when it with no effect on the database. is truly "committed." in the sense that under no circumstances, including 3. Both are corrnnitted. Then the read of S by Tz was not dirty. the occurrence of a system failure, will the effect of that transaction be lost. As we noted in Chapter 17, it is possible for a transaction to finlsh On the other hand, suppose that the buffer containing Tz's commit record its work and even write its COMMIT record to the log in a main-memory got flushed to disk (say because the buffer manager decided t o use the buffer buffer, yet have the effect of that transaction lost if there is a system crash for somet11i1:g else). but the buffer containing TI'Scommit lecord did not. If and the COMMIT record has not yet readied disk. Lloreover, we saw in there is a crash a t that point. it will look t o the recovery manager that TI did Section 17.5 that even if the COMMIT record is on disk but not yet backed not commit, but T2 did. The effect of T2 will be perlrianently reflected in tlie up in the archive, a media failure can cause the transaction to be undone database, but this effect was based on the dirty read of X by T2. and its effect to be lost. In the absence of failure, all these states are equivalent, in the sense Our conclusion from E s a ~ n p l e 19.5 is that we can release locks earlier than that each transaction will surely advance from being finished to having its the time that the transaction's commit record is flushed to disk. This policy, effects survive even a media failure. However, when rve need to take failures often called g i a z p commit. is: and recovery into account, it is important to recognize the differences Do iiot release locks until the transaction finishes: and the comniit log among these states, which otherwis'e could all be referred to informally as record at least appears in a buffer. 'L~ommitted." Flush log blocks in the order that they \\-ere created. Group commit. like the policy of requiring .'recoverable schedules" as discussed portion of the log is still in a buffer Hone1 er. it could also invol~ extensix e e in Section 19.1.3, guarantees that there is never a read of dirty data. esamination of portions of the log on disk. sea~ching the update record that for tells the correct former value. Tlie last approach does not require disk accesses. but may consume a large fraction of menioi y for the main-memory '.logs." 19.1.7 Logical Logging We salv in Section 19.1.5 that dirty reads are easier to fs up rvhen the unit of i 19.1.6 Group Commit locking is the block or page. Holvever, there are at least two problems prese~lted when database elements are blocks. Under some circumsta~ices, can avoid reading dirty data even if r e do not n-e flush every commit record on the log to disk immediately. As long as a-e flush 1. -411 logging methods I-equirc either the old or new value of a database log records in the order that they ale written, we can release locks as soon as element, or both: to be recorded in the log. \Vhen the change to a block tlle commit record is written to tlie log in a buffer. is small, e.g., a ren-rittcri attribute of one tuple. or an inserted or deleted tuple, then there is a great deal of redundant information written on tile Example 19.5: Suppose transaction TI I\-rites X , finishes, writes its COMMIT log. record on the log, but the log record remains in a buffer. Even though TI has not committed in the sense that its connilit record can survive a crash. 2. Tlie recluireme~itthat the schedule be recoverable; releasing its locks only we shall release TL's locks. Then T2 reads S and .'colnmits." but its c o ~ n n ~ i t after co~nnlit.car1 illhibit concurrency severely. For esample, recall our record, n-hicli follows that of TI. also remains in a buffer. Since we are flushing discilssion in Section 18.7.1 of the advantage of early lock release as xr log records ill the order 1s-ritten. T2 cannot be perceived as co~nmittcdb?- a access data tllro,lgll a B-tree indes. If we require that locks be helti until recovery manager (because its commit record reached disk) unless Tl is also connnit. thcn this advalitagc cannot be obtained: and n-e effectively allon- perceived as committed. Thus, there arc three cases that the recovery manager only one writing transaction to access a B-tree at any time. could find: Both these concerns motivate the use of logical logging. villere only the 1. Neither TI nor T.L has its commit record on disk. Then both are aborted by changes to the blocks are described. There are several degrees of coniplesity. the recovery manager, and the fact that T2 read S from an uncommitted depending on the nature of the change. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
  10. 1. .A small rlunlber of bytes of the database element are changed, e.g.. the As 101ig as the block and its o\.erflow block(s) are considered part of one update of a fixed-length field. This situation call be handled in a straight- database cl~inent, then it is straightforward to use the old and/or new value of forward way, where we record only the changed bytes and their positions. tlic changed field to tundo or redo the change. Ho~vever, block-plus-overflox~~- the Example 19.6 \rill show this situation and an appropriate form of update bloik(s) must l ~ thougilt of as holding certain tuples a t a "lo@cal" level 1Ve e record. nlay not even be able to restore the bytes of these blocks to their original state after an undo or redo, because there nlay have been reorganization of the blocks 2. The change to the database element is simply described; and easily re- due t o othcr cliarges that varied the length of other fields. Holvever. if we think stored, but it has the effect of cliangiiig most or all of the bytes in the of a database ele~nentas being a collection of blocks that together represent database element. One coninion situation: discussed in Example 19.7: is certain tupleb. tile11 a redo or undo can indeed restore the logical *state" of the when a variable-length field is changed and illuch of its record, and even eleme~it. O other records must slide within the block. The new and old values of the block look very different unless we realize and indicate the simple cause Hoxvever, it ]nay not be possible, as we suggested in Example 19.7, to treat of the change. blocks as expandable through the mechanis~ll overflow blocks. IVe nmay thus of 3. The change affects many bytes of a database clement, and further changes be able to undo or redo actions only a t a level higher than blocks. The next call prevent this change from ever being undone. This situation is true esample discusses the important case of B-tree indexes, nhere the management "logical" logging, since we cannot even sec the undo/rcdo process as occur- ' of blocks does not perinit ove~flowblocks, and we must think of undo and redo ring on the database elenieilts thetiiselves, hut rather on some higher-level as occuiring a t the ..logical.. level of the B-tree itself; rather tllan the blocks. '.logical" structure that tlie database elenletits represent. 1 shall, in Es- % Example 19.8 : Let us consider the problem of logical logging for B-tree nodes. ample 19.8, take up the matter of B-trees, a logical structure represe~ited Instead of xvriting the old and/or new value of a n entire node (block) on the by database clements that are disk blocks, t o illustrate this co~rlples form log. we n-rite a short record that describes the change. These changes include: of logical logging. Example 19.6 : Suppose database elements are blocks that each contain a set 1. Insertion or deletion of a key/pointer pair for a child. of tuples from some relation. 11'e call express the update of an attribute by a 2. Change of the key associated \x-it11 a pointer log record that says somethirig like .'tuple t had its attribute a changed f r o ~ n vahie ~ ' 1 02.'' An insertion of a nerv tuple into empty space on the block can to 3. Splittirig or ~rlergingof nodes. be expressed as "a tuple t with value (nl.a 2 : .. . : a k ) was inserted beginning at offset position p." Unless the attribute changed or the tuple inserted are Each of these changes call be indicated with a short log record. Even the comparable in size t o a block, the alnount of space taken by these records will splittin: operation requires only telling xvhere t,he split occurs; and ivhere tahe be much smaller than the entire block. lloreot-er, thcy serve for both undo and iiex lodes are. Likewise: merging requires only a reference to the nodes in- redo operations. volved; since rhe manner of rnergirlg is determined by the B-tree rnallagenlent Notice that both these operations are idernpotent; if you perform them scv- algorithms used. csillg logical iljii!at~ rerorris of these tj-pesalloirs us to release locks earlier era1 tinlcs on a block; the result is the same as perfor~ning them once. Liken-ise. thcir implied inrerses, I\-here the value of t [ n ] is restored from vz back to 1.1. or than xrould othern-ise be required for a recoverable schedule. The reasoil is the tuple t is removed. are also idenrpoteiit. Thus. records of these types can that d i r t - reads of B-tree blocks are never a problem for the transaction that be used for rccol-cry in exactly tlie same way that update log rccords were used reads tl~ein.provided its only purpose is to use the B-tree t o locate the data throughout Cliaptcr 17. 0 the transaction needs to access. T For instance. suppose that tra~lsactioll reads a leaf node dY. the trans- but Exanlple 19.7: Again assunic database clc~nentsarc blocks lioldiiig t l ~ p l c . action c- tilat 1a.t wrote -\- lates aborts. and sorne change nlade to S (e.g.; the but the tul~lesIlavc sonie rariahle-lengtil ficlds. If a c l l t ~ ~ ~ g a f i ~ l d to e such as illscrrioll of a nelr keT/lloillter pair into due to a n insertion of a tuple b\. Ivas described in Exalilple 19.6 occurs, n.e niay 1la1-e to slide large portio~ls of liceds to be undone. If T has also inserted a key/poi~~ter into S.then it is pair the block to make room for a longer field. or to preserve space if a ficld beco~~ics liot possiMe to restore ' to the !ray it was before L inodified it. Hoxevcr. tlie . T smaller. In extreme cases, ~ v ecould have to crcatc ail overfloxr block (1.c~cal1 effect of L- on -\- be undone; in this exa~nple would delete the key/pointer call n-e Section 12.5) to hold part of the contents of the original block, or wc could pair that C had iiiscrted. Tlie resulting 5 is riot the same as that irllich ex- remove an ovc.rflo\v block if a shorter field allows us to combine the contenrs of isted before U operated: it has the i~lsertionmade by T. Hon-ever, there is no two bl~clis into one. database inconsistency. siilcc the B-tree as a ivhole continues to reflect only the Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
  11. 1000 CHa4PTER 19. MORE ABOUT TRAA7S.4CTION AlANrlGEJlEl-T 19.1. SERMLIZ.4BILITY A N D RECOVERABILITY changes made by committed transactions. That is, we have restored the B-tree If a transaction T aborts, then for each action performed or1 the database a t a logical level, but not at the physical level. by T, the compensating action is performed, and the fact that this action was performed is also rccorded in the log. 19.1.8 Recovery From Logical Logs Each block maintains, in its header, the log sequence number of the last action that affected that block. If the logical actions are idempotent - i.e.. they can be repeated any number of times without harm - then we can recover easily using a logical log. For Suppose noxv that we need t o use the logical log to recover after a crash. instance, we discussed in Example 19 6 how a tuple insertion could be repre- Here is an outlirie of tlle steps to take. sented in the logical log by the tuple and the place within a block where the tuple was placed. If we write that tuple in the same place two or more tune5 1. Our first step is to reconstruct the state of the database at the time of the then it is as if we had written it once. Thus. when recovering, should \ve need crash. including blocks xvhose current values were in buffers and therefore to redo a transaction that inserted a tuple, we can repeat the insertion into got lost. To do so: the proper block at the proper place, without worrying whether me had a l r e a d ~ (a) Find the most recent checkpoint on the log, and determine frorn it inserted that tuple. the set of transactions that nere active a t that time. In contrast, consider a situation ishere tuples can move around withi11 blocks (b) For each log entry , compare the log sequence number or between blocks, as in Examples 19.7 and 19.8. Sow, we cannot associate a IV on block B with the log sequence number L for this log record. particular place into which a tuple is to be inserted; the best we can do is place If V < L, then redo action A: that action was never perfornled on ! in the log an action such as '.the tuple t was inserted somewhere on block B.. block I?. However, if N 2 L. then do nothlng; the effect of '4 was If we need to redo the insertion of t during recovery, we may ~r,iildup with t n o already felt by B. copies o f t in block B. W'oise, we may not know whether the block B 1vit11 tlle first copy o f t made it to disk. Another transaction writing to another database (c) For each log entry that informs us that a transaction T started, com- element on block B may have caused a copy of B t o be written to disk. for mitted, or aborted, adjust the set of active transactions accordingly. example. 2. The set of transactions that remain active .evllcn .se reach the end of the To disambiguate situations such as this ~vhen recover using a logical log. we log must be aborted. To do so: a technique called log sequence numbers has been developed. (a) Scan the log again, rhis time from the end back to the plel-ious check- Each log record is g i ~ e n number one greater than that of tlle previous a point. Each time we encounter a record for a transac- log record.' Thus, a typical logical log record has the form . I tion T that must be aborted. perfor111 the compensating action for where: -4 on block B and record in the log the fact that that compensatillg action was performed. - L is the log sequence number, an integer. (b) If we must abort a tiansaction that began prior to the most recent - T is the transaction involved. checkpoint (i.e., that transaction was on the active list for the check- p i l l t ) . then continue back in the log until tile start-records f o ~ all - A is the action performed by T. e.g., "insert of tuple t." such trailsactions have been found. - B is the block on which the action was performed. (c) Write abort-records in the log for each of the transactions we had to abort. For each action, there is a cornpensating action that logically undoes the action. -4s discussed in Esample 19.8. the compensating action niny not restore the database to exactly the same state S it ~vouldliar-e I ~ c c ~ l in 19.1.9 Exercises for Section 19.1 had the action never occurred, but it restores the database to a statc that * Exercise 19.1.1 : Consider all \\-ays to insert locks (of a single type only. as in is logically equivalent to S. For instance, the compensating action for Section 18.3)into the sequellce of actiorls "insert tuple t" is "delete tuple t." ' ~ v e n t u a l l yt h e log sequence numbers must restart a t 0; but the time hetween restarts of the sequence is so large that no ambiguity can occur. so that the transaction TI is: 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.
  19. 1016 CH.4PTER 19. JIORE ABOUT TR=II\~SACTION AIIAh'AGEIIEYT 19.3. RESOLVISG DEADLOCKS 1017 starvation; if extra measures are not taken, a transaction could repeatedly start, Why Timestamp-Based Deadlock Detection Works get in\-olved in a deadlock, and be rolled back. See Exercise 19.3.7. There is, however, a subtle difference in the way wait-die and wound-wait be- We claim that in either the wait-die or wound-wait scheme, there can be have. In wound-nait, a newer transaction is killed whenever a n old transaction no cycle in the waits-for graph, and hence no dcadlock. Suppose other- asks for a lock held by the newer transaction. If \ve assume that transactions wise; that is. there is a cycle such as TI -+ T2 -+ T3 -+ TI. One of the take their locks near the time that they begin, it will be rare that an old trans- transactions is the oldest, say T?. action was beaten to a lock by a new transaction. Thus, we expect rollback to In the wait-dic scheme, you can only wait for younger transactions. be rare in wound-wait. Thus, it is not possible that TI is waiting for TI, since T2 is surely older On the other hand, when a rollback does occur, wait-die rolls back a trans- than TI. In the wound-wait scheme, you can only wait for older transac- action that is still in the stage of gathering locks, presumably the earliest phase tions. Thus, there is no way Tl could be 11-aiting for the younger T3. \Ye of the transaction. Thus, although wait-die Inay roll back more transactions conclude that the cycle cannot exist, and therefore there is no deadlock. than n-ound-xait, these transactions tend to have done little work. In contrast, when ~vound-~i-ait roll back a transaction, it is likely to have acquired its does locks and for substantial processor time to have been invested in its activity. is older than T2. In step (3), T3 gets a lock on B, but in step (4). T asks for4 . Thus. either scheme may turn out to cause more wasted work, depending on the population of transactions processed. a loclc on d and dies because TI, the holder of the lock on A, is older than T4. Sext, T3 gets its lock on C and conlpletes. n'hen Tl continues, it finds the lock We sliould also consider the advantages and disadvantages of both wound- on B available and also completes at step (8). n-ait and wait-die xhen compared with a straightfor\vard construction and use Sow, the two transactions that rolled back - T2 and T4 - start again. of the waits-for graph. The important poi~lts are: - Their timestamps as far a deadlock is concerned, do not change: T2 is still s Both wound-wait and wait-die are easier to implement than a system older than T4. Honever, XT-e assume that T4 restarts first, at step (9). and when that maintains or periodically constructs the waits-for graph. The disad- the older transaction T.L requests a lock on .-I a t step ( l o ) , it is forced to n-ait. vantage of constructing the waits-for graph is even more extreme when but does not abort. Ti completes a t step (12), and then TI is allov-ed to run to the database is distributed. and the naits-for graph must be constructed completion, as slion-n in the last three steps. from a collection of lock tables a t different sites. See Section 19.6 for a discussion. E x a m p l e 19.16: Sext, let us consider the same transactions running urlder the 11-ound-wait policy, as shown in Fig. 19.15. As in Fig. 19.14, Tl begins by Lsing the waits-for minimizes the number of times we must abort locking .-I. When T2 requests a lock on .-I at step (2); it waits, since Tl is older a transaction because of deadlock. fi never abort a transaction unless than T2. After T3 gets its lock on B a t step (3), T4 is also made to wait for the there really is a deadlock. On the other hand. either wound-wait or wait- lock on .a. die will solnetimes roll back a transaction when there a-as no deadlock. Then, suppose that TI cont,inues a t step (5) with its request for the lock on and no deadlock 11-ould have occurred had the transaction been allo~ved B. That lock is already held by T3; but Tl is older than T3. Thus, TI .'wounds'- t o survive. T3. Since T3 is riot yet finished, the rvound is fatal: T3 relinquishes its lock and rolls back. Thus; TI is able to complete. 19.3.6 Exercises for Section 19.3 \\:hen Tl makes the lock on . available, suppose it is given to T2. n-hich 1 is thcn a l ~ l e procccd. After T2, the lock is given to T4:which proceeds to to Exercise 19.3.1: For each of the sequences of actions belorv. assume that coniplction. Finally. T3 restarts and co~llpletcs ~vithoutinterference. shared locks are requested immediately hcfore each read action. and exclusive locks are lequested immediately heforc every \\-rite action. .ilso, unlocks occur imnlediately after the filial action that a transaction executes. Tell what actions 19.3.5 Comparison of Deadlock-Management Met hods are denied, and nhether deadlock occurs. Also tell holv tlie waits-for graph In both the nait-die and n-ound-wait schc~n~es, older transactions kill off newer evolves during the executioll of the actions. If there are deadlocks, pick a transactions. Since tra~isactions restart ivith their old timestamp. eventually transaction to abort, and show how the sequence of actions continues. each trallsaction becomes the oldest In tlie system and is sure to complete. This guarantee. that every transaction eventually completes. is called n o starvat~orl Xotice that otllcr schcnles described in this scction do not necessarily prevent Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
  20. 1018 CHAPTER 19. IWORE ABOUT TRANSACTION MANAGE-\IEATT 19.4. DISTRIBUTED DATABASES 1019 2. Since data may be replicated a t several sites, the system may not hare to stop processing just because one site or component has failed. Exercise 19.3.2 : For each of the action sequences in Exercise 19.3.1, tell n-hat On the other hand, distributed processing increases the complexity of every happens under the wound-wait deadlock avoidance system. .Assume the order of aspect of a database system, so we need to rethink how even the most basic deadlock-timestamps is the same as the order of subscripts for the transactions, components of a DBMS are designed. In many distributed environments, the that is, Tl,T2, T3,T4. Also assume that transactions that need to restart do so cost of communicating may dominate the cost of processing, so a critical issue in the order that they were rolled back. becomes how many messages are sent. In this section we shall introduce the principal issues, while the next sections concentrate on solutions to two impor- Exercise 19.3.3 : For each of the action sequences in Exercise 19.3.1, tell tant problems that come up in distributed databases: distributed commit and what happens under the wait-die deadlock avoidance system. Make the same distributed locking. assumptions as in Exercise 19.3.2. ! Exercise 19.3.4: Can one have a waits-for graph with a cycle of length n, but 19.4.1 Distribution of Data no smaller cycle, for any integer n > l ? What about n = 1, i.e., a loop on a One important reason to distribute data is that the organization is itself dis- node? tributed among many sites, and the sites each have data that is germane pri- marily to that site. Some examples are: !! Exercise 19.3.5 : One approach t o avoiding deadlocks is to require each trans- action to announce all the locks it wants a t the beginning, and t o either grant 1. A bank may have many branches. Each branch (or the group of branches all those locks or deny them all and make the transaction wait. Does this ap- in a given city) will keep a database of accounts maintained a t that branch proach avoid deadlocks due to locking? Either explain why, or give an example (or city). Customers can choose t o bank a t any branch, but will normally of a deadlock that can arise. bank a t "their" branch, where their account data is stored. The bank ! Exercise 19.3.6: Consider the intention-locking system of Section 18.6. De- may also have data that is kept in the central office, such as employee scribe how to construct the waits-for graph for this system of lock modes. Espe- records and policies such as current interest rates. Of course, a backup of cially, consider the possibility that a database element A is locked by different the records a t each branch is also stored, probably in a site that is neither transactions in modes IS and also either S or Ix. If a request for a lock on '. 1 a branch office nor the central office. has to wait, what arcs do we draw? 2. A chain of department stores may have many individual stores. Each *! Exercise 19.3.7: In Section 19.3.5 we pointed out that deadlock-detection store (or a group of stores in one city) has a database of sales a t that methods other than wound-wait and wait-die do not necessarily prevent star- store and inventory a t that store. There may also be a central office vation, where a transaction is repeatedly rolled back and never gets to finish. with data about employees, chain-wide inventory, credit-card customers, Give an example of how using the policy of rolling back any transaction that and information about suppliers such as unfilled orders. and what each ~vouldcause a cycle can lead to starvation. Does requiring that transactions is owed. In addition. there may be a copy of all the stores' sales data in request locks on elements in a fixed order necessarily prevent starvation? \That a "data warehouse." which is used to analyze and predict sales through about timeouts as a deadlock-resolution mechanism? ad-hoc queries issued by analysts: see Section 20.4. 3. A digital library may consist of a consortium of universities that each hold 19.4 Distributed Databases on-line books and other documents. Search a t any site xvill examine the catalog of documents available a t all sites and deliver an electronic copy We shall now consider the elements of distributed database systems. In a dis- of the document to the user if any site holds it. tributed system, there are many, relatively autonomous processors that may participate in database operations. Distributed databases offer several oppor- In some cases, what we might think of logically as a single relation has tunities: been partitioned among many sites. For example, the chain of stores might be imagined t o have a single sales relation, such as 1. Since many machines can be brought to bear on a problem, the opportu- nities for parallelisn~and speedy response to queries are increased. Sales(itern, d a t e , p r i c e , purchaser) Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Đồng bộ tài khoản