www.eazynotes.com Sabyasachi De Page No.

T2 is a new transaction which deposits to account C 10% of the amount in account A.

If we prepare a serial schedule, then either T1 will completely finish before T2 can begin, or T2 will
completely finish before T1 can begin. However, if we want to create a concurrent schedule, then
some Context Switching need to be made, so that some portion of T1 will be executed, then some
portion of T2 will be executed and so on. For example say we have prepared the following
concurrent schedule.

T1 T2

Read A;
A = A – 100;
Write A;
Read A;
Temp = A * 0.1;
Read C;
C = C + Temp;
Write C;
Read B;
B = B + 100;
Write B;

No problem here. We have made some Context Switching in this Schedule, the first one after
executing the third instruction of T1, and after executing the last statement of T2. T1 first deducts Rs
100/- from A and writes the new value of Rs 900/- into A. T2 reads the value of A, calculates the
value of Temp to be Rs 90/- and adds the value to C. The remaining part of T1 is executed and Rs
100/- is added to B.

It is clear that a proper Context Switching is very important in order to maintain the Consistency and
Isolation properties of the transactions. But let us take another example where a wrong Context
Switching can bring about disaster. Consider the following example involving the same T1 and T2
www.eazynotes.com Sabyasachi De Page No. 7

T1 T2

Read A;
A = A – 100;
Read A;
Temp = A * 0.1;
Read C;
C = C + Temp;
Write C;
Write A;
Read B;
B = B + 100;
Write B;

This schedule is wrong, because we have made the switching at the second instruction of T1. The
result is very confusing. If we consider accounts A and B both containing Rs 1000/- each, then the
result of this schedule should have left Rs 900/- in A, Rs 1100/- in B and add Rs 90 in C (as C should
be increased by 10% of the amount in A). But in this wrong schedule, the Context Switching is being
performed before the new value of Rs 900/- has been updated in A. T2 reads the old value of A,
which is still Rs 1000/-, and deposits Rs 100/- in C. C makes an unjust gain of Rs 10/- out of
nowhere.

In the above example, we detected the error simple by examining the schedule and applying common
sense. But there must be some well formed rules regarding how to arrange instructions of the
transactions to create error free concurrent schedules. This brings us to our next topic, the concept of
Serializability.

Serializability
When several concurrent transactions are trying to access the same data item, the instructions within
these concurrent transactions must be ordered in some way so as there are no problem in accessing
and releasing the shared data item. There are two aspects of serializability which are described here:
www.eazynotes.com Sabyasachi De Page No. 8

Conflict Serializability
Two instructions of two different transactions may want to access the same data item in order to
perform a read/write operation. Conflict Serializability deals with detecting whether the instructions
are conflicting in any way, and specifying the order in which these two instructions will be executed
in case there is any conflict. A conflict arises if at least one (or both) of the instructions is a write
operation. The following rules are important in Conflict Serializability:
1. If two instructions of the two concurrent transactions are both for read operation, then they
are not in conflict, and can be allowed to take place in any order.
2. If one of the instructions wants to perform a read operation and the other instruction wants to
perform a write operation, then they are in conflict, hence their ordering is important. If the
read instruction is performed first, then it reads the old value of the data item and after the
reading is over, the new value of the data item is written. It the write instruction is performed
first, then updates the data item with the new value and the read instruction reads the newly
updated value.
3. If both the transactions are for write operation, then they are in conflict but can be allowed to
take place in any order, because the transaction do not read the value updated by each other.
However, the value that persists in the data item after the schedule is over is the one written
by the instruction that performed the last write.

It may happen that we may want to execute the same set of transaction in a different schedule on
another day. Keeping in mind these rules, we may sometimes alter parts of one schedule (S1) to
create another schedule (S2) by swapping only the non-conflicting parts of the first schedule. The
conflicting parts cannot be swapped in this way because the ordering of the conflicting instructions is
important and cannot be changed in any other schedule that is derived from the first. If these two
schedules are made of the same set of transactions, then both S1 and S2 would yield the same result
if the conflict resolution rules are maintained while creating the new schedule. In that case the
schedule S1 and S2 would be called Conflict Equivalent.

View Serializability:
This is another type of serializability that can be derived by creating another schedule out of an
existing schedule, involving the same set of transactions. These two schedules would be called View
Serializable if the following rules are followed while creating the second schedule out of the first.
Let us consider that the transactions T1 and T2 are being serialized to create two different schedules
www.eazynotes.com Sabyasachi De Page No. 9

S1 and S2 which we want to be View Equivalent and both T1 and T2 wants to access the same data
item.
1. If in S1, T1 reads the initial value of the data item, then in S2 also, T1 should read the initial
value of that same data item.
2. If in S1, T1 writes a value in the data item which is read by T2, then in S2 also, T1 should
write the value in the data item before T2 reads it.
3. If in S1, T1 performs the final write operation on that data item, then in S2 also, T1 should
perform the final write operation on that data item.

Except in these three cases, any alteration can be possible while creating S2 by modifying S1.

The above notes are submitted by:

Sabyasachi De
MCA
[email protected]
 Recovery System
(Unit-IV- Part B)

Reference
Database System Concepts, 6th Ed.
©Silberschatz, Korth and Sudarshan

Database Management System (PPT) – M V Kamal, Associate Professor

Failure Classification
 Transaction failure :
 Logical errors: transaction cannot complete due to some internal error condition
 System errors: the database system must terminate an active transaction due to an
error condition (e.g., deadlock)
 System crash: a power failure or other hardware or software failure causes the system to
crash.
 Fail-stop assumption: non-volatile storage contents are assumed to not be
corrupted as result of a system crash
 Database systems have numerous integrity checks to prevent corruption of disk
data
 Disk failure: a head crash or similar disk failure destroys all or part of disk storage
 Destruction is assumed to be detectable: disk drives use checksums to detect
failures

Database Management System (PPT) – M V Kamal, Associate Professor

Recovery Algorithms
 Consider transaction Ti that transfers $50 from account A to account B
 Two updates: subtract 50 from A and add 50 to B
 Transaction Ti requires updates to A and B to be output to the database.
 A failure may occur after one of these modifications have been made but before
both of them are made.
 Modifying the database without ensuring that the transaction will commit may
leave the database in an inconsistent state
 Not modifying the database may result in lost updates if failure occurs just after
transaction commits
 Recovery algorithms have two parts
1. Actions taken during normal transaction processing to ensure enough
information exists to recover from failures
2. Actions taken after a failure to recover the database contents to a state that
ensures atomicity, consistency and durability

Database Management System (PPT) – M V Kamal, Associate Professor

Storage Structure
 Volatile storage:
 does not survive system crashes
 examples: main memory, cache memory
 Nonvolatile storage:
 survives system crashes
 examples: disk, tape, flash memory,
non-volatile (battery backed up) RAM
 but may still fail, losing data
 Stable storage:
 a mythical form of storage that survives all failures
 approximated by maintaining multiple copies on distinct nonvolatile media

Database Management System (PPT) – M V Kamal, Associate Professor

Stable-Storage Implementation
 Maintain multiple copies of each block on separate disks
 copies can be at remote sites to protect against disasters such as fire or flooding.
 Failure during data transfer can still result in inconsistent copies.
Block transfer can result in
 Successful completion
 Partial failure: destination block has incorrect information
 Total failure: destination block was never updated
 Protecting storage media from failure during data transfer (one solution):
 Execute output operation as follows (assuming two copies of each block):
1. Write the information onto the first physical block.
2. When the first write successfully completes, write the same information onto the
second physical block.
3. The output is completed only after the second write successfully completes.

Database Management System (PPT) – M V Kamal, Associate Professor

Stable-Storage Implementation (Cont.)
Protecting storage media from failure during data transfer (cont.):
 Copies of a block may differ due to failure during output operation. To recover from failure:
1. First find inconsistent blocks:
1. Expensive solution: Compare the two copies of every disk block.
2. Better solution:
 Record in-progress disk writes on non-volatile storage (Non-volatile RAM or
special area of disk).
 Use this information during recovery to find blocks that may be inconsistent,
and only compare copies of these.
 Used in hardware RAID systems
2. If either copy of an inconsistent block is detected to have an error (bad checksum),
overwrite it by the other copy. If both have no error, but are different, overwrite the
second block by the first block.

Database Management System (PPT) – M V Kamal, Associate Professor