this is equivalent to the condition that all nodes in some cut set of the collection of all paths leading

16 Views Asked by At

I can't understand what a'cut set' is, can you please explain in simple form?

A node is implicitly granted in X mode if all of its parents are (implicitly or explicitly) granted to the transaction in X mode. By induction, this is equivalent to the condition that all nodes in some cut set of the collection of all paths leading from the node to the roots of the graph are explicitly granted to the transaction in X mode and all ancestors of nodes in the cut set are explicitly granted in IX or SIX mode. Jim Gray; Raymond A. Lorie; G. R. Putzolu; Iriving L. Traiger (1976). "Granularity of locks and degrees of consistency in a shared data base".

1

There are 1 best solutions below

1
On BEST ANSWER

The basic notion is that of a graph cut, but "cut set" seems to be used in a slightly different way in your article, where it refers to a vertex set instead of an edge set.

In any case, the idea is that the recursively-defined condition, that $n$ is IGX if each of its parents is either EGX or IGX, is equivalent to the (non-recursively-defined) condition that every path from $n$ to a root goes through an EGX node (abbreviating "explicitly/implicitly granted in X mode" as EGX/IGX). The cut set is the set of these EGX nodes.