On the Equivalence of a Class of Purely Exponential Logic Queries to Linear Queries

Document Type



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].


Electrical and Computer Engineering | Engineering


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.