Validation of interrelated fields

Question

We have a validation system which forces users to select from a valid set of values across a set of inter-related fields.

The user has to fill in the first value in the list, and whichever value they have selected determines which set of values they will be able to select from in the second field. Their choice of value in the second field limits the set of choices in the third. And so on.

All the interrelated fields are organised in a tree structure, i.e. there is one root field from which the user starts from, and there are various paths down the tree starting from the root, for example:

        Field1
       /      \
    Field2   Field7
      |        |
    Field3    etc
      |
    Field4
    /     \
 Field5   Field6

The way we have chosen to implement is using the following database model:

ID
Parent ID
Field Type
Delimited Chain Data


1,null,Field1,F1-1
2,   1,Field2,F1-1|F2-1
3,   1,Field2,F1-1|F2-2
4,   1,Field2,F1-1|F2-3
5,   1,Field2,F1-1|F2-4
6,   2,Field3,F1-1|F2-1|F3-1
7,   2,Field3,F1-1|F2-1|F3-2
8,   3,Field3,F1-1|F2-2|F3-1
9,   3,Field3,F1-1|F2-2|F3-3
etc

The relationship between the data values is many to many, e.g. multiple values in Field3 are related to multiple values in Field2.

What this structure lets you do is two things:

• Easily query for a set of values for a particular field, give the previously selected data above that field.
• Check that a given path in the tree contains valid values for all its fields

However, this system has grown. Some of these fields have thousands of possible values. There are around 30 fields in total. So, when you perm out all the possible sets of valid values across the tree, there are tens of millions of combinations. The system is beginning to creak at the seams and data maintenance of the sets of values has become difficult.

My questions are:

• Has anyone come across similar inter-related field validation problems? How did you solve it?
• Are there any products or open source libraries (preferably Java based) which help with similar problems containing such large volumes of combinations?
• Has anyone any suggestions on alternative implementation strategies?

Thanks.

Answer 1

Take a look at Rules Engines. They use the Rete Algorithm to speed up the time necessary to make millions of comparisons, using memory instead of CPU.

JBoss Drools would probably be worth a look.

Here's the quickest overview of the way you set up decision logic.

Answer 2

How about describing your rules in a PMML document and implement a predicate capable visitor at each node.

http://www.dmg.org/v4-0/TreeModel.html

PMML covers quite a few models, but the Tree Model may be the best fit for your needs.