This booklet is published under the terms of the licence summarized in footnote 1.
Fig. 4a places recursive structures into a three-by-three matrix. Remember, I always declare one end of the relationship to be the master (or top) and the other end to be the detail (or bottom).
This matrix classifies recursive problems into different kinds whose entity models take different shapes.
The less constraints you have to build into your model, the simpler the design. The more constraints you have to model, the more complex the design.
So, it is generally easier to design a system with variable-depth-network recursion (top-right corner of the matrix) than with fixed-depth-linear recursion (bottom-left corner of the matrix).
In practical enterprise application development, you tend to find mainly the more relaxed kinds of recursion. So we’ll start with simple examples of variable-depth recursion in the top row of the matrix.
In academic computer science courses, you often find the more constrained kinds of recursion. We’ll come back later to consider some case studies that illustrate patterns for more constrained kinds of recursion.
(By the way, many of the published design patterns for object-oriented software construction feature recursive communication between objects of a class. Two of the more easily understandable examples are shown in the book ‘object-oriented and business data’.)
Variable-depth recursion is more common in enterprise applications than fixed-depth recursion. This section shows the typical entity model shapes.
Fig. 4b shows a List, an ordered sequence of Entries. Entries may be added at the top, or the bottom, or the middle.
An entry in the middle has a one-to-one relationship to the entries on either side of it, the prior and next entries.These two relationships can be collapsed into a single relationship.
The relationship is optional at both ends because there must be a first and a last entry. And because if this is an enterprise application that only records lists rather than controls them, one might record an entry in the middle of the list before either of its neighbours.
One might store in each entry the key of both next and prior entries, but the convention in relational data analysis is to this is optimise this - to store either one or the other as a foreign key but not both. You can distinguish the primary key and the foreign key with role names:
Entry Number (this) mandatory primary key
Entry Number (next) optional foreign key
Fig. 4c shows a management hierarchy. Each manager may manage several other managers, down to the bottom level where a manager manages employees rather than other managers (but we don’t record employees here).
Again, the recursive relationship is optional at both ends, and following relational data analysis, the detail class will store the identity of the master class as a foreign key. Again, you can distinguish the primary key and the foreign key with role names:
Manager Name (self) mandatory primary key
Manager Name (manager) optional foreign key
Fig. 4d shows a ‘parts explosion’ problem. All but the lowest-level Components in a warehouse may be composed of several lower-level Components. All but the very largest Components may be used in composing several different larger Components. It is important to be able to find out which Components something is made of, and which Components something can be used to make.
Some Components are not composed of other Components and are not used in composing other Components. However, you cannot predict what Components a given Component may be composed from, or used to make, in the future.
Developing the previous pattern, you might draw the model shown in Fig. 4d:
But the many-to-many relationship in Fig. 4d is itself a generative pattern. Fig. 4e shows that resolving this in the normal way leads to a classic V structure, except that the two masters of the V are collapsed into one.
An object of the detail class forms a cross-reference between two different objects of the master class. In carrying out relational data analysis, the detail class holds the primary keys of the two masters. You can distinguish these keys by role names.
Component Number (made Component) mandatory foreign key
Component Number (used Component) mandatory foreign key
A constraint that applies most many-to-many link objects is that they cannot link one master object to itself. The normal way to specify this constraint is as a statement applied to the foreign key attributes of the link class. For example:
Manager Name (manager) not = Manager Name (self)
You should be aware that this constraint is not sufficient to guarantee an entity cannot relate to itself more indirectly. How to stop the situation where Manager A manages Manager B, who manages Manager C, who manages Manager A? You need to impose a more elaborate rule that might be expressed as ‘Do not create an object as belonging to master object that that it already owns as a detail object.’
Most business database designers ignore the problem. They would say that if the user is silly enough to create objects in such a structure, they do so at their own risk. In cases where it is needed, the rule is best specified in specifying the logic of the event that creates a new object (the event must follow the recursive relationships and fail on finding an invalid self-reference).
In most of the examples people use to illustrate network recursion, the link class is specifically designed to relate two objects of the master class. It is primarily a cross-reference. Often it is a key-only class.
In other examples, the link class is a concrete entity in its own right, and the recursive connection between objects of the master class is almost incidental. Fig. 4f shows an example on the right.
A Person who plays the role of committee chair on one or more committees is related to one or more other Persons playing the role of reserve committee chair (and the other way around of course). But this recursive relationship is almost an incidental feature of the situation in which a Committee has two chairpeople - two relationships to Person.
It seems highly doubtful that anybody will every enquire of a Person - which chairpeople are they related to via Committees? However, if they did enquire, you could design a simple enquiry process to retrieve the information for them.
Fig. 4g divides recursive structures in a more curious way, into symmetrical and asymmetrical cases.
Fig. 4h shows some asymmetrical examples, where the two masters of the detail are different, and can be named differently.
Given a Component, you use one relationship to list all the Components is it made of, and the other to list all the Components it goes to make.
Given a Person, you use one relationship list all their husbands, and the other to list all the wives (depending on their sex).
Fig. 4i shows some symmetrical examples, where every detail has two masters, but there is no way to differentiate one from the other.
The examples help to reveal a practical difficulty in drawing an enquiry access path for symmetrical cases.
Given a Town, you cannot use one relationship to list all the Towns it is connected to by a Route, because it is arbitrary whether that Town is recorded as End 1 or End 2 in the Route.
Given a Person, you cannot use one relationship to list all their Friends, because it is arbitrary whether that Person is recorded as Friend 1 or Friend 2 in the Friendship.
To list all of a person’s friends, or all of a town’s neighbouring towns, you are obliged to make any enquiry down both relationships (or else record each link entity twice, reversing the sequence of the foreign keys in the second).
What is going on here?
We set out to model things in the real world and classify them into sets. There is no order to the things in a real-world set. There is no precedence between the friends in a friendship, or the towns connected by a route.
But during software design we turn sets into lists. A list is ordered, one thing comes after another. When we represent an unordered set by an ordered list, we are obliged to impose a sequence on it. We are obliged to list one friend before the other, one town before the other.
So there is an inevitable mismatch between the real world and the implementation. This is the reason why you cannot devise a simple enquiry process to list all of a person’s friends, or all of a town’s neighbouring towns, without duplicating all the link data twice.
The entity models for recursive problems can look deceptively simple. Specifying processes to upadte recursive data strucures can be relatively difficult.
Consider the construction and deletion events of an object in a recursive structure. One event can appear in the state machine of the master class as having both ‘gain’ and ‘loss’ effects on different objects of the class. You have to distinguish the event effects with role names, much as you distinguish the attributes in relational data analysis.
Consider the construction event of an object in a network variable-depth recursive structure. When does it happen? You have to decide whether Composition Relationships are only created and destroyed on the birth and death events of a Component, or whether the users need additional events to create and destroy a Composition Relationship at any time between existing Components.
I find that methodical event modelling (supported by methodical object behaviour analysis) does lead economical solutions of the kind that are intuitively correct. The most difficult part is naming the event effects, since several events will affect different object instances of the same class, and you need to be careful to give these event effects a role name.
Fig. 4j shows a royal succession that starts with the declaration of a new king or queen. From that point on, each monarch inherits the throne from the previous monarch. Each succession is a one-to-one relationship between two monarchs.
But given that the first monarch has a fixed and unique place in the lineage, perhaps you should be more specific. Fig. 4k shows you might introduces subclasses and split the original one-to-one relationship into two halves - the next and the prior aspects of the relationship.
We’ll explore the use of subclasses in the next section.
Fixed-depth recursion is perhaps more common in academic and software engineering problems, but examples do occur enterprise applications.
Consider for example a map spotted with sites of interest. Each site may be divided into areas; each area may be further divided into sub areas; each sub area may be further divided; and so on down to the level of ‘elementary areas’ that are not sub-dividable.
A site is an area that cannot ever be part of a larger area. A site may contain many buildings. Each building on a site must be wholly contained in one ‘elementary area’ (though this may be the site itself).
The first attempt in Fig. 4l is somewhat ambiguous. The optionality of the recursive relationship allows all areas not to be part of a wider area.
The second attempt in Fig. 4m is more explicit, but there is still some ambiguity surrounding the optionality of the recursive relationship.
Fig. 4n removes the ambiguity, making all constraints explicit in the data structure.
Fig. 4n is interesting as a specification of constraints, but in developing event models to specify the processing of examples like this, you will come to a different view of what the distinct classes are.
Event modelling view of the same data structure
Fig. 4q shows the general pattern for modelling a fixed-depth hierarchic recursive class. It involves only three state machines - a basic class and two parallel aspect classes that specify what is different about the special instances of the first or top object and a last or bottom object.
Notice how subclasses roll up into their superclass. The book ‘object-oriented and business data’ describes how and why in more detail
Don’t forget we’re talking about the specification of the Business services layer. In Data services layer, you might roll all the classes up into one database table. The attributes of the subclasses may be stored in mutually exclusive columns of the table for the basic class.
Consider for example a variation of the ‘parts explosion’ problem, with the extra constraint that you know when recording a Component whether it is composed of other Components or not, and whether it is used in making other Components or not.
Fig. 4p shows the ‘typing’ of a Component can never be changed; it remains ‘elementary’ or ‘composed’, and ‘composing’ or ‘non-composing’, for all its life.
Again, Fig. 4p is interesting as a specification of constraints, but in developing event models to specify the processing of examples like this, you will come to a different view of what the distinct classes are.
Event modelling view of the same data structure
Fig. 4q shows the general pattern for modelling a fixed-depth network recursive class as state machines. It involves four state machines - a basic class with two parallel aspect classes, and a link class.
The two parallel aspect classes specify what is different about the special instances of a first or top object and a last or bottom object.
Often, the top and bottom objects in a recursive structure may change. In other words, the ‘topness’ and ‘bottomness’ types of an object are not fixed.
Where a type can be changed over time, the distinction between the ‘type’ and the ‘state’ of an object is blurred. It is rarely a good idea to model changeable types as subclasses in a data structure. The subclasses are better specified as options in event models and state machines than as subclasses in an entity model.
The standard entity models for fixed-depth recursion show the top and bottom types as subclasses that roll up into their superclass. The state machine of the superclass specifies only that behaviour that differs between subclasses, as mutually exclusive options in the state machine. The state variable of this state machine is in effect a type variable; it tells you what subclass applies.
What happens if you try to extend the standard fixed-depth model to handle a variable-depth structure? Suppose the top node is fixed, but the bottom node may be replaced. The bottomness of a node is now a temporary state rather than a fixed type. You could introduce a class called ‘period of time as a type’, between the master class and its subclasses.
You might well specify a period of time as a distinct class in this way if you need to keep a history of each period that each node was at the bottom of the structure.
Normally, past periods are forgotten, and the period of time is represented only by an iterated cycle inside the state machine of a higher-level persistent class. So all the lower-level classes disappear into the state machine of their master class.
If the top node were also variable, and you follow this line of reasoning through, you end up returning to the much simpler entity model I presented for a variable-depth hierarchic structure earlier.
From the design point of view, a relaxed recursive structure is not so interesting as a constrained recursive structure. The most interesting of all is a fixed-depth linear recursive structure.
I have worked through four case studies of linear recursion where one or both ends is fixed, from entity model to processing code. This section presents three of the resulting entity models.
Note how the standard pattern for fixed-depth recursion remains visible in the implemented solutions.
Dijkstra (1972) codes the Eight Queens problem as a peculiar kind of first-in-first-out stack. The main task is to model then implement the behaviour of a queen as she steps along a row of a chessboard looking for a safe square to sit in. Fig. 4s shows the entity model reverse-engineered from our coded solution.
As the patterns in this chapter have suggested, it turns out that what you need to model as state machines are the parallel classes QueenBasic, QueenFirstness and QueenLastness. The subclasses appear only as mutually exclusive options within these state machines, not as distinct machines.
The main task in the next example is to model then implement the events that store and remove Items from a first-in-first-out Shelf. Fig. 4t shows the entity model reverse-engineered from our coded solution.
I have shown the ‘classes’ that disappear during object behaviour analysis into the state machine of their master class, as boxes without solid boundaries.
It turns out that what you need to model as state machines are the parallel classes (SlotBasic, SlotBottomness and SlotTopness); the subclasses and periods of time beneath them appear only as components within these state machines, not as distinct state machines.
The main task in the final example is to model then implement the insert and delete events that manipulate Items in a chained list. Fig. 4u shows the entity model reverse-engineered from our coded solution.
Again I have shown the ‘classes’ that disappear during object behaviour analysis into the state machine of their master class, as boxes without solid boundaries.
It turns out that what you need to model as state machines are the parallel classes (ItemBasic, ItemFirstness and ItemLastness); the subclasses and periods of time beneath them appear only as components within these state machines, not as distinct machines.
The fourth case study I looked at was a very simple last-in-first-out stack. I did follow the standard design pattern, but the design was so trivial and so far optimisable by following various optimisation tricks, that very little of the pattern remained by the time I had finished with it. The design was transformed into less than a dozen lines of code.
(The last-in-first-out stack turned out to be interesting from a different point of view. It is better for revealing optimisation tricks than for illustrating a standard pattern for recursive design.)
Some have challenged us with: ‘You cannot reconcile the modelling of state machines with the object-oriented modelling of class hierarchies’ or ‘There are rules you cannot specify as tests on state variables.’ Some throw in arguments recalled from their computer science course such as ‘You cannot specify a stack using a regular expression’.
The detailed workings of the case studies (not shown here) support my claim that you can meet all these challenges, some by contradicting them, some by accommodating them.
You can reconcile inheritance with state machines
The case studies demonstrate the principle from our paper in the Computer Journal (1994) that you can accommodate inheritance in state machines by specifying the subclasses of a class as mutually exclusive options within one state machine. So a type variable becomes nothing more or less than a state variable.
You can equate classes with state machines
The case studies demonstrate the idea from chapter 5 that you can equate a class with a state machine. There are some cases where it seems a single variable is best maintained by more than one state machine (so ‘encapsulation’ is broken), but these are very rare and the principle is easily bent to accommodate them when they happen.
The full workings of the case studies exemplify some of the tricks that you need to know about how to model classes in the form of state machines, such dividing a class into parallel aspects. And importantly, the case studies illustrate how to coordinate state machines via event models, and how to turn these event models into working code, object-oriented or not.
You can apply constraints by testing cardinal numbers
The last-in-first out stack case study (not shown here) shows you can derive a simple solution involving precondition tests on the value of a cardinal number from a more complex solution involving precondition tests on the keys and state variables of objects, by well-defined transformation steps. Given that the transformations are understandable and reasonable, you can jump to designing the simple solution without any academic concern about the validity of the approach.
You can solve academic problems using our design techniques
The case studies show that the structured design techniques developed
for enterprise applications are equally well suited to computer-world systems.
Our notations and techniques are based on those in the
The case studies show you can completely ‘solve’ even obscure design problems like Dijkstra’s Eight Queens problem using an entity model, object behaviour analysis and Event Modelling.
Other case studies suggest the same analysis techniques apply equally well to embedded systems such as real-time process control systems.
All computer systems have at their heart a set of communicating state machines. We build these as a model of real-world objects and events in the Business services layer.
Prototyping the user interface may help to reveal the objects and events but it cannot completely specify them. Quite distinct effort is needed for analysing, specifying and implementing the Business services layer. This distinct effort involves thinking in ways made explicit by our three-way conceptual modelling techniques.
Ref. 1: “Software is not Hardware” in the Library at http://avancier.co.uk
Footnote 1: Creative Commons Attribution-No Derivative Works Licence 2.0
Attribution: You may copy, distribute and display this copyrighted work only if you clearly credit “Avancier Limited: http://avancier.co.uk” before the start and include this footnote at the end.
No Derivative Works: You may copy, distribute, display only complete and verbatim copies of this page, not derivative works based upon it. For more information about the licence, see http://creativecommons.org