香港科技大学：Transaction Management、Serializability Theory and Concurrency Control、Lock-Based Protocols、Deadlock Problems、Recovery

Transaction Management Department of Computer Science and Engineering, HKUST 1

Department of Computer Science and Engineering, HKUST 1 Transaction Management

Introduction Time sharing systems executes more than one program at the same time by interleaving the execution of the programs In DBMS we consider transactions, not programs a transaction is a database program that must be completed entirely in order to retain the consistency of the database if the transaction cannot be completed the database should remain at the same state as if the transaction hadn 't been executed at all if the database is initially in consistent state(or empty), a sequence of transactions would bring the database from one consistent state to another Concerned only with interleaved execution of transactions Department of Computer Science and Engineering, HKUST 2

Department of Computer Science and Engineering, HKUST 2 • Time sharing systems executes more than one program at the same time by interleaving the execution of the programs • In DBMS, we consider transactions, not programs • A transaction is a database program that must be completed entirely in order to retain the consistency of the database; if the transaction cannot be completed, the database should remain at the same state as if the transaction hadn’t been executed at all • Concerned only with interleaved execution of transactions Introduction If the database is initially in consistent state (or empty), a sequence of transactions would bring the database from one consistent state to another

Assumptions and Basic operations a database is a set of data items accessed and modified by transactions o a transaction accesses or modifies the contents of a database 口 read item(x)orR(X): Reads a database itemⅩ a write_item(X)or W(X): Writes a value into the database item X a Additional operations Commit- the transaction is successful and the data items value must be changed(if any) on the database permanently Rollback/Abort- the transaction is not successful, do not change any of the data values BEGIN TRANSACTION, END TRANSACTION a data item x could be. An attribute DBMS may need UNDO and REDO for database recovery. A column A row A page(of tuples) A table Department of Computer Science and Engineering, HKUST 3

Department of Computer Science and Engineering, HKUST 3 • A database is a set of data items accessed and modified by transactions • A transaction accesses or modifies the contents of a database  read_item(X) or R(X): Reads a database item X  write_item(X) or W(X): Writes a value into the database item X  Additional operations: – Commit - the transaction is successful and the data items value must be changed (if any) on the database permanently – Rollback/Abort - the transaction is not successful, do not change any of the data values – BEGIN_TRANSACTION, END_TRANSACTION DBMS may need UNDO and REDO for database recovery Assumptions and Basic Operations A data item X could be: • An attribute • A column • A row • A page (of tuples) • A table

Correctness Requirement of Transactions a database state consists of the complete set of data values in the database a database state is consistent if the database obeys all the integrity constrain a transaction brings the database from one consistent state to another consistent state whether or not The transaction is executed alone or concurrently with other transactions Failures occur in any transaction during its execution Database in a Database may be temporarily in an Database in a consistent state inconsistent state during execution consistent state Execution of transaction Begin Transaction End transaction Department of Computer Science and Engineering, HKUST 4

Department of Computer Science and Engineering, HKUST 4 • A database state consists of the complete set of data values in the database • A database state is consistent if the database obeys all the integrity constraint • A transaction brings the database from one consistent state to another consistent state, whether or not: • The transaction is executed alone or concurrently with other transactions • Failures occur in any transaction during its execution Database in a consistent state Database may be temporarily in an inconsistent state during execution Database in a consistent state Begin Transaction End Transaction Correctness Requirement of Transactions Execution of Transaction

States of a Transaction Read/rite transaction.( active transaction, Partially-commit committed committed abort failed terminated Active: transaction is started and is issuing reads and writes to the database Partially committed: operations are done and values are ready to be written to the database Committed: writing to the database is permitted and successfully completed Abort: the transaction or the system detects a fatal error Terminated: transaction leaves the system Department of Computer Science and Engineering, HKUST 5

Department of Computer Science and Engineering, HKUST 5 Active: transaction is started and is issuing reads and writes to the database Partially committed: operations are done and values are ready to be written to the database Committed: writing to the database is permitted and successfully completed Abort: the transaction or the system detects a fatal error Terminated: transaction leaves the system active Partially committed failed terminated committed Begin transaction End transaction commit abort abort Read/Write States of a Transaction

Other Properties of a Transaction Incomplete transactions cannot reveal its results to other transactions before commitment Committed updates are persistent (won't be lost) Once a transaction commits, the system must guarantee that the results of its operations will never be lost(database recovery) Department of Computer Science and Engineering, HKUST 6

Department of Computer Science and Engineering, HKUST 6 Other Properties of a Transaction • Incomplete transactions cannot reveal its results to other transactions before commitment • Committed updates are persistent (won’t be lost) • Once a transaction commits, the system must guarantee that the results of its operations will never be lost (database recovery)

Requirements on the DBMS o maintain database consistency over time(consistency atomicity) To ensure multiple users can simultaneously access and modify the data without creating inconsistency(isolation) To make the changes to data permanent (durability) Consistency atomicity and durability are needed even if transactions are executed serially (i.e. no interleaving) Department of Computer Science and Engineering, HKUST 7

Department of Computer Science and Engineering, HKUST 7 • To maintain database consistency over time (consistency, atomicity) • To ensure multiple users can simultaneously access and modify the data without creating inconsistency (isolation) • To make the changes to data permanent (durability) • Consistency, atomicity and durability are needed even if transactions are executed serially (i.e., no interleaving) Requirements on the DBMS

Why is Concurrency Control Needed? Several problems occur when concurrent transactions execute in an uncontrolled manner A sChedule of concurrent transactions is a particular sequence of interleaving of their read or write operations In general a transaction, has a set of data items it accesses (read set), and a set of data items it modifies( write set Department of Computer Science and Engineering, HKUST 8

Department of Computer Science and Engineering, HKUST 8 • Several problems occur when concurrent transactions execute in an uncontrolled manner • A schedule of concurrent transactions is a particular sequence of interleaving of their read or write operations • In general a transaction, has a set of data items it accesses (read set), and a set of data items it modifies (write set) Why is Concurrency Control Needed?

Problem 1: Lost Update Problem a transaction overwrites a data item modified by other transactions Transaction 1(HK ATM) Transaction 2(KIn ATm) RI(Balance) R2 Balance Balance=Balance +500 Balance=Balance-700 W1(Balance) W2(Balance) Schedule 1 Balance Schedule 2 Balance RI(Balance) 1000 RI(Balance) 1000 R2(Balance) 1000 R2(Balance) 1000 WI(Balance) 1500 W2(Balance) 300 overwrite W2( Balance) 300 WI(Balance) 1500 overwrite The correct(consistent)value of Balance is 800, when initial Balance is 1000 Department of Computer Science and Engineering, HKUST 9

Department of Computer Science and Engineering, HKUST 9 A transaction overwrites a data item modified by other transactions The correct (consistent) value of Balance is 800, when initial Balance is 1000 Transaction 1 (HK ATM) R1(Balance) Balance=Balance + 500 W1(Balance) Transaction 2 (Kln ATM) R2(Balance) Balance=Balance - 700 W2(Balance) Schedule 1 Balance R1(Balance) 1000 R2(Balance) 1000 W1(Balance) 1500 W2(Balance) 300 Schedule 2 Balance R1(Balance) 1000 R2(Balance) 1000 W2(Balance) 300 W1(Balance) 1500 Problem 1: Lost Update Problem overwrite overwrite

Problem 2: Dirty Read a transaction reads uncommitted modified data item values updated by other transactions Transaction 1(HK ATM) Transaction 2(KIn ATM) RI(Balance) R2 Balance) Balance=Balance +500 Balance=Balance-1200 WI(Balance) W2( Balance) abort Commit Schedule RI(Balance) 1000 T2 read a wIBalance) 1500 For a consistent database ction dirty value also be aborted from t1 W2(Balance) 300 Abort tl Commit t2 300 Department of Computer Science and Engineering, HKUST 10

Department of Computer Science and Engineering, HKUST 10 A transaction reads uncommitted modified data item values updated by other transactions. For a consistent database state, Transaction 2 should also be aborted Transaction 1 (HK ATM) R1(Balance) Balance=Balance + 500 W1(Balance) Abort Transaction 2 (Kln ATM) R2(Balance) Balance=Balance -1200 W2(Balance) Commit Schedule R1(Balance) 1000 W1(Balance) 1500 R2(Balance) 1500 W2(Balance) 300 Abort T1 Commit T2 300 Problem 2: Dirty Read T2 read a “dirty value” from T1