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

Finitely Representable Databases.

Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300
@inproceedings{DBLP:conf/pods/GrumbachS94,
  author    = {St{\'e}phane Grumbach and
               Jianwen Su},
  title     = {Finitely Representable Databases},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {289-300},
  ee        = {http://doi.acm.org/10.1145/182591.182654, db/conf/pods/pods94-289.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We study classes of infinite but finitely representable databases based on constraints, motivated by new database applications such as geographical databases. The mathematical framework is based on classical decidable first-order theories. We investigate the theory of finitely representable models and prove that it differs strongly from both classical model theory and finite model theory. In particular, we show that most of the well known theorems of either one fail (compactness, completeness, locality, 0/1 laws, etc.). An immediate consequence is the lack of tools to consider the definability of queries in the relational calculus over finitely representable databases. We illustrate this very challenging problem through some classical examples.

Copyright © 1994 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 ... BibTeX

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

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

Journal Edition

Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. J. Comput. Syst. Sci. 55(2): 273-298(1997) BibTeX

References

[Ajt83]
...
[AHV92]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CK73]
...
[Cod70]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Com88]
...
[Ehr61]
...
[Fag76]
...
[Fag93]
Ronald Fagin: Finite-Model Theory - A Personal Perspective. Theor. Comput. Sci. 116(1&2): 3-31(1993) BibTeX
[FSS84]
Merrick L. Furst, James B. Saxe, Michael Sipser: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1): 13-27(1984) BibTeX
[Fra54]
...
[Gai81]
...
[HH93]
Tirza Hirst, David Harel: Completeness Results for Recursive Data Bases. PODS 1993: 244-252 BibTeX
[Hul86]
Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. SIAM J. Comput. 15(3): 856-886(1986) BibTeX
[Imm87]
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX
[KG94]
...
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[KRVV93]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
[Kup90]
Gabriel M. Kuper: On The Expressive Power of the Relational Calculus with Arithmetic Constraints. ICDT 1990: 202-211 BibTeX
[Kup93]
Gabriel M. Kuper: Aggregation in Constraint Databases. PPCP 1993: 166-173 BibTeX
[Kup93a]
...
[Rev90]
Peter Z. Revesz: A Closed Form for Datalog Queries with Integer Order. ICDT 1990: 187-201 BibTeX
[Tar51]
...
[Tra50]
...
[Vau60]
...
[vdD82]
...
[Via93]
...
[Yao90]
...

Referenced by

  1. Oscar H. Ibarra, Jianwen Su: On the Containment and Equivalence of Database Queries with Linear Constraints. PODS 1997: 32-43
  2. Jan Paredaens, Bart Kuijpers, Gabriel M. Kuper, Luc Vandeurzen: Eucil, Tarski, and Engler Encompassed (Preliminary Report). DBPL 1997: 1-24
  3. Alexei P. Stolboushkin, Michael A. Taitslin: Linear vs. Order Contstrained Queries Over Rational Databases. PODS 1996: 17-27
  4. Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. PODS 1996: 81-92
  5. Stéphane Grumbach, Jianwen Su: Towards Practical Constraint Databases. PODS 1996: 28-39
  6. Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16
  7. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  8. Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
  9. Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150
  10. Jan Chomicki, Gabriel M. Kuper: Measuring Infinite Relations. PODS 1995: 78-85
  11. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
  12. Stéphane Grumbach, Zoé Lacroix: Computing Queries on Linear Constraint Databases. DBPL 1995: 11
  13. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  14. Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:11 2009