| Type of Document |
Master's Thesis |
| Author |
Asgharzadeh Talebi, Zohreh , |
| Author's Email Address |
z_asgharzadeh@yahoo.com |
| URN |
etd-05092006-123513 |
| Title |
Exact and Heuristic Methods for solving the View-Selection Problem for Aggregate Queries |
| Degree |
Master of Science |
| Graduate Program |
Operations Research |
| Advisory Committee |
| Advisor Name |
Title |
| Dr. Rada Chirkova |
Committee Co-Chair |
| Dr. Yahya Fathi |
Committee Co-Chair |
| Dr. Matt Stallmann |
Committee Member |
|
| Keywords |
- DBMS
- database optimization
- materialized views
- integer programming
|
| Date of Defense |
2006-04-25 |
| Availability |
unrestricted |
Abstract
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].
|
| Files |
| Filename |
Size |
Approximate Download Time
(Hours:Minutes:Seconds)
|
| 28.8 Modem |
56K Modem |
ISDN (64 Kb) |
ISDN (128 Kb) |
Higher-speed Access |
| |
etd.pdf |
660.83 Kb |
00:03:03 |
00:01:34 |
00:01:22 |
00:00:41 |
00:00:03 |
|
