Abstract
Linear Constraint Databases
by: Stephane Grumbach, Jianwen Su, and Cristophe Tollu
Abstract:
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.
Keywords:
linear constraints, constraint databases, query languages,expressive power, computational complexity
Date:
February, 1995
Document: 1995-03
