Local Definition

A partial ordering on a finite collection of objects may be described as follows: each object can have multiple immediate sucessors; however, it is not possible to start at a any object and following a path from that object to an immediate successor object and ultimately get back to the initial object—there are no loops.

Mathematical Definition

A binary relationship $ a \le b $ (read as a precedes or equals b) between two objects is said to be a partial ordering if there is a single root $ r $ and:

• For all $ a $, $ a \le a $,
• If both $ a \le b $ and $ b \le a $ it follows that $ a = b $, and
• The relationship is transitive: if $ a \le b $ and $ b \le c $, this implies that $ a \le c $.

Example

Figure 1 shows a partial ordering of fifteen objects. You may observe how with the local definition, $ a_{21} $ has two immediate successors $ a_{31} $ and $ a_{32} $; however, using the partial ordering, we can also make statements such as $ a_{21} \le a_{41} $, $ a_{12} \le a_{21} $, and $ a_{00} \le a_{21} $.

Figure 1. A partial ordering on fifteen objects.

Nonexistence of Cycles

One feature of a partial ordering is that it is not possible to have a cycle occur. This is most easily demonstrated by looking at Figure 2: three immediate relationships are possible: $ a_0 \le a_1 $, $ a_1 \le a_2 $, and $ a_2 \le a_0 $; however, we can combine the second and third together with transitivity (the third rule) to get that $ a_1 \le a_0 $. Unfortunately, because $ a_0 \le a_1 $ and $ a_1 \le a_0 $, it follows that $ a_0 = a_1 $ which is false; therefore this relationship is not a partial ordering.

Figure 2. A non-partial ordering relationship on three objects.

Partial Orderings and Linear/Hierarchical Orderings

Note that any linear or hierarchical ordering defines a partial ordering where objects is the successor of at most one other object.

Implicit and Explicit Partial Orderings

In general, most hierarchical orderings are explicitly defined by the programmer and the data structure is constructed through explicit definitions.

Additional Operations on Partial Orderings

• Access those object which are not the successor of any other object;
• Provide a means for traversing through the partial order in a regular manner (e.g., a traversal through a topological sort);
• Given a reference to an object in the partial order:
  • Find the number of successors,
  • Determining if the object has no successors,
  • Provide a means of stepping through any successors,
  • Find the number of objects for which this object is a successor, and
  • Provide a means for stepping through those objects for which this object is a successor.

Additional Operations on Explicitly Defined Hierarchical Orderings

• Establish an edge from one object to another.
• Given a reference to an object, insert a successor.

Abstract Data Types Based on Partial Orders

There most common abstract data structure associated with a partial ordering is the Directed Acyclic Graph (DAG).