Tech Report CS-92-50

Constraint Query Languages

Paris C. Kanellakis, Gabriel M. Kuper and Peter Z. Revesz

October 1992

Abstract:

We investigate the relationship between programming with constraints and database query languages. We show that efficient, declarative database programming can be combined with efficient constraint solving. The key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints over a small number of variables. We describe the basic constraint query language design principles and illustrate them with four classes of constraints: real polynomial inequalities, dense linear order inequalities, equalities over an infinite domain, and boolean equalities. For the analysis, we use quantifier elimination techniques from logic and the concept of data complexity from database theory. This framework is applicable to managing spatial data and can be combined with existing multi-dimensional searching algorithms and data structures.

KEYWORDS: database queries, spatial databases, data complexity, quantifier elimination, constraint logic programming, relational calculus, Datalog.

(complete text in pdf or gzipped postscript)