Effectively indexing Data Warehouses: A Constraint Programming Perspective

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.