There is a striking similarity between decision tables and databases.  The way in which we model and represent sets of rules can benefit from the insights obtained in database design.  Good decision table design and good database design are subject to similar concerns, such as consistency, non-redundancy, normalization, etc.

Decision tables and relational tables

The decision table contains a set of rules (expressed as rows or columns) indicating which action(s) should be applied for which combination of condition values.  By analogy with functional dependencies in relational database design, the relationship between conditions and actions (or between conditions) in decision tables can be expressed as implications.  A more extensive treatment of this similarity between decision tables and databases and a number of interesting consequences (functional dependencies, primary key, normalization forms, factoring) can already be found in [1], [2], and [3].

The decision table, being a set of implications, can be described in terms of functional dependencies:

Given a decision table with conditions and actions, a set of actions is functionally dependent on a set of conditions if every combination of condition values corresponds to (one and) only one configuration of action values.

Conditions as key

This is the most important criterion when designing decision tables:  are columns mutually exclusive (single hit versus multiple hit)?  In a complete single-hit table, each possible combination of conditions can be found in exactly one (one and only one) row (or column).  If the rows are not exclusive, at least one combination of conditions is present in more than one row, which may lead to inconsistency.  If a combination of conditions is missing, then the table is incomplete.

Figure 1 indicates a decision table that is complete and consistent.  Condition combinations do not overlap, and every combination of condition values is present.

Figure 1.  A complete and consistent decision table

It is intuitively clear that this decision table and a relational table are very similar.  But whereas the database table contains data, the decision table contains rules — rules as data.

The conditions are the key attributes and the actions the non-key attributes.  Possible condition values are the key domains, and action values are the non-key domains.  Condition and action entries correspond to attribute values.  Every rule is an n-tuple, and the number of rules of the expanded decision table is the cardinality of the relation.

Because conditions are the key attributes, and the key should be unique, condition combinations should be exclusive.

The whole key, and nothing but the key^[4] 

But there is more to it.  It is clear in Figure 1 that the Discount action is only dependent on CustomerLocation.  Whatever the TypeOfOrder is, the result is the same.  So the discount is only dependent on part of the key, not the whole key.  The TypeOfOrder condition is therefore not necessary and can be omitted, as can be seen from the contracted decision table (Figure 2).

Figure 2. The contracted decision table

Normalization and Factoring of Decision Tables

Although there are major differences between decision table knowledge and database dependencies, the analogy is striking, such that the normalization rules of database design^[5] provide an excellent guideline to evaluate the design and decomposition of decision tables.  Both normalization of relations and of decision tables have as a primary goal to avoid redundancy and to correct anomalies.  In addition, the normalization of decision tables simplifies decision tables and increases their readability.

Normalization rules for decision tables require that actions are fully dependent on all the conditions (2^nd normal form) and that actions are non-transitively dependent on the conditions (3^rd normal form).  Transitive dependencies have to do with relations between conditions.

These rules can then be used to improve the design and factoring of decision tables.

An Example

Figure 3.  Order Policy

If we examine the table in Figure 3, it can be seen that the value for Discount depends on TypeOfOrder and KnownCustomer, but there is no difference between the CustomerLocations.  So CustomerLocation is not part of the key.

The same holds for ShipmentSurplus.  The surplus is only applicable to non-US Customers, so it is only dependent on CustomerLocation.

Because the sets of conditions for the two actions do not overlap, the decision table of Figure 3 could be simplified into the two tables of Figure 4 and Figure 5.

Figure 4.  Discount policy

Figure 5.  Surplus policy

References

[1]  J. Vanthienen and M. Snoeck, "Knowledge Factoring Using Normalization Theory," International Symposium on the Management of Industrial and Corporate Knowledge (ISMICK'93), Compiègne, FR, (October 27–28, 1993), pp. 97–106.  

[2]  J. Vanthienen and G. Wets, "Integration of the Decision Table Formalism with a Relational Database Environment," Information Systems, Vol. 20, No. 7 (1995), pp. 595–616.  

[3]  J. Vanthienen and J. Wijsen, "On the Decomposition of Tabular Knowledge Systems," New Review of Applied Expert Systems, (1996), pp. 77–89.  

[4]  W. Kent, "A Simple Guide to Five Normal Forms in Relational Database Theory," Communications of the ACM, Vol. 26, No. 2 (Feb. 1983), pp. 120–125.  Online at :  http://www.bkent.net/Doc/simple5.htm   

[5]  C.J. Date, An Introduction to Database Systems, 8th ed., Pearson/Addison Wesley, 2004.   

# # #