This project explores the development and use of constraint programming languages in database applications. Constraint Query Languages (or CQLs) are applicable to many domain-specific areas, such as spatial databases, because their basic data type generalizes the relational tuple data type and is closer to the application semantics, e.g., for spatial databases these generalized tuples are convex spatial point sets . Most importantly, CQLs are designed so that I/O-efficient access to large sets of generalized tuples can be supported through existing multi-dimensional searching data structures. This project is an investigation of both the principles and the practice of CQLs. The principles include: the expressive power of various classesof constraints both linear and nonlinear; the design of calculus/algebra languages combining constraints and objects; the optimization of constraint programs; and the data structures for indexing very large sets of constraints. The practice involves developing prototypes of persistent constraint languages and evaluating them in three concrete application areas: solid modeling in design databases; map overlays in spatial databases; and subsequence matching in scientific databases. Constraint Query Languages will be key components of the next generation of declarative database interfaces, because they capture domain-specific semantics in an efficient fashion, and their successful implementation will be a significant extension of the current relational and object- oriented database technologies
