| Abstract: | An evaluation algorithm for Boolean expressions is efficient if it recognizes when particular conditions cannot affect the value of the result. Of special interest are efficient algorithms which do not expect the conditions to be evaluated in the order in which they appear in the expression. This is important for selective retrieval from a large data base, when the evaluation (retrieval) order depends on the data organization and not on the order in which the qualifiers appear in the query. Another aspect of data retrieval is that we may repeatedly change part (but not all) of the values of the variables, and wish to re-evaluate part of the expression. Algorithms are given for representing and efficiently evaluating Boolean expressions both for the sequential and random cases; for the latter, an algorithm for partial re-initialization is also given. |
