Question? Leave a message!




Introduction to Transaction Management

Introduction to Transaction Management
Chapter 8: Introduction to Transaction Management • Definition and Examples • Properties • Classification • Processing Issues Acknowledgements: I am indebted to Arturas Mazeika for providing me his slides of this course. DDB 2008/09 J. Gamper Page 1Definition • Transaction: A collection of actions that transforms the DB from one consistent state into another consistent state; during the exectuion the DB might be inconsistent. DDB 2008/09 J. Gamper Page 2Definition . . . • States of a transaction – Active: Initial state and during the execution – Paritally committed: After the final statement has been executed – Committed: After successful completion – Failed: After the discovery that normal execution can no longer proceed – Aborted: After the transaction has been rolled back and the DB restored to its state prior to the start of the transaction. Restart it again or kill it. DDB 2008/09 J. Gamper Page 3Example • Example: Consider an SQL query for increasing by 10 the budget of the CAD/CAM project. This query can be specified as a transaction by providing a name for the transaction and inserting a begin and end tag. Transaction BUDGETUPDATE begin EXEC SQL UPDATE PROJ SET BUDGET = BUDGET 1.1 WHERE PNAME = "CAD/CAM" end. DDB 2008/09 J. Gamper Page 4Example . . . • Example: Consider an airline DB with the following relations: FLIGHT(FNO, DATE, SRC, DEST, STSOLD, CAP) CUST(CNAME, ADDR, BAL) FC(FNO, DATE, CNAME, SPECIAL) • Consider the reservation of a ticket, where a travel agent enters the flight number, the date, and a customer name, and then asks for a reservation. Begin transaction Reservation begin input(flightno, date, customername); EXEC SQL UPDATE FLIGHT SET STSOLD = STSOLD + 1 WHERE FNO = flightno AND DATE = date; EXEC SQL INSERT INTO FC(FNO, DATE, CNAME, SPECIAL); VALUES (flightno, date, customername, null); output("reservation completed") end. DDB 2008/09 J. Gamper Page 5Example . . . • Example (contd.): A transaction always terminates – commit or abort. Check the availability of free seats and terminate the transaction appropriately. Begin transaction Reservation begin input(flight no, date, customer name); EXEC SQL SELECT STSOLD,CAP INTO temp1,temp2 FROM FLIGHT WHERE FNO = flight no AND DATE = date; if temp1 = temp2 then output("no free seats"); Abort else EXEC SQL UPDATE FLIGHT SET STSOLD = STSOLD + 1 WHERE FNO = flight no AND DATE = date; EXEC SQL INSERT INTO FC(FNO, DATE, CNAME, SPECIAL); VALUES (flight no, date, customer name, null); Commit output("reservation completed") endif end. DDB 2008/09 J. Gamper Page 6Example . . . • Transactions are mainly characterized by its Read and Write operations – Read set (RS): The data items that a transaction reads – Write set (WS): The data items that a transaction writes – Base set (BS): the union of the read set and write set • Example (contd.): Read and Write set of the “Reservation” transaction RSReservation = FLIGHT.STSOLD, FLIGHT.CAP WSReservation = FLIGHT.STSOLD, FC.FNO, FC.DATE, FC.CNAME, FC.SPECIAL BSReservation = FLIGHT.STSOLD, FLIGHT.CAP, FC.FNO, FC.DATE, FC.CNAME, FC.SPECIAL DDB 2008/09 J. Gamper Page 7Formalization of a Transaction • We use the following notation: – T be a transaction andx be a relation or a data item of a relation i – O ∈R(x),W(x) be an atomicread/write operation ofT on data itemx ij i S – OS = O be the set of all operations ofT i ij i j – N ∈A,C be the termination operation, i.e.,abort/commit i • Two operationsO (x) andO (x) on the same data item are in conflict if at least one ij ik of them is awrite operation • A transactionT is a partial order over its operations, i.e.,T =Σ ,≺, where i i i i – Σ =OS ∪N i i i – For anyO =R(x)∨W(x) andO =W(x), eitherO ≺ O or ij ik ij i ik O ≺ O ik i ij –∀O ∈OS (O ≺ N ) ij i ij i i • Remarks – The partial order≺ is given and is actually application dependent – It has to specify the execution order between the conflicting operations and between all operations and the termination operation DDB 2008/09 J. Gamper Page 8Formalization of a Transaction . . . • Example: Consider the following transaction T Read(x) Read(y) x ← x + y Write(x) Commit • The transaction is formally represented as Σ =R(x),R(y),W(x),C ≺ =(R(x),W(x)),(R(y),W(x)),(W(x),C),(R(x),C),(R(y),C) DDB 2008/09 J. Gamper Page 9Formalization of a Transaction . . . • Example (contd.): A transaction can also be specified/represented as a directed acyclic graph (DAG), where the vertices are the operations and the edges indicate the ordering. – Assume ≺=(R(x),W(x)),(R(y),W(x)),(W(x),C),(R(x),C),(R(y),C) – The DAG is DDB 2008/09 J. Gamper Page 10Formalization of a Transaction . . . • Example: The reservation transaction is more complex, as it has two possible termination conditions, but a transaction allows only one – BUT, a transaction is the execution of a program which has obviously only one termination – Thus, it can be represented as two transactions, one that aborts and one that commits Transaction T1: Begin transaction Reservation begin input(flight no, date, customer name); Σ=R(STSOLD),R(CAP),A EXEC SQL SELECT STSOLD,CAP INTO temp1,temp2 ≺=(R(STSOLD),A),(R(CAP),A) FROM FLIGHT WHERE FNO = flight no AND DATE = date; if temp1 = temp2 then output("no free seats"); Abort Transaction T2: else EXEC SQL UPDATE FLIGHT Σ=R(STSOLD),R(CAP), SET STSOLD = STSOLD + 1 WHERE FNO = flight no AND DATE = date; EXEC SQL INSERT W(STSOLD),W(FNO),W(DATE), INTO FC(FNO, DATE, CNAME, SPECIAL); VALUES (flight no, date, customer name, null); W(CNAME),W(SPECIAL),C Commit output("reservation completed") ≺=(R(STSOLD),W(STSOLD)),... endif end. DDB 2008/09 J. Gamper Page 11Properties of Transactions • The ACID properties – Atomicity ∗ A transaction is treated as a single/atomic unit of operation and is either executed completely or not at all – Consistency ∗ A transaction preserves DB consistency, i.e., does not violate any integrity constraints – Isolation ∗ A transaction is executed as if it would be the only one. – Durability ∗ The updates of a committed transaction are permanent in the DB DDB 2008/09 J. Gamper Page 12Properties of Transactions . . . • Atomicity – Either all or none of the transaction’s operations are performed – Partial results of an interrupted transactions must be undone – Transaction recovery is the activity of the restoration of atomicity due to input errors, system overloads, and deadlocks – Crash recovery is the activity of ensuring atomicity in the presence of system crashes DDB 2008/09 J. Gamper Page 13Properties of Transactions . . . • Consistency – The consistency of a transaction is simply its correctness and ensures that a transaction transforms a consistent DB into a consistent DB – Transactions are correct programs and do not violate database integrity constraints – Dirty data is data that is updated by a transaction that has not yet committed – Different levels of DB consistency (by Gray et al., 1976) ∗ Degree 0 · TransactionT does not overwrite dirty data of other transactions ∗ Degree 1 · Degree 0 +T does not commit any writes before EOT ∗ Degree 2 · Degree 1 +T does not read dirty data from other transactions ∗ Degree 3 · Degree 2 + Other transactions do not dirty any data read byT beforeT completes DDB 2008/09 J. Gamper Page 14Properties of Transactions . . . • Isolation – Isolation is the property of transactions which requires each transaction to see a consistent DB at all times. – If two concurrent transactions access a data item that is being updated by one of them (i.e., performs a write operation), it is not possible to guarantee that the second will read the correct value – Interconsistency of transactions is obviously achieved if transactions are executed serially – Therefore, if several transactions are executed concurrently, the result must be the same as if they were executed serially in some order (→ serializability) DDB 2008/09 J. Gamper Page 15Properties of Transactions . . . • Example: Consider the following two transactions, where initiallyx = 50: T1: Read(x) T2: Read(x) x ← x+1 x ← x+1 Write(x) Write(x) Commit Commit • Possible execution sequences: T1: Read(x) T1: Read(x) T1: x ← x+1 T1: x ← x+1 T2: Read(x) T1: Write(x) T1: Write(x) T1: Commit T2: x ← x+1 T2: Read(x) T2: Write(x) T2: x ← x+1 T1: Commit T2: Write(x) T2: Commit T2: Commit – Concurrent execution: T reads the 2 – Serial execution: we get the correct re value ofx while it is being changed; the sultx = 52 (the same forT ,T) 2 1 result isx = 51 and is incorrect DDB 2008/09 J. Gamper Page 16Properties of Transactions . . . • SQL92 specifies 3 phenomena/situations that occur if proper isolation is not maintained – Dirty read ∗ T modifiesx which is then read byT beforeT terminates; ifT aborts,T has 1 2 1 1 2 read value which never exists in the DB: – Nonrepeatable (fuzzy) read ∗ T readsx;T then modifies or deletesx and commits;T tries to readx again 1 2 1 but reads a different value or can’t find it – Phantom ∗ T searches the database according to a predicateP whileT inserts new tuples 1 2 that satisfyP DDB 2008/09 J. Gamper Page 17Properties of Transactions . . . • Based on the 3 phenomena, SQL92 specifies different isolation levels: – Read uncommitted ∗ For transactions operating at this level, all three phenomena are possible – Read committed ∗ Fuzzy reads and phantoms are possible, but dirty reads are not – Repeatable read ∗ Only phantoms possible – Anomaly serializable ∗ None of the phenomena are possible DDB 2008/09 J. Gamper Page 18Properties of Transactions . . . • Durability – Once a transaction commits, the system must guarantee that the results of its operations will never be lost, in spite of subsequent failures – Database recovery is used to achieve the task DDB 2008/09 J. Gamper Page 19Classification of Transactions • Classification of transactions according to various criteria – Duration of transaction ∗ Online (shortlife) ∗ Batch (longlife) – Organization of read and write instructions in transaction ∗ General model T :R(x),R(y),W(y),R(z),W(x),W(z),W(w),C 1 ∗ Twostep (all reads before writes) T :R(x),R(y),R(z),W(x),W(z),W(y),W(w),C 2 ∗ Restricted (a data item has to be read before an update) T :R(x),R(y),W(y),R(z),W(x),W(z),R(w),W(w),C 3 ∗ Action model: each (read,write) pair is executed atomically T :R(x),W(x),R(y),W(y),R(z),W(z),R(w),W(w),C 2 DDB 2008/09 J. Gamper Page 20Classification of Transactions . . . • Classification of transactions according to various criteria . . . – Structure of transaction ∗ Flat transaction · Consists of a sequence of primitive operations between a begin and end marker Begin transaction Reservation ... end. ∗ Nested transaction · The operations of a transaction may themselves be transactions. Begin transaction Reservation ... Begin transaction Airline ... end. Begin transaction Hotel ... end. end. ∗ Workflows (next slide) DDB 2008/09 J. Gamper Page 21Classification of Transactions . . . • Workflows: A collection of tasks organized to accomplish a given business process – Workflows generalize transactions and are more expressive to model complex business processes – Types of workflows: ∗ Humanoriented workflows · Involve humans in performing the tasks. · System support for collaboration and coordination; but no systemwide consistency definition ∗ Systemoriented workflows · Computationintensive and specialized tasks that can be executed by a computer · System support for concurrency control and recovery, automatic task execution, notification, etc. ∗ Transactional workflows · In between the previous two; may involve humans, require access to heterogeneous, autonomous and/or distributed systems, and support selective use of ACID properties DDB 2008/09 J. Gamper Page 22Classification of Transactions . . . • Example: We extend the reservation example and show a typical workflow • T1: Customer request • T2: Airline reservation • T3: Hotel reservation • T4: Auto reservation • T5: Bill DDB 2008/09 J. Gamper Page 23Transaction Processing Issues • Transaction structure (usually called transaction model) – Flat (simple), nested • Internal database consistency – Semantic data control (integrity enforcement) algorithms • Reliability protocols – Atomicity and Durability – Local recovery protocols – Global commit protocols • Concurrency control algorithms – How to synchronize concurrent transaction executions (correctness criterion) – Intratransaction consistency, isolation • Replica control protocols – How to control the mutual consistency of replicated data DDB 2008/09 J. Gamper Page 24Conclusion • A transaction is a collection of actions that transforms the system from one consistent state into another consistent state • TransactionT can be viewed as a partial order:T =Σ,≺, whereΣ is the set of all operations, and≺ denotes the order of operations.T can be also represented as a directed acyclic graph (DAG) • Transaction manager aims to achieve four properties of transactions: atomicity, consistency, isolation, and durability • Transactions can be classified according to (i) time, (ii) organization of reads and writes, and (iii) structure • Transaction processing involves reliability, concurrency, and replication protocols to ensure the four properties of the transactions DDB 2008/09 J. Gamper Page 25