Types of Schedules | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Types of Schedules in DBMS

Schedule, as the name suggests, is a process of lining the transactions and executing them one by one. When there are multiple transactions that are running in a concurrent manner and the order of operation is needed to be set so that the operations do not overlap each other, Scheduling is brought into play and the transactions are timed accordingly. The basics of Transactions and Schedules is discussed in Concurrency Control (Introduction), and Transaction Isolation Levels in DBMS articles. Here we will discuss various types of schedules.

1. Serial Schedules
   Schedules in which the transactions are executed non-interleaved, i.e., a serial schedule is one in which no transaction starts until a running transaction has ended are called serial schedules.
   Example: Consider the following schedule involving two transactions T1 and T2.
   where 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 T1 —> T2
2. Non-Serial Schedule
   This is a type of Scheduling where the operations of multiple transactions are interleaved. This might lead to a rise in the concurrency problem. The transactions are executed in a non-serial manner, keeping the end result correct and same as the serial schedule. Unlike the serial schedule where one transaction must wait for another to complete all its operation, in the non-serial schedule, the other transaction proceeds without waiting for the previous transaction to complete. This sort of schedule does not provide any benefit of the concurrent transaction. It can be of two types namely, Serializable and Non-Serializable Schedule.
   The Non-Serial Schedule can be divided further into Serializable and Non-Serializable.
   • Serializable: This is used to maintain the consistency of the database. It is mainly used in the Non-Serial scheduling to verify whether the scheduling will lead to any inconsistency or not. On the other hand, a serial schedule does not need the serializability because it follows a transaction only when the previous transaction is complete. The non-serial schedule is said to be in a serializable schedule only when it is equivalent to the serial schedules, for an n number of transactions. Since concurrency is allowed in this case thus, multiple transactions can execute concurrently. A serializable schedule helps in improving both resource utilization and CPU throughput. These are of two types:
     (i) 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:
     (a) They belong to different transactions
     (b) They operate on the same data item
     (c) At Least one of them is a write operation
     (ii) 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 serializable.
   • Non-Serializable: The non-serializable schedule is divided into two types, Recoverable and Non-recoverable Schedule.
     (i) 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₂.
     This is a recoverable schedule since T₁ commits before T₂, that makes the value read by T₂ correct.
     There can be three types of recoverable schedule:
     (a) Cascading Schedule:
     Also called Avoids cascading aborts/rollbacks (ACA). When there is a failure in one transaction and this leads to the rolling back or aborting other dependent transactions, then such scheduling is referred to as Cascading rollback or cascading abort. Example:
     (b) Cascadeless Schedule: Schedules in which transactions read values only after all transactions whose changes they are going to read commit are called cascadeless 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₂.
     This schedule is cascadeless. Since the updated value of A is read by T₂ only after the updating transaction i.e. T₁ commits.
     Example: Consider the following schedule involving two transactions T₁ and T₂.
     It is a recoverable schedule but it does not avoid cascading aborts. It can be seen that if T₁ aborts, T₂ will have to be aborted too in order to maintain the correctness of the schedule as T₂ has already read the uncommitted value written by T₁.
     (c) 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 value of T_i only after T_i commits/aborts.
     Example: Consider the following schedule involving two transactions T₁ and T₂.
     This is a strict schedule since T₂ reads and writes A which is written by T₁ only after the commit of T₁.
     (ii) Non-Recoverable Schedule:
     Example: Consider the following schedule involving two transactions T1 and T2.T2 read the value of A written by T1, and committed. T1 later aborted, therefore the value read by T2 is wrong, but since T2 committed, this schedule is non-recoverable.

Note: It can be seen that:

1. Cascadeless schedules are stricter than recoverable schedules or are a subset of recoverable schedules.
2. Strict schedules are stricter than cascadeless schedules or are a subset of cascadeless schedules.
3. Serial schedules satisfy constraints of all recoverable, cascadeless and strict schedules and hence is a subset of strict schedules.

The relation between various types of schedules can be depicted as:

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 view serializable schedule and strict recoverable schedule
(b) The schedule is non-serializable schedule and strict recoverable schedule
(c) The schedule is non-serializable schedule and is not strict recoverable schedule.
(d) The Schedule is serializable schedule and is not strict recoverable schedule
Ans: (d)
Solution: The schedule can be re-written as:-

First of all, it is a view serializable schedule as it has 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 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 is violated in the given schedule. Hence the given schedule is serializable but not strict recoverable. So, option (d) is correct.