Efficient View-Design Algorithms to Achieve Near-Optimal Performance of Sets of Relational Queries

本提案的目标是开发新的有效方法来提高大型关系数据库中频繁和重要查询集的性能，从而提高用户与数据管理系统交互的效率。解决这个问题将对查询优化、数据仓库和信息集成产生最大的影响。该项目侧重于使用视图评估查询的方法；视图是由辅助查询定义的关系，可用于重写和回答用户查询。提高查询性能的一种方法是预先计算和存储（即“物化”）视图。要真正优化查询性能，实现“正确”视图至关重要。该项目将证明，通过设计和实现视图，对于常见和重要的查询类型，可以确保频繁查询和重要查询的最佳或接近最佳性能。这项工作的重点是开发高效和可扩展的启发式算法，为给定的查询设计（接近）最优的视图集。该项目分为两个部分：(1)视图设计算法和启发式的理论分析和设计；(2)在大型数据库上的实现和实验，以评估使用视图所带来的性能改进。这个项目产生的技术可以应用于商业和实验数据库系统，它们将提供降低查询处理成本的新方法。研究结果将可通过项目网站http://research.csc.ncsu.edu/selftune/、出版物和免费分发的软件获得。该项目将为研究生和本科生提供教育和研究经验的机会。

The goal of this proposal is to develop new effective methods to improve the performance of sets of frequent and important queries on large relational databases, which could improve the efficiency of user interactions with data-management systems. Solving the problem will have the most effect in query optimization, data warehousing, and information integration. The project focuses on the methodology of evaluating queries using views; views are relations that are defined by auxiliary queries and can be used to rewrite and answer user queries. One way to improve query performance is precompute and store (i.e., "materialize") views. To truly optimize query performance, it is critical to materialize the "right" views. The project will demonstrate that, by designing and materializing views, it is possible to ensure optimal or near-optimal performance of frequent and important queries, for common and important query types. The focus of this effort is on developing efficient and scalable heuristic algorithms that design (near-) optimal sets of views for the given queries. The project has two parts: (1) theoretical analysis and design of algorithms and heuristics for view design, and (2) implementation and experiments on large databases, to evaluate the performance improvements caused by using the views. The techniques resulting from this project could have application in commercial and experimental database systems, where they will provide new ways to lower query-processing costs. The research results will be accessible via a project web site http://research.csc.ncsu.edu/selftune/, publications, and freely disseminated software. The project will provide educational and research experience opportunities for graduate and undegraduate students.