23.2.3. Example of Partial Ordering with Software Modules

Imagine that I have several software modules and I have defined a relationship or a dependency between the modules by a relation R. I say that module i is related to module j if there is a dependency on the module j for the module i. Thus, module j can start only after module i is complete.

In a software project, modules often depend on each other. For example, if Module A must finish before Module B can start, we define a dependency relationship R, where Module A is related to Module B. This means B is dependent on A. Therefore, in project management and software design, a clear understanding of module dependencies helps in planning the execution and scheduling of tasks.

Think of a kitchen where preparing a meal involves multiple tasks. Cooking rice needs to be done before making fried rice, as the latter requires rice. Here, cooking rice is Module A and making fried rice is Module B. You can only start making fried rice after the rice is cooked, establishing a dependency similar to the software modules.

This dependency relationship is reflexive because I can always say that a module always depends on itself. It is antisymmetric because I cannot have two separate modules that depend on each other. If Module 1 depends on Module 2 and Module 2 depends on Module 1, this would lead to a deadlock. It is also transitive; if Module 2 depends on Module 1 and Module 3 depends on Module 2, then it implies Module 3 depends on Module 1.

The reflexive property means that a module's dependency relationship includes itself. Antisymmetry prevents any circular dependencies which can halt progress in a project, while transitivity allows us to infer dependencies indirectly. So if there's a chain of dependencies, we can understand them without needing to explicitly list every dependency.

Continuing the kitchen analogy, reflexivity means that cooking chicken requires itself; you can’t cook chicken without chicken. Antisymmetry prevents a situation where you need to finish cooking chicken to prepare fried chicken while also needing fried chicken to finish cooking chicken. Transitivity allows you to understand that if you need to boil water to cook rice (A), and you need to cook rice to make fried rice (B), then you must boil water to make fried rice (C).

This leads to the general definition of partial ordering. A relation R defined on a set S is a partial ordering if it is reflexive, antisymmetric, and transitive. In this case, the set S with the relation R is called a poset, which stands for partially ordered set.

A partial order is a way of defining how elements in a set relate to one another through a specific relation that respects these three properties. Each property helps us maintain a structured and logical relationship between the modules, enabling efficient planning.

Consider organizing books on a shelf. If you have a rule that a larger book must be placed before a smaller book (like in a stack from largest to smallest), you create a partial order among the books based on size. Some books may not have a relation at all (e.g., a cookbook and a travel book). This arrangement maintains a sense of order and categorization.

--