Transactions, ACID and schedule serializability
Goals and notation
Explain transaction guarantees, preserve each transaction's program order when interleaving operations, and determine whether a schedule is conflict serializable. Distinguish conflict equivalence from view equivalence and from the weaker coincidence of one final database value. Use r_i(X), w_i(X), c_i and a_i for transaction Ti reading X, writing X, committing and aborting. Unless stated otherwise, each read sees the most recent preceding write to that item, or its initial value. The serializability exercises use single-version schedules of committed transactions.
1. ACID as four different promises
Atomicity means the transaction's effects happen as a unit: after failure it should not leave only a committed-looking prefix. Consistency means a correct transaction preserves declared constraints and application invariants when starting from a valid state; the DBMS cannot invent all business rules. Isolation controls how concurrent execution is observed. Durability means a reported commit survives the failures covered by the system's durability contract.
Example: transfer 40 units from account A to B. Starting balances are 100 and 50. A correct serial transfer finishes at 60 and 90, preserving the total 150. A crash after storing A=60 but before changing B needs rollback or completion under the recovery design; keeping 60 and 50 violates the transfer invariant. Another transaction reading between these changes can observe a partial transfer unless isolation prevents it. Committing without ensuring recoverable durable information threatens durability.
Typical lifecycle: active while operations execute; partially committed after the last statement but before commitment is guaranteed; committed after successful commit; failed if execution cannot continue; aborted after rollback. A restart creates a new execution attempt. Finishing the last SQL statement is not by itself durable commit.
2. Serial schedules and interleavings
A serial schedule runs each transaction's operations contiguously with no interleaving. A serializable schedule may interleave but is equivalent, under a specified equivalence relation, to some serial ordering. Transactions' own program orders must remain unchanged. With m operations in T1 and n in T2, the number of order-preserving interleavings is binomial(m+n,m) when all operations are distinct and there are no other restrictions; this count does not imply those schedules are serializable.
Lost-update example: initial X=10, T1 intends X←X+5 and T2 intends X←2X. Schedule r1(X=10),r2(X=10),w1(X=15),w2(X=20) ends at 20. Serial T1 then T2 would produce 30; serial T2 then T1 would produce 25. The concurrent result is neither. This numerical example illustrates an anomaly; a general serializability proof uses operation dependencies rather than a chosen initial value.
3. Conflicts and precedence graphs
Two operations conflict if they belong to different transactions, access the same item, and at least one is a write. Thus read–write, write–read and write–write conflict; read–read does not. Operations on different items do not conflict in this abstract model. Operations within the same transaction are ordered by the program, not by graph edges between distinct vertices.
Make one vertex per transaction. For each conflicting pair where an operation of Ti precedes one of Tj, add Ti→Tj. A schedule is conflict serializable exactly when this graph is acyclic. Any topological order gives a conflict-equivalent serial order. Multiple topological orders may exist, and duplicate reasons for an edge still produce only one graph edge. A directed cycle, including a two-way pair, rules out conflict serializability.
Worked acyclic schedule: r1(A),w1(A),r2(A),w2(B),r3(B),w3(C). A contributes T1→T2; B contributes T2→T3; C has no intertransaction conflict. The graph is a chain, so T1,T2,T3 is its only topological order. T1 and T3 need not directly conflict for their order to be constrained transitively.
Worked cycle: r1(A),r2(B),w1(B),w2(A). The first read and final write give T1→T2 on A. The read by T2 and write by T1 give T2→T1 on B. The cycle means no conflict-equivalent serial order, despite each transaction performing only two operations.
4. Conflict equivalence and safe swaps
Schedules are conflict equivalent when they contain the same operations of the same transactions and order every conflicting pair identically. Adjacent nonconflicting operations from different transactions can be swapped without changing conflict equivalence. Repeated safe swaps can transform a conflict-serializable schedule to a serial one. Swapping reads on different items is safe here; swapping a write and another transaction's read of the same item is not.
Equal final states for one initial state are weaker. For example, arithmetic may accidentally produce the same result on X=0 even when the dependency graph has a cycle. Read observations matter, and conflict serializability is a structural property of the schedule.
5. View equivalence and blind writes
Two schedules are view equivalent if every read of an initial value remains an initial-value read; every noninitial read gets its value from the same specific transaction's write; and each item's final writer is the same. These conditions are about read-from relationships and final writers, not merely equal numerical values. A schedule is view serializable if view equivalent to a serial schedule.
Every conflict-serializable schedule is view serializable, but not conversely. Example with no reads: w1(X),w2(X),w1(X). The graph has T1→T2 and T2→T1, so it fails conflict serializability. It is view equivalent to serial T2 then T1 because there are no reads to preserve and the final writer is T1 in both. T1's writes are blind: they are not preceded by a read of X in T1. View-serializable schedules outside the conflict-serializable class require blind writes; the presence of a blind write alone does not guarantee view serializability. General view-serializability testing is harder than the polynomial graph test for conflict serializability.
Pitfalls and next step
Serializability describes equivalence of concurrent execution; recoverability describes whether commit/abort dependencies are safe. One does not automatically guarantee the other. ACID isolation is not a claim that every real database's default isolation level is serializable. Keep item-level assumptions explicit; predicates and phantoms require more than a graph that omits those accesses. Next, add commit/abort events and examine recoverability and recovery.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Which pair conflicts in an item-level schedule?
A. r1(X), r2(X) B. r1(X), w2(Y), X≠Y C. w1(X), r2(X) D. r1(X), w1(X)
Answer: C
A: Read–read has no write.
B: Different items do not conflict here.
C: Different transactions, same item and a write meet all conditions.
D: These are from one transaction, not an intertransaction conflict.
P02. A precedence graph is acyclic. What follows?
A. Schedule is conflict serializable B. Schedule must be serial C. Schedule must be strict D. Exactly one serial order exists
Answer: A
A: A topological order supplies a conflict-equivalent serial schedule.
B: Interleaving is allowed.
C: Strictness involves uncommitted accesses and is separate.
D: A DAG can have multiple topological orders.
P03. For r1(A),r2(B),w1(B),w2(A), the graph contains:
A. Only T1→T2 B. Only T2→T1 C. Both directions D. No edges
Answer: C
A: The B conflict also gives the reverse edge.
B: The A conflict also gives the reverse edge.
C: A gives T1→T2; B gives T2→T1.
D: There are read–write conflicts on both items.
P04. w1(X),w2(X),w1(X), with no reads, is:
A. Conflict serializable only B. View serializable but not conflict serializable C. Neither D. View equivalent only to T1 then T2
Answer: B
A: The graph has a cycle.
B: Final writer T1 matches serial T2 then T1; there are no reads.
C: It has a view-equivalent serial order.
D: T1 then T2 would make T2 the final writer.
P05. Which guarantee prevents a failed transfer from leaving only its debit permanently applied?
A. Atomicity B. A particular index type C. Read–read conflicts D. A unique topological order
Answer: A
A: Atomicity treats the transfer effects as a unit.
B: Index choice does not provide all-or-nothing behavior.
C: Reads alone do not conflict here.
D: Graph uniqueness does not supply rollback.
P06. Graph edges are T1→T3 and T2→T3 only. How many serial orders are consistent?
A. 1 B. 2 C. 3 D. 6
Answer: B
A: T1 and T2 can exchange positions.
B: T1,T2,T3 and T2,T1,T3 are the two orders.
C: T3 must follow both others.
D: Not all six permutations put T3 last.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in