Dbms assignment

1). Time Stamp Protocol

It says a very basic rule that if a transaction Tj that enters after Ti then TimeStamp(Ti) <
TimeStamp(Tj) which means that producing schedule must be equivalent to a serial schedule Ti->Tj.
In Time Stamp Protocol ensures that any conflicting read and write operations are executed in time
stamp order
if not such an operation is rejected and transaction will be rolled back.
The rolled back transaction will be restarted with a new Time Stamp.

T1 T2

Read(A)

Write(A)

Write(A)

Here you could see that conflict is occurring between T2->T1 and it is given that Time Stamp (T1) <
Time Stamp (T2)
which means it the generated conflict must be resolved in T1->T2. But which is not possible so we
rollback transaction T1.

Thomos Write Rule

We allow write-write conflict by ignoring.
T1 T2

Read(A)

Write(A)

Write(A)

Note The conflict occurred says T1->T2 and it is given that Time Stamp (T2) < Time Stamp (T1)
which means it the conflict can’t be resolved but

1|Page
 Dbms assignment

Thomos write rule says that we can ignore the write done by T1 as it has been overwritten by T2
later.

Example 1 
The above two arrows are showing conflict of type Read-Write.
Time Stamp (T1) < Time Stamp (T2), this is already given and conflicts are saying T1 -> T2. So we are
good.

Example
2 

It is given that Time Stamp (T2) < Time Stamp (T3) so according to Time Stamp T2 -> T3 should be
there.
But the conflict says it should be T3 -> T2
And is also not allowed in Thomos write Rule as well.

Advantages
1. Serializability
2. Ensures freedom from dead lock

Disadvantage
Starvation may occur due to continuously getting aborted and restarting the transaction.

2|Page
 Dbms assignment

2). Data recovery

Data loss is something that no one ever wants to go through, but
unfortunately, a lot of us will at some point. Whether it's a lost thumb drive that
we failed to back up or an accidental deletion of an important folder, potential
hazards are everywhere. Prevention is your first step, but in the case that you
do encounter a disaster, this guide will help you through it.

Crash Recovery
DBMS is a highly complex system with hundreds of transactions being executed every
second. The durability and robustness of a DBMS depends on its complex architecture
and its underlying hardware and system software. If it fails or crashes amid
transactions, it is expected that the system would follow some sort of algorithm or
techniques to recover lost data.

Failure Classification
To see where the problem has occurred, we generalize a failure into various
categories, as follows −

Transaction failure

A transaction has to abort when it fails to execute or when it reaches a point from
where it can’t go any further. This is called transaction failure where only a few
transactions or processes are hurt.
Reasons for a transaction failure could be −
 Logical errors − Where a transaction cannot complete because it has some
code error or any internal error condition.
 System errors − Where the database system itself terminates an active
transaction because the DBMS is not able to execute it, or it has to stop
because of some system condition. For example, in case of deadlock or
resource unavailability, the system aborts an active transaction.

System Crash

There are problems − external to the system − that may cause the system to stop
abruptly and cause the system to crash. For example, interruptions in power supply
may cause the failure of underlying hardware or software failure.
Examples may include operating system errors.

Disk Failure

3|Page
 Dbms assignment

In early days of technology evolution, it was a common problem where hard-disk drives
or storage drives used to fail frequently.
Disk failures include formation of bad sectors, unreachability to the disk, disk head
crash or any other failure, which destroys all or a part of disk storage.

Storage Structure
We have already described the storage system. In brief, the storage structure can be
divided into two categories −
 Volatile storage − As the name suggests, a volatile storage cannot survive
system crashes. Volatile storage devices are placed very close to the CPU;
normally they are embedded onto the chipset itself. For example, main memory
and cache memory are examples of volatile storage. They are fast but can store
only a small amount of information.
 Non-volatile storage − These memories are made to survive system crashes.
They are huge in data storage capacity, but slower in accessibility. Examples
may include hard-disks, magnetic tapes, flash memory, and non-volatile (battery
backed up) RAM.

Recovery and Atomicity

When a system crashes, it may have several transactions being executed and various
files opened for them to modify the data items. Transactions are made of various
operations, which are atomic in nature. But according to ACID properties of DBMS,
atomicity of transactions as a whole must be maintained, that is, either all the
operations are executed or none.
When a DBMS recovers from a crash, it should maintain the following −
 It should check the states of all the transactions, which were being executed.
 A transaction may be in the middle of some operation; the DBMS must ensure
the atomicity of the transaction in this case.
 It should check whether the transaction can be completed now or it needs to be
rolled back.
 No transactions would be allowed to leave the DBMS in an inconsistent state.
There are two types of techniques, which can help a DBMS in recovering as well as
maintaining the atomicity of a transaction −
 Maintaining the logs of each transaction, and writing them onto some stable
storage before actually modifying the database.
 Maintaining shadow paging, where the changes are done on a volatile memory,
and later, the actual database is updated.

4|Page
 Dbms assignment

Log-based Recovery
Log is a sequence of records, which maintains the records of actions performed by a
transaction. It is important that the logs are written prior to the actual modification and
stored on a stable storage media, which is failsafe.
Log-based recovery works as follows −
 The log file is kept on a stable storage media.
 When a transaction enters the system and starts execution, it writes a log about
it.
<T , Start>
n

 When the transaction modifies an item X, it write logs as follows −

<T , X, V , V >
n 1 2

It reads T  has changed the value of X, from V  to V .

n 1 2


When the transaction finishes, it logs −
<T , commit>
n

The database can be modified using two approaches −

 Deferred database modification − All logs are written on to the stable storage
and the database is updated when a transaction commits.
 Immediate database modification − Each log follows an actual database
modification. That is, the database is modified immediately after every
operation.

Recovery with Concurrent Transactions

When more than one transaction are being executed in parallel, the logs are
interleaved. At the time of recovery, it would become hard for the recovery system to
backtrack all logs, and then start recovering. To ease this situation, most modern
DBMS use the concept of 'checkpoints'.

Checkpoint

Keeping and maintaining logs in real time and in real environment may fill out all the
memory space available in the system. As time passes, the log file may grow too big to
be handled at all. Checkpoint is a mechanism where all the previous logs are removed
from the system and stored permanently in a storage disk. Checkpoint declares a point
before which the DBMS was in consistent state, and all the transactions were
committed.

Recovery

5|Page
 Dbms assignment

When a system with concurrent transactions crashes and recovers, it behaves in the
following manner −

 The recovery system reads the logs backwards from the end to the last
checkpoint.
 It maintains two lists, an undo-list and a redo-list.
 If the recovery system sees a log with <T , Start> and <T , Commit> or just <T ,
n n n

Commit>, it puts the transaction in the redo-list.

 If the recovery system sees a log with <T , Start> but no commit or abort log
n

found, it puts the transaction in undo-list.

All the transactions in the undo-list are then undone and their logs are removed. All the
transactions in the redo-list and their previous logs are removed and then redone
before saving their logs.

6|Page