Tag: Schedules and Recoverability in DBMS

Cascading Rollback | Cascadeless Schedule

Recoverability-

 

Before you go through this article, make sure that you have gone through the previous article on Recoverability in DBMS.

 

We have discussed-

  • Non-serial schedules which are not serializable are called as non-serializable schedules.
  • Non-serializable schedules may be recoverable or irrecoverable.

 

Recoverable Schedules-

 

If in a schedule,

  • A transaction performs a dirty read operation from an uncommitted transaction
  • And its commit operation is delayed till the uncommitted transaction either commits or roll backs

then such a schedule is called as a Recoverable Schedule.

 

Types of Recoverable Schedules-

 

A recoverable schedule may be any one of these kinds-

 

 

  1. Cascading Schedule
  2. Cascadeless Schedule
  3. Strict Schedule

 

Cascading Schedule-

 

  • If in a schedule, failure of one transaction causes several other dependent transactions to rollback or abort, then such a schedule is called as a Cascading Schedule or Cascading Rollback or Cascading Abort.
  • It simply leads to the wastage of CPU time.

 

Example-

 

 

Here,

  • Transaction T2 depends on transaction T1.
  • Transaction T3 depends on transaction T2.
  • Transaction T4 depends on transaction T3.

 

In this schedule,

  • The failure of transaction T1 causes the transaction T2 to rollback.
  • The rollback of transaction T2 causes the transaction T3 to rollback.
  • The rollback of transaction T3 causes the transaction T4 to rollback.

Such a rollback is called as a Cascading Rollback.

 

NOTE-

 

If the transactions T2, T3 and T4 would have committed before the failure of transaction T1, then the schedule would have been irrecoverable.

 

Cascadeless Schedule-

 

If in a schedule, a transaction is not allowed to read a data item until the last transaction that has written it is committed or aborted, then such a schedule is called as a Cascadeless Schedule.

In other words,

  • Cascadeless schedule allows only committed read operations.
  • Therefore, it avoids cascading roll back and thus saves CPU time.

 

Example-

 

 

NOTE-

 

  • Cascadeless schedule allows only committed read operations.
  • However, it allows uncommitted write operations.

 

Example-

 

 

Strict Schedule-

 

If in a schedule, a transaction is neither allowed to read nor write a data item until the last transaction that has written it is committed or aborted, then such a schedule is called as a Strict Schedule.

In other words,

  • Strict schedule allows only committed read and write operations.
  • Clearly, strict schedule implements more restrictions than cascadeless schedule.

 

Example-

 

 

Remember-

 

  • Strict schedules are more strict than cascadeless schedules.
  • All strict schedules are cascadeless schedules.
  • All cascadeless schedules are not strict schedules.

 

 

Next Article-Equivalence of Schedules

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Recoverability in DBMS | Recoverable Schedule

Schedules in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Schedules in DBMS.

 

We have discussed-

  • A schedule is the order in which the operations of multiple transactions appear for execution.
  • Non-serial schedules may be serializable or non-serializable.

 

 

In this article, we will discuss about Non-Serializable Schedules.

 

Also read-Serializability in DBMS

 

Non-Serializable Schedules-

 

  • A non-serial schedule which is not serializable is called as a non-serializable schedule.
  • A non-serializable schedule is not guaranteed to produce the the same effect as produced by some serial schedule on any consistent database.

 

Characteristics-

 

Non-serializable schedules-

  • may or may not be consistent
  • may or may not be recoverable

 

Irrecoverable Schedules-

 

If in a schedule,

  • A transaction performs a dirty read operation from an uncommitted transaction
  • And commits before the transaction from which it has read the value

then such a schedule is known as an Irrecoverable Schedule.

 

Example-

 

Consider the following schedule-

 

 

Here,

  • T2 performs a dirty read operation.
  • T2 commits before T1.
  • T1 fails later and roll backs.
  • The value that T2 read now stands to be incorrect.
  • T2 can not recover since it has already committed.

 

Recoverable Schedules-

 

If in a schedule,

  • A transaction performs a dirty read operation from an uncommitted transaction
  • And its commit operation is delayed till the uncommitted transaction either commits or roll backs

then such a schedule is known as a Recoverable Schedule.

 

Here,

  • The commit operation of the transaction that performs the dirty read is delayed.
  • This ensures that it still has a chance to recover if the uncommitted transaction fails later.

 

Example-

 

Consider the following schedule-

 

 

Here,

  • T2 performs a dirty read operation.
  • The commit operation of T2 is delayed till T1 commits or roll backs.
  • T1 commits later.
  • T2 is now allowed to commit.
  • In case, T1 would have failed, T2 has a chance to recover by rolling back.

 

Checking Whether a Schedule is Recoverable or Irrecoverable-

 

Method-01:

 

Check whether the given schedule is conflict serializable or not.

  • If the given schedule is conflict serializable, then it is surely recoverable. Stop and report your answer.
  • If the given schedule is not conflict serializable, then it may or may not be recoverable. Go and check using other methods.

 

Thumb Rules

  • All conflict serializable schedules are recoverable.
  • All recoverable schedules may or may not be conflict serializable.

 

Method-02:

 

Check if there exists any dirty read operation.

(Reading from an uncommitted transaction is called as a dirty read)

  • If there does not exist any dirty read operation, then the schedule is surely recoverable. Stop and report your answer.
  • If there exists any dirty read operation, then the schedule may or may not be recoverable.

 

If there exists a dirty read operation, then follow the following cases-

 

Case-01:

 

If the commit operation of the transaction performing the dirty read occurs before the commit or abort operation of the transaction which updated the value, then the schedule is irrecoverable.

 

Case-02:

 

If the commit operation of the transaction performing the dirty read is delayed till the commit or abort operation of the transaction which updated the value, then the schedule is recoverable.

 

Thumb Rule

No dirty read means a recoverable schedule.

 

Next Article-Cascading Schedule | Cascading Rollback | Cascadeless Schedule

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Schedules in DBMS | Types of Schedules in DBMS

Schedules in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Transactions in DBMS.

 

The order in which the operations of multiple transactions appear for execution is called as a schedule.

 

Types of Schedules-

 

In DBMS, schedules may be classified as-

 

 

In this article, we will discuss about Serial and Non-Serial Schedules.

 

Serial Schedules-

 

In serial schedules,

  • All the transactions execute serially one after the other.
  • When one transaction executes, no other transaction is allowed to execute.

 

Characteristics-

 

Serial schedules are always-

  • Consistent
  • Recoverable
  • Cascadeless
  • Strict

 

Example-01:

 

 

In this schedule,

  • There are two transactions T1 and T2 executing serially one after the other.
  • Transaction T1 executes first.
  • After T1 completes its execution, transaction T2 executes.
  • So, this schedule is an example of a Serial Schedule.

 

Example-02:

 

 

In this schedule,

  • There are two transactions T1 and T2 executing serially one after the other.
  • Transaction T2 executes first.
  • After T2 completes its execution, transaction T1 executes.
  • So, this schedule is an example of a Serial Schedule.

 

Non-Serial Schedules-

 

In non-serial schedules,

  • Multiple transactions execute concurrently.
  • Operations of all the transactions are inter leaved or mixed with each other.

 

Characteristics-

 

Non-serial schedules are NOT always-

  • Consistent
  • Recoverable
  • Cascadeless
  • Strict

 

Example-01:

 

 

In this schedule,

  • There are two transactions T1 and T2 executing concurrently.
  • The operations of T1 and T2 are interleaved.
  • So, this schedule is an example of a Non-Serial Schedule.

 

Example-02:

 

 

In this schedule,

  • There are two transactions T1 and T2 executing concurrently.
  • The operations of T1 and T2 are interleaved.
  • So, this schedule is an example of a Non-Serial Schedule.

 

Finding Number Of Schedules-

 

Consider there are n number of transactions T1, T2, T3 …. , Tn with N1, N2, N3 …. , Nn number of operations respectively.

 

Total Number of Schedules-

 

Total number of possible schedules (serial + non-serial) is given by-

 

 

Total Number of Serial Schedules-

 

Total number of serial schedules

= Number of different ways of arranging n transactions

= n!

 

Total Number of Non-Serial Schedules-

 

Total number of non-serial schedules

= Total number of schedules – Total number of serial schedules

 

PRACTICE PROBLEM BASED ON FINDING NUMBER OF SCHEDULES-

 

Problem-

 

Consider there are three transactions with 2, 3, 4 operations respectively, find-

  1. How many total number of schedules are possible?
  2. How many total number of serial schedules are possible?
  3. How many total number of non-serial schedules are possible?

 

Solution-

 

Total Number of Schedules-

 

Using the above formula, we have-

 

 

Total Number of Serial Schedules-

 

Total number of serial schedules

= Number of different ways of arranging 3 transactions

= 3!

= 6

 

Total Number of Non-Serial Schedules-

 

Total number of non-serial schedules

= Total number of schedules – Total number of serial schedules

= 1260 – 6

= 1254

 

Next Article-Serializability in DBMS

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.