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.
**************