We extend some of the classical characterization theorems of relational dat
abase theory-particularly those related to query safety-to the context wher
e database elements come with fixed interpreted structure and where formula
e over elements of that structure can be used in queries. We show that the
addition of common interpreted functions, such as real addition and multipl
ication, to the relational calculus preserves important characterization th
eorems of the relational calculus and also preserves certain combinatorial
properties of queries. Our main result of the rst kind is that there is a s
yntactic characterization of the collection of safe queries over the relati
onal calculus supplemented by a wide class of interpreted functions a class
that includes addition, multiplication, and exponentiation and that this c
haracterization gives us an interpreted analog of the concept of range-rest
ricted query from the uninterpreted setting. Furthermore, our range-restric
ted queries are particularly intuitive for the relational calculus with rea
l arithmetic and give a natural syntax for safe queries in the presence of
polynomial functions. We use these characterizations to show that safety is
decidable for Boolean combinations of conjunctive queries for a large clas
s of interpreted structures. We show a dichotomy theorem that sets a polyno
mial bound on the growth of the output of a query that might refer to addit
ion, multiplication, and exponentiation.
We apply the above results for finite databases to get results on constrain
t databases representing potentially infinite objects. We start by getting
syntactic characterizations of the queries on constraint databases that pre
serve geometric conditions in the constraint data model. We consider classe
s of convex polytopes, polyhedra, and compact semilinear sets, the latter c
orresponding to many spatial applications. We show how to give an effective
syntax to safe queries and prove that for conjunctive queries the preserva
tion properties are decidable.