Complexity and Optimization Issues in Constraint Query Languages

该项目主要关注线性约束查询语言的三个问题领域。约束数据库系统将数据库技术与约束求解技术相结合，以处理涉及空间或地理数据集和算术计算的应用。线性约束数据库通常是用一些算术域（如带加法的实数（实闭域））上的无量词逻辑公式来表示的。从概念上讲，约束查询使用量词消除算法以封闭形式进行评估。该项目的第一部分旨在开发用于线性或密集顺序约束查询的高效查询计算算法，以及用于表示约束数据库的语法形式，从而使高效查询计算成为可能。第二部分使用一种基于抽象机器的新技术展示了约束查询语言属性的复杂性，包括查询包含性、等价性、可满足性和不连接性。第三部分旨在开发用于递归（非一阶）和拓扑查询的增量计算技术。该项目将提供复杂性结果和高效算法，作为设计约束数据库模型、查询语言和系统的理论基础。

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.