Ask
Login
0
42kviews
Describe conflict serializability and view serializability with examples.
written 7.8 years ago by gravatar for teamques10 teamques10 ★ 64k modified 23 months ago by gravatar for pratikshajawale456 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
3

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.

6.6 years ago by teamques10 ★ 64k
1 Answer
1
1.2kviews
written 7.8 years ago by gravatar for teamques10 teamques10 ★ 64k

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

  • Conflict serializability:

    • Instructions Ii and Ij, of transactions Ti and Tj respectively, conflict 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 conflict.

      ii. Ii = read(P), Ij = write(P). They conflict.

      iii. Ii = write(P), Ij = read(P). They conflict.

      iv. Ii = write(P), Ij = write(P). They conflict.

  • A conflict between Ii and Ij forces a 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 Scan be transformed in to a schedule S by a series of swaps of non-conflicting instructions, then S and S` are conflict equivalent.
  • In other words a schedule Sis conflict serializable if it is conflict equivalent to a serial schedule.
  • Example of a schedule that is not conflict 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-conflicting instructions making the below Schedule conflict 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 final write(P) operation in schedule S must perform the final 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 conflict serializable schedule is also view serializable.
    • Every view serializable schedule which is not conflict serializable has blind writes.

enter image description here
ADD COMMENT EDIT
Please log in to add an answer.