<figure><img src="image_1.png" /></figure>

HAL
open science

# Utilisation des vues matérialisées, des index et de la fragmentation dans la conception logique et physique d'un entrepôt de données

Ladjel Bellatreche

► To cite this version:

Ladjel Bellatreche. Utilisation des vues matérialisées, des index et de la fragmentation dans la conception logique et physique d'un entrepôt de données. Informatique [cs]. Université de Clermont II, 2000. Français. NNT: tel-04368306

HAL Id: tel-04368306

https://theses.hal.science/tel-04368306

Submitted on 31 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
UNIVERSITÉ DE CLERMONT-FERRAND II

ÉCOLE DOCTORALE

SCIENCES POUR L'INGÉNIEUR DE CLERMONT - FERRAND

THÈSE

présentée par

Ladjel BELLATRECHE

pour obtenir le grade de

DOCTEUR D'UNIVERSITÉ

Spécialité: INFORMATIQUE

Utilisation des Vues Matérialisées, des Index et
de la Fragmentation dans la Conception Logique
et Physique d'un Entrepôt de Données

Soutenue publiquement le 18 Décembre 2000 devant le jury:

M. Djamel ZIGHED

M. Henri BRIAND

M. Jacques KOULOUMDJIAN

M. Michel SCHNEIDER

M. Michel SIMONET

Président

Rapporteur

Rapporteur

Directeur de thèse

Co-Directeur de thèse
<figure><img src="image_2.png" /></figure>
Remerciements

Je tiens à remercier toutes les personnes qui ont contribué de manière directe ou indirecte à l'aboutissement de ce travail :

En premier lieu, je remercie vivement Monsieur Michel Schneider qui m'a permis d'effectuer cette thèse sous sa direction. J'ai particulièrement apprécié son enthousiasme, sa disponibilité et sa gentillesse. Son sens critique et son optimisme ont fait de cette thèse un travail motivant.

Je tiens à remercier Michel Simonet et Ana Simonet Directeur et Directeur adjoint de l'équipe OSIRIS du laboratoire TIMC-IMAG, pour m'avoir permis de trouver un bon créneau de recherche et pour m'avoir encadré tout au long de cette thèse.

Je remercie Monsieur Jacques Demongeot, Professeur à l'université Joseph Fourier, Directeur du laboratoire TIMC-IMAG, pour m'avoir facilité mon séjour à Hong Kong.

Je remercie également Kamalakar Karlapalem qui m'a accepté dans son équipe de recherche au Department of Computer Science, Hong Kong University of Science and Technology durant deux années avec un financement.

Je remercie Djamel ZIGHED, qui me fait l'honneur de présider ce jury.

Je remercie Messieurs Jacques KOULOUMDJIAN et Henri BRIAND d'avoir accepté d'être les rapporteurs de ma thèse. Leurs lectures et leurs remarques m'ont beaucoup aidé à finaliser ce document.

Je remercie Messieurs Mukesh Mohania, Qing Li, Gopal K. Bassak, Dimitris Papadias, Fred Lochovsky, et Zohra Bellahsène avec lesquels j'ai pris grand plaisir à travailler.

Je remercie mes collègues du laboratoire TIMC et tous les membres de l'équipe Osiris pour leur présence et leur soutien cordial.

Des pensées particulières vont à tous mes amis qui m'ont soutenu durant ces années.

Mille merci à mon père, ma mère, mes frères, mes soeurs, ma tante, son mari, mes cousins pour le soutien et l'aide qu'ils m'ont apportés durant mes études et sans qui ce travail n'aurait pas pu avoir lieu.

Enfin, une pensée très forte à ma femme et ma fille qui m'ont soutenu durant les moments difficiles.

Que tous ceux et celles que j'ai oubliés n'en recoivent pas moins ma gratitude.
# Résumé

Un entrepôt de données est une collection de données orientées sujet, intégrées, non volatiles et historisées, organisées pour supporter un processus d'aide à la décision. Typiquement ce processus est mené par l'intermédiaire de requêtes de type OLAP (On-Line Analytical processing). Ces requêtes sont généralement complexes car elles contiennent de nombreuses opérations de jointure et de regroupement et induisent des temps de réponse très élevés.

Dans ce contexte, nos travaux s'intéressent à diverses techniques d'amélioration des performances des entrepôts de données pour favoriser au mieux les requêtes. Ils interpellent deux niveaux de la conception des entrepôts : le niveau logique et le niveau physique. Au niveau logique, nous suggérons une méthodologie de fragmentation des structures de données de l'entrepôt. Au niveau physique, nous nous intéressons (1) à la définition et à la sélection d'index de jointure en présence des vues matérialisées et (2) à la distribution de l'espace disque entre les vues matérialisées et les index.

En ce qui concerne l'indexation, nous proposons une nouvelle technique d'indexation de jointure appelée index de graphe de jointure. Ces index permettent de réduire considérablement le coût d'exécution des requêtes. Une stratégie d'exécution des requêtes en présence de ces index est décrite, et un modèle de coût évaluant le coût d'exécution d'un ensemble de requêtes est développé. Nous formulons ensuite le problème de sélection d'index de jointure en présence d'une contrainte d'espace disque et nous proposons trois algorithmes de résolution optimaux ou quasi-optimaux (un algorithme exhaustif et deux algorithmes gloutons).

Le problème de la distribution de l'espace disque entre les vues matérialisées et les index a été posé assez récemment et peu de travaux l'ont interpellé. Dans ce mémoire, nous formulons ce problème dans le cas statique et dans le cas dynamique. Nous proposons un algorithme approché de résolution basé sur l'interaction entre deux agents, l'un opérant pour le compte des vues et l'autre pour le compte des index.

L'intérêt de la fragmentation est bien connu dans les bases de données relationnelles. Pour les entrepôts, nous justifions que la fragmentation horizontale apparaît plus spécialement appropriée et nous proposons une méthodologie de fragmentation horizontale pour décomposer un schéma d'entrepôt en étoile. Nous montrons ensuite que les algorithmes de fragmentation basés uniquement sur les fréquences d'accès des requêtes ne sont pas les plus intéressants. Nous suggérons deux nouveaux types d'algorithmes. Le premier type est dirigé par les affinités entre prédicats et le deuxième est dirigé par un modèle de coût. Pour cette dernière catégorie nous comparons un algorithme exhaustif recensant tous les schémas de fragmentation et un algorithme approximatif.

**Mots-Clefs** : Entrepôt de données, sélection des vues matérialisées, sélection d'index, interaction entre la sélection des vues et la sélection des index, distribution de l'espace entre les vues et les index, fragmentation, modèle de coût.
Abstract

A data warehouse is a subject-oriented, integrated, time-variant, non-volatile collection of data in support of a decision process. This process is usually performed with OLAP (On-Line Analytical processing) queries that aggregate, filter, and join the data in a variety of ways. Because the queries are often complex and the warehouse database is often very large, processing queries rapidly is a critical issue in the data warehousing environment.

Our work focuses on several optimization techniques to enhance query execution in data warehousing environments. These techniques concern the logical and the physical design levels of the data warehouse. At the logical design level, we suggest a fragmentation methodology of the data warehouse schema. At the physical design level, we are interested in (1) the definition and selection of join indexes in the presence of materialized views and (2) the problem of space distribution among views and indexes.

Concerning indexing, we propose a new join indexing technique called graph join index. These indexes reduce significantly the query processing cost. A query execution strategy using these indexes is described and a cost model to compute the cost of a set of queries is developed. We formulate the graph join index selection problem, and present three algorithms (one exhaustive and two greedy) which can provide good query performance under limited storage space for the indexes.

The space distribution problem among views and indexes was only recently introduced and therefore little work has been done on the subject. In this thesis, we formulate this problem in the static and dynamic cases. We propose an iterative approach to automatically distribute the storage space among views and indexes. This approach considers the interaction between indexes and views. Two agents (one for views and another for indexes) cater for this interaction. We extend this approach to handle changes dynamically.

Partitioning is a well known logical database design technique which was first applied to relational databases. We propound horizontal fragmentation as a better adapted technique for ROLAP data warehouses. To do this, we develop a fragmentation methodology to decompose the star schema of a data warehouse. Furthermore, we show that existing fragmentation algorithms are not suitable because of their complexity. We develop two families of algorithms: the first is based on affinities between predicates and the second is driven by a cost model. For the latter, we compare an exhaustive algorithm which enumerates all fragmentation schemas with an approximative algorithm.

**Keywords:** Data warehouse, materialized view selection, index selection, index, interaction between index and view selection, space distribution between views and indexes, fragmentation, cost model.
# Table des matières

<table><tr><td>1 Introduction générale</td><td>1</td></tr><tr><td>1.1 Entrepôt de données et data mining</td><td>2</td></tr><tr><td>1.2 OLTP et OLAP</td><td>2</td></tr><tr><td>1.3 Les caractéristiques des entrepôts de données</td><td>4</td></tr><tr><td>1.4 Architecture d'un entrepôt</td><td>4</td></tr><tr><td>1.5 Problématique abordée et résultats obtenus</td><td>5</td></tr><tr><td>1.5.1 Index de jointure pour les vues matérialisées</td><td>6</td></tr><tr><td>1.5.2 La répartition des ressources entre les index et les vues</td><td>7</td></tr><tr><td>1.5.3 La fragmentation</td><td>8</td></tr><tr><td>1.6 Organisation de la thèse</td><td>9</td></tr><tr><td>2 État de l'art</td><td>11</td></tr><tr><td>2.1 Introduction</td><td>11</td></tr><tr><td>2.2 Les modèles de données pour les entrepôts</td><td>12</td></tr><tr><td>2.2.1 Les modèles multidimensionnels</td><td>13</td></tr><tr><td>2.2.2 Les implémentations des modèles multidimensionnels</td><td>16</td></tr><tr><td>2.2.3 Les Systèmes HOLAP</td><td>20</td></tr><tr><td>2.3 Les vues matérialisées</td><td>20</td></tr><tr><td>2.3.1 La sélection des vues matérialisées</td><td>21</td></tr><tr><td>2.3.2 Les algorithmes de sélection des vues</td><td>23</td></tr><tr><td>2.3.3 Maintenance de vues matérialisées</td><td>27</td></tr><tr><td>2.3.4 La réécriture des requêtes</td><td>30</td></tr><tr><td>2.4 Les index</td><td>30</td></tr><tr><td>2.4.1 Les techniques d'indexation</td><td>31</td></tr><tr><td>2.4.2 Le problème de sélection des index</td><td>34</td></tr><tr><td>2.4.3 Discussion</td><td>35</td></tr><tr><td>2.4.4 La sélection des vues en présence des index</td><td>36</td></tr><tr><td>2.5 La fragmentation</td><td>38</td></tr><tr><td>2.5.1 Les types de fragmentation</td><td>39</td></tr><tr><td>2.5.2 Les contextes de la fragmentation</td><td>40</td></tr><tr><td>2.5.3 Les avantages et les inconvénients de la fragmentation</td><td>40</td></tr><tr><td>2.5.4 Les algorithmes de fragmentation verticale</td><td>41</td></tr><tr><td>2.5.5 Les algorithmes de fragmentation horizontale</td><td>44</td></tr><tr><td>2.5.6 La fragmentation horizontale dérivée</td><td>46</td></tr><tr><td>2.5.7 Les algorithmes de fragmentation mixte</td><td>48</td></tr><tr><td>2.5.8 Bilan et discussion</td><td>49</td></tr><tr><td>2.5.9 La fragmentation dans les bases de données objet</td><td>50</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>2.5.10</td>
      <td>La fragmentation dans les entrepôts de données</td>
      <td>51</td>
    </tr>
    <tr>
      <td>2.5.11</td>
      <td>La transparence de la fragmentation</td>
      <td>52</td>
    </tr>
    <tr>
      <td>2.6</td>
      <td>Le groupement</td>
      <td>52</td>
    </tr>
    <tr>
      <td>2.7</td>
      <td>Incidences pratiques</td>
      <td>53</td>
    </tr>
    <tr>
      <td>2.7.1</td>
      <td>Partitionnement des données</td>
      <td>53</td>
    </tr>
    <tr>
      <td>2.7.2</td>
      <td>Vues matérialisées</td>
      <td>54</td>
    </tr>
    <tr>
      <td>2.7.3</td>
      <td>Interaction entre les index et les vues</td>
      <td>54</td>
    </tr>
    <tr>
      <td>2.8</td>
      <td>Conclusion</td>
      <td>55</td>
    </tr>
    <tr>
      <td><b>3</b></td>
      <td><b>Les index de jointure pour les vues matérialisées</b></td>
      <td><b>57</b></td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Introduction</td>
      <td>57</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Objectifs visés</td>
      <td>59</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>La sélection des vues matérialisées</td>
      <td>61</td>
    </tr>
    <tr>
      <td>3.3.1</td>
      <td>Concepts et définitions</td>
      <td>61</td>
    </tr>
    <tr>
      <td>3.3.2</td>
      <td>Motivation de l'algorithme sélect_vue</td>
      <td>63</td>
    </tr>
    <tr>
      <td>3.3.3</td>
      <td>Les étapes principales de sélect_vue</td>
      <td>65</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>Le processus de réécriture des requêtes</td>
      <td>70</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>Le problème des jointures et les index de jointure</td>
      <td>72</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>Une stratégie d'exécution de requêtes</td>
      <td>75</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>Un modèle de coût</td>
      <td>77</td>
    </tr>
    <tr>
      <td>3.7.1</td>
      <td>Les composantes d'un modèle de coût</td>
      <td>77</td>
    </tr>
    <tr>
      <td>3.7.2</td>
      <td>Les statistiques et les estimations</td>
      <td>77</td>
    </tr>
    <tr>
      <td>3.7.3</td>
      <td>Les méthodes d'accès</td>
      <td>79</td>
    </tr>
    <tr>
      <td>3.7.4</td>
      <td>Le modèle de coût dans notre contexte</td>
      <td>79</td>
    </tr>
    <tr>
      <td>3.7.5</td>
      <td>La maintenance des IGJs</td>
      <td>82</td>
    </tr>
    <tr>
      <td>3.7.6</td>
      <td>Le coût de stockage des IGJs</td>
      <td>83</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>Les algorithmes de sélection des IGJs</td>
      <td>83</td>
    </tr>
    <tr>
      <td>3.8.1</td>
      <td>La complexité de la sélection des IGJs</td>
      <td>83</td>
    </tr>
    <tr>
      <td>3.8.2</td>
      <td>La formulation du problème de sélection des IGJs</td>
      <td>83</td>
    </tr>
    <tr>
      <td>3.8.3</td>
      <td>Les algorithmes de sélection des IGJs</td>
      <td>84</td>
    </tr>
    <tr>
      <td>3.9</td>
      <td>Evaluation des index de graphe de jointure</td>
      <td>89</td>
    </tr>
    <tr>
      <td><b>4</b></td>
      <td><b>Interaction entre les vues matérialisées et les index</b></td>
      <td><b>93</b></td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Introduction</td>
      <td>93</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Motivations</td>
      <td>94</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Le cas statique</td>
      <td>95</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Le cas dynamique</td>
      <td>96</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>L'intuition de notre approche de distribution</td>
      <td>97</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Le problème de la distribution statique</td>
      <td>99</td>
    </tr>
    <tr>
      <td>4.4.1</td>
      <td>La formulation du problème</td>
      <td>100</td>
    </tr>
    <tr>
      <td>4.4.2</td>
      <td>L'architecture de notre approche</td>
      <td>101</td>
    </tr>
    <tr>
      <td>4.4.3</td>
      <td>Les étapes de notre algorithme</td>
      <td>101</td>
    </tr>
    <tr>
      <td>4.4.4</td>
      <td>La solution initiale</td>
      <td>101</td>
    </tr>
    <tr>
      <td>4.4.5</td>
      <td>Le processus d'amélioration de la solution initiale</td>
      <td>102</td>
    </tr>
    <tr>
      <td>4.4.6</td>
      <td>Le test d'arrêt</td>
      <td>106</td>
    </tr>
    <tr>
      <td>4.4.7</td>
      <td>La détermination de l'espion privilégié</td>
      <td>106</td>
    </tr>
    <tr>
      <td>4.4.8</td>
      <td>Description de l'algorithme</td>
      <td>106</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>4.4.9</td>
      <td>Les caractéristiques de notre approche</td>
      <td>107</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>La problème de la distribution dynamique</td>
      <td>107</td>
    </tr>
    <tr>
      <td>4.5.1</td>
      <td>Position du problème</td>
      <td>107</td>
    </tr>
    <tr>
      <td>4.5.2</td>
      <td>L'algorithme répartition dynamique</td>
      <td>109</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Evaluation</td>
      <td>109</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>Conclusion et perspectives</td>
      <td>113</td>
    </tr>
    <tr>
      <td>5</td>
      <td>La fragmentation dans les entrepôts de données</td>
      <td>115</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Position du problème</td>
      <td>116</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Exemple d'illustration: service de ventes d'un magasin</td>
      <td>118</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Les principes de notre méthode de fragmentation</td>
      <td>119</td>
    </tr>
    <tr>
      <td>5.3.1</td>
      <td>Les alternatives</td>
      <td>119</td>
    </tr>
    <tr>
      <td>5.3.2</td>
      <td>Une méthodologie de fragmentation</td>
      <td>121</td>
    </tr>
    <tr>
      <td>5.3.3</td>
      <td>Complexité de la fragmentation</td>
      <td>124</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Sélection des tables de dimensions</td>
      <td>125</td>
    </tr>
    <tr>
      <td>5.4.1</td>
      <td>Principes</td>
      <td>125</td>
    </tr>
    <tr>
      <td>5.4.2</td>
      <td>Un algorithme "glouton"</td>
      <td>126</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Les propriétés de la fragmentation</td>
      <td>127</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Graphe de jointure simple</td>
      <td>127</td>
    </tr>
    <tr>
      <td>5.5.2</td>
      <td>Complétude, reconstruction, et disjonction</td>
      <td>128</td>
    </tr>
    <tr>
      <td>5.5.3</td>
      <td>Identification des fragments participants à une requête</td>
      <td>129</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Modèle de coût pour l'exécution des requêtes</td>
      <td>131</td>
    </tr>
    <tr>
      <td>5.7</td>
      <td>Evaluation d'un entrepôt fragmenté</td>
      <td>132</td>
    </tr>
    <tr>
      <td>5.8</td>
      <td>Problèmes ouverts</td>
      <td>135</td>
    </tr>
    <tr>
      <td>5.8.1</td>
      <td>Principes des data marts</td>
      <td>135</td>
    </tr>
    <tr>
      <td>5.8.2</td>
      <td>La fragmentation et l'adaptation des vues</td>
      <td>138</td>
    </tr>
    <tr>
      <td>5.9</td>
      <td>Conclusion</td>
      <td>138</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Nouveaux algorithmes pour la fragmentation horizontale</td>
      <td>141</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Introduction</td>
      <td>141</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Un algorithme dirigé par les affinités</td>
      <td>143</td>
    </tr>
    <tr>
      <td>6.2.1</td>
      <td>Les phases de l'algorithme des affinités</td>
      <td>143</td>
    </tr>
    <tr>
      <td>6.2.2</td>
      <td>Complexité de l'algorithme des affinités</td>
      <td>151</td>
    </tr>
    <tr>
      <td>6.2.3</td>
      <td>Les règles de correction</td>
      <td>151</td>
    </tr>
    <tr>
      <td>6.2.4</td>
      <td>Bilan de cette section</td>
      <td>152</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Les algorithmes dirigés par un modèle de coût</td>
      <td>152</td>
    </tr>
    <tr>
      <td>6.3.1</td>
      <td>Motivations</td>
      <td>152</td>
    </tr>
    <tr>
      <td>6.3.2</td>
      <td>Le modèle de coût et les algorithmes de fragmentation</td>
      <td>153</td>
    </tr>
    <tr>
      <td>6.3.3</td>
      <td>Le générateur de schémas</td>
      <td>154</td>
    </tr>
    <tr>
      <td>6.3.4</td>
      <td>Le modèle de coût</td>
      <td>158</td>
    </tr>
    <tr>
      <td>6.3.5</td>
      <td>L'algorithme exhaustif</td>
      <td>158</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>L'algorithme approximatif</td>
      <td>160</td>
    </tr>
    <tr>
      <td>6.4.1</td>
      <td>Les étapes de l'algorithme</td>
      <td>160</td>
    </tr>
    <tr>
      <td>6.4.2</td>
      <td>La détermination de la solution initiale</td>
      <td>161</td>
    </tr>
    <tr>
      <td>6.4.3</td>
      <td>Un mécanisme d'amélioration de la solution initiale</td>
      <td>161</td>
    </tr>
    <tr>
      <td>6.4.4</td>
      <td>Le test d'arrêt</td>
      <td>168</td>
    </tr>
    <tr>
      <td>6.4.5</td>
      <td>Description de l'algorithme</td>
      <td>168</td>
    </tr>
  </tbody>
</table>
<table><tr><td>6.5</td><td>Evaluation des trois algorithmes</td><td>168</td></tr><tr><td>6.5.1</td><td>La première expérimentation</td><td>170</td></tr><tr><td>6.5.2</td><td>La deuxième expérimentation</td><td>170</td></tr><tr><td>6.5.3</td><td>Discussion</td><td>170</td></tr><tr><td>7</td><td>Conclusion et Perspectives</td><td>173</td></tr><tr><td>7.1</td><td>Conclusion</td><td>173</td></tr><tr><td>7.1.1</td><td>Les index de jointure en présence des vues matérialisées</td><td>173</td></tr><tr><td>7.1.2</td><td>Interaction entre les problèmes de sélection des vues et de sélection d'index</td><td>173</td></tr><tr><td>7.1.3</td><td>La fragmentation horizontale</td><td>174</td></tr><tr><td>7.1.4</td><td>De nouveaux algorithmes de fragmentation horizontale</td><td>174</td></tr><tr><td>7.2</td><td>Perspectives</td><td>175</td></tr><tr><td>7.2.1</td><td>Autres types d'algorithmes</td><td>175</td></tr><tr><td>7.2.2</td><td>Utilisation d'une représentation binaire des index</td><td>175</td></tr><tr><td>7.2.3</td><td>La sélection incrémentale des vues et des index</td><td>175</td></tr><tr><td>7.2.4</td><td>La prise en considération du coût de maintenance</td><td>175</td></tr><tr><td>7.2.5</td><td>La fragmentation dynamique</td><td>175</td></tr><tr><td>7.2.6</td><td>La fragmentation d'un schéma en flocon de neige</td><td>176</td></tr><tr><td>7.2.7</td><td>Evaluation des algorithmes par benchmarks</td><td>176</td></tr></table>
Liste des figures

<table><tr><td>1.1</td><td>L'organigramme d'analyse des données dans une entreprise</td><td>2</td></tr><tr><td>1.2</td><td>Le data mining et les entrepôts de données</td><td>3</td></tr><tr><td>1.3</td><td>Architecture conceptuelle d'un entrepôt de données</td><td>5</td></tr><tr><td>2.1</td><td>Cube de données</td><td>13</td></tr><tr><td>2.2</td><td>Le cube VENTES</td><td>15</td></tr><tr><td>2.3</td><td>Systèmes MOLAP</td><td>16</td></tr><tr><td>2.4</td><td>Systèmes ROLAP</td><td>17</td></tr><tr><td>2.5</td><td>Un exemple d'un schéma en étoile</td><td>19</td></tr><tr><td>2.6</td><td>Un exemple d'un schéma en flocon de neige</td><td>20</td></tr><tr><td>2.7</td><td>Les types de PSV</td><td>22</td></tr><tr><td>2.8</td><td>Le processus de sélection des vues matérialisées</td><td>22</td></tr><tr><td>2.9</td><td>Le principe de base de la sélection de Yang et al. [YKL97]</td><td>24</td></tr><tr><td>2.10</td><td>Treillis des vues</td><td>25</td></tr><tr><td>2.11</td><td>Index binaire</td><td>32</td></tr><tr><td>2.12</td><td>Index de projection</td><td>32</td></tr><tr><td>2.13</td><td>Index de jointure pour l'équi-jointure Employé.Ville = Département.Ville</td><td>33</td></tr><tr><td>2.14</td><td>L'architecture de l'outil de sélection d'index</td><td>34</td></tr><tr><td>2.15</td><td>Entrepôt avec une vue primaire</td><td>37</td></tr><tr><td>2.16</td><td>Entrepôt avec une vue de support</td><td>37</td></tr><tr><td>2.17</td><td>Principe général de la méthode de Hammer et Niamir</td><td>42</td></tr><tr><td>2.18</td><td>Les différents types de graphe de jointure</td><td>47</td></tr><tr><td>2.19</td><td>Le principe général de la fragmentation mixte</td><td>48</td></tr><tr><td>2.20</td><td>Les différents algorithmes pour la fragmentation horizontale</td><td>49</td></tr><tr><td>3.1</td><td>Les trois scénarios d'exécution d'une requête</td><td>58</td></tr><tr><td>3.2</td><td>L'indexation dans les trois scénarios</td><td>59</td></tr><tr><td>3.3</td><td>Les étapes de conception physique de l'entrepôt</td><td>60</td></tr><tr><td>3.4</td><td>Les opérateurs relationnels</td><td>62</td></tr><tr><td>3.5</td><td>L'arbre algébrique correspondant à la requête Q</td><td>63</td></tr><tr><td>3.6</td><td>Les arbres algébriques individuels</td><td>64</td></tr><tr><td>3.7</td><td>L'ensemble des requêtes utilisées dans l'évaluation de la fragmentation</td><td>66</td></tr><tr><td>3.8</td><td>Le PMEV correspondant aux cinq requêtes de la Figure 3.7</td><td>69</td></tr><tr><td>3.9</td><td>Le processus de réécriture</td><td>71</td></tr><tr><td>3.10</td><td>La matrice de réécriture</td><td>71</td></tr><tr><td>3.11</td><td>Exemple de graphe d'une base de données</td><td>73</td></tr><tr><td>3.12</td><td>Graphe de jointure</td><td>75</td></tr><tr><td>3.13</td><td>La stratégie d'exécution d'une jointure en présence d'un IJE</td><td>75</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>3.14</td>
      <td>Le graphe de jointure étiqueté</td>
      <td>85</td>
    </tr>
    <tr>
      <td>3.15</td>
      <td>Un exemple de déroulement de l'AGS1</td>
      <td>88</td>
    </tr>
    <tr>
      <td>3.16</td>
      <td>La matrice de réécriture</td>
      <td>90</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Le processus de sélection des vues et des index</td>
      <td>94</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>La formulation séquentielle de PSV et PSI: le cas de A ≠ B</td>
      <td>95</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>La formulation séquentielle de PSV et PSI: le cas A = B</td>
      <td>95</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>L'intuition de notre approche itérative</td>
      <td>98</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Les éléments de notre algorithme statique et leurs interactions</td>
      <td>100</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>La matrice de réécriture initiale</td>
      <td>104</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>La matrice de réécriture après l'exécution de l'espion des index</td>
      <td>104</td>
    </tr>
    <tr>
      <td>4.8</td>
      <td>Le PMEV pour les requêtes: Q<sub>1</sub>, Q<sub>2</sub> and Q<sub>3</sub></td>
      <td>110</td>
    </tr>
    <tr>
      <td>4.9</td>
      <td>Les effets des espions dans le cas des cinq requêtes</td>
      <td>111</td>
    </tr>
    <tr>
      <td>4.10</td>
      <td>Les effets des espions dans le cas des trois requêtes</td>
      <td>111</td>
    </tr>
    <tr>
      <td>4.11</td>
      <td>La distribution d'espace pour les cinq requêtes</td>
      <td>112</td>
    </tr>
    <tr>
      <td>4.12</td>
      <td>La distribution d'espace pour les trois requêtes</td>
      <td>112</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>L'ensemble des requêtes utilisées dans l'évaluation de la fragmentation</td>
      <td>120</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Evolution des coûts en fonction du nombre de fragments</td>
      <td>125</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>L'algorithme glouton</td>
      <td>127</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>La jointure simple dans un schéma en étoile</td>
      <td>128</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Identification de(s) sous-schéma(s) en étoile</td>
      <td>131</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>L'effet de variation de la taille de la table des faits</td>
      <td>135</td>
    </tr>
    <tr>
      <td>5.7</td>
      <td>L'approche ascendante</td>
      <td>137</td>
    </tr>
    <tr>
      <td>5.8</td>
      <td>L'approche descendante</td>
      <td>137</td>
    </tr>
    <tr>
      <td>5.9</td>
      <td>Analogie entre la conception des base de données réparties et la conception de data marts</td>
      <td>138</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Le modèle de coût comme outil de sélection</td>
      <td>142</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>La matrice d'usage des prédicats</td>
      <td>144</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>La signification de la valeur numérique</td>
      <td>145</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>La signification de la valeur des implications</td>
      <td>146</td>
    </tr>
    <tr>
      <td>6.5</td>
      <td>La matrice d'affinité des prédicats</td>
      <td>146</td>
    </tr>
    <tr>
      <td>6.6</td>
      <td>Les ensembles de prédicats générés par l'approche graphique</td>
      <td>147</td>
    </tr>
    <tr>
      <td>6.7</td>
      <td>La matrice d'usage des attributs</td>
      <td>150</td>
    </tr>
    <tr>
      <td>6.8</td>
      <td>Les principales composantes des algorithmes dirigés par un modèle de coût</td>
      <td>154</td>
    </tr>
    <tr>
      <td>6.9</td>
      <td>Les étapes du processus de génération des schémas de fragmentation</td>
      <td>155</td>
    </tr>
    <tr>
      <td>6.10</td>
      <td>Le mécanisme d'amélioration du schéma initial</td>
      <td>161</td>
    </tr>
    <tr>
      <td>6.11</td>
      <td>Les SDSs des attributs de fragmentation</td>
      <td>163</td>
    </tr>
    <tr>
      <td>6.12</td>
      <td>Un exemple de représentation de fragments dans le cas de deux attributs</td>
      <td>163</td>
    </tr>
    <tr>
      <td>6.13</td>
      <td>Un exemple de représentation de fragments dans le cas de trois attributs</td>
      <td>165</td>
    </tr>
    <tr>
      <td>6.14</td>
      <td>Nombre de fragments vs. coût total d'exécution de requêtes</td>
      <td>171</td>
    </tr>
  </tbody>
</table>
## Liste des tables

<table><tr><td>1.1</td><td>Base de données Vs Entrepôt de données</td><td>4</td></tr><tr><td>2.1</td><td>ROLAP vs. MOLAP</td><td>18</td></tr><tr><td>2.2</td><td>La description de l'algorithm de Blakeley et al. [BLT86]</td><td>28</td></tr><tr><td>3.1</td><td>Les paramètres de l'entrepôt</td><td>80</td></tr><tr><td>3.2</td><td>Les paramètres des index</td><td>80</td></tr><tr><td>3.3</td><td>Les paramètres physiques</td><td>80</td></tr><tr><td>3.4</td><td>Les paramètres utilisés dans l'expérience</td><td>89</td></tr><tr><td>3.5</td><td>L'ensemble de IGJs et leurs tailles</td><td>90</td></tr><tr><td>3.6</td><td>Le coût de stockage des IGJs et le coût d'évaluation des requêtes</td><td>91</td></tr><tr><td>3.7</td><td>Coût normalisé d'évaluation des requêtes</td><td>91</td></tr><tr><td>4.1</td><td>Les vues matérialisées sélectionnées et leurs tailles</td><td>99</td></tr><tr><td>4.2</td><td>Réduction du coût dû à l'espion des index</td><td>100</td></tr><tr><td>4.3</td><td>La description des solutions pour les cinq requêtes</td><td>110</td></tr><tr><td>4.4</td><td>La description des solutions pour les trois requêtes</td><td>110</td></tr><tr><td>4.5</td><td>Les vues sélectionnées et leurs tailles pour les cinq requêtes après mises à jour</td><td>113</td></tr><tr><td>5.1</td><td>Les tables et leurs prédicats respectifs</td><td>123</td></tr><tr><td>5.2</td><td>Les fragments de la table des faits</td><td>124</td></tr><tr><td>5.3</td><td>La table de spécification de la fragmentation</td><td>129</td></tr><tr><td>5.4</td><td>La spécification de la fragmentation (cas 2)</td><td>133</td></tr><tr><td>5.5</td><td>La spécification de la fragmentation (cas 3)</td><td>133</td></tr><tr><td>5.6</td><td>Le coût d'exécution des requêtes sous l'hypothèse HML</td><td>134</td></tr><tr><td>5.7</td><td>Le coût d'exécution des requêtes sous hypothèse HMM</td><td>135</td></tr><tr><td>6.1</td><td>Les six prédicats</td><td>156</td></tr><tr><td>6.2</td><td>La complexité du nombre de schémas</td><td>160</td></tr></table>
Liste des algorithmes

<table><tr><td>1</td><td>Algorithme de Harinarayan et al. [HRU96]</td><td>26</td></tr><tr><td>2</td><td>Algorithme générant des prédicats minimaux et complets</td><td>45</td></tr><tr><td>3</td><td>L'algorithme de fragmentation primaire de Özsu et al.</td><td>46</td></tr><tr><td>4</td><td>Les étapes de sélect_vue</td><td>69</td></tr><tr><td>5</td><td>Les étapes de AGS1</td><td>86</td></tr><tr><td>6</td><td>Les étapes de AGSK</td><td>88</td></tr><tr><td>7</td><td>La procédure espion-index-vol-espace-vue</td><td>104</td></tr><tr><td>8</td><td>La procédure espion-vues-vol-espace-index</td><td>105</td></tr><tr><td>9</td><td>Algorithme statique</td><td>107</td></tr><tr><td>10</td><td>étendre une composante incomplète</td><td>149</td></tr><tr><td>11</td><td>La description de l'algorithme exhaustif</td><td>159</td></tr><tr><td>12</td><td>L'algorithme approximatif</td><td>169</td></tr></table>
# Notations

Description des symboles utilisés dans la thèse.

## Opérations relationnelles:

⊠ L'opération de jointure

⊝ L'opération de semi-jointure

σ L'opération de sélection

π L'opération de projection

## Notations:

||T|| Cardinalité de la table T

|T| Nombre de page de la table T

PSV Problème de sélection de vues

PSI Problème de sélection d'index

ASV Algorithme de sélection des vues

ASI Algorithme de sélection des index

IGJ Index de graphe de jointure

IJE Index de jointure en étoile

PMEV Plan multiple d'exécution des vues

AGS1 Algorithme glouton sélectionnant un seul IGJ

AGSK Algorithme glouton sélectionnant K IGJs

CT Coût total d'exécution des requêtes

CTG Coût total d'exécution des requêtes en utilisant l'index G

S Espace global

S<sup>V</sup> Espace réservé aux vues matérialisées

S<sup>I</sup> Espace réservé aux index

W Matrice de réécriture

RI Matrice requête-index

VPPT Vue de plus petite taille

VMFU Vue la moins fréquemment utilisée

IMFU Index le moins fréquemment utilisé

PGI Plus grand index

SDS Sous domaine stable

Dist Distance de Hamming

## Logique des prédicats :

V disjonction

∧ conjonction

⇒ implication
# Chapitre 1

## Introduction générale

L'informatique a connu et connaît aujourd'hui encore un essor spectaculaire. Cette évolution est due aux nombreux services qu'elle offre aux usagers et aux entreprises. Grâce à l'informatique, ces dernières ont pu améliorer leur contrôle sur leurs informations et leurs processus de traitement de l'information. Elles ont également augmenté leur productivité en gérant efficacement et rapidement les diverses informations relatives à la production, au marketing et aux ressources humaines. Les aspects transactionnels sont au coeur de ces systèmes informatiques développés depuis un demi-siècle, et de vastes volumes de données ont été constitués. Ces données représentent maintenant une véritable mine de connaissances sur les produits, les clients, les fournisseurs et les opérations de l'entreprise. Cependant, la nature éphémère et hétérogène des données opérationnelles amassées par ces systèmes prive l'entreprise d'une grande partie des connaissances. Pour accroître ses performances, l'entreprise doit mettre en place de nouvelles technologies décisionnelles pour obtenir une meilleure compréhension des informations disponibles et définir des indicateurs pertinents pour faciliter les prises de décision opérationnelles.

Une solution consiste à utiliser des médiateurs permettant d'accéder à toutes les données de l'entreprise depuis un poste client [GO96]. Cependant cette approche est limitée par la taille du poste client et par l'accès aux données distribuées nécessaires. Une autre approche, l'entrepôt de données (**data warehouse**) consiste à regrouper les informations disséminées, après les avoir prétraitées, au sein d'une base de synthèse unique, intégrée par sujet. En extrayant par **des requêtes** des parties de cette base, il devient possible pour les dirigeants de l'entreprise **d'analyser** les données et de prendre les **meilleures décisions rapidement** [GO96].

Les exemples les plus parlants pour ce genre d'applications se trouvent dans le domaine de la grande distribution, les ventes par correspondance et les compagnies téléphoniques (comme AT&T). Il est important dans ces domaines de regrouper les informations sur les ventes pour déterminer les produits à succès, mieux suivre les tendances, détecter les habitudes d'achat des clients et leurs préférences par secteur géographique. De telles applications nécessitent un accès interactif à des données issues d'applications variées, intégrant l'historique, à partir de logiciels d'aide à la décision.
<figure><img src="image_3.png" /><figcaption>FIG. 1.1: L'organigramme d'analyse des données dans une entreprise</figcaption></figure>

## 1.1 Entrepôt de données et data mining

C'est une nécessité pour toute entreprise de recueillir des informations variées sur le comportement de leurs clients (préférences, habitudes) afin de mener diverses analyses et d'en déduire des modalités d'actions (voir Figure 1.1). L'analyse par exemple des transactions de vente d'un supermarché permettra d'étudier les habitudes des clients, en fonction de quoi il sera possible de réorganiser les rayons afin d'améliorer les ventes.

L'extraction de connaissances dans les bases de données (data mining)<fnref n="1" /> désigne le processus non-trivial d'extraction d'informations implicites, précédemment inconnues et potentiellement utiles concernant les données stockées dans les bases de données [PS91]. Les travaux en ce domaine sont motivés par l'évolution très rapide des techniques de génération (telles que les techniques de lecture des codes barres des articles achetés en supermarché) et de stockage de données (augmentation de la capacité et diminution des coûts des disques) qui ont permis la création par de nombreuses entreprises de **bases de données volumineuses** (entrepôts) concernant leurs activités commerciales. L'extraction des données d'un entrepôt de données se fait à l'aide des **requêtes ad-hoc, complexes, exigeant beaucoup d'agrégations et de jointures.** Pour conclure, nous pouvons dire que l'entrepôt de données constitue une source indispensable pour l'extraction des connaissances.

## 1.2 OLTP et OLAP

Les bases de données des systèmes existants, de type On-line Transaction Processing (OLTP) (appelés systèmes transactionnels), permettent d'enregistrer, de chercher et de gérer des données variées et de réaliser des transactions sur ces données

<footnote n="1">¹Le terme data mining est fréquemment utilisé comme synonyme de Knowledge Discovery in Databases, introduit par Shapiro en 1989.</footnote>
<figure><img src="image_4.png" /><figcaption>FIG. 1.2: Le data mining et les entrepôts de données</figcaption></figure>

(lectures, mises à jour, etc). Ces systèmes ont bien répondu aux besoins en gestion transactionnelle de l'information. Les bases de données de type OLTP sont généralement créées pour une large communauté d'utilisateurs. Chaque utilisateur connaît ses besoins, et avec une seule transaction il accède à un petit nombre de n-uplets. L'objectif principal de ces bases de données est de maximiser le débit des transactions et de minimiser les conflits concurrentiels.

Avec l'évolution de la société, les besoins ont évolué: l'accroissement des volumes de données a induit des changements dans la vision de l'information et suscité une sophistication des traitements [Mar98]. Maintenant, les entreprises souhaitent avoir un point de vue global pour manipuler des sources de données hétérogènes, sur lesquelles des traitements analytiques sont associés aux traitements transactionnels. Cependant, les systèmes transactionnels sont limités au niveau des fonctions d'aide à la décision [Inm92] et ne peuvent pas extraire toutes les informations nécessaires pour prendre une décision rapide et intelligente permettant une gestion efficace d'une organisation. Par exemple, il est difficile pour les systèmes transactionnels de répondre à la question suivante: quels sont les types de fournisseurs du produit 'x' à Grenoble en 1997 et comment se différencient-ils de ceux de l'année dernière?

L'objectif principal des entrepôts de données est d'être une plate-forme commune pour supporter les opérations de type OLAP (On-Line Analytical Processing). Codd et al. [CCS93] ont décrit ces opérations comme des analyses dynamiques nécessaires pour la création, la manipulation, l'animation et la synthèse des informations reflétant la vision de l'analyste. Les entrepôts de données sont souvent conçus pour les opérations (ou requêtes) de type OLAP. Ces requêtes accèdent généralement à un grand volume de données et effectuent beaucoup d'opérations de jointure et d'agréation. Les entrepôts de données opèrent dans un environnement où les requêtes de lecture sont plus fréquentes que les requêtes d'écriture (query-centric). Dans les entrepôts le temps de réponse est le facteur de performance primordial à satisfaire.

Le data mining a une forte relation avec OLAP, dont les objectifs sont similaires, mais il faut cependant souligner une différence essentielle. OLAP traite les données, alors que le data mining vise également à extraire des connaissances à partir de ces données (règles d'association par exemple [Pas00]).

La Table 1.1 résume les différences principales entre les bases de données de type OLTP et les entrepôts de données [Men97].
<table><caption>TAB. 1.1: Base de données Vs Entrepôt de données</caption><thead><tr><th>Caractéristique</th><th>Base de données</th><th>Entrepôt de données</th></tr></thead><tbody><tr><td>Données</td><td>Courantes</td><td>Historiques</td></tr><tr><td>Usage</td><td>Support de l'opération de l'entreprise</td><td>Support de l'analyse de l'entreprise</td></tr><tr><td>Unité de travail</td><td>Transaction</td><td>Requête</td></tr><tr><td>Nombre de données accédées</td><td>Dizaines</td><td>Millions</td></tr><tr><td>Mode d'accès</td><td>Lecture/écriture</td><td>Lecture</td></tr><tr><td>Requête</td><td>Simple Prédéterminée</td><td>Complexe Ad-hoc</td></tr><tr><td>Type d'utilisateur</td><td>Employé</td><td>Décideur</td></tr><tr><td>Nombre d'utilisateurs</td><td>Mille</td><td>Cent</td></tr></tbody></table>

## 1.3 Les caractéristiques des entrepôts de données

Bill Inmon dans son ouvrage de référence "Using the Data Warehouse" [Inm92] définit l'entrepôt de la façon suivante : "l'entrepôt de données est une collection de données orientées sujet, intégrées, non volatiles et historisées, organisées pour le support d'un processus d'aide à la décision". Nous en précisons les caractéristiques ci-dessous.

Les données d'un entrepôt de données possèdent les caractéristiques suivantes:

- **Orientation sujet:** Les données d'un entrepôt s'organisent par sujets ou thèmes. Pour ce qui est du domaine commercial d'une entreprise par exemple, nous aurons des données sur la production, les ventes, le marketing et la finance. Cette organisation permet de rassembler toutes les données pertinentes et nécessaires pour toutes les analyses relatives à ce thème.

- **Intégration:** Les données d'un entrepôt de données sont le résultat de l'intégration de données en provenance de plusieurs sources. Ainsi, toutes les données nécessaires pour réaliser une analyse particulière se trouvent dans l'entrepôt de données. L'intégration est le résultat d'un processus qui peut devenir très complexe compte tenu de l'hétérogénéité des sources.

- **Historique:** Les données d'un entrepôt de données représentent l'activité d'une entreprise pendant une longue période, d'où l'importance de gérer les différentes valeurs qu'une donnée prend au cours du temps. Cette caractéristique donne la possibilité de suivre une donnée dans le temps pour analyser ses variations.

- **Non-Volatilité:** Les données chargées dans l'entrepôt de données sont surtout utilisées en interrogation et ne peuvent pas être modifiées, sauf cas particulier (rafraîchissement par exemple).

## 1.4 Architecture d'un entrepôt

La Figure 1.3 montre l'architecture conceptuelle d'un entrepôt de données. L'entrepôt stocke des données, brutes ou modifiées provenant des sources d'informations
<figure><img src="image_5.png" /><figcaption>FIG. 1.3: Architecture conceptuelle d'un entrepôt de données</figcaption></figure>

(qui peuvent être internes ou externes, et souvent distribuées, autonomes et hétérogènes). Avant d'être chargées dans l'entrepôt, les données sélectionnées doivent être extraites des sources et soigneusement épurées, pour éliminer les erreurs et réconcilier les différences sémantiques (ce processus est appelé nettoyage). Une fois ces données nettoyées, elles seront intégrées dans l'entrepôt, qui contient des données détaillées, des vues matérialisées et des données multidimensionnelles. Lors de changements dans les données des sources, ces derniers sont propagés vers l'entrepôt. Ce processus est connu sous le nom de rafraîchissement [WB97]. Les méta-données contiennent des informations concernant la création, la gestion, et l'usage de l'entrepôt. Les méta-données sont stockées dans un répertoire différent de celui de l'entrepôt. Elles sont considérées comme un pont entre les utilisateurs et l'entrepôt. L'entrepôt est accédé par le serveur OLAP afin de présenter les données sous forme multidimensionnelle aux clients pour des besoins d'analyses et des besoins informationnels (data mining, rapport, etc.). Le serveur OLAP interprète les requêtes des clients et les convertit en requêtes d'accès à l'entrepôt ou aux sources opérationnelles. Finalement, le serveur OLAP fournit des vues multidimensionnelles des données aux outils de front end, et ces derniers formatent les données conformément aux besoins des usagers.

## 1.5 Problématique abordée et résultats obtenus

Comme nous l'avons déjà mentionné, la taille des entrepôts de données peut être très grande. Par exemple, *Sagent Technology*, dont les produits sont utilisés pour construire des entrepôts de données, est régulièrement confronté à des volumes de 100 Gigabytes ou plus, et la chaîne de supermarchés *Wal*Mart aux U.S.A. gère un entrepôt (créé en 1988) de 2,7 Tera octets sur une machine *TerraData* avec 365 processeurs d'accès [MLWZ98]. Le processus d'analyse de données s'appuie souvent sur des requêtes qui regroupent et filtrent des données de différentes formes. Compte tenu de la nature interactive des entrepôts de données, la nécessité d'avoir un temps de réponse rapide est un objectif critique [CY99a, OQ97]. Des délais trop longs sont inacceptables dans la plupart des systèmes décisionnels, puisqu'ils peuvent diminuer la productivité. L'exigence courante est un temps de réponse ne dépassant pas quelques *secondes* ou quelques *minutes* [Gup99]. Sans *technique d'optimisation de*
requêtes, l’interrogation d’un entrepôt de données serait complexe, et le traitement de ces requêtes pourrait prendre des heures, voire des jours [OQ97].

Les travaux concernant l'optimisation des performances des requêtes décisionnelles sont principalement basés sur des techniques éprouvées, et héritées des bases de données relationnelles/objets. Les éléments suivants influencent notablement les performances des requêtes (nous y reviendrons plus en détail dans le Chapitre 2):

- les vues matérialisées (sélection et maintenance),

- le calcul du cube de données,

- les techniques d'indexation (sélection et maintenance),

- la fragmentation,

- le groupement des n-uplets sur le disque (clustering).

Nous abordons dans cette thèse trois types de problèmes liés à la performance des requêtes: le premier concerne la *définition des index de jointure pour les vues matérialisées* à un niveau physique, le second est relatif à la *distribution de l'espace entre les vues matérialisées et les index*, et le dernier concerne la *fragmentation des données* d'un schéma d'un entrepôt de données à un niveau logique. Les deux premiers problèmes n'ont pas encore été traités dans la littérature, et, pour le dernier, nous proposons des solutions originales.

Nous résumons ci-dessous la problématique de recherche posée par chacun de ces problèmes.

### 1.5.1 Index de jointure pour les vues matérialisées

Une vue est une requête nommée. Une vue matérialisée est une table contenant les résultats d'une requête. Certaines requêtes nécessitent seulement l'accès à la vue matérialisée [GM95] et sont ainsi exécutées plus rapidement. L'entrepôt de données dans *the Mervyn's department store-chain* a 2400 vues matérialisées pour accélérer l'exécution des requêtes [Gup99]. Les vues matérialisées peuvent être utilisées pour satisfaire plusieurs besoins, comme l'amélioration de la performance des requêtes en réduisant le coût des opérations de jointure, ou la fourniture des données dupliquées. La sélection d'un ensemble de vues à matérialiser garantissant une meilleure performance des requêtes décisionnelles constitue un problème majeur. Ce problème est connu sous le nom de **problème de sélection de vues à matérialiser (PSV)**. Lorsqu'une vue est matérialisée, elle doit être mise à jour périodiquement pour tenir compte des changements pouvant survenir dans les sources de données. Ce problème est connu sous le nom de **maintenance de vues matérialisées**.

Le PSV consiste donc à sélectionner des vues de telle manière que les coûts d'évaluation des requêtes et de maintenance des vues soient les moins élevés possibles et sous une contrainte de limitation de ressources (contrainte d'espace par exemple).

Une fois les vues matérialisées sélectionnées, toutes les requêtes décisionnelles sont écrites en fonction de ces vues (voir par exemple les travaux de Divesh et al. [SDJL96]). Notons que les vues matérialisées peuvent être jointes entre elles ou avec d'autres tables du schéma. La jointure est très coûteuse, en particulier lorsque la taille des tables est importante par rapport à la mémoire centrale disponible [LR98]. De nombreuses techniques ont été proposées afin d'accélérer cette opération, en
particulier par l'intermédiaire d'index de jointure [Val87]. L'index de jointure en étoile [Sys97] a été utilisé dans les entrepôts de données modélisés par un schéma en étoile. Il consiste à installer un index pour faciliter la jointure entre une table des faits et plusieurs tables de dimensions. Il a été prouvé que cet index est la structure d'accès la plus efficace pour accélérer des jointures définies sur la table des faits et les tables de dimensions [Sys97, OQ97].

Le recours aux vues matérialisées pose un nouveau problème d'indexation, celui de savoir *comment indexer ces vues*. Une vue matérialisée peut être indexée en utilisant les techniques d'indexation des tables. Cependant, il n'existe pas de travaux concrets sur la définition et la sélection des index de jointure pour les vues matérialisées.

Notre contribution consiste à présenter une nouvelle technique d'indexation de jointure appelée *index de jointure de graphe* pour les vues matérialisées. Cet index pourra être construit en utilisant les vues matérialisées, les tables de dimensions, et la table des faits. Nous proposerons une stratégie d'exécution de requêtes en présence de ces index. Nous formulerons le problème de sélection d'index de jointure pour les vues matérialisées comme un problème d'optimisation. Nous proposerons alors trois algorithmes pour déterminer la solution optimale ou une solution quasi-optimale.

## 1.5.2 La répartition des ressources entre les index et les vues

La sélection des vues matérialisées se fait durant la phase de conception logique de l'entrepôt. Au niveau de la conception physique, l'administrateur de l'entrepôt doit sélectionner des index afin d'accélérer l'exécution des requêtes. Ce problème est connu sous le nom de **problème de sélection d'index (PSI)**. Comme pour les vues matérialisées, les index doivent être mis à jour périodiquement pour refléter les changements pouvant survenir dans les sources de données. Ce problème est connu sous le nom de **maintenance des index**.

Etant donné un ensemble de requêtes décisionnelles et une ressource donnée (comme l'espace disque, le coût de maintenance, et le coût de calcul), le PSI consiste à sélectionner un ensemble d'index afin de minimiser le coût d'évaluation des requêtes et de maintenance des index. Dans cette thèse nous nous intéressons à la ressource représentant l'espace disque.

De nombreux travaux ont été réalisés pour résoudre le PSV [Gup97, KR99, RSS96, TS97, YKL97] et le PSI [CN98, CN99, FST88, LQA97]. Ainsi ont été développés des algorithmes générant un ensemble de vues matérialisées et un ensemble d'index optimal ou quasi-optimal. Les vues et les index se définissent comme des structures physiques pouvant être utilisées pour accélérer les performances des requêtes. Les vues et les index présentent des similitudes. Ce sont des structures **re-dondantes** et **compétentes** pour la même ressource (l'espace disque). Tous deux peuvent entraîner des **surcharges** causées par des opérations de mise à jour, et demandent un **temps de calcul élevé**. Une vue matérialisée est stockée sous forme de table relationnelle dans le contexte ROLAP, et son indexation peut améliorer la performance des requêtes accédant à cette vue. La présence d'index peut rendre les vues matérialisées plus attractives et vice versa. Mais la plupart des travaux ne considèrent pas l'interaction entre ces deux problèmes.

La non considération de cette interaction, pose le problème de la **gestion des**
ressources (espace disque, coût de maintenance, etc.). Par exemple, si nous supposons que le PSV et le PSI sont contraints par l'espace, l'ignorance de l'interaction pose le problème de distribuer l'espace entre les vues et les index. La tâche de répartition de l'espace disque entre les vues matérialisées et les index dans l'objectif d'améliorer les performances des requêtes est difficile pour l'administrateur de l'entrepôt. Cette difficulté est due à plusieurs facteurs:

- La nécessité d'avoir une métrique pour décider de la distribution d'espace entre les vues et les index.

- L'interdépendance mutuelle entre les deux problèmes.

- La nécessité de tenir compte des répercussions des opérations de mise à jour sur les vues matérialisées et les index [HMA99]. Ainsi, les tailles des vues et des index peuvent augmenter ou diminuer. Il est donc nécessaire de redistribuer l'espace entre les vues et les index afin de garantir une meilleure performance.

- La nécessité de tenir compte de l'évolution des fréquences des requêtes qui peut modifier l'intérêt de certaines vues ou de certains index et par conséquent entraîner une redistribution de l'espace.

Ainsi, le problème de répartition de l'espace disque entre les vues matérialisées et les index doit être une partie intégrante du problème de sélection de vues et d'index. Ce problème a été identifié plus récemment [Bel00a] et n'a pas encore reçu de solution définitive.

Dans cette thèse, nous répondrons à la question suivante:

*comment distribuer/redistribuer d'une manière automatique l'espace disque entre les vues matérialisées et les index afin de garantir une meilleure performance d'exécution d'un ensemble de requêtes décisionnelles?*

### 1.5.3 La fragmentation

La fragmentation est une technique de conception logique introduite dans les années 80 dans les bases de données réparties [CNP82, CP84, OV91]. Étant donné une table relationnelle, la fragmentation consiste à partitionner cette table horizontalement en fonction de ses n-uplets, ou verticalement en fonction de ses attributs, de façon à réduire le nombre des accès nécessaires pour le traitement de certaines requêtes.

Dans cette thèse, nous nous intéressons seulement à la fragmentation horizontale, qui est la mieux adaptée aux entrepôts de données.

Tout d'abord, nous proposerons une méthodologie pour utiliser la fragmentation horizontale dans les entrepôts de données modélisés avec un schéma en étoile, dans le but de réduire le coût total d'exécution des requêtes. Cette méthodologie consiste à fragmenter les tables de dimensions en utilisant la fragmentation primaire (en utilisant un algorithme parmi les algorithmes disponibles dans les bases de données relationnelles), et la table des faits en utilisant la fragmentation dérivée. Durant le processus de fragmentation, nous avons remarqué que le choix des tables de dimensions utilisées pour fragmenter la table des faits a une incidence forte sur les performances. Nous développerons un algorithme "glouton" pour sélectionner les "meilleures" tables de dimensions. Puis nous proposerons un modèle de coût analy-
tique pour évaluer le coût d'exécution d'un ensemble de requêtes sur un schéma en étoile fragmenté.

Etant donné que notre objectif est d'améliorer la performance des requêtes dé-
cisionnelles, nous développerons une autre famille d'algorithmes qui comblent les
lacunes des algorithmes existants. Ces algorithmes sont dirigés par un modèle de
coût (cost-driven algorithms). Leur principale caractéristique est la garantie d'obte-
nir de bons schémas de fragmentation.

1.6 Organisation de la thèse

Cette thèse est organisée autour de six chapitres principaux.

Le chapitre 2 est un état de l'art original portant sur les problèmes d'optimisation des requêtes dans les bases de données et en particulier dans les entrepôts de données. La contribution principale de cette synthèse est de proposer un recensement et une classification de ces problèmes et de leurs algorithmes.

Le chapitre 3 explicite les limites des index de jointure existants (par exemple l'index de jointure en étoile) dans les entrepôts de données, pour indexer les vues matérialisées. Il présente également une nouvelle technique d'indexation des vues matérialisées.

Le chapitre 4 aborde le problème d'interaction entre les vues matérialisées et les index dans les entrepôts de données. Il présente deux algorithmes pour distribuer l'espace entre les vues et les index. Le premier algorithme est statique et le deuxième est dynamique.

Le chapitre 5 traite le problème de la fragmentation dans les entrepôts de données et discute des différents facteurs à prendre en compte dans les algorithmes de fragmentation. Il présente également une méthodologie pour la fragmentation dans les entrepôts de données en adaptant les algorithmes utilisés dans les bases de données relationnelles.

Le chapitre 6 décrit les principes de fragmentation dans les bases de données. Il présente les différents algorithmes de fragmentation proposés dans les bases de données relationnelles et objets et une classification de ces algorithmes. Deux nouveaux algorithmes de fragmentation sont proposés.

Le chapitre 7 présente les conclusions générales de ce travail et esquisse diverses perspectives.
# Chapitre 2
## État de l'art

### 2.1 Introduction

Depuis quelques années, les entrepôts de données ont pris une place importante dans les préoccupations des utilisateurs des bases de données. Le marché estimé a connu une croissance énorme [GGT96], et de nombreux projets ont été développés au sein des universités. Citons par exemple le projet WHIPS de l'université de Stanford, le projet H2O de l'université du Colorado en collaboration avec la Southern California University, et le projet ADMS des universités du Maryland, de Stanford et du Queensland.

L'idée sous-jacente à la mise en oeuvre d'un entrepôt est de fournir un accès permanent aux données même lorsque les bases de données individuelles sont inaccessibles, et de réduire les accès distants aux systèmes gérant les données d'origine. Les entrepôts de données sont dédiés aux applications d'analyse et de prise de décision. Le processus d'analyse est réalisé à l'aide de requêtes complexes comportant de multiples jointures et des opérations d'agrégation sur des tables volumineuses. Les performances de ces requêtes dépendent directement de l'usage qui est fait de la mémoire secondaire. En effet, chaque entrée-sortie sur disque nécessitant jusqu'à une dizaine de milli-secondes [Dar99], l'accès à la mémoire secondaire constitue de ce fait un véritable goulot d'étranglement. L'administrateur, dans le but de minimiser le coût d'exécution de ces requêtes, sélectionne un ensemble de vues matérialisées et un ensemble d'index. Cette sélection diminue le coût des requêtes, mais entraîne un autre problème: les tables, les vues matérialisées et les index occupent une place très importante, et en conséquence ils ne peuvent pas être stockés en totalité dans la mémoire centrale. Dans un tel environnement, le nombre des entrées-sorties peut être grand si de bonnes techniques d'optimisation ne sont pas mises en oeuvre.

Les entrepôts de données ont d'abord été abordés par les industriels, mais par la suite les chercheurs se sont également penchés sur ce concept. Afin d'atteindre un niveau de performance acceptable, les deux communautés ont développé des techniques d'optimisation des requêtes au niveau de chaque phase de la conception d'un entrepôt (phase *conceptuelle*, phase *logique*, phase *physique*). Il existe cependant beaucoup plus de travaux concernant la phase de conception logique (la sélection et la maintenance des vues matérialisées, etc.) et la phase de conception physique de l'entrepôt (la sélection des index, les techniques d'indexation, les regroupements, etc.) comme nous le verrons tout au long de ce chapitre. Ce dernier est divisé en
quatre sections:

**Modèle de données pour les entrepôts:** L'entrepôt de données est typiquement modélisé par des modèles multidimensionnels (encore appelés cubes de données). Ces modèles sont appropriés pour les applications OLAP [AGS97, MSRK00]. En fonction de la manière dont le cube est stocké, deux approches existent pour construire des systèmes multidimensionnels: Relational OLAP (ROLAP), and Multidimensional OLAP (MOLAP).

La section 2.2 décrit en détail ces modèles multidimensionnels et leur schéma d'implémentation.

**Les vues matérialisées:** Un modèle multidimensionnel de données est stocké dans l'entrepôt comme un ensemble de vues matérialisées sur les données de bases. Les vues matérialisées permettent d'offrir des réponses rapides pour des requêtes, mais introduisent le problème de leur mise à jour. Pour des raisons d'efficacité les mises à jour sont souvent effectuées en utilisant des techniques incrémentales. De nombreux travaux de recherche ont été développés pour la maintenance des vues dans les bases de données traditionnelles [BLT86, CW81, LHM+86].

La section 2.3, définit le concept de vue matérialisée, présente le problème de sélection des vues matérialisées pour satisfaire les requêtes, et discute les techniques de mise à jour.

**Les index:** La matérialisation des vues est une approche embarrassante du fait qu'elle nécessite une anticipation des requêtes à matérialiser. Or, les requêtes dans les environnements des entrepôts sont souvent ad-hoc et ne peuvent pas toujours être anticipées. En effet, un utilisateur peut poser une requête sur des dimensions qui ne sont pas matérialisées dans une vue. En conséquence, la stratégie de précalcul est limitée. Une traduction effective des cubes de données en schémas relationnels (schémas en étoile) exige des méthodes d'indexation compte tenu du nombre important d'opérations de sélection et de jointure. Les requêtes qui ne sont pas précalculées doivent être élaborées à la volée. Cela nécessite des structures d'accès rapides pour conserver l'intérêt d'une analyse on-line.

Dans la section 2.4, nous montrons que les techniques d'indexation des systèmes OLTP ne sont pas appropriées pour un système multidimensionnel. Nous présentons également le problème de sélection d'index dans les entrepôts, et son utilité dans la réduction du temps de réponse des requêtes.

**La fragmentation des données:** La fragmentation est une technique de conception logique utilisée dans les modèles relationnels et objet. Elle consiste à partitionner le schéma d'une base de données en plusieurs sous-schémas dans le but de réduire le temps d'exécution des requêtes.

Dans la section 2.5 nous présentons ce concept et les algorithmes associés pour les modèles relationnel et objet.

## 2.2 Les modèles de données pour les entrepôts

La conception d'un entrepôt est très différente de celle d'une base de données pour un système OLTP. Les concepts sont plus ouverts et plus difficiles à définir. De
<figure><img src="image_6.png" /><figcaption>FIG. 2.1: Cube de données</figcaption></figure>

plus, les besoins des utilisateurs de l'entrepôt ne sont pas aussi clairs que ceux des utilisateurs des systèmes OLTP. Les modèles de données utilisés dans la conception des systèmes transactionnels traditionnels ne sont pas adaptés aux requêtes complexes. En effet, les transactions dans les systèmes OLTP sont simples, alors que, dans les entrepôts, les requêtes utilisent beaucoup de jointures, demandent beaucoup de temps de calcul et sont de nature ad-hoc. Pour ce type d'environnement on a suggéré une nouvelle approche de modélisation: les modèles multidimensionnels.

## 2.2.1 Les modèles multidimensionnels

La conception des bases de données est en général basée sur le modèle Entité-Association (Entity-Relationship) (E-R). Ce modèle permet de décrire des relations entre les données élémentaires (entités) en éliminant des redondances, ce qui provoque l'introduction d'un nombre important de nouvelles entités. De ce fait, l'accès aux données devient compliqué et le diagramme généré difficile à comprendre pour un utilisateur. C'est pour cette raison que l'utilisation de la modélisation E-R pour la conception d'un entrepôt n'est pas considérée comme appropriée [Kim97].

Le modèle multidimensionnel de données, par contre, permet d'observer les données sous plusieurs perspectives. Son axe d'analyse facilite l'accès aux données. Il est plus facilement compréhensible, même pour les personnes qui ne sont pas expertes en informatique. Dans ce modèle, les lignes et les colonnes sont remplacées par des dimensions, en tant que catégories descriptives, et par des mesures qui font office de valeurs quantitatives. La modélisation multidimensionnelle part du principe que l'objectif majeur est la vision multidimensionnelle des données. Le problème de performance est inhérent au modèle. Le constructeur fondamental de ces modèles est le cube de données.

### 2.2.1.1 Le cube de données

Le cube de données offre une abstraction très proche de la façon dont l'analyste voit et interroge les données. Il organise les données en une ou plusieurs dimensions qui déterminent une mesure d'intérêt. Une dimension spécifie la manière dont on regarde les données pour les analyser, alors qu'une mesure est un objet d'analyse.
Chaque dimension est formée par un ensemble d'attributs et chaque attribut peut prendre différentes valeurs. Les dimensions possèdent en général des hiérarchies associées qui organisent les attributs à différents niveaux pour observer les données à différentes granularités. Une dimension peut avoir plusieurs hiérarchies associées, chacune spécifiant différentes relations d'ordre entre ses attributs.

**Exemple 1** Nous pouvons modéliser les données de ventes d'une chaîne de magasins en utilisant un cube à trois dimensions. Chaque cellule de ce cube stocke le total des ventes pour un produit particulier, sur une localisation particulière et pour un jour particulier. Dans cet exemple, l'attribut de mesure (ou fait) est le total de ventes et les attributs de dimension sont le produit, la localisation et le jour. Nous pouvons avoir la hiérarchie suivante pour la dimension "localisation → ville → état" qui représente l'attribut localisation en l'attribut ville, et l'attribut ville en l'attribut état. D'une manière similaire l'attribut jour est représenté par des hiérarchies "année → semestre → mois → jour" (voir Figure 2.1).

Plus formellement, la structure d'un cube de données est la suivante [AGS96]:

- chacune des *d* dimensions porte un nom $D_i$. À chaque dimension $D_i$ est associé un domaine de valeurs $Dom_i$.

- Une référence de cellule est un n-uplet $<v_1, v_2, ..., v_d>$ appartenant à $Dom_{D_1} \times Dom_{D_2} \times ... \times Dom_{D_d}$. Le contenu d'une cellule d'un cube est soit la constante 0, soit la constante 1, soit un n-uplet $<v'_1, v'_2, ..., v'_k>$ appartenant à $Dom_{D'_1} \times Dom_{D'_2} \times ... \times Dom_{D'_k}$.

On dit encore que $v_1, v_2, ..., v_d$ sont les dimensions membres et que $v'_1, v'_2, ..., v'_k$ sont les dimensions mesures.

Un cube *C* de *d* dimensions est une fonction $F_c$ associant à chaque cellule de coordonnées $<v_1, v_2, ..., v_d>$ l'un des éléments suivants:

- La constante 0 si la cellule de référence $<v_1, v_2, ..., v_d>$ n'existe pas pour *C*;

- La constante 1 si la cellule de référence $<v_1, v_2, ..., v_d>$ existe mais ne contient pas de mesure;

- Un n-uplet $<v'_1, v'_2, ..., v'_k>$ si la cellule de coordonnées $<v_1, v_2, ..., v_d>$ contient $<v'_1, v'_2, ..., v'_k>$.

**Exemple 2** La Figure 2.2 décrit un cube de données VENTES modélisant les ventes d'un magasin. Les dimensions sont client, produit, temps et quantité dont les domaines sont: $dom_{produit} = \{P1, P2, P3\}$, $dom_{client} = \{C1, C2, C3\}$, $dom_{temps} = \{1999, 2000\}$, et $dom_{quantit} \subseteq N$.

Le cube VENTES est défini par trois dimensions pour les membres (produit, client et temps), et une dimension pour les mesures (le n-uplet $<quantité>$ et la fonction $F_{ventes}$ de $dom_{produit} \times dom_{client} \times dom_{temps}$ vers $dom_{quantit} \cup \{0, 1\}$). Une cellule du cube VENTES est par exemple $<P_2, C_2, 2000>$.

Plusieurs opérations sont introduites pour offrir des possibilités d'animation dans la représentation du cube à l'écran. Elles consistent à faire pivoter le cube, le couper en tranches, interchanger ou combiner les coordonnées et/ou les contenus.
<figure><img src="image_7.png" /><figcaption>FIG. 2.2: Le cube VENTES</figcaption></figure>

### 2.2.1.2 Opérations liées à la structure

Les opérations agissant sur cette structure multidimensionnelle de l'information sont motivées par l'aspect interactif de l'analyse en ligne de données, et le souci d'offrir des possibilités d'animation de la représentation [Mar98]. De plus, elles illustrent l'importance des liens entre la manipulation des données et la représentation du cube à l'écran.

Ces opérations sont regroupées sous le nom de restructuration. Tout cube obtenu par une opération de restructuration d'un cube initial contient tout ce qu'il faut pour régénérer le cube initial par restructuration réciproque. Ces opérations sont: *pivot*, *swich*, *split*, *nest*, *push*, *et pull*.

**Pivot** Cette opération consiste à faire effectuer à un cube une rotation autour d'un des trois axes passant par le centre de deux faces opposées, de manière à présenter un ensemble de faces différent.

**Switch** Cette opération consiste à interchanger la position des membres d'une dimension.

**Split** Elle consiste à présenter chaque tranche du cube, et à passer d'une représentation tridimensionnelle d'un cube à sa représentation sous la forme d'un ensemble de tables. D'une manière générale, cette opération permet de réduire le nombre de dimensions d'une représentation. On notera que le nombre de tables résultant d'une opération split dépend des informations contenues dans le cube de départ et n'est pas connu à l'avance.

**Nest** Cette opération permet d'imbriquer des membres. L'un de ses intérêts est qu'elle permet de grouper sur une même représentation bi-dimensionnelle toutes les informations (mesures et membres) d'un cube, quel que soit le nombre de ses dimensions. L'opération réciproque, "unnest", reconstitue une dimension séparée à partir des membres imbriqués.
<figure><img src="image_8.png" /><figcaption>FIG. 2.3: Systèmes MOLAP</figcaption></figure>

**Push** Cette opération consiste à combiner les membres d'une dimension aux mesures du cube, et donc de faire passer des membres comme contenus de cellules. L'opération réciproque appelée pull, permet de changer le statut de certaines mesures d'un cube en membres, et de constituer une nouvelle dimension pour la représentation du cube, à partir de ces nouveaux membres.

### 2.2.1.3 Opérations associées à la granularité

Le deuxième aspect de la vision de l'analyste est de hiérarchiser l'information en différents niveaux de détail appelés niveaux de granularité. Les opérations permettant la hiérarchisation sont: *roll-up* et *drill-down*. Ces deux opérations autorisent l'analyse de données à différents niveaux d'agrégation en utilisant des hiérarchies associées à chaque dimension.

**Roll-up** Cette opération effectue l'agrégation des mesures en allant d'un niveau particulier de la hiérarchie vers un niveau général. Elle est dénotée par:

$$RollUp_{niveau\_inf}^{niveau\_sup}(CUBE)$$

**Drill-down** Elle consiste à représenter les données d'un cube à un niveau inférieur, et donc sous une forme plus détaillée. Elle peut être vue comme l'opération réciproque du roll-up. Elle est dénotée par:

$$DrillDown_{niveau\_inf}^{niveau\_sup}(CUBE)$$

### 2.2.2 Les implémentations des modèles multidimensionnels

Selon la façon dont le cube de données est stocké, il existe deux approches fondamentales pour construire des systèmes basés sur un modèle multidimensionnel. L'approche MOLAP (Multidimensional OLAP) (par exemple Hyperion Essbase OLAP Server [Hyp]) implémente le cube de données dans un tableau multi-dimensionnel (multi-dimensional array). Par contre, l'approche ROLAP (Relational OLAP) (par exemple, Informix Red Brick Warehouse [Cor97b]) utilise un SGBD relationnel pour gérer et stocker le cube de données. Une comparaison détaillée des produits OLAP peut être trouvée dans [PC98].
<figure><img src="image_9.png" /><figcaption>FIG. 2.4: Systèmes ROLAP</figcaption></figure>

### 2.2.2.1 Les systèmes MOLAP

Les système de type MOLAP stockent les données dans un SGBD multi-dimensionnel sous la forme d'un tableau multi-dimensionnel (multi-dimensional array). Chaque dimension de ce tableau est associée à une dimension du cube (voir Figure 2.3). Seules les valeurs de données correspondant aux données de chaque cellule sont stockées. Ces systèmes demandent un pré-calcul de toutes les agrégations possibles. En conséquence, ils sont plus performants que les systèmes traditionnels, mais difficiles à mettre à jour et à gérer [VS99].

Les systèmes MOLAP apparaissent comme une solution acceptable pour le stockage et l'analyse d'un entrepôt lorsque la quantité estimée des données d'un entrepôt ne dépasse pas quelques gigaoctets et lorsque le modèle multidimensionnel évolue peu [GCA01]. Mais, lorsque les données sont éparses, ces systèmes sont consommateurs d'espace [CD97] et des techniques de compression doivent être utilisées. Les produits de Hyperion Essbase OLAP Server [Hyp] ont adopté cette technique de stockage.

### 2.2.2.2 Les systèmes ROLAP

Les systèmes de type ROLAP utilisent un SGBD relationnel pour stocker les données de l'entrepôt. Ils représentent une interface multidimensionnelle pour le SGBD relationnel. Le moteur OLAP est un élément supplémentaire qui fournit une vision multidimensionnelle de l'entrepôt, des calculs de données dérivées et des agrégations à différents niveaux. Il est aussi responsable de la génération des requêtes SQL mieux adaptées au schéma relationnel, qui profitent des vues matérialisées existantes pour exécuter efficacement ces requêtes. Les mesures (par exemple les quantités vendues) sont stockées dans une table qu'on appelle *la table des faits*. Pour chaque dimension du modèle multidimensionnel, il existe une table qu'on appelle *la table de dimension* (comme Produit, Temps, Client) avec tous les niveaux d'agrégation et les propriétés de chaque niveau (voir Figure 2.4).

Ces systèmes peuvent stocker de grands volumes de données, mais ils peuvent présenter un temps de réponse élevé. Les principaux avantages de ces systèmes sont: (1) une facilité d'intégration dans les SGBDs relationnels existants, (2) une bonne efficacité pour stocker les données multidimensionnelles. Les exemples de produits de cette famille sont *DSS Agent de MicroStrategy* [Mic98] et *MetaCube d'Informix* [Cor97b].

Mendelzon [Men97] fait une comparaison entre l'approche ROLAP et l'approche MOLAP (voir la Table 2.1).
<table><caption>TAB. 2.1: ROLAP vs. MOLAP</caption><thead><tr><th></th><th>Avantages</th><th>Inconvénients</th></tr></thead><tbody><tr><td rowspan="3">ROLAP</td><td>Technologie familière</td><td>Lent</td></tr><tr><td>Scalable</td><td></td></tr><tr><td>Ouvert</td><td></td></tr><tr><td rowspan="3">MOLAP</td><td>Modèle multidimensionnel</td><td>Technologie non prouvée</td></tr><tr><td>Traitement de requête spécialisé</td><td>Non scalable</td></tr><tr><td>Techniques d'indexation spécialisées</td><td></td></tr></tbody></table>

Trois schémas sont utilisés pour modéliser les systèmes ROLAP: (1) le schéma en étoile, (2) le schéma en flocon de neige et (3) le schéma en constellation.

### Le schéma en étoile
Dans ce type de schéma [Kim96], les mesures sont représentées par une table de faits et chaque dimension par une table de dimensions. La table des faits référence les tables de dimensions en utilisant une clé étrangère pour chacune d'elles et stocke les valeurs des mesures pour chaque combinaison de clés. Autour de cette table des faits figurent les tables de dimensions qui regroupent les caractéristiques des dimensions. La table des faits est normalisée et peut atteindre une taille importante par rapport au nombre de n-uplets. Les tables de dimension sont généralement dénormalisées afin de minimiser le nombre de jointures nécessaires pour évaluer une requête. Ce schéma est largement utilisé dans les applications industrielles (les groupes Redbrik [Sys97], ou encore Informix [Cor97b]).

Cependant, un schéma en étoile est souvent un concept centré-requête, par op-position au schéma centré-mise à jour employé par les applications de type OLTP. Les requêtes typiques de ce schéma sont appelées les requêtes de jointure en étoile (star-join queries) qui ont les caractéristiques suivantes:

1. Il y a des jointures multiples entre la table des faits et les tables de dimension.

2. Il n'y a pas de jointure entre les tables de dimensions.

3. Chaque table de dimension impliquée dans une opération de jointure a plusieurs prédicats de sélection sur ses attributs descriptifs.

La syntaxe générale de ces requêtes est la suivante:

```
SELECT <Liste de projection> <Liste d'agrégation>
FROM <Nom de la table des faits> <Liste de noms de tables de dimension>
WHERE <Liste de prédicats de sélection & jointure>
GROUP BY <Liste des attributs de tables de dimension>
```

La Figure 2.5 montre un schéma en étoile pour le cube VENTES où la table des faits VENTES stocke la quantité de produits vendus et les tables correspondant à PRODUIT, à CLIENT et à TEMPS comportent les informations pertinentes sur ces dimensions.

Comme nous le constatons dans la Figure 2.5, la table de dimension TEMPS est dénormalisée, et donc le schéma en étoile ne capture pas directement les hiérarchies (c'est-à-dire les dépendances entre les attributs).
<figure><img src="image_10.png" /><figcaption>FIG. 2.5: Un exemple d'un schéma en étoile</figcaption></figure>

### Le schéma en flocon de neige
Le schéma en étoile ne reflète pas les hiérarchies associées à une dimension [JLS99b]. Il exige que les informations complètes associées à une hiérarchie de dimension soient représentées dans une seule table, même lorsque les différents niveaux de la hiérarchie ont des propriétés différentes. Pour résoudre ce problème, le schéma en flocon de neige a été proposé. Ce dernier est une extension du schéma en étoile. Il consiste à garder la même table des faits et à éclater les tables de dimensions afin de permettre une représentation plus explicite de la hiérarchie [JLS99b]. Cet éclatement peut être vu comme une normalisation des tables de dimensions.

Contrairement au schéma en étoile, le schéma en flocon de neige capture les hiérarchies entre les attributs. La Figure 2.6 montre un schéma en flocon de neige après la normalisation de la table de dimension TEMPS.

Ce schéma a été fortement déconseillé par Kimball [Kim96] qui disait : “*ne structurez pas vos dimensions en flocons de neige même si elles sont trop grandes*”, mais en même temps, conseillé par des chercheurs (comme Jagadish et al. [JLS99b]) et des industriels de AT&T Labs-Research [JLS99b].

### Le schéma en constellation
Il est possible d'avoir plusieurs tables des faits partageant des tables de dimensions. Dans ce cas, les tables des faits forment une famille [KS95]. Chaque membre de cette famille possède ses propres dimensions. Si les tables des faits partagent une dimension, il faut vérifier que cette dimension soit exactement la même. Le schéma résultant s'appelle constellation des faits [CD97].

Dans cette thèse nous utilisons un schéma en étoile pour élaborer nos techniques, mais ces dernières peuvent facilement être étendues aux schémas en flocon de neige et constellation.
<figure><img src="image_11.png" /><figcaption>FIG. 2.6: Un exemple d'un schéma en flocon de neige</figcaption></figure>

### 2.2.3 Les Systèmes HOLAP

Ces systèmes essayent de tirer les bénéfices des deux systèmes précédemment décrits. Dans les systèmes HOLAP, les données sont maintenues par un SGBD relationnel, tandis que les agrégations le sont dans un SGBD multidimensionnel. Le produit *Express d'Oracle Corp.* [Cor98] est un des exemples de cette famille de systèmes.

## 2.3 Les vues matérialisées

Une vue est une requête nommée. Une vue matérialisée est une table contenant les résultats d'une requête. Les vues améliorent l'exécution des requêtes en pré calculant les opérations les plus coûteuses comme la jointure et l'agrégation, et en stockant leurs résultats dans la base. En conséquence, certaines requêtes nécessitent seulement l'accès aux vues matérialisées et sont ainsi exécutées plus rapidement. Les vues dans le contexte OLTP ont été largement utilisées pour répondre à plusieurs rôles: la sécurité, la confidentialité, l'intégrité référentielle, etc.

Les vues matérialisées peuvent être utilisées pour satisfaire plusieurs objectifs, comme l'amélioration de la performance des requêtes ou la fourniture des données dupliquées. Le concept a été largement utilisé dans l'informatique distribuée et l'informatique mobile. Les vues matérialisées dans l'informatique distribuée sont utilisées pour dupliquer des données au niveau des sites distribués. Les réplicas permettent de résoudre des requêtes uniquement par des accès locaux. L'information mobile a pris un essor considérable au cours des cinq dernières années grâce aux performances croissantes des matériels (utilisation des batteries, baisse de la
consommation d'énergie) et à des coûts de plus en plus faibles. Afin de pallier les déconnexions inhérentes aux environnements sans fil, les machines mobiles sont sou- vent contraintes de copier localement les données.

Deux problèmes majeurs sont liés aux vues matérialisées: (1) *le problème de sélection des vues matérialisées* et (2) *le problème de maintenance des vues matérialisées*. Nous abordons ces deux problèmes dans les sections suivantes.

### 2.3.1 La sélection des vues matérialisées

Dans l'environnement d'un entrepôt de données, il est généralement possible d'isoler un ensemble de requêtes à privilégier. L'ensemble des vues matérialisées doit être déterminé en fonction de cet ensemble de requêtes.

Le problème de sélection des vues matérialisées (PSV) peut être vu sous deux angles en fonction du type de modèles de données: (1) le PSV de type ROLAP et (2) le PSV de type MOLAP (voir Figure 2.7).

- Dans le PSV de type MOLAP, nous considérons le cube de données comme la structure primordiale pour sélectionner les vues matérialisées. Chaque cellule du cube est considérée comme une vue potentielle. Notons que le cube de données est un cas spécial d'entrepôt, ne contenant que les requêtes ayant des agrégations sur les relations de base.

- Dans le PSV de type ROLAP, chaque requête est représentée par un arbre algébrique [BC81]. Chaque noeud (non feuille) est considéré comme une vue potentielle. Ce type de PSV est plus général que le premier type.

Il existe trois possibilités pour sélectionner un ensemble de vues [Ull96]:

1. **matérialiser toutes les vues:** Dans le cube de données cette approche consiste à matérialiser la totalité du cube, tandis que dans le cas du ROLAP, elle consiste à matérialiser tous les noeuds intermédiaires des arbres algébriques représentant les requêtes. Cette approche donne le meilleur temps de réponse pour toutes les requêtes. Mais stocker et maintenir toutes les cellules/noeuds intermédiaires est impraticable pour un entrepôt important. De plus, l'espace utilisé par les vues peut influencer la sélection des index.

2. **ne matérialiser aucune vue:** Dans ce cas nous sommes obligés d'accéder aux données des relations de base. Cette solution ne fournit aucun avantage pour les performances des requêtes.

3. **matérialiser seulement une partie du cube/des noeuds:** Dans un cube, il existe une certaine dépendance entre les cellules, c'est à dire que la valeur de certaines cellules peut être calculée à partir des valeurs d'autres cellules. Dans le cas d'un système ROLAP, on trouve également cette dépendance dans les arbres algébriques. Il est alors souhaitable de matérialiser les parties partagées (cellules ou noeuds) par plusieurs requêtes. Cette approche a pour but de sélectionner les cellules ou les noeuds partagés. Cette solution semble la plus intéressante par rapport aux deux approches précédentes.

Quel que soit le type de PSV, ce dernier peut être défini de la manière suivante [Gup99, Ull96]:

Étant donné une contrainte de ressource S (capacité de stockage, par exemple),
<figure><img src="image_12.png" /><figcaption>FIG. 2.7: Les types de PSV</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>FIG. 2.8: Le processus de sélection des vues matérialisées</figcaption></figure>

le PSV consiste à sélectionner un ensemble de vues {$V_1, V_2, ..., V_k$} minimisant une fonction objectif (coût total d'évaluation des requêtes et/ou coût de maintenance des vues sélectionnées) et satisfaisant la contrainte (voir la Figure 2.8).

Ce problème a été largement étudié tant pour l'approche MOLAP [KR99, Ull96, DRSN98] que pour l'approche ROLAP [Gup99, Gup97, TS97, YKL97, Ked99] afin de sélectionner un ensemble de vues optimales résultant d'une énumération de toutes les vues à matérialiser (ou à précalculer). Leur nombre est très grand et a la complexité $O(2^n)$, où $n$ est le nombre des agrégations dans le schéma. Si $d$ est le nombre de dimensions dans ce schéma, et qu'il ne contient aucune hiérarchie, alors $n = 2^d$. De ce fait, le PSV est NP-difficile [Gup99, SDN98, Ull96].

Rappelons que le rôle principal des vues matérialisées est de réduire le coût d'évaluation de certaines requêtes $Q = \{Q_1, ..., Q_k\}$ (les plus fréquentes, par exemple) définies sur l'entrepôt. La question qui se pose concerne la **connaissance préalable ou non de l'ensemble des requêtes** $Q$, d'où la distinction de deux catégories de PSV: (1) le PSV statique et (2) le PSV dynamique.

**Le PSV statique** Ce problème possède les données suivantes comme entrées:

- un schéma d'un entrepôt

- un ensemble de $k$ requêtes les plus fréquemment utilisées (les requêtes sont donc **connues a priori**)
- une ressource.

Le PSV statique consiste à sélectionner un ensemble de vues à matérialiser afin de minimiser le coût total d'évaluation de ces requêtes, le coût de maintenance, ou les deux, sous la contrainte de la ressource.

Le problème suppose donc que l'ensemble des requêtes n'évolue pas. Si des évolu-
tions des requêtes sont enregistrées alors il est nécessaire de reconsidérer totalement
le problème (en reconstruisant les vues à matérialiser).

**Le PSV dynamique** Pour combler les lacunes du PSV statique, Kotidis et al. [KR99] ont proposé un système appelé *DynaMat*, qui matérialise les vues d'une ma-nière dynamique. *DynaMat* combine en fait les problèmes de sélection et de mainte-nance des vues. Ce système enregistre les évolutions des requêtes et matérialise dans chaque cas le meilleur ensemble de vues pour satisfaire ces requêtes. La contrainte à satisfaire est celle de la capacité d'espace sur mémoire secondaire. Pendant les opé-rations de mise à jour, DynaMat rafraîchit les vues et si la taille des vues dépasse la capacité de l'espace autorisé, il procède à certaines éliminations selon des critères de placement (par exemple les vues les moins utilisées sont éliminées).

De nombreux algorithmes ont été développés pour élaborer une solution optimale
ou quasi-optimale pour le PSV. La plupart de ces algorithmes étaient destinés au cas statique comme nous allons le voir dans la section suivante.

2.3.2 Les algorithmes de sélection des vues

Les algorithmes proposés pour la sélection des vues peuvent être classés en trois
catégories, en fonction du type de contrainte qu'ils utilisent: (1) *algorithmes sans aucune contrainte* [RSS96, YKL97, BPT97, TS97], (2) *algorithmes dirigés par la contrainte d'espace* [Gup97] et (3) *algorithmes dirigés par la contrainte du temps total de maintenance des vues* [GHRU97].

2.3.2.1 Les algorithmes sans aucune contrainte

Il existe plusieurs approches pour la sélection des vues sans contrainte. Nous en retenons deux, qui sont l'approche de Yang et al. [YKL97] proposée dans le contexte ROLAP, et l'approche de Baralis [BPT97] proposée dans le contexte MOLAP.

Les travaux de Yang et al. [YKL97] Les auteurs ont développé un algorithme de sélection des vues dans un contexte ROLAP statique. Les auteurs partent du principe suivant: *la principale caractéristique des requêtes décisionnelles est qu'elles utilisent souvent les résultats de certaines requêtes pour répondre à d'autres requêtes* [BPT97]. On peut tirer de cette caractéristiques que les requêtes décisionnelles par-tagent certaines expressions.

L'algorithm de Yang et al. procède de la façon suivante:
Chaque requête est représentée par un arbre algébrique [BC81, EN94]. Etant donné
que chaque requête peut avoir plusieurs arbres algébriques, les auteurs sélectionnent
l'arbre optimal (en fonction d'un modèle de coût). Une fois les arbres optimaux
identifiés, l'algorithm essaye de trouver des expressions communes entre ces arbres
<figure><img src="image_14.png" /><figcaption>FIG. 2.9: Le principe de base de la sélection de Yang et al. [YKL97]</figcaption></figure>

(ou noeud partagé). Finalement, les arbres sont fusionnés en un seul graphe, appelé *plan multiple d'exécution des vues* en utilisant les noeuds partagés identifiés.

Ce graphe a plusieurs niveaux. Les feuilles sont les tables de base de l'entrepôt et représentent le niveau 0. Dans le niveau 1, nous trouvons des noeuds représentant les résultats des opérations algébriques de sélection et de projection. Dans le niveau 2, les noeuds représentent les opérations ensemblistes comme la jointure, l'union, etc. Le dernier niveau représente les résultats de chaque requête. Chaque noeud intermédiaire de ce graphe est étiqueté par le coût de l'opération algébrique (sélection, jointure, union, etc.) et le coût de maintenance. Ce graphe est utilisé pour rechercher l'ensemble des vues dont la matérialisation minimise la somme des coûts d'évaluation des requêtes et de maintenance des vues. La solution prend en considération l'existence de plusieurs expressions possibles pour une requête. Chaque noeud intermédiaire est considéré comme une vue potentielle.

**Exemple 3** Soit un schéma d'un entrepôt ayant cinq tables et sur lequel trois requêtes sont définies. La Figure 2.9 montre que les requêtes $Q_1$ et $Q_2$ ont une expression commune ($Exp_1$). Ces noeuds sont de bons candidats pour la matérialisation.

La description de cet algorithme sera détaillée dans le chapitre 3 car nous l'utilisons comme support de nos travaux.

**Les travaux de Baralis et al. [BPT97]** Dans le contexte MOLAP, Baralis et al. [BPT97] ont développé une heuristique pour le PSV statique. Leur technique consiste à élaborer le treillis des vues qui prend en compte les hiérarchies des attributs (par exemple jour → semaine → semestre). Avant de parler des treillis des vues, quelques définitions s'imposent.

**Définition 1** Une relation de dépendance $\leq$ entre les requêtes Soient $Q_i$ et $Q_j$ deux requêtes (vues). On dit que $Q_i \leq Q_j$ si et seulement si $Q_i$ peut être évaluée en utilisant seulement les résultats de la requête $Q_j$.

**Définition 2** Un treillis est construit de la façon suivante: les noeuds de ce treillis représentent les vues (agrégées sur certaines dimensions) et un arc existe entre deux noeuds $V_i$ et $V_j$ si elles sont dépendantes ($V_i \leq V_j$). Le noeud $V_i$ est un noeud ancêtre
<figure><img src="image_15.png" /><figcaption>FIG. 2.10: Treillis des vues</figcaption></figure>

et $V_j$ un descendant. Les ancêtres et les descendants d'un noeud $V_i$ du treillis sont définis comme suit:

$$ \begin{aligned} \text{ancêtre}(V_i) &= \{V_j \mid V_i \le V_j\} \\ \text{descendant}(V_i) &= \{V_j \mid V_j \le V_i\} \end{aligned} $$

**Exemple 4** La Figure 2.10 présente le treillis des vues possibles à partir des dimensions PIECE (représenté par P), CLIENT (représenté par C) et FOURNISSEUR (représenté par F) tirées de la base de données du benchmark TPC-D [Pag].

Le treillis permet non seulement d'établir des dépendances entre les vues à matérialiser mais constitue également un bon support pour les algorithmes de sélection. Il permet aussi de dire dans quel ordre les vues sont matérialisées [HRU96]. On dit qu'une vue $V_i$ du treillis est une vue candidate si une des deux conditions suivantes est satisfaite:

- $V_i$ est associée à quelques requêtes (voir Figure 2.10).

- il existe deux vues candidates $V_j$ et $V_k$, telle que $V_i$ est la plus petite borne supérieure de $V_j$ et $V_k$ (le coût de mise à jour des vues $V_j$ et $V_k$ est supérieur à celui de $V_i$).

Une fois les vues candidates sélectionnées, le bénéfice pour chaque noeud descendant est recalculé et la vue de bénéfice maximal est sélectionnée.

Pour conclure sur ce type d'algorithmes, nous pouvons dire qu'étant donné l'absence de contrainte liée à ces algorithmes, il n'existe aucun moyen d'évaluer leur résultat [Gup99].

### 2.3.2.2 Algorithmes dirigés par la contrainte d'espace

Dans le travail initial réalisé pour la sélection des vues, Harinarayan et al. [HRU96] ont présenté un algorithme glouton pour sélectionner un ensemble de celules (vues) dans un cube de données. L'objectif de cet algorithme est de minimiser le temps de réponse des requêtes sous la contrainte que la taille des vues sélectionnées ne dépasse pas la capacité d'espace $S$. Les auteurs s'intéressent seulement aux requêtes ayant des fonctions d'agrégation.

**Exemple 5** Prenons les mêmes dimensions de l'exemple 4: PIECE (P), FOURNISSEUR (F) et CLIENT (C), et la mesure représente le total des ventes. Chaque cellule (p, f, c) du cube de données stocke le total des ventes de la pièce p qui est acheté par le fournisseur f et vendue au client c. On ajoute la valeur ALL aux domaines des dimensions pour répondre aux requêtes qui ne référencent pas toutes les dimensions. Par exemple, si l'utilisateur cherche le total des ventes de la pièce
p pour un client donné c (la représentation est (p, ALL, c)). Pour trois dimensions, le nombre de vues potentielles est de l'ordre de $2^3 = 8$.

Les auteurs ont modélisé le problème sous la forme d'un treillis de vues (voir Figure 2.10). Les auteurs ont développé un modèle de coût afin d'estimer le coût de chaque vue du treillis. Ce coût est basé sur le principe suivant:

Pour évaluer une requête $Q$ (vue), nous choisissons une vue ancêtre de $Q$ (disons $Q_A$), qui a été matérialisée. Le coût d'évaluation de la requête $Q$ est le nombre de n-uplets présents dans la table correspondante à $Q_A$. Chaque vue est associée à un coût de stockage correspondant au nombre de n-uplets de cette vue.

L'algorithme de sélection des vues est décrit de la façon suivante (voir l'algorithme 1):

Soit $S$ l'ensemble des vues matérialisées à l'étape $j$ de l'algorithme. Pour chaque vue $v$, un **bénéfice** dénoté par $B(v, S)$ et défini comme suit:

- Pour chaque relation de dépendance $w \leq v$, définir une quantité $B_w$ par:

1. Soit $u$ la vue ayant le plus petit coût dans $S$ tel que $w \leq u$

2. Si $C(v) < C(u)$, alors $B_w = C(u) - C(v)$, sinon, $B_w = 0$

$$ - B(v, S) = \sum_{w \leq v} B_w $$

En d'autres termes, le bénéfice de $V$ est calculé en considérant sa contribution dans la réduction du coût d'évaluation des requêtes. Pour chaque vue $w$ couvrant $v$, nous calculons le coût d'évaluation $w$ en utilisant $v$ et d'autres vues dans $S$ offrant un coût moins élevé pour évaluer $w$. Si la présence de la vue $v$ est inférieure au coût de $w$, alors la différence représente une partie du bénéfice de la matérialisation de la vue $v$. Le bénéfice total $B(v, S)$ est la somme de tous les bénéfices en utilisant $v$ pour évaluer $w$, et fournissant un bénéfice positif. Les auteurs montrent que cet algorithme

**Algorithm 1** Algorithme de Harinarayan et al. [HRU96]

1: A: la capacité d'espace

2: $|v|$: la taille de la vue $v$

3: **while** ($A > 0$) **do**

4:     $v$: vue ayant un bénéfice maximal

5:     **if** ($A - |v| > 0$) **then**

6:         $V := V \cup v$ {$V$: l'ensemble des vues}

7:     **end if**

8: **end while**

présente des performances très proches de l'optimum. Cependant, il parcourt l'espace des solutions possibles à un niveau élevé de granularité et peut éventuellement laisser échapper de bonnes solutions [SDN98].

### 2.3.2.3 Algorithmes dirigés par le temps de maintenance

Ce type d'algorithmes a été étudié par Gupta [Gup99]. Avant de décrire ces algorithmes, quelques définitions sont introduites.
**Définition 3** Un graphe d'une requête (ou vue) de type ET est un graphe de requête (vue) dans lequel cette dernière possède un plan d'exécution unique.

**Définition 4** Un graphe d'une requête (ou vue) de type OU est un graphe de requête (vue) dans lequel cette dernière possède plusieurs plans d'exécution.

Etant donné un graphe de vues de type ET-OU et une quantité S (temps de maintenance disponible), le PSV consiste à sélectionner un ensemble de vues minimisant le temps de réponse total tel que le temps total de maintenance des vues soit inférieur à S. Les auteurs ont présenté deux heuristiques pour résoudre ce problème: (1) un algorithme "glouton" polynômial fournissant une solution quasi-optimale pour les graphes de vues de type ET et pour les graphes de vues de type OU (où chaque requête a de multiple plans d'exécution), (2) un algorithme de type A* [Nil80] pour les graphes de vues de type ET et OU. Notons que tout algorithme de type A* cherche la solution optimale dans un graphe ayant un nombre petit de noeuds, où chacune représente une solution potentielle.

### 2.3.3 Maintenance de vues matérialisées

Un entrepôt de données contient un ensemble de vues matérialisées dérivées à partir de tables qui ne résident pas dans l'entrepôt de données. Les tables de base changent et évoluent à cause des mises à jour. Cependant, si ces changements ne sont pas reportés dans les vues matérialisées, leurs contenus deviendront obsolètes et leurs objets ne représenteront plus la réalité. Par conséquent, un objet d'une vue peut continuer à exister alors que les objets à partir desquels il a été dérivé ont été supprimés ou modifiés. Afin de résoudre ce problème d'inconsistance des données, une procédure de maintenance des vues doit être mise en place.

Trois stratégies fondamentales ont été proposées. Dans la première stratégie, les vues sont mises à jour périodiquement [AL80, LHM+86]. Dans ce cas, ces vues peuvent être considérées comme des photographies (snapshots). Dans la deuxième stratégie [CW81, BLT86], les vues sont mises à jour immédiatement à la fin de chaque transaction. Dans la dernière stratégie, les modifications sont propagées d'une manière différée [SP89]. Dans ce cas, une vue est mise à jour uniquement au moment où elle est utilisée par une requête d'un utilisateur.

Quelle que soit la stratégie adoptée, la maintenance pourrait consister à simplement recalculer le contenu des vues matérialisées à partir des tables sources. Cependant, cette approche est complètement inefficace (très coûteuse). En effet, une bonne maintenance des vues est réalisée lorsque les changements (insertions, suppressions, modifications) effectués dans les tables sources peuvent être propagés aux vues sans obligation de recalculer complètement leur contenu.

Plusieurs techniques ont été proposées dans la littérature pour répondre à ce besoin: la maintenance incrémentale, la maintenance autonome des vues, et la maintenance des vues en batch.

#### 2.3.3.1 Maintenance incrémentale

Une vue matérialisée peut être maintenue d'une manière incrémentale. Cette maintenance consiste à identifier le nouvel ensemble de n-uplets à ajouter à la vue
dans le cas d'une insertion ou le sous-ensemble de n-uplets à retirer de la vue dans le cas d'une suppression, sans pour autant réévaluer complètement la vue [BLT86].

Plusieurs approches traitant le problème de la maintenance incrémentale des vues matérialisées ont été développées dans les bases de données relationnelles classiques [BLT86] et dans les entrepôts de données [RSS96, Gup99]. Nous en retenons deux, les travaux de Blakeley et al. [BLT86] dans le contexte de base de données et les travaux de Ross et al. [RSS96] dans le contexte des entrepôts de données.

Blakeley et al. [BLT86] s'intéressent aux vues SPJ (sélection, projection et join-
ture). Par souci de clarté, nous présentons l'algorithme incrémental pour les vues de
jointures <fnref n="1" />. Soit $V = R_1 \bowtie R_2 \bowtie \dots \bowtie R_n$ une vue joignant $n$ relations. Supposons
que l'on insère les ensembles de n-uplets $\Delta R_i$ dans les relations $R_i$, $i = 1, \dots, n$, res-
pectivement. D'après la propagation de ces insertions au niveau de la vue $V$, nous
obtenons $V' = (R_1 \cup \Delta R_1) \bowtie (R_2 \cup \Delta R_2) \bowtie \dots \bowtie (R_n \cup \Delta R_n)$. En appliquant la
propriété de distributivité de la jointure sur l'union, la mise à jour de $V$ est égale à
l'union de $2^n$ multi-jointures. Les auteurs ont montré que pour maintenir la vue $V$
de façon incrémentale, il est facile d'obtenir toutes les multi-jointures de $V'$ grâce à
une table de vérité dont chaque entrée $B_i$ ($1 \le i \le n$) est associée à une relation $R_i$
de la vue.

$$
\mathbf{B}_i = \begin{cases} 1, & \text{correspond aux nouveaux n-uplets (i.e., } \Delta R_i) \\ 0, & \text{correspond aux anciens n-uplets} \end{cases}
$$

**Exemple 6** Supposons que $n = 3$ ($V = R_1 \bowtie R_2 \bowtie R_3$). L'ensemble de toutes les multi-jointures est décrit dans la Table 2.2.

<table><caption>TAB. 2.2: La description de l’algorithme de Blakeley et al. [BLT86]</caption>
  <thead>
    <tr>
      <th>B<sub>1</sub></th>
      <th>B<sub>2</sub></th>
      <th>B<sub>3</sub></th>
      <th>Multi-jointure</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>0</td>
      <td>0</td>
      <td>R<sub>1</sub> &lt; R<sub>2</sub> &lt; R<sub>3</sub></td>
    </tr>
    <tr>
      <td>0</td>
      <td>0</td>
      <td>1</td>
      <td>R<sub>1</sub> &lt; R<sub>2</sub> &lt; &Delta;R<sub>3</sub></td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
      <td>0</td>
      <td>R<sub>1</sub> &lt; &Delta;R<sub>2</sub> &lt; R<sub>3</sub></td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
      <td>1</td>
      <td>R<sub>1</sub> &lt; &Delta;R<sub>2</sub> &lt; &Delta;R<sub>3</sub></td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>&Delta;R<sub>1</sub> &lt; R<sub>2</sub> &lt; R<sub>3</sub></td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
      <td>1</td>
      <td>&Delta;R<sub>1</sub> &lt; R<sub>2</sub> &lt; &Delta;R<sub>3</sub></td>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>&Delta;R<sub>1</sub> &lt; &Delta;R<sub>2</sub> &lt; R<sub>3</sub></td>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>1</td>
      <td>&Delta;R<sub>1</sub> &lt; &Delta;R<sub>2</sub> &lt; &Delta;R<sub>3</sub></td>
    </tr>
  </tbody>
</table>

Si on suppose que la relation $R_3$ n'est pas mise à jour, nous devons donc évaluer
l'expression suivante:

$$
(\Delta R_1 \bowtie R_2 \bowtie R_3) \cup (R_1 \bowtie \Delta R_2 \bowtie R_3) \cup (\Delta R_1 \bowtie R_2 \bowtie R_3)
$$

La même procédure est appliquée dans le cas de suppression de n-uplets, en
respectant la propriété de la distributivité de la jointure par rapport à la différence.

Ross et al. [RSS96] ont abordé le problème de la maintenance incrémentale de la manière suivante: Etant donné un ensemble de vues V, quelles sont les vues qu'on

<footnote n="1">¹Cet algorithme s'étend naturellement aux vues de types SPJ.</footnote>
peut matérialiser (et maintenir) afin de garantir une maintenance incrémentale op-
timale de l'ensemble V ?

Il est clair que l'ajout d'un nouvel ensemble de vues augmente d'une manière consi-
dérable le besoin d'espace, mais il peut également réduire le coût de maintenance
(compromis entre l'espace et le coût de maintenance). Les auteurs ont formulé le
problème de détermination d'un ensemble optimal de vues additionnelles à matéria-
liser comme un problème d'optimisation sur l'espace de toutes les vues possibles. Ils
ont proposé deux algorithmes dirigés par un modèle de coût (pour plus de détails
voir [RSS96]) dont l'un est exhaustif.

2.3.3.2 Maintenance autonome des vues

Considérons un schéma d'un entrepôt de données ayant un ensemble de tables de base $T = \{T_1, T_2, ..., T_n\}$. Soit $V$ une vue matérialisée. L'ensemble des tables $T$ peut résider dans une ou plusieurs source de données. Un changement au niveau de la table $T_i$ noté par $\Delta T_i$ pourra affecter la vue $V$.

**Définition 5** *Soit V une vue matérialisée calculée à partir d'une table $T_i$. Supposons qu'un changement intervienne au niveau de $T_i$ ($\Delta T_i$). La vue V est dite à maintenir d'une manière autonome si elle peut être maintenable en utilisant seulement la vue V et les changements de $T_i$ ($\Delta T_i$).*

Plusieurs travaux ont été réalisés pour garantir la maintenance autonome des vues matérialisées. Une des approches consiste à *dupliquer* entièrement toutes les données de base dans l'entrepôt. Le processus de maintenance des vues devient alors local à l'entrepôt [GM95, GMS93]. Toutefois cette approche crée de nouveaux problèmes. Les données ajoutées au niveau de l'entrepôt augmentent la capacité d'espace pour stocker les données dupliquées et entraînent une redondance des informations pouvant causer des inconsistances.

Quass et al. [QGMW96] se sont intéressés à la situation où la vue V n'est pas auto-maintenable. Dans ce cas, les auteurs cherchent un ensemble de vues *auxiliaires* $V$ défini sur les mêmes relations que la vue V tel que $\{V\} \cup V$ soit auto-maintenable. Notons que l'ensemble de vues auxiliaires doit être minimal. Les auteurs ne fournissent pas de solution sur ce point.

La plupart des approches maintiennent les vues séparément en utilisant un gestionnaire de vues pour chacune d'elles. Les approches reconnaissant la possibilité pour les vues d'être maintenues ensemble en identifiant les vues en relation sont moins courantes. Cette vision de maintenance autonome de vues multiples a été proposée pour la première fois dans [Huy97].

Un problème qui reste ouvert est de trouver *l'ensemble de vues auxiliaires* le plus économique en termes d'espace et de coût de calcul pour réduire le coût de maintenance des vues matérialisées.

2.3.3.3 Maintenance de vues en batch ou en temps réel

Dans les systèmes commerciaux, la mise à jour s'effectue en batch par l'inter-
médiaire de *transactions de maintenance* [QW97]. Une transaction de maintenance
est relativement longue et peut donc bloquer l'usage de l'entrepôt. Pour cette raison
elle est exécutée pendant les périodes d'activité creuse (la nuit par exemple).
Avec Internet, cette approche n'est pas très souhaitable, l'entrepôt devant rester en ligne 24 heures sur 24. La maintenance incrémentale qui vise une mise à jour instantanée à chaque changement au niveau d'une source de données est coûteuse et n'évite pas les lectures inconsistantes durant l'opération. Dans [QW97], les auteurs ont proposé une approche pour ce problème en maintenant deux versions de chaque n-uplet de l'entrepôt simultanément afin que les transactions de lecture et la transaction de maintenance n'interférent pas.

### 2.3.4 La réécriture des requêtes

Les vues matérialisées sont stockées sous forme de tables relationnelles [BDD$^{+98}$]. Cela permet à l'utilisateur de les interroger, de les indexer, de les partitionner pour améliorer les performances. Après la sélection des vues matérialisées, toutes les requêtes définies sur l'entrepôt doivent être réécrites en fonction des vues disponibles. Ce processus est appelé *réécriture des requêtes en fonction des vues* [SDJL96]. La réécriture des requêtes a attiré l'attention de nombreux chercheurs car elle est en relation avec plusieurs problèmes de gestion de données: l'optimisation de requêtes, l'intégration des données, la conception des entrepôts de données, etc. Le processus de réécriture des requêtes a été utilisé comme une technique d'optimisation pour réduire le coût d'évaluation d'une requête.

Plus formellement, ce processus peut se définir ainsi:
Soit une requête $Q$ définie sur un schéma d'une base de données et un ensemble de vues $\{V_1, V_2, ..., V_n\}$ sur le même schéma. Est-il possible de répondre à la requête $Q$ en utilisant seulement les vues? Alternativement, quel est le plan d'exécution le moins cher pour $Q$ en supposant qu'en plus des tables de la base de données, on a aussi un ensemble de vues?

Supposons que nous ayons une requête $Q$ exprimée en SQL dans laquelle nous trouvons un ensemble de tables de dimensions et la table des faits. La réécriture d'une requête $Q$ en utilisant des vues est une requête $Q'$ référençant ces vues. C'est à dire que dans la clause FROM, nous trouvons des vues, des tables de dimensions et la table des faits.

Sélectionner la meilleure réécriture pour une requête est une tâche difficile. Plusieurs travaux ont été développés dans ce sens (pour plus de détail voir l'étude de Levy [Lev]). La plupart des solutions proposées sont basées sur des modèles de coût. Dans [BDD$^{+98}$], les auteurs décrivent une implémentation d'un algorithme de réécriture pour ORACLE.

## 2.4 Les index

Compte tenu de la complexité des requêtes décisionnelles et de la nécessité d'un temps de réponse court, plusieurs techniques d'indexation ont été développées pour accélérer l'exécution des requêtes. Dans les entrepôts de données, lorsque nous parlons des index, nous devons faire la différence entre: (1) les techniques d'indexation, et (2) la sélection des index.
## 2.4.1 Les techniques d'indexation

Les techniques d'indexation utilisées dans les bases de données de type (OLTP) ne sont pas bien adaptées aux environnements des entrepôts des données. En effet la plupart des transactions OLTP accèdent à un petit nombre de n-uplets, et les techniques utilisées (index $B^+$ par exemple) sont adaptées à ce type de situation. Les requêtes décisionnelles adressées à un entrepôt de données accèdent au contraire à un très grand nombre de n-uplets (ce type de requête est encore appelé *requêtes d'intervalle*). Réutiliser les techniques des systèmes OLTP conduirait à des index avec un grand nombre de niveaux qui ne seraient donc pas très efficaces [OQ97, Cor97b].

Un index peut être défini sur une seule colonne d'une relation, ou sur plusieurs colonnes d'une même relation. Nous appelons ce type d'index mono index. Il pourra être clustérisé ou non clustérisé. Nous pouvons également avoir des index définis sur deux relations comme les index de jointure [Val87] qui sont appelés multi-index.

Dans les entrepôts de données, les deux types d'index sont utilisés: index sur liste des valeurs, et index de projection (pour les mono index), index de jointure en étoile (star join index) pour les index multi-index. Dans la section suivante, nous allons énumérer les nouvelles techniques d'indexation et des variantes des techniques existantes efficaces pour les requêtes décisionnelles.

### 2.4.1.1 Index sur liste des valeurs

Un index sur liste de valeurs est constitué de deux parties. La première partie est une structure d'arbre équilibré et la deuxième est un schéma de correspondance. Ce schéma est attaché aux feuilles de l'arbre et il pointe vers les n-uplets de la table à indexer. L'arbre est généralement de type *B* avec une variation de pourcentage d'utilisation. Deux types différents de schéma de correspondance sont utilisés. Le premier consiste en une liste de RowID associée à chaque valeur unique de la clé de recherche. Cette liste est partitionnée en blocs disque chaînés entre eux. Le deuxième schéma est de type bitmap. Il utilise un index binaire [OQ97] représenté sous forme d'un vecteur de bits. Dans ce vecteur, chaque n-uplet d'une relation est associé à un bit qui prend la valeur 1 si le n-uplet est membre de la liste ou 0 dans le cas contraire. Un index binaire est une structure de taille réduite qui peut être gérée en mémoire, ce qui améliore les performances. De plus, il est possible d'exécuter des opérations logiques (par exemple les opérations ET, OU, XOR, NOT) de manière performante [OQ97].

Cette technique d'indexation est appropriée lorsque le nombre de valeurs possibles d'un attribut est faible (par exemple l'attribut *sexe* qui peut prendre comme valeur masculin ou féminin) (voir Figure 2.11). Évidemment, le coût de maintenance peut être élevé car tous les index doivent être actualisés à chaque nouvelle insertion d'un n-uplet. L'espace de stockage augmente en présence de dimensions de grande cardinalité, parce qu'il faut gérer une quantité importante de vecteurs qui contiennent un grand nombre de bits avec la valeur 0. Pour éviter ce problème, des techniques de compression ont été proposées, comme le "run-length encoding". Dans cette technique, une séquence de bits de la même valeur est représentée de manière compacte par une paire dont le premier élément est la valeur des bits et le deuxième le nombre de bits dans la séquence. L'utilisation de ce type de méthode dégrade les
<figure><img src="image_16.png" /><figcaption>FIG. 2.11: Index binaire</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>FIG. 2.12: Index de projection</figcaption></figure>

performances du système décisionnel à cause des traitements de compression et de décompression des index.

### 2.4.1.2 Index de projection

Soit $C$ la colonne d'une table à indexer. L'index de projection sur $C$ est constitué d'une séquence stockée des valeurs de $C$, ces dernières apparaissant dans le même ordre que le numéro de n-uplet dans la table de laquelle les valeurs ont été extraites (voir Figure 2.12). Les auteurs de [OQ97] ont montré que les index de projection non seulement améliorent d'autres techniques d'indexation traitant les requêtes impliquant deux ou plusieurs colonnes, mais sont également souhaités pour les requêtes de groupement (GROUP-BY). Cette technique est implémentée dans Sybase IQ [OQ97].

### 2.4.1.3 Index de jointure

Les requêtes complexes définies sur une base de données relationnelle demandent fréquemment des opérations de jointure entre plusieurs tables. L'opération de jointure est fondamentale dans les bases de données, et est très coûteuse en terme de temps de calcul lorsque les tables concernées sont grandes [LR98]. Plusieurs méthodes ont été proposées pour accélérer ces opérations. Ces méthodes incluent les boucles imbriquées, le hachage, la fusion etc [Ram98].
<figure><img src="image_18.png" /><figcaption>FIG. 2.13: Index de jointure pour l'équi-jointure Employé.Ville = Département.Ville</figcaption></figure>

Valduriez [Val87] a proposé des index spécialisés appelés *index de jointure*, pour pré-joindre des relations. Un index de jointure matérialise les liens entre deux relations par le biais d'une table à deux colonnes, contenant les RID (identifiant de n-uplet) des n-uplets joints deux par deux (voir Figure 2.13). Cet index peut être vu comme une jointure précalculée. Créé à l'avance, il est implémenté par une *relation d'arité* 2. L'efficacité dépend du coefficient de sélectivité de jointure [Val85]. Si la jointure a une forte sélectivité, l'index de jointure sera petit et aura une grande efficacité. Ce genre d'index est souhaité pour les requêtes des systèmes OLTP car elles possèdent souvent des jointures entre deux tables [Sys97]. Par contre, pour les entrepôts de données modélisés par un schéma en étoile (schéma le plus couramment utilisé), ces indexes sont limités. En effet les requêtes décisionnelles définies sur un schéma en étoile possèdent plusieurs jointures (entre la table des faits et plusieurs tables de dimension). Il faut alors subdiviser la requête en fonction des jointures. Or le nombre de jointures possibles est de l'ordre de $N!$, $N$ étant le nombre de tables à joindre (*problème d'ordonnancement de jointure* [KL90]).

Pour résoudre ce problème, Red Brick [Sys97] a proposé un nouvel index appelé *index de jointure en étoile* (star join index), adapté aux requêtes définies sur un schéma en étoile. Un index de jointure en étoile peut contenir toute combinaison de clés étrangères de la table des faits. Supposons par exemple que nous ayons un schéma en étoile modélisant les ventes au niveau d'un grand magasin. Ce schéma contient une table des faits VENTES et trois tables de dimensions (TEMPS, PRODUIT et CLIENT). Un index de jointure en étoile peut être n'importe quelle combinaison contenant la clé de la table de faits et une ou plusieurs clés primaires des tables de dimensions.

Ce type d'index est dit **complet** s'il est construit en joignant toutes les tables de dimensions avec la table des faits. Un index de jointure partiel est construit en joignant certaines des tables de dimensions avec la table des faits. En conséquence, l'index complet est bénéfique pour n'importe quelle requête posée sur le schéma en étoile. Il exige cependant beaucoup d'espace pour son stockage.

A ce stade de notre présentation, deux remarques s'imposent concernant l'index de jointure en étoile:

- Comme son nom l'indique, ce type d'index est exclusivement adapté aux schémas en étoile [JLS99b]. Par contre, pour d'autres schémas comme le flocon de
<figure><img src="image_19.png" /><figcaption>FIG. 2.14: L'architecture de l'outil de sélection d'index</figcaption></figure>

neige, ces index ne sont pas bien adaptés. Notons qu'il n'existe pas d'index de jointure efficace pour tous les schémas logiques de type ROLAP.

- Dans la littérature, nous ne trouvons pas d'algorithmes de sélection d'index de jointure en étoile pour un ensemble de requêtes. Ce problème est important car très souvent il n'est pas possible de construire un index de jointure en étoile complet. Il faut donc sélectionner un ou plusieurs index de jointure en étoile pour satisfaire au mieux les requêtes.

## 2.4.2 Le problème de sélection des index

Comme pour le PSV, le PSI consiste, à partir d'un ensemble de requêtes décisionnelles et la contrainte d'une ressource donnée (l'espace, le temps de maintenance, etc.) à sélectionner un ensemble d'index afin de minimiser le coût d'exécution des requêtes. Ce problème a été reconnu par la communauté académique et industrielle. Les chercheurs ont modélisé le PSI comme un problème d'optimisation et ont proposé des heuristiques afin de trouver des solutions optimales ou quasi-optimales.

Récemment, le groupe base de données de Microsoft a développé un outil pour sélectionner des index avec Microsoft SQL Server 7.0 [CN98]. Étant donné une charge constituée d'un ensemble de requêtes SQL, l'outil de sélection des index recommande d'une manière automatique un ensemble d'index pour cette charge. L'utilisateur peut spécifier des contraintes, par exemple une borne maximale pour l'espace aloué ou pour le nombre d'index. L'outil permet à l'utilisateur d'établir une analyse quantitative de l'impact de la recommandation proposée. Si l'utilisateur accepte les recommandations, l'outil crée (et/ou élimine) des index afin que les index recommandés soient matérialisés. L'architecture de l'outil de sélection des index proposé est illustrée dans la Figure 2.14.

L'outil prend un ensemble de requêtes définies sur un schéma de base de données.
Le traitement est itératif. Durant la première itération, il choisit les index sur une colonne (mono-index); dans la deuxième les index sur deux colonnes et ainsi de suite. L'algorithme de recherche d'index est testé en fonction de ces trois modules: (1) la sélection des index candidats, (2) l'énumération des configurations <fnref n="2" /> et (3) la génération des multi-index.

- Le module de sélection des index candidats permet de déterminer la meilleure configuration pour chaque requête d'une manière indépendante. Finalement, il fait l'union de ces configurations.

- Le module d'énumération des configurations: s'il existe *n* index candidats, et que l'outil doit sélectionner *k* parmi *n* index, le module d'énumération doit énumérer toutes les configurations, et à l'aide d'un modèle de coût sélectionner le meilleur ensemble de configurations garantissant un coût minimal.

Cet algorithme de sélection des index prend une requête à un moment donné et sélectionne tous les index possibles. Cependant, l'ensemble des index utilisant cette méthodologie pourra exiger beaucoup d'espace de stockage et des coûts de maintenance élevés.

Dans le but de minimiser les coûts de stockage et de maintenance, Chaudhuri et al. [CN99] ont proposé une technique appelée *fusion d'index* (index merging). Elle prend un ensemble d'index ayant une capacité d'espace *S* et fournit un nouvel ensemble d'index ayant une capacité d'espace *S'* inférieure à celle de départ (*S'* < *S*). L'opération de fusion est guidée par un modèle de coût: la fusion est appliquée s'il y a une réduction dans le coût d'exécution des requêtes. La technique de fusion d'un ensemble d'index ressemble à la reconstruction des fragments verticaux d'une relation donnée. Le problème de fusion des index est formulé comme suit:

**Entrées:**

- Une configuration d'index initiale $C = \{I_1, I_2, ..., I_N\}$

- Un ensemble de requêtes $Q = \{Q_1, Q_2, ..., Q_p\}$

- Une borne maximale $U$ pour le coût d'exécution des requêtes

Le but consiste à trouver une configuration minimale $C' = \{J_1, J_2, ..., J_k\}, k \le N$ tel que:

- coût($Q, C$) $\le$ $U$, (coût($Q, C$) représente le coût (ou estimation) d'exécution de l'ensemble des requêtes de $Q$ en présence de la configuration $C$)

- $C'$ doit avoir un coût de stockage inférieur à celui de $C$.

### 2.4.3 Discussion

Jusqu'à présent, nous avons présenté les deux problèmes PSV et PSI ainsi que les algorithmes proposés pour les résoudre. Avant d'aller plus loin, quelques remarques s'imposent:

1. Le PSV et PSI sont réalisés durant la phase de conception logique et physique de l'entrepôt, respectivement. Ces deux problèmes sont fortement dépendants.

2. Tous les algorithmes proposés pour résoudre ces problèmes sont dirigés par un modèle de coût. Ce dernier permet non seulement de dire si une vue (ou

<footnote n="2">²Les auteurs utilisent le terme *configuration* pour signifier un ensemble d'index</footnote>
index) est plus bénéfique qu'une autre vue (ou index), mais également de guider
ces algorithmes dans leur sélection. En conséquence il faut prévoir un modèle
de coût des requêtes pour mieux les optimiser [Naa99]. Le modèle de coût
accepte en paramètre le plan d'exécution d'une requête et retourne son coût.
Le coût d'un plan d'exécution est évalué en cumulant le coût des opérations
élémentaires (sélection, jointure, etc.). Ces modèles de coûts contiennent, d'une
part, des statistiques sur les données et, d'autre part, des formules pour évaluer
le coût. Ces coûts sont mesurés en unités de temps si l'objectif est de réduire
le temps de réponse des requêtes, le nombre d'entrées-sorties ou le temps de
maintenance des vues et des index.

3. Ces deux problèmes sont traités d’une manière séquentielle; c’est-à-dire, d’abord la sélection des vues matérialisées et ensuite la sélection des index. Cette façon de procéder ne prend pas en compte l’interaction entre les vues et les index et pose un problème de gestion de ressources. Par exemple, considérons que ces deux problèmes soient contraints par la capacité d’espace. Il s’agit alors de savoir comment distribuer l’espace entre les vues et les index afin de garantir une meilleure performance des requêtes.

Dans la section suivante, nous présenterons quelques travaux traitant du PSV en présence des index.

2.4.4 La sélection des vues en présence des index

Tous les travaux précédents considèrent la sélection des vues à matérialiser sans
index et la sélection des index sans vues matérialisées. Dans cette section, nous
regardons certains travaux de sélection considérant simultanément les vues et les
index. Parmi ces travaux, on trouve ceux de Labio et al. [LQA97] et Gupta et al.
[GHRU97].

2.4.4.1 Les travaux de Labio et al.

Rappelons d'abord que Ross et al. [RSS96] ont abordé le problème de la mainte-
nance des vues d'une manière incrémentale, et ont démontré la possibilité de réduire
le temps total de maintenance des vues en matérialisant un ensemble de vues addi-
tionnelles.

Labio et al. [LQA97] ont repris la même formulation du problème [RSS96] (voir
section 2.3.3), mais en plus de vues additionnelles, ils considèrent l'ajout des index.
Soit un ensemble de vues matérialisées {$V_1, V_2, ..., V_n$}, déjà sélectionnées par un
algorithme de sélection donné. Leur approche consiste à choisir un ensemble de vues
additionnelles (appelées vues de support) et un ensemble d'index à matérialiser afin
que le coût total de maintenance soit minimal.

**Exemple 7** La Figure 2.15 montre un entrepôt de données avec trois relations R, S et T provenant des sources R<sub>SRC</sub>, S<sub>SRC</sub> et T<sub>SRC</sub> avec l'objectif de répondre à des requêtes basées sur une jointure R ⊕ S ⊕ T. Supposons que R ⊕ S ⊕ T (RST) soit matérialisée. Cette vue est appelée la vue primaire. Dans la Figure 2.16, nous supposons qu'une autre vue (ST) est matérialisée. Elle est appelée vue de support. En matérialisant la vue ST, le coût total de maintenance des deux vues RST et ST pourra être moins élevé que le coût de maintenance de la vue primaire seule.
<figure><img src="image_20.png" /><figcaption>FIG. 2.15: Entrepôt avec une vue primaire</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>FIG. 2.16: Entrepôt avec une vue de support</figcaption></figure>

Les auteurs calculent d'abord le nombre d'ES nécessaire pour maintenir les vues matérialisées et les relations de base de l'entrepôt de données. Ils ajoutent ensuite un ensemble de vues additionnelles et des index qui eux-mêmes doivent être maintenus. L'opération d'ajout peut avoir lieu si le coût total de l'évaluation des requêtes l'emporte sur le coût de maintenance des vues et des index.

Pour résoudre le problème, Labio et al. [LQA97] ont proposé un algorithme basé sur $A^*$ [Nil80] qui donne la solution optimale. L'inconvénient majeur de cette solution est sa difficulté d'application lorsque le nombre de vues devient très grand. Pour surmonter la complexité de cet algorithme, les auteurs ont proposé des règles de bon sens (rules of thumb) qui peuvent aider l'administrateur de l'entrepôt dans le choix des vues de support et d'index (pour plus de détails, voir [LQA97]).

En fait, nous pouvons dire que Labio et al. [LQA97] ont traité le problème de maintenance des vues mais non pas le problème de sélection des vues et des index.

### 2.4.4.2 Les travaux de Gupta et al. [GHRU97]

Les auteurs ont combiné le PSV et PSI en un seul problème appelé problème de sélection des vues et des index (PSVI) dans un cube de données. L'idée de base de leur travaux est de considérer les vues et les index comme un seul ensemble. Le PSVI est formulé comme suit:

- Soit un ensemble de vues matérialisées $V = \{V_1, V_2, ..., V_n\}$, dont chaque vue $V_i$ possède un ensemble de mono index.

- Soit un ensemble de requêtes $Q$ les plus fréquemment utilisées (une vue et des index peuvent être utilisés pour répondre à une requête donnée).

- Soit $S$ la quantité d'espace allouée pour stocker les vues et les index sélectionnés.

Le PSVI consiste à sélectionner un ensemble de vues et d'index qui ne devront pas occuper un espace supérieur à $S$, afin de minimiser le coût total d'évaluation de ces requêtes. Ce problème est NP-complet [GHRU97]. Le PSVI est formalisé sous la forme d'un graphe bipartite $G = (V \cup Q, E)$, appelé graphe de requête-vue.

- Chaque vue $V_i \in V$ est associée à un u-uplet $(S_i, I_i)$, $S_i$ est l'espace occupé par la vue $V_i$, et $I_i$ est l'ensemble des index de cette vue.
- Un coût par défaut est associé à chaque requête, représentant le coût pour évaluer cette requête sans vue et sans index.

- Chaque arête $(Q_i, V_j)$ est associée à un ensemble d'étiquettes $(k, t_{ijk})$, où $t_{ijk}$ est le coût d'évaluation de la requête $Q_i$ en utilisant la vue $V_j$ et son kième index.

L'algorithme naïf pour résoudre ce problème consiste à tester tous les candidats (vues et index) et à sélectionner la meilleure solution. Cet algorithme est impratiable dans la réalité, compte tenu du nombre trop élevé de candidats. Les auteurs ont donc proposé un algorithme appelé "r-glouton" pour résoudre ce problème. L'algorithme "r-glouton" fonctionne par étapes. Au lieu de sélectionner un objet à chaque étape de l'algorithme naïf, cet algorithme sélectionne plusieurs objets à la fois. Supposons que nous soyons dans une étape où nous avons sélectionné une structure $M^3$. Pendant cette étape, l'algorithme considère tous les ensembles possibles ayant au plus $r$ structures qui sont, soit (1) une vue et quelques uns de ses index, soit (2) un seul index dont la vue a déjà été sélectionnée dans les étapes précédentes.

Parmi tous les ensembles considérés, l'ensemble présentant le bénéfice maximum au niveau de l'espace sera sélectionné. Cet algorithme garantit de bonne performances lorsque chaque structure occupe le même espace. Cela est rarement le cas en pratique.

En ce qui concerne la complexité de cet algorithme, supposons qu'il y ait $v$ vues et $i$ index. Pour chaque étape, l'algorithme doit alors considérer et calculer le bénéfice d'au moins $(v \times i + C_{r-1}^i)$ ensembles. La borne supérieure du temps d'exécution de cet algorithme est donnée par $O(l \times m^r)$, où $m$ est le nombre de structures dans le graphe de requête-vue, et $l$ le nombre de structures sélectionnées par l'algorithme, respectivement.

## 2.5 La fragmentation

Dans la littérature, deux termes sont utilisés pour la segmentation d'une relation: *partitionnement* et *fragmentation*. Le partitionnement d'une relation se définit par la division de cette dernière en plusieurs partitions disjointes. La fragmentation consiste en la division en plusieurs fragments (sous-ensembles de la relation) qui peuvent être non disjoints. Cependant, la plupart des chercheurs utilisent les deux termes indifféremment [NKR95, OV91]. Dans cette thèse, nous ne ferons pas de différence entre les deux concepts.

Dès le début des années 80, de nombreuses études ont été menées sur la fragmentation dans les bases de données relationnelles [CNP82, CP84, CY87, NCWJ84, NR89]. Avec l'apparition des systèmes de bases de données objets, de nouvelles études ont vu le jour [KNM94, KL95, KLV96, Bel96, BSS96, BS96, EB95, BKS97, BKL98b].

**Définition 6** *Un schéma de fragmentation [KNM94] est le résultat du processus de la fragmentation.*

<footnote n="3">³Une structure est un ensemble de vues et d'index</footnote>
## 2.5.1 Les types de fragmentation

Comme nous l'avons déjà mentionné précédemment, deux sortes de fragmentation sont possibles: la fragmentation horizontale et la fragmentation verticale.

### 2.5.1.1 La fragmentation verticale

Dans la fragmentation verticale, une relation est divisée en sous relations appelées *fragments verticaux* qui sont des projections appliquées à la relation.

Soit une relation $R(K, A_1, A_2, ..., A_n)$, avec $n$ attributs $A_1, A_2, ..., A_n$ et une clé $K$. Chaque attribut $A_i$ a un domaine de valeurs que nous appelons $dom(A_i)$. La fragmentation verticale de la relation $R$ est donnée par:
$$V^1(K, A_1^1, A_2^1, ..., A_{k_1}^1), V^2(K, A_1^2, A_2^2, ..., A_{k_2}^2), ..., V^p(K, A_1^p, A_2^p, ..., A_{k_p}^p)$$ où chaque attribut $A_i^j \in \{A_1, A_2, ..., A_n\}$. Les fragments verticaux $V_1, V_2, ..., V_p$ sont disjoints si chaque attribut $A_i$ ($1 \le i \le n$) de la relation $R$ appartient à un et un seul fragment vertical. La clé $K$ est dupliquée dans chaque fragment afin de faciliter la reconstruction de la relation $R$ à partir de ces fragments qui est réalisée par la jointure de $p$ fragments verticaux.

La fragmentation verticale favorise naturellement le traitement des requêtes de projection portant sur les attributs utilisés dans le processus de la fragmentation, en limitant le nombre de fragments à accéder. Son inconvénient est qu'elle requiert des jointures supplémentaires lorsqu'une requête accède à plusieurs fragments.

### 2.5.1.2 La fragmentation horizontale

Comme pour la fragmentation verticale, la fragmentation horizontale a été étudiée dans le cadre des bases de données relationnelles. Elle consiste à diviser une relation $R$ en sous ensembles de n-uplets appelés *fragments horizontaux*, chacun étant défini par une opération de restriction appliquée à la relation. Les n-uplets de chaque fragment horizontal satisfait une clause de prédicats 4. Le schéma de fragmentation de la relation $R$ est donné par:
$$H_1 = \sigma_{cl_1}(R), H_2 = \sigma_{cl_2}(R), ..., H_q = \sigma_{cl_q}(R),$$ où $cl_i$ est une clause de prédicats. La reconstruction de la relation $R$ à partir de ces fragments horizontaux est obtenue par l'opération d'union de ces fragments.

La fragmentation horizontale se décline en deux versions [CNP82]: les fragmentations *primaire* et *dérivée* (ou indirecte [GGT96]). La fragmentation primaire d'une relation est effectuée grâce à des prédicats de sélection définis sur la relation [OV91]. La fragmentation horizontale dérivée s'effectue avec des prédicats de sélection définis sur une autre relation.

La fragmentation horizontale primaire favorise le traitement des requêtes de restriction portant sur les attributs utilisés dans le processus de la fragmentation. La fragmentation horizontale dérivée est utile pour le traitement des requêtes de jointure.

### 2.5.1.3 La fragmentation mixte

La fragmentation mixte combine les deux types de fragmentation: horizontale et verticale. Elle consiste à partitionner une relation en sous-ensembles de sous-

<footnote n="4">4 Une clause de prédicats est une combinaison de prédicats avec les opérateurs logiques `∧` et `∨`</footnote>
relations, ces dernières étant définies par la fragmentation verticale et les sous-ensembles par la fragmentation horizontale.

### 2.5.2 Les contextes de la fragmentation

L'idée sous-jacente à la fragmentation est de pouvoir constituer des ensembles de données partielles dont les attributs (pour la fragmentation verticale) et les n-uplets (pour la fragmentation horizontale) ont des propriétés géographiques communes. Le mot géographique peut, comme nous allons le voir, être perçu à une échelle différente suivant le contexte *centralisé, réparti* ou *parallèle*.

**Définition 7** Une base de données répartie [GGT96, OV91] est un ensemble de bases de données coopérantes, chacune résidant sur un site différent, cet ensemble étant vu et manipulé par l'utilisateur comme une seule base de données centralisée.

**Définition 8** Une base de données parallèle est une base de données répartie homogène dont les sites sont les noeuds d'une machine parallèle (multi-processeurs), les noeuds communiquent par messages.

**Le contexte centralisé** La fragmentation verticale dans un contexte centralisé favorise naturellement le traitement des requêtes de projection portant sur les attributs utilisés dans la définition des fragments, en limitant le nombre de fragments à accéder.

La fragmentation horizontale permet de limiter le nombre de pages accédées, ou en d'autres termes, à réduire le nombre de n-uplets accédés inutilement.

**Le contexte réparti** Le principe général reste bien sûr le même. Seule, l'interprétation de la notion de propriétés géographiques, communes entre attributs, change. Dans le contexte réparti, la fragmentation consiste à découper une relation par rapport à un ensemble de sites. Il faut donc une certaine adéquation entre les sites et l'utilisation des données. Dans un tel contexte, deux phases se distinguent lorsqu'on parle de la fragmentation: la phase de partitionnement en elle-même, et la phase d'allocation des fragments aux sites.

Les premiers travaux importants sur la fragmentation ont été réalisés dans le contexte de la conception d'une base de données répartie (distributed database design) [CNP82, CP84, NCWJ84, OV91, OV99].

**Le contexte parallèle** Dans ce contexte, la fragmentation consiste à partitionner les données d'une relation afin de pouvoir les traiter en parallèle et ainsi diminuer le temps de réponse. Il n'est donc plus question de rassembler les données utilisées simultanément, mais au contraire de les disséminer pour obtenir un taux important de parallélisme pour l'exécution d'une même opération. Les fragmentations verticale et horizontale permettent respectivement l'augmentation du parallélisme inter-requêtes et intra-requêtes.

### 2.5.3 Les avantages et les inconvénients de la fragmentation

Les objectifs de la fragmentation de données sont multiples:
- limiter le nombre d'accès inutiles aux données (attributs ou n-uplets).

- limiter le transfert de données (en nombre et en volume) en les répartissant où elles sont le plus utilisées dans le cas d'une base de données répartie (par exemple dans les agences d'une banque nationale, ou encore aux guichets de réservation d'une compagnie aérienne).

- accroître les performances par la répartition de la charge de travail en plusieurs unités de traitement opérant en parallèle.

- augmenter la fiabilité en faisant effectuer le même traitement par plusieurs ordinateurs. Par exemple, dupliquer les données sur différents sites, lorsque la base de données concerne un domaine sensible où la moindre erreur peut avoir des conséquences catastrophiques (comptes bancaires, centrales nucléaires, lancement de fusées spatiales).

- étendre la disponibilité des informations, en les dupliquant sur plusieurs sites. L'exemple type est l'annuaire téléphonique national dont chaque ville importante possède un exemplaire.

La fragmentation a plusieurs avantages, mais elle a aussi des inconvénients [OV91]:

- Certains problèmes, tels que la sécurité, la synchronisation ou la coordination, sont difficiles à résoudre dans les systèmes répartis.

- Le manque de méthode de conception d'une base de données répartie. De nos jours, il n'existe pas ou peu de méthodes ou outils pour convertir une base de données centralisée en une base de données répartie.

- Qui dit fragmentation des données, dit surplus d'informations de maintenance tels que les dictionnaires globaux et locaux de données, les fonctions de partitionnement, les index locaux et globaux, etc. La gestion de ces informations et de ces mécanismes est parfois complexe et nécessite une charge supplémentaire. L'administrateur d'une base de données fragmentée doit assurer la transparence aux utilisateurs.

- La principale difficulté de la fragmentation horizontale réside dans le fait qu'une opération de mise à jour dans une relation de schéma global se traduit par plusieurs sous-opérations de mises à jour dans différents fragments. Il faut donc identifier les fragments concernés, puis décomposer l'opération initiale en un ensemble d'opérations sur ces fragments. Après l'opération de mise à jour, certains n-uplets devront changer de fragments (migration de n-uplets). Cette opération de migration peut être coûteuse.

La fragmentation semble être une bonne technique pour l'amélioration des performances dans les entrepôts de données connus pour leur taille volumineuse. Oracle dans sa version Oracle8i offre une option de fragmentation (partitioning option) permettant de fragmenter un schéma d'un entrepôt de données, ses vues matérialisés, et ses index.

### 2.5.4 Les algorithmes de fragmentation verticale

Le problème de la fragmentation verticale est de déterminer comment partitionner une relation (ou une classe) en fragments, dans le but de maximiser la performance du système. Dès les années 70, de nombreux travaux ont été proposés pour
<figure><img src="image_22.png" /><figcaption>FIG. 2.17: Principe général de la méthode de Hammer et Niamir</figcaption></figure>

définir les fragments verticaux d'un fichier [ES76], d'une relation [NCWJ84, CPW89, HN79, NR89], d'une classe [EB95, BSS96] ou de bases de données parallèles définies avec le modèle $NF^2$ (Non First Normal Form) [Nic91]. Sélectionner les fragments optimaux d'une relation est un problème difficile: en effet, une relation de $m$ attributs peut être fragmentée en $B(m)$ différentes manières [OV91], $B(m)$ étant le nombre de Bell. Pour $m$ grand, $B(m)$ peut atteindre $m^m$.

Dans cette section, nous présentons deux travaux que nous considérons de base dans la littérature de la fragmentation verticale: les travaux de Hammer et al. [HN79] et ceux de Navathe et al. [NCWJ84].

### Travaux de Hammer et Niamir
Les auteurs ont proposé une solution basée sur un modèle de simulation pour l'évaluation des performances présentées par le schéma après une fragmentation verticale. Les deux composantes principales de cette méthode sont: (1) un générateur de partitions et (2) un évaluateur de performances qui attribue une valeur de mérite à chaque partition (voir Figure 2.17).

Le générateur de partitions fonctionne aussi selon un principe heuristique qui comprend deux étapes itératives. A chaque itération, le générateur construit un ensemble de variations autour de la fragmentation courante. Les variations sont ensuite soumises à l'évaluateur, et la fragmentation qui représente le plus faible coût est sélectionnée comme la fragmentation courante de l'itération suivante.

Les différences entre les deux étapes concernent le choix de la fragmentation initiale et la génération des variations. Dans la première étape, la fragmentation initiale est constituée de fragments à un seul attribut. La fragmentation initiale de
la deuxième étape est celle obtenue à l'issue de la 2ème étape. Dans la première étape, les variations sont générées en considérant toutes les fusions (deux à deux) possibles des blocs de la fragmentation courante. Dans la seconde, les variations sont obtenues par mouvement d'un seul attribut à la fois de son bloc actuel vers tous les autres blocs.

L'évaluation des performances se fait grâce à un estimateur de coûts de transactions qui simule le nombre de pages de la mémoire secondaire transférées pendant l'exécution des transactions. L'algorithme s'arrête dès qu'aucune opération de fusion n'est possible ou qu'aucune réduction du coût n'est constatée.

**Les travaux de Navathe et al.** Ces travaux ont approfondi ceux de Hoffer et al. [HS75] et Hammer et al. [HN79]. Deux approches ont été proposées par Navathe et al.: le partitionnement binaire [NCWJ84] et le partitionnement graphique [NR89].

La première approche suppose une relation ayant *m* attributs à fragmenter et un ensemble de *n* requêtes les plus fréquentes. Elle s'exécute en deux phases. Pendant la première phase, trois matrices sont construites: (i) la matrice d'usage des attributs, (ii) la matrice des affinités d'attributs, et (iii) la matrice d'affinité ordonnée.

- Dans la matrice d'usage des attributs, la valeur de l'élément de la ligne *i* et la colonne *j* a pour valeur 1 si l'attribut *j* est accédé par la requête *i*, sinon cette valeur est nulle. Cette matrice est complétée par une valeur de fréquence d'accès pour chacune des requêtes représentée dans une colonne supplémentaire.

- La matrice des affinités d'attributs a *m* lignes et *m* colonnes correspondant aux attributs de la relation à fragmenter. La valeur de l'élément de la ligne *i* et la colonne *j* reporte les valeurs d'affinité définies entre ces attributs. Cette affinité correspond à la somme des fréquences d'accès des requêtes accédant simultanément aux deux attributs.

- La matrice d'affinité ordonnée est obtenue après l'application de l'algorithme de B.E.A. [MSW72] sur la matrice des affinités d'attributs. Par permutation de lignes et de colonnes, l'algorithme B.E.A. regroupe les attributs qui sont utilisés simultanément en fournissant une matrice sous la forme d'un semi-bloc diagonal.

La deuxième phase est la recherche des fragments verticaux qui optimisent une fonction objectif. Elle consiste à effectuer un partitionnement binaire récursif de la matrice d'affinité ordonnée. Cette étape revient à définir des sous-matrices sur la diagonale principale. Chaque sous-matrice regroupe un ensemble de valeurs proches et donc d'attributs fréquemment accédés simultanément. Chaque sous-matrice contient donc les attributs d'un fragment vertical.

Pour la seconde approche, Navathe et Ra [NR89] ont présenté une méthode de regroupement des attributs basée sur les graphes. Cet algorithme part de la matrice des affinités d'attributs considérée comme un graphe complet, appelé **graphe d'affinité**. Les noeuds de ce graphe représentent les attributs de la relation à fragmenter, et les valeurs des arêtes représentent les valeurs d'affinités. Cet algorithme cherche à générer des cycles dont les arêtes possèdent des grandes valeurs d'affinités. Ces cycles sont appelés cycles d'affinités qui sont en fait des fragments potentiels.
Cet algorithme présente l'avantage d'avoir une complexité en $O(m^2)$ plus faible que celle de l'algorithme proposé dans [NCWJ84] ($O(m^2(\log m))$), m étant le nombre d'attributs de la relation à fragmenter.

### 2.5.5 Les algorithmes de fragmentation horizontale

Les algorithmes de fragmentation primaire proposés dans les contextes relationnel et objet se divisent en deux catégories: (1) les algorithmes basés sur la minimalité et la complétude des prédicats (travaux de Ceri et al. [CNP82, CP84] et de Özsu et al. [OV91]), (2) les algorithmes dirigés par les affinités des prédicats (travaux de Na-vathe et al. [NR89]). Ces algorithmes ont été développés dans les bases de données relationnelles et ont été adaptés pour prendre en considération les caractéristiques du modèle objet (méthodes, attributs complexes, héritage, etc.) [EB95, BKS97, Rav96].

Ces deux types d'algorithmes partagent les mêmes entrées, c'est-à-dire, qu'ils partent d'un ensemble de requêtes et de leur fréquence d'accès. Ces requêtes respectent la règle de 80/20, signifiant que 20% de requêtes produisent 80% des accès aux données [NKR95].

Avant de décrire ces algorithmes, quelques définitions s'imposent:

**Définition 9** Un prédicat simple [CNP82] $p$ est de la forme :
$p: \text{Attribut } \theta \text{ Valeur; avec } \theta \in \{=, <, \le, >, \ge, \ne\}, \text{ Valeur} \in D_i \text{ et } D_i \text{ est le domaine de l'attribut } A_i$.

**Définition 10** La fréquence d'accès d'une requête [EB95] est le nombre d'accès aux données que la requête pourra faire pendant une période spécifique. Dans notre contexte, ces données peuvent être une relation, un fragment, ou un n-uplet.

**Définition 11** Un prédicat pertinent [CNP82] Un prédicat simple $p$ est pertinent à un ensemble de prédicats simples $P$ s'il existe un prédicat simple $q \in P$ tel que les fragments horizontaux définis par $(p \wedge q)$ et $(p \wedge \neg q)$ soient accédés individuellement par au moins une application.

**Définition 12** Un ensemble de prédicats est dit minimal s'il ne contient que des prédicats qui lui sont pertinents.

#### 2.5.5.1 Les algorithmes dirigés par la minimalité et la complétude des prédicats

Özsu et al. [OV91] ont proposé dans le prolongement des travaux de Ceri et al. [CNP82] une méthode de fragmentation dont les étapes sont les suivantes:

1. **Classification des transactions:** il s'agit de regrouper, dans une même classe, toutes les transactions ayant pour origine le même noeud du réseau d'ordinateurs composant le système réparti. Notons qu'une fréquence d'accès est associée à chaque transaction.

2. **Spécification d'un ensemble complet et minimal de prédicats simples:** à partir de ces transactions, on énumère tous les prédicats simples $P$. La complétude garantit que chaque fragment soit accédé par toutes les applications avec la même probabilité. L'algorithme de production d'un ensemble de prédicats complet et minimal (COM-MIN) à partir d'un ensemble de prédicats simples procède
en deux étapes. La première étape initialise l'ensemble résultat avec un prédicat et sa négation qui partitionne la relation en deux fragments, chacun étant accédé par au moins une application. La seconde étape est itérative, et ajoute tout nouveau prédicat qui partitionne un fragment défini dans l'ensemble résultat en deux fragments, chacun étant accédé par au moins une application. Lors de cette étape, les prédicats qui deviennent non pertinents par rapport à l'ensemble résultat sont éliminés.

**Algorithmme 2** Algorithme générant des prédicats minimaux et complets

1. **Données:** Une relation $R$ et un ensemble de prédicats simples $\mathcal{P}$ définis sur $R$

2. **Sortie:** Un ensemble complet et minimal de prédicats simples $\mathcal{P}'$ de $\mathcal{P}$

3. Déclaration: $F$ : l'ensemble de fragments, $f_i$ : un fragment défini par un minterm $m_i$

4. **Règle 1:** Toute relation est partitionnée en au moins deux fragments qui seront accédés différemment par au moins une application

5. Initialisation:

6. $\mathcal{P}' = \emptyset$

7. Chercher un prédicat $q_i$ de $\mathcal{P}$ tel que $q_i$ partitionne $R$ en respectant la règle 1

8. $\mathcal{P}' = q_i; \mathcal{P} = \mathcal{P} - q_i; F = f_i$

9. **repeat**

10. Chercher un prédicat $q_i$ de $\mathcal{P}$ tel que $q_i$ partitionne $f_k$ de $F$ en respectant la règle 1

11. $\mathcal{P}' = \mathcal{P}' \cup q_i; \mathcal{P} = \mathcal{P} - q_i; F = F \cup f_i$

12. **if** il existe $q_k \in \mathcal{P}'$ qui n'est pas pertinent **then**

13. $\mathcal{P}' = \mathcal{P}' - q_k$

14. $F = F - f$

15. **end if**

16. **until** $\mathcal{P}'$ est complet

3. **Construction des prédicats minterm $M$ de $\mathcal{P} = \{q_1, ..., q_n\}$:** ces prédicats sont générés de la façon suivante:

$$M = \{m_i \mid m_i = \bigwedge_{q_j \in \mathcal{P}} q_j^*\} \text{ avec } q_j^* = q_j \text{ ou } q_j^* = \neg q_j \quad (1 \le j \le n), (1 \le i \le 2^n).$$

4. **Elimination des minterms non significatifs:** cette élimination est réalisée par l'identification des minterms contradictoires par rapport à un ensemble d'imPLICATIONS (voir l'algorithme 3).

### 2.5.5.2 Les algorithmes dirigés par les affinités

Zhang et al. [ZO94] ont adapté l'algorithme proposé par Navathe et al. [NCWJ84] en considérant les trois matrices: la matrice d'usage des prédicats, la matrice d'affinité des prédicats et la matrice d'affinité ordonnée. Ces dernières sont construites de la même façon que celles introduites pour la fragmentation verticale.
**Algorithmme 3** L’algorithme de fragmentation primaire de Ozsu et al.

1: **données:** Une relation $R$, un ensemble de prédicats simples $\mathcal{P}$

2: **sortie:** Un ensemble de fragments

3: $\mathcal{P}' = \text{COM\_MIN}(R, \mathcal{P})$

4: déterminer l'ensemble de minterms $M_i$

5: déterminer l'ensemble des implications $I$ entre les prédicats $p_i$ de $\mathcal{P}'$

6: **for** each minterm $m_i \in M_i$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $m_i$ est contradictoire en respectant $I$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$M_i := M_i - m_i$

9: **end if**

10: **end for**

11: Le nombre de fragments horizontaux correspond aux nombre de minterms résultat.

12: La clause de chaque fragment horizontal représente un minterm.

- Les lignes et les colonnes de la matrice d'usage des prédicats représentent les $n$ requêtes de départ utilisées dans le processus de la fragmentation et les $m$ prédicats de sélection définis dans ces requêtes. La valeur de l'élément de la ligne $i$ et la colonne $j$ a pour valeur 1 si le prédicat $j$ est utilisé par la requête $i$, sinon cette valeur est nulle.

- La matrice d'affinité des prédicats a $m$ lignes et $m$ colonnes correspondants aux prédicats de sélection. La valeur de l'élément de la ligne $i$ et la colonne $j$ reporte les valeurs d'affinité définies entre ces prédicats. Cette affinité correspond à la somme des fréquences d'accès des requêtes accédant simultanément aux deux attributs.

- La matrice d'affinité ordonnée est obtenue après l'application de l'algorithme de B.E.A. [MSW72] sur la matrice d'affinité des prédicats (voir section 2.5.4).

La dernière étape de l'algorithme proposé par Zhang et al. [ZO94] consiste à construire les fragments horizontaux à partir des semi-blocs diagonaux obtenus après l'applicatiion de l'algorithme de B.E.A. La construction d'un fragment à partir d'un semi-bloc consiste à lier tous les prédicats simples comprenant le même attribut par l'opérateur logique OU et les prédicats avec des attributs distincts avec l'opérateur logique ET. Enfin, ils définissent le fragment résiduel en construisant la négation de la disjonction des différents prédicats de fragmentation.

### 2.5.6 La fragmentation horizontale dérivée

Une relation $S$ (relation membre) peut contenir une clé étrangère vers une relation $R$ (relation propriétaire) [CP84]. La fragmentation horizontale dérivée est définie sur la relation membre $S$ en fonction des fragments horizontaux de la relation propriétaire $R$.
<figure><img src="image_23.png" /><figcaption>FIG. 2.18: Les différents types de graphe de jointure</figcaption></figure>

Plus formellement, soit $R$ une relation propriétaire horizontalement fragmentée en $m$ fragments horizontaux $\{R_1, R_2, ..., R_m\}$. Soit $S$ une relation membre. Les fragments horizontaux dérivés $\{S_1, S_2, ..., S_m\}$ de $S$ sont définis par l'opération de jointure suivante:

$$S_i = S \llcorner R_i \qquad (2.1)$$

Trois informations sont nécessaires pour effectuer une fragmentation horizontale dérivée: (1) le nom de la relation membre et de la relation propriétaire, (2) le nombre de fragments horizontaux de la relation membre, et (3) la qualification de la jointure entre ces deux relations.

La fragmentation horizontale dérivée pourra jouer un rôle important dans la réduction du coût de jointure entre deux ou plusieurs relations, qui est une des opérations les plus coûteuses dans les bases de données [LR98]. Pour mieux situer ce rôle, nous introduisons quelques définitions.

**Définition 13** La jointure distribuée [CNP82] est une jointure entre des relations horizontalement fragmentées.

Lorsqu'une application nécessite une opération de jointure entre deux relations globales $R$ et $S$, tous les n-uplets de $R$ doivent être comparés à ceux de $S$, d'où la nécessité de comparer tous les fragments $\{R_1, R_2, ..., R_n\}$ de $R$ avec tous les fragments $\{S_1, S_2, ..., S_n\}$ de $S$. Mais souvent certaines jointures partielles ($R_i \llcorner S_j$) sont vides. Il est donc intéressant de les identifier a priori.

Une jointure distribuée peut être représentée par un graphe appelé *graphe de jointure* dont les noeuds représentent les fragments de $R$ et $S$. Une arête est introduite lorsque la jointure entre les fragments correspondants n'est pas vide (Figure 2.18).

**Définition 14** Un graphe de jointure est dit **total** [CNP82] lorsqu'il contient toutes les arêtes possibles entre les fragments de $R$ et les fragments de $S$. Il est dit **réduit** sinon. Un graphe de jointure réduit est dit **partitionné** s'il est composé de deux ou plusieurs sous-graphes non connexes. Un graphe de jointure réduit est dit **simple** s'il est partitionné et si chaque sous-graphe a une seule arête.

Déterminer si une jointure a un graphe de jointure simple est très important dans les bases de données relationnelles fragmentées [CP84], car il permettra la jointure en parallèle en joignant séparément les fragments liés par une arête et en faisant ensuite l'union des résultats.
<figure><img src="image_24.png" /><figcaption>FIG. 2.19: Le principe général de la fragmentation mixte</figcaption></figure>

## 2.5.7 Les algorithmes de fragmentation mixte

La fragmentation mixte combine la fragmentation horizontale et la fragmentation verticale [CP84, NR89, PKN91]. Une méthodologie de fragmentation mixte a été développée comme une partie du Projet ($D^3T$) (Distributed Database Design Tool) à l'Université de Floride [Kar96]. Tous les algorithmes de fragmentation mixte ont été étudiés dans le contexte relationnel. Deux types d'algorithmes sont distingués: la fragmentation par création de grilles [NR89] et la fragmentation par la définition de vues [PKN91].

### 2.5.7.1 La fragmentation par création de grilles

Cet algorithme a été proposé par Navathe et al. [NR89]. Sa première étape consiste à fragmenter horizontalement et verticalement une relation puis à combiner le résultat de ces deux fragmentations afin de construire une grille comme le montre la Figure 2.19. Chaque cellule de cette grille définie par un prédicat de sélection de la fragmentation horizontale et un prédicat de projection de la fragmentation verticale correspond à un fragment mixte [Kar96] (Figure 2.19). Puisque le nombre de cellules peut être très grand, Karlapalem [Kar96] dans sa thèse présente un algorithme d'optimisation qui consiste à trouver les cellules adjacentes afin de minimiser un coût.
<figure><img src="image_25.png" /><figcaption>FIG. 2.20: Les différents algorithmes pour la fragmentation horizontale</figcaption></figure>

### 2.5.7.2 La fragmentation par définition de vues

Pernul et Karlapalem [PKN91] ont considéré que les vues font partie intégrante du modèle de données d'une base de données. Les auteurs ont présenté une méthodologie de décomposition des relations du schéma d'une base de données en sous-ensembles de fragments disjoints. Un ou plusieurs fragments représentent une vue. La procédure de fragmentation se décompose en trois étapes:

1. Trouver toutes les vues ayant une intersection,

2. Pour chaque paire de vues recouvrantes, effectuer une décomposition structurée d'une vue en appliquant respectivement les processus de la fragmentation verticale, horizontale primaire et horizontale dérivée afin de construire des fragments potentiels disjoints.

3. Appliquer les processus de la fragmentation verticale, horizontale primaire et horizontale dérivée sur les vues isolées.

### 2.5.8 Bilan et discussion

La Figure 2.20 propose un récapitulatif des différents travaux de la fragmentation horizontale dans les bases de données. L'inconvénient majeur des algorithmes dirigés par la complétude et la minimalité des prédicats est qu'ils génèrent $2^n$ minterms pour n prédicats simples. Dans certaines applications comme les entrepôts de données, où les requêtes possèdent un grand nombre de prédicats de sélection [DRT99], ces algorithmes peuvent être impraticables. En plus, ils demandent un calcul combina-toire des probabilités d'accès pour déterminer la complétude des prédicats simples (voir l'étape 2 de ces algorithmes).
Les algorithmes dirigés par les affinités sont moins complexes que ceux basés sur la complétude et la minimalité. Mais l'inconvénient majeur est le même que celui défini pour la fragmentation verticale [FKL97]. La matrice d'affinité peut exprimer l'affinité *seulement* entre des paires de prédicats, mais pas entre plusieurs prédicats. D'où la nécessité de développer des algorithmes de fragmentation d'une complexité raisonnable et garantisant une meilleure performance.

Finalement, ces deux types d'algorithmes n'offrent aucune garantie sur l'optima-
lité de leur solution. Intuitivement, la fragmentation horizontale réduit le nombre
d'accès inutiles pendant l'évaluation d'une requête. Malheureusement ces algorithmes
ne possèdent pas de mesure qui permettrait d'évaluer le bénéfice apporté par l'utili-
sation d'un algorithme donné de fragmentation. Le principe de groupement qu'utilise
ces algorithmes est basé sur une seule information, à savoir la fréquence des requêtes
(Figure 2.20). Cependant, d'autres paramètres plus importants sont à considérer
(par exemple, le coût d'exécution d'une requête).

Notons que tous les algorithmes de fragmentation (horizontale et verticale) sont
statiques. Lors d'un changement dans les entrées de ces algorithmes, ces derniers
devront être réexécutés pour définir de nouveaux fragments. Deux types de change-
ments peuvent être distingués dans les bases de données: *les changements physiques*
*et les changements logiques*.

- Les changements physiques concernent le système physique supportant la base de données. Ils incluent l’ajout de nouveaux disques, le changement de la topologie du réseau (si la base de données est répartie).

- Les changements logiques incluent la modification (ajout, suppression) des requêtes, le changement du modèle de données de la base de données, le changement de la fréquence d'accès des requêtes.

La notion de grille proposée par Karlapalem [Kar96] est un concept important qui pourra être utilisé dans le processus de re-fragmentation des relations grâce aux opérations de groupement de cellules [Kar96].

Notons que la plupart des algorithmes de fragmentation partent d'un ensemble
de requêtes (les plus fréquentes) que le concepteur doit déterminer. La détermination
de cet ensemble est parfois délicate. Pernul et al. [PKN91] ont suggéré d'utiliser les
vues à la place des requêtes dans le processus de fragmentation, car les vues peuvent
être construites en *avance* sans connaître les requêtes des utilisateurs.

2.5.9 La fragmentation dans les bases de données objet

Karlapalem et al. [KNM94] ont été les premiers à étudier les aspects de la frag-
mentation dans les modèles objets. Ces derniers se sont essentiellement concentrés
sur les besoins des algorithmes de fragmentation et non sur les algorithmes en eux-
mêmes [ODV92]. Ils définissent les concepts suivants: attribut simple, attribut com-
plexe, méthode simple et méthode complexe.

Dans [KL95], les auteurs définissent les concepts de fragments verticaux et hori-
zontaux de classes. Un *fragment-classe vertical* d'une classe *C* est un sous-ensemble
non vide de l'ensemble d'attributs de *C* et son ensemble d'objets est identique à
*C*. Un *fragment-classe horizontal* d'une classe *C* possède une définition structurelle
identique à celle de *C* et son ensemble d'objets représente un sous-ensemble non
vide de *C*. Une représentation objet est proposée pour implémenter les fragments verticaux et horizontaux. Cette représentation facilite le support de la transparence de la fragmentation. Les algorithmes de partitionnement définis pour le modèle relationnel [NCWJ84, NR89] peuvent être adaptés pour les bases de données objet. Toutefois aucune précision n'est donnée à ce sujet.

Ezeife et Barker [EB95] ont suggéré des algorithmes pour les fragmentations verticale et horizontale. Se basant sur les concepts de Karlapalem et al. [KNM94], ils définissent les attributs simples (le domaine de l'attribut est atomique) et complexes (le domaine de l'attribut est une autre classe) ainsi que les notions méthodes simples (elles n'invoquent pas d'autres méthodes) et complexes (elles invoquent d'autres méthodes). Les algorithmes proposés sont basés sur les affinités entre les méthodes définies dans les requêtes. La construction des fragments suit la démarche suivante:

- Les méthodes sont réparties en groupes en utilisant le concept d'affinité entre méthodes et en reprenant les algorithmes développés dans [NCWJ84]. Cette première étape permet de construire la matrice d'usage pour chaque classe. Les lignes et les colonnes de cette matrice représentent les requêtes et les méthodes spécifiques à la classe *C*, respectivement.

- Les groupes de méthodes sont complétés par les attributs manipulés par ceux-ci. Si un même attribut est manipulé par plusieurs groupes, il est placé dans le groupe avec lequel il a le plus d'affinité.

Un ensemble d'algorithmes pour la fragmentation horizontale pour quatre modèles de classes est proposé: (1) classes d'attributs simples et méthodes simples, (2) classes d'attributs complexes et méthodes simples, (3) classes d'attributs complexes et méthodes complexes, (4) classes d'attributs simples et méthodes complexes. Ils reprennent les principes de l'algorithme de Özsu et al. [OV91] avec la même notion de prédicats simples. Leur complexité est exponentielle en nombre de prédicats simples.

## 2.5.10 La fragmentation dans les entrepôts de données

Peu de travaux ont apporté une solution à la fragmentation dans les entrepôts de données, bien que ces derniers contiennent de très grandes tables.

Wu et al. [WB97] dans leur article "research issues in data warehousing" ont recommandé l'utilisation de la fragmentation verticale et horizontale dans les entrepôts de données pour améliorer l'évaluation des requêtes en évitant le balayage des grandes tables. Il est précisé que les algorithmes développés dans les bases de données réparties doivent être adaptés et réévalués pour les entrepôts de données. Deux cas d'utilisation de la fragmentation dans les entrepôts sont considérés:

- Une table des faits peut être partitionnée d'une manière horizontale en fonction d'une ou plusieurs table(s) de dimension. En d'autres termes, la table des faits peut être fragmentée en utilisant la fragmentation dérivée.

- Une table des faits peut également être fragmentée verticalement; toutes les clés étrangères de la table des faits y sont partitionnées. Cependant la reconstruction des tables fragmentées verticalement nécessite l'opération de jointure, qui est très coûteuse.

Les auteurs [WB97] n'ont pas proposé d'algorithme de fragmentation.
Le concept de fragmentation verticale a été introduit dans la définition des index de projection dans les entrepôts par O'Neil et al. [OQ97]. Les index de projection ressemblent à un fragment vertical d'une relation.
Dernièrement, Datta et al. [DRT99] ont développé un nouvel index appelé “Curio” dans les entrepôts modélisés par un schéma en étoile. Basé sur la fragmentation verticale de la table des faits, il permet d'accélérer l'exécution des requêtes décisionnelles, et élimine la duplication des données en stockant l'index et non pas les colonnes indexées. Cela permet de réduire l'espace nécessaire pour ces index.

Golfarelli et al. [GMR99] ont utilisé la fragmentation verticale pour partitionner les vues matérialisées. Pour eux, le terme de fragmentation verticale signifie deux choses: d'une part *le partitionnement* des attributs d'une vue en plusieurs fragments et d'autre part *l'unification* en une seule vue de deux ou plusieurs vues ayant une clé commune. L'unification correspond à la règle de reconstruction d'une table fragmentée à partir de ses fragments verticaux [OV91].

Pour ce qui est de la fragmentation horizontale, peu de travaux ont été réalisés, excepté celui de Noaman et al. [NB99]. Ces auteurs ont proposé une technique de construction d'un entrepôt réparti en utilisant la stratégie descendante [GV90]. Cette stratégie est couramment utilisée pour la conception de bases de données réparties. Elle part du schéma conceptuel global d'un entrepôt, qu'elle répartit pour construire les schémas conceptuels locaux. Cette répartition se fait en deux étapes essentielles, à savoir, la fragmentation et l'allocation, suivies éventuellement d'une optimisation locale [CMVN94]. Les auteurs [NB99] se sont inspirés de ce qui avait été fait pour les bases de données relationnelles [OV91]. Ils ont proposé une architecture pour un entrepôt distribué, basée sur l'architecture ANSI/SPARC [TK78] et suggéré un algorithme adapté de Özsu et al. [OV91] pour fragmenter la table des faits.

### 2.5.11 La transparence de la fragmentation

Lorsqu'une relation est fragmentée en plusieurs fragments, le système doit assurer la transparence aux utilisateurs, c'est à dire cacher aux utilisateurs le fait que les données sont fragmentées. L'utilisateur ne manipule que des relations conceptuelles non partitionnées. Dès que l'utilisateur pose une requête, ces requêtes doivent être automatiquement transposées sur les fragments, en identifiant les fragments valides. Le même processus d'identification est réalisé lors des opérations de mise à jour. Ce problème a jusqu'à présent été peu pris en compte par les chercheurs.

## 2.6 Le groupement

Le groupement de données (clustering dans la terminologie anglo-saxonne) consiste à stocker les données (n-uplets ou objets) logiquement liées (c'est à dire, susceptibles d'être utilisées fréquemment ensemble) proches les unes des autres en mémoire secondaire. L'avantage de cette technique est que lorsqu'un objet est chargé depuis le disque, tous les objets liés sont chargés en même temps en mémoire primaire. En conséquence, un groupement judicieux des objets minimise en fait non seulement le nombre de pages disques à lire, mais aussi le nombre d'objets non pertinents chargés en mémoire primaire. Dans les systèmes relationnels, de telles optimisations sont
principalement destinées à accélérer les opérations de jointure, grâce à la création de clusters [Dar99]. Dans le cadre des bases de données objet, le groupement est plus complexe compte tenu des caractéristiques des modèles objet (lien de composition, hiérarchie d'héritage, etc.) [Dar99].

Dans les entrepôts, peu de travaux ont été réalisés sur le groupement. Un seul article traite le problème [JLS99a]. Il s'agit de Jagadish et al. [JLS99a] qui ont considéré le problème de regrouper les enregistrements de la table des faits, afin de minimiser le nombre entrées-sorties d'exécution d'un ensemble de requêtes. Sélectionner les clusters optimaux est un problème combinatoire compte tenu des hiérarchies définies sur les attributs des tables. Les auteurs ont proposé des heuristiques de groupement basés sur les courbes Z et les courbes de Hilbert.

Le problème de regroupement a été largement étudié dans le data mining. Le but de cette technologie est d'extraire des données pour permettre à une entreprise d'améliorer ses fonctions de soutien au marketing, aux ventes et au service client à travers une meilleure compréhension de ses clients. Parmi les techniques les plus utilisées dans le data mining nous trouvons le regroupement, qui consiste à segmenter une population hétérogène en un certain nombre de sous-groupes plus homogènes, ou clusters. Les enregistrements sont en fait regroupés en fonction d'une similitude mutuelle. L'analyse des clusters est souvent préalable à une autre forme d'exploitation des données. Par exemple, pour une étude de segmentation de marché, au lieu de chercher une règle comme "à quel type de promotion les clients répondent le mieux?", il est possible de diviser la base de données client en clusters de personnes ayant les mêmes habitudes de consommation avant de poser la question pour chaque cluster.

Après avoir défini le concept de groupement, nous avons quelques remarques à présenter:

- La fragmentation et le groupement sont orthogonaux, le premier est réalisé pendant la conception logique de l'entrepôt et le deuxième pendant la conception physique.

- Les deux concepts ont le même objectif, à savoir regrouper les objets afin de minimiser le nombre des entrées-sorties.

- Les fragments peuvent être considérés comme des unités de groupement, si tous les n-uplets d'un fragment sont stockés de façon contiguë sur le disque.

## 2.7 Incidences pratiques

Les problèmes et les approches considérés dans ce chapitre et dans ce travail ont des incidences pratiques importantes et ont suscité l’intérêt des éditeurs et des utilisateurs de SGBD. Dans cette section nous explicitons certaines de ces incidences, [BKM00a]. Nous indiquons en particulier comment certaines de ces approches ont été incorporées dans ORACLE 8i et Microsoft SQL server.

### 2.7.1 Partitionnement des données

ORACLE 8i incorpore le partitionnement horizontal pour gérer les grands objets (tables, vues matérialisées, index) et les décomposer en parties plus petites
appelées partitions. ORACLE 8i propose plusieurs méthodes de partitionnement : le partitionnement par intervalles, le partitionnement par hachage, le partitionnement composite, et le partitionnement orienté jointure. Dans le partitionnement par intervalles, les données dans la table (la vue ou l'index) sont partitionnées relativement à des intervalles de valeurs. Dans le partitionnement par hachage les données sont partitionnées relativement à une fonction de hachage. Dans le partitionnement composite les données sont partitionnées par intervalles et ensuite subdivisées en utilisant une fonction de hachage. Finalement dans le partitionnement orienté jointure, une opération de jointure est divisée en jointures plus petites qui sont exécutées en séquence ou en parallèle. Pour utiliser ce partitionnement les deux tables doivent être équi-partitionnées.

## 2.7.2 Vues matérialisées

ORACLE 8i incorpore un processus de réécriture de requête qui transforme une commande SQL de telle façon qu'elle puisse accéder aux vues matérialisées. Cet outil de réécriture permet de réduire significativement le temps de réponse pour des requêtes d'agrégation ou de jointure dans les grandes tables des entrepôts. Quand une requête cible une ou plusieurs tables de base pour calculer un agrégat (ou pour réaliser une jointure) et qu'une vue matérialisée contient les données requises, l'optimiseur d'ORACLE peut réécrire la requête d'une manière transparente pour exploiter la vue, et procurer ainsi un temps de réponse plus court. Si les données requises ne sont pas disponibles dans une unique vue matérialisée, mais dans plusieurs, l'administrateur doit définir un index de jointure couvrant les tables de base pour optimiser la requête. Il n'est pas certain que les administrateurs disposent des outils adéquats pour identifier les situations pour lesquelles ces index sont intéressants.

## 2.7.3 Interaction entre les index et les vues

Ce problème a reçu une grande attention de la part des industriels et des utilisateurs. Récemment le DEM (Data Management, Exploration Mining Group) de Microsoft Research a présenté des solutions pour sélectionner automatiquement un ensemble approprié de vues matérialisées et d'index pour une base de données relationnelle. Cette sélection passe par l'énumération de tous les index et vues pouvant contribuer à l'exécution d'un ensemble de requêtes. Une réduction du nombre de candidats est effectuée ensuite par l'optimiseur de requêtes (via son modèle de coût). Un ensemble final d'index et de vues matérialisées est alors proposé.

D'une manière plus générale, les outils et les techniques développés dans ce chapitre constituent un ensemble cohérent sur lequel peut s'appuyer valablement l'administrateur d'un entrepôt, non seulement pour concevoir l'entrepôt, mais aussi pour l'optimiser en tenant compte des changements dans les requêtes des utilisateurs. Un entrepôt convenablement conçu exécutera les requêtes des usagers plus rapidement tout en facilitant l'actualisation des données. Ces facilités contribueront à améliorer la compétitivité de l'entreprise et faciliteront l'incorporation des changements dans le comportement des usagers et des changements dans l'environnement de l'entreprise.
## 2.8 Conclusion

Dans cette partie, nous avons non seulement présenté les principales techniques d'optimisation des requêtes utilisées dans les entrepôts de données, mais également décrit les problèmes liés à chaque technique. Dans les prochaines sections, nous apportons des solutions à quelques problèmes concernant: la définition des index de jointure pour les vues matérialisées, la gestion et la distribution de l'espace entre les vues et les index, la fragmentation horizontale.
# Chapitre 3

## Les index de jointure pour les vues matérialisées

### 3.1 Introduction

À partir des données d'un entrepôt, de nombreuses analyses (e.g., data mining) peuvent être réalisées afin d'améliorer la productivité et la qualité des services offerts aux utilisateurs de l'entrepôt. Ces analyses sont effectuées en examinant des données extraites de l'entrepôt à l'aide des requêtes décisionnelles. Ces dernières sont très complexes (contenant de multiples jointures, opérations de groupement, etc.) et, par conséquent, peuvent demander un temps de calcul élevé. Les décideurs au niveau des entreprises exigent un temps de réponse raisonnable afin de prendre rapidement des décisions. Pour satisfaire cet objectif, l'entrepôt matérialise un ensemble de vues (persistantes) définies sur des tables sources, qui seront stockées et périodiquement rafraîchies pour refléter les modifications survenues au niveau des sources. La présence des vues accélère l'exécution de certaines requêtes. Les requêtes en question sont appelées requêtes bénéficiaires. Cette accélération est due au fait que ces requêtes n'accèdent pas aux tables sources (c'est l'avantage principal des vues matérialisées).

La principale caractéristique des requêtes bénéficiaires est que leur résultat coïncide exactement ou partiellement avec des vues matérialisées. En effet, le résultat d'une requête peut être une vue entière, une projection d'une vue, une sélection d'une vue, ou une jointure de plusieurs vues. Il faut noter que nous ne pouvons pas matérialiser toutes les vues possibles pour satisfaire toutes les requêtes (actuelles et futures) définies sur un entrepôt. Cette contrainte est due à la limitation des ressources, e.g., l'espace disque destiné au stockage des vues matérialisées, ou le coût de leur maintenance. En conséquence, certaines requêtes ne retirent aucun bénéfice des vues matérialisées. Pour les exécuter, on doit accéder aux tables sources, et cette exécution peut être très coûteuse.

La sélection des vues matérialisées dans un entrepôt joue un rôle important dans la réduction du coût d'évaluation des requêtes. Une bonne sélection doit maximiser le nombre des requêtes bénéficiaires. En effet, la sélection des vues à matérialiser représente un enjeu important pour les administrateurs des entrepôts. Cet enjeu a motivé chercheurs [BPT97, Gup99, GM95, MK00, YKL97] et industriels [BDD$^{+}$98, SSN00] pour développer des algorithmes de sélection offrant de bonnes performances
<figure><img src="image_26.png" /><figcaption>FIG. 3.1: Les trois scénarios d'exécution d'une requête</figcaption></figure>

(voir Chapitre 2).

Une fois les vues sélectionnées, toutes les requêtes décisionnelles définies sur l'entrepôt doivent être réécrites en fonction de ces vues et des tables de base. Cette réécriture permet de réduire le coût des requêtes [SDJL96, BDD+98].

Plus formellement, soit $Q$ une requête décisionnelle définie sur un schéma d'un entrepôt ayant un ensemble de $d$ tables de base dénoté par $\mathcal{T}\mathcal{B} = \{TB_1, TB_2, ..., TB_d\}$. Supposons que, sur ce schéma, un ensemble de vues matérialisées $V = \{V_1, V_2, ..., V_k\}$ ait été sélectionné. L'optimiseur doit prendre en compte ces vues matérialisées pour trouver le meilleur plan d'exécution de la requête $Q$. Trois scénarios se présentent à l'optimiseur pour réaliser sa tâche (voir Figure 3.1):

- **Scénario 1:** La requête $Q$ est exécutée en utilisant seulement des vues matérialisées.

- **Scénario 2:** La requête $Q$ est exécutée en utilisant des vues matérialisées et des tables de base,

- **Scénario 3:** La requête $Q$ est exécutée en utilisant des tables de base seulement.

Si nous associons à chaque scénario un coût (calculant le nombre des entrées-sorties pendant l'évaluation de la requête $Q$, par exemple), c'est-à-dire le coût $C_1$ (pour le scénario 1), le coût $C_2$ (pour le scénario 2), et le coût $C_3$ (pour le scénario 3), nous pouvons déclarer d'une manière intuitive que:

$$C_1 \ll C_2 \ll C_3 \qquad (3.1)$$

Généralement, cette inégalité n'est pas toujours satisfaite comme nous allons le voir dans la section 3.9.

Certes, la présence des vues matérialisées a un effet positif sur la réduction du coût d'exécution des requêtes, mais sans techniques d'indexation, ce coût reste toujours important [BKS00, LQA97, SSN00]. Étant donné que les vues peuvent être stockées sous forme de tables, les techniques d'indexation des tables peuvent être facilement adaptées aux vues. La définition de ces index dépend du scénario.

**Les index dans le premier scénario** Les index sont définis seulement sur les vues. Deux types d'index sont possibles: (1) les index simples et (2) les index de jointure.
<figure><img src="image_27.png" /><figcaption>FIG. 3.2: L’indexation dans les trois scénarios</figcaption></figure>

1. Un index simple peut être défini sur une ou plusieurs colonnes d'une vue. Cette indexation peut être réalisée en utilisant les mêmes techniques que celles dédiées aux tables (e.g., arbre $B^+$, index de projection, index binaire, etc. (voir chapitre 2)).

2. Un index de jointure peut être défini sur deux ou plusieurs vues. Si l'opération de jointure est définie sur deux vues seulement, l'index de jointure de Valduriez et al. [Val87] peut être utilisé. Par contre, si elle concerne plus de deux vues, il n'existe pas a priori d'index de jointure performant [BKL00].

**Les index dans le deuxième scénario** Les index simples peuvent être définis soit sur les vues soit sur les tables de base. Les index de jointure peuvent être définis entre: (1) des vues seules, pour accélérer par exemple des jointure de plusieurs vues, (2) des tables seules, ou (3) entre des vues et des tables. Les observations sur les index de jointure décrites dans le paragraphe précédent sont valides également dans ce scénario.

**Les index dans le troisième scénario** Ce cas ressemble au premier, mais au lieu d'indexer les vues, on indexe les tables. Les index simples sont définis sur les tables. L'application des index de jointure dépend du schéma de l'entrepôt. Si ce dernier est modélisé par un schéma en étoile, l'index de jointure en étoile défini par Redbrick [Sys97] peut être utilisé. Il peut réduire le coût d'exécution de toute requête en étoile<fnref n="1" />. Mais si l'entrepôt de données est modélisé par un autre schéma que le schéma en étoile, il n'existe pas d'index de jointure utilisable pour satisfaire les requêtes joignant plusieurs tables [JLS99b].

La Figure 3.2 résume les techniques d'indexation pour chaque scénario.

## 3.2 Objectifs visés

La conception d'un entrepôt de données est réalisée en trois étapes principales, à savoir: (i) *le processus de sélection des vues matérialisées*, (ii) *le processus de selection*

<footnote n="1">¹Cette appellation est destinée aux requêtes définies sur un schéma en étoile (voir chapitre 2)</footnote>
<figure><img src="image_28.png" /><figcaption>FIG. 3.3: Les étapes de conception physique de l'entrepôt</figcaption></figure>

réécriture des requêtes en fonction des vues matérialisées, et (iii) le processus de sélection d'index (Figure 3.3). Ces étapes partagent le même objectif: optimiser la performance des requêtes décisionnelles [SDJL96, CN98, YKL97].

En examinant la littérature, nous constatons que la première et la deuxième étape ont été largement étudiées par les communautés académique et industrielle (voir Chapitre 2). Dans ce chapitre, nous ne développons pas de nouveaux algorithmes pour la sélection des vues à matérialiser, ou la réécriture des requêtes en fonction des vues, mais nous utilisons les algorithmes existants.

Pour la sélection des vues matérialisées, nous étendons l'algorithme de Yang et al. [YKL97]. Notre choix s'est porté sur cet algorithme pour deux raisons :

1. Il est bien adapté au contexte ROLAP et coïncide donc avec notre étude.

2. Il a été développé par le groupe de recherche avec lequel j'ai collaboré pendant deux ans (Department of Computer Science, Hong Kong University of Science and Technology).

La description de cet algorithme fera l'objet de la section 3.3.

Pour le processus de réécriture, nous utilisons l'approche adopté par [SDJL96, BDD+98]. Nous illustrons ce processus dans la section 3.4.

Dans ce chapitre, nous nous concentrons sur la troisième phase de la conception d'un entrepôt, **la sélection d'index**, et plus précisément sur la définition et la sélection d'index de jointure en présence des vues matérialisées. Ce type d'index n'a pas suscité beaucoup d'intérêt de la part des chercheurs.

Le reste du chapitre décrit notre approche de sélection des index en présence des vues matérialisées. La section 3 décrit en détail l'algorithme de sélection des vues matérialisées de Yang et al. [YKL97]. La section 4 présente le processus de réécriture des requêtes en fonction des vues matérialisées. À travers la section 5, nous tirons un bilan sur l'insuffisance des techniques d'optimisation des jointures existantes dans les entrepôts de données. Cette section introduit les index de graphe de jointure et
justifie leur intérêt. La section 6, présente une stratégie d'exécution des requêtes en présence des index de graphe de jointure. La section 7 décrit un modèle de coût évaluant le coût d'exécution d'un ensemble de requêtes sur un schéma indexé par les index proposés. La section 8 donne la complexité de la sélection des index de graphe de jointure. Elle formule le problème de sélection des index et propose trois algorithmes: un **algorithme exhaustif** et **deux algorithmes gloutons** pour sélectionner les index optimaux ou quasi-optimaux pour un ensemble de requêtes. Finalement la section 9 illustre l'utilité de ces index à travers des expérimentations.

## 3.3 La sélection des vues matérialisées

Dans cette section, nous décrivons l'algorithmes de Yang et al. [YKL97], que nous appelons *sélect_vue*<fnref n="2" />. La description de cet algorithme nécessite le rappel de quelques concepts et définitions.

### 3.3.1 Concepts et définitions

#### 3.3.1.1 Bases de données relationnelles

Les notions de base du modèle relationnel sont les suivantes: **univers**, **attribut**, **schéma**, **domaine**, **relation** [Cod70]. Pour modéliser une application réelle, on détermine d'abord les propriétés pertinentes auxquelles on s'intéresse. Dans la terminologie relationnelle, ces propriétés sont appelées *attributs*.

Un univers est un ensemble fini, non vide, noté $U = \{A_1, A_2, ..., A_n\}$, où chaque élément est appelé attribut. À chaque attribut $A_i$ de $U$, est associé un ensemble appelé **domaine** de $A_i$, noté par $Dom(A_i)$; chaque élément de ce domaine est considéré comme une valeur possible de la propriété représentée par l'attribut.

Nous considérons des requêtes SQL de la forme suivante [SDJL96]:

```
Q: SELECT Sel(Q) % Q: requête
FROM Table(Q)
WHERE Cond(Q)
GROUPBY Groups(Q)
```

où Sel(Q), Table(Q), Cond(Q) et Groups(Q) représentent respectivement l'ensemble des colonnes (agrégation ou non) de la clause SELECT, l'ensemble des tables à manipuler, la condition de sélection, et un sous-ensemble des colonnes de Sel(Q) servant au regroupement.

#### 3.3.1.2 L'algèbre relationnelle

L'algèbre relationnelle a été introduite par Codd [Cod70] comme une collection d'opérations formelles agissant sur des relations et produisant des relations en résultats [Cod70]. Codd a initialement introduit des opérations, dont certaines peuvent être composées à partir d'autres. Ces opérations sont: la sélection ($\sigma$), la projection (Π), la jointure (ém), l'union (U), la différence, le produit cartésien [Gar83, EN94].

<footnote n="2">²Rappelons que cet algorithme appartient à la catégorie statique de PSV: il optimise un ensemble de requêtes a priori connues (voir chapitre 2)</footnote>
<figure><img src="image_29.png" /><figcaption>FIG. 3.4: Les opérateurs relationnels</figcaption></figure>

Une requête exprimée sous forme d'une expression algébrique peut être représentée par un arbre relationnel. La figure 3.4 représente les opérateurs relationnels ainsi que leur représentation graphique.

**Définition 15 (Un arbre relationnel)** Soit $Q$ une requête exprimée sous forme algébrique $E_Q$. L'arbre relationnel de la requête $Q$ est un arbre $A : (N, V)$ dont les noeuds $N$ correspondent à:

- Le nom de la requête dénoté par $Q$ et représentant le sommet de cet arbre,

- Les noms des relations à partir desquelles la requête $Q$ est définie. Ces noeuds représentent les feuilles de l'arbre, et

- Les noms des résultats intermédiaires résultant de l'évaluation des opérations successives.

Les arcs désignent les opérandes de chaque opérateur. Les expressions suivantes: graphe de requête, graphe de calcul, arbre algébrique, renvoient au même concept. Au cours de cette thèse, nous utilisons indifféremment ces termes.

**Exemple 8** Soit $Q$ la requête définie en SQL sur le schéma en étoile de la Figure 2.5 de la façon suivante:

<table><tr><td>SELECT</td><td>PID</td><td>SUM(V.ventes_sales)</td></tr><tr><td>FROM</td><td>CLIENT</td><td>VENTES</td></tr><tr><td>WHERE</td><td>CLIENT.Cid = VENTES.Cid</td><td>% prédicat de jointure</td></tr><tr><td>AND</td><td>CLIENT.Etat = 'IL'</td><td>% prédicat de sélection</td></tr><tr><td>GROUP BY</td><td>PID</td><td></td></tr></table>

L'arbre algébrique de cette requête est illustré par la Figure 3.5. Il contient deux feuilles représentant la table de dimension `CLIENT` et la table des faits `VENTES`, et trois noeuds intermédiaires représentant les résultats de l'opération de jointure, de sélection et de projection.

Tout graphe de requête doit respecter les règles suivantes:

1. Un sommet admet deux prédécesseurs s'il représente une relation produite par un opérateur relationnel binaire.

2. Un sommet n'admet qu'un seul prédécesseur s'il représente une relation produite par un opérateur relationnel unaire.

3. Quel que soit le type de l'opérateur, un sommet intermédiaire n'admet qu'un seul successeur.
<figure><img src="image_30.png" /><figcaption>FIG. 3.5: L'arbre algébrique correspondant à la requête $Q$</figcaption></figure>

4. Un sommet représentant une table de base n'admet pas de prédécesseur, les tables de base sont les feuilles du graphe. Les feuilles sont les seuls noeuds à admettre plusieurs successeurs car dans la même expression algébrique, on peut définir plusieurs variables sur la même relation.

5. Il existe un sommet unique dans $N$ (l'ensemble des noeuds du graphe) n'admettant aucun successeur; il s'agit de la racine de l'arbre à laquelle est attachée le résultat et qui porte le nom de la requête.

### 3.3.2 Motivation de l'algorithme sélect_vue

Cette section présente un aperçu progressif des aspects clés de l'algorithme sélect_vue. Pour ce faire, considérons le schéma en étoile de la Figure 2.5. Supposons que nous ayons deux requêtes décisionnelles $Q$ (définie dans l'exemple 8) et $Q'$ dont la description est:

```sql
SELECT PID, SUM(VENTES.ventes_dollar)
FROM   CLIENT, TEMPS, VENTES
WHERE  CLIENT.Cid = VENTES.Cid
AND    TEMPS.Tid = VENTES.Tid
AND    TEMPS.Mois = 'Mars'
AND    CLIENT.Etat = 'IL'
GROUP BY PID
```

La Figure 3.6 donne l'arbre algébrique de chaque requête. Pour atteindre un bon temps de réponse, nous pouvons matérialiser quelques noeuds intermédiaires de chaque arbre. Notons que le résultat intermédiaire $V_1$ de la requête $Q$ est équivalent à celui de la requête $Q'$. Ce noeud est appelé sous-expression commune [Sel88]. Étant donné que $V_1$ est partagé par les deux requêtes, il sera un bon candidat pour la matérialisation. S'il est matérialisé dans les deux plans d'exécution indépendemment (cas 1), le coût des deux requêtes sera inférieur à celui obtenu par l'accès aux tables
<figure><img src="image_31.png" /><figcaption>FIG. 3.6: Les arbres algébriques individuels</figcaption></figure>
de base seulement (cas 0).

Maintenant supposons que les deux plans correspondants à $Q$ et $Q'$ soient fusionnés en utilisant la sous-expression commune $V_1$ en un seul graphe appelé **plan multiple d'exécution des vues (PMEV)** (Figure 3.6). Si le noeud $V_1$ est matérialisé (cas 2), nous pouvons conclure que:

1. Le coût d'exécution des requêtes $Q$ et $Q'$ dans le cas 2 est inférieur à celui des cas 0 et 1,

2. Lorsque les deux plans sont fusionnés, le coût de maintenance de la vue $V_1$ est inférieur à celui de la somme des vues non fusionnées.

L'idée principale sur laquelle repose l'algorithme *sélect_vue* est la fusion des sous-expressions communes trouvées dans les graphes de requêtes. Cette idée se situe dans la lignée des travaux réalisés sur l'optimisation des requêtes dans les bases de données relationnelles traditionnelles en utilisant des techniques de traitement de requêtes multiples (multiple query processing) [Sel88].

### 3.3.3 Les étapes principales de sélect_vue

Yang et al. [YKL97] ont formulé le PSV comme suit:

- Soit un entrepôt de données modélisé par un schéma relationnel ayant *d* tables de dimensions et une table des faits,

- Soit $Q = \{Q_1, Q_2, ..., Q_n\}$ un ensemble de requêtes d'interrogation (les plus fréquentes) avec leur fréquence d'accès $\{f_1, f_2, ..., f_n\}$,

- Soit $U = \{U_1, U_2, ..., U_{n'}\}$ un ensemble de requêtes de mise à jour (les plus fréquentes) avec leur fréquence d'accès $\{g_1, g_2, ..., g_{n'}\}$.

Le PSV consiste à sélectionner un ensemble de vues minimisant la somme des coûts d'évaluation de requêtes et de maintenance des vues sélectionnées.

L'algorithme *sélect_vue* se caractérise par quatre étapes, à savoir, (1) la construction de l'arbre algébrique de chaque requête, (2) la génération de PMEV, (3) l'attribution des coûts à chaque noeud de graphe, et (4) la sélection des vues.

1. **La construction des arbres algébriques:** Cette étape consiste à construire un arbre algébrique pour chaque requête $Q_i$ ($1 \le i \le n$). Notons qu'une requête $Q_i$ peut avoir plusieurs arbres algébriques. Parmi ces arbres, il en existe un qui est *optimal* (cette optimalité est évaluée en fonction d'un modèle de coût). L'existence de plusieurs arbres algébriques est due à la présence de propriétés sur des opérations algébriques [Ull89] (appelées **règles de transformation des arbres** [Gar83]). Ces règles sont au nombre de huit: (1) la commutativité des jointures, (2) l'associativité des jointures, (3) le groupement des restrictions, (4) la commutativité des restrictions et des projections, (5) la commutativité des restrictions et des jointures, (6) la commutativité des restrictions et des unions, ou des restrictions et des différences, (7) la commutativité des projections et des jointures, et (8) la commutativité des projections et des unions.

Ces règles peuvent servir dans plusieurs cas de figure:

(a) Démontrer qu'une expression algébrique est équivalente à une autre

(b) Réécrire une expression sous une autre forme
<table><caption>FIG. 3.7: L'ensemble des requêtes utilisées dans l'évaluation de la fragmentation</caption><thead><tr><th>ID</th><th>Formulation en SQL</th><th>Sélectivité</th><th>Freq</th></tr></thead><tbody><tr><td>1</td><td>SELECT sum(V.Ventes_Dollars) FROM CLIENT C, VENTES V WHERE C.Etat = "IL" AND C.CID = V.CID GROUP BY CID</td><td>1/50</td><td>15</td></tr><tr><td>2</td><td>SELECT sum(V.Ventes_Dollars), sum(S.Coût Unitaire) FROM PRODUIT, VENTES V, TEMPS T WHERE V.PID = P.PID AND V.TID = T.TID AND P.Type paquet = "Boîte" AND T.Mois = "Mars" GROUP BY PID</td><td>1/25<br>1/36</td><td>5</td></tr><tr><td>3</td><td>SELECT sum(V.Ventes_Dollars), sum(S.Coût Unitaire) FROM VENTES V, PRODUIT P, CLIENT C, TEMPS T WHERE V.PID = P.PID AND V.CID = C.CID AND V.TID = T.TID AND P.Type paquet = "Boîte" AND T.Mois = "Mars" AND C.Sexe = 'M' GROUP BY TID</td><td>1/25<br>1/36<br>1/2</td><td>5</td></tr><tr><td>4</td><td>SELECT sum(V.Vente_Dollars) FROM VENTES V, CLIENT C, TEMPS T WHERE V.TID = T.TID AND V.CID = C.CID AND C.Etat = "IL" AND T.Mois = "Mars" GROUP BY CID</td><td>1/50<br>1/36</td><td>10</td></tr><tr><td>5</td><td>SELECT sum(S.Vente_Dollars) FROM VENTES V, CLIENT C, PRODUIT P WHERE V.PID = P.PID AND V.CID = C.CID AND C.Sexe = 'M' AND P.Type paquet = "Boîte" GROUP BY PID</td><td>1/25</td><td>15</td></tr></tbody></table>