La fragmentation horizontale a été largement adoptée par la communauté des bases de données. Elle a une place à part entière dans la conception physique. Plusieurs systèmes de gestion de bases de données (SGBD) commerciaux ont proposé un langage de définition de données pour partitionner des tables relationnelles en utilisant différents modes. Dans ce papier, nous présentons d'abord l'évolution de la fragmentation ces dernières années au sein des SGBDs. Deuxièmement, nous étudions le problème de sélection de schéma de fragmentation d'un entrepôt de données relationnel, et nous montrons qu'il est NP-complet. Vu sa complexité, nous développons un algorithme de hill climbing (méthode de voisinage) pour sélectionner un schéma de fragmentation quasi optimal. Nous effectuons des expérimentations afin de comparer cet algorithme avec deux autres algorithmes: un génétique et un recuit simulé en utilisant un modèle de coûtmathématique. Finalement, nous effectuons une validation réelle de nos algorithmes sous ORACLE10g en utilisant les données issues du banc d'essai APB1.