Conflict Serialisability

Running transactions one at a time is correct by definition. Interleaving them is faster, and the question is whether a particular interleaving is still correct. Serialisability is the answer: a schedule is acceptable if its effect matches *some* serial order — any one will do, and nobody has to say in advance which.

Conflict serialisability is a slightly stricter, and much more checkable, version of that idea. It asks whether the schedule can be turned into a serial one by repeatedly swapping adjacent operations that do not conflict.

Functional dependency (X → Y)

Knowing X pins down Y. If two rows agree on X they must agree on Y. This is a statement about the world being modelled, not about the rows that happen to be in the table today.

Superkey and candidate key

A superkey determines every attribute in the relation. A candidate key is a superkey with nothing spare in it — remove any attribute and it stops working.

Prime attribute

One that appears in some candidate key. The normal forms are mostly rules about how non-prime attributes are allowed to depend on prime ones.

Partial dependency

A non-prime attribute determined by only part of a composite key. Forbidden by 2NF, and the direct cause of the update, insert and delete anomalies.

Transitive dependency

Key → X → Y where X is not a key. Forbidden by 3NF: the fact really belongs in a table keyed by X.

Lossless decomposition

Splitting a relation so that re-joining it gives back exactly the original rows — no more, no fewer. Guaranteed when the shared attribute is a key of one of the two pieces.

Two operations conflict when they are from different transactions, touch the same item, and at least one writes. Non-conflicting operations can be reordered freely without changing any outcome — so only the conflicts pin down the ordering.

1. 1Draw one node per transaction.
2. 2For every conflicting pair where Ti's operation comes before Tj's in the schedule, draw an edge Ti → Tj.
3. 3Look for a cycle.
4. 4No cycle: the schedule is conflict serialisable, and any topological sort gives an equivalent serial order.
5. 5A cycle: it is not, and no serial order produces the same result.

Each edge is a constraint saying *this transaction must come first*. A cycle means a transaction must precede itself, which no ordering can satisfy — that is the entire proof.

View serialisable

A weaker condition that accepts a few extra schedules involving blind writes. Every conflict serialisable schedule is view serialisable; testing view serialisability is NP-complete, which is why nobody does it.

Recoverable

No transaction commits before one it read from. Independent of serialisability — a schedule can be serialisable and still unrecoverable.

Cascadeless

A transaction only reads values written by transactions that have already committed, so one abort cannot force others to roll back. Strict 2PL guarantees this.

The precedence graph can only be built once the schedule exists — and by then any damage has been done. It is an analysis tool, not a scheduler.

Two-phase locking earns its place by guaranteeing in advance that the graph will be acyclic, without ever building it. The test is what proves the protocol is worth using; the protocol is what you actually run.