TESTING FOR SERALIZABILITY Database Management System

TESTING FOR SERALIZABILITY Database Management System

TESTING FOR SERALIZABILITY Database Management System

TESTING FOR SERALIZABILITY

  • Consider Some schedule of a set of transactions T1, T2,…, Tn.
  • Precedence graph – a directed graph where the vertices are the transactions (names).
  • We draw an arc from Tito Tjif the two transactions conflict, and Ti accessed the data item on which the conflict arose earlier.
  • We may label the arc by the item that was accessed.

Example: Schedule A

TESTING FOR SERALIZABILITY Database Management System

 

Test for Conflict Serializability

  • A schedule is conflict serializable if and only if its precedence graph is acyclic.
  • Cycle-detection algorithms exist which take order n + e where, e is the number of edges, n is the number of vertices in the graph.

 

Which algorithm would you use?

  • If precedence graph is acyclic, the serializability order can be obtained by a topological sorting of the graph.

 

Test for view serializability

The precedence graph test for conflict serializability cannot beused directly to test for view serializability.

Extension to test for view serializability has cost exponential in the size of the precedence graph. The problem of checking if a schedule is view serializable fallsin the class of NP-complete problems. Thus existence of an efficient algorithm is extremely unlikely.

However practical algorithms that just check some sufficient conditions for view serializability can still be used.

Recoverable Schedule

Recoverable schedule— if a transaction Tj reads a data item previously written by a transaction Tj, then the commit operation of Tj appears before the Commit operation of Tj.

The following schedule (Schedule 11) is not recoverable if T9 Commits immediately after the read

TESTING FOR SERALIZABILITY Database Management System

 

If T8 should abort, T9 would have read (and possibly shown to the user) an inconsistent database state. Hence, database must ensure that Schedules are recoverable.

Cascading rollback-a single transaction failure leads to a series of transaction rollbacks. Consider the following schedule where none of the transactions has yet committed (so the schedule is recoverable)

TESTING FOR SERALIZABILITY Database Management System

lf T10 fails, T11 and T12 must also be rolled back.

Can lead to the undoing of a significant amount of work

Cascadeless schedules—cascading rollbacks cannot occur; for each pair of transactions Ti and Tj Such that Tj reads a data item previously written by Ti, the commit operation of Tiappears before the read operation of Tj.

 

  • Every cascadeless schedule is also recoverable.
  • It is desirable to restrict the Schedules to those that are CascadeleSS.