  We model the algorithmic task of geometric elimination (e.g., quantifier
elimination in the elementary field theories of real and complex numbers) by
means of certain constraint database queries, called geometric queries. As a
particular case of such a geometric elimination task, we consider sample point
queries. We show exponential lower complexity bounds for evaluating geometric
queries in the general and in the particular case of sample point queries.
Although this paper is of theoretical nature, its aim is to explore the
possibilities and (complexity-)limits of computer implemented query evaluation
algorithms for Constraint Databases, based on the principles of the most
advanced geometric elimination procedures and their implementations, like,
e.g., the software package "Kronecker".
