Unit VIII: Transactions
Dr. Anushree Tripathi
Department of Computer Science
National Institute of Technology Patna
Patna
Overview
• Transaction concept
• Transaction state
• System log
• Commit point
• Desirable Properties of a Transaction
• Concurrent executions
• Serializability
• Recoverability
• Implementation of isolation
• Transaction definition in SQL
• Testing for serializability
Transaction concept
Basic
• Unit of program execution that accesses and updates data items
• All operations between begin transaction and end transaction
Example
• Transaction to transfer $50 from account A to account B:
read(A)
A := A – 50
write(A)
read(B)
B := B + 50
write(B)
Transaction concept
Properties
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
Atomicity Consistency Isolation Durability
• Either all operations • Sum of A and B • Each transaction is • After a transaction
of transaction unchanged by the unaware of other completes
reflected or none execution of the transactions successfully, the
• If transaction fails transaction executing changes it has
after step 3 or step • Requirements concurrently in the made to the
6 leads to • Explicitly specified system database persist,
inconsistent integrity constraints even if there are
database such as primary system failures
keys and foreign
keys
• Implicit integrity
constraints
Transaction concept
Properties
Isolation
T1 T2
1. read(A)
if between steps 3 and 6,
2. A: = A-50 another transaction T2 is
allowed to access the
3. write(A) partially updated database,
read(A),read(B), print(A+B) it will see an inconsistent
database (the sum A + B
4.read(B) will be less than it should
be).
5. B: = B+50
6. Write(B)
Transaction state
States of Active: Initial state, transaction stays while
transaction executing
Partially committed: State after final statement
executed
Failed: State after finding normal execution no
longer proceed
Rollback or Aborted: Indicates transaction has
ended unsuccessfully, changes must be undone
Committed: State after successful completion
Transaction state (contd.)
State diagram of a transaction
Reference: Silberschatz−Korth−Sudarshan, Database System Concepts, Sixth Edition
System log
• To recover from transaction failure by restoring most recent consistent
state
• To keep information about changes to data items
• Strategies for recovery
➢ Reconstructs a more current state by reapplying the operations of
committed transactions from backed up log in case of extensive
damage
➢ Identify any changes that may cause an inconsistency in database.
System log entries determine appropriate actions for recovery
• Contains list of active transactions (checkpoints). Actions of
checkpoints:
➢ Suspend execution of transaction
➢ Force-write all main memory buffers, modified to disk
➢ Write a record to the log
➢ Resume execution transaction
Commit point
• A transaction T reaches its commit point when all its
operations that access the database have been executed
successfully and the effect of all the transaction
operations on the database have been recorded in the log
• Its effect must be permanently recorded
Concurrent executions
• Transaction-processing systems allow multiple
transactions to run concurrently
Reason
Problems
Complications to use Improved
with throughout
consistency of and resource
data utilization
Requires Reduced
extra work waiting time
Concurrent executions
Concurrency control schemes
• To achieve isolation
• To control the interaction among the concurrent
transactions in order to prevent them from destroying the
consistency of the database
Concurrent executions
Schedules
Sequence of instructions to specify chronological
order of execution
Must preserve
order of
instructions
Concurrent executions
Schedule 1
• Let T1 transfer $50 from A to B, and T2 transfer 10% of the balance
from A to B.
• A serial schedule in which T1 is followed by T2:
Concurrent executions
Schedule 2
• A serial schedule where T2 is followed by T1
Concurrent executions
Schedule 3
• Let T1 and T2 be the transactions defined previously. The following
schedule is not a serial schedule, but it is equivalent to Schedule 1.
Concurrent executions
Schedule 4
• The following concurrent schedule does not preserve the
value of (A + B )
Serializability
• Need
➢To preserves database consistency
➢Schedule is serializable if it is equivalent to a serial
schedule
Conflict
serializability
•
Serializability
View serializability
Conflict serializability
Four li = read(Q), lj = read(Q) li and lj No conflict
cases
li = read(Q), lj = write(Q) Conflict
li = write(Q), lj = read(Q) Conflict
li = write(Q), lj = write(Q) Conflict
Conflict serializability (contd.)
S and S´ are conflict equivalent if S can be transformed
into a schedule S´ by a series of swaps of non-conflicting
instructions
S is conflict serializable if it is
conflict equivalent to a serial
schedule
Conflict serializability (contd.)
Schedule 3
Schedule 6
Conflict serializability (contd.)
• No conflict serializability
• No swapping of instructions either the serial schedule
<T3, T4>, or the serial schedule <T4, T3>
Testing for serializability
How to determine
conflict serializability
of a schedule Precedence graph
Directed graph where the vertices are the
transactions
G= (V,E)
Set of edges consists of all edges Ti → Tj
Cycle detection algorithm
Based on depth-first search, require on order of
n2
Schedule is conflict serializable if and only if its
precedence graph is acyclic
Testing for serializability (contd.)
Schedule 1 Schedule 2
Precedence graph for schedule 1 Precedence graph for schedule 2
Reference: Silberschatz−Korth−Sudarshan, Database System Concepts, Sixth Edition
Testing for serializability (contd.)
Topological sorting
• To find serializability order, if precedence graph is acyclic
Reference: Silberschatz−Korth−Sudarshan, Database System Concepts, Sixth Edition
Recoverability
• Need to address the effect of transaction failures on concurrently
running transactions
• Recoverable schedule — if a transaction Tj reads a data item
previously written by a transaction Ti , then the commit operation of Ti
appears before the commit operation of Tj
• Schedule 11 is not recoverable if T9 commits immediately after the read
• If T8 should abort, T9 would have read (and possibly shown to the user)
an inconsistent database state. Hence, database must ensure that
schedules are recoverable
•
Cascading Rollbacks
Basics Single transaction failure leads to a series
of transaction rollbacks
If T10 fails, T11 and T12 must also be rolled
back
Cascadeless Schedules
• Cascadeless schedules — cascading rollbacks cannot
occur; for each pair of transactions Ti and Tj such that Tj
reads a data item previously written by Ti, the commit
operation of Ti appears before the read operation of Tj.
• Every cascadeless schedule is also recoverable
Concurrency Control
mechanism that will ensure
that all possible schedules are
to develop concurrency
either conflict or view
control protocols that will
serializable, and
assure serializability
are recoverable and
preferably cascadeless
Implementation of isolation
Concurrency control mechanisms
Locking
Two-phase locking to ensure
serializability Shared locks
First phase: Transaction acquires Transaction reads
locks
Second phase: Transaction releases
locks Exclusive locks
Transaction writes
Timestamps
Technique assigns each transaction a
timestamp, when it begins
For each data item, system keeps two
timestamps for reading and writing data
Transaction definition in SQL
DML must include a construct
for specifying the set of In SQL, transaction begins
actions that comprise a implicitly
transaction
A transaction in SQL ends by:
In almost all database
Commit work commits
systems, by default, every
current transaction and begins
SQL statement also commits
a new one.
implicitly if it executes
Rollback work causes successfully
current transaction to abort.
