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 properties of 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.
