Module 5 Chapter 1: Transaction Processing 5.0 Introduction 5.1 Objectives 5.2 Introduction to Transaction Procéssing 5.2.1 Single-User versus Multiuser Systems 5.2.2 Transactions, Database Items, Read and Write Operations, and DBMS Buffers 5.2.3 Why Concurrency Control Is Needed 5.2.4 Why Recovery Is Needed $.3 Transaction and System Concepts 5.3.1 Transaction States and Additional Operations 5.3.2 The System Log, 5.3.3 Commit Point of a Transaction: 5.34 DBMS specific buffer Replacement policies 5.4 Desirable Properties of Transactions 5.5 Characterizing Schedules Based on Recoverability 5.6 Characterizing Schedules Based on Serializal 5.6.1 Testing conflict serializability of a Schedule S 5.7 Transaction Support in SQL 5.8 Introduction to Concurrency Control 5,9 Two-Phase Locking Techniques for Concurrency Control 5.9.1 Types of Locks and System Lock Tables 5.9.2 Guaranteeing Serializability by Two-Phase Locking 5.10 Variations of Two-Phase Locking 5.11 Dealing with Deadlock and Starvation 5.11 Deadlock Detection. 5.13 Concurrency Control Based on Timestamp Ordering 5.13.1 Timestamps 5.13.2 The Timestamp Ordering Algorithm 3.14Maliversion Concurrency Control Techniques 5.14.1 Multiversion Technique Based on Timestamp Ordering -Phase Locking Using Certify Locks 5.15 Validation (Optimistic) Concurrency Control Techniques 3.16 Granularity of Data Items and Multiple Granularity Locking 5.16.1 Granularity Level Considerations for Locking 5.16.2 Multiple Granularity Level Locking 5.14.2 Multiversion Tw5.0 Introduction The concept of transaction provides 2 mechanism for describing logical units of database processing. Transaction processing systems are systems with large databases and hundreds of concurrent users executing database transactions. Examples: + airline reservations + barking + credit card processing, + online retail purchasing + Stock markets, supermarket checkouts, and many other applications These systems require high availability and fas! response time for huncreds of concurrent users. A transaction is typically implemented by a computer program, which includes database commands such as retrievals, insertions, deletions, and updates. 1 Objectives “To study transaction properties. 4 To study creation of schedule and maintaining schedule equivalence, + To check whether the given schedule is serailizable or not % To study protocols used for locking objects + Differentiating between 2PL and Strict 2PL §.2 Introcuction to Transaction Processing 5.2.1 Single-User versus Multiuser Systems * One criterion for classifying a database system is according to the number of users who can use the system concurrently Single-User versus Multiuser Systems = ADBMS is + single-user ~at most one user at a time can use the system - Eg: Personal Computer Systerr + multiuser = many users can use the system and hence access the database concurrentl, - Eg: Airline reservation databaseConcurrent acoass is possible because of Multiprogramming. Multiprogramming car be achieved by: + interleaved executor + Parallel Processing Multiprogramming operating systems execute some commands trom one process, then suspend that process and execute some commands from the next process, and so on A process is resumed at the point where t was suspended whenever it gets its turn to use the CPU again Hence, concurrent execution of processes is actually interleaved, as illustrated in Figure 24.1 Figure 21.1 Interleaved proc ing versus parallel processing of cr current transactions Figure 21.1, shows two processes, A and B, executing concurrently in an interleaved fashion Interleaving keeps the CPU busy when 2 process joa iras an input oF cutput (VO) operation, such as reading a block from disk The CPU is switched to execute another process rather har remairing idle during VO time interleaving also prevents 2 long process from delaying other processes. If the computer system has multiple hardware processers (CPUs), parallel processing of multiple processes is possible, as illustrated by processes C and D in Figure 21.1 Most of the theory concerning concurrency control in databases is developed in terms of interleaved concurrency In @ multiuser DBMS, the stored data items are the primary resources that may be accessed concurrently by interactive users or apolication programs, which are constantly retrieving information from and modifying the database.§.2.2 Transactions, Database Items, Read and Write Operations, and DBMS Buffers * A Transaction an executing program that forms a logical unit of database processing + It includes one or more DB access operations such as insertion, deletion, modification o1 retrieval operation = It-can be either embedded within an application program using begin transaction anc end transaction statements Or specified interactively via a high level query language such as SQL + Transaction which do not update database are known as read only transactions. = Transaction which co update database are known as read write transactions, "A database is basically represented as a collection of named data items The size of ¢ data item is called its granularity "A data item can be a database record, but it can also be @ larger unit such as a whole disk block. or even a smaller Unit such as an indivicual field (attribute) value of some record in the database "Each data item has a unique name "Basic DB access operations that a transaction can include are: + read_item(X): Reads a DB item named X intoa program variable. + write_item(X): Writes the value of a program variable into the DB item named X * Executing read_item(X) include the following steps: 1. Find the address of the disk block that contains item X 2. Copy the block into a buffer in main memory 3, Copy the item X from the butferto program variable named X. "Executing write_item(X) include the following stops: 1. Find the address of the disk block that contains item X 2. Copy the disk block into a buffer in main memory 3. Copy item X from program variable named X into its correct location in buffer. 4, Store the updated disk block from bufler back to disk (either immediately or later). * Decision of when to store a modified disk block is handled by recovery manager of the DBMS in cooperation with operating system. + ADB cache includes a number of data buffers * When the buffers are all occupied a buffer replacement pclicy is used to choose one of the buffers to be replacec. EG: LRU«A transaction includes read_item and write_item operations to access and update DB, @ ty ) is Figure 2 as read_item(X); read_item(X); fons. (@) Transaction X=X-N; X=X+M: Ty. (b) Transaction To write_item(X); write_item0); tead_item(Y); Y=Y+N; write item(Y); + The read-set of a transactior is the set of ail items that the transaction reads + The write-set is the set of ell items that the transaction writes + For example, the read-set of 71 in Figure 21.2 is (X_Y)and its write-set is also (X. Y} 3 Why Concurrency Control Is Needed Several problems can occur when concurrent transactions execute in an uncontrolled panes ‘ample + We consider an Airline reservation DB + Each records is stored for an airline flight which includes Number of reserved seats among other information + Types cf problems we may encounter: 1. The Lost Update Problem 2. The Temporary Update (or Dirty Read) Problerr 3, The Incorrect Summary Problem 4. The Unrepeatable Read Problerr Th Th read_item(X); read_item(X); X=X+M; X=X-N; write_item(X); write_item(X); read_item(Y) Y=Y+N; write_item(Y);= Transaction 11 + transfers N reservations from one flight whose number of reserved seats is stored in the database item named X to ancther fight whose number of reserved seats is stored in the database item named Y. + Transaction T2 + reserves M seats on the first fight (X) 1. The Lost Update Problem * occurs when two transactions that access the same DB items have their operations interleaved in a way that makes the value of some DB item incorrect * Suppose that transactions T1 and T2 are submittec at approximately the same time, and ‘suppose that their operations are interleaved as shown in Figure below read_item(X); XaX+M; Time ER Item X has an incorrect value because ‘waite tem(A); 1“ — its update by T; is fost (overwritten). Y=Yen, write_item(Y); "Final value of item Xis incorrect because [2 reads the value of X before T1 changes it in the database, and hence the updated value resulting from T1 is lost. * For example: X = 80 at the start (there were 80 reservations on the flight) N= 5 (71 transfers 5 seat reservations from the flight corresponding to X to the flight corresponding to Y M=4 (72 reserves 4 seats on X) The final result should be X = 78, + The interleaving of operations shown in Figure is X = 84 because the update in T1 that removed the five seats from X was lost.