Browse Prior Art Database

Method for Evaluation a Boolean Expression

IP.com Disclosure Number: IPCOM000113530D
Original Publication Date: 1994-Sep-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 75K

Publishing Venue

IBM

Related People

Ames, GL: AUTHOR [+2]

Abstract

One usage of a Boolean expression is to select records from a file (data base) based on selection criteria specified by the user as a Boolean expression.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Method for Evaluation a Boolean Expression

      One usage of a Boolean expression is to select records from a
file (data base) based on selection criteria specified by the user as
a Boolean expression.

For example, if a user specifies
 field_a > 10 & (field_b < 20 | field_c = 'Az')
& ^field_d >= 30 | field_e <>
 then each record in an input file could be evaluated to see if this
expression is true for the record.

This method would be applicable when
  o  one expression is evaluated multiple times
  o  the expression uses the Boolean operators (AND, OR, and NOT),
     plus parentheses.

      This solution converts the Boolean expression into a table
(called the "operand list" in the pseudo-code below).  This table
consists of
  o  the operand (this may be a pointer to the operand; also, the
     operand type or length fields may be used)
  o  a pointer (or index) to the next operand to evaluate if this
     operand is true for the specific input, and
  o  a pointer (or index) to the next operand to evaluate if this
     operand is false for the specific input.

This table is "executed" by starting at the first entry in the table.
If the first operand evaluates as True for the current input record,
the "true" pointer is used to find the next operand to evaluate.  If
the first operand evaluates as False for the current input record,
the "false" pointer is used to find the next operand to evaluate.
This process continues until the "pointer" is either TRUE or FALSE,
indicating the whole Boolean expression evaluates as true or false
for the current input record.

For example, the table for the above example is:
  Index    Operand         True Index  False Index
    1      field_a > 10         2           5
    2      field_b < 20         4           3
    3      field_c = 'Az'       4           5
    4      field_d >= 30        5          TRUE
    5      field_e <> 40       TRUE        FALSE

      This table is executed as follows:  Starting with index 1,
evaluate the current input record's field_a.  If field_a is greater
than 10, evaluate the operand at index 2.  If field_a is not greater
than 10, evaluate the operand at index 5.

      Note that this method allows the evaluation process to stop as
soon as the whole expression is known to be true or false for the
current input record, rather than evaluating the whole expression.
For example, if the current record has the following values
        field_a       8
        fiel...