CODEWITHSUNDEEP
javasolrlucenelogicboolean-logic
Ivan
Ivan

Reputation: 980

Lucene: converting boolean queries with ORs to ANDs only

I need to convert a boolean query with ANDs, ORs and NOTs to ANDs and NOTs only. All my ORs need to be converted to ANDs, obviously maintaining the original meaning.

For example:

a AND b AND (c OR d OR e)

Should be converted to several separated queries:

a AND b AND c
a AND b AND d
a AND b AND e

Which is has the same logic result, but it isn't using ORs. I've tried a lot of different approaches but no real solution yet. I know I could use some De Morgan's laws maybe, but haven't found a solution yet.

It's important to notice that I need to convert ANY kind of query, not only the one on my example. I have to really cover it all. As other examples (comma meaning another query):

a OR b > a, b
a AND (b OR c) > a AND b, a AND c
a OR (b AND (c OR d)) > a, b AND c, b AND d
...

Thanks!

EDIT: more clear examples:

lucene AND (solr OR hadoop) > lucene AND solr, lucene AND hadoop
stackoverflow AND (java OR lucene) -solr > stackoverflow AND java -solr, stackoverflow AND lucene -solr

Upvotes: 0

Views: 1314

Answers (2)

MattClarke
MattClarke

Reputation: 1647

Sounds like you need to convert the search expression to disjunctive normal form. Then each term of the disjunction can be used as a separate search and the search results combined.

Try googling "convert to disjunctive normal form" for processes and examples.

Upvotes: 1

mduf
mduf

Reputation: 69

Whenever you encounter an 

E = a OR b

then you can convert OR operation to an AND of NOTs

E = NOT NOT E 
E = NOT NOT (a OR b)
E = NOT (NOT a AND NOT b)

So you're example would be converted as below:

E = a AND b AND (c OR d OR e) 
E = a AND b AND NOT NOT (c OR d OR e) 
E = a AND b AND NOT (NOT c AND NOT d AND NOT e)

Upvotes: 0

Related Questions