###
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.