Database model for saving random boolean expressions

Question

I have expressions like this:

(cat OR cats OR kitten OR kitty) AND (dog OR dogs) NOT (pigeon OR firefly)

Anyone having idea how to make tables to save those?

Before I got request for usage of brackets, I limited usage of operators to avoid ambiguous situations. So only ANDs and NOTs or only ORs and saved those in this manner:

operators

id | name  
1  | AND  
2  | OR  
3  | NOT  

keywords

id | keyword  
1  | cat  
2  | dog  
3  | firefly  

expressions

id | operator | keywordId  
1  | 0        | 1   
1  | 1        | 2  
1  | 3        | 3  

which was: cat AND dog NOT firefly

But now, I'm really puzzled...

Answer 1

Saving them as strings or serialized data structures (a parse tree for example) is most likely the best solution unless you really need to modify parts of the expression in the database itself.

Answer 2

I'd store them as reverse Polish in text format with operators/operands by blanks, for your examples:

cat cats OR dog dogs OR AND
pigeon firefly OR NOT

This allows you to implement an boolean expression evaluator really easily and simply, and I presume is what you want to with them.

If you wanted to make it even easier to evaluate, I'd store bindings of object names to a small vocabulary (e.g., A-Z) and a similar vocabulary for AND, OR, NOT:

cat A cats B dog C dogs : DAB+CD+&
pigeon A firefly : AB+~

Then the basic expression evaluator only has to work on invidual characters and is really, really easy to code.