Figure 1. Example of a decomposition diagram with the process names omitted
The structured analysis method allows us to model the dynamics of an information system with an increasing amount of detail as processes are resolved into their component subprocesses.
At some level of detail, however, it is no longer efficient to split up processes any further. This is the 'leaf' level of the tree structure generated by the structured analysis' top-down stepwise refinement (decomposition diagram, see figure 1).
At that level of detail we still need to describe how the subprocess transforms its inputs into its outputs. This chapter enumerates several techniques at hand for doing so, and briefly describes them.
On the one hand, we describe several ways of specifying the behaviour of a process as an algorithm: flowcharts, Nassi-Schneiderman diagrams, structured English. On the other hand, certain aspects of information transformation can best be described in terms of decision tables.
The word 'algorithm' is derived from the arabic 'Al-Khwarizmi', the name of the author of a 12th century book that describes, among other things, the procedure to solve quadratic equations. Incidentally, the word 'algebra' is derived from the first word of the title of that book.
An algorithm is an unambiguous description of a procedure to achieve a complex result in terms of elementary, supposedly well-known steps.
In information technology and computer science, algorithms are the descriptions of computer procedures independent of the particular machines or languages they are to be implemented in.
The ancient mathematician Euclid has described a general procedure to compute the greatest common divisor (GCD) of two numbers efficiently:
"Repeatedly divide the larger number by the smaller one, replacing the larger number by the smaller one and the smaller one by the remainder of the division. As soon as the remainder is zero, the divisor of that last division is the GCD of the original two numbers."
Note that the above is not the definition of the greatest common divisor: it assumes that we already know the definition of the GCD, and it gives us a general way of quickly computing it.
Let us compute GCD(28, 192).
The greatest common divisor of 28 and 192 is therefore 4.
We shall use Euclid's algorithm as a running example in several of the following paragraphs on algorithm description techniques.
Early computer program designs would include symbolic descriptions of the flow of control in a computer program: a diagram containing the different instructions that the machine has to carry out, with arrows and lines showing the possible different chronological orderings of these instructions.
Flowcharting has developed into a highly sophisticated diagramming language in the course of time. Here, we only need a few elementary symbols (see figure 2): a rectangle for simple machine instructions (or any other steps considered 'elementary'), a diamond for yes/no type decisions (depending on the outcome of a test), and flow lines connecting them. Flow lines can be equipped with arrows if the direction of the flow is not immediately clear.
Flows may converge in meeting points. A flow can only diverge at a diamond shape. Rectangles have a single point of entry and a single point of exit.
Sometimes actions are modelled slightly differently if they involve some form of interaction with the user or a disk file. Also, circles or ovals will denote entry and exit points of the process. Most processes will have a single point of entry, but a process may have several terminators (exits). See figure 3.
A typical flowchart for a simple process would then look somewhat like figure 4, except that actions need to be specified inside the rectangles, and the diamonds must contain specific test conditions, i.e., yes/no questions.
Flowcharts for complex processes may be more difficult to read, but complex processes should be split up into simple ones anyway. Note that sequence lines may cross each other, but this is usually a sign that your process is getting too complicated.
The following flowchart describes Euclid's algorithm for finding the greatest common divisor of two positive integers a and b.
Of course it could be a matter of debate whether things like "swap a and b" are sufficiently elementary to be unambiguously clear, or whether they should be further refined, e.g., into:
And similarly one might decide to replace "compute the remainder of a divided by b" by an explicit description of how to compute the remainder, using only elementary instructions of a simple microprocessor (i.e., addition and subtraction). The point being: it depends on your audience how detailed your flowchart should be. There is certainly no universal agreement on what constitutes an "elementary step".
In order to restrict the amount of complexity that a designer can bring into a flowchart, and hence avoid the 'spaghetti' design problem, several technical solutions have historically been proposed. All of these come down to the principle that any action, even a branch or a loop, should have a single point of entry and a single point of exit.
A Nassi-Schneiderman diagram is a rectangular representation of a process. Simple processes are just that: rectangles with descriptions inside them.
If a process can be detailed as a time sequence of simpler processes, this is modeled by drawing several smaller rectangles underneath each other (see the left hand side of figure 6).
A conditional branching instruction (selection) always gives rise to an action being performed or not. Optionally an action can be specified to be carried out if and only if the test fails (the so-called else-part of the process). Diagrammatically, a selection is modeled by writing the test condition inside a downward-pointing equilateral triangle near the top of the rectangle, with the two alternative actions to be taken in two equal-sized rectangles underneath it. Conventionally, the action on the left hand side will be carried out if the condition turns out to be true, the right hand side containing the alternative 'false' part. Usually this convention is explicitly (and redundantly) indicated by putting the characters 'Y' and 'N' above the corresponding subprocess rectangles. The right hand side of figure 6 shows such a diagram.
A selection is inherently less complex than a test in a flowchart, because the latter has two end points, whereas the former has only a single point of exit. The two alternative courses of action are rejoined at the end of the selection block.
Repetition of statements, as when a flowchart points back to a previous instruction, can be achieved through an iteration. The statements to be iterated, i.e., repeated, are drawn inside a smaller rectangle that takes up the lower right of the actual rectangle. The remaining upside-down L-shape is used to describe the controlling condition for the iteration: the statements are repeated over and over until the controlling condition becomes false. If the condition is false from the start, the iteration statements are never performed. This construction corresponds to the WHILE-statement in structured programming languages like Pascal, C and some forms of Basic. See the central part of figure 6.
The following Nassi-Schneiderman diagram describes Euclid's algorithm for finding the greatest common divisor of two positive integers. Note that we have had to duplicate the statement "Divide a by b, calling the remainder r" from our flowchart, because iterations in a Nassi-Schneiderman diagram always have their controlling condition before the statements to be iterated.
Yourdon in fact does not recommend any specific diagramming technique for documenting processes at the elementary level. His suggestion is to write structured English, a kind of natural-language version of structured programming. Close reading of his text reveals that structured English is actually very close to Nassi-Scheiderman diagramming, except that it will be easier to read to anyone who has never heard of those diagrams.
Structured English uses sequence, selection and iteration through the use of natural English constructions like "and", "next", "finally", "while", "if/otherwise". Different levels of detail are obtained through indentation of the text.
Euclid's algorithm in structured English would look like this:
Note the similarity in structure between the above and the diagram in figure 7. We recommend using Nassi-Schneiderman diagrams for internal use by the design team, but structured English is definitely better for communication with the customers or any other party in the outside world.
Decision tables are a convenient technique for analyzing complex decisions, i.e., decisions involving several yes/no-inputs at once. If the number of testing conditions involved in a decision is larger than, say, two, flowcharts and Nassi-Schneiderman diagrams may grow unnecessarily complicated through having to incorporate every possible combination of outcomes in a separate part of the drawing.
A decision table has three types of components:
Graphically, a decision table consists of two rectangles of equal width placed on top of each other. The left part of the upper rectangle contains the elementary conditions, listed underneath each other. The left part of the lower rectangle contains the list of all possible actions.
The right hand side of both rectangles consists of a number of columns, each columns specifying a rule. In the upper rectangle, the columns contain "yes" and "no" marks (or T and F, or 1 and 0, depending on convention). In the lower rectangle, actions to be taken are indicated by crosses or check marks in the corresponding rows.
The following table indicates that bank customers whose balance has been positive for the past two years, receive a bonus if they take a car loan. If they don't take the car loan, they receive a gadget for a present.
| Conditions | Rules | |||
|---|---|---|---|---|
| Positive Balance | Y | Y | N | N |
| Car Loan | Y | N | Y | N |
| Actions | ||||
| Award Bonus | x | |||
| Send Gadget | x | |||
The number of rules may actually get very large in this way, doubling with every extra condition. For a complex decision involving a little as 7 inputs, we need 27 = 128 separate rule columns !
Fortunately it is then often possible to simplify the table by any or both of the following mechanisms:
| Conditions | Rules | ||
|---|---|---|---|
| Positive Balance | Y | Y | N |
| Car Loan | Y | N | - |
| Actions | |||
| Award Bonus | x | ||
| Send Gadget | x | ||
| Conditions | Rules | ||
|---|---|---|---|
| Balance > 0 | Y | Y | N |
| Balance > 1 Mio | Y | N | N |
| Actions | |||
| Send Publicity Flyer | x | ||
| Treat With Champaign | x | ||
(inspired by [Whitten], chapter 6, problem 8)
Transfer the following informal description of an exam grading procedure into a decision table.
Grades for a language examination can be A, B, C, D (pass grades from excellent to pass) or F (fail).
Initially, students are awarded percentages separately for the oral and written exams. Then a preliminary grade is given according to the following set of rules.
Afterwards, students who have attended at least two thirds of the lectures receive an upgrade, i.e., B becomes A, C becomes B, D becomes C. An F is only upgraded to D if the student had at least 60 percent for the oral test and at least 50 percent for the written test. Attendance therefore effectively upgrades the score for the written test by 10 percent points.