Relational expressive power of constraint query languages Title

Relational expressive power of constraint query languages

Michael Benedikt, AT&T

Guozhu Dong, The University of Melbourne

Leonid Libkin, AT&T

Limsoon Wong, Institute of System Sciences, Singapore

Status

Tech report of AT&T

Abstract

We study the expressive power of first order query languages with several classes of equality and inequality constraints and give three main results. (1) We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in relational calculus with polynomial inequality constraints over the reals. (2) Noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic queries expressible in relational calculus augmented with a class of constraints coincides with the class of queries expressible in relational calculus (with or without an order relation). We prove such results for both natural and active-domain semantics. (3) As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic relational queries under 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 constraints coincides with a constraint-free query on databases whose elements come from a certain infinite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of analytic functions.