Finitely Representable Databases.

Stéphane Grumbach 1 Jianwen Su 2
1 VERSO - Databases
Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8629
Abstract : We study infinite but finitely representable databases based on constraints, motivated by new database applications such as those involving spatio-temporal information. We introduce a general defini- tion of finite representation and define the concept of a query as a generalization of a query over relational databases. We investigate the theory of finitely representable models and prove that it differs from both classical model theory and finite model theory. In particular, we show the failure of most of the well-known theorems of logic (compactness, completeness, etc.). An important consequence is that properties such as query satisfiability and containment are undecidable. We illustrate the use of EhrenfeuchtFra@ sse games on the expressive power of query languages over finitely representable databases. As a case study, we focus on queries over dense order constraint databases. We consider in particular ``order-generic'' queries which are mappings closed under order-preserving bijections and topological queries, map- pings closed under homeomorphisms. We prove that many interesting queries such as topological connectivity are not first-order definable with dense order constraints. We then consider an inflationary fixpoint query language, and prove that it captures exactly all PTIME order- generic queries. Finally, we give a rapid survey of recent results for more general contexts, such as polynomial constraints.
Type de document :
Article dans une revue
Journal of Computer and System Sciences (JCSS), Elsevier, 1997, 55 (2), pp.273-298
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
Contributeur : Chine Publications Liama <>
Soumis le : mercredi 13 décembre 2006 - 18:29:28
Dernière modification le : mardi 17 avril 2018 - 11:30:26
Document(s) archivé(s) le : mercredi 7 avril 2010 - 00:37:31


Fichiers éditeurs autorisés sur une archive ouverte


  • HAL Id : inria-00120273, version 1



Stéphane Grumbach, Jianwen Su. Finitely Representable Databases.. Journal of Computer and System Sciences (JCSS), Elsevier, 1997, 55 (2), pp.273-298. 〈inria-00120273〉



Consultations de la notice


Téléchargements de fichiers