Technical Report CS0018

TR#:CS0018
Class:CS
Title: ON EVALUATING BOOLEAN EXPRESSIONS
Authors: E. Gudes and A. Reiter
PDFCS0018.pdf
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 o~er 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 reevaluate 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 reinitialization is also given.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1972/CS/CS0018), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1972
To the main CS technical reports page

Computer science department, Technion
admin