Publishing house / Banach Center Publications / All volumes

Abstract

In the relational model of databases a database state is thought of as a finite collection of relations between elements. For many applications it is convenient to pre-fix an infinite domain where the finite relations are going to be defined. Often, we also fix a set of domain functions and/or relations. These functions/relations are infinite by their nature. Some special problems arise if we use such an approach. In the paper we discuss some of the problems. We show that there exists a recursive domain with decidable theory in which (1) there is no recursive syntax for finite queries, and in which (2) the state-safety problem is undecidable. We provide very general conditions on the FO theory of an ordered domain that ensure collapse of order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of ordered domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all o-minimal domains, but also the ordered group of integer numbers and the ordered semigroup of natural numbers, and some other domains. We generalize all the notions to the case of finitely representable database states - as opposed to finite states - and develop a general lifting technique that, essentially, allows us to extend any result of the kind we are interested in, from finite to finitely-representable states. We show, however, that these results cannot be transferred to arbitrary infinite states. We prove that safe $Datalog^{¬,<_z}$-programs do not have any effective syntax.