Decision Tables

Recently I wrote a filter that took a stream of messages as an input, and if
the messages matched a certain criteria, transformed them into something
else; otherwise, it let the messages pass through unchanged. Writing the
algorithm for determining whether a message matched the filter's criteria
was a bit of a challenge. It could have involved a long string of nested
if/else statements. This led me to consider alternatives, such as state
machines. What I wound up doing was setting the bits in an integer for each
field I'm interested in matching and using the integer as an index into a
function table. The function would then test the message to see if I have a
match.

That's a bit vague, so I'll try to give an example. Say we have messages
with four fields:

FirstName
LastName
Address
Country

What we'd like to do is this:

if(match(receivedMessage, comparisonMessage))
{
// We have a match.
}
else
{
// Messages do not match.
}

The thing is is that we may only be interested in matching certain fields.
For example, I may only be interested in filtering messages where the
LastName is Jones and the Country is Canada. So I'd like my match function
to compare the received message to my comparison message. If the LastName is
Jones and the Country is Canada, I'd like it to return true. There are four
fields, so there are 16 different combination of fields I could be
interested in matching, e.g. only the FirstName, FirstName and LastName,
FirstName and Address, and so on...

So what I did was to construct an index in which each bit (in this case,
only the first four) represent one of the fields. If I'm interested in
matching a field, I set the bit to 1; otherwise, 0. For example, if I'm only
interested in matching the LastName and the Country, I'd do this:

index = 1 << 1; // LastName
index |= 1 << 3; // Country

Later when I need to match a message, I'd do this:

comparisonMessage.LastName = "Jones";
comparisonMessage.Country = "Canada";

if(decisionTable[index](receivedMessage, comparisonMessage))
{
// We have a match.
}
else
{
// Messages do not match.
}

The functions in the decision table would look like this:

bool match0000(receivedMessage, comparisonMessage)
{
return true;
}

bool match0001(receivedMessage, comparisonMessage)
{
return receivedMessage.FirstName == comparisonMessage.FirstName;
}

bool match0010(receivedMessage, comparisonMessage)
{
return receivedMessage.LastName == comparisonMessage.LastName;
}

bool match0011(receivedMessage, comparisonMessage)
{
return match0001(receivedMessage, comparisonMessage) &&
match0010(receivedMessage, comparisonMessage);
}

And so on...

A couple of things. One, I'm not sure this is actually what is classically
thought of as a decision table, but it seems pretty close to me. Two, this
solution unfortunately doesn't scale. In my example, I need 16 match
functions for my decision table. This goes up exponentially with each new
condition. However, in the case where I applied this solution, I don't have
to worry about new conditions being added; it works like a charm. But I'm
wondering if there's a way to approach this without the combinatory
explosion.

I'm also wondering if I've over-engineered a solution. That's one of my
faults when approaching a problem. So I'd appreciate any thoughts or
insights.










.

Relevant Pages

  • Re: Decision Tables
    ... bool match0000(receivedMessage, comparisonMessage) ... encode arbitrarily complex expressions a newly created match function. ...
    (comp.programming)
  • Re: Decision Tables
    ... bool match0000(receivedMessage, comparisonMessage) ... insights. ... It doesn't scale like you said and it seems a lot of work creating the ...
    (comp.programming)