On the First-Order Expressibility of Recursive Queries.

@inproceedings{DBLP:conf/pods/Cosmadakis89,
  author    = {Stavros S. Cosmadakis},
  title     = {On the First-Order Expressibility of Recursive Queries},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {311-323},
  ee        = {http://doi.acm.org/10.1145/73721.73752, db/conf/pods/Cosmadakis89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1989 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.

• 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/...

• 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

Online Edition: ACM Digital Library

References

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[BR86]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[BKBR87]

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX

[BH79]

...

[Ch81]

Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX

[CH80]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[CH85]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[CM77]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[ChK73]

...

[CGKV88]

Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490 BibTeX

[CK86]

Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX

[Fa75]

...

[Fr54]

...

[Ga81]

...

[GMSV87]

Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX

[GV85]

...

[GM78]

...

[HN84]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[Im81]

Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. J. Comput. Syst. Sci. 22(3): 384-406(1981) BibTeX

[Im86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Io85]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX

[Ka86]

...

[Ko87]

...

[MUV84]

David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX

[MW88]

David Maier, David Scott Warren: Computing with Logic: Logic Programming with Prolog. Benjamin/Cummings 1988, ISBN 0-8053-6681-4
BibTeX

[Mo74]

...

[Na86]

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

[NS87]

Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236 BibTeX

[Sa85]

Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180 BibTeX

[Ul85]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[Va82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[Va88]

Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 BibTeX

Referenced by

1. Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116