A Brief (but necessary) Interlude - Hierarchy Inversion 

Introduction 
Before pressing on with physical design, we must pause for a few moments to reintroduce an advanced Warnier/Orr construct, and to introduce some new concepts. The advanced construct is "concurrency," and the new concept is called an "inverted hierarchy." Fortunately, both topics are quite a bit simpler than they might at first sound.

Concurrency Revisited 
You will recall that concurrency is shown on a Warnier/Orr diagram with a plus sign "+", and is used to indicate that the order of the features separated by it is unimportant. Thus...

means the same thing as...

"A" (whether a data item or a process) contains both "B" and "C," but their order within "A" is unimportant..."B" may be present before "C", "C" may be present before "B", or they may be present simultaneously.

With the use of the concurrency operator, we can begin to describe some complex data structures which we could not otherwise adequately describe. For instance, if we diagram the structure of a calendar year, we get a structure like the following...

Remember that one important level in the calendar--"Week"--cannot be placed in this hierarchy, since weeks are not subsets of either months, quarters, or years (remember there are not exactly 52 weeks in a year, only approximately).

However, if we use the concurrency operator, we can describe the relationship of weeks and years quite nicely...

This diagram says that within the calendar, years and weeks occur at the same time (the doubled bracket is the Brackets notation for a duplicated set: it means that the same set is present on the diagram in two or more places).

Anytime you have two or more concurrent structures present in a data set, you have what is termed a "structure clash" (a term borrowed from the British guru in data structured design, Michael A. Jackson (not the entertainer)--his methodology is called JSP (for Jackson Structured Programming) and was created independently from Warnier's LCP a few years later).

Structure clashes occur regularly in data, and are often difficult to deal with when trying to create a single "sequential" program design. It is therefore advantageous to know another way of describing structure clashes that doesn't require the use of the concurrency operator. This alternate method involves the use of "inverted hierarchies."

Inverted Hierarchies 
Consider the following structure...

Assuming a calendar week that starts on a Sunday and ends on a Saturday, we can examine what would run on any given day of the week...

Thus for any given day of the week we always do daily activities. If it happens to be the beginning of the week, we must do week beginning activities beforehand, and if it happens to be the end of the week we must do week end processing afterwards. This can be summed up by the following diagram...

For each day we begin by asking "is today the Week Begin" (which it may or may not be). If it is we do week beginning activities. If it is not, we skip the Week Begin process and go on to daily activities. At the conclusion of the day we ask "was today the Week End" (again, it may or may not be). If it is we finish the day by processing week end activities.

If you substitute dummy identifiers for the three different categories of activities described on the previous diagram (and the diagram we started with), you can compare the two more easily...

The structure on the left is the original, and is said to be a hierarchy in its "native" form. The structure on the right is called an "inverted" hierarchy (for reasons which will become more obvious later on). Both diagrams do the same things in the same sequence as they operate, therefore they are equivalent. However, the inverted structure only views the world "one cycle at a time."

Notice that inverted hierarchies can be used to represent concurrent hierarchies on the same structure, without using the concurrency symbol. Look at the structure which follows...

Standard Pattern for Inversion 
Inverted hierarchies always follow a set pattern, which can be easily seen in the "year/quarter/month/day" hierarchy. Consider the following hierarchy, where [A] through [G] represent the activities done at the times indicated...

This hierarchy is inverted as follows...

For each day, daily processing [D] is done. Before processing daily activities, however, we check to see if today is the beginning of a new month (notice that if it isn't, we don't have to check for the the beginning of a quarter or a year, either). If today is the beginning of a month, we must additionally check to see if today is the beginning of a quarter (if it is, we must run quarter begin process [B] before running month begin process [C]). Similarly, if today is the beginning of a quarter, we further check to see if it is the beginning of a year, and if so run year begin process [A].

Similarly at the end of each day, we check to see if the day was the end of a month, and if so run month end process [E]. Then we check to see if the day was also the end of the quarter, and if so run quarter end process [F]. Finally, we check to see if the day was also the end of the year, and if so run year end process [G].

This "pattern" of inversion holds for any hierarchy, regardless of the names of the levels. For instance, the hierarchy in the following "nonsense" diagram...

would be inverted in exactly the same way...

You can begin to see why they are known as "inverted" hierarchies: not only to they appear to be sort of "inside out," but you'll notice that the repeating sets have turned into alternating sets, and that the lowest level has become the highest.

Inverted hierarchies are very useful in physical design, and we will be using them extensively when we design the Physical Output Mapping and the Physical Input Mapping. If you would like to see some more examples of inverted hierarchies, and learn some advanced techniques for inverting different kinds of structures, take a look at the advanced section that follows. If you have had enough of inverted hierarchies for the time being, go on to the tutorial on Physical Output and Input mappings.