On Purely Exponential Logic Queries

The recursive nature of logic programs has long been the subject of optimization techniques [2, 8]. Recently, the database community has taken interest in extending the expressive power of relational algebra by augmenting it with function-free Horn style logic queries. This extension has led to various optimization techniques [2, 6, 8]. It seems, almost invariably, these techniques are most efficient in the processing of linear recursive queries. Moreover, as the equivalence of nonlinear rules to linear rules in general is undecidable [3, 9], the best one can hope is to rewrite some nonlinear rules as linear rules. For this reason, there is a genuine interest in identifying those classes of non-linear recursive queries which can be rewritten as linear queries. Among these classes are binary chained purely exponential queries [5] and doubly recursive queries [11]