Hierarchical Ordering

Hierarchical Orderings

A relation ≤ is said to be a hierarchical ordering if the following three statements hold:

  • For all tex:$$ a $$, tex:$$ a \leq a $$ ,
  • If tex:$$ a \leq b $$ and tex:$$ b \leq a $$, tex:$$ a = b $$,
  • If tex:$$ a \leq b $$ and tex:$$ b \leq c $$, it follows that tex:$$ a \leq c $$,
  • There is an object tex:$$ r $$ such that tex:$$ r \leq a $$ for all tex:$$ a $$, and
    • If tex:$$ a \leq c $$ and tex:$$ b \leq c $$ then either tex:$$ a \leq b $$ or tex:$$ b \leq a $$.

A finite collection of objects which are related with a hierarchical ordering are said to form a tree and the singular object referenced in Requirement 4 is referred to as the root of the tree.

The astute reader will note that the first three requirements are identical to a partial ordering; however, there are two further requirements: Requirement 4 states that there is a single root object tex:$$ r $$ which must precede all other objects. Requirement 5 may be reinterpreted as saying that from any object tex:$$ x $$, there is only one path tex:$$ r = x_0, x_1 , x_2,q \ldots, x_n = x $$ such that tex:$$ r = x_0 \leq x_1 \leq x_2 \leq \mdots \leq x_n = x $$.

Strict Hierarchical Ordering

A relation < is said to be a strict hierarchical ordering if the following statements hold:

  • For all tex:$$ a $$, tex:$$ a \not\le a $$ ,
  • At most one of tex:$$ a \le b $$ or tex:$$ b \le a $$ is true,
  • If tex:$$ a \le b $$ and tex:$$ b \le c $$, it follows that tex:$$ a \le c $$,
  • There is an object tex:$$ r $$ such that tex:$$ r \le a $$ for all other objects tex:$$ a $$, and
    • If tex:$$ a \le c $$ and tex:$$ b \le c $$, either tex:$$ a = b $$ , tex:$$ a \le b $$, or tex:$$ b \le a $$.

Local Definitions

Most hierarchical orderings are defined locally with definitions of form tex:$$ a $$ immediately precedes tex:$$ b $$.

Forests

If we remove Restriction 4, the natural consequence is that there may be more than one root. These n roots then define n disjoint trees. Such a collection of trees is said to be a forest.

Examples

  • The Unix directory structure with dir_a immediately preceding dir_b if dir_b is a directory within dir_a; the root of the tree is the root directory designated /.
  • Java inheritance defines a hierarchical ordering with Class_A immediately preceding Class_B if Class_B is a subclass of Class_A; the root of the tree is the class Type.
  • Most hierarchical organizations in society describe a hierarchical ordering where tex:$$ a \leq b $$ if tex:$$ b $$ is a subordinate of tex:$$ b $$.
  • Given all members of the species Homo sapian, the local definition that Ann immediately precedes Bob/Barb if Ann is the mother of Bob or Barb defines a hierarchical ordering. The root is the most recent common ancestor of all Homo sapians (see common descent).
  • Given a person tex:$$ r $$ and his or her ancestors (but not too far back), then define tex:$$ a \le b $$ if tex:$$ a $$ is a descendant of tex:$$ b $$.
  • The DOS file system forms a forest where each drive is the root of a tree.

References