ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
...
[10]
...
[11]
...
[12]
Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:54 2010 by Michael Ley (ley@uni-trier.de)