Lesson 27: Concurrent Execution and Serialisability¶
Interference problems, schedules, precedence graphs and locking
About this lesson
Course: Database Management Systems
Unit 6: Data Storage and Indexes · 4 Lecture Hours
Lesson duration: 1 lecture
Reading: Elmasri & Navathe, Ch. 20.5, 21
Learning Outcomes
- Explain why transactions are interleaved rather than run one at a time.
- Identify the four concurrency problems: lost update, dirty read, unrepeatable read, phantom.
- Define schedule, serial schedule and conflict serialisability.
- Test a schedule with a precedence graph.
- Explain two-phase locking, deadlock and the SQL isolation levels.
27.1 Why Interleave at All?¶
Running transactions strictly one after another would make all the concurrency problems disappear — and make the system unusable.
Two reasons for interleaving
1. Throughput and processor utilisation. A transaction spends most of its life waiting for disk (Lesson 1: 10 ms per block access, against nanoseconds of CPU work). While one transaction waits, the processor can execute another. Serial execution would leave the CPU idle almost all the time.
2. Response time and fairness. Without interleaving, a short transaction arriving behind a long one must wait for it to finish entirely. A five-millisecond seat enquiry would queue behind a five-minute report.
The cost of interleaving is interference, and the whole of this lesson is about controlling it.
27.2 The Four Concurrency Problems¶
Throughout, T1 and T2 run concurrently on data items X and Y.
Problem 1 — Lost update (write–write)¶
Two transactions read the same item, both compute from the old value, and one overwrites the other.
Initially X = 100 (seats available)
TIME T1 T2 X
---- ------------------- ------------------ ---
t1 read(X) -> 100 100
t2 read(X) -> 100 100
t3 X := X - 10 100
t4 X := X - 20 100
t5 write(X) = 90 90
t6 write(X) = 80 80 <-- T1's update LOST
Correct answer: 100 - 10 - 20 = 70. Actual: 80.
T1's subtraction has vanished because T2 read BEFORE T1 wrote.
This is the two-clerks-and-the-last-seat problem of Unit 1, Lesson 1.
Problem 2 — Dirty read (uncommitted dependency, write–read)¶
One transaction reads a value written by another that later aborts.
Initially X = 100
TIME T1 T2 X
---- ------------------- ------------------ ---
t1 read(X) -> 100 100
t2 X := X - 10 100
t3 write(X) = 90 90
t4 read(X) -> 90 90 <-- reads DIRTY data
t5 (uses 90) 90
t6 **ROLLBACK** 100 <-- T1 undone
t7 commit 100
T2 committed a decision based on a value that NEVER OFFICIALLY EXISTED.
If T2 has already committed, the damage cannot be undone by rolling T2 back either — this is why aborting T1 may force cascading rollback of every transaction that read its uncommitted data.
Problem 3 — Unrepeatable read (read–write)¶
One transaction reads the same item twice and gets different values, because another transaction modified it in between.
TIME T1 T2 X
---- ------------------------- ------------------- ---
t1 read(X) -> 100 100
t2 read(X) -> 100 100
t3 X := X - 50 100
t4 write(X) = 50 50
t5 commit 50
t6 read(X) -> 50 50 <-- DIFFERENT!
T1 read X twice within one transaction and got two answers.
Any calculation comparing the two is meaningless.
Problem 4 — Phantom read¶
T1 runs a query twice; the second time, new rows satisfying the condition have appeared.
TIME T1 T2
---- ------------------------------------- ---------------------------
t1 SELECT COUNT(*) FROM ADMISSION
WHERE SID='CS01'; -> 40
t2 INSERT INTO ADMISSION
VALUES ('X9999','CS01',...);
t3 commit
t4 SELECT COUNT(*) FROM ADMISSION
WHERE SID='CS01'; -> 41 <-- a PHANTOM row appeared
Locking the 40 rows T1 read does NOT help -- row 41 did not exist to lock.
Preventing phantoms requires locking the RANGE or the PREDICATE.
Distinguishing the four — the table examiners want
| Problem | Conflict type | What goes wrong | Prevented by |
|---|---|---|---|
| Lost update | write–write | One update silently overwritten | Any correct protocol |
| Dirty read | write–read | Reading data that is later rolled back | Read Committed |
| Unrepeatable read | read–write | Same row read twice, different values | Repeatable Read |
| Phantom | read–insert | Same query run twice, different row set | Serializable |
Unrepeatable read vs phantom is the pair most often confused. An unrepeatable read concerns an existing row whose value changed; a phantom concerns rows appearing or disappearing from a result set. Row-level locking stops the first; only range or predicate locking stops the second.
27.3 Schedules¶
Schedule
A schedule (history) S of n transactions is an ordering of all their operations such that, for each transaction, its operations appear in S in the same order as within the transaction. Operations of different transactions may be interleaved.
Serial schedule
A schedule in which the operations of each transaction are executed consecutively, with no interleaving.
Every serial schedule is correct by definition — each transaction sees a consistent database and leaves one. For n transactions there are n! serial schedules, which may give different results; all are considered correct.
Serialisable schedule
A schedule is serialisable if it is equivalent to some serial schedule of the same transactions.
Serialisability is the accepted criterion of correctness for concurrent execution: it delivers the performance of interleaving with the correctness of serial execution.
Conflicting operations¶
Conflict
Two operations conflict if all three hold:
- They belong to different transactions;
- they access the same data item;
- at least one of them is a
write.
| Pair | Conflict? |
|---|---|
read(X) / read(X) |
No — neither changes anything |
read(X) / write(X) |
Yes |
write(X) / read(X) |
Yes |
write(X) / write(X) |
Yes |
write(X) / write(Y) |
No — different items |
Non-conflicting operations may be swapped without changing the result. Conflicting ones may not.
Conflict serialisability
A schedule S is conflict serialisable if it can be transformed into some serial schedule by a sequence of swaps of adjacent non-conflicting operations.
Equivalently — and far easier to test — its precedence graph is acyclic.
27.4 The Precedence Graph Test¶
Algorithm
- Draw one node for each transaction.
- Draw a directed edge Ti → Tj whenever an operation of
Tiprecedes and conflicts with an operation ofTj. Specifically, addTi → TjifTiexecutes:write(X)beforeTjexecutesread(X), orread(X)beforeTjexecuteswrite(X), orwrite(X)beforeTjexecuteswrite(X).
- If the graph has no cycle, the schedule is conflict serialisable, and any topological order of the graph gives an equivalent serial schedule. If it has a cycle, it is not.
Worked example 1 — serialisable¶
S1: T1: read(X) T1: write(X) T2: read(X) T2: write(X)
T1: read(Y) T1: write(Y) T2: read(Y) T2: write(Y)
Conflicts: T1:write(X) precedes T2:read(X) → edge T1 → T2. T1:write(Y) precedes T2:read(Y) → also T1 → T2. No conflict runs the other way.
+----+ +----+
| T1 |------>| T2 | no cycle
+----+ +----+
Acyclic → conflict serialisable, equivalent to the serial order T1, T2.
Worked example 2 — not serialisable¶
S2: T1: read(X) T2: read(X) T2: write(X) T1: write(X)
T1:read(X)precedesT2:write(X)→ edge T1 → T2T2:write(X)precedesT1:write(X)→ edge T2 → T1
+----+ -----> +----+
| T1 | | T2 | CYCLE
+----+ <----- +----+
Cyclic → not conflict serialisable. This is exactly the lost update schedule of Section 4.2: T1's write is overwritten.
Worked example 3 — three transactions¶
S3: T1: read(X) T2: write(X) T3: read(X) T1: write(Y) T3: write(Y)
T1:read(X)beforeT2:write(X)→ T1 → T2T2:write(X)beforeT3:read(X)→ T2 → T3T1:write(Y)beforeT3:write(Y)→ T1 → T3
+----+ -----> +----+ -----> +----+
| T1 | | T2 | | T3 |
+--+-+ +----+ +--^-+
| |
+---------------------------+ no cycle
Acyclic → serialisable, equivalent to the serial order T1, T2, T3 (the unique topological order here).
Conflict serialisability is sufficient, not necessary
Every conflict-serialisable schedule is serialisable, but some serialisable schedules are not conflict serialisable — they happen to produce the right answer for reasons the conflict analysis cannot see (for instance a blind write that overwrites a value nobody used).
The broader notion is view serialisability, which admits more schedules. But testing view serialisability is NP-complete, whereas the precedence graph test is linear-time. Practical systems therefore enforce the stricter, cheaply testable conflict serialisability.
Recoverable and cascadeless schedules¶
Serialisability is not the whole story; a schedule must also behave correctly when a transaction aborts.
Three further classes
Recoverable — a transaction commits only after every transaction whose data it read has committed. Otherwise a committed transaction might depend on an aborted one, which cannot be repaired.
Cascadeless (avoiding cascading rollback) — a transaction reads only data written by committed transactions. This prevents one abort from forcing a chain of rollbacks.
Strict — a transaction neither reads nor writes an item until the transaction that last wrote it has committed or aborted. The strongest and simplest to recover; it makes undo trivial, since the before-image is always the last committed value.
strict ⊂ cascadeless ⊂ recoverable
27.5 Locking and Two-Phase Locking¶
Testing a schedule after the fact is of no use — the scheduler must prevent non-serialisable schedules as they form. Locking is the standard mechanism.
Lock modes
Shared lock S(X) (read lock) — several transactions may hold it simultaneously; permits reading only.
Exclusive lock X(X) (write lock) — only one transaction may hold it, and no shared lock may coexist; permits reading and writing.
Compatibility matrix:
| Requested \ Held | None | Shared | Exclusive |
|---|---|---|---|
| Shared | grant | grant | wait |
| Exclusive | grant | wait | wait |
Only read–read is compatible, which is precisely the pair that does not conflict.
Two-Phase Locking (2PL)
Every transaction obeys two phases:
Growing (expanding) phase — the transaction may acquire locks but may not release any. Shrinking phase — the transaction may release locks but may not acquire any.
The moment of the first release is the lock point.
Theorem: if every transaction follows 2PL, every resulting schedule is conflict serialisable — and the equivalent serial order is the order of the transactions' lock points.
locks
held
^
| .-----. <-- LOCK POINT
| / \
| / \
| / \
+----------------------------> time
GROWING | SHRINKING
(acquire | (release only)
only) |
Variants:
| Variant | Rule | Guarantees |
|---|---|---|
| Basic 2PL | As above | Conflict serialisability |
| Conservative (static) 2PL | Acquire all locks before starting | Serialisability and deadlock-freedom; but requires knowing all items in advance, and reduces concurrency |
| Strict 2PL | Hold all exclusive locks until commit or abort | Serialisability and strict schedules — no dirty reads, no cascading rollback. The most widely used. |
| Rigorous 2PL | Hold all locks until commit or abort | Simplest to implement; slightly less concurrency |
Deadlock¶
2PL prevents non-serialisable schedules but permits deadlock
T1: X(A) granted ......................... wants X(B) -- WAITS
T2: ............... X(B) granted ......... wants X(A) -- WAITS
+----+ waits for +----+
| T1 |------------>| T2 |
+----+<------------+----+ CYCLE in the wait-for graph
waits for = DEADLOCK
Neither can proceed; both wait forever.
Handling deadlock — three approaches:
- Detection and recovery. Maintain a wait-for graph; periodically look for a cycle; when one is found, choose a victim transaction and abort it. The usual choice in practice, and what MySQL's InnoDB does.
- Prevention. Impose an ordering that makes cycles impossible: acquire locks in a fixed global order, or use timestamp schemes such as wait-die (an older transaction waits, a younger one aborts) and wound-wait (an older transaction forces a younger one to abort).
- Timeout. Abort any transaction waiting longer than a threshold. Simple but crude — it aborts transactions that were merely slow.
A related hazard is starvation, where one transaction is repeatedly chosen as the victim and never completes. Fair scheduling — for example, by using transaction age in the victim choice — prevents it.
27.6 SQL Isolation Levels¶
Full serialisability is expensive. SQL therefore lets an application trade isolation for concurrency, choosing which problems it can tolerate.
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
START TRANSACTION;
...
COMMIT;
| Isolation level | Dirty read | Unrepeatable read | Phantom |
|---|---|---|---|
| READ UNCOMMITTED | possible | possible | possible |
| READ COMMITTED | prevented | possible | possible |
| REPEATABLE READ | prevented | prevented | possible* |
| SERIALIZABLE | prevented | prevented | prevented |
* The standard permits phantoms at REPEATABLE READ; MySQL's InnoDB actually prevents them too, using next-key (gap) locking.
Choosing a level
- READ UNCOMMITTED — almost never justified. Use only for approximate reporting where a small error is acceptable and speed is paramount.
- READ COMMITTED — the default in Oracle, PostgreSQL and SQL Server. A good balance for most applications.
- REPEATABLE READ — the default in MySQL/InnoDB. Necessary when a transaction reads the same row more than once and must see a stable value.
- SERIALIZABLE — full correctness, lowest concurrency. Use for financial reconciliation, stock-taking, or anything where a phantom would be unacceptable.
The principle: the lowest level at which the application remains correct, never lower. Do not lower the level to fix a performance problem without proving the resulting anomalies are harmless.
27.7 Solved Questions¶
Solved Question 1
Q. Why are transactions interleaved rather than executed serially? Explain the four concurrency problems that result, with a time-line for each.
A. Two reasons for interleaving.
- Throughput. A transaction spends most of its life waiting for disk — about 10 ms per block access, against nanoseconds of CPU work. Serial execution would leave the processor idle almost all the time; interleaving lets it run another transaction while the first waits.
- Response time. Without interleaving a short transaction queues behind a long one, so a five-millisecond seat enquiry could wait behind a five-minute report.
The four problems (time-lines as in Section 4.2):
Lost update (write–write). Both transactions read X = 100, one subtracts 10 and the other 20, and the second write overwrites the first. The result is 80 instead of 70 — one update has vanished, because T2 read before T1 wrote.
Dirty read (write–read). T1 writes X = 90 and T2 reads it; T1 then rolls back, so X returns to 100. T2 has acted on a value that never officially existed. Worse, if T2 has already committed, rolling it back too is impossible — which is why an abort may force cascading rollback.
Unrepeatable read (read–write). T1 reads X = 100; T2 changes it to 50 and commits; T1 reads X again and gets 50. The same item gave two answers within one transaction, so any calculation comparing them is meaningless.
Phantom read (read–insert). T1 counts admissions to CS01 and gets 40; T2 inserts a new admission and commits; T1 recounts and gets 41. Locking the 40 rows T1 read would not have helped — row 41 did not exist to be locked — so preventing phantoms needs range or predicate locking.
Solved Question 2
Q. Define schedule, serial schedule and conflict serialisability. When do two operations conflict?
A. A schedule S of n transactions is an ordering of all their operations such that each transaction's own operations appear in S in their original relative order. Operations of different transactions may be interleaved.
A serial schedule executes each transaction's operations consecutively, with no interleaving. Every serial schedule is correct by definition. For n transactions there are n! of them, which may give different results — all equally acceptable.
A schedule is serialisable if it is equivalent to some serial schedule. This is the accepted criterion of correctness: the performance of interleaving with the correctness of serial execution.
Two operations conflict if all three conditions hold:
- they belong to different transactions;
- they access the same data item;
- at least one is a
write.
So read/read never conflicts; read/write, write/read and write/write on the same item always do.
Conflict serialisability. A schedule is conflict serialisable if it can be turned into a serial schedule by repeatedly swapping adjacent non-conflicting operations. Since only non-conflicting swaps are allowed, the result computed is unchanged — which is why the transformation proves equivalence.
The practical test is the precedence graph: draw Ti → Tj whenever an operation of Ti precedes and conflicts with one of Tj; the schedule is conflict serialisable if and only if the graph is acyclic, and any topological order gives an equivalent serial schedule.
Solved Question 3
Q. Test this schedule for conflict serialisability using a precedence graph, and give an equivalent serial schedule if one exists.
S: r1(X) r2(X) w1(X) r3(Y) w2(X) w3(Y) r1(Y)
r1(X) means T1: read(X).)
A. Examine every pair of conflicting operations, in schedule order.
On item X — operations in order: r1(X), r2(X), w1(X), w2(X).
| Earlier | Later | Conflict? | Edge |
|---|---|---|---|
r1(X) |
r2(X) |
no (read–read) | — |
r1(X) |
w2(X) |
yes (read–write) | T1 → T2 |
r2(X) |
w1(X) |
yes (read–write) | T2 → T1 |
w1(X) |
w2(X) |
yes (write–write) | T1 → T2 |
On item Y — operations in order: r3(Y), w3(Y), r1(Y).
| Earlier | Later | Conflict? | Edge |
|---|---|---|---|
r3(Y) |
w3(Y) |
same transaction | — |
w3(Y) |
r1(Y) |
yes (write–read) | T3 → T1 |
Precedence graph:
+----+ -------> +----+
| T1 | | T2 |
+----+ <------- +----+ T1 <--> T2 is a CYCLE
^
|
+--+-+
| T3 |
+----+
Edges: T1 → T2, T2 → T1, T3 → T1.
There is a cycle T1 → T2 → T1.
Conclusion: the schedule is NOT conflict serialisable. No equivalent serial schedule exists.
Why intuitively. T2 reads X before T1 writes it, so T2 must come before T1; but T1 writes X before T2 writes it, so T1 must come before T2. The two requirements are contradictory. Concretely, T1's write to X is lost — the lost update problem.
Solved Question 4
Q. Explain two-phase locking. State the theorem, prove informally why it works, and describe the variants.
A. Under two-phase locking, every transaction has two phases:
- a growing phase, in which it may acquire locks but release none;
- a shrinking phase, in which it may release locks but acquire none.
The instant of the first release is the transaction's lock point.
Theorem. If every transaction in a schedule follows 2PL, the schedule is conflict serialisable, and the equivalent serial order is the order of the transactions' lock points.
Informal proof. Suppose the precedence graph had a cycle T1 → T2 → ... → Tn → T1. An edge Ti → Tj means Ti performed a conflicting operation on some item before Tj did. Since conflicting operations require incompatible locks, Ti must have released its lock on that item before Tj acquired its own. Releasing puts Ti into its shrinking phase, so Ti's lock point precedes Tj's. Following the cycle round gives lock point of T1 < that of T2 < ... < that of T1 — a contradiction. Hence no cycle exists, and the schedule is conflict serialisable.
Variants:
| Variant | Rule | What it adds |
|---|---|---|
| Basic 2PL | Growing then shrinking | Conflict serialisability |
| Conservative (static) | Acquire all locks before starting | Deadlock-free, but needs all items known in advance and reduces concurrency sharply |
| Strict 2PL | Hold all exclusive locks until commit/abort | Produces strict schedules: no dirty reads, no cascading rollback. Most widely used. |
| Rigorous 2PL | Hold all locks until commit/abort | Simplest to implement; the serial order is the commit order |
The limitation. 2PL prevents non-serialisable schedules but does not prevent deadlock — two transactions can each hold a lock the other needs. Deadlock must be handled separately, by detection with a wait-for graph, by prevention (wait-die, wound-wait), or by timeout.
Solved Question 5
Q. What is deadlock? Give an example and describe three ways of handling it. What is starvation?
A. Deadlock is a state in which two or more transactions each hold a lock the other needs, so none can proceed. It corresponds to a cycle in the wait-for graph.
Example:
T1: X(A) granted ................. requests X(B) -- WAITS (T2 holds it)
T2: ............ X(B) granted ... requests X(A) -- WAITS (T1 holds it)
Wait-for graph: T1 → T2 and T2 → T1 — a cycle. Neither transaction can ever proceed.
Three approaches:
1. Detection and recovery. Maintain a wait-for graph with an edge Ti → Tj when Ti waits for a lock held by Tj. Run a cycle-detection algorithm periodically. On finding a cycle, choose a victim and abort it, releasing its locks. Victim selection weighs how long the transaction has run, how many locks it holds, and how many times it has already been aborted. This is what MySQL's InnoDB does. It permits maximum concurrency and pays only when a deadlock actually occurs.
2. Prevention. Make cycles structurally impossible:
- Ordered acquisition — all transactions request locks in one fixed global order, so no cycle can form.
- Wait-die — if an older transaction wants a lock held by a younger one it waits; if a younger one wants a lock held by an older one it aborts (dies) and restarts.
- Wound-wait — the reverse: an older transaction wounds (aborts) the younger holder; a younger one waits. Both timestamp schemes are deadlock-free because waiting always runs in one direction of age.
3. Timeout. Abort any transaction that has waited longer than a threshold. Trivial to implement, but crude: it aborts transactions that were merely slow, and choosing the threshold is guesswork.
Starvation is the situation in which a transaction is repeatedly chosen as the deadlock victim, or repeatedly denied a lock, and so never completes. It is prevented by making the victim-selection and lock-granting policies fair — for example by favouring transactions that have already been aborted several times, or by granting locks first-come-first-served.
Solved Question 6
Q. Describe the four SQL isolation levels and the problems each permits. Which would you choose for (a) a monthly sales report, (b) a seat-booking transaction, (c) an end-of-year financial audit?
A. (Table of Section 4.6.)
READ UNCOMMITTED — permits dirty reads, unrepeatable reads and phantoms. Effectively no isolation; a transaction may read data that is later rolled back.
READ COMMITTED — prevents dirty reads by reading only committed data, but a value may change between two reads within the transaction. Default in Oracle, PostgreSQL and SQL Server.
REPEATABLE READ — additionally guarantees that a row read twice gives the same value. Phantoms are permitted by the standard, though InnoDB prevents them with next-key locking. Default in MySQL.
SERIALIZABLE — full isolation; the outcome is equivalent to some serial execution. Lowest concurrency.
Recommendations:
(a) Monthly sales report. READ COMMITTED. The report reads a large volume of data; SERIALIZABLE would hold locks across the whole run and block the transactional workload. Dirty reads must be excluded — reporting figures from rolled-back transactions is unacceptable — but a small inconsistency between the beginning and end of a long read-only report is tolerable. (If a perfectly consistent snapshot is required, use the DBMS's snapshot-isolation or READ ONLY transaction facility rather than raising the lock level.)
(b) Seat booking. REPEATABLE READ at minimum, and SERIALIZABLE if overbooking must be impossible. The transaction reads the seat count, decides, and writes — the classic lost update pattern. READ COMMITTED would permit two clerks to read the same last seat. In practice the robust idiom is SELECT ... FOR UPDATE, which takes an exclusive lock at read time and works at any level.
(c) End-of-year financial audit. SERIALIZABLE. The audit must see one consistent instant across many tables; a phantom transaction appearing mid-audit would make the accounts fail to balance, and the cost of a wrong answer far exceeds the cost of reduced concurrency for one overnight run.
The general principle: choose the lowest level at which the application is still correct — and never lower it to fix a performance problem without first proving that the anomalies it admits are genuinely harmless.
27.8 Exercises¶
A. Short answer
- Give two reasons for interleaving transactions.
- Name the four concurrency problems.
- Distinguish unrepeatable read from phantom read.
- When do two operations conflict?
- Define conflict serialisability.
- State the two phases of 2PL.
- What is a deadlock, and how is it detected?
B. Precedence graphs — test each schedule and give an equivalent serial order if one exists
r1(X) w1(X) r2(X) w2(X)r1(X) r2(X) w1(X) w2(X)r1(X) w1(X) r2(X) w2(X) r1(Y) w1(Y)r1(A) r2(B) w1(A) w2(B) r1(B) w1(B)r1(X) r2(Y) w1(X) r3(X) w2(Y) w3(X) r1(Y)w1(A) r2(A) w2(B) r1(B) w1(C) r3(C)
C. Concurrency problems
- Construct a time-line demonstrating a lost update on the
TotalSeatscolumn, and state what the correct result should have been. - Construct a dirty-read scenario in the college database, and explain why cascading rollback may be needed.
- Construct a phantom-read scenario using the
ADMISSIONtable, and explain why row-level locking does not prevent it. - For each of the four problems, state the lowest SQL isolation level that prevents it.
D. Locking
- Rewrite the lost-update schedule of question 14 with 2PL locks inserted, and show that the problem disappears.
- Show that basic 2PL does not prevent deadlock, by constructing a deadlocked schedule.
- Explain why conservative 2PL is deadlock-free, and why it is nevertheless rarely used.
- Explain why strict 2PL prevents cascading rollback.
- Two transactions repeatedly deadlock and one is always chosen as the victim. Name the problem and give a remedy.
E. Analysis
- Explain why conflict serialisability is preferred to view serialisability in practice.
- Explain the relationship
strict ⊂ cascadeless ⊂ recoverable, giving a schedule in each class but not the next. - Recommend an isolation level for each, with justification: an ATM withdrawal; a "how many seats are left?" display; a payroll run; a search-results page.
- Explain why
SELECT ... FOR UPDATEsolves the lost-update problem at any isolation level. - A developer sets
READ UNCOMMITTEDto make a slow report faster. Evaluate this decision and suggest alternatives.
F. Objective — True or False with reason
- Two read operations on the same item conflict.
- Every serial schedule is serialisable.
- Every serialisable schedule is conflict serialisable.
- 2PL prevents deadlock.
- A cycle in the precedence graph means the schedule is not conflict serialisable.
- REPEATABLE READ prevents phantoms in the SQL standard.
- Strict 2PL prevents cascading rollback.
Answers to Section F
- False. Conflict requires at least one write; two reads change nothing and may be swapped freely.
- True. A serial schedule is trivially equivalent to itself.
- False. The converse holds. Some serialisable schedules (with blind writes) are not conflict serialisable; the broader class is view serialisable, but testing it is NP-complete.
- False. It guarantees conflict serialisability but permits deadlock, which needs separate handling.
- True. That is exactly the test.
- False. The standard permits phantoms at that level; only
SERIALIZABLEforbids them. (MySQL's InnoDB happens to prevent them anyway, via next-key locking.) - True. Exclusive locks are held until commit, so no transaction can read uncommitted data, and therefore no abort can cascade.
Lesson Summary
- Transactions are interleaved for throughput and response time; the price is interference.
- Four problems: lost update (w–w), dirty read (w–r), unrepeatable read (r–w), phantom (r–insert).
- Two operations conflict if they are from different transactions, on the same item, with at least one write.
- A schedule is conflict serialisable iff its precedence graph is acyclic; a topological order gives the equivalent serial schedule.
- 2PL (growing then shrinking) guarantees conflict serialisability but not freedom from deadlock. Strict 2PL additionally prevents dirty reads and cascading rollback.
- Deadlock is a cycle in the wait-for graph, handled by detection, prevention or timeout.
- SQL isolation levels trade isolation for concurrency: choose the lowest level at which the application remains correct.
End of Unit 6, and of the lecture series. Next: the Laboratory Manual and the Course Handbook.