Transaction Management properties - Schedules - Serializability - Concurrency Control - Two-phase esaction cOncEPIS ~ .. Dec.-14,., Transaction Concepts .... .. May-14,18,19, Properties ... .. Dec.-11,19, May-14,18.... Transaction States... Schedules .. May-15,18,19 .. Serializabilty . Concurrency Control .. May -19. Need for Concurrency .... . May-17,19, .. Locking Protocol .. Dec.-15,17, May-16,. Two-Phase Locking Techniques.... .. Dec.-11,16,19, May-14,18... Z Two Marks Questions with Answers (4-1)2200 Ma Database De mnagemont a ‘ge Ed Transaction Concopts COTTE vd asa group of tasks that tion can be define jon: A tran SBI gy For example - ant to withdraw & 100 from an account then we follow following operation 1) Check account balance is present request for withdrawal, Suppose we W : wil) 2) Ifsufficient balance 3) Get the money 4) Calculate Balance = Balance 100 5) Update account with new balance. ‘The above mentioned four steps denote one transaction. In a database, each transaction should maintain ACID properly to meet te consistency and integrity of the database. einen [ 1. Write a short note on ~ Transaction Concept. (Crore | Ed Properties ‘AU : May-14,18,19, Marks 15 1) Atomicity : unit an * This property states that cach transaction must be considered as a single must be completed fully or not completed at all. # No transaction in the database is left half completed. * Database should be in a state either before the transaction execution oF after transaction execution. It should not be in a state ‘executing’. + For example - In above mentioned withdrawal of money transaction all the fie eae be complete fully or none of the step is completed: sur arene ae = ater step 3, then the customer will get the moe a Sonn ata up aed accordingly. The state of database should be ‘ i withdrawal (ie customer without withdrawn money) & withdrawal (i.e. custo . he i istomer with money at C This will 0 system in gonsistent state, y and account updated). TECHNI ® CAL PUBLICATIONS. - an up-thrust for knowlodg®sister? cons! tabase must remain in consistent state atabast | Ted after Performing, In ATM withdrawal operation, the any transaction, balance must be updated latabase can be in consistent example ¢ o For ately after performing transaction. Thus the d. appro state tsolation : In a database system where more than one transaction are bei ena de ing executed imultancously and in parallel, the property of isol lation states that all the transactions will be carried out and executed as if it is the only transaction in the system. No transaction will affect the existence of any other transaction, For example : If a bank manager is checking the account balance of particular customer, then manager should see the balance either before withdrawing the money or after withdrawing the money. This will make sure that each individual transaction is completed and any other dependent transaction will get the consistent data out of it. Any failure to any transaction will not affect other transaction in this case. Hence it makes all the transactions consistent. 4) Durability : * The database should be strong enough to handle any system failure. * If there is any set of insert /update, then it should be able to handle and commit to the database. * If there is any failure, the database should be able to recover it to the consistent state, * For example : In ATM withdrawal example, if the system failure happens after Customer gel tting the money then the system should be strong enough to update Database with his new balance, after system recovers. For that purpose the system Pes to keep the log of each transaction and its failure. So when the system “covers, it should be able to know when a system has failed and if there is any ‘ing transaction, then it should be updated to Database. Review Que Expl 7 Main with an example the Properties that must be satisfied by transaction. Explai be im the ACID Properties of transaction. SCUss jj es Sin detail about the ACID properties of transaction. Rc eo ec ® TECHNICAL PUBLICATIONS. - an up-thrust for knowledgeDesign and Management Database, [Bi Transaction States as following five states : Partially Committed, Fig. 4.3.4 Transaction states Each transaction hi 1) Active : This is the first state of transaction. For example : insertion, dele updation of record is done here. But data is not saved to database, 2) Partially Committed : When a transaction executes its final Operation, itis sity be ina partially committed state. 3) Failed : A transaction is said to be in a failed state if any of the checks madety the database recovery system fails. A failed transaction can no longer pre! further. 4) Aborted : Ifa transaction is failed to execute, then the database recovery syn will make sure that the database is in its previous consistent state. If not, itbing the database to consistent state by aborting or rolling back the transaction. 5) Committed : If a transaction executes all its operations successfully, it is said be committed. This is the last step of a transaction, if it executes without fil EEERIBERD define «transaction. Then discuss the following with relevant 1A rend only transaction 2. A read write transaction 3. An aborted transa Solution : (1) Read only transaction Read(A) -——_____ Read(B) ee ig Display(A-B) © TECHNICAL PUBLICATIONS - an up-thrust for knowledg®several states, until it Finally commits or rough wi hich transaction may pass. Explain rity Oe Seed tha neat shetch explain the states of transaction. {he States of transaction with neat diagram, edulesetabase Design and Management Database Design and ‘Schedule Non serial Serializable [ra] Conflict View | Fig. 4.4.1 : Types of schedule serial schedule : The schedule in which the transactions execute one ater ty called serial schedule. It is consistent in nature. For example : Consider fl te m DS be transactions T1 and T2. Tl R R(A) pester S| Wa) We) = en B exerts Od te. The R sta All the operations of transaction T] on data items A and th transaction T2 all the operations on data items A and B execu operation and W stands for write operation. a, Non serial schedule : The schedule in which operations present within a intermixed. This may lead to conflicts in the result or inconsistency lata. TECHNICAL PUBLICATIONS. - an up-thrust for knowledg?gemont Transection Menegemont and Mana: = Ce le actions, (Fig 90 ES ait oe he Theabove transaction is said to be non serial which result in inconsistency or conflicts ‘nbedata, Useiatzabitity * When multi 518,19, Marks 13 then it may lead to inconsistency of from different transactions), the transact ‘epiand Management Trans ection nitially TI will read the values from database as es of A and B. But transaction T2 wi sh atabase Des * Inabove and modify the valu ead the m, mod “tn se. 90 and will modify it to 80 and perform write operation, Thus a Med 0. 90.0 action TI value of A will be 90 but at end of transaction T2 yay He alue of , 80. Thus conflicts or inconsistency occurs here. This sequence aN be co, Wily, zequence which may give ws consistent result. This process is called see la difference between serial schedule and serializable schedule ‘[Link]. Serial schedule 1 No concurrency is allowed in serial schedule. Concurrency i is allowed in, Bic ‘schedule, 2, Inseval schedule, if there are two transactions "in serializable schedule, re meng ‘executing at the same time and no interleaving of operations i permitted then following can interleaving of i ial be the possibilities of execution - oes there can be different possible order executing an individual operation of te transactions. "transactions executing atthe sameting 4) Execute all the operations of transactions Ty in a sequence and then execute all the operations of transactions T; in a sequence. ii) Execute all the operations of transactions T ina sequence and then execute all the operations of transactions T; in a sequence, Example of serial schedule Example of ses schedule Ty : es TECHNICAL PUBLICATIONS. - an up-thrust for knowledgeMo! nagoment Transaction Man: rit ond) serializabilities : Conflict setializabiti . he two tyPes ce ability and view mn a ( onl ose T; and T; are two transactions and I, and I, are the i instructions ne ih mrepectively. Then these two transactions are said to be conflict if both the instruction access the data item d, and at least one of the ple, ea is write operation. anfict?: In the definition three conditions are specified for a conflict in isc at a nic eralizaility ~ | there should be different transactions 3) The operations must be performed on same data items 3) One of the operation must be the Write (W) operation. | Wecan test a given schedule for conflict serializability by constructing a precedence | - gaph forthe schedule, and by searching for absence of cycles in the graph. + Predence graph is a directed graph, consisting of G = (V, E) where V is set of vertices and Eis set of edges. The set of vertices consists of all the transactions participating inthe schedule. The set of edges consists of all edges T, > T; for which one of three conditions holds : 1. Tyexecutes write(Q) before T; executes read(Q). 2 Tyexecutes read(Q) before Tj executes write(Q). 4. Tyexecutes write(Q) before ‘[Link] write(Q). * Acerializability order of the transactions can be obtained by finding a linear order “sistent with the partial order of the precedence graph. This process is called ‘°pological sorting. Teng for Serializability Follow ia "B method is used for testing the serializability : To test the conflict ‘abili ral lity we can draw a graph G = (V, E) where V = Vertices which represent the ea ansactions, Beg for Conflicting pairs. 1G Teate a Node for each transaction. fe 4 the conflicting pairs (RW, WR, WW) on the same variable (or data item) by eae ion: tran; 1n up-thnust for knowledge Se TECHNICAL PUBLICATIONSDatabase Design and Management Step 3 : Draw edge for the given schedule. Consider following ca se 1. Ty executes write(Q) before T; executes read(Q), then draw. AW @ ‘dge f Tom, . oe edge fron OT, en t Pa edge 2. T, executes read(Q) before T; executes writeQ), then 3. T, executes write(Q) before T; executes write(Q),, Step 4 : Now, if precedence graph is cyclic then it is a TON conflict [Link] and if the precedence graph is acyclic then it is conflict Serializable ga : ge Schedule, “heyy | gt Consider the fllowing too transaction ond sce mn one vel in . bottom). Is this schedule confict-serializable ? Explain why or why no, om ‘or, T, T; 7 R(A) ster Wa) will RA) | R@) R@) i Wo) Solution : su Step 1 : To check whether the schedule is conflict serializable or not we will checkin | fo" top to bottom. Thus we will start reading from top to bottom as, on Ty: R(A) > Ty : WA) >T,:R(A) > Ty: RB) OT; :R(B) > T,: WB) nat Step 2 : We will find conflicting operations. Two operations are called as contig | operations if all the following conditions hold true for them - @ i) Both the operations belong to different transactions. ii) Both the operations are on same data item. iii) At least one of the two operations is a write operation. From above given example in the top to bottom scanning we find the conflict T,: W(A) >T, (A). i) Here note that there are two different transactions T, and Tz, ii) Both work on same data item ie. A and iii) One of the operation is write operation. rans Step 3: We will build a precedence graph by drawing one node from aT above given scenario as there are two transactions, there will be two nodes Tr TECHNICAL PUBLICATIONS. - an up-thrust for knowledge' 41 Transaction Management ana Management _—_ ye ee © Fig. 4.5.1 between conflicting transactions. For example in above giv - : en irs while moving from T, : W(A) to T; : R(A). Hence edge ee Fig. 4.5.2 _ praw the edge Set the conflict 08 ari tetom q,and Tr grep 5: Repeat the step 4 while reading from top to bottom. Finally the precedence graph uillbeas follows because of T; : WAT? : RIA) because of T, : R(B)T; WB) Fig. 4.5.3 : Precedence graph Cycle is a path using which we can start the is cycle found then schedule is not that means given schedule is step 6 : Check if any cycle exists in the graph. fom one node and reach to the same node. If conflict serializable. In the step 5 we get a graph with cycle, nol conflict serializable. PRERIPEEY icc rete following schedule is conflict serializable or not. If 's rot conflict serializable then find the serializability order. TL 12 13 R(A) RB) RB) We) Wi) Wa) R(A) WiA) o TECHNICAL PUBLICATIONS. - an up-thrust for knowledge4-12 tr OA Solution : We will read from top to bottom, and build a precedence graph T Cong: Step 1: , entries, We will build a precedence graph by drawing one node from each tra, Cony lity Shove given scenario as there are thee transactions, there will be two inf T2, and T3 * namely 4, Step 2: The conflicts are found as follows - 1 12 3 R(A) ——+ © \ R@) a! oF) \ we) ] ry) \ ZL op ROA) Wa) | Step 3: The precedence graph will be as follows - Step 4 : As there is no cycle in the precedence graph, the given sequen? ys serializable. Hence we can conver this non serial schedule to serial sched purpose we will follow these steps to find the serializable order. os ene or ing * Step 5: A serializability order of the transactions can be obtained by fod at! order consistent with the partial order of the precedence graph. This P topological sor TECHNICAL PUBLICATIONS - an up-thrust for knowledg?4-13 Transact nagernemt msaction Management which has no incoming edge which is T1, . Hf we delete T1 0d eno incoming edge. If we delete T3, then T2 . isa node that has no the nodes can be deleted in a order Tl, T3 and T2. Hence the order will be ® this Check whether the below schedule is conflict serializable i200) 1 r1(X),W1(X),r1(Y), W1(Y), W2(X),e1,C1,e2,C2} 2 sos b2 and represents begin transaction 2 and begin transaction 1. Similarly, and e2 represents end transaction 1 and end transaction 2. Wewill rewrite the schedule as follows - MWe co ‘pag, V° Will find ost conflicting operations. Two operations are called as conflicting tall the fol eth the g owing conditions hold true for ee : 9 both the Ee belong to different transactions. ii) ©Perations are on same data item. | cong. t OR of the two operations is a write operation. "Sting entries are as follows - TECHNICAL PUBLICATIONSDatabase Design and Management RX) W(X) 5] RY) wiv) {\ WX) Step 2: Now we build a precedence graph for conflicting entries, Ta = 12(X), Ty: Wy) Te W406, Tz Wa(X) Fig. 4.5.4 As there are two transactions only two nodes are present in the graph. Step 3 : We get a graph with cycle, that means given schedule is not conflict serializable LE SUIIEEERS Consider the three transactions T1, T2, and T3 and schedules $1 and S2 sitet << corjalizable unit. below. Determine whether each schedule is serializable or not ? If a schedule is serializable 4 down the equivalent serial schedule(S), TI: RU(x) R12); WIG); T2: R2x);R2(y);W2(z);W2(y) T3:R3(x),R3(y);W3(y); \ SU: R(x); R2(z)-R1(2);R3(x)-R3(y); W(x); W3 y);R2(y): W2(2) WA) : W2(y): 52: R1(x);R2z);R3(x);R1. (2);R2(y);R3(y); W(x); W2(z); W3(y) W2Y) Solution : Step 4: We will Tepresent the schedule S1 as follows TECHNICAL PUBLICATIONS - an up-thrust for knowledg® 4_ Transaction Management k 4-15 i: i ions ar Ye will find conflicting operations. Two Operation: 7 if all the following conditions hold true for them - ios taththe operations belong to different transactions, Bot . ijt the operations are on same data item, e called as conflicting ijatleast one of the two operations is a write Operation Trconflicting entries are as follows MCE Braph ag follows. A Flaass Precedence 9raphDatabase Desi and Management 4 FO ye" Teste . ‘ele in the precedence graph, the given ‘As there is noc ‘ 5 serializable. Hence we can convert this non serial schedule t0 seria) syn Me.” purpose we wil low these steps to find the serializable order, Sched My . “Ty Step (c): A serializability order of the transactions can be obtained by ty Y find ng order consistent with the partial order of the precedence graph. This topological sorting Process ia, Step (d) : Find the v ertex which has no incoming edge which is T3. If we d edge that has no incoming edge. Finally find the vertex having itis out Tt is the ek which is T2. Hence the order will be T3- T1-T2. Bring, Step 2: We will represent the schedule S2 as follows - | ificiss | jed as co Step ) We will find conflicting operations. Two operations are call operations if all the following conditions hold true for them - i) Both the operations belong to different transactions. ii) Both the operations are on same data item. iii) At least one of the two operations is a write operation TECHNICAL PUBLICATIONS. - an up-thrust fr knowed??Me nd atsies eran i gO Mj} | 3] e R1(x) ' Raa) | | Rae R12) Ray) [|] \ R3(y) wa(z) r-W3ty) wavy) ww we will draw precedence graph as follows - or No @) @ () Fig. 4.5.6 Precedence graph as there is no cycle in the precedence graph, the given sequence is conflict gilizable. Hence we can convert this non serial schedule to serial schedule. For that pose we will follow these steps to find the serializable order. sep(0): A serializability order of the transactions can be obtained by finding a linear ‘er consistent with the partial order of the precedence graph. This process is called tpological sorting. ‘p(d) : Find the vertex which has no incoming edge which is T3. Finally find the vertex Steno outgoing edge which is T2. So in between them is TI. Hence the order will be B-T1-T2 Consider the Transaction, Transaction and Transaction are any hypothetical transactions working on data item Q. Schedule explaining the execution a and are given, below. Decide whether following schedule is conflict serializable or not ? Justify your Aansaver, 73 T# zs | read (O) j | write () rite (2) vwrite (O) eelDatabase Design and Management 4-18 Solution : We will find the conflicting entries as follows - 13 4 Te read (Q) write (Q), write (Q) #7] Hh write (Q) ‘The precedence graph is as follows - O—® @) Fig. 4.5.7 Procedence graph As there exi 's cycle, the given schedule is not conflict serializable, Explain the concept of conflict serializabilily. Decide whet és conflict serializable or not. Justify your ansiver. er folocin i TI T2 read (A) write (A) } read (A) write (A) read (B) | write (B) } read (B) } write (B) Solution : for conti | Step 1: We will read from top to bottom, and build a precedence rap! | entries. ledge I TECHNICAL PUBLICATIONS. - an up-tiust for= pont and Manager” > ae i? Transaction Managemont Mananemant as follows - jeting entries are 1 12 ‘| read (A) write (A) fead (A) 2 a waite (Ay tead (B) waite (B) read (B) waite (BY will build precedence graph as follows - ere is no cycle in the precedence graph. That means this schedule is conflict low w she, Hence we can convert this non serial schedule to serial schedule. For that eve will follow the following steps to find the serializable order. d the vertex which has no incoming edge which is T1. x equivalent schedule : Consider two schedules $1 and S2 consisting of ns TI and T2 respectively, then schedules S1 and S2 are said to be view lent schedule if it satisfies following three conditions : Fe tion T1 reads a data item A from the database initially in schedule S2, irom th Schedule $2 also, T1 must perform the initial read of the data item X e database. This is same for all the data items. In other words - The initial i lait, be same for all data items. schedule S A has been updated at last by t Ite > also, the data item A must be up’ nsaction Ti reads a data item that has been updated b; tem qu St then in schedule $2 also, transaction Ti mus ris ence must be same. ransaction Ti in schedule S1, then in dated at last by transaction Ti y the transaction Tj in t read the same data rds the Write-Read that has been updated by transaction Tj. In other Wo! © lodge TECHNICAL PUBLICATIONS. - an up-thnustfor knowDatabase Design and Management * Difference between conflict seria [Link]. Conflict serializability serializable is, TE! Every conf Every view serializable scheduleig serializable. necessarily conflict serializable, 2, Itiseasy totest conflict serializability. __Itis complex to test view serialz Steps to check whether the given schedule is view serializable or not Step 1 : If the schedule is conflict serializable then it is surely view serializable teaue conflict serializability is a restricted form of view serializability. Step 2 : If it is not conflict serializable schedule then check whether there exist any bing write operation. The blind write operation is a write operation without reading a value there does not exist any blind write then that means the given schedule is not view serializable. In other words if a blind write exists then that means schedule may or my not be view conflict. Step 3 : Find the view equivalence schedule Consider the following schedules for checking if these are view serializable not. Ty, T, Ty wo R(A) we) RB) RO) we) We) Solution : i) The initial read operation is performed by T2 Hence we will begin with T; or T;. We will choose T2 a ii) The final write is performed by T, on the same data item Jast position, iii) The data item C is written by T; and then it is read by before'T,, Thus we get the order of schedule of view serialize 1H‘and Management at os! Transaction eo Consider following two transactions Management read A) reat(B) jac then BB+; zorite(B) + readlB): read Al; ifB-0 then A=A+1; write(A) Let consistency requirement be A=0 V B=0 with A=B=9 1) Show that every serial execution involving these tw . consistency of the database ? transactions preserves the 2) Show a concurrent execution of T, and T, that produces a ilsthere a concurrent execution of T, and T, that produces sation: 1) There are two possible executions Eh Consider case T,->T, then the initial values, 4 serializable schedule ? >T,orT,T, AvB=A OR B= EvT = T. This meai : ns consistency is met. Consider case T;>T, then * ABeA Q o7 RB=EyT a 7 can B=FvT=T, This means consistency is met. ‘current execution means interleaving of transactions T, and T;. It can be R®) If B=O then’ | IfA=0 then ArAtl WA) TECHNICAL PUBLICATIONS. - an up-thrust fork aDatabase Design and M: agement This is 2 non-serializable schedule. rent execution resulting in a serializable schedy}, le. 3) There is no concu Conster the felling schedules. The actions are listed in the order i reheuled, and prefixed wth te transaction name, they 1), TWO. TWO TRO, Ty:RMy ,:T;:R(X), Ts: R $27 2X), TARO) TWO), Th R(Z),T:: WZ) T,:R(2) answer the following questions : For each of the schedules, 3) What is the precedence graph for the schedule ? i) I the schedule confict-serializable ? Ifo, what areal the conflict equivalent sg schedules ? i Is the schedule view-serializable ? If so, what are all the view equi equivalent ses schedules ? Solution i) We will ind conflicting operations. Two operations are called as conti, operations if all the following conditions hold true for them - : «Both the operations belong to different transactions. «Both the operations are on same data item. « Atleast one of the two operations is a write operation For S; : From above given example in the top to bottom scanning we find the cos as 0 T,: WW), Tz: WO) and 0 Te: WO), TRO) Hence we will build the precedence graph. Draw the edge between confit: transactions. For example in above given scenario, the conflict occurs while moving fe T,W(Y) to TW(Y). Hence edge must be from T; to Tp. Similarly for second conflict will be the edge from T; toT}. Fig. 4.5.8 Precedence graph for st For S, : The conflicts are, 0 T;: W(X), Ty: RO) oT): W(Z) Ty: R(Z) TECHNICAL PUBLICATIONS. - an up-thrust for knowledgeaie ve Fig. 4.5.9 Precedence Graph for g2 not conflict-serializable since the dependency 8taph has a cycle, gis oS conflict-serializable as the dependency 8raph is acylic. The order Try, is is . ° ° only equivalent serial order, the only 4, is not view serializable, oS 5, s trivially view-serializable as it is conflict Serializable. The only serial order ° allowed is Ty-Ts-T). le given below : = A read (A) |S Ar=A-50 write (A) read (A) temp: = A*0,1 AISA- temp write (A) read (B) B:=B+50 ‘write (B) (Saas read (B) B+ temp uorite (B) y Stuion : Mey 1 Mpg an t. For that J ! Will first find if the given schedule is conflict sores no “Ne will find the Conflicting operations. These are as shown st or knowledge TECHNICAL PUBLICATIONS. - anand Management road (A) A eel rt 4 Toad (Ay tomp: &A‘01 A= A~tomp [waite (A) read (B) B:=B+50 write (GO) read (B) B:= B+ tomp, write (B) ‘The precedence graph is as follows - Fig. 4.5.10 Procedonce graph As there exists no cycle, the schedule is conflict serializable. The possible setalizabiliy order can be T1-T2 Now we check it for view serializability. As we get the serializability order as Tl Wwe will find the view equivalence with the given schedule as serializable schedule Let S be the given schedule as given in the problem statement. Let the serializable schedule is S'={T1,T2}. These two schedules are represented as follows : T2 11 read (A) Ars A-50 write (A) read (A) read (B) temp: = A‘0.1 B:=B +50 A: A-temp E write (A) write (B) ke © write (B) Schedule S TECHNICAL PUBLICATIONS in upettirust for knowledge read (A)and Management 4-25 i Transactioy equi Nn May * evil check the equivalence between them using, following = yw Conditioy d ms « aaial Reat quer oe oh : jpsceslle g initial read on A is in transaction T1. Similarly initial ; al read on B is; Isin ransaction TL. cinirly 1" schedule S', initial read on A is in transaction TL Similan similarly initial read oaBisin transaction T1. ifinal Write inschedule $ final write on A is in transaction T2. Similarly final write on B i transaction T2. fe on B is in Inschedule S’ final write on A is in transaction T2. Similarly final write on B is i transaction T2 st be (Intermediate Read Consider schedule S for finding intermediate read operation. read (A) A:=A-50 write (A) ead (A) temp :=A*0.1 A:= A-temp Intermediate Read obtained only after T1 performs Write operation tead (B) B:=B+50 write (B) read (B) B:=B+temp Sin Marly Consider schedule $’ for finding intermediate read operation.rend (A) Bah 50 toad (B) ashy 50 rrr Py tend (a) ™~ temp = 0.4 Intermediate Read ope he nt obtained ony afer Performs Vite operation vite (A) io) —— | B= 8 temp write (B) In both the schedules $ and S, the intermediate read operation is perfomnea only after TI performs write operation. bn Thus all the above three conditions get satisfied. Hence given schedule iS view serializable. UO TS ES 1. Explain Conflict serializability and view serializability 2. Discuss in detail about the testing of serializability. EX] concurrency Control Cee * One of the fundamental properties of a transaction is isolation. * When several transactions execute concurrently in the database, however, isolation property may no longer be preserved. + A database can have multiple transactions running at the same time. Ths concurrency. rare jinteraction ami" * To preserve the isolation property, the system must control the interaction id the concurrent transactions; this control is achieved through one of 2 Y=" mechanisms called concurrency control schemes. eo sures that simul Definition of concurrency control : A mechanism which en: y danh® execution of more than one transactions does not lead t inconsistencies is called concurrency control mechanism. cols ta ‘The concurrency control ean be achieved with the help of various Pret ~ lock based protocol, Deadlock handling, Multiple Granulatity, Ti" protocol, and validation based protocols. TECHNICAL PUBLICATIONS. - an up-thust for knowled9®cone ry for - | ee ie the purposes of concurrency control gon _ qoensute * soresolve rea * sq preserve consistency of database jsolation d-write or write-write conflicts cogent execution of transactions over shared database creates several data a and consistency problems — these are st pate Problem This problem occurs when to transactions that acess the ‘ipo database items have their operations interleaved in a way that makes the salue of some database item incorrect. forexample - Consider following transactions (t)Sslary of Employee is read during transaction TI. (2)Salary of Employee is read by another transaction T2. (3)During transaction T1, the salary is incremented by € 200 (4) During transaction T2, the salary is incremented by €500 fe Tesult of the above sequence is that the update made by transaction TI is pletely lost. Therefor this problem is called as lost update problem. TECHNICAL PUBLICATIONS b>Database Design and. ‘Management s-= JTansactic +: mited Read Problem : The dirty weed eee (2) Dirty Read or Uncom ° : y which one transaction reads the data immediately after the write 9. previous transaction Petatin Ti T, ‘ ps RA) LArASO Dirty read WA) R(A) AzA-20 W(A) & Commit Commit For example — Consider following transactions - ‘Assume initially salary is = = 1000 " bs ; * f Dirty Read } ts Rollback Salary = = 1000 (1) At the time t1, the transaction T2 updates the salary to %1200 (2) This salary is read at time t2 by transaction T1. Obviously itis € 1200 _ (@) But atthe time 3, the transaction 2 performs Rollback by undoins the ts made by TI and T2 at time tl and t2. a ‘ ity RO (4) Thus the salary again becomes = % 1000. This situation leads '© pe a i d Read because here the read made at time t2{imm update of another transaction) becomes a dirty read © TECHNICAL PUBLICATIONS. - an up-thrust fr knowleo9? Uncom:Transacten a y y and Manas pe a Ps et table re ' | ? rope jg also known as inconsistent analysis problem. This problem ticular transaction sees two different values for the same row d Problem is : when 4 pal velifetime. For example ~ eee | eae PT Stary = 81000 Update salary from |_| % 1000t0% 1200 | Salary ee (1) Attime #1, the transaction T1 reads the salary as % 1000 (2) Attime t2 the transaction T2 reads the same salary as % 1000 and updates it to 1200 (@) Then at time t3, the transaction T2 gets committed. AA (4) Now when the transaction T1 reads the same salary at time t4, it gets different value than what it had read at time tl. Now, transaction T1 cannot repeat its reading operation. Thus inconsistent values are obtained. Hence the name of this problem is non-repeatable read or inconsistent 2 analysis problem. B a () Phantom read Problem i : The phantom read problem is a special case of non repeatable read problem. This is a problem in which one of the transaction makes the changes in the database system and due to these changes another transaction can not read the data item which it has read just recently. For example - § (1) At time ty, the transaction Ti reads the value of salary as 1000 ©) Attime ts, the transaction Te reads the value of the same salary a5 1000 {) At time ts, the transaction Ts deletes the variable salary. TECHNICAL PUBLICATIONS. ~ an up-thrust for knowledvenagement Database Design & Transaction Bets error. Ng = Ts can not identify the reason why it is not getting the Salary vaty, = read just few time back (4) Now at time ts, when T: again read i, This problem occurs due to changes in the database and j 1S called read problem Phat, «caused by each of the following: dirty read, nom repens tad rn suitable example 2. What is concurrency control ? How it is implemented in DBMS ? Briefly elaborate iggy, ry rs Ue and examples EE] Locking Protocol EVE SES ae ey [EEE Why Do We Need Locks ? + One of the method to ensure the isolation property in transactions isto require he data items be accessed in a mutually exclusive manner. That means, while ce transaction is accessing a data item, no other transaction can modify that dataiten. * The most common method used to implement this requirement is to allow 2 transaction to access a data item only if it is currently holding a lock on thatiten. + Thus the lock on the operation is required to ensure the isolation of transaction ERY] simple Lock Based Protocol * Concept of Protocol : The lock based protocol is a mechanism in which there 5 exclusive use of locks on the data item for current transaction. * Types of Locks : There are two types of locks used - Lock [— Shared Lock "— Exclusive Lock Fig. 4.8.1 Types of locks we i) Shared Lock : The shared lock is used for reading data ites denoted by Lock-S. This is also called as read lock. on if) Exclusive Lock : The exclusive lock is used for both el operations. It is denoted as Lock-X. This is also called as WHlE nd —____ 6 TECHNICAL PUBLICATIONS. - an up-thrust for knowledg®4-31 : Transaction Mana lament agome! ‘ i of Ye natrix is used while working on set of locks, The concurren cpt ae the compatibility matrix before granting the lock, bg rt er on are compatible to each other then only the lock will be ; ci ff rans so! : lusi 5 . eit may consists of shared or exclusive locks, Following matrix of locks bility between modes of locks. ax compatil a ens tne COMP’ ape Fig. 4.8.2 Compatibility matrix for locks Here T stands for True and F stands for False. If the control Manager get the compatibility mode as True then it grant the lock otherwise the lock will be denied. + for example : If the transaction T, is holding a shared lock in data item A, then the control manager can grant the shared lock to transaction T, as compatibility is True. Butit cannot grant the exclusive | ‘ensaction T, is reading a data ‘other transaction T, but cannot lock as the compatibility is false. In simple words if item A then same data item A can be read by be written by another transaction, * Similarly if an exclusive lock (ie. lock for read and write operations) is hold on the ion then no other transaction can acquire Shared or patibility function denotes F. That means of some a iter data item in some transactic ®lusive lock as the comy tensagii— ; *Nsaction ig writing a dat tha m A then another transaction can not read or write data item A. “nce the rule of thumb is Ny ‘Dp 'Y Number of transactions can : ‘ut &clusive lock can be hold sted of a schedule denoting dat _ Which initially A=100. item A in transaction T, hold shared lock on an item. by only one transaction, shared and exclusive locks : Consider following We deduct 50 from A in T, transaction and Read The scenario can be represented with the help of a ind Soncurrency control mar nager as follows : SeDatabase Design ans Management Grant X(AT1) because | | write operati | Exclusive Lock i peration. ———— | |rw es cae \| caso a we) ao oa © eas, ow, ee Ge Lock-S(A) : Shared Lock Lot Saree) amen eee | Read operation 4 We RA) Unlock(A) 1. State and explain the lock based concurrency control with suitable example KX Sse 2. What is Concurrency control ? How is implemented in DBMS ? Illustrat example, ree o Mats Two-Phase Locking Techniques ena «The two phase locking is a protocol in which there are two phases* ant i) Growing phase (Locking phase) : It is a phase in which the trans obtain locks but does not release any lock. st ii) Shrinking phase (Unlocking phase) : It is a phase in wh may release the locks but does not obtain any new lock. TECHNICAL PUBLICATIONS. - an up-thrst for xnowes?nent ne last lock positi jon or first unlock position is called lock ez Fi by. point * ¢ ve or example in Lock pint wes pn set acquit rar (Gr a) ase) aan i) phase) i statin ee i begin ot Lock Point is ncn aloo) lock) alo) orexample~ consider following transactions «All Lock operations precede all The im Portant rule for being a two phase locking is ‘lock operations ‘ode but transaction T2 is not in two ed by data item B, then data item B by data item A, then the Jock-unlock-lock-tnlodl | nab | selon transactions T1 is in two phase locking ™ | read ang be Because in T2, the Shared lock is acquire j “item An the lock is released. Again the lock is acquired is read and the lock is then reloased. Thus We get nce, C Teatly this is not possible in two phase locking: TECHNICAL PUBLICATIONS = 2” ypthnst for knowledge4-34 Database Design and Management ee Transaction Verse, ™ ERERTSREIORM Prove that two phase locking guarantees serializability. if © Serializability is mainly an issue of handling write operation. Because any inconsistency may only be created by write operation. Solution : © Multiple reads on a database item can happen parallely. © 2-Phase locking protocol restricts this unwanted read/write by applying ex clusive lock. © Moreover, when there is an exclusive lock on an item it will only be released in shrinking phase. Due to this restriction there is no chance of getting any inconsistent state. The serializability using two phase locking can be understood with the help of following example Consider two transactions TOT RA) ___ RA) R@) We) Step 1: Now we will apply two phase locking. That oars growing and shrinking phase ig. That means we will applyd Management _ pesian and Transaction Manegement_ that above schedule is serializable as it prevents interference between two tha ability order can be obtained based on the lock point. The lock point is ee ock operation position or first unlock position in the transaction. Fa jaat lock position is in Ty, then it is in T,, Hence the serializability will be T,>T, on lock points. Hence The serializability sequence can be Ra(A),R1(B);W1(B) ans of Two Phase Locking Protocol .o phase locking protocol leads to two problems - deadlock and cascading Deadlock : The deadlock problem can not be solved by two phase locking. eadlock is a situation in which when two or more transactions have got a lock and waiting for another locks currently held by one of the other transactions. For example T1 12 Lock-X(A) Lock-X(B) Read(A) Read(B) A=A-50 B=B+100 Write(A) Write(B) a = 7 he & < XN 7 Delayed, Delayed, I waitforT2 \ waitforTl 1 \ to release 1 to release 4 \ LockonB LockonA 7 7 g Rollback : Cascading rollback is a situation in which a single ction failure leads to a series of transaction rollback. For example — o TECHNICAL PUBLICATIONS - an up-thrust for knowledge aeWrite(©)_ Read(C) Write(C) When TI writes value of C then only T2 can read it. And when T2 writes the value of C then only transaction T3 can read it. But if the transaction T1 gets failed then automatically transactions T2 and T3 gets failed. The simple two phase locking does not solve the cascading rollback problem. To solve the problem of cascading Rollback two types of two phase locking mechanisms can be used. Types of Two Phase Locking (1) Strict Two Phase Locking : The strict 2PL protocol is a basic two phase protocol but all the exclusive mode locks be held until the transaction commits. That means in other words all the exclusive locks are unlocked only after the transaction is committed. That also means that if T, has exclusive lock, then T, will release the exclusive lock only after commit operation, then only other transaction is allowed to read or write. For example Consider two transactions If we apply the locks then RA) Unlock-S(A) = o TECHNICAL PUBLICATIONS. - an up-thrust for knowledge4-37 pond Managenrent Transaction Management Cs ry attr commit operation in, we can unlock the exclusive lock. This ensures ys onl) alizability- ed to basic two phase locking protocol, the advantage of strict 2PL Pe compare two phy si compares strict seralizability. olis sete 4242 gus Two Phase Locking : This is stricer two phase locking protocol. Here all a er tobe held until the transaction commits. The transactions can be seriealized in at rin wich they commit. pe der transactions “example - Consi exampl = R(A) RG) WO) feapply the locks then . 1 ‘Lock-S(A) R(A) Lock-X(B) R@) We) Commit ‘Unlock(A) Unlock(B) ‘Thus the above transaction uses rigorous two phase locking mechanism REUTER Consider the, following two transactions + “oe TECHNICAL PUBLICATIONS. - an up-thrust for knowledgeDatabase Design and Management 4208 Transaction Man2oe ney Solution : = © Lock-S(A) Lock-S(B) Read(A) Read(B) Lock-XB) Lock-X(A) ~ Read(B) Read(A) if AO then B=B+1 if B-O then A=A+1 t Write) Write(A) Unlock(A) Unlock(B) Commit ‘Commit Unlock(B) Unlock(A) This is lock-unlock instruction sequence help to satisfy the requirements for strict two phase locking for the given transactions. The execution of these transactions result in deadlock. Consider execution scenario which leads to deadlock. following partial 1 12 Lock-S(A) Lock-S(B) Read(A) Read(B) “Lock-X(B) Lock-X(A) Now it will wait for T2 to. Now it will wait for Tl to release exclusive lock on/A.__release exclusive lock on B Lock Conversion Lock conversion is a mechanism in two phase locking mechanism - which conversion of shared lock to exclusive lock or exclusive lock to shared lock. Method of Conversion : First Phase : © can acquire a lock-S on item © canacquire a lock-X on item © can convert a lock-§ to a lock-X (upgrade) Second Phase : © can release a lock-S © can release a lock-X © can convert a lock-X to a lock-S (downgrade) © TECHNICAL PUBLICATIONS. - an up-thrust for knowledge allows_Transaction Management emits Ts R(A) R(A) RO) R(B) RO, WIA) art applying locks, then we must apply the exclusive lock on data item ye have to read as well as write on data item A. Another transaction T2 does Jock on A until transaction T1 performs write operation on A. Since [needs exclusive lock only at the end when it performs write operation on T1 could initially lock A in shared mode and then later change it to mode lock when it performs write operation. In such situation, the lock chanism becomes useful. onvert the shared mode lock to exclusive mode then it is called upgrading wert exclusive mode lock to shared mode then it is called downgrading. upgrading takes place only in growing phase and downgrading takes g phase. Thus we can refine above transactions using lock ism i follows - Lock-S(A)os 4-40 Transaction Msn Database Design and Manag gment_4- 80 att ee RO) ee Ou Upgrade(A) —wiA) Unlock(A) Unlock(B) Unlock(©) Review Questions 1. What is concurrency control ? Explain two phase locking protocol with an example. FBO eC) 2. Illustrate t2v0 phase locking protocol with an example. Cees 3. Discuss elaborately the two phase locking protocol that ensures serailizabilit red Two Marks Questions with Answers Q.1 Whatis a transaction ? Ans. : A transaction can be defined as a group of tasks that form a single logical unit. Q.2 What does time to commit mean? a) Ans. : ‘The COMMIT command is used to save permanently any transaction to database. When we perform, Read or Write operations to the database then those changes canbe undone by rollback operations. To make these changes permanent, we should mie use of commit 3 Whatare the various properties of transaction that the database system maintains 0 ensure integrity of data. OR Q.4 What are ACID properties ? Ans. : In a database, each transaction should maintain ACID property '© consistency and integrity of the database. These are (1) Atomicity (2) Consistency (3) Isolation (4) Durability @ TECHNICAL PUBLICATIONS. - an up-thrust for knowledg?Transaction Management ction that follows the ACID eaning of the expression ACID transaction. ession ACID transaction represents the transa atomicity property of a transaction, Cy . tbe ,e completed fully or not completed at all. action in the database is left half completed. “What is meant by concurrency control ? state the need for concurrency control. ny is it necessary to have control of concurrent execution of transactions ? How is it ne common wed concurrency conta teens Cn ‘commonly used concurrency control techniques are ~ ii) Timestamp iii) Snapshot Isolation | What is meant by serializability? How it is tested? Serializability is a concept that helps to identify which non serial schedule and find action equivalent to serial schedule. Fested using precedence graph technique. =i. What is serializable schedule ? Ms. alled serial The schedule in which the transactions execute one after the other is lule. It is consistent in nature. For example : Consider following two transactions TL dt x) TECHNICAL PUBLICATIONS. - an up-thrust for knowledgeDatabase Design and Management See R(A) WIA) R(B) We) All the operations of transaction T, on data items A and then B executes and then in transaction T; all the operations on data items A and B execute. The R stands for Read operation and W stands for write operation. Q.13 | When are two schedules conflict equivalent ? t= Ans. : Two schedules are conflict equivalent if : * They contain the same set of the transaction. * every pair of conflicting actions is ordered the same way. For example ~ Non Serial Schedule Serial Schedule Sea Read(A) Write(A) Schedule 52 is a serial schedule because, in this, all operations of T1 are performed be ie starting any operation of T2. Schedule $1 can be transformed into a serial schedule PY swapping non-conflicting operations of S1. Hence both of the above the schedules are contlict equivalent. _) Soe 5 TECHNICAL PUBLICATIONS - an up thrust for knowledgend Management 4-43 Transaction Management se Dosian two phase locking. Eee ase locking is a protocol in which there are two phases : i efine F The two phi sowing Phase (Loc! icks but does not release any lock. king Phase (Unlocking Phase) : It is a phase in which the transaction may) king Phase) : It is a phase in which the transaction may obtain} “ jease the locks but does not obtain any new lock. at is the difference between shared lock and exclusive lock? | Au: May-13 | Exclusive Lock Tock is used for when the transaction Exclusive lock is used when the transaction wants to perform both read and write operation. Only one exclusive lock can be placed on a data item ata time. perform read operation. shared lock can be set on @ transactions eously. Using exclusive lock data can be inserted or deleted. nd delete operations. Da d delete operations. e ? What disadvantages result ? iat type of lock is needed for insert a! is,: The exclusive lock is needed to insert an¢ ‘at benefit does strict two-phase locking provid on Dec.-07 an uncommitted transaction are locked in exclusive transaction from reading that is ensure that any data written by mode until the transaction commits and preventing other protocol solves dirty read problem. (tage : sy id until the rrency is reduced. e locking protocol ? at Is rigorous two phas e locking protocol. F This is stricter two phas ction commits. Here all locks are to be hel s two phase locking protocol. CaS Differentiate strict two phase locking and rigourou: Transacti Database Design and Managment 4eAd action Managemen Ans. : * In Strict two phase locking protocol all the exclusive mode locks be held UNtil the transaction commits. * The rigourous two phase locking protocol is stricter than strict two phase locking protocol. Here all locks are to be held until the transaction commits. Q.20. What are states of transaction ? CI) Ans. : Various states of transaction are - (1) Active, (2) Partially Committed (3) Failed (4) Aborted (5) Committed. gaa