Precedence graph

A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.

The precedence graph for a schedule S contains:

  • A node for each committed transaction in S
  • An arc from Ti to Tj if an action of Ti precedes and conflicts with one of Tj's actions.

Precedence graph examples

Example 1

Example 2

Example 2

A precedence graph of the schedule D, with 3 transactions. As there is a cycle (of length 2; with two edges) through the committed transactions T1 and T2, this schedule (history) is not Conflict serializable. Notice, that the commit of Transaction 2 does not have any meaning regarding the creation of a precedence graph.

Testing Serializability with Precedence Graph

Testing Serializability Example

Algorithm to test Conflict Serializability of a Schedule S along with an example schedule.

or

  1. For each transaction Tx participating in schedule S, create a node labeled Ti in the precedence graph. Thus the precedence graph contains T1, T2, T3.
  2. For each case in S where Tj executes a read_item(X) after Ti executes a write_item(X), create an edge (Ti → Tj) in the precedence graph. This occurs nowhere in the above example, as there is no read after write.
  3. For each case in S where Tj executes a write_item(X) after Ti executes a read_item(X), create an edge (Ti → Tj) in the precedence graph. This results in a directed edge from T1 to T2 (as T1 has R(A) before T2 having W(A)).
  4. For each case in S where Tj executes a write_item(X) after Ti executes a write_item(X), create an edge (Ti → Tj) in the precedence graph. This results in directed edges from T2 to T1, T2 to T3 and T1 to T3.
  5. The schedule S is serializable if and only if the precedence graph has no cycles. As T1 and T2 constitute a cycle, the above example is not (conflict) serializable.
gollark: I think the most cost-effective internal HDDs right now are 10TB ones pulled from a certain brand of external hard drives... the mystical WD EasyStore.
gollark: Also, if you have an NVMe SSD, though, those are usually in the M.2 form factor, which means they use a few of the (usually one to three) M.2 slots on the board itself, and sometimes take away bandwidth from regular SATA ports.
gollark: HDDs are a bit stagnant right now, but SSDs continue to cheapen.
gollark: You'd certainly hope so.
gollark: You can put in as many as you want as long as you have SATA cables and internal space.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.