Query optimization for Deductive Databases

A systematic, efficient compilation method for query evaluation of Deductive Databases (DeDB) is proposed in this paper. In order to eliminate redundancy and to minimize the potentially relevant facts, which are two key issues to the efficiency of a DeDB, the compilation process is decomposed into two phases. The first is the pre-compilation phase, which is responsible for the minimization of the potentially relevant facts. The second, which we refer to as the general compilation phase, is responsible for the elimination of redundancy. The rule/goal graph devised by J. D. Ullman is appropriately extended and used as a uniform formalism. Two general algorithms corresponding to the two phases respectively are described intuitively and formally.