Complexity and Optimization Issues in Constraint Query Languages

Oscar H Ibarra and Jianwen Su

Department of Computer Science
University of California at Santa Barbara

Contact Information

Jianwen Su
Department of Computer Science
University of California
Santa Barbara, CA 93106
Phone: (805) 893-3698
Fax : (805) 893-8553
Email: su@cs.ucsb.edu

WWW PAGE

http://www.cs.ucsb.edu/~su/cdb/

Keywords

Constraint databases, optimization, query languages, spatial databases, complexity

Project Award Information

August 1997 - July 2000, $341,396, "Complexity and Optimization Issues in Constraint Query Languages".

Project Summary

This project focuses on three problem areas concerning linear constraint query languages. Constraint database systems integrate database technology with constraint solving techniques to deal with applications involving spatial or geographical datasets and arithmetic computations. Linear constraint databases are generally represented by quantifier-free logical formulas over some arithmetical domain such as the real numbers (the real closed field) with addition. Conceptually, constraint queries are evaluated in closed form using quantifier elimination algorithms. The first part of this project aims at developing efficient query evaluation algorithms for linear or dense order constraint queries and syntactic forms for representing constraint databases so that efficient query evaluation becomes possible. The second part aims at showing the complexity of decision problems concerning constraint query languages including query containment, equivalence, satisfiability, and disjointness using a new technique based on abstract machines. The third part aims at developing incremental evaluation techniques for recursive (non-first-order) and topological queries. This project will provide complexity results and efficient algorithms as a theoretical foundation for the design of constraint database models, query languages, and systems.

Goals, Objectives, and Targeted Activities

To investigate complexity issues related to constraint query languages, query evaluation and the equivalence and
containment of queries; and to develop efficient query evaluation algorithms and optimization techniques.

Project References

Area Background

Constraint databases and query languages were introduced by Kanellakis,Kuper, and Revesz. They combine techniques from database systems with constraint solving techniques to deal with applications involving spatial or geographical datasets and arithmetic computations. Constraint databases generalize the relations of the relational model by defining generalized tuples as conjunctions of constraints. For instance, the formula x2+y2=1 and x<=0 defines a binary generalized tuple.  A generalized, or finitely representable, relation is then a finite set (disjunction) of such tuples. In the real plane for instance, it results in an infinite set of points, or tuples, over R2. The relational calculus over such relations constitutes a constraint query
language. Similar to the relational model, equivalent algebras can also be defined.  The fundamental property here is
that the relational calculus can be used as a query language as soon as the constraints are based on a decidable theory which admits the elimination of quantifiers.  The evaluation of a (first-order) query is then done by quantifier elimination.

Area References

Introduction to constraint databases: Expressiver Power and Complexity: Issues in Constraint Query Languages: Indexing: