What is serializable schedule

What is serializable schedule? When do we say that the schedule is serializable? When can we say that a concurrent schedule is serializable? Define serializable schedule

Serializable schedules

When we execute database transactions serially, that is, one after the other it will consume a lot of time. Instead, we can permit the transactions to execute simultaneously. 

What is the problem if we do so?

Let us assume ticket booking for flights from a booking office. Also assume that the booking office have only two counters and tickets can be booked from that office only. Consider the following two cases;

• people can purchase from both counters for different flights or different flight schedules.

• people are trying to book the ticket for same flight at both counters.

In the first case, there is no problem as they are trying to book for different flights. The second case may see the same database state. For example, 5 tickets are available, both counters try to book each one ticket. The balance ticket should be 3. But due to simultaneous execution, we may see 4 tickets which is wrong. Hence, we cannot permit the transactions simultaneously.

When/How can we permit those transactions simultaneously?

In such cases we can permit the transactions that are trying to access the same data items in serial order. Or we can permit the transactions as they are if they produce the same result as a serial execution. This is called as serializable.

Definition

If we permit a set of transactions to execute simultaneously as a concurrent schedule, if the schedule is able to produce the same result as some serial execution of this schedule, then we call the schedule as serializable schedule.

Transaction T1	Transaction T2
read(A); A := A – 50; write(A); read(B); B := B + 50; write(B);	read(A); temp := A * 0.1; A := A – temp; write(A); read(B); B := B + temp; write(B);

Schedule 1

Consider the concurrent (parallel) schedule given above. Let us suppose A = 1000 and B = 1000 at the start of the schedule 1. The values of A and B at the end of the execution of schedule 1 are 855 and 1145. Schedules 2 and 3 are serial schedules. All instructions of T1 finish before T2 in schedule 2. All instructions of T2 finish before T1 in schedule 3.

Transaction T1	Transaction T2
read(A); A := A – 50; write(A); read(B); B := B + 50; write(B);	read(A); temp := A * 0.1; A := A – temp; write(A); read(B); B := B + temp; write(B);

Schedule 2

Transaction T1	Transaction T2
read(A); A := A – 50; write(A); read(B); B := B + 50; write(B);	read(A); temp := A * 0.1; A := A – temp; write(A); read(B); B := B + temp; write(B);

Schedule 3

At the end of schedule 2 the values of A and B are 855 and 1145. At the end of schedule 3 the values of A and B are 850 and 1150. Among these two results, the result produced by schedule 2 is same as the concurrent schedule 1. As schedule 1 is equivalent to the serial schedule T1 followed by T2, the schedule 1 is said to be serializable schedule.

**************

Go to Transaction Management page