I started the dialogue addressing this question in two recent blog posts:
Filter Brainteaser Part I
Filter Brainteaser Part II

In part II, I presented an example of a real-life database filter that would seem to be impossible to build in TrackVia, which is limited to conditions that have only one level of grouping (see the illustrations in the prior post). The filter had to do with a mailing list for updates about a train station:

opted-in AND (interested-in-this-station OR (close-to-tracks AND (zip=X OR zip=Y OR zip=Z)))

The supposedly impossible filter was reworked into a logically equivalent version that was TrackVia friendly:

opt-in AND (interested-in-this-station OR close-to-tracks) AND (interested-in-station OR zip=X OR zip=Y OR zip=Z)

In this post I’ll answer the question: can any filter be reworked to conform to TrackVia’s limitations? Or are there some filters that are so complex that TrackVia can’t represent them?

The train tracks example asserts the following general equivalence:

A and (B or (C and (D or E or F))) --> A and (B or C) and (B or D or E or F)  Eqn. (1)

Here the arrow (-->) means “is equivalent to,” and the expressions on both sides of it should be evaluated from the inside out – that is, the inner-most parentheses should be evaluated first.

Equation (1) is true because of the following properties of the AND and OR operations:

 A and (B or C) --> (A and B) or (A and C)   Eqn. (2)
 A or (B and C) --> (A or B) and (A or C)   Eqn. (3)

In mathematics, we say that the AND and OR operations are distributive over each other. (We call it that because, in Eqn. (2) for example, we can distribute the “A and” part across the “(B or C)” part.) These two properties give us a tool for transforming logical conditions from a form that’s not TrackVia friendly, like the left-hand side of (1), to a form that is, like the right-hand side of (1).

The question is whether any condition can be similarly transformed. Consider the most general two-layer, or doubly-grouped, condition that uses AND as its outer glue:

 [(A and B) or (C and D)] and [(E and F) or (G and H)]  Cond. (4)

Using the two distributive properties above, we can rework this into an equivalent one-layer (singly-grouped) condition that has AND as the outer glue:

 (A or C) and (A or D) and (B or C) and (B or D) and
 (E or G) and (E or H) and (F or G) and (F or H)   Cond. (5)

We can also rework it into a one-layer condition with OR as the outer glue:

 (A and B and E and F) or (A and B and G and H) or
 (C and D and E and F) or (C and D and G and H)  Cond. (6)

How do we know that conditions 4, 5, and 6 are all equivalent? One way is to use the properties (2) and (3) repeatedly to distribute and regroup the parts. This is a lot of fun for the crowd that loved algebra in high school. Another way is to prove it by brute force, by evaluating each statement for every possible combination of true/false values of A through H. This appeals to those of us who build robust business software for a living, and who don’t trust ourselves not to make mistakes. The brute force approach is easier than it sounds: Microsoft Excel can, with a few tricks, quickly generate all 1,024 true/false combinations, and compare statements 4, 5, and 6. The resulting “truth table” clearly shows the equivalence of the different versions (click here to see the spreadsheet).

For the sake of completeness, we should also show that the most general two-layer condition that uses OR as the outer glue:

 [(A or B) and (C or D)] or [(E or F) and (G or H)]   Stmt. (7)

can be transformed into a one-layer condition with OR as the outer glue:

 (A and C) or (A and D) or (B and C) or (B and D) or
 (E and G) or (E and H) or (F and G) or (F and H)   Stmt. (8)

and also into a one-layer condition with AND as the outer glue:

 (A or B or E or F) and (A or B or G or H) and
 (C or D or E or F) and (C or D or G or H)    Stmt. (9)

Again, 7, 8, and 9 can be shown to be equivalent using either algebra or Excel.

What’s the point? All of the above shows that any two-layer condition (and the prototypes 4 and 7 are in fact representative of all possible two-layer conditions – although this I’ll leave as an exercise for what few readers I have left) can be transformed into a TrackVia-safe one-layer condition, with a choice of outer glue.

By extension, any three-layer condition can also be transformed into a one-layer condition: first by removing a layer (going from three to two), then removing another layer. And so on for conditions with arbitrary numbers of nested levels.

So the answer to our brain teaser is: Yes, any condition can be represented in TrackVia’s filter tool. And No, there is no filter too complex for TrackVia’s single-layer mechanism to represent.

Phew! I’m glad we went through that.