The lost update problem

Example: bank accounts A, B and C, whose balances are $100, $200 and $300 respectively. 

Transaction T transfers an amount from account A to B.

• Transaction U transfers an amount from account C to B. 
• The amount transferred is calculated to increase the balance of B by 10%. 
• The net effects on account B of executing the transactions T and U should be to increase the balance of account B by 10% twice, so the final value is $242. 
• If transactions T and U run concurrently as in the following figure, U’s update is lost because T overwrites it without seeing it. 
• Both transactions have read the old value before either writes the new value.
  
  

  Figure 5: The lost update problem
  

Inconsistent retrievals problem

• Example: Transaction V transfers a sum from account A to B and transaction W invokes the branchTotal method to obtain the sum of the balances of all the accounts in the bank. 
• The balances of the two bank accounts, A and B are both initially $200. 
• The result of branchTotal includes the sum of A and B as $300, which is wrong.
• W’s retrievals are inconsistent because V has performed only the withdrawal part of a transfer at the time the sum is calculated.
  
  

  Figure 6: The inconsistent retrievals problem
  

Serial equivalence

• An interleaving of the operations of the transactions in which the combined effect is the same as if the transactions had been performed one at a time in some order is a serially equivalent interleaving. 
• It can be used to solve the lost update problem as shown in the following figure.
• The interleaving operations that affect the shared account B are actually serial.
• Transaction T does all its operations on B before transaction U does. 
• Another interleaving of T and U that has this property is one in which transaction U completes its operations on account B before transaction T starts. 
  

  
  Figure 7: A serially equivalent interleaving of T and U
  
  

It also can be used to solve the inconsistent retrievals problem.

• Based on the example on transaction V is transferring a sum from account A to B and transaction W is obtaining the sum of all the balances.
• The inconsistent retrievals problem occur when a retrieval transaction runs concurrently with an update transaction.
• It cannot occur if the retrieval transaction is performed before or after the update transaction.
• A serially equivalent interleaving of a retrieval transaction and an update transaction 
  
  

  Figure 8: A serially equivalent interleaving of V and W
  
  

Conflicting operations

• A pair of operations conflicts mean that their combined effect depends on the order in which they are executed. 
• Consider a pair of operations: read and write.
  • read: accesses the value of an object
  • write: changes the value of an object
• Conflict rule for read and write are given in the following figure. 
• For two transactions to be serially equivalent, it is necessary and sufficient that all pairs of conflicting operations of the two transactions be executed in the same order at all of the objects they both access. 
• Consider the following example for the transactions T and U:
• T:x = read(i); write(i, 10); write(j, 20);
• U:y = read(j); write(j, 30); z = read(i);
  
  

  Figure 9: Read and write operation conflict rules
  
  
  Figure 10: A non-serially equivalent interleaving of operations of transactions T and U
  
  

From the Figure 10, each transaction’s access to objects i and j is serialized with respect to one another, because T makes all of its accesses to i before U does and U makes all of its accesses to j before T does. 

But the ordering is not serially equivalent, because the pairs of conflicting operations are not done in the same order at both objects. 

Serially equivalent orderings require one of the following two conditions:

• 1. T accesses i before U and T accesses j before U.
• 2. U accesses i before T and U accesses j before T.