Horn Clause Transformation by Restrictor in Deductive Databases

概要

論文の詳細を見る
Several methods have been proposed to improve the performance of bottom-up evaluation by query transformation (or rule rewriting) in the deductive database field. One way to realize this improvement is to introduce new predicates, such as magic predicates, to be used as filters. This is considered one of the most promising ways to realize efficient query processing. Most algorithms in this category are formulated based on SLD semantics, and their fixpoint semantics is difficult to recognize. This paper proposes a method called Horn clause transformation by restrictor (HCT/R) based on declarative semantics, which is the common foundation of both SLD semantics and fixpoint semantics. HCT/R is formulated as an equivalent transformation that maps the least Herbrand model to a smaller model. It is most general in this category and can be considered as a formal framework of the methods in this category. Optimization of this transformation is also discussed and a semi-optimal algorithm is proposed.
1989-12-25