Although at first sight decision tables look almost the same as in the days of their first developments, some evolution in form and content, as well as in application areas, can be noted.  The power of decision tables and table structures to model, represent, and implement complex decision situations in a compact way — easy to check for completeness, consistency, and correctness — has however always been the common factor.

This is the first part in a series of articles that brings the reader up-to-date on the rich history of tabular models for decisions.  Although the overview is not complete because of space and time constraints, a reasonable insight into prior art will allow the reader to appreciate this powerful — yet often forgotten and re-invented — technique that is worth examining in the context of business rules (and business processes).

The overview is historical, so as to bring some order to the developments.  But this classification does not intend to diminish the value of earlier achievements.  In fact, some of the findings and basics have been known for a long time (or at least should have been), but that does not make them outdated or any less valuable.

The series will consist of six parts, covering decades of decision table research and practice:

Part 1.  Early developments and fundamentals
            The sixties and seventies:  conversion and algorithms
            The 1982 CODASYL Report of the Decision Table Task Group

Part 2.  Detailed description of CODASYL Report of the Decision Table Task Group
            (structures and types of tables, development methods, best practices, application areas)

Part 3.  The eighties:  modeling and verification & validation

Part 4.  The nineties:  tool support for modeling decisions

Part 5.  The millennium:  integration

Part 6.  Nowadays:  business logic modeling and decision analysis

Early developments and fundamentals

The concept of decision tables was first reported in 1957, in data processing applications, more specifically in programming [see NCC 70].  The story goes that General Electric, the Sutherland Corporation, and the USAF had unsuccessfully tried to define a complex file maintenance problem for more than six man-years, and then defined the problem with four people in four weeks using decision tables.  Earlier descriptions of the stages in the history of decision tables can be found in Pollack, Hicks & Harrison [71], Maes [81], and CODASYL [82].

Because of its representational capabilities, the decision table was introduced as a structured alternative to classical flowcharting.  Structured programming had not yet been born, but it was clear that the decision table could offer a solution to the spaghetti structure of complex conditionals by grouping related conditions in a table, where each column (or row) corresponds to a different situation, thereby allowing easy checking for the three C's:  completeness, consistency, and correctness.

The decision tables at that time were limited-entry tables (conditions had only two values:  Yes or No).  But the fundamental design of the table was already there:  conditions are listed in a certain order, and every column represents a conjunction of specific condition values for the conditions in the given order, e.g.:

if condition1 is true and condition2 is false then indicate some result.

Because the names of conditions and actions were only written once (in the 'stub') and did not have to be repeated in every column, the table was rather compact.

The ability to represent conditional logical expressions in a readable, compact manner and the ease of adaptation and consistency checking were considered to be a solution to the problem of growing program complexity (Montalbano [74]).

Originally the tables were manually translated into code.  A number of specific languages and initial preprocessors were soon developed (1961-1962) in order to convert the two-dimensional decision table into linear program code (rule engines were not available yet!).  Due in part to the limited efficiency of these simple processors, the initial interest did not lead to a general acceptance of decision table programming.  But the use of tables for code generation remained and the name 'Decision Tables' became the standard term.

The sixties and seventies:  conversions and algorithms

From 1965 onward, more attention was paid to the optimization of the conversion process, followed by the emanation of more powerful commercial preprocessors.  The Canadian Standards Association issued a first formal standard for decision tables (CSA [70]).

Decision tables were often limited-entry tables (tables with Boolean conditions), but gradually extended-entry conditions were introduced, with conditions showing a range of values, e.g., numeric intervals or value sets.  Decision tables containing extended-entry conditions were called extended-entry tables (or mixed-entry in case Boolean conditions are also present).

Conversion of decision tables into program code means that an efficient execution tree has to be generated for all the combinations of the condition values.  A different path in the execution tree can test the conditions in a different order; therefore the number of possible trees is enormous (and grows fast with a larger number of conditions).  Additional information used in the conversion algorithm can be:  the test time for each condition (if not available, all test times are considered equal) and case frequencies.  In that way, the average execution time for the decision can be minimized.

The conversion of decision tables into program code also means that the original sequence of the conditions in the decision table is not fixed for execution, because it may be optimized during implementation.  This is probably one of the first instances of model driven architecture, where the implementation is separated (and generated from) the tabular specification model.

In the era between 1965 and 1980, much effort was devoted to research on this conversion of decision tables into efficient computer programs, leading to a growing list of conversion algorithms.  The most important algorithms were (in chronological order):  Pollack [65], Reinwald & Soland [66], King [66], Mutukrishnan & Rajaraman [70], Shwayder [71], Verhelst [72], Bayes [73], Ganapathy & Rajaraman [74], Shwayder [74], Smillie & Shave [75], Shumacher & Sevcik [76], Lew [78], Martelli & Montanari [78], Sethi & Chatterjee [80], Papakonstantinou [80].  A discussion of the evolution and results of the most important algorithms can be found in Pooch [74] and Verhelst [80].

The development of new algorithms and preprocessors ended around 1975 (with some theoretical results up to 1980).  Was it because decision tables were considered less relevant (see e.g., Chvalovsky [76]), now that structured programming was already able to achieve a considerable reduction in program complexity?  Or was it because decision tables had grown too complex?  For example, it is no use trying to fit iterations and sequences into the strict decision table format and then apply an optimal table conversion algorithm, as these structures can easily and efficiently be implemented in a structured language.  Probably the new hype threw away some good practices, as the decision table technique is not incompatible with structured programming.  On the contrary, well-defined application of decision tables provides a perfect fit with structured programming control structures.

The 1982 Report of the CODASYL Decision Table Task Group:  A Modern Appraisal of Decision Tables

The findings about the decision table technique and the best practices were discussed and summarized by the Decision Table Task Group, installed by CODASYL (Conference on Data Systems and Languages) and chaired by dr. Paul C. Jorgensen from 1975-1978.  The group produced the excellent report "A Modern Appraisal of Decision Tables" (Figure 1), which offers an interesting and often neglected overview of the state of the art on decision tables (CODASYL [82]).

Figure 1.  The 1982 CODASYL report

Quoting from the report, the purpose was "to define decision tables, to explain much of the underlying theory, and to recommend a development methodology that centers on decision tables."  The conclusion of this report is that, when properly used, decision tables are an excellent tool for problem analysis, specification, design, coding, and documentation.

The report contained the following chapters:

• Introduction.
• Overview:  Advantages and use of decision tables.
• Theory:  A theoretical foundation for decision tables based on set theory and modern algebra.
• Conversion:  A review of decision table optimization techniques.
• Development Methodology:  The recommended use of decision tables in each phase of the software development process, from specification to acceptance and maintenance.
• Education:  A plan for teaching decision table technology to various categories of users, with thirteen subject matter modules and a set of sample problems.
• Glossary.
• Annotated Bibliography:  An annotated bibliography on 545 decision table publications.

As can be seen from the Table of Contents, a full overview and a number of new developments were described:

1. The ability of decision tables to represent logically complex situations is not limited to the world of programming; examples include information systems design, laws and regulations, standard operating procedures, analysis of specifications, structuring of management decisions, etc.
   
   
2. The report defines the syntax, semantics, and pragmatics of decision tables.  It describes:
1. vertical layout (rules in columns)
2. horizontal layout (rules in rows)
3. single-hit tables (with no overlapping rules) and first-hit tables
4. multiple-hit tables (with overlapping rules)
5. decision table structures
6. contracted tables (containing irrelevant condition entries)
7. canonical form (containing single condition entries only)
8. completeness, consistency, etc.
   
   
3. The report describes an entire development method for structures of decision tables and individual tables.  It provides guidelines, criteria, and basic principles.
   
   
4. With decision table software, specification, implementation, and testing could be improved and strengthened by checking the decision tables for completeness and contradictions before going into implementation.
   
   
5. Decision tables improve the communication between business experts and software designers, because the tables are precise, consistent, and understandable.
   
   
6. Decision tables are not isolated, but are part of an entire structure (see the picture on the title page shown in Figure 1).  Anyone who thinks that decision table theory is about single decision tables is hopelessly outdated.

References

Bayes, A. [73], 'A Dynamic Programming Algorithm to Optimise Decision Tables Code," The Australian Computer Journal, 5(2), May 1973, pp. 77-79.

Chapin, N. [67], "Parsing Of Decision Tables," Communications of the ACM, 10(8), August 1967, pp. 507-512.

Cheng, C., Rabin, J. [76], "Synthesis of Decision Rules," Communications of the ACM, 19(7), July 1976, pp. 404-406.

Chvalovsky, V. [76], "Problems with Decision Tables," Communications of the ACM, 19(12), Dec. 1976, pp. 705-707.

Codasyl [82], "A Modern Appraisal of Decision Tables," Report of The Decision Table Task Group, ACM, New York, 322 pp., 1982.

CSA [70], CSA Standard Z243.1-1970 for Decision Tables, Canadian Standards Association, 1970.

Ganapathy, S., Rajaraman, V. [74], "Information Theory Applied to the Conversion of Decision Tables to Computer Programs," Communications of the ACM, 16(9), Sept. 1974, pp. 532-539.

Gildersleeve, T. [75], "The Dark Side Of Structured Programming," Datamation, 21(11), Nov. 1975, Pp. 178-180.

Johnson, R. [74], Logical Relations between Conditions in Decision Tables, Ph. D. Thesis, University Of London, 1974.

Johnson, R., King, P. [78], "Computer Assisted Decision Table Development," Computer Bulletin, Series 2(15), 1978, pp. 22-24.

King, P. [66], "Conversion of Decision Tables to Computer Programs by Rule Mask Techniques," Communications of the ACM, 9(11), Nov. 1966, pp. 796-801.

Lew, A. [78], "Optimal Conversion of Extended-Entry Decision Tables with General Cost Criteria," Communications of the ACM, 21(4), April 1978, pp. 269-279.

Maes, R. [78], "On the Representation of Program Structures by Decision Tables:  A Critical Assessment," The Computer Journal, 21(4), Nov. 1978, pp. 290-295.

Maes, R. [81], Bijdrage tot ten Kritische Herwaardering van de Beslissingstabellentechniek, Doctoraal Proefschrift, K.U.Leuven, Faculteit Der Toegepaste Wetenschappen, 1981, 397 pp.

Maes, R., Vanthienen, J., Verhelst, M. [81], "Procedural Decision Support Through The Use of Prodemo," Proc. Second Int. Conf. On Information Systems, Cambridge (Mass.), December 7-9, 1981, pp. 135-152.

Maes, R., Vanthienen, J., Verhelst, M. [82], "Practical Experiences with The Procedural Decision Modeling System," Proc. Joint Ifip Wg 8.3/Iiasa Working Conference on Processes And Tools for Decision Support, Laxenburg (Austria), July 19-21, 1982, pp. 139-154.

Martelli, A., Montanari, U. [78], "Optimizing Decision Trees Through Heuristically Guided Search," Communications of the ACM, 21(12), Dec. 1978, pp. 1025-1039.

McDaniel, H. [68], An Introduction to Decision Logic Tables, John Wiley & Sons, Inc., New York, 1968, 96 pp.

McDaniel, H. (Ed.) [70a], Applications of Decision Tables, A Reader, Brandon/Systems Press, Inc., Princeton, 1970, 226 pp.

McDaniel, H. [70b], Decision Table Software, A Handbook, Brandon/ Systems Press, Inc., Princeton, 1970, 84 pp.

Montalbano, M. [74], Decision Tables, Science Research Associates, Inc., Chicago, 1974, 191 pp.

Muthukrishnan, C., Rajaraman, V. [70], "On the Conversion of Decision Tables to Computer Programs," Communications of the ACM, 13(6), June 1970, pp. 247-251.

NCC [70], Decision Tables in Data Processing, A Report, National Computing Centre Limited, Manchester, 1970, 107 pp.

Papakonstantinou, G. [80], "A Recursive Algorithm for the Optimal Conversion of Decision Tables," Angewandte Informatik, 80(9), 1980, pp. 350-354.

Pollack, S. [65], "Conversion of Limited-Entry Decision Tables to Computer Programs," Communications of the ACM, 8(11), Nov. 1965, pp. 677-682.

Pollack, S., Hicks, H., Harrison, W. [71], Decision Tables:  Theory and Practice, John Wiley & Sons, Inc., New York, 1971, 179 pp.

Pooch, U. [74], "Translation Of Decision Tables," Computing Surveys, 6(2), June 1974, pp. 125-151.  Corrigendum: 6(4), Dec. 1974, P. 321.

Reinwald, L., Soland, R. [66], "Conversion of Limited-Entry Decision Tables to Optimal Computer Programs: Minimum Average Processing Time," Journal of the ACM, 13(3), July 1966, pp. 339-358.

Schumacher, H., Sevcik, K. [76], "The Synthetic Approach to Decision Table Conversion," Communications of the ACM, 19(6), June 1976, pp. 343-351.

Sethi, I., Chatterjee, B. [80], "Conversion of Decision Tables to Efficient Sequential Testing Procedures," Communications of the ACM, 23(5), May 1980, pp. 279-285.

Shwayder, K. [71], "Conversion of Limited-Entry Decision Tables to Computer Programs, A Proposed Modification to Pollack's Algorithm," Communications of the ACM, 14(2), Feb. 1971, pp. 69-73.

Shwayder, K. [74], "Extending the Information Theory Approach to Converting Limited-Entry Decision Tables to Computer Programs," Communications of the ACM, 17(9), Sept. 1974, pp. 532-537.

Smillie, K., Shave, M. [75], "Converting Decision Tables to Computer Programs," The Computer Journal, 18(2), May 1975, pp. 108-111.

Strunz, H. [73], "The Development of Decision Tables Via Parsing of Complex Decision Situations," Communications of the ACM, 16(6), June 1973, pp. 366-369.

Vanthienen, J. [85], "A Note On English For Decision Tables Considered Harmful and The Nested If-Then-Else," Sigplan Notices, 20(5), May 1985, pp. 45-47.

Verhelst, M. [69], "A Technique For Constructing Decision Tables," Iag Quarterly Journal (Later: Information & Management), 2(1), March 1969, pp. 27-36.

Verhelst, M. [72], "The Conversion of Limited-Entry Decision Tables to Optimal and Near-Optimal Flowcharts:  Two New Algorithms," Communications of the ACM, 15(11), Nov. 1972, pp. 974-980.

Verhelst, M. [80], De Praktijk van Beslissingstabellen, Kluwer, Deventer/Antwerpen, 1980, 175 pp.

# # #