Linear Constraint Databases

We give an AC/sup 0/ upper bound on the complexity of first-order queries over(infinite) databases defined by restricted linear constraints. This resultenables us to deduce the non-expressibility of various usual queries, such asthe parity of the cardinality of a set or the connectivity of a graph infirst-order logic with linear constraints over the reals.