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 
[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)
References
- [Ajt83]
- ...
- [AHV92]
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - [AU79]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120
- [CH80]
- Ashok K. Chandra, David Harel:
Computable Queries for Relational Data Bases.
J. Comput. Syst. Sci. 21(2): 156-178(1980)
- [CK73]
- ...
- [Cod70]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970)
- [Com88]
- ...
- [Ehr61]
- ...
- [Fag76]
- ...
- [Fag93]
- Ronald Fagin:
Finite-Model Theory - A Personal Perspective.
Theor. Comput. Sci. 116(1&2): 3-31(1993)
- [FSS84]
- Merrick L. Furst, James B. Saxe, Michael Sipser:
Parity, Circuits, and the Polynomial-Time Hierarchy.
Mathematical Systems Theory 17(1): 13-27(1984)
- [Fra54]
- ...
- [Gai81]
- ...
- [HH93]
- Tirza Hirst, David Harel:
Completeness Results for Recursive Data Bases.
PODS 1993: 244-252
- [Hul86]
- Richard Hull:
Relative Information Capacity of Simple Relational Database Schemata.
SIAM J. Comput. 15(3): 856-886(1986)
- [Imm87]
- Neil Immerman:
Languages that Capture Complexity Classes.
SIAM J. Comput. 16(4): 760-778(1987)
- [KG94]
- ...
- [KKR90]
- Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz:
Constraint Query Languages.
PODS 1990: 299-313
- [KRVV93]
- Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter:
Indexing for Data Models with Constraints and Classes.
PODS 1993: 233-243
- [Kup90]
- Gabriel M. Kuper:
On The Expressive Power of the Relational Calculus with Arithmetic Constraints.
ICDT 1990: 202-211
- [Kup93]
- Gabriel M. Kuper:
Aggregation in Constraint Databases.
PPCP 1993: 166-173
- [Kup93a]
- ...
- [Rev90]
- Peter Z. Revesz:
A Closed Form for Datalog Queries with Integer Order.
ICDT 1990: 187-201
- [Tar51]
- ...
- [Tra50]
- ...
- [Vau60]
- ...
- [vdD82]
- ...
- [Via93]
- ...
- [Yao90]
- ...
Referenced by
- Oscar H. Ibarra, Jianwen Su:
On the Containment and Equivalence of Database Queries with Linear Constraints.
PODS 1997: 32-43
- Jan Paredaens, Bart Kuijpers, Gabriel M. Kuper, Luc Vandeurzen:
Eucil, Tarski, and Engler Encompassed (Preliminary Report).
DBPL 1997: 1-24
- Alexei P. Stolboushkin, Michael A. Taitslin:
Linear vs. Order Contstrained Queries Over Rational Databases.
PODS 1996: 17-27
- Christos H. Papadimitriou, Dan Suciu, Victor Vianu:
Topological Queries in Spatial Databases.
PODS 1996: 81-92
- Stéphane Grumbach, Jianwen Su:
Towards Practical Constraint Databases.
PODS 1996: 28-39
- Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong:
Relational Expressive Power of Constraint Query Languages.
PODS 1996: 5-16
- 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
- Guozhu Dong, Jianwen Su:
Space-Bounded FOIES.
PODS 1995: 139-150
- Jan Chomicki, Gabriel M. Kuper:
Measuring Infinite Relations.
PODS 1995: 78-85
- Peter Z. Revesz:
Datalog Queries of Set Constraint Databases.
ICDT 1995: 425-438
- Stéphane Grumbach, Zoé Lacroix:
Computing Queries on Linear Constraint Databases.
DBPL 1995: 11
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
Towards a Theory of Spatial Database Queries.
PODS 1994: 279-288
Last update Fri May 25 08:32:48 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
