Completeness Results for Recursive Data Bases.

Tirza Hirst, David Harel: Completeness Results for Recursive Data Bases. PODS 1993: 244-252

@inproceedings{DBLP:conf/pods/HirstH93,
  author    = {Tirza Hirst and
               David Harel},
  title     = {Completeness Results for Recursive Data Bases},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {244-252},
  ee        = {http://doi.acm.org/10.1145/153850.153905, db/conf/pods/HirstH93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We consider infinite recursive (i.e., computable) relational data bases. Since the set of computable queries on such data bases is not closed under even simple relational operations, one must either make do with a very humble class of queries or considerably restrict the class of allowed data bases. We define two query languages, one for each of these possibilities, and prove their completeness. The first is the language of quantifier-free first-order logic, which is shown to be complete for the non-restricted case. The second is an appropriately modified version of Chandra and Harel's complete language QL, which is proved complete for the case of "highly symmetric" data bases, i.e., ones whose set of automorphisms is of finite index for each tuple-width. We also address the related notion of BP-completeness.

Copyright © 1993 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/...

BibTeX

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 763 KB]

Journal Version

Tirza Hirst, David Harel: Completeness Results for Recursive Data Bases. J. Comput. Syst. Sci. 52(3): 522-536(1996) BibTeX

References

[AV]: Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX
[B]: ...
[Be1]: ...
[Be2]: ...
[BG]: ...
[CH]: Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CK]: ...
[H]: David Harel: Hamiltonian Paths in Infinite Graphs. STOC 1991: 220-229 BibTeX
[HH]: ...
[NR]: ...
[P]: Jan Paredaens: On the Expressive Power of the Relational Algebra. Inf. Process. Lett. 7(2): 107-111(1978) BibTeX

Referenced by

Serge Abiteboul, Victor Vianu: Queries and Computation on the Web. ICDT 1997: 262-275
Catriel Beeri, Tova Milo, Paula Ta-Shma: On Genericity and Parametricity. PODS 1996: 104-116
Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]