RELATIONAL EXPRESSIVE POWER OF CONSTRAINT QUERY LANGUAGES

The expressive power of first-order query languages with several class es of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augm ented with polynomial inequality constraints over the reals. Furthermo re, noting that relational queries exhibit several forms of genericity , we establish a number of collapse results of the following form: The class of generic Boolean queries expressible in the relational calcul us augmented with a given class of constraints coincides with the clas s of queries expressible in the relational calculus (with or without a n order relation). We prove such results for both the natural and acti ve-domain semantics. As a consequence, the relational calculus augment ed with polynomial inequalities expresses the same classes of generic Boolean queries under both the natural and active-domain semantics. In the course of proving these results for the active-domain semantics, we establish Ramsey-type theorems saying that any query involving cert ain kinds of constraints coincides with a constraint-free query on dat abases whose elements come from a certain infinite subset of the domai n. To prove the collapse results for the natural semantics, we make us e of techniques from nonstandard analysis and from the model theory of ordered structures.