DATABASE MANAGEMENT SYSTEM EES November - 2021 April - 2022 n-t STUDY MANUAL | : Important Questions V- Vill SENE! unit -1 1-59 3 Unit - I 60 - 86 = Unit - HI 87-114 Unit - IV 115 - 152 ee Unit - V 153-211 SOLVED MODEL PAPERS Model Paper - I 212-212 E| Model Paper - II 213-213 Ss Model Paper - Ill 214-214ay 1 1 | i I ie I 1 1 1 | 1 | aM 1 1 1 1 1 1 1 1 1 V I 1 I I t I ae iy 5.1.5 Multiversion Schemes 5.1.6 Deadlock Handling _ 5.1.7. Insert And Delete Operations 5.1.8 Weak Levels of Consistency 5.1.9 Concurrency of Index Structures Recovery System: 5.2.1 Failure Classification 5.2.2 Storage Structure — 5.2.3 Recovery And Atomicity | 5.2.4 Log-based Recovery 5.2.5 Recovery With Concurrent Tran-sactions 5.2.6 Buffer Management 5.2.7 Failure with Loss of Nonvolatile storage ~ 5.2.8 Advanced Recovery Techniques 5.2.9 Remote Backup SystemsConcurrency Control: Lock-based Protocols, Timestamp-based Protocols, Validation-based Protocols, Multiple Granularity, Multi-version Schemes, U N IT Deadlock Handling, Insert and Delete Operations, Weak Levels of Consistency, Concurrency of Index Structures. Recovery System: Failuré Classification, | Storage Structure, Recovery and Atomicity, Log-Based Recovery, Recovery Vv with Concurrent Transactions, Buffer Management, Fallure with Loss of Nonvolatile Storage, Advanced Recovery Techniques, Remote Backup Systems nT GEE ETETET EE SSSST STP it Itwill unlock the data item after completing 5.1.1 Lock-based Protocols the transaction’ QI. What are the various types oflocks used'| 2, _Pre-claiming Lock Protocol 1. Explain lock ee ee > Pre-claiming Lock Protocols evaluate based tocols. ‘ Rast 4e the transaction to list all the data items fins: (Imp.) on which they need locks. In this type of protocol, any transaction > Before initiating an execution of the cannot read ot write data until it acquires an transaction, it requests DBMS for all the appropriate lock on it. There aré two types of lock: lock on all those data items. Shared lock > Jf all the locks are granted then this protocol allows the transaction to begin. When the transaction is completed then it releases all the lock. i) > Itisalso known asa Read-only lock. In a shared lock, the data item can only read by the transaction. > Itcan be shared between the transactions » If all the locks are not granted then this because when the transaction holds a protocol allows the transaction-to rolls Jock, then it can't update the data on the back and waits until all the locks are data item. granted. ii) ee Lock is attained | [ Lockis released > In the exclusive lock, the data item can cil be both reads as well as written by the transaction, | This lock is exclusive, and in this lock, ‘Begin Tend. Time multiple transactions do not modify the 3. Two-phase locking (2PL) same data simultaneously, There are four types of lock protocols > The two-phase locking protocol divides evcilable: i the execution phase of the transaction iy to three parts, ° 1. Simplistic lock protocol ee sib > In the first part, when the execution of Itis the simplest way of locking the data while AH tice ca ae transaction, Simplistic jock-based protocols bere en allow all the transactions to get the lock on : ee Ce, NNNMCA LYEAR Il SEMESTER > In the second part, the transaction | Transaction TL ‘acquires all the locks. The third phase is “ } started as soon as the transaction Ran COMIN Bie from step 13 releases its first lock. » Shrinking phase: from step 5-7 > Inthe third phase, the transaction cannot > Lock point: at3 demand any new locks. It only releases the acquired locks. Transaction T2 | | >» Growing phase: from step 2-6 | Locks released > Shrinking phase: from step 8-9 > Lock point: at6 Strict Two-phasé locking (Strict-2PL) > The fin phaeet se 2PL. In the first * all the locks, ees A to execute normally Scan were meen © strict 2PL is that Strict-2PL sales a lok ‘after using it. ansackion coat ‘an¢ releases all the locks at a aa > Strict 2PL protocol : ica < aes shrinking) phase of lock relenes |Lockis attained Locks attaines 4. Release at commit Teegin Tend Time Ita pet have Ceoaine abortas 28 does TOCKSIAY TOCKSIAY feat Q2. Discuss Time stamp based protocols. estamp-based, Protocols 2 [locextey UNLOCKAY Aas: , (imp.) TOCKX(CY Concurrency Control can be implemented TNLOCK(B) in different ways. One way to implement it is by | TURF using Locks, Now, lets discuss about Time Stamp A Ordering Protocol. UHLOCK{E) i — = Asearlier introduced, Timestamp isaunique identifier created by the DBMS to identify a transaction. They are usually assigned in the order — The following way shows how unlocking and | in which they are submitted to the system. Refer 0 locking work with 2-PL. the timestamp of a transaction T as TS(T). | 164 Rahul Publications — Cesinerieah ieee mines eRe unt -¥ sjmestamp Ordering Protocol ‘The Timestamp Ordering Protocol is used to ? crder the transactions based on their Timestamps. The order of transaction is nothing but the ascending order of the transaction creation The priority of the older transaction is higher > that's why it executes first, To determine the: timestamp of the transaction, this protocol uses system time or logical counter. > The lockbased protocol is used to manage the order between conflicting paits among transactions at the execution time. But Timestamp based protocols start working as soon as a transaction is created. > _ Let's assume there are two transactions T1 * and T2. Suppose the transaction T1 has entered the system at 007 times and transaction T2 has entered the system at 009 times, T1 has the higher priotity, so it executes first as it is entered the system first > The timestamp ordering protocol also maintains the timestamp of last ‘tead’ and ‘vrite’ operation on a data. Basic Timestamp ordering protocol works as follows: 1 Check the following’ condition whenever a transaction Ti issues a Read (X) operation: > If W_TS(X) >TS(Ti) then the operation is rejected, > If W_TS(X) <= TS(Ti) then the operation is executed. > Timestamps of all the data items are updated. Check the following condition whenever a transaction Ti issues a Write(X) operation: » If TS(Ti) < R_TS(X) then the operation is rejected, > IETS(Ti) < W_TS(X) then the operation is rejected-and Ti is rolled back otherwise the operation is executed DATABASE MANAGEMENT SYSTEMS: Where, TS(TI) denotes the timestamp of the transaction Ti . R_TS(X) denotes the Read time-stamp of data-item X. W_TS(X) denotes the Write time-stamp of data-item X. Advantages and Disadvantages of TO protocol: “> — TO protocol enstires serializability since the precedence graph is as follows: Transaction with larger TS Transaction with smaller TS Fig, : Precedence Graph for TS ordering > TS protocol ensures freedom from deadlock that means no transaction ever waits. > Butthe schedule may not be recoverable and may not even be cascade- free. Strict Timestamp Ordering A distinct form of Basic TO is called Strict TO confirm that the schedules have both the properties Strict and Conflict Serializable. In these changes, a Transaction T that provides a Read_itern (Z) or Write item (2) in such a way that TS (T) > Write_TS:(Z) has its read or write operation of functioning delayed up to the point when the Transaction T from which the values of Z wrote down has committed or terminated, ee et 5.1.3. Validation-based Protocols Q3. Write about validation based protocols in concurrency control. (imp.) Validation phase is also known as optimistic concurrency control technique. In the validation based protocol, the transaction is executed in the following three phases: 1. Read phase: In this phase, the transaction Tis read and executed, It is used to read the | hus —(188)- ‘Rahul Publications:value of various data items and stores them in temporary local variables. It can perform * allthe write operations on temporary variables without an update to the actual database. 2. Validation phase: In this phase, the temporary variable value will be validated against the actual data to see if it violates the serializability 3. Write pha: If the validation of the transaction is validated, then the temporary results are written to the database or system otherwise the transaction is rolled back. @ phases of condlvenily executing ions can be interleaved, but each: through the three phases as op istic concurrency ‘control executes fully in the hope go well during validation. on Ti has 3 timestamps: (Ti); the time when Ti started its ae reer by 1D oe jatvalidation time, to increase prok That is because the serializability order is not pre-decided and relatively less transactions will have to be rolled back. 9. Validation Test for Transaction Tj i) for all Ti with TS (TL) < TS (Tj) either ‘one of the following éondition holds: 1. finish(Ti ) < start(Tj ) 2, start(Tj ) < finish(Ti ) < validation(Tj ) and the set of data items written by Ti does not ere tt Hes ts eas tead by T). Rahul Pul 1 YEAR Il SEMI 3. Then validation succeeds and can be committed. Otherwise, validation fails and Tj is aborted.” ii) . du: ‘ation: Either first condition is satisfied, and there is no overlapped execution, or second condition ig satisfied and 4, — The writes of Tj do not affect reads of Ti since they occur after Ti has finished its reads. 5. the writes of Ti do not affect reads »e0f-Tj. sinice.-Tj, doesnot read. item written by Ti Schedule Produced by Validatio: Example of schedule produced usi validation | 5) ™ readlB> B:-B-50 readtay AAO seadi(Al (ealidatey display (AvB) Thomas write Rule Thomas Write Rule provides the guarantee of serializability order for the protocol. It improves the Basic Timestamp Ordering Algorithm. The basic Thomas write rules are as follows: >» — If TS(T) < R_TS(X) then transaction T is aborted and rolled back, and operation is rejected. * % IF TS(T) < W.TS{(X) then don't execute the _ W_item(X) operation of the transaction and. continue processing. » Ifneither condition 1 nor condition 2 occurs, then allowed to execute the WRITE by transaction Ti and set W_TS(X) to TST). |If'we use the Thomas write rule then some ‘erilizable schedule can be permitted that does not ‘fit sevalizable as itustrate by the schedule in a Fig. : A Serializable Schedule that is not Conflict Serializable In the above figure, T1’s read and precedes ‘Ti'swriteof the same data item, This schedule does not conflict serializable, Thomas write rule checks that T2's write is » operation in transaction T2, then conflict serializable schedule can be obtained which is shown in below figure. 7 12 R(A) Commit wW(A) Commit Fig. : A Conflict Serializable Schedule 5.1.4 Multiple Granularity Q4. Write about multiple granularity. Aas: Granularity: It is the size of data item 10 lock. Multiple Granularity » It ean be defined as hierarchically breaking up the database into blocks which can be lockéd, ‘The Multiple Granularity protocol enhances Concurrency and reduces lock overhead, It eae the track of what to lock and how It makes easy to decide eithér to lock a data ‘fam oF to unlock @ data item. This type of can be graphically represented as a never seen by any transaction, If we delete the write, For levels of nodes. > area. The higher level database exactly these areas.” The area consists of children nodes which are known as files. No file can be present in more. than one area, » — Finally, each file contains child nodes known as records, The file has exactly those records: that are its child nodes. No records represent in more than one file. > — Hence, the levels of the tree starting from the top level are as follows: Database Area File Record Re we Fig. : Multi Granularity tree Hierarchy In this example, the highest level shows the entire database. The levels below are file, a and fields. i There are three aie lock modes with multiple granularity: Intention Mode Lock ne aMCA : NEAR II SEMESTER Intention-Exclusive (IX): It contains explicit locking at a lower level with exclusive or shared Shared & Intention-Exclusive (SIX): In this lock, the node is locked in shared mode, and some node is locked in exclusive mode by the same transaction. Compatibility Matrix with Intention Lock Modes: The below table describes the compatibility matrix for these lock modes: Rey ee: oe mode. Finally, itneed: tolock Ry in S ne s record R,, in file F,, then it can do so after locking th Ay and fle. inlX mode, Finally, it Minette lock the R,, in X mode. > If transaction T3 reads all the records in file F,, then transaction T3 needs to lock the database, and area A in IS mode. At last, it needs to lock F, in S mode. » If transaction T4 reads the entire database, then T4 needs to lock the database in S mode. 5.1.5 Multi-version peiees Q5. Explain about multi version concurrency control techniques. Aus Multiversion Concurrency Control Techniques Other protocols for concurrency control keep the old values of a data item when the item is updated. These are brow as mulivenion coneurency onto, because several versions (values) of an im ae maintains Rahul Publications ule,Pes sv ‘An obvious drawback of multiversion quesis that more storage is needed to maintain wealiple versions of the database items Several multiversion concurrency control schemes have been proposed. We discuss two SSyemes here, one based on timestamp ordering and fhe other based on 2PL j, Multiversion Technique Based on Timestamp Ordering In this method, several versions X,, X», .. X, of each data item X ate maintained. For each version, the value of version X, and the following two timestamps are kept: read_TS(X,). The read timestamp of X, is the largest of all the timestamps of transactions that have successfully read version X, write _TS(X,). The write timestamp of X, is the timestamp of the transaction that wrote the value of version X,. Whenever a transaction T isallowed to execute a write_item(X) operation, a new version X,,, ofilem X iscreated, with both the write TS(X,,,) andthe read TS(X,_,)set to TS(T). Correspondingly, when a transaction T is allowed to read the value of version X, the value of read_TS(X) is set to the larger ‘of the current read_TS(X,) and TS(T) To ensure serializability, the following rules are used: If transaction T issues a write_item(X) operation, and'version i of X has the highest write_TS(X) of all versions of X that is also less than or equal to TS(T), and read_TS(X,) > TS(T), then abort and roll back transaction T, otherwise, create a new version X, of X with read TS(X,) = write TS(X) = TSIT). If transaction T issues a read_item(X) operation, find the version i of X. that has the highest write TS(X,) of all versions of X thatis also less than orequal to TS(T); then return the value of X, to transac- tion T, and set the value of read_TS(X) to the larger. of TS(T) and the current tead_TS(X). (159 DATABASE MANAGEMENT SYSTEMS ‘As.we can see in a read_item(X) is always successful, since it finds the appropriate version X, to read based on the write TS of the various existing versions of X. In case 1, however, transaction T may be aborted and rolled back. This happens if T attempts to write a version of X that should have been read by another transaction T whose timestamp is read_TS(X); however, T has already read version X, which was written by the transaction with timestamp equal to write_TS(X,). If this conflict occurs, T is rolled back; otherwise, a new version of X, written by transaction T, is created. Notice that if T is rolled back, cascading rollback may occur, Hence, to ensure recoverability, a transaction T should not be allowed to commit until after all the transactions that have written some version that T has read have committed. Multiversion Two-Phase Locking Using Certify Locks In this multiple-mode locking scheme, there are three locking modes for an item: read, write, and certify, Hence, the state of LOCK(X) for an item X can be one of read-locked, write-locked, certify-locked; or unlocked, in the standard scheme by means of the lock compatibility table shown in Figure (a). An entry of Yes means that if a transaction T holds the type of lock specified in the column header @ Read White Read| Yes. No Wiite | No No o 1 1 Rese Sa Read| Yeo Yes No wite| Yea “No No Coty} No “No No Fig. ; Lock comptaibility tables. (a) A compatibility table for read/write locking schemd. (b) A compatibility table for read/write / certify locking schemd ‘Rahul Peblications: