Precedence graph

A precedence graph, also named conflict graph and <a href="/facts/Serializability/j6LY0fqE">serializability</a> graph, is used in the context of <a href="/facts/Concurrency_control/JWnmhVd5">concurrency control</a> in <a href="/facts/Database/VYcpkevb">databases</a>. It is the <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> representing precedence of transactions in the schedule, as reflected by precedence of conflicting operations in the transactions. A schedule is conflict-serializable <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> its precedence graph of committed transactions is <a href="/facts/Directed_acyclic_graph/k6zq1os9">acyclic</a>.
The precedence graph for a schedule S contains:

<ul><li>A node for each committed transaction in S</li>
<li>An arc from Ti to Tj if an action of Ti precedes and <a href="/facts/Database_transaction_schedule/9kRscku5">conflicts</a> with one of Tj's actions. That is the actions belong to different transactions, at least one of the actions is a write operation, and the actions access the same object (read or write).</li></ul>
Cycles of committed transactions can be prevented by aborting an undecided (neither committed, nor aborted) transaction on each cycle in the precedence graph of all the transactions, which can otherwise turn into a cycle of committed transactions (and a committed transaction cannot be aborted). One transaction aborted per cycle is both required and sufficient in number to break and eliminate the cycle (more aborts are possible, and can happen under some mechanisms, but are unnecessary for serializability). The probability of cycle generation is typically low, but, nevertheless, such a situation is carefully handled, typically with a considerable amount of overhead, since correctness is involved. Transactions aborted due to serializability violation prevention are restarted and executed again immediately.

Precedence graph open-in-new

Precedence graph