Category Archives: Serializability

What is Lost Update Problem in DBMS?

Posted on by Leave a comment

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)

T1T2
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:

Read more

Serial Schedules, Concurrent Schedules and Conflict Operations

Posted on by One comment

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.

Read more

Precedence Graph to check Conflict Serializable Schedule

Posted on by 2 comments

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.
Read more