Transaction Schedule or History
When transactions are executing concurrently in an interleaved fashion, the order of execution of instructions from the various transaction as transaction schedule.
A schedule S of n transactions t1,t2,t3,... tn, is an ordering of the operations of the transaction subject to consistent that, for each transaction t1 that participate in S, the operation of t1 in S must appear in the same order in which they occur in t1.
However, those operations from another transaction tj can be interleaved with the operations.
Schedule classification
The classification of the schedule is given bellow.
Serial Schedule
A schedule s is serial if, for every transaction T participating in the schedule, all the operations of T are executed consecutively in the schedule.
-
suppose there are two users that submit their transactions T1 and T2 at approximately the same time. If no interleaving is permitted, then there are only two possible out comes.
Execute all operations of transaction T1 and then execute all operations of transaction T2.
OR
Execute all operations of transaction T2 and then execute all operations of transaction T1.
-
In a serial schedule only one transaction at a time is active.
-
A commit or abort of the active transaction initiates execution of the next transaction.
-
No interleaving occurs in a serial schedule.
-
Serial Execution is so far the simplest method to execute transactions. No extra work is required to ensure consistency.
Non Serial Schedule
A Schedule is non-serial if, for every transaction T participating in the schedule, the operation of T are executed in an interleaved manner with the operations of there transaction in the schedule.
Example
Let us consider transaction T1 and T2
T1: R(X); w(X);R(y);W(Y); committed.
T2:R(X);W(X); committed.
Serializability of the schedule
The concept of serializability of schedules used to identify which schedule are correct, when transaction execution has interleaving of there operations in the schedule.
A schedule S of n Transactions is serializable. If it is equivalent to some serialization schedule of the same n transactions. then when are the two schedules equivalent?
Result equivalent
Two Schedules are Result Equivalent if they produce the same final state of the database. In the following example Schedules S1 and Schedule s2 are Result Equivalent for x=100 but not in general:
S1 S2
read_item(x) read_item(x);
X=x-10; X=X*1.1;
write_item(X) write_item(X);
Conflict Equivalent
Two schedules are said to be conflict equivalent if the order of two conflicting operations is the same in both schedules. The example is given below; see:
T1 T2 T1 T2
read_item(A); read_item(A);
write_item(A); read_iteam(B);
read_item(B); write_item(A);
write_item(B); read_iteam(A);
read_item(A); write_item(A);
write_item(A); write_item(B);
read_item(B); read_item(B);
write_item(B); write_item(B);
Serial Schedule (S) Non Serial Schedule (S1)