DBMS - Module III - TRANSACTION PROCESSING

Transaction Concepts – ACID Properties–Need for Concurrency Control

Schedules- Serializability: Conflict and View - Concurrency Control - Locking
Mechanisms – Two phase locking- Time Stamp based Concurrency Control –
Deadlock-Recovery Techniques-Immediate update- Deferred update- shadow
paging.

TRANSACTIONS CONCEPTS

Introduction
 A transaction is a unit of program execution that accesses and possibly updates
various data items.
 The transaction consists of all operations executed between the statements begin
and end of the transaction
 Transaction operations: Access to the database is accomplished in a transaction
by the following two operations:
 read (X): Performs the reading operation of data item X from the database
 write (X): Performs the writing operation of data item X to the database
 A transaction must see a consistent database
 During transaction execution the database may be inconsistent
 When the transaction is committed, the database must be consistent
 Two main issues to deal with:
 Failures, e.g. hardware failures and system crashes
 Concurrency, for simultaneous execution of multiple transactions

ACID Properties
 To preserve integrity of data, the database system must ensure:
 Atomicity: Either all operations of the transaction are properly reflected in the
database or none are
 Consistency: Execution of a transaction in isolation preserves the consistency of
the database
 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
 Durability: After a transaction completes successfully, the changes it has made
to the database persist, even if there are system failures
 Example of Fund Transfer: Let Ti be a transaction that transfers 50 from
account A to B. This transaction can be illustrated as follows

1
 DBMS - Module III - TRANSACTION PROCESSING
Transfer $50 from account A to B:
Ti : read(A)
A := A – 50
write(A)
read(B)
B := B + 50
write(B)

 Consistency: the sum of A and B is unchanged by the execution of the transaction.

 Atomicity: if the transaction fails after step 3 and before step 6, the system should
ensure that its updates are not reflected in the database, else an inconsistency will
result.
 Durability: once the user has been notified that the transaction has completed,
the updates to the database by the transaction must persist despite failures.
 Isolation: between steps 3 and 6, no other transaction should access the partially
updated database, or else it will see an inconsistent state (the sum A + B will be
less than it should be).

Transaction and Schedules

 A transaction is seen by the DBMS as a series, or list of actions. We therefore
establish a simple transaction model named as transaction states.

 Transaction State: A transaction must be one of the following states:

 Active, the initial state; the transaction stays in

this state while it is executing
 Partially 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 database restored to its state prior
to the start of the transaction.

Concurrent Execution and Schedules

 Concurrent execution: executing transactions simultaneously has the following
advantages:
 increased processor and disk utilization, leading to better throughput
 one transaction can be using the CPU while another is reading from or
writing to the disk
 reduced average response time for transactions: short transactions need not
wait behind long ones

2
 DBMS - Module III - TRANSACTION PROCESSING
 Concurrency control schemes: these are mechanisms to achieve isolation
 to control the interaction among the concurrent transactions in order to
prevent them from destroying the consistency of the database
 Schedules: sequences that indicate 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
 Example Schedules
 Let T1 transfer $50 from A to B, and T2 transfer 10% of the balance from A to B.
The following is a serial schedule (Schedule 1 in the text), in which T1 is followed
by T2.

 Let T1 and T2 be the transactions defined previously. The following schedule

(Schedule 3 in the text) is not a serial schedule, but it is equivalent to Schedule 1.

 The following concurrent schedule (Schedule 4 in the book) does not preserve the
value of the the sum A + B

3
 DBMS - Module III - TRANSACTION PROCESSING

 Serializable Schedule
 A serializable schedule over a set S of committed transactions is a schedule whose
effect on any consistent database is guaranteed to be identical to that of some
complete serial schedule over S. i.e., even though the actions of transactions are
interleaved, the result of executing transactions serially in different order may
produce different results.
 Example: The schedule shown in the following figure is serializable.

T1 T2
R(A)
W(A)
R(A)
W(A)
R(B)
W(B)
R(B)
W(A)
Commit
Commit

Even though the actions of T1 and T2 are interleaved, the result of this schedule is
equivalent to first running T1 entirely and then running and T2 entirely. Actually
T1‘s read and write of B is not influenced by T2‘s actions on B, and the net effect is
the same if these actions are the serial schedule First T1, then T2. This schedule is
also serializable if first T2, then T1. Therefore if T1 and T2 are submitted
concurrently to a DBMS, either of these two schedules could be chosen as first
 A DBMS might sometimes execute transactions which is not a serial execution i.e.,
not serializable.
 This can be happen for two reasons:
 First the DBMS might use a concurrency control method that ensures the
executed schedule itself.
 Second, SQL gives programmers the authority to instruct the DBMS to
choose non-serializable schedule.
4
 DBMS - Module III - TRANSACTION PROCESSING
 Anomalies due to Interleaved execution
 There are three main situations when the actions of two transactions T1 and T2
conflict with each other in the interleaved execution on the same data object.
 Write-Read (WR) Conflict: Reading Uncommitted data.
 Read-Write (RW) Conflict: Unrepeatable Reads
 Write-Write (WW) Conflict: Overwriting Uncommitted Data.
 Reading Uncommitted Data (WR Conflicts)
 Dirty Read: The first source of anomalies is that a transaction T2 could
read a database object A that has been just modified by another transaction
T1, which has not yet committed, such a read is called a dirty read.
 Example: Consider two transactions T1 and T2, where T1 stands for
transferring $100 from A to B and T2 stands for incrementing both A and B
by 6% of their accounts. Suppose that their actions are interleaved as
follows:
(i) T1 deducts $100 from account A, then immediately
(ii) T2 reads accounts of A and B adds 6% interest to each, and then,
(iii) T1 adds $100 to account B.
This corresponding schedule is illustrated as follows:

T1 T2
R(A)
A: = A -100
W(A)
R(A)
A: = A + 0.06 A
W(A)
R(B)
B:= B+.06 B
W(B)
R(B) Commit
B: = B + 100
W(B)
Commit

The problem here is T2 has added incorrect 6% interest to each A and B. Because
before commitment that $100 is deducted from A, it has added 6% to account A
before commitment that $100 is credited to B, it has added 6% to account B. thus,
the result of this schedule is different from the result of the other schedule which
is serializable: first T1 then T2.

 Unrepeatable Reads (RW Conflicts)

 The second source of anomalies is that a transaction T2 could change the value of
an object A that has been read by a transaction T1 and T1 is still in progress. This
situation causes a problem that, if T1 tries to read the value of A again, it will get a
different result, even though it has not modified A in the meantime. But, this

5
 DBMS - Module III - TRANSACTION PROCESSING
situation could not arise in a serial execute of two transactions: this, it is called as
unrepeatable read.
 Example: Suppose that both T1 and T2 reads the same value of A, say 5. Then T1
has incremented A value to 6 but before commitment as A value 6, T2 has
decremented A value from 5 to 4. Thus, instead of answer of A value as 5, i.e., from
to 5 we got an answer 4 which is incorrect.

 Overwriting Uncommitted Data (WW Conflicts)

 The third source of anomalies is that a transaction T2 could overwrite the value of
an object A, which has already been modified by a transaction T1, while T1 is still
in progress.
 Example: Suppose that A and B are two employees, and their salaries must be
kept equal. Transaction T1 sets their salaries to $1000 and transaction T2 sets
their salaries to $2000.
The following interleaving of the actions T1 and T2 occurs:
i) T1 sets A’s salary to $1000, at the same time, T2 sets B’s salary to $2000.
ii) T1 sets B’s salary is set to to $2000, at the same time, T2 sets A’s salary to
$2000.
As a result A’s salary is set to $2000 and B’s salary is set to $1000, i.e., the result is
not identical
 Blind-Write: Neither transaction reads a value before writing it-such a
write is called a blind-write.
The above example is the best example of blind write because T1 and T2
are concentrating only on writing but not on reading.
 Schedules involving aborted Transactions
 All transactions of aborted transactions are to be undone, and we can therefore
imagine that they were never carried out to begin with.
 Example: Suppose that transaction T1 deducts $100 from account A then immediately
before committing A’s new value the transaction T2 reads the current values of accounts
A and B and adds 6% interest to each, then commits, but incidentally T1 is aborted. So, we
get incorrect result of transaction T2 because T1 was aborted in the middle of the process
and T2 has taken incorrect value of A by T1 and added 6%. We say that such a schedule is
Unrecoverable Schedule. The corresponding schedule is shown as follows:
T1 T2
R(A)
A: = A -100
W(A)
R(A)
A: = A + 0.06 A
W(A)
R(B)
B:= B+.06 B
W(B)
Abort Commit
 Whereas, a recoverable schedule is one in which transactions read only the
6
 DBMS - Module III - TRANSACTION PROCESSING
changes of committed transactions.

Serializability
 Basic Assumption – Each transaction, on its own, preserves database consistency
 i.e. serial execution of transactions preserves database consistency
 A (possibly concurrent) schedule is serializable if it is equivalent to a serial
schedule
 Different forms of schedule equivalence give rise to the notions of conflict
serializability and view serializability
 Simplifying assumptions:
 ignore operations other than read and write instructions
 assume that transactions may perform arbitrary computations on data in
local buffers between reads and writes
 simplified schedules consist only of reads and writes

 Conflict Serializability
 Instructions li and lj of transactions Ti and Tj respectively, conflict if and only if
there exists some item Q accessed by both li and lj, and at least one of these
instructions wrote Q.
1. li = read(Q), lj = read(Q). li and lj don’t conflict.
2. li = read(Q), lj = write(Q). They conflict.
3. li = write(Q), lj = read(Q). They conflict
4. li = write(Q), lj = write(Q). They conflict
 Intuitively, a conflict between li and lj forces a (logical) temporal order between
them
 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 ordering
 If a schedule S can be transformed into a schedule S´ by a series of swaps of non-
conflicting instructions, we say that S and S´ are conflict equivalent.
 We say that a schedule S is conflict serializable if it is conflict equivalent to a
serial schedule
 Example of a schedule that is not conflict serializable:

We are unable to swap instructions in the above

schedule to obtain either the serial schedule < T3, T4 >, or
the serial schedule < T4, T3 >.
 Schedule 3 below can be transformed into Schedule 1, a
7
 DBMS - Module III - TRANSACTION PROCESSING
serial schedule where T2 follows T1, by series of swaps
of non-conflicting instructions.
Therefore Schedule 3 is conflict serializable.

 View Serializability
 Let S and S´ be two schedules with the same set of transactions. S and S´ are view
equivalent if the following three conditions are met, where Q is a data item and Ti
is a transaction:
1. If Ti reads the initial value of Q in schedule S, then Ti must, in schedule
S´, also read the initial value of Q
2. If Ti executes read(Q) in schedule S, and that value was produced by
transaction Tj (if any), then transaction Ti must in schedule S´ also read
the value of Q that was produced by transaction Tj
3. The transaction (if any) that performs the final write(Q) operation in
schedule S (for any data item Q) must perform the final write(Q) operation
in schedule S´
NB: View equivalence is also based purely on reads and writes
 A schedule S is view serializable it is view equivalent to a serial schedule
 Every conflict serializable schedule is also view serializable
 Schedule 9 (from book) — a schedule which is view-serializable but not conflict
serializable

 Every view serializable schedule that is not conflict serializable has blind writes

 Other Notions of Serializability

 This schedule produces the same outcome as the serial schedule < T1, T5 >
 However it is not conflict equivalent or view equivalent to it
 Determining such equivalence requires analysis of operations other than read
and write

8
 DBMS - Module III - TRANSACTION PROCESSING

 Testing for Serializability

 Consider some schedule of a set of transactions T1, T2, ..., Tn
 Precedence graph: a directed graph where the vertices are transaction names
 We draw an arc from Ti to Tj if the two transaction conflict, and Ti accessed the
data item before Tj
 We may label the arc by the item that was accessed
 Example:

 Example Schedule and Precedence Graph

 A schedule is conflict serializable if and only if its precedence graph is acyclic

 ycle-detection algorithms exist which take order n2 time, where n is the number
of vertices in the graph
 If precedence graph is acyclic, the serializability order can be obtained by a
topological sorting of the graph. This is a linear order consistent with the partial
order of the graph. For example, a serializability order for this graph is T2 T1
T3 T4 T5
9
 DBMS - Module III - TRANSACTION PROCESSING
 The precedence graph test for conflict serializability must be modified to apply to
a test for view serializability
 The problem of checking if a schedule is view serializable is NP-complete. Thus
existence of an efficient algorithm is unlikely. However practical algorithms that
just check some sufficient conditions for view serializability can still be used

Example of an acyclic precedence graph

 Concurrency Control vs. Serializability Tests

 Goal – to develop concurrency control protocols that will ensure serializability
 These protocols will impose a discipline that avoids nonseralizable schedules
 A common concurrency control protocol uses locks
 while one transaction is accessing a data item, no other transaction can modify it
 require a transaction to lock the item before accessing it
 two standard lock modes are “shared” (read-only) and “exclusive” (read-write)

Concurrency Control
What is Concurrency?

Concurrency in terms of databases means allowing multiple users to access the data
contained within a database at the same time. If concurrent access is not managed by the
Database Management System (DBMS) so that simultaneous operations don't interfere
with one another problems can occur when various transactions interleave, resulting in an
inconsistent database.

Concurrency is achieved by the DBMS, which interleaves actions (reads/writes of DB

objects) of various transactions. Each transaction must leave the database in a consistent
state if the DB is consistent when the transaction begins. Concurrent execution of user
programs is essential for good DBMS performance. Because disk accesses are frequent, and
relatively slow, it is important to keep the CPU humming by working on several user
programs concurrently. Interleaving actions of different user programs can lead to
inconsistency: e.g., check is cleared while account balance is being computed. DBMS
ensures such problems don’t arise: users can pretend they are using a single-user system.

10
 DBMS - Module III - TRANSACTION PROCESSING
Needs of Concurrency Control

To enforce Isolation (through mutual exclusion) among conflicting transactions.

To preserve database consistency through consistency preserving
execution of transactions.
To resolve read-write and write-write conflicts.
Example: In concurrent execution environment if T1 conflicts with T2 over a
data item A, then the existing concurrency control decides if T1 or T2 should
get the A and if the other transaction is rolled-back or waits.

Timestamp based concurrency control algorithm

Timestamp
A monotonically increasing variable (integer) indicating the age of an operation
or a transaction. A larger timestamp value indicates a more recent event or
operation.
Timestamp based algorithm uses timestamp to serialize the execution of
concurrent transactions.

Basic Timestamp Ordering

1. Transaction T issues a write_item(X) operation:

If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an younger transaction has
already read the data item so abort and roll-back T and reject the operation.
If the condition in part (a) does not exist, then execute write_item(X) of T and set
write_TS(X) to TS(T).

2. Transaction T issues a read_item(X) operation:

If write_TS(X) > TS(T), then an younger transaction has already written to the
data item so abort and roll-back T and reject the operation.
If write_TS(X) TS(T), then execute read_item(X) of T and set read_TS(X) to the
larger of TS(T) and the current read_TS(X).
3. Strict Timestamp Ordering :
Transaction T issues a write_item(X) operation:
If TS(T) > read_TS(X), then delay T until the transaction T’ that wrote or read X has
terminated (committed or aborted).
Transaction T issues a read_item(X) operation:
If TS(T) > write_TS(X), then delay T until the transaction T’ that wrote or read X has
terminated (committed or aborted).

11
 DBMS - Module III - TRANSACTION PROCESSING
Locking Mechanisms
Lock-Based Concurrency Control

 Locking is a concurrent control technique used to ensure serializability.

 A lock disables occurs to data. There are two types of locks. A transaction needs to
acquire a lock before performing a transaction.
 The read lock is known as shared lock and write lock is known as exclusive lock.
 A locking protocol is a set of rules that a transaction follows to attain
serializability

 Strict Two-Phase Locking (Strict 2PL) Protocol

 The Strict 2PL has the following two rules:
 Rule 1: A transaction can read data only when it acquires a shared lock
and can write data only when it acquires an exclusive lock on object.
 Rule 2: A transaction should release the locks when it is completed.
 The entire request for the locks is maintain by DBMS without user intervention. A
transaction is blocked until it gets a requested lock.
 If two transactions operate on two independent database objects then locking
protocol allows such transactions. However if transactions operate on related
data, locking protocol allows only the transaction which acquired lock.
 Example: Consider two transactions, T1 increments the values by 10 and T2
increments then by 20% of the values. If the initial values of database objects A
and B are 10, then after serial execution they would have 24.
T1 T2
R(A)
A: = A + 10 [A = 20]
W(A)
R(A)
A: = A + 0.20 A [A = 24]
W(A)
R(B)
B: = B + 0.20 B [B = 12]
W(B)
Commit
R(B)
B: = B + 10 [B = 14]
W(B)
Commit
Such an interleaving would yield A = 24 and B = 14 as results.
Using Strict 2PL we can avoid such anomalies. When T1 wishes to operate on A, it
has to first acquire the key on A. When T1 acquires the key no other transaction
can interleave.

12
 DBMS - Module III - TRANSACTION PROCESSING

T1 T2
X(A)
R(A)
A: = A +10
W(A)
X(B)
R(B)
B: = B + 10
W(B)
Commit
X(A)
R(A)
A: = A + 0.20 A
W(A)
X(B)
R(B)
B:= B+.20 B
W(B)
Commit
 Using strict 2PL, the transaction first acquire a lock performs the action. However
T2 cannot be interleaved and hence results in correct execution.

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 , the commit operation of Ti appears before the commit operation
of Tj
 The following schedule (Schedule 11) is not recoverable if T9 commits
immediately after the read

13
 DBMS - Module III - TRANSACTION PROCESSING
 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 rollback – a single transaction failure leads to a series of transaction
rollbacks
 Consider the following schedule where none of the transactions has yet
committed (so the schedule is recoverable)
 If T10 fails, T11 and T12 must also be rolled back
 Can lead to the undoing of a significant amount of work

 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
 It is desirable to restrict the schedules to those that are cascadeless

Concurrency control without locking.

 In DBMS the concurrency can be controlled without locking also, by using the
following techniques:
 Optimistic Concurrency Control
 Timestamp-Based Concurrency Control
 Multiversion Concurrency Control

 Time Stamp –Based Concurrency control Time Stamp

 In optimistic concurrency control, a timestamp ordering is imposed on
transactions and validation checks that all conflicting actions occurred in the same
order.

 So, each transaction can be assigned a timestamp at startup, and we can ensure, at
execution time, that if an action ai of transaction Ti conflicts with action aj of
transaction Tj, ai occurs before aj if TS(Ti)< TS(Tj). If an action violates this
ordering, the transaction is aborted and restarted.

14
 DBMS - Module III - TRANSACTION PROCESSING
 The timestamp concurrency control is implemented by giving every database
object O a read timestamp RTS(O) and a write timestamp WTS(O). If transaction T
wants to read object O, and TS(T)<WTS(O), the order of the read with respect to
the most recent write on O would violate the timestamp order between this
transaction and the writer. Therefore, T is aborted and restarted with anew,
larger timestamp, if TS(T)> WTS(O), T reads O, and RTS(O) is set to the larger of
RTS(O) and TS(T).

 Now consider what happens when transaction T wants to write object O:

1. If TS(T)<RTS(O), the write actions conflicts with the most recent read action of
O, and T is therefore aborted and restarted.
2. If TS(T)<WTS(O), a simple approach would be to abort T because it writes
action conflicts with the most recent write of O and is out of timestamp order.
However, we can safely ignore such writes and continue. Ignoring outdated
writes is called the Thomas Write Rule.
3. Otherwise, T writes O and WTS(O) is set to TS(T).

 Thomas’s Write Rule: As roll back restart doesn’t occur in the time stamp
method, Thomas’s write rule ahs been used.
1. When transaction i wants to write the value of some data item ‘D’ which is
already being read by some younger transaction then it is not possible for
transaction i to write its value hence, it must be aborted, rolled back and
restarted with a new time stamp value.
2. When a transaction i wants to write a new value to some data item ‘D’ on
which the write operation has already been applied by some younger
transaction then the write operation requested by the transaction i is
neglected and is allowed to proceed with its normal execution.
3. Whereas in other operations a transaction; is permitted to continue with its
execution and its write time stamp is changed along with the change in
transactional time stamp.

 Thus, by using Thomas’s write rule it would be possible to obtain both

serializable and recoverable schedules.

 The time stamp protocol just presented above, permits schedules that are not
recoverable, as illustrated in the following figure:

15
 DBMS - Module III - TRANSACTION PROCESSING
 If TS(T1) = and TS(T2)=2, this schedule is permitted by the time stamp protocol
(with or without the Thomas write Rule). This timestamp protocol can be
modified to disallow such schedules by buffering all write actions until the
transaction commits.
 In the above example, when T1 wants to write A, WTS(A) is updated to reflect this
action, but the change to A is not carried out immediately; instead, it is recorded in
a private workspace, or buffer. When T2 wants to read A, then its timestamp is
compared with WTS (A), and the read is seen to be permissible. However, T2 is
blocked until T1 completes. If T1 commits, its change to A is copies from the
buffer; otherwise, the changes in the buffer are discarded. T2 is then allowed to read A.

 This blocking of T2 is similar to the effect of T 1 obtaining an exclusive lock on A.

With this modification, the timestamp protocol permits some schedules which are
not permitted by 2PL at all.

 As recoverability is essential, such a modification must be used for the timestamp

protocol.

Deadlocks

 Deadlock is a situation where two or more transactions wait for locks held by
other to be released.
 Example: T1 has lock on A and T2 has lock on B. If T1 requests for lock on B by
holding lock on A. Similarly, T2 requests for lock on B. Either T1 nor T2 can
continue with the execution. This is called deadlock.
 Deadlocks can be handled in three ways.
i) Time-outs
ii) Deadlock prevention
iii) Deadlock detection and recovery

 Timeouts: With this approach, the transaction waits for predefined amount of
time before acquiring the lock. If the time-outs, DBMS assumes that so there
could be a deadlock and aborts the transaction holding the object.
 Deadlock prevention: DBMS looks ahead to determine a deadlock. If a
deadlock is predicted, then it aborts the transaction and never allows a
deadlock to occur.
 Two algorithms are used for the purpose.
i) Wait-Dies
ii) Wound-Wait.
 Deadlock Detection: DBMS waits until a deadlock occurs and then takes
measures to solve the deadlock problem. It constructs a wait- for graph (WFG)
for the purpose.

16
 DBMS - Module III - TRANSACTION PROCESSING
Performance of Locking
 Long-based techniques use two methods to acquire serializabilty.
i) Blocking
ii) Aborting

 Blocking: A transaction is blocked until it gets a lock for operation.

Deadlock is an extreme situation where a transaction blocks forever
waiting for lock. This can be avoided by aborting the transaction.
 Abort: A transaction is forced to stop its execution and to restart.
 Practically, only 1% of transactions suffer from deadlocks and the transaction are
aborted even less than 1%. Hence, there needs a wide consideration only on the
delay introduced by blocking. These blocking delays in turn have an adverse effect
on the throughput.
 Initially the throughput of the system increases with increasing number of
transactions. This is because initially transactions are unlikely to conflict. As the
transactions are increased, the throughput will not increase proportionally
because of certain conflicts. As the transactions increase, there will reach a point
when the system can no more handle the transactions and reduces the system
throughput. This point is called thrashes.

 If the system reaches the thrash point, the DBA takes effective measures to reduce
the number of transactions.
 The following steps are taken to increase throughput:
i) Reducing the situation where two objects request for same lock.
ii) Each transaction should be allowed to hold the lock for a short period of
time such that other transactions are not blocked for a long time.
iii) Avoiding hot spots. A frequently accessed database object is known as hot
spots. This hot spot reduces the system performance drastically.

17
 DBMS - Module III - TRANSACTION PROCESSING

Recovery Techniques
 A computer system, like any other mechanical or electrical device, is subject to failure.
There are many causes of such failure, such as disk crash, power failure, software
error, etc. In each of these cases, information may be lost. Therefore, the database
system maintains an integral part known as recovery manager, which is responsible
for the restorage of the database to a consistent state that existed prior to the
occurrence of the failures.
 The recovery manager of a DBMS is responsible for ensuring transaction atomicity
and durability. It ensures atomicity by undoing the action of transactions, that do not
commit, and durability by making sure that all actions of Data Base Management
Systems 1 committed transactions survive system crashes (example: the central part
of the system is dumped by an error) and media failure (example: a disk is corrupted).
 When a DBMS is restarted after crashes, the recovery manager is given control and
must bring the database to a consistent state. The recovery manager is also
responsible for undoing the actions of aborted transactions. „

System/transaction failures
There are two types of errors that may cause a transaction failure:
1. Logical Error: The transaction can no longer continue with its normal execution
with some internal conditions such as bad input, data not found, overflow or resource
limits exceeded.
2. System Error: The system has entered an undesirable state (example: deadlock),
as a result of which a transaction cannot continue with its normal execution. This
transaction can be re-executed at a later time.
3. System Crash: there is a hardware failure or an error in the database software or
the operating system, the causes the loss of the content of temporary storage and
brings transaction processing to a halt. The content of permanent storage remains
same and is not corrupted.
4. Disk Failure: A disk block loses its content as result of either a head crash or
failure brings a data transfer operating. Copies of the data on other disks, or backups
on tapes, are used to recover from the failure.

 Recovery manager keeps track of the following operations:

 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 limit of transaction execution.
 At this point it may be necessary to check whether the changes introduced by
the transaction can be permanently applied to the database or whether the
transaction has to be aborted because it violates concurrency control or for
some other reason.

18
 DBMS - Module III - TRANSACTION PROCESSING
 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.
 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.
 Recovery techniques use the following operators:
 undo: Similar to rollback except that it applies to a single operation rather
than to a whole transaction.
 redo: This specifies that certain transaction operations must be redone to
ensure that all the operations of a committed transaction have been applied
successfully to the database.
Two Main Techniques
Deferred Update
No physical updates to db until after a transaction commits.
During the commit, log records are made then changes are made
permanent on disk. What if a Transaction fails?
No UNDO required
REDO may be necessary if the changes have not yet been made
permanent before the failure
Immediate Update
Physical updates to db may happen before a transaction commits.
All changes are written to the permanent log (on disk) before changes are
made to the DB. What if a Transaction fails?
After changes are made but before commit – need to UNDO the changes
REDO may be necessary if the changes have not yet been made permanent before
the failure
Recovery based on Deferred Update
Deferred update
Changes are made in memory and after T commits, the changes are made permanent
on disk.
Changes are recorded in buffers and in log file during T’s execution.
At the commit point, the log is force-written to disk and updates are made in database.
No need to ever UNDO operations because changes are never made permanent
REDO is needed if the transaction fails after the commit but before the changes are
made on disk.
Hence the name is NO UNDO/REDO algorithm

2 lists are maintained:

 Commit list: committed transactions since last checkpoint
 Active list: active transactions
REDO all write operations from commit list in order that they were written to the log
Active transactions are cancelled & must be resubmitted.

19
 DBMS - Module III - TRANSACTION PROCESSING
Recovery based on Immediate Update
Immediate update:
Updates to disk can happen at any time
But, updates must still first be recorded in the system logs (on disk) before
changes are made to the database.
Need to provide facilities to UNDO operations which have affected the db
2 flavors of this algorithm
1. UNDO/NO_REDO recovery algorithm
if the recovery technique ensures that all updates are made to the database on
disk before T commits, we do not need to REDO any committed transactions

2. UNDO/REDO recovery algorithm

Transaction is allowed to commit before all its changes are written to the
database o (Note that the log files would be complete at the commit point)

UNDO/REDO Algorithm
2 lists maintained:
Commit list: committed transactions since last checkpoint
Active list: active transactions
UNDO all write operations of active transactions.
Undone in the reverse of the order in which they were written to the log
REDO all write operations of the committed transactions
In the order in which they were written to the log.

Shadow paging
 An alternative to log-based crash-recovery techniques is shadow paging. Shadow
paging may require fewer disk accesses when compared to the log-based recovery
method.
 The database is partitioned into some number of fixed-length blocks, which are
referred as pages. The term page is borrowed from operating systems, since we
are using a paging scheme for memory management.
 Assume that there are n pages, numbered from 1 to n. (n may be in hundreds or
thousands). These pages are not stored in any particular order on disk. But, there
is a way to find the ith page of the database for any given i, by using a page table, as
illustrated in the following figure.

X Y
X' Y'

Database
Data Base Management Systems

X and Y: Shadow copies of data items X`

and Y`: Current copies of data items
20
 DBMS - Module III - TRANSACTION PROCESSING
 The page table has n entries-one for each database page. Each entry contains a pointer
to page on disk. The first entry contains a pointer to the first page of the database, the
second entry may contain a pointer to the second page, and so on.
 The key idea behind the shadow-paging technique is to maintain two page tables
during the life of a transaction: the current page table and the shadow page table, as
illustrated in the following figure:

C urre nt Directory Sh a d o w Directory

(after up d ati n g pa ges 2, 5) (not u p d ate d )
1 1
2 2
3 3
4 4
5 5
6 6

 When a transaction starts, both pages are identical. The shadow page table is never
changed over the duration of the transaction. The current page table may be changed
when a transaction performs a write operation. Thus, all input and output operations
use the current page table to locate the database pages on disk.

 Drawbacks of shadow –paging

1. Commit overhead: the commit of a single transaction using shadow paging requires
multiple blocks to the output-the actual data blocks, the current page table, and the
disk address of the current page table.
2. Data fragmentation: we consider strategies to ensure locality-that is, to keep related
database pages close physically on the disk. Because, locality allows for faster data
transfer. But, shadow paging causes database pages to change location when they are
updated.
3. Garbage collection: Each time that a transaction commits, the database pages
containing the old version of data changed by the transaction become inaccessible.
Such pages are considered garbage, since they are not a part of free space and do not
contain usable information. Garbage may be created also as a side effect of crashed.
Periodically, it is necessary to find all the garbage pages and add them to the list of
free pages. This process is called garbage collection.
 In addition to the drawbacks of shadow paging, even shadow paging is more
difficult than logging to adapt to systems that allow several transactions to
execute concurrently.

21