Designing Genetic Algorithms for Materialized View and Index Selection

摘要

Organizational decision-making involves accessing and integrating data that resides in various autonomous, localized databases. Our approach to providing integrated access to multiple databases is the data warehousing approach: we assume data is extracted from different sources in advance, integrated, and stored at a centralized location to answer queries posed to support decision-making. The stored data sets are materialized relational views, and auxiliary data structures such as indexes can be built on these materialized views to speed up data retrieval. Since the amount of data available in source databases can be much larger than the available storage space in the warehouse, not all source data can be materialized. Materialized views are built on frequently posed queries and any other data is communicated from the sources when required. Identifying the data to be materialized as views and the indexes to be built on these views is a leading research issue in data warehousing. Due to the large search space for this problem, we explore the use of genetic algorithms (GAs) to select materialized views and indexes in a data warehouse. We minimize query response time for a given workload while also considering a limit on storage space. In this paper, we discuss the design of a genetic algorithm including creating the initial solution space, encoding the problem as a chromosome, generating new populations, and evaluating the fitness of a chromosome. We illustrate the approach for a relational data warehouse since it is well-known and widely used.