Recognizing immediacy in an N-tree hierarchy and its application to protection groups

The benefits of providing access control with groups of users as the unit of granularity are enhanced if the groups are organized in a hierarchy (partial order) by the subgroup relation ⩽, where g ⩽h signifies that every member of group g is thereby also a member of group h. It is often useful to distinguish the case when g is an immediate subgroup of h , that is when g<h and there is no group k such that g<k<h. The class of partial orders called n-trees was recently defined by using rooted trees and inverted rooted trees as basic partial orders and combining these recursively by refinement. Any n-tree hierarchy can be expressed as the intersection of two linear orderings, so it is possible to assign a pair of integers l[x] and r [x] to each group x such that g⩽h if and only if l[g]⩽l[h] and r[g ]⩽r[h]. The author shows how to extend this representation of n-trees by assigning four additional integers to each group so that it is also easily determined whether or not g is an immediate subgroup of h