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).
Fig. 4a
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.
Fig. 4b
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).
Fig. 4c
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:
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.
Fig. 4e
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.
Fig. 4f
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. 4g
Fig. 4h shows some asymmetrical examples, where the two masters of the
detail are different, and can be named differently.
Fig. 4h
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.
Fig. 4i
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.
Fig. 4j
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.
Fig. 4k
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.
Fig. 4l
The second attempt in Fig. 4m is more explicit, but there is still some
ambiguity surrounding the optionality of the recursive relationship.
Fig.4m
Fig. 4n removes the ambiguity, making all constraints explicit in the
data structure.
Fig. 4n
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.
Fig. 4o
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.
Fig. 4p
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.
Fig. 4q
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.
Fig. 4r
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.
Fig. 4s
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.
Fig. 4t
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.
Fig. 4u
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.
References
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