An optimal evaluation of Boolean expressions in an online query system

In this paper we consider the problem of retrieving reeords from a very large file, containing hundreds of thousands of records. Each record consists of a list of attributes and values. The selection of the subset of reeords from the file is in response to a Boolean expression which specifies a combination of desired values of certain attributes and values. The Boolean expression is communicated to the system by the user as a query, typed in on a low speed remote terminal. As a response to the query, the entire file has to be searched, and the Boolean expression is evaluated for each record. The method presented here improves the performance of such a system by speeding up the process of computing the truth value of a Boolean expression for an individual record. This is done by evaluating the expression based on the values of a subset of its components rather than the entire expression.