The idea: is this interleaving as good as a serial run?
A database runs many transactions at the same time, so their reads and writes get mixed. Running them one by one (a serial run) is always correct, but slow. So the question is: given one mixed order, is its effect the same as some serial run? Conflict serializability gives a simple test. Find the pairs of operations whose order matters, draw them as arrows between the transactions, and look for a cycle.
The canvas shows the schedule as a grid (one row per transaction, time goes right), the data items A, B and C, the precedence graph, and a table that compares the schedule's final values with every serial run.
Schedules and the three programs
A schedule is one fixed order of all the operations. r1(A) means T1 reads item A, and w2(A) means T2 writes A. Inside the schedule each transaction keeps its own order; only the mixing between transactions changes. The items start at A = 100, B = 200 and C = 300.
To get real numbers, each transaction runs one small program on every item it touches:
| transaction | program | needs a read first? |
|---|---|---|
| T1 | X = X + 10 | yes |
| T2 | X = X × 2 | yes |
| T3 | X = 50 | no (a blind write) |
A read copies the item into the transaction's own copy. A write computes the new value from that copy, not from what the item holds at that moment. The order of these programs matters: (100 + 10) × 2 = 220, but 100 × 2 + 10 = 210.
Which operations conflict
Two operations conflict when all three of these hold:
- they are on the same item,
- they belong to different transactions,
- at least one is a write.
| earlier | later | conflict? | why |
|---|---|---|---|
| r1(A) | r2(A) | no | two reads see the same value in either order |
| r1(A) | w2(A) | yes | swapped, T1 would read T2's value |
| w1(A) | r2(A) | yes | swapped, T2 would read the old value |
| w1(A) | w2(A) | yes | swapped, the other value would be left in A |
| w1(A) | w2(B) | no | different items |
Two neighbours that do not conflict can be swapped without changing any value read or written. If such swaps can turn a schedule into a serial one, the schedule is conflict-serializable.
The precedence graph
Trying all swaps is slow. The precedence graph (also called the serialization graph) gives the answer directly. It has one node per transaction. For every conflicting pair it gets an edge Ti → Tj, where Ti's operation came first. The edge says: in any equivalent serial schedule, Ti must run before Tj. Many pairs can give the same edge; the page then only adds the item to the edge's label.
On the page, each Add Op runs the operation, lights the earlier operations it conflicts with, and draws the edge. Demo: serial schedule, T1 then T2 gives a single edge T1 → T2. Demo: interleaved but serializable mixes the two transactions on A and on B, but every conflict still points from T1 to T2.
Cycle or no cycle
If the graph has a cycle, the schedule is not conflict-serializable. A cycle T1 → T2 → T1 says T1 must run before T2 and T2 before T1. No serial order can do both.
If the graph has no cycle, the schedule is conflict-serializable, and any topological order of the graph is an equivalent serial schedule. Test Graph finds it the usual way: take a transaction with no incoming edge, remove it, and repeat (see topological sort by indegree). If the sort gets stuck, the transactions that are left form a cycle.
The serial order need not follow the transaction numbers or who started first. In Demo: three transactions, order T2 → T1 → T3 the edges are T2 → T1 (on A) and T1 → T3 (on B). A cycle also need not be between two transactions: in Demo: three transactions, a cycle through all three no pair has edges both ways, yet T1 → T2 → T3 → T1 closes a loop.
What goes wrong: real values
Compare Serial runs the same transactions one by one in every possible order and lists the final values.
| demo | graph | the schedule ends with | serial runs give |
|---|---|---|---|
| interleaved but serializable | T1 → T2, no cycle | A = 220, B = 420 | T1, T2: 220, 420 (same ✓) · T2, T1: 210, 410 |
| lost update | T1 ⇄ T2, cycle | A = 200 | 220 or 210, never 200 ✗ |
| two items, opposite orders | T1 → T2 on A, T2 → T1 on B | A = 220, B = 410 | 220, 420 or 210, 410 ✗ |
| order T2 → T1 → T3 | no cycle | A = 210, B = 50 | only T2, T1, T3 of the 6 runs is the same ✓ |
| a cycle through all three | T1 → T2 → T3 → T1 | A = 60, B = 420, C = 50 | none of the 6 runs ✗ |
In the lost update, T1 and T2 both read A = 100. T1 writes 110. Then T2 writes 100 × 2 = 200 from its old copy, and T1's + 10 is gone. In the "opposite orders" demo each item alone looks fine: A was updated in the order T1, T2 and B in the order T2, T1. Only together they match no serial run.
Two serial runs may give different values (220 or 210). Both are correct: a database promises the result of some serial order, not of one chosen order.
What MariaDB does instead
MariaDB does not build a precedence graph. Testing a schedule after it ran would be too late. InnoDB instead stops bad schedules while they happen, with row locks held until commit (strict two-phase locking). A lock makes the second transaction wait, so every conflict on a row points the same way and a cycle in the precedence graph cannot form. If the waits themselves form a cycle, InnoDB's deadlock detector rolls one transaction back with ERROR 1213 (40001), and the application runs it again.
How much is locked depends on the isolation level, set with SET TRANSACTION ISOLATION LEVEL …:
| level | plain SELECT | the lost update above |
|---|---|---|
| REPEATABLE READ (the default) | reads a snapshot, takes no lock | can happen when the application reads, computes and then writes |
| SERIALIZABLE | takes a shared lock, like SELECT … LOCK IN SHARE MODE (when autocommit is off) | both hold a shared lock and both want to write: a deadlock, one is rolled back |
At the default level you prevent the lost update yourself. Read with SELECT … FOR UPDATE, so the second reader waits for the first writer. Or let the server do the read and the write in one statement: UPDATE account SET balance = balance + 10 WHERE id = 1. See InnoDB isolation: snapshot reads vs current reads and MVCC and isolation levels.
Other ways to get the same guarantee without locks: timestamp ordering fixes the serial order in advance, and PostgreSQL's serializable snapshot isolation watches for a dangerous pattern of edges while transactions run.
See also recoverable, cascadeless and strict schedules, where transactions abort and a rollback can reach the transactions that read their data.
See also Validation-Based Optimistic Concurrency Control, where the validation order fixes the serial order.
What the page leaves out
Aborts and commits: every transaction here commits, so recoverable, cascadeless and strict schedules are not shown. View serializability: with blind writes a schedule can have a cycle and still equal a serial run; the conflict test is safe but stricter than needed (try r1(A), w3(A), w1(A), w3(A)). Comparing final values is also a weaker check than the graph: values can match by luck. Predicates and phantoms, where the conflict is on rows that do not exist yet (InnoDB uses gap locks for those). MariaDB has no command that shows a precedence graph or tests a schedule.