Investigation of evolutionary multi-objective algorithms in solving view selection problem / Seyed Hamid Talebian

Today’s huge volumes of data are maintained in conventional database systems. The data distributed in these systems sometimes come in inconsistent formats. On the other hand, data analysts require an environment so that they are able to obtain the required information. However, the distributed and heterogeneous structure of these systems prevents them from taking advantage of these data for analytical purposes. In order to overcome this weakness the data warehouse concept was introduced (Inmon, 1992). The main idea is such that, incompatible data spread over heterogeneous systems are extracted and after transformations to a unified form are loaded to a central and separate database for analytical purposes. Since analytical queries are complex and take a long time to be processed under normal circumstance, there is a need for a strategy to improve the speed of such queries. One of the ways for resolving this problem is by using pre-computed results of queries. In this approach, results of possible queries are computed in advance and whenever a user submits a query, instead of referring to the main table with enormous numbers of records, a proper pre-computed result is fetched and used for answering the query. The results of each query can be a logical table which is derived from the base tables. Such tables are called views in database terminology. Once the records of a view are stored on disk, the view is called a materialized view. Another important issue resulting from materializing view is updating the views. If during periodical reload from the conventional database systems new records are inserted to the fact table, the views that have been derived from the fact table need to be updated. The process of updating views in response to changes to base tables is called view update or view maintenance (Kotidis, 2002). This process is expensive because it is time consuming. In today’s systems availability is one goal and this is achieved by minimizing the update window during which the system is down. Although using materialized views for answering queries reduces the query response time but at the same time it increases the view update time. Selecting a subset of views which gives the best compromise between minimizing query response time and minimizing total update time is known as the view selection problem. This is considered a multi-objective problem because the problem involves optimizing more than one problem simultaneously subject to constraint(s). Evolutionary multi-objective algorithms are considered as good candidate for solving multi-objective optimization problems and have been applied to variety of problems in different areas. In this research, we showed how evolutionary multi-objective algorithms can be used to solve the view selection problem and its advantage over classical optimization problems were described. As a comparative study, the performance of the algorithms was evaluated based on various standard metrics. In addition to the normal metrics, the computational time for executing each algorithm was also measured and compared. Our results show that algorithms which use elitism feature are superior to other algorithms in most of the metrics. At the same time implementing elitism feature increases the computational complexity of the algorithm. Furthermore, niching strategies in some algorithms play an important role in delivering a diverse set of solutions. Generally, it can be said that two algorithms SPEA-II and NSGA-II perform better than other algorithms in terms of convergence to the optimal solution and diversity