Exact and Heuristic Methods for solving the View-Selection Problem for Aggregate Queries

DBMS;database optimization;materialized views;integer programming

Asgharzadeh Talebi, Zohreh ; Dr. Matt Stallmann, Committee Member,Dr. Yahya Fathi, Committee Co-Chair,Dr. Rada Chirkova, Committee Co-Chair,Asgharzadeh Talebi, Zohreh ; Dr. Matt Stallmann ; Committee Member ; Dr. Yahya Fathi ; Committee Co-Chair ; Dr. Rada Chirkova ; Committee Co-Chair

University:North Carolina State University

关键词: DBMS;    database optimization;    materialized views;    integer programming;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/2359/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

In this thesis we present a formal study of the following view-selection problem: Given a set of queries, a database, and an upper bound on the amount of disk space that can be used to store materialized views, return definitions of views that, when materialized in the database, would reduce the evaluation costs of the queries. Optimizing the layout of stored data using view selection has a direct impact on the performance of the entire database system. At the same time, the optimization problem is intractable, even under natural restrictions on the types of queries of interest. We introduce an integer-programming model to obtain optimal solutions for the view-selection problem for aggregate queries on data warehouses. Through a computational experiment we show that this model can be used to solve realistic-size instances of the problem. We also report the results of the post-optimality analysis that we performed to determine the impact of changing certain input characteristics on the optimal solution. We solve large instances by applying several methods of reducing the size of the search space. We compare our approach to the leading heuristic procedure in the field [20].