Schedule in DBMS

 Schedule

( Meaning:- program/event/task:-, a plan for carrying out a process or procedure, giving lists of intended events and times. )

• A series or set of instructions that perform specific operations.
• Maintain the order of the operation according to time in each transaction.

 Example: Schedule involving two transactions T₁ and T₂.

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

In this example, r and w are read and write operations which perform by schedules and A and B are databases.

================================================ 

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.

 

Example: Consider the following schedule involving two transactions T₁ and T₂.

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

here R(A) denotes that a read operation is performed on some data item ‘A’.

This is a serial schedule since the transactions perform serially in the 

order T₁ —> T₂

_{==============================================================================}

 

1.    Non-Serial Schedule:

In non-serial schedules,

• ·         Multiple transactions execute concurrently.
• ·         Transactions are interleaved (mix ).
• ·         Operations of all the transactions are interleaved or mixed with each other.
• ·         It creates a concurrency problem.
• ·         Other transaction proceeds without waiting for the previous transaction to complete.

  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.

 

These are two types A. Serializable and B. Non-Serializable Schedule.

============================================================

 

A. Serializable:

• Transaction to execute concurrently without interfering with one another.
• It identifies which schedules are correct when executions of the transaction have to interleave their operations.

·         A non-serial schedule will be serializable if its result is equal to the result of its transactions executed serially.

·         This is used to maintain the consistency (uniformity/stability) of the database.

·         Since concurrency is allowed in this case thus, multiple transactions can execute concurrently.

• Helps in improving both resource utilization and CPU throughput (flow capacity).  
• A non-serial schedule will be serializable if its result is equal to the result of its transactions executed serially.

• 
  
  
  
  
  

  These are of two types:

  1. Conflict Serializable:

  A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Two operations are said to be conflicting if all conditions satisfy:

  ·                 They belong to different transactions

  ·                They operate on the same data item

  ·                At Least one of them is a written operation

   

  2.  View Serializable:

  A Schedule is called view serializable if it is view equal to a serial schedule (no overlapping transactions). A conflict schedule is a view serializable but if the serializability contains blind writes, then the view serializable does not conflict with serializable.

   ==========================================

  b.     Non-Serializable:

  A non-serial schedule will be serializable if its result is equal to the result of its transactions executed serially.

  
  
  
  
  
  
  
  
  
  

   

  The non-serializable schedule is divided into two types, Recoverable and Non-recoverable Schedules.

   

  Recoverable Schedule:

   Schedules in which transactions commit only after all transactions whose changes they read commit are called recoverable schedules.

   In other words, if some transaction T_j is reading value updated or written by some other transaction T_i, then the commit of T_j must occur after the commit of T_i.

  Example – Consider the following schedule involving two transactions T₁ and T₂.

   

  T1	T2
  R(A)
  W(A)
  	W(A)
  	R(A)
  commit
  	commit

  This is a recoverable schedule since T₁ commits before T₂, which makes the value read by T₂ correct.

  There can be three types of recoverable schedules:

  
  Cascading (flow) Schedule:

• Also called Avoids cascading aborts/rollbacks (ACA).

  When a failure in one transaction leads to the rolling back or aborting of other dependent transactions, then such scheduling is referred to as Cascading rollback or cascading abort.  Example:

  
  
  

  
  
  

   

  Cascade less Schedule:
  Schedules in which transactions read values only after all transactions whose changes they are going to read commit are called cascade-less schedules.

  Avoids that a single transaction abort leads to a series of transaction rollbacks.

  A strategy to prevent cascading aborts is to disallow a transaction from reading uncommitted changes from another transaction in the same schedule.

  In other words, if some transaction T_j wants to read value updated or written by some other transaction T_i, then the commit of T_j must read it after the commit of T_i.

  Example: Consider the following schedule involving two transactions T₁ and T₂.

   

  T1	T2
  R(A)
  W(A)
  	W(A)
  commit
  	R(A)
  	commit

   

  This schedule is cascading. Since the updated value of A is read by T₂ only after the updating transaction i.e. T₁ commits.

   

  Strict Schedule:
  A schedule is strict if for any two transactions T_i, T_j, if a write operation of T_i precedes a conflicting operation of T_j (either read or write), then the commit or abort event of T_i also precedes that conflicting operation of T_j.
  In other words, T_j can read or write updated or written values of T_i only after T_i commits/aborts.

  Example: Consider the following schedule involving two transactions T₁ and T₂.

   

  T1	T2
  R(A)
  	R(A)
  W(A)
  commit
  	W(A)
  	commit

  This is a strict schedule since T₂ reads and writes A which is written by T₁ only after the commitment of T₁.

   

  Non-Recoverable Schedule:
  Example: Consider the following schedule involving two transactions T₁ and T₂.

  T1	T2
  R(A)
  W(A)
  	W(A)
  	R(A)
  	commit
  abort

  T₂ read the value of A written by T₁ and committed. T₁ later aborted, therefore the value read by T₂ is wrong, but since T₂ committed, this schedule is non-recoverable.

  Note – It can be seen that:

  1. Cascade-less schedules are stricter than recoverable schedules or a subset of recoverable schedules.

  2.    Strict schedules are stricter than cascade-less schedules or are a subset of cascade-less schedules.

  3.    Serial schedules satisfy constraints of all recoverable, cascade less, and strict schedules and hence are a subset of strict schedules.

   

  Example: Consider the following schedule:

  S: R1(A), W2(A), Commit2, W1(A), W3(A), Commit3, Commit1

  Which of the following is true?
  (A) The schedule is viewed as a serializable schedule and a strict recoverable schedule
  (B) The schedule is the non-serializable schedule and strict recoverable schedule
  (C) The schedule is a non-serializable schedule and is not a strict recoverable schedule.
  (D) The Schedule is the serializable schedule and is not a strict recoverable schedule

  Solution: The schedule can be re-written as:-

   

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

  First of all, it is a view serializable schedule as it has a view equal serial schedule T₁ —> T₂ —> T₃ which satisfies the initial and updated reads and final write on variable A which is required for view serializability. Now we can see there is a write–write pair done by transactions T₁ followed by T₃ which is violating the above-mentioned condition of strict schedules as T₃ is supposed to do write operation only after T₁ commits which are violated in the given schedule. Hence the given schedule is serializable but not strict recoverable.
  So, option (D) is correct.

   ====================================================