Category: Serializability

What is Lost Update Problem in DBMS?

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:

Continue reading “What is Lost Update Problem in DBMS?” →
Advertisements

Serial Schedules, Concurrent Schedules and Conflict Operations

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 “Serial Schedules, Concurrent Schedules and Conflict Operations” →

Precedence Graph to check Conflict Serializable Schedule

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 “Precedence Graph to check Conflict Serializable Schedule” →