Home » DBMS

Classification of Schedules in DBMS

In this article, we are going to discuss about the schedules, classification of schedules and try to find that whether the schedule is consistent or not?
Submitted by Prerana Jain, on June 19, 2018

Serial schedules will always be consistent in nature but a non-serial schedule may or may not be therefore the idea is to transform a non-serial schedule into a serial schedule by swapping of non-conflicting instructions. We do not have any method to prove a schedule is consistent but from the above discussion understand that Serial schedule will always be consistent so somehow we prove that non serial schedules will also have same effects as of a serial schedule that we get a proof that this particular non-serial schedule will also be consistent. Find those schedules that are logically equal to serial schedules.

Classification of schedules

The schedules can be classified as on the basis of two types,

  1. On the basis of serializability
  2. On the basis of recoverability

Serializability

To Ensure consistency of database we make are that concurrent schedules should be in some sense equivalent to a serial schedule. The concept of schedules is used to identify which solutions are correct when transactions have interleaving of their operations in schedules. A schedule is said to be serializable if either it is conflict serializable, view serializable or both. On the basis of serializability, the schedules can be of two types:

1) Conflict serializable

If a non-serial schedule can be transformed into a serial schedule by swapping of non-conflicting instructions than it is called serializable. If two schedules are conflict equivalent and one of them is serial than other is conflict serializability. The problem of finding whether a schedule is a conflict reliable or not is actually the problem of finding whether the graph contains the cycles or not, therefore, the cost is: o(n2) where n is the number of participating a schedule.

Example:

Let I and J be two consecutive instructions belonging to two different transactions Ti and Tj in a schedules s, the possible I and J instruction can be as:

    I = READ(Q),    J = READ(Q)  → Non conflicting
    I = READ(Q),    J = WRITE(Q) →  Conflicting
    I = WRITE(Q),  J = READ(Q)   →  Conflicting
    I = WRITE(Q),  J = WRITE(Q)  → Conflicting

2) View serializable

A schedules S is viewed serializable if it is view equivalent to a serial schedule.

View equivalent - Consider two schedules S and S' where the same set of transactions participating. Two schedules S and S’ are view equivalent if they satisfy following conditions

  • For any data item of q if the transactions Tj read initial values of q in schedules s then the transactions Tj must in schedules S’ also read the initial value of q.
  • If a transactions Ti in schedules S reads any data item q which is updated by transaction Tj then a transactions Ti must in schedules S' also read data item q updated by transactions Tj in schedules S'.

Recoverability

On the basis of recoverability the schedules are of three types:

1) Recoverable schedules

A schedule is recoverable if in case of failure dependent schedules have a chance of roll back.

Example:

T1		T2		T3
R(x)
W(x)
C		R(x)
		W(x)
		C		R(x)
				C

This schedule is recoverable but if a failure occurs just before transition T1 commit T1 will rollback and based on which T2 and T3 will also rollback.

2) Non recoverable schedules

The non recoverable schedules is one in which for each pair of transaction Ti and Tj such that if Ti read a data item previously written by ti then commit or abort operations of Ti appears before Tj.

Cascading Rollback

It is the phenomenon in which a single transactions failure leads to a series of transaction rollbacks is called cascading rollback. Even if the schedules are recoverable the commit of transactions may lead to a lot of transactions to rollback. Cascading rollback is undesirable since it leads to undoing of a significant amount of work. Uncommitted reads are not allowed in cascadeless schedules.

Cascadeless schedules

To avoiding cascading rollback cascadeless schedules are used. A transaction in which each pair of transactions Ti and Tj such that if Tj reads a data item previously written by Ti then the commit or abort of Ti must appear before operations of Tj such a schedule is called cascadeless schedules.






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.