Constraint Databases: Optimization Techniques and Applications

约束数据库：优化技术和应用

• 批准号: 0101134
• 负责人: Jianwen Su
• 金额: $ 45万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0101134&HistoricalAwards=false
• 关键词: Constraint; Databases; Optimization; Techniques; 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.

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