Boolean Chart Redesign

[David Marshall]

On 7/19/10 6:42 PM, "Bernd Groh" <bgroh at redhat.com> wrote:


>>   
> 
> Charts inside charts? To be honest, I'd much prefer it if we did away
> with this entire new chart thing. If you allow the use of parentheses,
> and you apply logical precedence to your operators NOT, AND and OR, you
> don't need any new charts, neither AND nor OR, as you'll be able to
> express everything within a single chart. I'd much rather formulate the
> entire query within a single chart, than using multiple charts in
> multiple dimensions and having to consider nesting charts within charts.
> But maybe that's just me? As to everything above the boolean charts, I
> think the entire logic of the advanced search page implies AND with
> respect to each of the sub-components. This should still apply. Whatever
> is above the boolean charts, using the current logic, AND the entirety
> of the one boolean chart. And in my opinion, there should only be one
> boolean chart, and logic rules should apply.
> 

The predicate of an SQL query is a tree[*].  Boolean charts are an
expression of trees that can be composed in the advanced search UI in a way
that is easy to write in a URL.  As a result, as Max has pointed out, there
are some trees that cannot be expressed with Boolean charts as they are now
implemented.

If we want arbitrarily complex queries, we must determine how to express the
resulting trees in a URL.

If we choose to express the queries with parentheses and such, then we're
not really using the chart concept anymore - we're just passing a stream of
tokens that Search.pm will evaluate.  That's OK, actually - no one should
really care how the tree is represented in a URL.

[*] A brief discussion of predicate trees

The simplest tree is just an atomic predicate, such as "product = 'foo'" or
"bug_status IN ('NEW', 'REOPENED')".  Such a tree has only its root node,
the atomic predicate.

The next simplest is a negated atomic predicate.  This tree is a NOT node
with its one atomic child.

Next, of course, comes AND/OR nodes, with two or more subtrees.

These trees have some interesting properties, but I will not bore you with
tedious detail.

I currently use these trees for putting Boolean charts into a data structure
and then express them in SQL.  I have interesting ideas about evaluating the
trees with methods other than the database, caching the results of the
evaluation of some nodes, and so on.