Static and incremental dynamic approaches for multi-objective bitmap join indexes selection in data warehouses
- PDF / 1,608,312 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 102 Downloads / 201 Views
Static and incremental dynamic approaches for multi‑objective bitmap join indexes selection in data warehouses Lyazid Toumi1 · Ahmet Ugur2 Accepted: 30 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Data warehouses are very large databases and play key role in intelligent decision making in enterprises. The bitmap join indexes selection problem is crucial in the data warehouse physical design and known to be NP-hard. All the existing methods that solve this problem use single objective function and static query workload during the optimization. In the present work, we propose a multi-objective formulation of the problem using I) a static query workload and II) an incremental dynamic query workload. Three best well-known multi-objective evolutionary algorithms, Non-dominated sorting-based genetic algorithm II, S-Metric Selection Evolutionary Multi-Objective Algorithm and Strength Pareto Evolutionary Algorithm 2, are used to solve the multi-objective bitmap join indexes selection problem using both static and incremental dynamic query workloads. A set of experiments are performed to demonstrate the effectiveness of the proposed approaches. The incremental dynamic approach demonstrates a new perspective on bitmap join indexes optimization in a changing environment of an operational data warehouse. Keywords Data warehouse physical design · Bitmap join indexes optimization · Multi-objective optimization · Static physical design · Incremental physical design · Evolutionary multi-objective algorithm
* Lyazid Toumi lyazid.toumi@univ‑setif.dz Ahmet Ugur [email protected] 1
Department of Computer Science, Ferhat Abbas Unversity, Mechatronics Laboratory (LMETR) - E1764200, Setif 19000, Algeria
2
Department of Computer Science, Central Michigan University, Mount Pleasant, MI 48859, USA
13
Vol.:(0123456789)
L. Toumi, A. Ugur
1 Introduction Data warehouse (DW) physical design optimization is a complex and difficult task in general [3]. The main objective of the optimization in a data warehouse physical design is minimizing query costs and increasing the performance. Several optimization techniques have been used, some of which are from classical databases, such as horizontal and vertical partitioning [5, 7, 35], materialized views [1, 15, 32] and b-tree and bitmap indexes [2, 4, 34, 36, 37]. Techniques like bitmap join indexes and referential horizontal partitioning are introduced later. Usually, a data definition language is used to create and maintain the optimization structures in both commercial and open source database management systems (DBMS). Yet, optimizing the performance while maintaining the optimization structure(s) in data warehouses remains a continuous challenge. Bitmap joint index (BJI) introduced by ONeil et al. [28] is the most common optimization technique used in DW. Finding an optimum set of BJIs is known as bitmap join indexes selection problem (BJISP) and known to be an NP-hard problem in data warehouse physical design [2]. The BJISP is formu
Data Loading...
