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

Marks: 10M

Year: May 2014

• To process transactions concurrently, the database server must execute some component statements of one transaction, then some from other transactions, before continuing to process further operations from the first.
• The order in which the component operations of the various transactions are interleaved is called the schedule.
• Applying transactions concurrently in this manner can result in many possible outcomes.
• Sometimes, the final state of the database also could have been achieved had the transactions been executed sequentially, meaning that one transaction was always completed in its entirety before the next was started.
• A schedule is called serializable whenever executing the transactions sequentially, in some order, could have left the database in the same state as the actual schedule.
• Serializability is the commonly accepted criterion for correctness.
• A serializable schedule is accepted as correct because the database is not influenced by the concurrent execution of the transactions.

• To check for conflict serializability takes two steps.

  Step 1: Check for the conflicting actions

  Two or more actions are said to be in conflict if:

• The actions belong to different transactions.
• At least one of the actions is a write operation.

• The actions access the same object (read or write).

  The following set of actions is conflicting:

  T1:R(X), T2:W(X), T3:W(X)

  While the following sets of actions are not:

  T1:R(X),T2:R(X),T3:R(X)

  T1:R(X), T2:W(Y), T3:R(X)

  For example, we have a conflict on X (T1 reads it and T2 writes it).

  We also have a conflict on Y (T2 reads it and T3 writes it).

  So it has a conflict property but is it serializable?

  Step 2: Check for a cycle in the Precedence Graph

  First, draw all the Transactions (Tx):

• Check if there is a Tx that reads an item after a different Tx writes it.
• We have T1 that reads X after T2 writes it, so draw arrow from T2 -> T1 Check if there is a Tx that writes an item after a different Tx reads it.
• We have T2 that writes X after T1 reads it, so draw arrow from T1 -> T2

• We also have T3 that writes Y after T2 reads it, so draw arrow from T2 -> T3

  Check if there is a Tx that writes an item after a different TX writes it. So, the final graph is:

We can see that there is a cycle between T1 and T2, so the graph is cyclic, and therefore it is not conflict serializable.