Serializability

Ideally, transactions should be serializable. Transactions are said to be serializable if the results of running transactions simultaneously are the same as the results of running them serially, that is, one after the other. It is not important which transaction executes first, only that the result does not reflect any mixing of the transactions.

For example, suppose transaction A multiplies data values by 2 and transaction B adds 1 to data values. Now suppose that there are two data values: 0 and 10. If these transactions are run one after another, the new values will be 1 and 21 if the transaction A is run first or 2 and 22 if the transaction B is run first. But what if the order in which the two transactions are run is different for each value? If transaction A is run first on the first value and transaction B is run first on the second value, the new values will be 1 and 22. If this order is reversed, the new values are 2 and 21. The transactions are serializeable if 1, 21 and 2, 22 are the only possible results. The transactions are not serializable if 1, 22 or 2, 21 is a possible result.

So why is serializability desirable? In other words, why is it important that it appears that one transaction finishes before the next transaction starts? Consider the following problem. A salesman is entering orders at the same time a clerk is sending out bills. Suppose the salesman enters an order from Company X but does not commit it; the salesman is still talking to the representative from Company X. The clerk requests a list of all open orders and discovers the order for Company X and sends them a bill. Now the representative from Company X decides they want to change their order, so the salesman changes it before committing the transaction. Company X gets an incorrect bill.

If the salesman’s and clerk’s transactions were serializable, this problem would never have occurred. Either the salesman’s transaction would have finished before the clerk’s transaction started, in which case the clerk would have sent out the correct bill, or the clerk’s transaction would have finished before the salesman’s transaction started, in which case the clerk would not have sent a bill to Company X at all.