The Schedule in the DBMS

Introducing the schedule in the DBMS and some more details about it.

What is Schedule & Why

The schedule is a series of operations from one transaction to the next, it contains several transactions and is a sequence of operations.

Usually, when only one user is doing one transaction to the DBMS, everything works great, but when multiple transactions execute simultaneously, some concurrency problems may occur, thus we need a way to manage those transactions, which is why the schedule is required.

Type of Schedule

There are mainly two types of schedules: Serial schedules and Non-serial schedules.

Type of Schedule

1. Serial-schedule

Transactions in this type of schedule are executed in order, one transaction starts executing only when another transaction is complete.

Transaction Ti    |    Transaction Tj
--------------         --------------
    Read(A)       |         
    Write(A)      | 
    Commit        |       
                  |       Read(B)
                  |       Write(B)    
                  |       Commit          

In this schedule, there are two transactions T1 and T2, and each of them is executed one after another, so this schedule is a Serial Schedule.

2. Non-serial schedule

Unlike the serial schedule, transactions in the non-serial schedule can proceed without waiting for the previous transactions to complete.

Transaction Ti    |    Transaction Tj
--------------         --------------
   Read(A)        |
   Write(B)       |
                  |       Read(B)   
                  |       Read(A)
    Commit        |  
                  |       Commit

In this schedule, two transactions are executed concurrently, and the operations of T1 and T2 are interleaved. Thus this schedule is a Non-Serial Schedule.

The Non-Serial Schedule can be divided further into Serializable and Non-Serializable.

2.1 Serializable schedule

A non-serial schedule that can get the same result as a serial schedule is called a serializable schedule.

Example:

Schedule S1 (Serial Schedule)
-------------------------------------
Transaction Ti    |    Transaction Tj
--------------         --------------
   Read(A)        |
   Write(A)       |
   Commit         |
                  |        Read(B)
                  |        Write(B)      
                  |        Commit

Schedule S2 (Non-Serial Schedule)
-------------------------------------
Transaction Ti    |    Transaction Tj
--------------         --------------
   Read(A)        |
                  |        Read(B)
                  |        Write(B)
   Write(A)       |            
                  |        Commit
    Commit        |

Schedule 1 and 2 will get the same result even though the order of each operation is not the same, schedule 1 is a serial schedule, and we can say schedule 2 is a Serializable Schedule.

And also, the serializable schedule can be divided into two types: Conflict Serializable Schedule and View Serializable Schedule.

2.1.2 View Serializable Schedule

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

As for view equivalent, two schedules are view equivalent if the following three conditions are met:

• In schedule S1, if a transaction T1 reading data “D”, then in schedule S2 also T1 should read data “D” from database
• If Ti is reading “D” which is updated by Tj in S1 then in S2 also Ti should read “D” which is updated by Tj. The example T3 is reading A which is updated by T2 in both schedules:

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

• The transaction Ti that performs the final write(D) operation in schedule S1 and then in schedule S2 also the final write(D) operation must be performed by Ti.

2.2 Non-Serializable Schedule

2.2.1 Recoverable Schedule

In one schedule, if all the transactions which will read certain values are updated or written by other transactions commit after these transactions which update or write that certain values, then this schedule can be called the recoverable schedule.

Example:

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

In this schedule, it contains two transactions: T1 and T2, and T2 will read data A which is written by T1, and T2 commits after T1, then this schedule can be called a recoverable schedule.

Recoverable schedules can be categorized into 3 types:

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

2.2.1.1. Cascading Schedule

If in one schedule, the failure of one transaction will cause several other dependent transactions to roll back or abort, then this schedule will be called cascading schedule.

Example:

T1    |    T2    |    T3    
------  --------   --------
R(A)  |          |
W(A)  |          |  
      |   R(A)   |    
      |   W(A)   |
      |          |   R(A)  
      |          |   W(A)
Failure|         |

In this example schedule, T2 reads data from T1, and T3 reads from T2. If T1 failed, then all the other transactions have to roll back, thus this is a cascading schedule.

But if any of the transactions in the example commit before T1’s failure, then this schedule will not be a cascading schedule.

2.2.1.2 Cascadeless Schedule

In the cascadeless schedule, one transaction can read value only after the transaction which changes that value commit.

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

In this example, T2 will read data A which is updated by T1, and it only read data when T1 commits, the same as T3.

It solved some of the problems caused by the cascade schedule but was also problematic in some aspects which were overcome by the next type of schedule.

2.2.1.3. Strict Schedule

If any of the two transactions Ti and Tj in one schedule meet: Tj can only read/write the updated or written value of Ti after Ti commits or aborts, this schedule is called the Strict schedule.

    T1    |    T2
----------  ---------
    R(A)  |
          |    R(B)
    W(A)  |
   Commit |
          |    W(A)
          |    R(A)
          |   Commit

In this example, Ti writes data A and commits, and after that Tj writes and reads the same data, thus this is a strict schedule. But before T1 commits, T2 still be able to read data B which is not updated by T1.

2.2.2 Non-Recoverable Schedule

If transaction Ti updates or writes the value, Tj reads it and commits it before Ti commits, then this schedule will be called the Non-recoverable schedule. If Ti aborts after Tj commits, then the data that Tj read will be incorrect, but since Tj has already committed the value, thus this is non-recoverable.

    T1    |    T2
----------  --------
    R(A)  |
    W(A)  |
          |    W(A)
          |    R(A)
          |   Commit
   Abort  |

This is the example that I mentioned above. T1 read and write data A first, then T2 writes and reads the same data and commits it, but after that T1 aborts, thus the write operation will be aborted, the data that T2 read will not be correct, but T2 has committed the changes, this schedule is non-recoverable.

Summary

To make all the schedules type more clear, we can see this image:

The outermost schedule is the non-recoverable schedule, and the recoverable schedule is stricter than it. At the same time, the cascadeless schedule has more constrained than the recoverable schedule, and the strict is stricter than cascadeless schedule. In the end, the serial schedule satisfies all constraints.

Conclusion

In this blog, I mainly introduced what is the schedule in DBMS and why it is important, and then discussed different types of schedules with examples.

Thanks for reading!

Level Up Coding

Thanks for being a part of our community! Before you go:

• 👏 Clap for the story and follow the author 👉
• 📰 View more content in the Level Up Coding publication
• 🔔 Follow us: Twitter | LinkedIn | Newsletter

🚀👉 Join the Level Up talent collective and find an amazing job