Safe constraint queries

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.