Question

6.explain characterizing schedules based on recoverability and serialibality.(50marks)

Need own answer and no internet answers r else i il downvote nd report to chegg.Even a single is wrong i il downvote.its 50marks question so no short answer minimum 10page answer required and own answer r else i il downvote.

Note:Minimum 10page answer and no plagarism r else i il downvote and report to chegg.Minimum 10 to 15page answer required r else dnt attempt.strictly no internet answer n no plagarism.

its 50marks question so i il stricly review nd report

Answer 1

Serializability

Serializability is the preserve database consistency and assuming no transaction fails.

Two types of serializability.

• Conflict serializability
• View serializability

These two are the different forms of Schedule equivalence.

• Conflict serializability

Let us consider a schedule  in which there are two consecutive instructions  _{​​​​​​}I_i and I​​​​​​j of transactions T_{​​​​​​i} and T_j respectively ( i j ). The I_{​​​​​​i} and I_{​​​​​​j} refer to different data items. Then we can swap I_i and I_j without affecting the result of any instruction in the schedule. However if I_i and I_j refer to the same data item Q then the order of the two steps may matter since we are dealing with only read and write instructions.

T1	T2
read (A) write (A)
	read (A) write (A)
read (B) write (B)
	read (B) write (B)

We need to consider 4 cases:

1. I_i = read (Q) I_j = read (Q). The order of I_i and I_j does not matter. since the same value of Q is read by T_{​​​​​​i} and T_j  regardless of the order.

2. I_i = read (Q) I_j = write (Q). If I_i comes before I_j then T_{​​​​​​i} does not read the value of Q. That is written by T_j. Thus the order of I_i and I_j matters.

3. I_i = write (Q) I_j = read (Q). The order of I_i and I_j matters for reasons similar to those of the previous case.

4.I_i = write (Q) I_j = write (Q). Since both instructions are write operations. The order of these instructions does not affect either T_{​​​​​​i} or T_j

I_i and I_j conflict if they are operations by different transactions on the same data item and at least one of these instructions is a write operations.

The write instruction of T₁ conflicts with the read(A) instruction of T₂. The write (A) instruction of T₂ does not conflict with the read (B) instruction of T₁. Because the two instructions access different data items.

The write (A) instruction of T₂ does not conflict with the read (B) instruction of T₁. We can swap these instructions to generate an equivalent schedule.

T1	T2
read (A) write (A)
	read (A)
read (B)
	write (A)
write (B)
	read (B) write (B)

To swap non conflicting instructiond are:

• To swap the read (B) instruction of T₁ with the read (A) instruction of T₂.
• To swap the write (B) instruction of T₁ with the write (A) instruction of T₂.
• To swap the write (B) instruction of T₁ with the read (A) instruction of T_2.

The final result of these swaps is a serial schedule.

If the schedule S can be transformed into a schedule S by a series of swaps of non-conflicting instructions . That is , S and S^{​​​​​​'} are conflict equivalent.

The concept of conflict equivalence leads to the concept of conflict serializability. we say that schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

T1	T2
read (A) write (A) read (B) write (B)
	read (A) write (A) read (B) write (B)

Consider the significant operations of transaction T₃ and T_{4 .} This schedule is not conflict serializable since it is not equivalent to either the serial schedule < T_3,T₄ > or the serial schedule < T_4,T₃ >

T3	T4
read(Q)
	write(Q)
write(Q)

It is possible to have two schedule that produce the same outcome , but they are not conflict equivalent.

• View serializability

Consider two schedules S and S' . Where the same set of transactions participates in both schedules. The schedules S and S' are called view equivalent.

The three conditione are :

1. For each data item Q if transaction T_{​​​​​​i} reads the initial value of Q in schedule S, then transaction T_i must in schedule S' also read the initial value of Q.   
2. For each data item Q if transaction T_{​​​​​​i} execute read (Q) in schedule S and if the value was produced by a write (Q) operation executed by transaction T_j. Then the read (Q) operation of transaction T_{​​​​​​i} must in schedule S' also read the value of Q that was produced by the same write (Q) operation of transaction T_j.   
3. For each data item Q. The transaction that performs the final write (Q) operation in schedule S must perform the final write (Q) operation in schedule S'.   

The conditions 1 and 2 says that each transaction reads the same values in both schedules and therefore performs the same computation. The condition 3 coupled with condition 1 and 2 says that both schedules results in the same final system state.

The concept of view equivalence leads to the concept of view serializability. We says that a schedule S is view serializable. If it is view equivalent to a serial schedule.

Recoverability

The recoverability is the transaction with in the schedule. If transaction fails atomicity requires effect of transaction to be undone.

If a transaction T_{​​​​​​i} fails for whatever reason we need to undo the effect of this transaction to ensure the atomicity property of the transaction. In a system that allows concurrent execution it is necessary also to ensure that any transaction T_j. To dependent on T_i is also aborted.

• Recoverable schedules

Consider T₉ is a transaction that performs only one instruction- read (A). Suppose the system allows T₉ to commit immediately after executing the read (A) instruction. Thus T₉ commits before T₈ does. Now suppose that T₈ fails before it commits. Since T₉ has read the value of data item A written by T₈, we must abort T₉ to ensure transaction atomicity. However T₉ has already committed and connot be aborted. Thus we have a situation where it is impossible to recover correctly from the failure of T₈.

T8	T9
read (A) write (A)
	read (A)
read (B)

The recoverable schedule is one where for each pair of transaction T_{​​​​​​i} and T_j such that T_j reads a data item previously written by T_{​​​​​​i} . The commit operation of T_{​​​​​​i} appears before the commit operation of T_j.

• Cascadeless schedule

A schedule is recoverable, to recover from the failure of a transaction T_{​​​​​​i}. We may have to roll back several transactions. Such situations occur if transactions have read data written by T_i. The transaction T₁₀ writes a value of A. that is read by transaction T₁₁. Transaction T₁₁ writes a value of A is read by transaction T₁₂. Suppose that at this point T₁₀ fails. T₁₀ must be rolled back. Since T₁₁ is dependent on T₁₀. T₁₁ must be rolled back since T₁₂ is dependent on T₁₁. T₁₂ must be rolled back. This phenomenon is a single transaction failure leads to a series of transaction rollbacks is called cascading rollback.

T10	T11	T12
read (A) read (B) write (A)
	read (A) write (A)
		read (A)

The cascading rollback is undesirable. It leads to the undoing of a significant amount of work. It is desirable to restrict the schedules to those where cascasing rollbacks cannot occur. Such schedules are called cascadeless schedules. A cascadeless schedule is one where for each pair of transactions T_{​​​​​​i} and T_j such that T_j reads a data item previously written by T_{​​​​​​i}. The commit operation of T_{​​​​​​i} appears before the read operation of T_j . It is easy to verify that every cascadeless schedule is also recoverable.