How to combine and optimize a predicate, generally?

Question

I'm doing some work on a Complex Event Processing system. It supports filtering of sets of records based on members of those records, using a query language. The language supports logical, arithmetic and user-defined operators over arbitrary members.

Here's an example of a supported query:

( MemberA > MemberB ) && 
( @in MemberC { "str1", "str2" } ) &&
( com.foo.Bar.myPred( MemberD, MemberE ) )

My problem is that I want to combine queries into one super query, and then I want to optimize that super query to eliminate redundancies, tautologies and contradictions. e.g. I want to take

A > 0

and combine it with

A > 1

which is quite easy:

A > 0 || A > 1

but then I want to optimize it so that it reduces to

A > 0

If there are any URLs or books that discuss this general topic, I'd appreciate knowing about them.

Answer 1

Books? I think there's a few; and most likely you should look up for articles in this area.

What you may look at are SMT solvers that can work with your domain of queries. You feed them with the mathematicalized definition of your expression language, state axioms of the relations you support. Then they can, for instance, reason if (yes, two equal conjunctions) whether one predicate implies another is a tautology.

Note that the automated solutions to this task are vague and sometimes are beyond the theoretical capabilities of Turing machines (i.e. computer). You won't have an only and right solution to your problem.