Abstract
Multi-table indexes boost the performance of extremely large databases by reducing the cost of joins involving several tables. The bitmap join indexes (\(\mathcal{B}\mathcal{J}\mathcal{I}\)) are one of the most popular examples of this category of indexes. They are well adapted for point and range queries. Note that the selection of multi-table indexes is more difficult than the mono-table indexes, considered as the pioneer of database optimisation problems. The few studies dealing with the \(\mathcal{B}\mathcal{J}\mathcal{I}\) selection problem in the context of relational data warehouses have three main limitations: (i) they consider \(\mathcal{B}\mathcal{J}\mathcal{I}\) defined on only two tables (a fact table and a dimension table) by the use of one or several attributes of that dimension table, (ii) they use simple greedy algorithms to pick the right indexes and (iii) their algorithms are static. In this paper, we propose genetic algorithms for selecting \(\mathcal{B}\mathcal{J}\mathcal{I}\) using a large number of attributes belonging to n ( ≥ 2) dimension tables in the static and incremental ways. Intensive experiments are conducted to show the efficiency of our proposal.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aouiche, K., Darmont, J., Boussaïd, O., Bentayeb, F.: Automatic Selection of Bitmap Join Indexes in Data Warehouses. In: Tjoa, A.M., Trujillo, J. (eds.) DaWaK 2005. LNCS, vol. 3589, pp. 64–73. Springer, Heidelberg (2005)
Azefack, S., Aouiche, K., Darmont, J.: Dynamic index selection in data warehouses. In: 4th International Conference on Innovations in Information Technology, Innovations 2007 (2007)
Bäck, T.: Evolutionnary algorithms in theory and practice. Oxford University Press, New York (1995)
Bellatreche, L., Boukhalfa, K.: Yet Another Algorithms for Selecting Bitmap Join Indexes. In: Bach Pedersen, T., Mohania, M.K., Tjoa, A.M. (eds.) DAWAK 2010. LNCS, vol. 6263, pp. 105–116. Springer, Heidelberg (2010)
Bouchakri, R., Bellatreche, L.: On Simplifying Integrated Physical Database Design. In: Eder, J., Bielikova, M., Tjoa, A.M. (eds.) ADBIS 2011. LNCS, vol. 6909, pp. 333–346. Springer, Heidelberg (2011)
Canahuate, G., Apaydin, T., Sacan, A., Ferhatosmanoglu, H.: Secondary bitmap indexes with vertical and horizontal partitioning. In: EDBT, pp. 600–611 (2009)
Chaudhuri, S.: Index selection for databases: A hardness study and a principled heuristic solution. IEEE Transactions on Knowledge and Data Engineering 16(11), 1313–1323 (2004)
OLAP Council. Apb-1 olap benchmark, release ii (1998), http://www.olapcouncil.org/research/bmarkly.htm
Comer, D.: The dificulty of optimum index selection. ACM Transactions on Database Systems (TODS) 3(4), 440–445 (1978)
Frank, M.R., Omiecinski, E., Navathe, S.B.: Adaptive and Automated Index Selection in RDBMS. In: Pirotte, A., Delobel, C., Gottlob, G. (eds.) EDBT 1992. LNCS, vol. 580, pp. 277–292. Springer, Heidelberg (1992)
Kratica, J., Ljubic, I., Tosic, D.: A genetic algorithm for the index selection problem. In: Applications of Evolutionary Computing Workshops, pp. 280–290 (2003)
Li, Q., Fung, C.-W., Karlapalem, K.: Structural join index driven complex object retrieval: Mechanisms and selection. In: CIKM, pp. 150–157 (2000)
Morzy, T., Wrembel, R., Chmiel, J., Wojciechowski, A.: Time-hobi: Index for optimizing star queries. Information Systems 37(5), 412–429 (2012)
O’Neil, P., Quass, D.: Improved query performance with variant indexes. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 38–49 (May 1997)
Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Discovering Frequent Closed Itemsets for Association Rules. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 398–416. Springer, Heidelberg (1998)
Shekhar, S., Lu, C.T., Chawla, S., Ravada, S.: Efficient join-index-based spatial-join processing: A clustering approach. IEEE Transactions on Knowledge and Data Engineering 14(6), 1400–1421 (2002)
Stöhr, T., Märtens, H., Rahm, E.: Multi-dimensional database allocation for parallel data warehouses. In: VLDB, pp. 273–284 (2000)
Valduriez, P.: Join indices. ACM Transactions on Database Systems 12(2), 218–246 (June 1987)
Wrembel, R.: Data warehouse performance - selected techniques and data structures. In: European Business Intelligence Summer School, pp. 27–62. Springer (2012)
Wu, K., Otoo, E., Shoshani, A.: An efficient compression scheme for bitmap indices. ACM Transactions on Database Systems (TODS) 31(1), 1–38 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bouchakri, R., Bellatreche, L., Hidouci, KW. (2012). Static and Incremental Selection of Multi-table Indexes for Very Large Join Queries. In: Morzy, T., Härder, T., Wrembel, R. (eds) Advances in Databases and Information Systems. ADBIS 2012. Lecture Notes in Computer Science, vol 7503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33074-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-33074-2_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33073-5
Online ISBN: 978-3-642-33074-2
eBook Packages: Computer ScienceComputer Science (R0)