Reducing the Arity of Recursive Predicates by Realigning Some Predicates

摘要

The work of [SN91] showed that the optimization which aims at reducing the arity of recursive predicates is more meaningful than that which aims at reducing the set of related fact. In this paper, we propose a simple but quite effective approach to optimize linear recursions in deductive databases by reducing the arity of recursive predicates by realigning some base predicates. A graph model, called IE-graph, is used to represent linear recursive definitions, and an equivalence-preserving graph transformation operation, called realigning, is newly defined on IE-graph. The paper shows that some variables can be transformed to isolated variables after realigning some base predicates, hence can be detached from the definition.