International Journal of Advanced Studies in Computer Science and Engineering

Open Access Open Access  Restricted Access Subscription Access

Effectively indexing Data Warehouses: A Constraint Programming Perspective


Affiliations
1 LIM Laboratory, Amar Telidji University of Laghouat, Bp 37G, Ghardaia Road, Laghouat 03000,, Algeria
 

Data warehouses have become, nowadays, at the core of decisional systems. The Index Selection Problem (ISP) is a challenging problem in data warehouses physical design. Regarding the NP-hard nature of this problem, existing solutions rely heavily on heuristics which constitutes a major drawback. In this paper, we propose a novel exact approach to the ISP based on Constraint Programming (CP). We formulate the problem as a Constraint Optimization Problem in a declarative way, then its resolution is automatically supported by a generic CP solver. Our proposed approach has also the advantage of being declarative, flexible, and expandable as it allows incorporating various kinds of user preferences, expressed as constraints, as well as choosing or defining new search strategies. Experimental results confirm our expectations and show that our approach scales well enough to solve much larger realistic instances in a faster and more effective way compared to well-known state-of-the-art approximation approaches.

Keywords

data warehouses; bitmap join index; constraint programming; index selection problem; constraint optimization problem; decisional systems.
User
Notifications
Font Size

  • L. Toumi and A. Ugur, “Static and incremental dynamic approaches for multi-objective bitmap join indexes selection in data warehouses,” Journal of Supercomputing, vol. 77, no. 4, pp. 3933–3958, Apr. 2021, doi: 10.1007/s11227-020-03423-7.

  • R. Kain, D. Manerba, and R. Tadei, “The index selection problem with configurations and memory limitation: A scatter search approach,” Comput Oper Res, vol. 133, Sep. 2021, doi: 10.1016/j.cor.2021.105385.

  • S. Amjad, I. Jellouli, M. Yahyaoui, and L. Benameur, “Efficient of bitmap join indexes for optimising star join queries in relational data warehouses,” International Journal of Computational Intelligence Studies, vol. 9, no. 3, 2020, doi: 10.1504/ijcistudies.2020.10031847.

  • B. Ziani and Y. Ouinten, “An improved approach for automatic selection of multi-tables indexes in ralational data warehouses using maximal frequent itemsets,” Intelligent Decision Technologies, vol. 7, no. 4, 2013, doi: 10.3233/IDT-130169.

  • E. O’Neil, P. O’Neil, and K. Wu, “Bitmap index design choices and their performance implications,” 2007. doi: 10.1109/IDEAS.2007.4318091.

  • S. Chaudhuri, M. Datar, and V. Narasayya, “Index selection for databases: A hardness study and a principled heuristic solution,” IEEE Trans Knowl Data Eng, vol. 16, no. 11, 2004, doi: 10.1109/TKDE.2004.75.

  • L. Bellatreche and K. Boukhalfa, “Yet another algorithms for selecting bitmap join indexes,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, vol. 6263 LNCS. doi: 10.1007/978-3-642-15105- 7_9.

  • H. Drias and I. Frihi, “ACO based approach and integrating information retrieval technologies in selecting Bitmap Join Indexes,” in Proceedings - 2010 IEEE/WIC/ACM International Conference on Web Intelligence, WI 2010, 2010, vol. 1. doi: 10.1109/WI-IAT.2010.180.

  • A. Gacem and K. Boukhalfa, “Immune algorithm for bitmap join indexes,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, vol. 7665 LNCS, no. PART 3. doi: 10.1007/978- 3-642-34487-9_68.

  • R. Bouchakri and L. Bellatreche, “On simplifying integrated physical database design,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, vol. 6909 LNCS. doi: 10.1007/978-3-642-23737- 9_24.

  • L. Toumi, A. Moussaoui, and A. Ugur, “Particle swarm optimization for bitmap join indexes selection problem in data warehouses,” Journal of Supercomputing, vol. 68, no. 2, 2014, doi: 10.1007/s11227-013-1058-9.

  • P. Ameri, J. Meyer, and A. Streit, “On a new approach to the index selection problem using mining algorithms,” 2015. doi: 10.1109/BigData.2015.7364084.

  • K. Aouiche and J. Darmont, “Data mining-based materialized view and index selection in data warehouses,” J Intell Inf Syst, vol. 33, no. 1, 2009, doi: 10.1007/s10844-009-0080-0.

  • K. Aouiche, J. Darmont, O. Boussaïd, and F. Bentayeb, “Automatic selection of bitmap join indexes in data warehouses,” in Lecture Notes in Computer Science, 2005, vol. 3589. doi: 10.1007/11546849_7.

  • L. Bellatreche, R. Missaoui, H. Necir, and H. Drias, “A Data Mining Approach for Selecting Bitmap Join Indices,” Journal of Computing Science and Engineering, vol. 1, no. 2, 2007, doi: 10.5626/jcse.2007.1.2.177.

  • P. Kołaczkowski and H. Rybiński, “Automatic index selection in RDBMS by exploring query execution plan space,” Studies in Computational Intelligence, vol. 223, 2009, doi: 10.1007/978-3-642- 02190-9_1.

  • R. Schlosser, J. Kossmann, and M. Boissier, “Efficient scalable multiattribute index selection using recursive strategies,” in Proceedings - International Conference on Data Engineering, 2019, vol. 2019-April. doi: 10.1109/ICDE.2019.00113.

  • E. C. Freuder, “Progress towards the Holy Grail,” Constraints, vol. 23, no. 2, 2018, doi: 10.1007/s10601-017-9275-0.

  • I. Mami, R. Coletta, and Z. Bellahsene, “Modeling view selection as a constraint satisfaction problem,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, vol. 6861 LNCS, no. PART 2. doi: 10.1007/978-3-642-23091-2_33.

  • E. C. Freuder, “Constraints: The ties that bind,” in Proceedings of the National Conference on Artificial Intelligence, 2006, vol. 2.

  • J. G. Fages and C. Prud’Homme, “Making the first solution good!,” in Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, 2018, vol. 2017-November. doi: 10.1109/ICTAI.2017.00164.

  • C. Prud’homme, J.-G. Fages, and X. Lorca, “Choco Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING SAS (2016),” URL http://www. choco-solver. org, 2019.

  • P. Refalo, “Impact-based search strategies for constraint programming,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3258, 2004, doi: 10.1007/978-3-540-30201-8_41.

  • F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais, “Boosting systematic search by weighting constraints,” in Frontiers in Artificial Intelligence and Applications, 2004, vol. 110.

  • L. Michel and P. van Hentenryck, “Activity-based search for black-box constraint programming solvers,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, vol. 7298 LNCS. doi: 10.1007/978-3- 642-29828-8_15.

  • O. Council, “Apb-1 olap benchmark, release ii.” 1998. Accessed: May 07, 2022. [Online]. Available: http://www.olapcouncil.org

  • C. Lecoutre, L. Sais, S. Tabary, and V. Vidal, “Last conflict based reasoning,” Frontiers in Artificial Intelligence and Applications, vol. 141, 2006.

  • S. Gay, R. Hartert, C. Lecoutre, and P. Schaus, “Conflict ordering search for scheduling problems,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, vol. 9255. doi: 10.1007/978-3-319- 23219-5_10


Abstract Views: 193

PDF Views: 105




  • Effectively indexing Data Warehouses: A Constraint Programming Perspective

Abstract Views: 193  |  PDF Views: 105

Authors

Youcef Ariouat
LIM Laboratory, Amar Telidji University of Laghouat, Bp 37G, Ghardaia Road, Laghouat 03000,, Algeria
Benamor Ziani
LIM Laboratory, Amar Telidji University of Laghouat, Bp 37G, Ghardaia Road, Laghouat 03000,, Algeria
Youcef Ouinten
LIM Laboratory, Amar Telidji University of Laghouat, Bp 37G, Ghardaia Road, Laghouat 03000,, Algeria

Abstract


Data warehouses have become, nowadays, at the core of decisional systems. The Index Selection Problem (ISP) is a challenging problem in data warehouses physical design. Regarding the NP-hard nature of this problem, existing solutions rely heavily on heuristics which constitutes a major drawback. In this paper, we propose a novel exact approach to the ISP based on Constraint Programming (CP). We formulate the problem as a Constraint Optimization Problem in a declarative way, then its resolution is automatically supported by a generic CP solver. Our proposed approach has also the advantage of being declarative, flexible, and expandable as it allows incorporating various kinds of user preferences, expressed as constraints, as well as choosing or defining new search strategies. Experimental results confirm our expectations and show that our approach scales well enough to solve much larger realistic instances in a faster and more effective way compared to well-known state-of-the-art approximation approaches.

Keywords


data warehouses; bitmap join index; constraint programming; index selection problem; constraint optimization problem; decisional systems.

References