Constraint Databases: Optimization Techniques and Applications

约束数据库集成了数据库和约束技术，可用于时空数据库应用，包括地理信息系统和移动对象。约束数据模型强调逻辑属性，同时隐藏物理表示；它们支持通用数据管理功能。该项目从三个方面研究约束数据库：算法、应用和基础。在算法方面，研究了约束数据库查询的优化技术。与交集谓词的连接称为空间连接。传统算法使用启发式、索引和计算几何技术来评估对象的最小外接矩形上的连接作为过滤器。最近的算法允许对过滤器进行更好的近似，甚至对对象执行直接连接。本项目的一个重点是研究和比较这些新算法的性能，并开发进一步的改进和模型，以根据数据集的属性和近似来预测过滤器的有效性。此外，交集连接的技术被扩展到与其他拓扑(如包容、相交)、距离和方向谓词的连接，以及多路空间连接。更根本的是，优化问题通常与逻辑属性的决策问题相关，例如事务(查询/更新)的包容性、等价性和分离性。抽象机器是最近发展起来的研究这类问题的工具。事务通常使用在运行时实例化的参数预先设计。对抽象机技术进行了扩展，用于研究参数事务的逻辑性质和相关的计算复杂性问题。在应用方面，本项目采用约束方法开发移动对象数据库的数据模型和查询语言，研究约束数据库的查询优化，将数据库和约束技术结合起来应用于时空数据库应用，包括地理信息系统和移动对象。约束数据模型强调逻辑属性，同时隐藏物理表示；它们支持通用数据管理功能。该项目从三个方面研究约束数据库：算法、应用和基础。在算法方面，研究了约束数据库查询的优化技术。与交集谓词的连接称为空间连接。传统算法使用启发式、索引和计算几何技术来评估对象的最小外接矩形上的连接作为过滤器。最近的算法允许对过滤器进行更好的近似，甚至对对象执行直接连接。本项目的一个重点是比较和表征这些新算法的性能，并开发进一步的改进和模型，以根据数据集的属性和近似来预测过滤器的有效性。此外，交集连接的技术被扩展到与其他拓扑(如包容、相交)、距离和方向谓词的连接，以及多路空间连接。更根本的是，优化问题通常与逻辑属性的决策问题相关，例如事务(查询/更新)的包容性、等价性和分离性。抽象机器(在自动机理论中)被发现是研究这类问题的一个非常有用的工具。事务通常使用在运行时实例化的参数预先设计。该项目旨在扩展这些自动机理论技术，以研究参数化事务的逻辑属性和相关的计算复杂性问题。在应用方面，该项目采用约束方法来开发移动对象数据库的数据模型和查询语言。其目标是提供用于管理和查询移动对象的概念框架和优化技术。

Constraint databases integrate database and constraint technologies for spatio-temporal database applications including GIS and moving objects. Constraint data models emphasize logical properties while hiding physical representations; they enable general purpose data management capabilities. The project investigates constraint databases in three aspects: algorithms, applications, and foundations. In algorithms, it aims at optimization techniques for constraint database queries. Joins with the intersection predicate are known as spatial joins. Traditional algorithms use heuristics, indexes, and computational geometry techniques to evaluate the join on minimum bounding rectangles of objects as a filter. Recent algorithms allow better approximations for filter, or even perform a direct join on objects. A focus of this project is to study and compare performance of such new algorithms and develop further improvements and models for predicting filter effectiveness in terms of dataset properties and approximations. Moreover, the techniques for intersection join are extended for joins with other topological (e.g., containment, meet), distance, and direction predicates, and to multiway spatial joins. More fundamentally, optimization issues are often related to decision problems of logical properties such as containment, equivalence, and disjointness of transactions (queries/updates). Abstract machines are a recently developed tool for studying such problems. Transactions are often designed in advance with parameters instantiated at runtime. The abstract machine techniques are extended for studying logical properties of parameterized transactions and related computational complexity issues. In applications aspect, the project uses the constraint approach to develop data models and query languages for moving object databases and study query optimization Constraint databases integrate database and constraint technologies for spatio-temporal database applications including GIS and moving objects. Constraint data models emphasize logical properties while hiding physical representations; they enable general purpose data management capabilities. The project investigates constraint databases in three aspects: algorithms, applications, and foundations. In algorithms, it aims at optimization techniques for constraint database queries. Joins with the intersection predicate are known as spatial joins. Traditional algorithms use heuristics, indexes, and computational geometry techniques to evaluate the join on minimum bounding rectangles of objects as a filter. Recent algorithms allow better approximations for filter, or even perform a direct join on objects. A focus of this project is to compare and characterize performance of such new algorithms and develop further improvements and models for predicting filter effectiveness in terms of dataset properties and approximations. Moreover, the techniques for intersection join are extended for joins with other topological (e.g., containment, meet), distance, and direction predicates, and to multiway spatial joins. More fundamentally, optimization issues are often related to decision problems of logical properties such as containment, equivalence, and disjointness of transactions (queries/updates). Abstract machines (in automata theory) have been found to be a very useful tool for studying such problems. Transactions are often designed in advance with parameters instantiated at runtime. The project intends to extend these automata-theoretic techniques for studying logical properties of parameterized transactions and related computational complexity issues. In applications aspect, the project applies the constraint approach to develop data models and query languages for moving object databases. The goal is to provide a conceptual framework and optimization techniques for managing and querying moving objects.