BCSE302L DBMS Module 5 PDF

Module - 5 Transaction Processing and Recovery LTPC BCSE302L - 3 0 0 3 BCSE302P - 0 0 2 1 Dr. Shashank Mouli Satapathy...

Module - 5 Transaction Processing and Recovery LTPC BCSE302L - 3 0 0 3 BCSE302P - 0 0 2 1 Dr. Shashank Mouli Satapathy Professor Grade 1, SCOPE School of Computer Science and Engineering Vellore Institute of Technology Vellore, Tamil Nadu - 632014, India September 25, 2024 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 1  Outline 1 Transaction Processing 2 Transaction States 3 Schedules & Serializability 4 Recovery Concepts Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 2  Transaction Processing Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 3  Introduction to Transaction Processing Transaction processing systems systems with large databases and hundreds of concurrent users executing database transactions. E.g., airline reservations, banking, credit card processing, online retail purchasing, stock markets, supermarket checkouts - require high availability and fast response time for hundreds of concurrent users. Concept of a transaction - logical unit of database processing that must be completed in its entirety to ensure correctness. Single-user versus Multi-user Systems Criterion for classifying a database system - Number of users who can use the system concurrently. Single-user if at most one user at a time can use the system. Multi-user if many users can use the system – hence access concurrently. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 4  Introduction to Transaction Processing Multi-programming - multi-users can access the database and use computer systems. It allows the operating system of the computer to execute multiple programs or processes at the same time. Interleaved Processing - Execute some commands from one process, then suspend that process and execute some commands from the next process, and so on. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 5  Introduction to Transaction Processing Parallel Processing - If the computer system has multiple hardware processors (CPUs) Transaction - executing program that forms a logical unit of database processing. This includes one or more database access operation - insertion, deletion, modification (update), or retrieval operations. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 6  Introduction to Transaction Processing Specifying transaction boundaries - Explicitly specify begin transaction and end transaction statements in an application program - all database access operations between the two are considered as forming one transaction. Read-only transaction - database operations in a transaction do not update the database but only retrieve data. Read-write transaction – both update and retrieve the data. Size of the data item is called the granularity – transaction processing is applied to the data item irrespective of the granularity. If the data item granularity is one disk block, then the disk block address can be used as the data item name. If the item granularity is a single record, then the record id can be the item name. The basic database access operations that a transaction can include are as follows: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 7  Introduction to Transaction Processing ➤ read item(X): Reads a database item named X into a program variable (say Program variable is also X) ➤ write item(X): Writes the value of program variable X into the database item named X Transfer from disk to main memory Executing a read item(X) command includes the following steps: ➤ Find the address of the disk block that contains item X. ➤ Copy that disk block into a buffer in main memory. ➤ Copy item X from the buffer to the program variable named X. Executing a write item(X) command includes the following steps: ➤ Find the address of the disk block that contains item X. ➤ Copy that disk block into a buffer in main memory ➤ Copy item X from the program variable named X into its correct location in the buffer. ➤ Store the updated disk block from the buffer back to disk Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 8  Introduction to Transaction Processing Example of Transaction Initially, the database state is as follows: When transaction T starts, the transaction processing system writes a begin transaction to the log file: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 9  Introduction to Transaction Processing Transaction T must read the data item x from disk into its memory buffer: To update data on disk, the transaction first update the data item x in its memory buffer: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 10  Introduction to Transaction Processing Transaction T writes the data item x from its buffer to disk: Transaction T then read y from disk into its memory buffer: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 11  Introduction to Transaction Processing T first update the data item y in its memory buffer: Transaction T writes the data from its buffer to disk: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 12  Introduction to Transaction Processing Finally, transaction T completes: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 13  Transaction States, Concepts Transaction Concept Two main issues to deal with: Concurrent execution of multiple transactions Recovery: Failures of various kinds, such as hardware failures and system crashes More specifically: After a transaction completes, the database must be in a consistent state. After a transaction completes, the changes it has made must persist. Failures must not corrupt the database, even during transaction execution. A transaction must see a consistent database. Multiple transactions should be able to execute in parallel. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 14  Transaction States, Concepts Why Concurrency Control is Needed? Concurrency control and recovery mechanisms are mainly concerned with the database commands in a transaction. Transactions submitted by the various users may execute concurrently and may access and update the same database items. If this concurrent execution is uncontrolled, it may lead to problems, such as an inconsistent database. Ex.: Airline reservations database in which a record is stored for each airline flight. Each record includes the number of reserved seats on that flight as a named (uniquely identifiable) data item. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 15  Transaction States, Concepts Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 16  Transaction States, Concepts The Lost Update Problem: This problem occurs when two transactions that access the same database items have their operations interleaved in a way that makes the value of some database items incorrect. Say, originally there were 80 reservations on the flight (X = 80). T1 transfers 5 seat reservations from the flight corresponding to X to the flight corresponding to Y (N = 5). M = 4 (T2 reserves 4 seats on X), the final result should be X = 79. However, in the interleaving of operations, it is X = 84 because the update in T1 that removed the five seats from X was lost. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 17  Transaction States, Concepts Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 18  Transaction States, Concepts The Temporary Update (or Dirty Read) Problem: This problem occurs when one transaction updates a database item and then the transaction fails for some reason. Meanwhile, the updated item is accessed (read) by another transaction (before the previous transaction is rollbacked). T1 updates item X and then fails before completion, so the system must roll back X to its original value. transaction T2 reads the temporary value of X, which will not be recorded permanently in the database because of the failure of T1. The value of item X that is read by T2 is called dirty data because it has been created by a transaction that has not been completed and committed – dirty read problem. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 19  Transaction States, Concepts Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 20  Transaction States, Concepts The Incorrect Summary Problem: If one transaction is calculating an aggregate summary function on a number of database items while other transactions are updating some of these items. The aggregate function may calculate some values before they are updated and others after they are updated. T3 is calculating the total number of reservations on all the flights, meanwhile, transaction T1 is executing. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 21  Transaction States, Concepts Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 22  Transaction States, Concepts The Unrepeatable Read Problem: Another problem that may occur is called unrepeatable read, where a transaction T reads the same item twice and the item is changed by another transaction T’ between the two reads. Hence, T receives different values for its two reads of the same item. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 23  Transaction States, Concepts Why Recovery Is Needed? Whenever a transaction is submitted to a DBMS, ➤ either all the operations in the transaction are completed successfully and their effect is recorded permanently in the database – committed. ➤ the transaction does not have any effect on the database or any other transactions - Aborted. Types of Failures - Failures are generally classified as transaction, system, and media failures. Reasons for a transaction to fail in the middle of execution: ➤ A computer failure (system crash): A hardware, software, or network error occurs in the computer system during transaction execution (hardware crash is called media failure – main memory failure) ➤ A transaction or system error: Some operation in the transaction may cause it to fail, such as integer overflow or division by zero. Transaction failure may also occur because of erroneous parameter values or because of a logical programming error. Additionally, the user may interrupt the transaction during its execution. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 24  Transaction States, Concepts ➤ Local errors or exception conditions detected by the transaction: Certain conditions may occur that necessitate cancellation of the transaction. For example, data for the transaction may not be found. An exception condition, such as insufficient account balance in a banking database, may cause a transaction, such as a fund withdrawal, to be canceled. This exception could be programmed in the transaction itself, and in such a case would not be considered as a transaction failure. ➤ Concurrency control enforcement: The concurrency control method may abort a transaction because it violates serializability, or it may abort one or more transactions to resolve a state of deadlock among several transactions. Transactions aborted because of serializability violations or deadlocks are typically restarted automatically at a later time. ➤ Disk failure: Some disk blocks may lose their data because of a read or write malfunction or because of a disk readwrite head crash. This may happen during a read or a write operation of the transaction. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 25  Transaction States, Concepts ➤ Physical problems and catastrophes: This refers to an endless list of problems that includes power or air-conditioning failure, fire, theft, sabotage, overwriting disks or tapes by mistake, and mounting of a wrong tape by the operator. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 26  Transaction States, Concepts Transaction States and Additional Operations Transaction is an atomic unit of work – recovery manager has to keep track of BEGIN TRANSACTION: This marks the beginning of transaction execution. READ or WRITE: These specify read or write operations on the database items that are executed as part of a transaction. END TRANSACTION: This specifies that READ and WRITE transaction operations have ended and marks the end of transaction execution. [Either commit or abort could have happened at the end.] COMMIT TRANSACTION: This signals a successful end of the transaction so that any changes (updates) executed by the transaction can be safely committed to the database and will not be undone. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 27  Transaction States, Concepts ROLLBACK (or ABORT): This signals that the transaction has ended unsuccessfully so that any changes or effects that the transaction may have applied to the database must be undone. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 28  Transaction States, Concepts Active: This is the initial state. T he transaction stays in this state while it is executing Partially Committed: When a transaction executes its final operations/instruction, it is said to be in a partially committed state. Failed: Discovery that normal execution can no longer proceed. Once a transaction cannot be completed, any changes that it made must be undone Roll back the transaction. Aborted: The state after the transaction has been rolled back and the database restored to its state prior to the start of the transaction. There are two options after it has been aborted: Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 29  Transaction States, Concepts ➤ restart the transaction! [can be done only if no internal logical error] ➤ kill the transaction Committed: The transaction enters in this state after successful completion of the transaction(after committing transaction) We cannot abort or rollback a committed transaction. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 30  Transaction States, Concepts The System Log Keep track of all transaction operations that affect the values of database items. When log buffer is full it is appended to log file. T – transaction id (generated automatically by the system) [start transaction, T]: Indicates that transaction T has started execution. [write item, T, X, old value, new value]: Indicates that transaction T has changed the value of database item X from old value to new value. [read item, T, X]: Indicates that transaction T has read the value of databaseitem X. [commit, T]: Indicates that transaction T has completed successfully, and affirms that its effect can be committed (recorded permanently) to the database. [abort, T]: Indicates that transaction T has been aborted. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 31  Desirable Properties of Transactions Transactions should possess several properties – ACID properties Atomicity (Either transaction execute 0% or 100%) Consistency (database state must remain in a consistent state after execution of any transaction) Isolation (Intermediate transaction result must be hidden from other concurrently executed transactions) Durability (Once a transaction completed successfully, the changes it has made into the database should be permanent) Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 32  Desirable Properties of Transactions Atomicity This property states that a transaction must be treated as an atomic unit that is, either all of its operations are executed or none [Either transaction execute 0% or 100%] For example, consider a transaction to transfer Rs 50 from account A to account B In this transaction if Rs 50 is deducted from account A then it must be added to account B Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 33  Desirable Properties of Transactions Consistency The database must remain in a consistent state after any transaction. If the database was in a consistent state before the execution of a transaction, it must remain consistent after the execution of the transaction as well. When the transaction completes successfully the database must be consistent. During the transaction execution the database may be temporarily inconsistent. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 34  Desirable Properties of Transactions In the given example, the total of A+B must remain same before and after the execution of the transaction. Execution of a transaction in isolation preserves the consistency of the database. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 35  Desirable Properties of Transactions Isolation Although multiple transactions may execute concurrently each transaction must be unaware of other concurrently executing transactions. Intermediate transaction results must be hidden from other concurrently executed transactions. That is, for every pair of transactions Ti and Tj it appears to Ti that either Tj finished execution before Ti started, or Tj started execution after Ti finished. Isolation can be ensure trivially by running transactions serially that is, one after another. However, executing multiple transactions concurrently has significant benefits. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 36  Desirable Properties of Transactions Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 37  Desirable Properties of Transactions Durability After a transaction completes successfully, the changes it has made to the database persist even if there are system failures. Once the user has been notified that the transaction has completed up to the last step(step 6 )(i.e., the transfer of the Rs 50 has taken place), the updates to the database by the transaction must persist permanently despite failures. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 38  Schedule Schedule - a sequences of instructions that specify the chronological order in which instructions of concurrent transactions are executed. ➤ A schedule for a set of transactions must consist of all instructions of those transactions. ➤ Must preserve the order in which the instructions appear in each individual transaction. Given a set of transactions, where each transaction consists of a sequence of instructions, a schedule is a sequence of instructions for the transactions specified in chronological order of execution. A transaction that successfully completes its execution will have a commit instructions as the last statement [By default transaction assumed to execute commit instruction as its last step]. A transaction that fails to successfully complete its execution will have an abort instruction as the last statement. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 39  Schedule Schedule 1 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 40  Schedule Schedule 2 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 41  Schedule Schedule 3 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 42  Schedule Schedule 4 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 43  Schedule There can be many possible schedules for n transactions set. A serial schedule is one in which no transaction starts until a running transaction has ended [Transactions are executed one after other.] There are n! different serial schedules for set of n transaction set. For example there are T1, T2 and T3 are currently executing in the system. The possible 6(3!) serial schedule are: ➤ T1, T2, T3 ➤ T1, T3, T2 ➤ T2, T1, T3 ➤ T2, T3, T1 ➤ T3, T1, T2 ➤ T3, T2, T1 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 44  Schedule Conflicting Operations in a Schedule Two operations in a schedule are said to conflict if they satisfy all three of the following conditions: 1 they belong to different transactions; 2 they access the same item X; and 3 at least one of the operations is a write item(X) Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 45  Schedule Complete Schedule A schedule S of n transactions T1, T2,... , Tn is said to be a complete schedule if the following conditions hold: ➤ The operations in S are exactly those operations in T1, T2,... , Tn, including a commit or abort operation as the last operation for each transaction in the schedule. ➤ For any pair of operations from the same transaction Ti , their relative order of appearance in S is the same as their order of appearance in Ti. ➤ For any two conflicting operations, one of the two must occur before the other in the schedule. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 46  Serializability The db system must control concurrent execution of transactions to ensure the consistency of the db system. The objective is to find non serial schedule that allow transactions to execute concurrently without interfering with one another and there by produce a db state that is equivalent too one of the serial schedule. A (possible concurrent) schedule is serializable if it is equivalent to a serial schedule. Different form of equivalence leads different kind of serializability. ➤ Conflict Serializability ➤ View Serializability Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 47  Serializability Serial, Non-serial, and Conflict-Serializable Schedules Serial schedules - the operations of each transaction are executed consecutively, without any interleaved operations. (e.g. in the previous slide). only one transaction at a time is active Non-serial schedules - each sequence interleaves operations from the two transactions. Problem with serial schedules is that: They limit concurrency by prohibiting interleaving of operations. if a transaction waits for an I/O operation to complete, we cannot switch the CPU processor to another transaction, thus wasting valuable CPU processing time. if some transaction T is long, the other transactions must wait for T to complete all its operations before starting. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 48  Serializability If li and lj are consecutive in a schedule and they do not conflict, their results would remain the same even if they had been interchanged in the schedule. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 49  Serializability Conflict Serializability An order is forced on two transaction if they access the same data and at least one changes it. If both the transactions consecutive instructions access different data item then they are not conflicting instructions. A schedule S of n transactions is serializable, if it is equivalent to some serial schedule of the same n transactions. Two schedules are called result equivalent, if they produce the same final state of the database. Two schedules are said to be conflict equivalent, if the order of any two conflicting operations is the same in both schedules. Schedule S is conflict serializable, if it is conflict equivalent to some serial schedule S’. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 50  Serializability Testing for Serializability of a Schedule There is a simple algorithm for determining whether a particular schedule is (conflict) serializable or not. Precedence Graph or Serialization Graph is used commonly to test Conflict Serializability of a schedule. It is a directed Graph (V, E) consisting, set of nodes V = T1 , T2 , T3 ,... Tn set of directed edges E = e1 , e2 , e3 ,..., em The graph contains one node for each Transaction Ti. An edge ei is of the form Tj → Tk where Tj is the starting node of ei and Tk is the ending node of ei. Create a node T in the graph for each participating transaction in the schedule. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 51  Serializability For the conflicting operation read item(X) and write item(X) – If a Transaction Tj executes a read item (X) after Ti executes a write item (X), draw an edge from Ti to Tj in the graph. For the conflicting operation write item(X) and read item(X) – If a Transaction Tj executes a write item (X) after Ti executes a read item (X), draw an edge from Ti to Tj in the graph. For the conflicting operation write item(X) and write item(X) – If a Transaction Tj executes a write item (X) after Ti executes a write item (X), draw an edge from Ti to Tj in the graph. The Schedule S is serializable if there is no cycle in the precedence graph. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 52  Serializability Example 1 Consider the schedule S : r1(x) r1(y) w2(x) w1(x) r2(y) Example 2 Consider the schedule S : S : R1(A), R2(A), R1(B), R2(B), R3(B), W1(A), W2(B) Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 53  Serializability Example 3 Example 4 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 54  Serializability Example 5 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 55  Serializability Example 6 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 56  Serializability Practice Exercise Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 57  Serializability View Serializability A schedule is said to be View-Serializable, if it is view equivalent to a Serial Schedule (where no interleaving of transactions is possible). Let s1 and s2 be two schedules for the same set of transactions. S1 and S2 are view equivalent if the following three conditions are satisfied, for each data item Q. 1 Initial Read 2 Updated Read 3 Final Write Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 58  Serializability Initial Read If in S1, transaction Ti reads the initial value of Q , then in schedule s2 also transaction Ti must read the initial value of Q. The two schedule s1 and s3 are not view equivalent because initial read operation in s1 is done by T1 and in s3 it is done by T2. The two schedule s1 and s2 initial read operation in s1 is done by T1 and also in s2 it is done by T1. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 59  Serializability Updated Read If in schedule S1 transaction Ti executes read(Q), and that value was produced by transaction Tj ,(if any), then in schedule S2 also transaction Ti must read the value of Q that was produced by the same write(Q) operation of transaction Tj. In S1, T3 is reading the value of A that is updated by T2 and in S2 also, T3 is reading the value of A that is updated by T2. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 60  Serializability Above two schedules are not view equivalent because, in S1, T3 is reading the value of A that is updated by T2 and in S3, T3 is reading the value of A that is updated by T1. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 61  Serializability Final Write If Ti performs final write on the data item Q in S1 then it also performs the final write on the dataitem Q in S2. Above two schedules are view equivalent because final write operation of A in S1 is done by T3 and in S2 also the final write operation of A is also done by T3. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 62  Serializability View Equivalence Let S1 and S2 be two schedules with the same set of transactions participate in both schedules. The schedules S1 and S2 are said to be view equivalent if three conditions are met: 1 If Ti reads initial value of A in S1, then Ti also reads initial value of A in S2. 2 If Ti reads value of A written by Tj in S1, then Ti also reads value of A written by Tj in S2. 3 If Ti writes final value of A in S1, then Ti also writes final value of A in S2 The view equivalence is purely based on read and write operation. The concept of view equivalence leads to the concept of view serializability. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 63  Serializability We say that a schedule S is view serializable if it is view equivalent to a serial schedule. Every conflict serializable schedule is view serializble. The schedule is not conflict serializable. Schedule S1 is view equivalent to serial schedule. T2 and T3 perform the write(Q) operation without having performed a read(Q) operation. This type of write operation is known as blind write. Every view serializable schedule that is not conflict serializable must contain at least one blind write. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 64  Recoverability For some schedules it is easy to recover from transaction and system failures. Some schedules are not possible to recover correctly after a failure. Hence, it is important to characterize the types of schedules for which recovery is possible, as well as those for which recovery is relatively simple - characterize the different types of schedules based on recoverability. recoverable schedule - Each transaction commits only after all transactions from which it has read has committed. Ex:- S1: R1(x), W1(x), R2(x), R1(y), R2(y), W2(x), W1(y), C1, C2; Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 65  Recoverability Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 66  Recoverability Consider the following schedule. Now suppose that T9 commits immediately after the read, but before T8 commits. The following schedule is not recoverable if T9 commits immediately after the read. The above schedule is said to be non-recoverable. If T8 should abort, T9 would have read an inconsistent database state. Hence, database must ensure that schedules are recoverable. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 67  Recoverability Schedule 9 is said to recoverable if T9 would have to delay committing until after T8 commits. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 68  Recoverability The DBMS must ensure that all concurrent schedules are recoverable by imposing the above ordering on transaction commits. However, even if the DBMS does ensure that schedules are recoverable, significant rework might still occur in the context of an abort. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 69  Recoverability Practice Question: Check if the schedule is recoverable, Sc: r1(X); w1(X); r2(X); r1(Y); w2(X); c2; a1; Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 70  Recoverability Practice Question: Check if the schedule is recoverable, Sc: r1(X); w1(X); r2(X); r1(Y); w2(X); c2; a1; Answer: Not recoverable Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 71  Recoverability Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 72  Recoverability Cascading rollback (or cascading abort) - uncommitted transaction has to be rolled back because it read an item from a transaction that failed. Costlier and time consuming. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 73  Recoverability Because cascading rollback can be time-consuming—since numerous transactions can be rolled back - it is important to characterize the schedules where this phenomenon is guaranteed not to occur – cascadeless or to avoid cascading rollback. If every transaction in the schedule reads only items that were written by committed transactions. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 74  Recoverability Cascadeless schedule allows only committed read operations. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 75  Recoverability Strict schedule allows only committed read and write operations. Clearly, strict schedule implements more restrictions than cascadeless schedule. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 76  Recoverability Practice Question: Check if the schedule is cascadeless recoverable or not, Sc: r1(x), r2(z), r1(z), r3(x), r3(y), w1(x), w3(y), r2(y), w2(z), c1, c3, c2 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 77  Recoverability Practice Question: Check if the schedule is cascadeless recoverable or not, Sc: r1(x), r2(z), r1(z), r3(x), r3(y), w1(x), w3(y), r2(y), w2(z), c1, c3, c2 Answer: Transactions are committing in the same order as they are completing their task. Hence the schedule is recoverable. Cascadeless Recoverable?? - NO. Analyze the pair w3(y) - r2(y). As T2 is reading the value of y, updated by T3, but T3 is not committed yet, hence due W-R issue, it is not cascadeless recoverable schedule. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 78  Recoverability Practice Question: Check if the schedule is strict recoverable or not, Sc: r1(x), r2(z), r3(x), r1(z), r2(y), r3(y), w1(x), c1, w2(z), w3(y), w2(y), c3, c2 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 79  Recoverability Practice Question: Check if the schedule is strict recoverable or not, Sc: r1(x), r2(z), r3(x), r1(z), r2(y), r3(y), w1(x), c1, w2(z), w3(y), w2(y), c3, c2 Answer: Transactions are committing in the same order as they are completing their task. Hence the schedule is recoverable. Cascadeless Recoverable?? - YES, as there is no dirty read (W-R) situation. Strict recoverable?? - NO. Analyze the pair w3(y) - w2(y). As T2 is writing the value of y, updated by T3, but T3 is not committed yet, hence due W-W issue, it is not a strict recoverable schedule. Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 80 Dr. Shashank Mouli Satapathy VIT - SCOPE - Database Systems BCSE302L - Module 5 September 25, 2024 81