sequences leads to the
chronological order in which the instructions of concurrent transactions are
executed schedule for a set of transactions must be consist of all instructions of those transactions must preserve the order in which the
instructions appear in each individual transaction.
Let T1 transfer fund $50 from A to B, and T2 transfer 10% of the balance from A to B. The following is a serial schedule (Schedule 1 in the text), in which T1 is followed by T2.
Let T1 and T2 be the transactions defined previously. The following schedule is not a serial schedule, but it is equivalent to Schedule 1.
We ignore the operation other than read and write instructions, and we also assume that transactions may perform arbitrary computations on data in local buffers in between reads and writes.
Conflict Serializability:-
Instructions li and lj of transactions Ti and Tj respectively, conflict if and only if there exists some item Q accessed by both li and lj, and at least one of these instructions wrote Q.
2. li = read(Q), lj = write(Q). They conflict.
3.
3.
3. li = write(Q), lj = read(Q). They conflict
4.
4.
4. li = write(Q), lj = write(Q). They conflict
Let T1 transfer fund $50 from A to B, and T2 transfer 10% of the balance from A to B. The following is a serial schedule (Schedule 1 in the text), in which T1 is followed by T2.
Let T1 and T2 be the transactions defined previously. The following schedule is not a serial schedule, but it is equivalent to Schedule 1.
We ignore the operation other than read and write instructions, and we also assume that transactions may perform arbitrary computations on data in local buffers in between reads and writes.
Conflict Serializability:-
Instructions li and lj of transactions Ti and Tj respectively, conflict if and only if there exists some item Q accessed by both li and lj, and at least one of these instructions wrote Q.
2. li = read(Q), lj = write(Q). They conflict.
3.
3.
3. li = write(Q), lj = read(Q). They conflict
4.
4.
4. li = write(Q), lj = write(Q). They conflict
Conflict Serializability (Cont.):-
If a schedule S can be transformed into a schedule S´ by a series of swaps of non-conflicting instructions, we say that S and S´ are conflict equivalent.
We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule
Example of a schedule that is not conflict serializable:
read(Q)
write(Q)
write(Q)
We are unable to swap instructions in the above schedule to obtain either the serial schedule We are unable to swap instructions in the above schedule to obtain either the serial schedule
We are unable to swap instructions in the above schedule to obtain either the serial schedule <T3, T4 >, or the serial schedule < T4, T3 >.
Schedule 3 below can be transformed into Schedule 1, a serial schedule where T2 follows T1, by series of swaps of non-conflicting instructions. Therefore Schedule 3 is conflict serializable.
View Serializability.
Let S and S´ be two schedules with the same set of transactions. S and S´ are view equivalent if the following three conditions are met:
A schedule S is view serializable it is view equivalent to a serial schedule.
Every conflict serializable schedule is also view serializable.
Examples:
Basic
Assumption – Each transaction preserves database consistency.Thus
serial execution of a set of transactions preserves database consistency.
A schedule is serializable
if it is equivalent to a serial schedule.
Different forms of schedule equivalence give rise to the notions of:
The
following concurrent schedule (Schedule 4 in the text) does not preserve the
value of the the sum A +
B.
Serializability:-
1. conflict serializability
2. view serializability
1. li = read(Q), lj = read(Q).
li and lj don’t conflict.
T3 T4
1. For each data item Q, if transaction Ti reads the initial value of Q in schedule S, then transaction Ti must, in schedule S´, also read the initial value of Q.
2. For each data item Q if transaction Ti executes read(Q) in schedule S, and that value was produced by
transaction Tj (if any), then transaction Ti must in schedule S´ also read the value of Q that was produced by transaction Tj .
3. For each data item Q, the transaction (if any) that
performs the final write(Q) operation in schedule S must perform the final write(Q) operation in schedule S´.
