Michael A. Taitslin

Tver State University

Linear vs. Order Constraint Queries Over Rational Databases

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

December 20, 1995 at 4:30 PM

Abstract:

We show that every finitely representable order database state can be represented by a finite state (of another scheme) such that these two states are uniformly FO-translatable to one another. Using this result, we show that, for any divisible ordered Abelian group, generic first-order queries with linear constraints over finitely representable database states can be effectively translated into first-order queries with order constraints. Over all rational database states, however, these two query languages differ.

Joint work with Alexei P. Stolboushkin (UCLA).