Mumbai University > Information Technology > Sem 3 > Database Management System

Marks: 10 M

Year: Dec 2014

1. Introduction:

i. A schedule is called as a serial schedule when the operations of each transaction are executed consecutively, without any interleaved operations from the other transaction.

ii. Formally, 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; otherwise, the schedule is called nonserial.

2. Explanation:

i. Suppose, two railway reservation agents perform two transactions T1 and T2 at approximately same time.

ii. If no interleaving of operations is permitted, there are only two possible outcomes:

• Execute all the operations of transaction T1 (in sequence) followed by all the operations of transaction T2 (in sequence).
• Execute all the operations of transaction T2 (in sequence) followed by all the operations of transaction T1 (in sequence).

They can be diagrammatically represented as:

Table 1: Serial Schedule A T1 followed by T2

Table 2: Serial Schedule B T2 followed by T1

iii. The concept of serializability of schedules is used to identify which schedules are correct when transaction executions have interleaving of their operations in the schedules.

iv. Thus, a schedule S of n transactions is serializable if it is equivalent to some serial schedule of the same n transactions.

v. There are n! possible serial schedules of n transactions and many more possible nonserial schedules.

3. Types of Serializability

I. Conflict Serializability

• Consider a schedule S which contains transactions Ti and Tj with instructions Ii and Ij respectively.
• If Ii and Ij refer to different data items, then Ii and Ij can be swapped without affecting the results of any instruction in the schedule. However, if Ii and Ij refer to the same data item Q, then the order of the two steps may matter.
• The four possible cases are as follows:
  • Ii = read(Q), Ij = read(Q). The order of Ii and Ij does not matter, since the same value of Q is read by Ti and Tj , regardless of the order.
  • Ii = read(Q), Ij = write(Q). If Ii comes before Ij, then Ti does not read the value of Q that is written by Tj in instruction Ij. If Ij comes before Ii, then Ti reads the value of Q that is written by Tj. Thus, the order of Ii and Ij matters.
  • Ii = write(Q), Ij = read(Q). The order of Ii and Ij matters for reasons similar to those of the previous case.
  • Ii = write(Q), Ij = write(Q). Since both instructions are write operations, the order of these instructions does not affect either Ti or Tj . However, the value obtained by the next read(Q) instruction of S is affected, since the result of only the latter of the two write instructions is preserved in the database.
• Intuitively, a conflict between Ii and Ij forces a (logical) temporal order between them. If Ii and Ij are consecutive in a schedule and they do not conflict, their results would remain the same even if they had been interchanged in the schedule.
• 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.
• Schedule S is conflict serializable if it is conflict equivalent to a serial schedule.
• Consider a schedule showing read and write transactions shown below :

The write (A) instruction of T1 conflicts with the read(A) instruction of T2. However, the write (A) instruction of T2 does not conflict with the read(B) instruction of T1, because the two instructions access different data items.

• Since the write(A) instruction of T2 in does not conflict with the read(B) instruction of T1, we can swap these instructions to generate an equivalent schedule shown below:

• Continuing with the swapping of nonconflicting instructions results in the generation of a schedule shown below:

Thus, a serial schedule is generated. If a schedule S can be transformed into a schedule S’ by a series of swaps of nonconflicting instructions, we say that S and S’ are conflict equivalent. A schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

II. View Serializability

• Two schedules S and S’ are said to be view equivalent if following three conditions are met:
  • 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.
  • For each data item Q, if transaction Ti executes read(Q) in schedule S, and if that value was produced by a write(Q) operation executed by transaction Tj , then the read(Q) operation of transaction Ti must, in schedule S’, also read the value of Q that was produced by the same write(Q) operation of transaction Tj .
  • 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’.
• Conditions 1 and 2 ensure that each transaction reads the same values in both schedules and, therefore, performs the same computation. Condition 3, coupled with conditions 1 and 2, ensures that both schedules result in the same final system state.
• The concept of view equivalence leads to the concept of view serializability. A schedule S is view serializable if it is view equivalent to a serial schedule.
• Consider the following schedule:

• On appending transaction T3 to the above schedule, it results in the creation of a view serializable schedule as shown below:

Thus, the above mentioned schedule is view equivalent to a serial schedule <t1, t2,="" t3="">, since the one read(Q) instruction reads the initial value of Q in both schedules, and T3 performs the final write of Q in both schedules.