Concurrency Control in DBMS: Isolation and 2PL | Part 7

Concurrency control coordinates overlapping transactions. SERIALIZABLE aims for an outcome equivalent to some serial order; weaker isolation levels deliberately allow some anomalies. Locks and multiversion concurrency control are different ways to manage concurrent access.

This is Part 7 of the DBMS exam notes. These are general BTech CSE notes, not one university syllabus. Previous: Part 6: Transactions and ACID. Next: Part 8: Crash Recovery.

1. Why concurrency is a problem

Two users can read and write the same row at the same moment. If their steps mix in a bad order, the data becomes wrong even though each transaction is correct on its own.

2. The four anomalies, with numbers

Anomaly	What happens	Example (x starts at 100)
Lost update	Two transactions read the same value and both write, so one write is lost	T1 and T2 each read 100 and add 10. Final x = 110, but a serial run gives 120
Dirty read	A transaction reads data another transaction has not committed	T1 sets x = 50 but has not committed. T2 reads 50. T1 rolls back, x is 100 again, but T2 used 50
Non-repeatable read	Same row read twice gives two values	T1 reads x = 100. T2 changes x to 120 and commits. T1 reads again and gets 120
Phantom read	Same query returns extra rows the second time	T1 counts salaries above 50000 and gets 2. T2 inserts 90000 and commits. T1 counts again and gets 3

Checked by program: lost update gives 110 (serial 120), dirty read shows 50 against the real 100, the non-repeatable read gives 100 then 120, and the phantom count goes 2 to 3.

3. Schedules and serializability

A schedule is the order in which steps from several transactions run. A serial schedule runs one whole transaction after another. A schedule is serializable if its result equals some serial schedule. The usual exam test is conflict serializability: two steps conflict if they touch the same item, come from different transactions and at least one is a write. Draw an arrow between transactions for each conflict. If the graph has no cycle, the schedule is conflict serializable. For solved graph problems, see conflict serializability practice.

4. Locks and two-phase locking (2PL)

• Shared lock (S): for reading. Many transactions can hold S on the same item.
• Exclusive lock (X): for writing. Only one transaction can hold it, and no S locks at the same time.
• 2PL rule: each transaction has a growing phase (only get locks) and then a shrinking phase (only release locks). Once it releases one lock it cannot get a new one.

2PL guarantees conflict serializability. It does not prevent deadlock: T1 holds a lock on A and waits for B, while T2 holds B and waits for A. A DBMS may detect deadlock and abort a victim, or use prevention/timeout policies. Strict 2PL holds all exclusive locks until commit or abort, preventing other transactions from reading those uncommitted writes. Basic 2PL alone does not guarantee recoverable or cascadeless schedules.

5. SQL isolation levels

Level	Dirty read	Non-repeatable read	Phantom
READ UNCOMMITTED	Possible	Possible	Possible
READ COMMITTED	No	Possible	Possible
REPEATABLE READ	No	No	Possible
SERIALIZABLE	No	No	No

This is the standard SQL table. These are minimum protections in the standard teaching table, not a full engine behavior chart. PostgreSQL READ UNCOMMITTED behaves like READ COMMITTED. Its REPEATABLE READ also stops phantom reads, but serialization anomalies can remain. SERIALIZABLE transactions can fail and require retrying the whole transaction. See the official PostgreSQL isolation documentation below.

6. Common mistakes

• Saying 2PL prevents deadlock. It does not.
• Drawing an arrow for a read-read pair. Two reads never conflict.
• Mixing non-repeatable read (a row changes) and phantom (new rows appear).

7. Practice questions

Q1. x = 200. T1 and T2 both read x, then T1 writes x = x + 50 and T2 writes x = x + 30 (both using the value they read). What is the final x, and what should a serial run give?

Answer: whichever write goes last wins. T1 writes 250 and T2 writes 230, so the final x is 230 or 250. A serial run gives 280. One update is lost.

Q2. Schedule: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B). Is it conflict serializable?

Answer: Yes. The only conflicts are on A (W1(A) before R2(A) and W2(A)), which give one arrow, T1 to T2. B is used only by T1. No cycle, so it equals the serial order T1 then T2.

Q3. Which isolation level is the weakest one that still stops non-repeatable reads?

Answer: REPEATABLE READ.

9. Lost update: follow the interleaving

Step	T1	T2	Stored x
Start			100
1	Read100 into local a		100
2		Read100 into local b	100
3	Write a+10=110		110
4		Write b+10=110	110

The final write uses a stale local value. A serial execution would let the second transaction read110and write120. This is an abstract read-modify-write model, not proof that a particular SQL UPDATE loses changes: row locks, atomic updates and isolation behavior depend on the engine and query.

10. Two different graphs: do not mix the arrows

Precedence graph
Earlier conflicting operation of T1 → later operation of T2
Cycle? The schedule is not conflict serializable.
↓
Wait-for graph
T1 waits for a lock held by T2 → edge T1→T2
Cycle? Deadlock in the ordinary single-instance lock-resource model.

A precedence edge means ordering dependence, not waiting. A wait-for edge means actual blocking. Use the graph named in the question.

11. Solved conflict graphs

S1: R1(A), W1(A), R2(A), W2(A), R1(B), W1(B). On A, R1 precedes W2, and W1 precedes R2 and W2. All give T1→T2. B involves only T1. Graph: T1→T2; no cycle; equivalent conflict order T1 then T2.

S2: R1(A), R2(B), W1(B), W2(A). R1(A) before W2(A) gives T1→T2. R2(B) before W1(B) gives T2→T1. Graph: T1⇄T2; cycle; not conflict serializable. That result alone is not a test for every broader notion of serializability.

This small Python checker examines all earlier/later operation pairs. It does not simulate a DBMS:

def conflict_edges(schedule):
    edges = set()
    for i, (tx, op, item) in enumerate(schedule):
        for other, other_op, other_item in schedule[i + 1:]:
            if tx != other and item == other_item and "W" in (op, other_op):
                edges.add((tx, other))
    return sorted(edges)

def has_cycle(edges):
    graph = {}
    for a, b in edges:
        graph.setdefault(a, set()).add(b)
    visiting, done = set(), set()
    def visit(node):
        if node in visiting:
            return True
        if node in done:
            return False
        visiting.add(node)
        if any(visit(n) for n in graph.get(node, ())):
            return True
        visiting.remove(node)
        done.add(node)
        return False
    return any(visit(n) for n in list(graph))

acyclic = [(1,"R","A"), (1,"W","A"), (2,"R","A"),
           (2,"W","A"), (1,"R","B"), (1,"W","B")]
cyclic = [(1,"R","A"), (2,"R","B"), (1,"W","B"), (2,"W","A")]
for name, schedule in [("S1", acyclic), ("S2", cyclic)]:
    edges = conflict_edges(schedule)
    print(name, edges, "cycle:", has_cycle(edges))

Executed result:

S1 [(1, 2)] cycle: False
S2 [(1, 2), (2, 1)] cycle: True

12. Lock compatibility and 2PL phases

Held / requested	S requested	X requested
S held by another transaction	Compatible	Wait
X held by another transaction	Wait	Wait

Growing phase: acquire S(A), upgrade/acquire X(B); do not release
↓ Lock point: last lock acquired
Shrinking phase: release locks; do not acquire new ones
↓
Strict 2PL: keep X locks until COMMIT/ABORT

Lock upgrades belong in the growing phase. A schedule that releases S(A) then obtains X(B) violates basic2PL. Holding X locks to the end avoids dirty reads of those writes, but can still cause deadlock.

13. Deadlock example and recovery

T1 holds X(A), requests X(B). T2 holds X(B), requests X(A). Each requested lock conflicts with the other's held lock. Wait-for graph T1⇄T2. A detector can choose a victim, roll it back and release its locks so the survivor can proceed. A consistent resource-acquisition order is one prevention strategy. A timeout is a policy, not proof that every wait is a deadlock.

14. MVCC is not "no locks"

Multiversion concurrency control keeps versions so readers can use snapshots instead of waiting on every writer. That does not make all updates lock-free or all snapshot executions serializable. PostgreSQL READ COMMITTED uses a new statement snapshot, while REPEATABLE READ uses a transaction snapshot and can still allow serialization anomalies. SERIALIZABLE checks more dependencies and may abort a transaction for retry.

15. End-topic exam Q&A

1. Dirty versus non-repeatable read? Dirty reads see uncommitted changes; non-repeatable reads see a committed change on rereading the same row.
2. Can a phantom mean fewer rows? Yes. The qualifying set can change by inserts, deletes or updates, not only grow.
3. Do two reads conflict? No. Same item and different transactions are insufficient; at least one operation must write.
4. Is an acyclic precedence graph enough for conflict serializability? Yes, for the modeled read/write schedule. A topological order gives a compatible serial order.
5. Does 2PL prevent deadlock? No. It guarantees conflict serializability under the locking model, not freedom from deadlock.
6. Basic versus strict2PL? Basic separates acquire/release phases. Strict additionally keeps exclusive locks until commit or abort.
7. Is PostgreSQL REPEATABLE READ the standard minimum table exactly? No. It also prevents phantoms, but not every serialization anomaly.
8. What to retry after a serialization failure? The whole transaction with appropriate application handling, not only its last failed statement.

Verification: original numerical anomalies, both possible lost-update orders in Q1, and both conflict graphs checked by Python. This is a teaching simulation, not a live two-session PostgreSQL test. Sources: PostgreSQL transaction isolation and University of Cape Town concurrency-control notes.

8. Five-minute revision

• Anomalies: lost update, dirty read, non-repeatable read, phantom.
• Conflict = same item, different transactions, at least one write.
• No cycle in the precedence graph means conflict serializable.
• 2PL = grow then shrink; strict 2PL holds X locks to commit.

DBMS Exam Notes series: Previous: Part 6: Transactions and ACID | DBMS series and hub | Next: Part 8: Crash Recovery