Transactions and concurrency control

Transaction model

Definition. A transaction is a sequence of database reads and writes treated as one logical unit. Read($X$) copies a database item into a transaction’s local workspace; Write($X$) propagates a local value to the database. A schedule is an interleaving that preserves each transaction’s internal order. Example. R1(A), W1(A), R2(A), W2(A) gives transaction 1 a chance to update A before transaction 2 reads it. Exam point. Schedule notation records operations, not whether a write eventually commits.

ACID properties

Definition. Atomicity requires all-or-nothing effects; consistency preserves declared database constraints when a transaction is correct; isolation controls interference among concurrent transactions; durability preserves committed effects across failures. These properties describe goals, while protocols implement them. Example. A transfer debits one account and credits another; atomicity prevents only one side from being committed. Exam point. Consistency is not a promise that the DBMS can repair arbitrary application logic.

Read and write conflicts

Definition. Two operations conflict when they belong to different transactions, access the same item, and at least one is a write. Thus R-W, W-R, and W-W conflict; R-R does not. Conflict order is the relative order of each conflicting pair. Example. R1(A), W2(A) conflict, while R1(A), R2(A) commute. Exam point. Different items never create a conflict, even if the operation types differ.

Conflict equivalence and serializability

Definition. Two schedules are conflict-equivalent if they contain the same operations and preserve the order of every conflicting pair. A schedule is conflict-serializable if it is conflict-equivalent to some serial schedule. Swapping adjacent nonconflicting operations leaves conflict-equivalence unchanged. Example. If only T1 writes A and T2 reads B, their operations on different items can be swapped without affecting conflict order. Exam point. Conflict serializability is sufficient for view serializability but is not the same as it.

Precedence graph test

Definition. Create one vertex per transaction. Add edge Ti→Tj when an operation of Ti precedes and conflicts with an operation of Tj on the same item. The schedule is conflict-serializable exactly when this graph is acyclic; a topological order gives an equivalent serial order. Example. If W1(A) precedes R2(A), add T1→T2. Exam point. For a cycle, cite the actual conflicting operations that justify each edge.

Worked precedence graph

Definition. Build edges item by item, considering all cross-transaction conflicts in schedule order. Multiple conflicts may yield the same directed edge; one edge is enough for cycle testing. A self-edge is not added because conflicts are defined across transactions. Example. Analyze R1(A), W2(A), R2(B), W1(B), R3(A), W3(B). Exam point. A transaction can create edges in both directions with another transaction on different items.

Step-by-step:

1. On A, R1(A) precedes W2(A), so add T1→T2.
2. W2(A) precedes R3(A), so add T2→T3.
3. On B, R2(B) precedes W1(B), so add T2→T1.
4. W1(B) precedes W3(B), so add T1→T3.
5. The graph has T1→T2 and T2→T1, a cycle. The schedule is not conflict-serializable.

Edge	Witness
T1→T2	R1(A) before W2(A)
T2→T1	R2(B) before W1(B)
T2→T3	W2(A) before R3(A)
T1→T3	W1(B) before W3(B)

Precedence graph and serial order

Definition. When the graph is acyclic, any topological ordering gives a serial transaction order equivalent under conflict swaps. There may be more than one valid order if some transactions are incomparable. A schedule can be serializable without being itself serial. Example. Edges T1→T3 and T2→T3 allow serial orders T1,T2,T3 and T2,T1,T3. Exam point. Do not report a unique serial order unless the graph forces one.

Recoverability

Definition. A transaction reads-from relation records which transaction produced the value it read. A schedule is recoverable if whenever Tj reads a value written by Ti, Ti commits before Tj commits. A recoverable schedule may still allow cascading aborts. Example. If T2 reads A written by T1, then T2 must not commit before T1. Exam point. Commit order is compared only for transactions connected by reads-from dependencies.

Cascadeless and strict schedules

Definition. A cascadeless schedule allows a transaction to read only values written by committed transactions. A strict schedule prevents any transaction from reading or writing an item last written by an uncommitted transaction. Strict implies cascadeless, and cascadeless implies recoverable, under the standard definitions. Example. W1(A), C1, R2(A) is safe for reading A; W1(A), R2(A) is not cascadeless if T1 has not committed. Exam point. Strictness also blocks dirty writes, which cascadelessness alone does not necessarily block.

Dirty read and cascading abort

Definition. A dirty read occurs when a transaction reads a value written by another transaction that has not committed. If the writer aborts, the reader may need to abort too; this dependency can cascade to further readers. Delaying reads until commit prevents this chain. Example. T1 writes A; T2 reads A and computes B; T1 aborts, forcing T2 to undo its dependent update. Exam point. Check the writer’s commit before the read, not merely before the reader’s commit.

Lost update and inconsistent analysis

Definition. A lost update occurs when two transactions read the same old value and one overwrites the other’s computed update. Inconsistent analysis occurs when an aggregate sees some but not all effects of a concurrent update. Isolation mechanisms prevent these anomalies. Example. A=10; T1 reads 10 and writes 15; T2 reads 10 and writes 8. The final value 8 loses T1’s increment. Exam point. A correct final value in one interleaving does not establish serializability.

Lock modes

Definition. A shared lock permits reads and is compatible with other shared locks. An exclusive lock permits reads and writes and conflicts with both shared and exclusive locks from other transactions. Lock compatibility is checked on the same item. Example. T1 holding S(A) can coexist with T2 holding S(A), but prevents T2 from acquiring X(A). Exam point. Lock conversion from S to X may wait if another reader remains.

Requested / held	S	X
S	compatible	incompatible
X	incompatible	incompatible

Two-phase locking

Definition. Under 2PL, a transaction has a growing phase, where it may acquire locks but release none, followed by a shrinking phase, where it may release locks but acquire none. Basic 2PL guarantees conflict serializability, but can deadlock and may permit cascading aborts. Example. lock-S(A), lock-X(B), unlock(A), unlock(B) respects 2PL; acquiring C after unlock(A) violates it. Exam point. 2PL does not by itself guarantee recoverability unless lock holding is strengthened.