Data Model for Boolean Expressions


Do you know a way to organize boolean expressions in a database while allowing infinite nesting of the expressions?


a = 1 AND (b = 1 OR b = 2)

The expression as a whole shouldn't be stored as varchar to preserve data integrity.

Best Solution

Option 1 would be to use a nested table (a tree with id / parent_id structure), like Gamecat suggested. This is relatively expensive to do, and requires issuing SQL queries repetitively to build the equivalent of a single nested expression.

Option 2 would be to use a serialized object and store it into a varchar column. For example, JSON would be a good choice. It is not white-space sensitive, can be created and parsed in a vast number of languages, and it retains data integrity.

As soon as you have parsed your expression string into a tree object in memory, you can serialize it and store it. If there was no need to manipulate the expression on the database level, I guess I would go that route.

Related Question