A precedence graph, also named conflict graph and serializability

Serializability

In concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...

 graph, is used in the context of concurrency control

Concurrency control

In information technology and computer science, especially in the fields of computer programming , operating systems , multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.Computer...

 in database

Database

A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...

s.

The precedence graph for a schedule S contains:

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

Precedence graph example

or


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

Schedule (computer science)

In the fields of databases and transaction processing , a schedule of a system is an abstract model to describe execution of transactions running in the system. Often it is a list of operations ordered by time, performed by a set of transactions that are executed together in the system...

 (history) is not Conflict serializable

Serializability

In concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...

.

Testing Serializability with Precedence Graph

The drawing sequence for the precedence graph:-

1. For each transaction T_i participating in schedule S, create a node labelled T_i in the precedence graph. So the precedence graph contains T₁, T₂, T₃
2. For each case in S where T_j executes a read_item(X) after T_i executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. Here this process is not happening anywhere as there is no read after write.
3. For each case in S where T_j executes a write_item(X) after T_i executes a read_item(X), create an edge (T_i --> T_j) in the precedence graph. This will bring to front a directed graph from T₁ to T₂.
4. For each case in S where T_j executes a write_item(X) after T_i executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. It creates a directed graph from T₂ to T₁, T₁ to T₃, and T₂ to T₃.
5. The schedule S is serializable if and only if the precedence graph has no cycles. As T₁ and T₂ constitute a cycle, the above schedule is not supposed to be serializable.

External links

• The Fundamentals of Database Systems, 5th Edition the use of precedence graphs is discussed in chapter 17, as they relate to tests for conflict serializability.