On the Equivalence of a Class of Purely Exponential Logic Queries to Linear Queries
Document Type
Article
Publication Date
1989
Publication Title
Journal of Information Processing
Volume
12
Issue
3
First page number:
280
Last page number:
285
Abstract
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].
Disciplines
Electrical and Computer Engineering | Engineering
Language
English
Permissions
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.
Repository Citation
Taghva, K.,
Wu, T.
(1989).
On the Equivalence of a Class of Purely Exponential Logic Queries to Linear Queries.
Journal of Information Processing, 12(3),
280-285.