Describe conflict serializability and view serializability with examples.

43kviews

written 8.4 years ago by

teamques10 ★ 68k

modified 2.6 years ago by

pratikshajawale456 • 30

Mumbai University > Computer Engineering > Sem 4 > Database Management System

Marks: 10 M

Year: Dec 2014, May 2014

database management systems

ADD COMMENT EDIT

Conflict Equivalence and Conflict Serializable Schedule

Conflict Equivalence :

Schedules are conflict equivalent if they can be transformed one into other by a sequence of non conflicting interchanges adjacent actions.

Conflict Serializable Schedule :

A Schedule is conflict serializable if it is conflict equivalent to any of serial schedule.

View Equivalent Schedule and View serializable schedule

View Equivalent Schedule :

Consider two schedules S1 and S2, they are said to be view equivalent if following conditions are true :

Initial read must be same. There are two transactions say Ti and Tj, The schedule S1 and S2 are view equivalent if in schedule S1, Ti reads A that has been updated by Tj, and in schedule S2, Ti must read A from Tj. i.e. write-read(WR) sequence must be same between S1 and S2. Final write operations should be same between S1 and S2. View serializable schedule :

A Schedule is view serializable if it is view equivalent to any serial schedule. The following two examples will illustrate how to find view equivalent schedule.

7.3 years ago by teamques10 ★ 68k

1 Answer

1.3kviews

written 8.4 years ago by

teamques10 ★ 68k

A schedule is serializable if it is equivalent to a serial schedule.

Conflict serializability:
- Instructions Ii and Ij, of transactions Ti and Tj respectively, conﬂict if and only if there exists some item P accessed by both Ii and Ij, and atleast one of these instructions wrote P.
- Consider the below operations-
  
  i. Ii = read(P), Ij = read(P). Ii and Ij don’t conﬂict.
  
  ii. Ii = read(P), Ij = write(P). They conﬂict.
  
  iii. Ii = write(P), Ij = read(P). They conﬂict.
  
  iv. Ii = write(P), Ij = write(P). They conﬂict.
A conﬂict between Ii and Ij forces a temporal order between them.
If Ii and Ij are consecutive in a schedule and they do not conﬂict, their results would remain the same even if they had been interchanged in the schedule.
If a schedule Scan be transformed in to a schedule S by a series of swaps of non-conﬂicting instructions, then S and S` are conﬂict equivalent.
In other words a schedule Sis conﬂict serializable if it is conﬂict equivalent to a serial schedule.
Example of a schedule that is not conﬂict serializable:

T3	T4
Read(P)
	Write(P)
Write(P)

The instructions cannot be swapped in the above schedule to obtain either the serial schedule < T 3 , T 4 >, or the serial schedule < T 4 ,T 3 >.
A serial schedule T2 follows T1, by a series of swaps of non-conﬂicting instructions making the below Schedule conﬂict serializable.

enter image description here

View serializability:
- S and S` are view equivalent if the following three conditions are met:
  
  i. For each data item P, if transaction Ti reads the initial value of P in schedule S, then transaction Ti must, in schedule S`, also read the initial value of P.
  
  ii. For each data item P, if transaction Ti executes read (P)in schedule S, and that value was produced by transaction Tj, then transaction Ti must in schedule S` also read the value of P that was produced by transaction Tj.
  
  iii. For each data item P, the transaction that performs the ﬁnal write(P) operation in schedule S must perform the ﬁnal write(P) operation in schedule S`.
- View equivalence is also based purely on reads and writes alone.
- A schedule S is view serializable if it is ie w equivalent to a serial schedule.
- Every conﬂict serializable schedule is also view serializable.
- Every view serializable schedule which is not conﬂict serializable has blind writes.

enter image description here

ADD COMMENT EDIT