Serializability

Lost-Update-Problem in Concurrent schedules

Ashutosh Tripathi DBMS, Serializability

In a schedule, if update performed by transaction T1 on data item ‘X’ gets overwritten by the update performed by transaction T2 on same data item ‘X’, then we say that update of T1 is lost to the update of T2.

This problem is known as Lost-Update-Problem in concurrent schedules.

Example:

with X = 50 and Y =50 (initial values)

T1 T2
read(x) (T1I1)
x=x+10 (T1I2)
read(x) (T2I1)
x=x+20 (T2I2)
write(x) (T1I3)
read(y) (T1I4)
write(x) (T2I2)
commit (T2I2)
y=y+10 (T1I5)
write(y) (T1I6)
commit (T1I7)

Explanation: Continue reading →

Serial Schedules, Concurrent Schedules and Conflict Operations

Ashutosh Tripathi DBMS, Serializability , ,

A schedule is the representation of execution sequence for all the instructions of the transactions.

Schedules are categorized in two types:

  • Serial Schedules
  • Concurrent Schedules

Serial Schedules:

A schedule is said to be serial if and only if all the instructions of all the transactions get executed non-preemptively as an unit.

OR

Each serial schedule consists of a sequence of instructions from various transactions, where the instructions belonging to one single transaction appear together in that schedule. Continue reading →

How to check Conflict Serializability using Precedence Graph Algorithm

Ashutosh Tripathi Conflict Serializability, DBMS, Precedence Graph, Serializability , , ,

Precedence graph algorithm can be used to find out whether the given concurrent schedule is conflict serializable or not.

Algorithm:

  1. Create the number of node in the graph equal to the number of transactions in the given schedule.
  2. Starting with each and every transaction identify all the existing conflicting operations and represent them in the graph in the form of edges following the direction of the conflicting operation.
  3. Check if the precedence graph has either a cycle or a loop.
  4. If the cycle or loop does exist, then the given schedule is not conflict serializable.
  5. Else the schedule is conflict serializable.
  6. In case the schedule is conflict serializable then apply the Topological ordering in the graph to find out the equivalent serial schedule.

Continue reading →