Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Precedence graph
Summary
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. 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).
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.
Algorithm to test Conflict Serializability of a Schedule S along with an example schedule.
or
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.
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.
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)).
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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.