dblp.uni-trier.de www.dagstuhl.de www.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},
  editor    = {Victor Vianu},
  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, USA},
  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}
}

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

Printed Edition

Victor Vianu (Ed.): Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota, USA. ACM Press 1994, ISBN 0-89791-642-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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

References

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Free | Complete | Author
Last update Thu May 24 04:40:30 2012 CET by the DBLP Team — This material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page