Data Independent Recursion in Deductive Databases.

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279

@inproceedings{DBLP:conf/pods/Naughton86,
  author    = {Jeffrey F. Naughton},
  title     = {Data Independent Recursion in Deductive Databases},
  booktitle = {Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 24-26, 1986, Cambridge, Massachusetts},
  publisher = {ACM},
  year      = {1986},
  isbn      = {0-89791-179-2},
  pages     = {267-279},
  ee        = {http://doi.acm.org/10.1145/6012.15420, db/conf/pods/Naughton86.html},
  crossref  = {DBLP:conf/pods/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We give a decision procedure that determines if a recursively defined predicate in a deductive database system can instead be defined by a fixed, finite set of conjunctions of base predicates. We consider two types of initialization of the recursively defined predicate: arbitrary initialization, and initialization by a given nonrecursive rule. This extends earlier work by Minker and Nicolas [7], and by Ioannidis [6] , and is related to bounded tableau results by Sagiv [12]. Even if there is no fixed finite set equivalent to the recursive definition, our procedure can be used to improve the efficiency of the compiled evaluation algorithms for recursive queries proposed in Henschen and Naqvi [5] and in Bancilhon et al. [3].

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 24-26, 1986, Cambridge, Massachusetts. ACM 1986, ISBN 0-89791-179-2
Contents

Online Edition: ACM Digital Library

Journal Version

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989)

References

[1]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)
[2]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[3]: François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15
[4]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[5]: Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984)
[6]: ...
[7]: Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983)
[8]: Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989)
[9]: ...
[10]: ...
[11]: ...
[12]: Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
[13]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985)