Data Model for Boolean Expressions?

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 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.

You are making a very good point here: one should not be using option 1 just because it can be used; there must be certain requirements in place to justify option 1. If such requirements are not imminent, I'd probably start from option 2. – Yarik Nov 15 '08 at 19:46.

An expression is a treelike structure. So you need a way to present the tree in a table. You can for example use the fields: ID TypeExpression (and, or etc...) FirstChildID SecondChildID In this case, you have the following types: AND, Children point to other expression.

OR, Children point to other expression. Equal, Children point to other expression. Literal, FirstChild points to an entry in a literal table.

VariableLookup, FirstChild points to an entry in a varable table. But I think there are better ways to organise expression. I once made a simple expression evaluator that accepts a string and produces a numeric result.

This is going to be difficult to represent relationally, because by its nature it is both hierarchical and polymorphic (the leaves of your tree can be either variables or constants).

This type of expression is most usually expressed as a tree (a hierarchy), which are notoriously annoying to query in SQL. We'll assume that a and be are numeric for the moment and that literals ('1', '2') are distinguished from variables. Table Nodes id type (Variable|Literal) name (nullable for literal) value Table Operators id name (=, AND, OR, NOT) leftNodeId rightNodeId This structure is very flexible, but querying it to retrieve a complex expression is going to be "fun" (read that "challenging").

And you still have to parse the structure to begin with and evaluate the expression after it has been reconstructed.

The traditional way to model Boolean functions is to use Binary Decision Diagrams, especially Reduced Order Binary Decision Diagrams. It's possible you can find an extension for your DBMS that provides good support for the concept. UPDATE: Alternately, if you don't need to query on the Boolean logic, you could use a BDD library and just serialize the BDD into a BLOB or equivalent.It beats using a varchar field because the BDD library would ensure the data was valid.

I would store the expression in polish form, in a varchar/text column. An expression in polish form (operand before operands, no brackets) is much easier to parse with a recursive function (or a stack of course). A = 1 AND (b = 1 OR be = 2) in polish form shows like this: AND = a 1 OR = be 1 = be 2.

Adding to @Gamechat answer I think it should be like this ID TypeExpression (and, or etc...) FirstChildID --This can be a leaf node or a pointer to another row in same table SecondChildID --This can be a leaf node or a pointer to another row in same table isFirstChildLeaf isSecondChildLeaf.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.