Need guidance towards evaluative boolean logic tree

Asked 2/12, 2009 at 5:58 Answered 5/12, 2009 at 14:16

Solved user-interface expression-trees boolean-logic decision-tree expression-evaluation

I can't seem to find a pointer in the right direction, I am not even sure what the terms are that I should be researching but countless hours of googling seem to be spinning me in circles, so hopefully the collective hive of intelligence of Stack Overflow can help.

The problem is this, I need a way to filter data in what I can only call a compound logic tree. Currently the system implements a simple AND filtering system. For example, lets say we have a dataset of people. You add a bunch of filters such that show all the people where (Sex = Female) AND (Age > 23) AND (Age < 30) AND ( Status = Single). Easy enough, iterate through each item, add to a valid items collection only if every condition is true.

The problem I'm encountering is how do I handle the user being able to build complex queries involved and's and or's? I'm thinking of something like a tree where each node represents and expression evaluating its children to true or false. A simplistic example would be - filter down to ((Sex == Male AND Age == 25) OR (Sex == Female AND Status == Single)) AND IQ > 120. Sorry I can't think of a better example at the moment. But how would you go about representing this type of expression tree, and evaluating the items in a collection against these filters. What are some references that would help? Hell, what are some damn Google searching that might lead into a positive direction?!

Thanks to anyone that can provide any help.

Here is an example of a compound query in tree form using a dataset of people

Query - Show me all people where sex is male and eyes are green or sex is female, eyes are blue, or status is single. In Paren form (Sex==Male && Eyes == Green) || ( Sex == Female && ( Eyes == Blue || Status == Single))

So In tree form im Thinking

o-Root Node
  - And - Sex = Male
     - And - Eyes = Blue
  - Or - Sex = Female
     - And Eyes = Blue
     - Or Status = Single

I believe the solution is to represent each node such in a data structure like

Node
{
   OpType - AND or OR
   ExpressionField - The field to evaluate
   ExpressionOp -   =, !=, >, >=, <, <=
   ExpressionValue - the value to compare the field's value against

   Function Evaluate() - returns a bool
}

So for a given node, evaluate the chilren, if you are an AND node, then return true if your expression results in true and all your AND children evaluate to true or any OR child evaluates to true and recurse up.

Seems to satisfy every conceptual condition I can throw at it, but we will since once I implement it. I will post the real code up later when its working and pictures to help describe this problem better for others.

Rolon answered 2/12, 2009 at 5:58 Comment(6)

Suggest you clarify what form your data is in : SQL db ? I assume the tag "as3" refers to ActionScript 3 : if so, are you really looking for C# or AS3 specific techniques, or just for "theory" ? – Syndesmosis 2/12, 2009 at 8:25

The data is in memory, although technically the implementation is both in flash and in silverlight, I am much more interested in understanding the general solution than a specific implementation. The crux of the problem involves presenting a UI to the user that allows them to dynamically build a complex query to filter the dataset. I need a solid data structure to represent the query. So far I have the following for a node - Type - And or Or - Field - the field of the dataset this node is targeting - Operation - =, !=, >, < <=, >= - Value - the value to apply the operation against – Rolon 2/12, 2009 at 17:51

Clearer explanation ! I suggest you clarify if the data structure is in C#/SilverLight : if so, I'd assume you'll use Linq to do the "heavy lifting." If you are already at a high level with Linq, using lambdas, anonymous methods, etc., that's one thing : if you are not, you can get good advice on SO (if you ask for it) on Linq study resources (imho Jon Skeet's "C# in Depth" is the best C# book on the planet with superb coverage of Linq). This may be irrelevant to your idea, but you can use a dictionary with "whatever" as keys and executable (anonymous) methods as Values. – BillW – Syndesmosis 3/12, 2009 at 10:42

The answers and comments here seem very relevant to your question : #1703840 – Syndesmosis 3/12, 2009 at 10:47

It would be interesting to know if, at this point, you have any "constraints" on the type of UI you want to see : for example, would you "rule out" a wizard that walks you through a logical sequence of steps that effectively isolates the selections of fields of interest from the data, that then, for each field queried, present you with an interface appropriate to visually (as much as possible) selecting the parameters that for that field's query ? Have you pretty much decied a treeview is going to be your major ui form ? – Syndesmosis 3/12, 2009 at 16:35

BillW - Thanks for your assistance, that other post is quite helpful and is right up this ally. I think I have found a great solution on my own that is this type of mini wizard in tree form that switches between a flat simple list for and conditions, but allows the user to add or conditions as well in which the list gets represented in the tree form. More on that later, thanks for the help! – Rolon 3/12, 2009 at 19:9

Your parsing of the expression ((Sex == Male AND Age == 25) OR (Sex == Female AND Status == Single)) AND IQ > 120 looks odd. I would parse it as:

* And
    * Or
        * And
            * ==
                * Sex
                * Male
            * ==
                * Eyes
                * Blue
        * And
            * ==
                * Sex
                * Female
            * ==
                * Status
                * Single
    * >
        * IQ
        * 120

The tree type would be :

Node
{
    bool evaluate ()
}

AndNode : Node
{
    Node left
    Node right

    bool evaluate ()
    {
        return left.evaluate () && right.evaluate ()
    }
}

// OrNode is similar

EqualsNode : Node
{
    Field field
    Value value

    bool evaluate ()
    {
        return field.value () == value
    }
}

// Likewise for <, >, etc

Shilashilha answered 4/12, 2009 at 12:40 Comment(2)

I see what your doing, but I think the inner expression ( value - op - field such such as IQ > 120) can always be evaluated to a simple bool, so factoring it down you end up with a bunch of bool inside the nodes to represent the result of that nodes expression, and a bunch of And & Or's at the nodes representing how that bool gets absorbed into the result tree. Marking as correct as for right now, I believe this is the best answer. – Rolon 7/12, 2009 at 19:5

Not sure i understand. Strictly evaluate() should take as an argument some sort of context object (maybe a row of a table), which would yield a value for the Field (which might be different for each row). – Shilashilha 7/12, 2009 at 19:41

These kinds of queries are often presented as an ORed array of ANDed clauses. That is, a tabular format in which you read across multiple conditions ANDed together, and then read down to OR them. That leads to some repetition of conditions, but is easy for users to read, write, and understand. Your sample ((Sex == Male AND Age == 25) OR (Sex == Female AND Status == Single)) AND IQ > 120 would look like

Sex == Male   & Age == 25        & IQ > 120 
Sex == Female & Status == Single & IQ > 120

Drops answered 4/12, 2009 at 17:55 Comment(0)

You might want to Google for terms such as 'predicate calculus' and 'conjunctive normal form'.

Vange answered 5/12, 2009 at 14:16 Comment(0)

I have to say that this is why database engines are built. You can do all that you require with set logic and you may even arrive at the result you are looking for, but theses are standard problems solved by databases and SQL. You can also look at linq for a in code solution.

Bernie answered 2/12, 2009 at 6:26 Comment(4)

I think he means on how he can dynamically build this expression within sql. – Drivein 2/12, 2009 at 7:17

Yes, this is about presenting a solid UI to the user that allows them to easily build a query. I think I have figured it out with a fairly simple tree structure and a few simple recursive functions, bit I know others have studied this problem and would like to learn their thoughts and experiments, but as of yet have not figured out how to find the others. Also, in this case all the data is in memory. – Rolon 2/12, 2009 at 17:46

An option would be to take the Set of criteria and allow the user to create a set of and criteria and Store the Set. So Set 1 would be Female IQ > 120 Then allow users to specify Multiple sets for the ors. This could be done graphically in an interesting fashion allowing users to drag and drop sets. Perhaps you could place sets inside of set to create a intersection or a join of sets. Just an Idea Sorry I didn't get the crux of your question the first go around. – Bernie 2/12, 2009 at 18:48

Thanks for the help, I believe I have come up with a good solution to this, and will post more later. – Rolon 2/12, 2009 at 23:43

Sounds like you need to create a user interface that allows the creation of a simple parse tree. When the presses GO you can then walk the tree and create a LINQ expression tree from that user interface structure. Execute the LINQ query and then process the results as needed. I would therefore recommend you read up on LINQ expression trees.

Klepht answered 4/12, 2009 at 4:13 Comment(0)

Recommended topics

Hot tags