Finite Queries do not Have Effective Syntax.

@inproceedings{DBLP:conf/pods/StoloboushkinT95,
  author    = {Alexei P. Stolboushkin and
               Michael A. Taitslin},
  title     = {Finite Queries do not Have Effective Syntax},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {277-285},
  ee        = {http://doi.acm.org/10.1145/212433.212477, db/conf/pods/StoloboushkinT95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A relational query is called finite, or sometimes safe, iff it yields a finite answer in every database state.

The set of finite queries of relational calculus is known to be unsolvable. However, in many cases it is possible to impose syntactical restrictions on the class of queries that guarantee finiteness and do not reduce the expressive power of the calculus.

We show that unfortunately this is not always the case, as we construct a recursive domain with decidable theory where any solvable (or enumerable, for that matter) subclass of queries either contains an infinite query, or misses a finite one.

Using the same example, we further show undecidability of the problem of state-finiteness, which is, given a query and a database state, to decide upon finiteness of the query in this state.

This settles two long-standing open problems in the theory of relational databases.

Copyright © 1995 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

[AGSS86]

...

[AH91]

Arnon Avron, Yoram Hirshfeld: On First Order Database Query Languages. LICS 1991: 226-231 BibTeX

[Cod70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[Cod72]

...

[Di69]

Robert A. Di Paola: The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. J. ACM 16(2): 324-327(1969) BibTeX

[ELTT65]

...

[End72]

...

[Hir91]

Yoram Hirshfeld: Safe Queries in Relational Databases with Functions. CSL 1991: 173-183 BibTeX

[Kif88]

Michael Kifer: On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report). JCDKB 1988: 405-415 BibTeX

[KKR90]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX

[Rab77]

...

[Ull82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Ull88]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[Ull89]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

Referenced by

1. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
2. Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27