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
