Questions tagged [precedence-graph]

A precedence graph or conflict graph or serializability graph is a graph of conflicts between transactions in a database.

Filter by
Sorted by
Tagged with
4
votes
2answers
278 views

Time complexity of a precedence constrained selection problem

I wonder if you have an idea over the time complexity of the following problem, or a problem similar to this one (generally a selection problem) [Assuming operations on integers take O(1) time] We ...
0
votes
1answer
2k views

Preparing precedence graph from fork and join code

I was referring to this page which defines fork, join and precedence graph as follows: When the statement ...
3
votes
2answers
440 views

Can you reduce a precedence graph or do *all* relevant nodes need to be connected

Let's say we have the following simple transaction-schedule: T1 | T2 | T3 -----+------+----- w(x)| | | w(x) | | | w(x) T1 comes before ...