Definition
Conflict Graph (ACID)
Given a schedule for a set of transactions . A conflict graph is a graph representation of the conflicts between two or multiple transactions.
- The vertices of a conflict graph are the transaction identifiers.
- An edge from to denotes that the two transactions are conflicting, with making the relevant access earlier.
- Sometimes the edge is labelled with the item involved in the conflict.
Serialisability
A schedule is conflict serialisable if its conflict graph is acyclic. Intuitively, a conflict between two transactions forces an execution order between them (topological sorting).
Example
