Space optimization in deductive databases

Reviewer: Robert J. Tufts

Space optimization can often be critical for string matching situations that use deductive databases. Examples include comparisons of DNA strings, change detection between digital images, and sequence querying in stock market applications to create summary statistics. Each of these processes, usually performed as bottom-up evaluations, can hog storage and I/O processing if the generated facts used for evaluation are all stored until the end of the process. There has been some earlier research into practical methods for reducing the number of facts that are saved and the number of repeated occurrences of the same derivation of facts. One of these techniques, the sliding window tabulation technique [1], has proven effective, but is applicable to a restricted class of programs. The authors have expanded on sliding window tabulation by defining a general framework for space optimization methods and creating a series of techniques that apply to a wider class of programs. They propose implementing these techniques during the compilation of each deductive database query. The query program would be evaluated to see which techniques are best. The chosen techniques would then be included in the compiled program and executed during query runtime to discard facts and eliminate duplicate fact derivation. The proposed techniques also ensure correctness, nonredundancy of derivation, and reduction in the time a fact is retained. The authors' purpose in writing this paper was to provide a broader set of techniques for reducing the space required during bottom-up evaluation of logic programs. The theorems and techniques provided admirably satisfy this purpose and carry the theory into practical applications for database queries. Some of the discussion is a bit tedious, but it is needed to prove that the techniques satisfy the need for soundness and completeness, nonredundancy, and reduction of fact lifetimes. One of the most enjoyable aspects of the paper is its readability. The authors do a good job of providing background information, deriving proofs of theorems, and showing examples where the techniques are applicable. The references, however, could have been improved. Eleven of the 22 references are to works by the same authors, either collaboratively or separately, and only a few of the remaining references cover space optimization in deductive databases. The paper is an excellent look into practical aspects of storage optimization for bottom-up query problems. As such, it is important to vendors of relational query packages, especially if they are focusing on bottom-up or recursive evaluations of fact databases. I also recommend the paper for those doing additional research, as suggested by the authors, into evaluation primitives for easily implementing the space optimization techniques.