2

Wikipedia defines following terms:

  • With a lock-based concurrency control DBMS implementation, serializability isolation level requires read and write locks (acquired on selected data) to be released at the end of the transaction. Also range-locks must be acquired when a SELECT query uses a ranged WHERE clause, especially to avoid the phantom reads phenomenon.
  • In repeatable reads isolation level, a lock-based concurrency control DBMS implementation keeps read and write locks (acquired on selected data) until the end of the transaction. However, range-locks are not managed, so phantom reads can occur.

As long as I interpret it correctly, both serializability and repeatable read isolation levels corresponds to rigorous two phase locking (in which both shared and exclusive mode locks are held till transaction commits/aborts), in which transactions are serializable by their commit order, according to the book by Korth et al..

However, book by Korth et al also says following repeatable read isolation level:

  • Repeatable read allows only committed data to be read and further requires that, between two reads of a data item by a transaction, no other transaction is allowed to update it.
  • However, the transaction may not be serializable with respect to other transactions. For instance, when it is searching for data satisfying some conditions, a transaction may find some of the data inserted by a committed transaction, but may not find other data inserted by the same transaction.

My doubt is, if rigorous 2PL schedules are serializable by commit order of its transaction, then why book by Korth et al says repeatable read isolation level may not ensure serializability?

3
  • Because it allows phantom reads? Phantom reads mean that transaction T2 started after T1 but committed before T1, thus violating serializability.
    – mustaccio
    Mar 13, 2019 at 12:59
  • Definition of phantom reads from the Korth's book: "A transaction re-executes a query returning a set of rows that satisfy a search condition and finds that the set of rows satisfying the condition has changed as a result of another recently committed transaction". So because Repeatable read does not have range locks, phantom reads might occur. But I am unable to see how phantom reads can affect serializability.
    – RajS
    Mar 13, 2019 at 13:38
  • [...continued from last comment] Is it like if the count of selected rows change and if the transaction uses this count to update database, then transactions wont be serializable since concurrent and any serial execution will have different effect on the database?
    – RajS
    Mar 13, 2019 at 13:39

1 Answer 1

3

Serializable means that there is some order the transactions can be run in without overlapping and we'll end up with the same answers and the same state of the database as we get by running the transactions in parallel with serializable isolation level.

Given two transactions, A and B, the only valid states of the system are

  1. All of A followed by all of B, OR
  2. All of B followed by all of A.

That's it. If the system can end up in any other state the transactions are not serializable. If we can show that two transactions running in parallel do not correspond to one or other of these states then those transactions are not serializable.

Think about a table with 4 rows, ID values 2, 4, 6 and 8. There are two transactions A and B. A counts the number of rows. B inserts two rows, ID values 3 and 7.

If they run A->B then A returns 4. If they run B->A then A returns 6. Those are the only possible answers if we are to guarantee serialization.

So A starts under Repeatable Read isolation. It will perform a table scan. A reads row 2 and takes a lock, then reads row 4 and takes a lock.

Now B starts in parallel with A. B tries to insert row 3. Nothing prevents it; A has never read a row with ID 3 to take a lock on it. Then B inserts row 7 and commits, releasing its locks.

Transaction A continues reading. It has just finished with 4 so the next row is 6, then comes 7 (Tx B has committed so its lock on 7 has been released) and finally 8. So A has seen rows 2, 4, 6, 7 & 8 - five rows! This workload is not serializable.

This is the scenario in the second bullet point in the quote from Korth.

The "problem" is the phantom rows produced by B. They overlap the range of data to be read by A. But Repeatable Read does not issue range locks so B is free to do this. Under Serializable isolation B's insertion locks would have prevented A taking range locks or A's range locks would have blocked B's insertions.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.