(c) Générer toutes les expressions équivalentes à une autre.

Appliquées aux arbres algébriques, ces règles vont permettre leur restructuration, afin d'obtenir un plan d'exécution optimal pour chaque requête.

2. **La génération du PMEV:** Une fois les graphes optimaux obtenus, les sous-expressions communes sont identifiées, puis les graphes de requêtes ayant des sous-expressions communes sont fusionnés en PMEV <fnref n="3" />.

Un PMEV est un graphe orienté, acyclique et étiqueté, dont la structure est définie par: (N, A), où N et A représentent les ensembles de noeuds et d'arcs du graphe dont les constructions se réalisent de la façon suivante:

- Pour chaque opération dans l'arbre algébrique de la requête $Q_i$ ($1 \le i \le n$) créer un noeud.

- $\forall v \in N, T(v)$ est la table générée par le noeud $v$. $T(v)$ pourra être une table de base, un résultat intermédiaire en exécutant une requête, ou le résultat final d'une requête.

- Pour tout noeud feuille $v$, $T(v)$ correspond à la table de base. Soit $L$ l'ensemble de feuilles.

- Pour tout noeud racine $v$ (le noeud qui n'a pas d'arc sortant du noeud), $T(v)$ correspond au résultat de la requête globale. Soit $R$ l'ensemble des noeuds racine.

- Si la table de base ou le résultat intermédiaire $T(v)$ correspondant à un noeud $v$ est demandé pour un autre traitement au niveau d'un noeud $v'$, introduire un arc $v \rightarrow v'$

- Pour tout noeud $v$, soit $S(v)$ l'ensemble des noeuds origines des arcs pointant vers $v$. Si $v \in L$; $S(v) = \emptyset$. Soit $S^*v$ l'ensemble des descendants de $v$.

- Pour $v \in N$, $C_{Q_i}(v)$ est le coût d'exécution de la requête $Q_i$ accédant à $T(v)$, lorsque $T(v)$ est matérialisée, $C_{U_j}(v)$ est le coût de maintenance de $T(v)$ causé par la requête de mise à jour $U_j$ et basé sur les changements des tables de bases $S^*(v) \cap L$.

En fonction des types d'opérations relationnelles (sélection, projection, et opérations ensemblistes), le PMEV peut être divisé en quatre niveaux:

(a) **Le niveau 0** représente seulement les relations de base (feuilles).

(b) **Le niveau 1** contient des noeuds représentant les résultats des opérations de sélection et projection. Nous appelons les noeuds de ce niveau *noeuds de SP* (sélection et projection).

(c) **Le niveau 2** contient les résultats intermédiaires des requêtes résultantes des opérations ensemblistes (comme la jointure, union, etc.). Nous appelons ces noeuds les *noeuds ensemblistes*.

(d) **Le niveau 3** représente les résultats des requêtes.

**Définition 16 Une vue de sélection** est définie par l'expression algébrique suivante: $\sigma_{cl(Y)}(T)$, où la condition de sélection $cl(Y)$ est une expression boo-léenne définie sur $Y \subseteq T$, et $T$ étant une table.

<footnote n="3">³Le PMEV final n'est pas forcément optimal [YKL97]</footnote>
**Définition 17 Une vue de projection** est définie par l'expression algébrique suivante: $\Pi_X(T)$, où $Y \subseteq T$.

**Définition 18 Une vue de jointure** est définie par l'expression algébrique suivante: $T_1 \times T_2 \times \dots \times T_p$, où les tables $T_i$ ($1 \le i \le p$) sont définies sur le schéma de l'entrepôt.

**Exemple 9** Considérons le schéma en étoile de la Figure 2.5 et les cinq requêtes décisionnelles dans la Figure 3.7. Ces dernières sont représentées par cinq arbres algébriques qui seront fusionnés en PMEV (voir Figure 3.8).

Yang et al. [YKL97] ont montré que les noeuds de niveaux 1 et 2 représentent des vues potentielles. La couche couvrant ces deux niveaux est appelée **couche des vues potentielles**.

3. **Attribution des coûts:** Avant de définir ces coûts, quelques notations sont introduites:

- $O_v$ dénote l'ensemble des requêtes utilisant le noeud $v$; $O_v = R \cap D^*(v)$; avec $R$ représentant l'ensemble des noeuds racines et $D^*(v)$ l'ensemble des ascendants de $v$

- $I_v$ est l'ensemble des tables de base utilisées pour produire $v$, $I_v = L \cap S^*(v)$; où $L$ est l'ensemble de feuilles et $S^*(v)$ est l'ensemble des descendants de $v$.

- $\mathcal{V}$ est l'ensemble de vues matérialisées.

- A chaque noeud est associé un poids statique $w(v)$ représentant le bénéfice si le noeud $v$ est matérialisé. Ce poids est donné par la formule suivante:

$$w(v) = \sum_{Q_i \in O_v} \left( f_i \times C_{Q_i}(v) \right) - \sum_{j \in I_v} \left( g_j \times C_{I_v}(v) \right) \quad (3.2)$$

Ce poids est utilisé pour ordonner les noeuds du PMEV, le noeud ayant la plus grande valeur sera privilégié pour la matérialisation.

- $O'_v$ dénote les requêtes globales qui utilisent $v$, excluant celles qui peuvent utiliser les ascendants de $v$ déjà sélectionnés. $O'_v = O_v - O_u$, avec $u \in \mathcal{V} \cap D^*(v)$

- $C_s$ dénote le poids dynamique d'un noeud donné par:

$$C_s = \sum_{Q_i \in O'_v} \left( f_i \times (C_{Q_i}(v) - \sum_{u \in S_v \cap \mathcal{V}} C_{Q_i}(v)) \right) - \sum_{r \in I_v} \left( g_r \times C_{I_v}(v) \right). \quad (3.3)$$

La première partie de la formule 3.3 représente le bénéfice si $v$ est matérialisée. La deuxième est le coût de maintenance de la vue $v$.

$\sum_{u \in S_v \cap \mathcal{V}} C_{Q_i}(v)$ est un facteur dupliqué dans le cas où quelques descendants de $v$ sont déjà choisis pour la matérialisation.

4. **la sélection des vues:** Cette étape consiste à ordonner les noeuds du PMEV en fonction de leur poids statique $w(v)$; ensuite on calcule leur poids dynamique. Si $C_s > 0$, $v$ est matérialisée (voir l'algorithme 4).
<figure><img src="image_32.png" /><figcaption>FIG. 3.8: Le PMEV correspondant aux cinq requêtes de la Figure 3.7</figcaption></figure>

**Algorithmme 4** Les étapes de sélect_vue

1: $V := \emptyset$

2: Créer la liste *LV* de tous les noeuds ayant des poids positifs (dans l'ordre descendant)

3: Prendre le premier élément *v* de *LV*

4: Calculer $O_v$, $I_v$, et $C_v$

5: Calculer $C_s$

6: **if** $C_s > 0$ **then**

7: Insérer *v* dans *M*

8: Retirer *v* de *LV*

9: **else**

10: Retirer *v* et tous les noeuds listés après *v* dans *LV* et qui sont dans la même branche de *v*

11: **end if**

12: **repeat**

13: Étape 3

14: **until** *LV* = [] % []: la liste vide

15: ∀v ∈ V, si $D(v) \subset M$, alors retirer v de V
## 3.4 Le processus de réécriture des requêtes

Pour que les requêtes retirent un bénéfice des vues matérialisées, elles doivent être réécrites en fonction de ces dernières.

**Définition 19 La réécriture d'une requête [SDJL96]** Soient $Q$ et $V$ une requête et une vue matérialisée, respectivement. Supposons que la requête $Q$ utilise la vue $V$. Une requête $Q'$ est une réécriture de la requête $Q$ si les deux conditions suivantes sont satisfaites:

- (i) $Q$ et $Q'$ donnent la même réponse, et

- (ii) $Q'$ contient une ou plusieurs occurrences de $V$ dans la clause FROM.

La réécriture des requêtes ne garantit pas toujours une meilleure performance. Le processus d'exécution des requêtes en présence des vues matérialisées se fait de la manière suivante:

Soit un entrepôt de données modélisé par un schéma ayant $k$ tables. Supposons que nous ayons un ensemble de vues matérialisées $V = \{V_1, V_2, ..., V_k\}$. Lorsqu'une requête $Q$ est posée sur l'entrepôt, l'optimiseur des requêtes élabore les trois processus suivants (voir Figure 3.9): (1) la **réécriture**, (2) la **génération des plans d'exécution de la requête** $Q$, et (3) la **sélection du meilleur plan de Q** [BDD$^{+98}$].

**Le processus de réécriture:** Lorsqu'une requête est posée sur l'entrepôt, l'optimiseur doit trouver une réponse à la question suivante: **existe t-il une réécriture de la requête Q?**

Trois réponses sont possibles:

- **Pas de réécriture:** Cela signifie qu'il n'existe aucune possibilité de réécriture de la requête $Q$ en fonction des vues sélectionnées. Pour exécuter $Q$, l'optimiseur est donc obligé d'accéder aux tables de base.

- **Une réécriture presque parfaite:** Dans ce cas, l'optimiseur trouve une réécriture $Q'$ de $Q$ dans laquelle, $Q'$ utilise des vues et des tables de base.

- **Une réécriture parfaite:** Comme dans le cas précédent, l'optimiseur trouve une réécriture $Q'$ de $Q$. Pour exécuter $Q$, l'optimiseur utilise uniquement des vues matérialisées.

**La génération des plans :** L'optimiseur génère deux plans d'exécution pour la requête $Q$: dans le premier, la requête $Q$ est exécutée sans utilisation des vues (voir Figure 3.9), et dans le deuxième, la requête $Q'$ est exécutée$^4$.

**La sélection du meilleur plan:** L'optimiseur dispose d'un modèle de coût calculant le coût de chaque plan. Le coût est calculé en fonction des statistiques sur les tables de base et les vues (e.g., leurs tailles). Finalement, l'optimiseur sélectionne le plan ayant un coût minimal. Si le plan sélectionné est celui de $Q'$, la requête $Q$ est considérée comme une requête bénéficiaire.

**Exemple 10** Soient $V_1$ et $V_2$ deux vues sélectionnées par l'algorithme `sélect_vue` dont les définitions sont:

<footnote>$^4$Nous supposons qu'il existe une réécriture de la requête $Q$</footnote>
<figure><img src="image_33.png" /><figcaption>FIG. 3.9: Le processus de réécriture</figcaption></figure>

```sql
CREATE VIEW V_1
SELECT *
FROM CLIENT, VENTES
WHERE CLIENT.Cid = VENTES.Cid
AND CLIENT.Etat = 'Illinois'

CREATE VIEW V_2
SELECT *
FROM PRODUIT, VENTES
WHERE PRODUIT.Pid = VENTES.Cid
AND PRODUIT.typePAQUET = 'Boîte'
```

Les cinq requêtes de la Figure 3.7 sont réécrites en fonction de $V_1$ et $V_2$ et d'autres tables. Cette réécriture peut être réalisée en utilisant une structure de données appelée **matrice de réécriture** ($W = w_{ij}$). Les lignes et les colonnes de W représentent les requêtes et les vues (et tables), respectivement. Ses valeurs $w_{ij}$ sont définies comme suit:

$$ w_{ij} = \begin{cases} 1 & \text{si la requête } Q_i \text{ utilise la vue (table) } j \\ 0 & \text{sinon} \end{cases} $$

Pour exécuter les cinq requêtes, l'optimiseur utilise les deux vues $V_1$, $V_2$ et deux tables de dimensions CLIENT et TEMPS (voir la Figure 3.10). À partir de cet exemple, nous constatons qu'il existe une réécriture parfaite pour la requête $Q_1$ (qui utilise seulement la vue $V_1$) et des réécritures presque parfaites pour les autres ($Q_2$, $Q_3$, $Q_4$ et $Q_5$).

<figure><img src="image_34.png" /><figcaption>FIG. 3.10: La matrice de réécriture</figcaption></figure>
## 3.5 Le problème des jointures et les index de jointure

Après la réécriture des requêtes en fonction des vues, dans la plupart des cas, l'opération de jointure est toujours présente. Rappelons que cette dernière est une des opérations les plus coûteuses dans les bases de données [LR98]. Deux méthodes principales existent pour évaluer une opération de jointure:

1. L'utilisation des techniques ad-hoc (e.g., la jointure par hachage, la jointure par tri-fusion, la jointure imbriquée, etc.). Il faut noter que ces techniques sont efficaces lorsque le nombre de tables à joindre est égal à 2. Si ce dernier est supérieur à 2, avant de les utiliser, il faut régler le problème d'ordonnancement des jointures (voir chapitre 2).

2. L'utilisation des index de jointure. Il s'agit de structures précalculées qui garentissent généralement une meilleure performance que les techniques ad-hoc [BS95, Val87, LR98]. L'utilisation des index dans les bases de données doit être utilisée soigneusement, car elle pose le problème de leur maintenance. Mais dans les entrepôts de données ce dernier est moins important que dans les bases de données de type OLTP (voir chapitre 2).

Notons que des index de jointure ont été proposés dans les bases de données de type OLTP pour des jointures entre deux tables [Val87]. Dans les entrepôts de données, l'existence de jointures entre *n* tables (*n* > 2) est fréquente. Prenons l'exemple d'un entrepôt modélisé par un schéma en étoile. La principale caractéristique des requêtes en étoile définies sur ce schéma est leurs multiples (> 2) jointures [Sys97]. Ces dernières doivent être optimisées afin de respecter les délais imposés par les décideurs. Les chercheurs ont d'abord essayé de voir si les méthodes de jointure développées dans les bases de données traditionnelles pouvaient être appliquées. Le résultat n'était pas significatif à cause du problème d'ordonnancement des jointures.

Pour résoudre ce problème, Red Brick [Sys97] a développé un nouvel index de jointure appelé **index de jointure en étoile**.

**Définition 20** Un index de jointure en étoile (IJE) est le résultat de l'opération de jointure des tables de dimensions avec la table des faits en utilisant les clés primaires des tables de dimensions et les clés étrangères de la table des faits.

**Exemple 11** Un IJE complet<fnref n="5" /> sur le schéma en étoile de la Figure 2.5 peut être défini de la manière suivante: (VID, CID, PID, TID), où VID, CID, PIDetTID représentent les identifiants de la table des faits et des trois tables de dimensions, respectivement. Cet index est le résultat de la requête suivante [Cor97b]:

```sql
SELECT CID, PID, VID, TID
FROM   CLIENT, PRODUIT, VENTES, TEMPS
WHERE  CLIENT.CID = VENTES.CID
AND    PRODUIT.PID = VENTES.PID
AND    TEMPS.TID = VENTES.SID
```

<footnote n="5">⁵Un IJE complet est un IJE possédant toutes les tables de dimensions et la table des faits dans sa définition (voir chapitre 2)</footnote>
<figure><img src="image_35.png" /><figcaption>FIG. 3.11: Exemple de graphe d'une base de données</figcaption></figure>

D'une manière similaire, un IJE partiel (VID, CID) 6 peut être défini entre la table des faits VENTES et la table de dimension CLIENT. Il est le résultat de la requête ci-dessous:

```sql
SELECT CID, VID
FROM CLIENT, VENTES
WHERE CLIENT.CID = VENTES.CID
```

Il faut noter que l'avantage principal de cet index est qu'il peut optimiser n'importe quelle opération de jointure définie sur un schéma en étoile (voir les avantages et les inconvénients de ces index dans le chapitre 2).

En conséquence, la présence des vues matérialisées rend ces index de jointure inefficaces. Pour exécuter une requête ayant plusieurs jointures de vues, nous devons avoir des techniques d'indexation offrant une meilleure performance que les techniques développées pour les systèmes OLTP. Ces techniques feront l'objet de ce chapitre.

Avant de décrire ces techniques d'indexation, quelques concepts et définitions sont nécessaires.

**Définition 21** Un **graphe d'une base de données** [MW89] est un graphe connecté où chaque noeud représente une table et où une arête entre deux noeuds $T_i$ et $T_j$ représente une possibilité de jointure entre ces deux noeuds.

Pour un graphe d'une base de données donné, nous pouvons avoir plus d'une arête entre deux noeuds comme le montre la Figure 3.11, où nous avons le cas de deux jointures entre les tables *Employé* et *Département* à représenter. En effet, une jointure relie un employé au département où il travaille, et l'autre relie l'employé au département où il/elle est gérant.

Dans l'environnement des entrepôts de type ROLAP (c'est-à-dire, les entrepôts modélisés par un schéma en étoile ou un schéma en flocon de neige), un graphe d'une base de données possède une et une seule arête entre deux noeuds. Dans ce cas, il est appelé un **graphe d'entrepôt de données**.

**Définition 22** Un **graphe de jointure** est un graphe d'une base de données tel qu'il existe exactement une condition de jointure entre deux tables. Le nombre de noeuds d'un graphe de jointure est appelé la cardinalité de ce graphe.

Dans les entrepôts de données sans vues matérialisées, le graphe de jointure et le graphe d'entrepôt de données sont équivalents (c'est-à-dire, un graphe de jointure est un graphe d'entrepôt de données et vice versa).

<footnote>6Un IJE partiel est un IJE possédant certaines tables de dimensions et la table des faits dans sa définition (voir chapitre 2)</footnote>
La présence des vues matérialisées change la structure du graphe d'entrepôt de données, car les vues peuvent remplacer les tables de dimensions et la table des faits. Par conséquent, le graphe de jointure correspondant au graphe d'entrepôt de données peut être non connecté, dans le sens où il peut contenir plus d'un sous-graphe. Dans ce cas, il est appelé **graphe de jointure partitionné**. Cette situation est attestée dans les cas suivants:

1. Les vues n'ont pas d'attribut de jointure commun. Par exemple, une vue est définie sur la table de dimensions CLIENT et l'autre sur la table de dimension PRODUIT.

2. Les vues ont des attributs de jointure communs mais ne peuvent jamais être jointes. Supposons par exemple que nous ayons deux vues matérialisées $V_1$ et $V_2$ définissant les montants de ventes pour les clients féminins et pour les clients masculins, respectivement. Dans cette situation, le résultat de la jointure entre $V_1$ et $V_2$ est vide.

**Définition 23 Index de graphe de jointure (IGJ)** Soit un **graphe de jointure** de cardinalité *m* (*m* ≥ 2). Un IGJ est un sous ensemble de *h* (*h* ≤ *m*) noeuds de **graphe de jointure**.

Dans le cas d'un **graphe de jointure partitionné**, l'IGJ peut être défini sur chaque sous-graphe du **graphe de jointure**.

D'après ces définitions, nous pouvons conclure qu'un index de jointure en étoile est un cas particulier d'IGJ (quand les vues ne sont pas considérées).

Dans cette étude, nous utilisons un schéma en étoile ayant un ensemble de tables de dimensions, et une table des faits. Sur ce dernier, un ensemble de vues matérialisées est sélectionné. Chaque table $T_i$ (qui peut être une table de dimensions, la table des faits ou une vue) a une clé dénotée par $K_{T_i}$. Un IGJ $G$ sur *m* tables peut être représenté par une table ayant *m* attributs ($K_{T_1}$, $K_{T_2}$, ..., $K_{T_m}$). Cet index est dénoté par:

$$G : (T_1 \sim T_2 \sim \dots \sim T_m)$$

**Définition 24 Un IGJ simple** est un IGJ défini sur deux tables seulement.

**Définition 25 Un IGJ complet** est un IGJ couvrant tous les noeuds du **graphe de jointure**.

**Définition 26 Un IGJ partiel** est un IGJ couvrant certains noeuds du **graphe de jointure**.

**Exemple 12** Reprenons l'exemple 10 dans lequel deux vues matérialisées $V_1$ et $V_2$ sont sélectionnées. À partir de la matrice de réécriture de la Figure 3.10, le **graphe de jointure** peut être construit. Il contient 4 noeuds représentant $V_1$, $V_2$, CLIENT et TEMPS et 5 arêtes (voir Figure 3.12). Notons qu'il n'existe pas une arête entre CLIENT et TEMPS car ces derniers ne peuvent pas être joints. Le seul IGJ complet correspondant à ce GJ est ($V_1 \sim V_2 \sim CLIENT \sim TEMPS$). Plusieurs IGJs simples peuvent être identifiés, par exemple l'IGJ ($V_1 \sim V_2$).

Considérons l'IGJ ($CLIENT \sim TEMPS$). Nous remarquons qu'il n'existe pas d'arête entre CLIENT et TEMPS dans le GJ, mais deux chemins $CLIENT - V_1 - TEMPS$, et $CLIENT - V_2 - TEMPS$. Ces derniers donnent deux IGJs, le premier référence tous les n-uplets de CLIENT qui peuvent être joints avec TEMPS
<figure><img src="image_36.png" /><figcaption>FIG. 3.12: Graph de jointure</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>FIG. 3.13: La stratégie d'exécution d'une jointure en présence d'un IJE</figcaption></figure>

en se basant sur les n-uplets communs de la vue $V_1$, et l'autre représente tous les n-uplets de CLIENT qui peuvent être joints avec TEMPS en se basant sur les n-uplets communs de la vue $V_2$. Un IGJ est utilisé en fonction des requêtes. Il est donc important de considérer la sémantique des requêtes dans la sélection des index.

## 3.6 Une stratégie d'exécution de requêtes

Dans cette section, une stratégie d'exécution des requêtes en présence des IGJs est décrite. Pour rendre cette présentation compréhensible, considérons un schéma en étoile *SED* de *d* tables de dimensions {$D_1, D_2, ..., D_d$} et une table des faits *F*. Supposons que toutes ces tables sont stockées en mémoire secondaire.

Soit $Q_i$ une requête dont la syntaxe est similaire à celle décrite en section 3.3. Cette requête est représentée par un arbre algébrique $G_{Q_i}$ dont l'ensemble des noeuds est dénoté par $N_{Q_i}$ (la cardinalité de $N_{Q_i}$ est dénotée par $t$). Soit *g* un IGJ pour supporter l'exécution de la requête $Q_i$. Soit *Table*(*g*) l'ensemble des tables sur lesquelles, *g* est défini.

La Figure 3.13 présente la stratégie d'exécution de $Q_i$ en utilisant l'IGJ *g*. Ce dernier a une position centrale. Le parcours des tables se fait de la manière suivante:
tables de dimensions, IGJ et enfin table des faits (tables de dimensions $\rightarrow$ IGJ $\rightarrow$ table des faits). Cette stratégie suit exactement le principe des requêtes de jointure en étoile (la sélection d'abord et ensuite la jointure).

Pour accéder aux n-uplets de l'IGJ à partir d'une table de dimensions, nous disposons d'un arbre $B^+$. Nous disposons également d'un arbre $B^+$ pour accéder aux n-uplets de la table des faits à partir de n-uplets de l'IGJ (voir Figure 3.13).

En fonction de la définition de $Q_i$, quatre scénarios d'exécution de la requête $Q_i$ sont possibles:

1. **Pas de jointure:** La présence de l'IGJ $g$ n'a pas d'influence.

Pour exécuter $Q_i$, des techniques d'indexation simples (comme l'index de projection, l'index binaire, etc.) peuvent être utilisées.

2. **Non Correspondance (non matching):** La requête $Q_i$ possède une opération de jointure, mais l'IGJ $g$ ne couvre aucune table de l'arbre de $Q_i$ (c'est-à-dire: $N_{Q_i} \cap \text{Table}(g) = \emptyset$ et $t \ge 2$).

Pour exécuter la requête $Q_i$, les techniques ad-hoc de jointure peuvent être utilisées (voir section 3.5).

3. **Correspondance totale (total matching):** L'IGJ couvre toutes les tables de $G_{Q_i}$ (c'est-à-dire: $N_{Q_i} \subseteq \text{Table}(g)$).

Pour exécuter la requête $Q_i$, nous effectuons les étapes suivantes:

- Charger toutes les tables de dimensions utilisées par la requête $Q_i$.

- Charger l'arbre $B^+$ correspondant à la table de dimension $D_{min}$ (celle qui a le facteur de sélectivité minimale). Une fois cet arbre chargé, les n-uplets de $D_{min}$ sont utilisés pour charger l'IGJ vers la mémoire centrale. Cette opération permet de charger seulement une partie de l'index et non sa totalité (Figure 3.13).

- Exécuter toutes les opérations de sélection définies sur les tables de $N_{Q_i}$ (si elles existent bien sûr). Pour chaque table de $N_{Q_i}$ ($1 \le i \le t$), nous considérons l'ensemble des clés primaires de ses n-uplets sélectionnés. Ces derniers peuvent être utilisés pour accéder à l'IGJ <fnref n="7" />. En calculant l'intersection de ces ensembles, nous obtenons les n-uplets satisfaisant l'opération de jointure.

- Charger l'arbre $B^+$ afin d'accéder aux n-uplets de la table des faits (voir Figure 3.13).

- Charger les n-uplets pertinents de la table des faits.

4. **Correspondance partielle (partial matching):** l'IGJ $g$ ne couvre que certaines tables de $G_{Q_i}$ (la table des faits incluse) (c'est-à-dire $\text{Table}(g) \cap N_{Q_i} \neq \emptyset$). Par exemple, l'IGJ ($VENTES \sim TEMPS$) couvre partiellement la requête $Q_3$ (Figure 3.7).

Pour exécuter la requête $Q_i$, l'IGJ est utilisé pour traiter les jointures définies sur les tables qu'il couvre (comme dans le total matching). Les résultats de ces jointures sont combinés avec les tables non couvertes pas l'IGJ en utilisant les techniques de jointure classiques (comme dans le cas de non matching).

<footnote n="7">⁷Chaque clé primaire identifie un ensemble de n-uplets de l'IGJ</footnote>
## 3.7 Un modèle de coût

Dans cette section, un modèle de coût est présenté. Son rôle est d'estimer le coût des requêtes en présence des IGJs. Il peut également être utilisé pour calculer le coût de chaque noeud (vue) de jointure du PMEV (voir section 3.3).

### 3.7.1 Les composantes d'un modèle de coût

Le coût total pour évaluer une requête dans un SGBD se décompose en trois coûts principaux [LDH+84, OV91]: (1) *le coût des entrées-sorties (IO)* pour lire et écrire entre la mémoire et le disque, (2) *le coût CPU* et (3) *le coût COM de communication sur le réseau* (si les données sont réparties sur le réseau). Ce dernier est généralement exprimé en fonction de la quantité totale des données transmises [Ape88, BKL98a]. Il dépend de la topologie du réseau.

Les modèles de coût utilisés par les optimiseurs ont généralement les mêmes composantes [Gru96, Naa99]: (1) *des statistiques des données stockées dans une métabase*, et (2) *des formules* pour évaluer la cardinalité des résultats intermédiaires et des requêtes. Le modèle de coût a comme entrée un plan d'exécution d'une requête et comme sortie le coût de ce plan. Le coût d'un plan d'exécution est évalué en cumulant le coût des opérations élémentaires (la sélection, la projection, la jointure, etc.). Une fonction de coût est associée à chaque opérateur élémentaire. Pour établir avec précision une fonction de coût nous devons connaître à l'avance les nombreux paramètres dont dépend l'opérateur ainsi que le détail de l'algorithme qui l'implémente.

**Exemple 13** Supposons que nous voulions évaluer le coût d'une requête ayant une opération de jointure entre deux tables *R* et *S*. Les paramètres dont l'opérateur de jointure dépend sont: la taille des deux tables, le nombre de pages occupées par ces deux tables, la sélectivité des prédicats de jointure, les méthodes d'accès déterminant la nature de l'algorithme de jointure utilisée [Ram98] (jointure avec boucles imbriquées, jointure en utilisant un index, jointure par fusion, etc.). La prise en compte de ces paramètres rend l'estimation de l'opération de jointure entre *R* et *S* plus facile.

### 3.7.2 Les statistiques et les estimations

#### 3.7.2.1 Les statistiques de base

L'optimiseur des requêtes se base sur les statistiques sur les données stockées pour générer les plans d'exécution des requêtes. La disponibilité de statistiques pertinentes peut largement améliorer la qualité des plans choisis par l'optimiseur [CN00]. Par contre, l'absence de statistiques peut donner de mauvais plans d'exécution. Le Groupe DMX (Data Management Exploration) de Microsoft Research a proposé des techniques d'automatisation des statistiques [CN00]. Ces dernières sont disponibles dans le catalogue du système [Cha82, YC84]. Ces statistiques peuvent être divisées en trois catégories:

- Les statistiques décrivant les tables et les distributions des valeurs d'attribut: le nombre n-uplets et leur taille moyenne pour chaque table, le nombre de valeurs distinctes pour chacun des attributs (qui permet de calculer la sélectivité
des opérations de sélection contenant des prédicats d'égalité), les valeurs minimales et maximales des attributs de sélection (pour calculer la sélectivité des prédicats de comparaison). La représentation la plus simple est celle qui suppose l'uniformité de la distribution des valeurs et l'indépendance des attributs [SAD+79, GGT96]. Ces paramètres sont pris en compte par les systèmes commerciaux [CN00].

- Les statistiques décrivant les paramètres de la machine utilisée: taille des pages disque et mémoire, taille mémoire, coût moyen d'une entrée-sortie, etc.

- Les statistiques des méthodes d'accès: les index sont des structures persistantes, il faut donc estimer leurs tailles, le nombre de pages occupées par ces index, etc.

### 3.7.2.2 Estimation de la sélectivité des prédicats

La sélectivité des prédicats (de sélection et de jointure) est un paramètre primordial pour estimer le coût des requêtes [IC91].

**Définition 27** La sélectivité est un coefficient représentant le nombre d'objets sélectionnés rapporté à un nombre d'objets total d'une table. Si la sélectivité vaut 1, tous les objets sont sélectionnés. Si elle vaut 0, aucun objet n'est sélectionné.

Nombre de travaux ont été développés pour estimer la sélectivité [IC91]. La plupart d'entre eux supposent une distribution uniforme des valeurs des attributs et une indépendance entre les attributs de chaque relation. Cette estimation se fait de la manière suivante:

Soient $A_i$ et $A_j$ deux attributs d'une relation $R$, les formules de sélectivité sont les suivantes:

$$Sel(A_i = valeur) = \frac{1}{card(\pi_{A_i}(R))}$$

$$Sel(A_i > valeur) = \frac{max(A_i)-valeur}{max(A_i)-min(A_i)}$$

$$Sel(A_i < valeur) = \frac{valeur-max(A_i)}{max(A_i)-min(A_i)}$$

$$Sel(p(A_i) \land p(A_j)) = Sel(p(A_i)) * Sel(p(A_j))$$

$$Sel(p(A_i) \lor p(A_j)) = Sel(p(A_i)) + Sel(p(A_j)) - (Sel(p(A_i)) * Sel(p(A_j))$$

$$Sel(A_i \in \{valeurs\}) = Sel(A_i = valeur) * card(\{valeur\})$$

La taille d'une opération de jointure entre deux tables $T_1$ et $T_2$ est estimée en utilisant la formule suivante [Ull89]:

$$||T_1 \bowtie_A T_2|| = \frac{||T_1|| \times ||T_2||}{max.card(\pi_A T_1), card(\pi_A T_2)}$$

Toutefois, certains travaux ne supposent aucune distribution particulière [Naa99]. Dans ce cas, une approche à base d'histogrammes est proposée dans [Ioa93].
### 3.7.2.3 Estimation de la sélectivité des prédicats complexes

Les prédicats complexes sont composés de prédicats conjonctifs (ET) et disjonctifs (OU). Grâce à la forme normale, la sélectivité des prédicats est calculée de proche en proche. La formule générale pour la conjonction est la suivante:

$$Sel(pred_1 \ AND \ pred_2) = Sel(pred_1) * Sel(pred_2|pred_1)$$
$pred_2|pred_1$ veut dire $pred_2$ sachant $pred_1$. Si les deux prédicats sont indépendants on aura $Sel(pred_2|pred_1) = Sel(pred_2)$. C'est toujours l'hypothèse envisagée [Gru96]. En effet aucun système n'est réellement capable de tenir compte de la corrélation entre les prédicats.

Pour les disjonctions, la formule générale est la suivante:

$$Sel(pred_1 \ OU \ pred_2) = Sel(pred_1) + Sel(pred_2) - Sel(pred_1 ET pred_2)$$
Si $pred_1$ et $pred_2$ sont mutuellement exclusifs, on a $Sel(pred_1 ET pred_2) = 0$.

Une méthode basée sur l'échantillonnage (sampling) [HS95] permet d'estimer la sélectivité des prédicats en exécutant la requête sur une portion des tables. Suivant les résultats obtenus sur ces petites portions, la sélectivité de la requête peut être estimée. Le problème dans un tel système est qu'il faut optimiser partiellement la requête pour pouvoir exécuter quelques parties. Ce système ne fonctionne que pour des requêtes simples et très coûteuses. En effet, le processus de l'échantillonnage doit être très efficace par rapport à l'exécution globale de la requête pour obtenir un gain significatif en performance.

## 3.7.3 Les méthodes d'accès

En l'absence d'index de jointure d'autres méthodes d'accès sont utilisées. Parmi ces méthodes, nous trouvons la jointure imbriquée, la jointure par tri, la jointure par hachage, etc. Dans ce chapitre nous utilisons la jointure par hachage. Ce choix s'est porté sur cette technique parce qu'elle est utilisée par plusieurs systèmes existants (e.g., Oracle, Informix). Les autres techniques peuvent également être utilisées dans cette thèse. La jointure par hachage se fait en deux phases [Ram98]. Dans la première phase, les deux relations sont partitionnées suivant la même fonction de hachage appliquée aux attributs participant à la jointure. Dans la deuxième phase, les partitions en correspondance sont jointes.

## 3.7.4 Le modèle de coût dans notre contexte

### 3.7.4.1 Les hypothèses

Nous avons maintenant tous les ingrédients pour présenter le modèle de coût pour évaluer un ensemble de requêtes décisionnelles. Nous nous sommes fixés comme objectif de donner une approximation du nombre des entrées-sorties et nous n'avons pas pris en compte le coût de CPU et le coût COM de communication sur le réseau. Ce choix se justifie dans la mesure où, dans les grandes bases de données, la contribution du coût CPU n'est pas aussi significative que le coût des entrées-sorties [FKL97, BKL98b, YKL97, Gup99]. Notons que notre modèle de coût peut facilement être étendu pour inclure les deux coûts non pris en compte. Nous considérons également que l'entrepôt est centralisé.
Soit un entrepôt de données modélisé par un schéma en étoile ayant *d* tables de dimensions et une table des faits. Sur ce schéma, un ensemble de requêtes sont définies $Q = \{Q_1, Q_2, ..., Q_s\}$. Chaque requête $Q_i$ ($1 \le i \le s$) a une fréquence d'accès $f_i$. Soient $V = \{V_1, V_2, ..., V_l\}$ et $\mathcal{IJ} = \{I_1, I_2, ..., I_m\}$ un ensemble de vues matérialisées et d'index de jointure.

Avant de décrire le modèle, deux hypothèses sont à considérer:

- Les tables de dimensions, la table des faits, les vues matérialisées, et les index sont stockés sur disque (notre modèle peut être facilement adapté lorsque les tables de dimensions, la table des faits, les vues matérialisées, ou les index sont en mémoire centrale).

- Les conditions de sélection sont toujours descendues sur l'arbre syntaxique comme dans [LQA97].

### 3.7.4.2 Les paramètres

Les paramètres de notre modèle de coût peuvent être classés en trois catégories: les paramètres relatifs à l'entrepôt (Table 3.1), les paramètres relatifs aux requêtes (Table 3.3) et les paramètres relatifs aux méthodes d'accès (les index) (Table 3.2).

<table><caption>TAB. 3.1: Les paramètres de l'entrepôt</caption><thead><tr><td>Nom de paramètre</td><td>Description</td></tr></thead><tbody><tr><td>||T<sub>j</sub>||</td><td>La cardinalité de la table T<sub>j</sub></td></tr><tr><td>|T<sub>j</sub>|</td><td>Le nombre de pages stockant la table T<sub>j</sub></td></tr><tr><td>w(c<sub>ij</sub>)</td><td>La taille, en bytes, de la colonne c<sub>i</sub> de la table T<sub>j</sub></td></tr><tr><td>w(K<sub>T<sub>j</sub></sub>)</td><td>La taille, en bytes, de la clé primaire de la table T<sub>j</sub></td></tr></tbody></table>

<table><caption>TAB. 3.2: Les paramètres des index</caption><thead><tr><td>Nom de paramètre</td><td>Description</td></tr></thead><tbody><tr><td>||G<sub>i</sub>||</td><td>La cardinalité de l'IGJ G<sub>i</sub></td></tr><tr><td>|G<sub>i</sub>|</td><td>Le nombre de pages stockant l'index G<sub>i</sub></td></tr></tbody></table>

<table><caption>TAB. 3.3: Les paramètres physiques</caption><thead><tr><td>Nom de paramètre</td><td>Description</td></tr></thead><tbody><tr><td>π</td><td>Taille de pointeur de la page</td></tr><tr><td>PS</td><td>Taille d'une page</td></tr><tr><td>M</td><td>Taille du tampon (en nombre de pages)</td></tr></tbody></table>

### 3.7.4.3 L'estimation des facteurs de base du modèle de coût

Dans les bases de données relationnelles, les tables sont stockées "as-is" [DRT99]: chaque table est représenté comme une série de n-uplets partitionnés en blocs de
données liés par des *pointeurs de bloc*. Dans cette étude, nous supposons que chaque n-uplet est assez petit pour tenir dans un bloc de données. En conséquence, le nombre de pages nécessaires pour stocker une table $T_j$ est donné par la formule suivante:

$$|T_j| = PS \times \left[ \frac{||T_j||}{\lfloor \frac{PS-\pi}{w(T_j)} \rfloor} \right] \quad (3.4)$$

où [ ] et [ ] représentent les fonctions *ceiling* et *floor*, respectivement. La même formule pourra être utilisée pour estimer le nombre de pages stockant une vue ou un IGJ, car ces derniers sont stockés sous la forme d'une table.

Le coût d'une jointure par hachage *Cost_Hash* entre deux tables $T_i$ et $T_j$ ($i \neq j$) est donné par la formule suivante [Ram98]:

$$Cost\_Hash = 3 \times (|T_i| + |T_j|) \quad (3.5)$$

### 3.7.4.4 Les formules du modèle de coût

Dans la section 3.6, nous avons vu qu'il existe quatre scénarios pour évaluer une requête $Q_i$ en présence d'un IGJ. Nous présentons maintenant, des formules pour chaque scénario:

**Non matching:** Dans ce cas, la technique de jointure par hachage est utilisée. Son coût est décrit par l'équation 3.5.

**Total matching** Le coût d'exécution de la requête $Q_i$ sous ce scénario est divisé en plusieurs coûts correspondant à chaque étape d'exécution (voir section 3.6):

1. Le coût de chargement *Load_Cost(D)* des tables de dimensions est donné par:

$$Load\_Cost(D) = \sum_{i=1}^{t} |D_i| \quad (3.6)$$

2. Le coût de sélection de la table de dimensions $D_{min}$ parmi toutes les tables de $N_{Q_i}$ est nul (car toutes les tables de dimensions sont déjà chargées en mémoire centrale).

3. Le coût de chargement de l'arbre $B^+$ est défini par la taille de cet arbre. Comme dans [GHRU97], nous considérons que la taille de l'arbre $B^+$ peut être estimée à partir de la taille de toutes les feuilles de cet arbre (le nombre de feuilles est approximativement égal au nombre de n-uplets de la table sous-jacente).

4. Le coût de chargement de l'IGJ $G_j$ est:

$$Load\_Cost(G_j) = \left| SF_{D_{min}} \times ||G_j|| \right| \quad (3.7)$$

5. Le coût de l'opération d'intersection est nul puisque les tables de dimensions et les index sont déjà chargés en mémoire centrale.

6. Le coût de chargement de l'arbre $B^+$ est identique à celui défini dans l'étape 3.
7. Le coût de chargement des n-uplets de la table des faits est:

$$Load\ Cost(F) = |SF_F \times ||F||| \qquad (3.8)$$

**Partiel matching** Le coût sous ce scénario peut être dérivé de celui de non matching et total matching.

**Le coût total d'exécution de l'ensemble de toutes les requêtes** Soit $C(Q_i)$ le coût d'exécution de la requête $Q_i$ ($1 \le i \le s$). Le coût total d'exécution de l'ensemble de toutes les requêtes ($CT$) est donné par l'équation suivante:

$$CT = \sum_{i=1}^{s} f_i \times C(Q_i) \qquad (3.9)$$

### 3.7.5 La maintenance des IGJs

Comme nous l'avons déjà vu dans le chapitre 2, lors de changements (opérations de suppression, ou d'ajout) au niveau des tables de base, les index correspondants doivent impérativement être remis à jour. Nous présentons le coût de maintenance des IGJs pour les opérations de suppression et d'ajout causées par des requêtes de mise à jour.

**Le cas de suppression** Soit $G$ un IGJ défini sur $m$ tables<fnref n="8" /> de la façon suivante: $G: (T_1 \sim T_2 \sim \dots \sim T_m)$. Supposons qu'une opération de suppression survienne sur la table $T_1$. Soit $\nabla T_1$ les n-uplets concernés par cette opération. Avant de supprimer ces n-uplets de l'index, ces derniers doivent être identifiés. L'identification de ces n-uplets est réalisée en évaluant l'opération suivante:

$$\nabla G = G \bowtie \nabla T_1 \qquad (3.10)$$

où $\bowtie$ représente l'opération de semi jointure. Une fois identifiés, ils doivent être éliminés de l'IGJ $G$.

**Le cas d'ajout** D'une manière similaire, la propagation des insertions au niveau de la table $T_1$ ($\Delta T_1$) vers l'index $G$ est égale à l'évaluation de l'opération suivante:

$$\Delta G = \Delta T_1 \bowtie T_2 \bowtie \dots \bowtie T_m \qquad (3.11)$$

Finalement, les n-uplets de $\Delta G$ sont insérés dans l'IGJ $G$.

<footnote n="8">⁸tables peuvant être tables de base ou vues</footnote>
### 3.7.6 Le coût de stockage des IGJs

La Figure 3.12 nous donne une idée claire sur les composantes d'un IGJ: (1) les arbres $B^+$ qui permettent d'accéder aux n-uplets de l'IGJ à partir de chacune des tables de dimensions, (2) l'IGJ lui-même et (3) l'arbre $B^+$ qui permet d'accéder aux n-uplets de la table des faits à partir de l'IGJ.

La taille d'un IGJ peut être estimée en utilisant les mêmes techniques d'estimation de la taille des jointures [HS95].

Le coût de stockage d'une structure d'un IGJ défini sur $m$ tables<fnref n="9" /> est la somme de la taille des arbres $B^+$ et de la taille de l'IGJ (voir Figure 3.13).

## 3.8 Les algorithmes de sélection des IGJs

### 3.8.1 La complexité de la sélection des IGJs

Notons que pour un schéma d'un entrepôt de $n$ tables, le nombre total de IGJs qui peut être généré est donné par:

$$ \binom{2^n - n - 1}{0} + \binom{2^n - n - 1}{2} + \dots + \binom{2^n - n - 1}{2^n - n - 1} = 2^{2^{(2^n - n - 1)}} $$

Si on veut sélectionner un seul IGJ, le nombre de possibilités est $2^n - n - 1$. Par exemple pour un entrepôt de 4 tables, $2^4 - 4 - 1 = 11$ IGJs peuvent être considérés, pour sélectionner le meilleur index.

Par contre, pour sélectionner plus d'un IGJ, le nombre de possibilités est $2^{(2^n - n - 1)}$. Pour $n = 5$, il est 67108864, et pour $n = 6$, il est supérieur à $10^{17}$. Sélectionner les meilleurs index pour un ensemble de requêtes reste aujourd'hui une question ouverte.

Étant donné que l'espace de recherche est très large ($2^{(2^n - n - 1)}$, pour $n$ tables), nous sommes obligés d'avoir des algorithmes de sélection pour trouver les IGJs optimaux ou quasi-optimaux afin d'évaluer un ensemble de requêtes. Ces algorithmes font l'objet de la section suivante.

Nous montrons d'abord que le problème de sélection des IGJs peut être formulé comme un problème d'optimisation. Nous suggérons ensuite des algorithmes pour résoudre ce problème.

### 3.8.2 La formulation du problème de sélection des IGJs

La plupart des algorithmes de sélection d'index proposés pour les bases de données [FST88, Val87, BG93, FKL98] ou les entrepôts [DRT99, CN97, GHRU97, LR98] sélectionnent un ensemble d'index optimisant une fonction objectif et satisfaisant une contrainte de ressource. Nous nous placons dans les mêmes conditions générales en choisissant comme fonction objectif le nombre d'entrées-sorties pour exécuter un ensemble de requêtes et comme contrainte de ressource l'espace disque pour stocker les index sélectionnés.

Les entrées de notre problème sont:

<footnote n="9">⁹vue, dimensions, ou faits</footnote>
1. Un schéma en étoile ayant une table des faits F et d tables de dimensions $\{D_1, D_2, ..., D_d\}$.

2. Un ensemble de requêtes (les plus fréquemment utilisées) $\mathcal{Q} = \{Q_1, Q_2, ..., Q_s\}$ avec leurs fréquences d'accès $\{f_1, f_2, ..., f_s\}$.

3. Un ensemble de vues matérialisées $\mathcal{V} = \{V_1, V_2, ..., V_m\}$ sélectionné pour supporter l'exécution de l'ensemble de requêtes.

4. Une capacité de stockage S destinée au stockage des index sélectionnés.

Le problème de sélection des IGJs consiste à sélectionner un ensemble d'IGJs $\mathcal{G}'$ minimisant le coût total d'exécution de l'ensemble des requêtes (CT). L'ensemble des index sélectionnés doit satisfaire la contrainte suivante: l'espace total occupé par $\mathcal{G}'$ (dénoté par $S_{\mathcal{G}'}$) doit être inférieur ou égal à S.

Plus formellement, soit $\mathcal{G}$ l'ensemble de tous les IGJs possibles. Notons par $C_{\mathcal{G}_j}(Q_i)$ le coût d'évaluation de la requête $Q_i$ en utilisant l'IGJ $\mathcal{G}_j$. Étant donné une capacité d'espace S, l'objectif de SIGJ est de sélectionner un ensemble d'IGJs $\mathcal{G}'$ ($\mathcal{G}' \subseteq \mathcal{G}$) tel que:

$$ CT = \sum_{i=1}^{s} f_i \times \{\min_{\forall \mathcal{G}_j \in \mathcal{G}'} C_{\mathcal{G}_j}(Q_i)\} \quad (3.12) $$

sous la contrainte: $S_{\mathcal{G}'} \le S$.

### 3.8.3 Les algorithmes de sélection des IGJs

Trois algorithmes de sélection sont présentés, à savoir: (1) un algorithme naïf sélectionnant un index optimal, (2) un algorithme glouton sélectionnant seulement un index, et (3) un algorithme glouton sélectionnant plusieurs index. Ces algorithmes sont décrits dans les sections qui suivent.

#### 3.8.3.1 L'algorithme naïf

Cet algorithme est utilisé seulement à des fins de comparaison. Il consiste à énumérer d'une manière exhaustive l'ensemble $\mathcal{G}$ de tous les IGJs possibles. Pour chaque IGJ $G_i \in \mathcal{G}$, l'algorithme naïf calcule le coût d'exécution de l'ensemble de requêtes (en utilisant cet index). Finalement, l'index offrant un coût d'exécution des requêtes minimum et satisfaisant la contrainte d'espace est sélectionné.

L'avantage majeur de cet algorithme est que l'index sélectionné est optimal. Il est à noter cependant que cet algorithme est impraticable dans les cas réels<fnref n="10" /> (voir section 3.8.1).

#### 3.8.3.2 L'algorithme glouton pour sélectionner un seul index

Comme nous l'avons vu, l'énumération exhaustive des IGJs est très coûteuse. Pour éviter cette énumération, un algorithme glouton sélectionnant un seul IGJ (AGS1) est présenté. Avant de présenter cet algorithme, définissons la notion de graphe de jointure étiqueté.

<footnote n="10">¹⁰Un entrepôt de données typique peut contenir 10 ou plus tables de dimensions [KR98]</footnote>
<figure><img src="image_38.png" /><figcaption>FIG. 3.14: Le graphe de jointure étiqueté</figcaption></figure>

**Définition 28** Un **graphe de jointure étiqueté** est un GJ où chaque arête $e(T_i, T_j)$ est associée à un poids. Ce dernier est égal à la somme des fréquences d'accès des requêtes utilisant cette arête.

**Exemple 14** Le graphe de jointure étiqueté correspondant au graphe de jointure de la figure 3.12 est illustré dans la figure 3.14. La représentation du poids de chaque arête peut être réalisée à l'aide de la matrice de réécriture. Par exemple, l'arête $(V_2, \text{CLIENT})$ a un poids égal à 20. Cette arête est utilisée par les requêtes $Q_3$ et $Q_5$ ayant les fréquences 5 et 15 (dont la somme est égale au poids de cette arête: 20) (voir Figure 3.14).

L'algorithme AGS1 a le graphe de jointure étiqueté et la capacité d'espace $S$ comme entrées. Il est décrit de la façon suivante:

Il commence par sélectionner un IGJ simple (une arête de graphe de jointure étiqueté) ayant un poids maximal. Une fois cet index sélectionné, l'algorithme essaye d'ajouter d'autres noeuds à cet index. L'objectif de cette opération est de réduire le coût d'exécution des requêtes.

Lorsque plus aucune opération d'ajout n'est possible, l'algorithme essaye de réduire la taille de l'index en éliminant certains noeuds. Le but de cette élimination est de réduire le coût d'exécution des requêtes et/ou le coût de stockage de l'index.

Les deux opérations sont dirigées par un coût (cost-driven): c'est-à-dire qu'elles sont appliquées si elles réduisent le coût d'exécution des requêtes et si le coût de stockage de l'IGJ sélectionné ne dépasse pas $S$.

Maintenant, nous décrivons les deux opérations ajout et élimination.

## L'opération d'ajout

1. Soit l'IGJ $G_i = (u_{i_1} \sim u_{i_2} \sim \dots \sim u_{i_k})$ obtenu à l'étape $i$ de l'algorithme. Notons que cet index doit respecter la contrainte suivante: $S_G < S$, où $S_G$ représente la capacité de stockage nécessaire pour l'index $G_i$.

2. Soit $CT_{G_i}$ le coût total d'exécution de toutes les requêtes en utilisant l'IGJ $G_i$. $CT_{G_i}$ est donné par l'équation suivante:

$$CT_{G_i} = \sum_{j=1}^{s} C_{G_i}(Q_j) \qquad (3.13)$$

où $C_{G_i}(Q_j)$ représente le coût d'exécution de la requête $Q_j$ en utilisant l'index $G_i$.

3. Pour ajouter un noeud à l'IGJ $G_i$, deux alternatives sont possibles:

$$(i) G'_i = (u_{i_1-1} \sim u_{i_1} \sim \dots \sim u_{i_k})$$
$$
(ii) G_i'' = (u_{i_1} \sim u_{i_2} \sim \dots \sim u_{(i_k+1)}
$$

Si $C_{G_i'} \le C_{G_i''} \le C_{G_i}$, alors $G_i = G_i'$ si $S_{G_i'} \le S$.

Si $C_{G_i''} \le C_{G_i'} \le C_{G_i}$, alors $G_i = G_i''$ si $S_{G_i''} \le S$.

Sinon, $G_i$ est inchangé.

L'opération d'élimination

1. Soit un IGJ $G_i = (u_{i_1} \sim u_{i_2} \sim \dots \sim u_{i_k})$ de longueur $k$. À partir de $G_i$, les IGJs suivants de longueur $k-1$ peuvent être générés:

$(u_{i_2} \sim \dots \sim u_{i_k}), (u_{i_1} \sim u_{i_3} \sim \dots \sim u_{i_k}), \dots, (u_{i_1} \sim u_{i_2} \sim \dots \sim u_{i_{k-1}}).$

Soit $G_i''$ l'IGJ offrant un meilleur coût entre tous ces IGJs. Si $C_{G_i'} < C_{G_i}$ et $S_{G_i'} < S$, alors $G_i = G_i''$, sinon, nous gardons l'IGJ courant $G_i$.

Un noeud peut être éliminé si les noeuds qui restent après l'élimination peuvent
être joignables.

Avec ces deux opérations, l'AGS1 peut facilement être décrit.

Algorithme 5 Les étapes de AGS1

1: Construire le graphe de jointure étiqueté

2: Trier les arêtes de ce graphe en fonction de leurs poids. Soit $L$ la liste triée dans un ordre descendant.

3: Sélectionner l’index $G_i = (u_i \sim u_j)$ de $L$ satisfaisant la contrainte de stockage.

4: Appliquer l'opération d'ajout ($G_i$)

5: Répéter cette opération jusqu'à ce qu'aucune réduction dans le coût d'exécution des requêtes ne soit constatée et que la capacité de stockage ne soit pas violée.

6: Appliquer l'opération d'élimination ($G_i$)

7: Répéter cette opération jusqu'à ce qu'aucune réduction dans le coût d'exécution des requêtes ne soit constatée et que la capacité de stockage ne soit pas violée.

8: L'IGJ sélectionné est $G_i$

**Exemple 15** Pour illustrer cet algorithme, considérons dans un premier temps que nous n'avons aucune contrainte d'espace; ensuite une contrainte d'espace est considérée.

- Pas de contrainte d'espace: Considérons le GJ étiqueté de la Figure 3.14. La liste des arêtes triées est construite de la manière suivante:

$$
L = [(V_2 \sim C), (V_2 \sim T), (V_1 \sim T), (V_1 \sim V_2), (T \sim C), (V_1 \sim C)]^{11}
$$

En exécutant la première étape de l'algorithm, nous sélectionnons l'IGJ suivant $G = (V_2 \sim C)$ (l'index représenté par l'arête de poids maximum). Le coût d'exécution des cinq requêtes de la Figure 3.7 en utilisant cet index est $C_G = 172495$ pages (voir Table 3.6).

L'opération d'ajout est ensuite utilisée afin de réduire le plus possible le coût
des requêtes. Le résultat de cette opération est l'IGJ $G'$ : $(V_1 \sim V_2 \sim C)$. Ce

<footnote n="11"><sup>11</sup>Pour des raisons de simplicité, les tables CLIENT et TEMPS sont remplacées par leurs initiaux C et T</footnote>
dernier réduit le coût des requêtes à 129034. L'algorithme essaye encore une fois d'ajouter un nouveau noeud à l'index G'. Finalement, nous obtenons l'IGJ complet: $G'' = (T \sim V_1 \sim V_2 \sim C)$. Le coût des requêtes en présence de cet index est de 27240 pages (voir la Figure 3.15).

Une fois l'IGJ complet atteint, l'application de l'opération d'ajout n'est plus possible. Maintenant, vient le tour de l'opération d'élimination. Cette dernière considère le dernier index obtenu à partir de l'opération d'ajout. Elle com-mence par exemple par éliminer la vue $V_1$ de l'index G entre $T$ et $V_2$ (voir Figure 3.15). Cette opération ne réduit pas le coût des requêtes et toutes les autres opérations d'élimination non plus. En effet l'IGJ complet garantit la meilleure performance des requêtes et aucune contrainte n'est considérée.

Finalement, l'IGJ obtenu par cet algorithme est: $G'' = (T \sim V_1 \sim V_2 \sim C)$. Notons que L'algorithme naif donne également le même IGJ. Dans cet exemple, l'algorithme AGS1 fournit donc une solution optimale.

- La présence d'une contrainte: Maintenant, nous exécutons l'algorithme AGS1 en considérant une contrainte d'espace de 0.1 Gigabytes. Dans ce cas, le premier index de la liste ($V_2 \sim C$) demande 189002678 bytes, ce qui supérieur à la capacité d'espace initial. L'algorithme devra donc sélectionner un autre élément de la liste L satisfaisant la contrainte d'espace. L'index ($V_1 \sim T$) (81504731 bytes) est le premier élément de L ayant un espace inférieur à 0.1 Gigabytes. L'opération d'ajout est donc appliquée à cet index. Cette dernière donne l'IGJ suivant: ($V_1 \sim T \sim C$) exigeant plus de 0.1 Gigabytes (125159899 bytes). La dernière opération donne l'IGJ suivant: ($V_1 \sim T \sim V_2$) exigeant un espace de 232690614 bytes qui est supérieur à 0.1 Gigabytes. L'index ($V_1 \sim T$) réprésente le meilleur index respectant la contrainte de stockage <fnref n="12" />. Notons au passage que l'algorithme naif donne la même solution.

### 3.8.3.3 L'algorithme glouton sélectionnant K IGJs (AGSK)

Rappelons que l'algorithme précédent sélectionne un seul IGJ. Notons que cet index peut être performant pour certaines requêtes, mais pas pour toutes. En consé-quence, la sélection de plusieurs IGJs doit être considérée afin d'assurer une meilleure performance de toutes les requêtes. Dans cette section, nous développons un autre algorithme glouton sélectionnant au plus $2^n-n-1$ IGJs sous une contrainte d'espace.

AGSK commence par une solution initiale représentant un seul index; elle est obtenue par l'algorithme AGS1. Ensuite, il sélectionne une arête du graphe étiqueté ayant un poids maximum et qui ne représente pas l'index obtenu par AGS1. L'algorithme AGSK applique alors les opérations d'ajout (une ou plusieurs fois) et d'élimination (une ou plusieurs fois) tant qu'il y a une possibilité de réduction dans le coût d'évaluation des requêtes et que la contrainte d'espace est satisfaite.

Cela génère un second GJI. L'algorithme répéte cette procédure jusqu'à ce que les K index soient identifiés ou que la capacité de stockage soit violée.

**Exemple 16** Dans cet exemple, nous illustrons le fonctionnement de l'algorithme AGSK (sans contrainte d'espace) en utilisant les mêmes données que dans l'exemple

<footnote n="12">¹²Dans cet exemple, l'opération d'élimination ne peut pas être appliquée à cause de la taille de l'index trouvé</footnote>
<figure><img src="image_39.png" /><figcaption>FIG. 3.15: Un exemple de déroulement de l'AGS1</figcaption></figure>

**Algorithm 6** Les étapes de AGSK

1: Soit $G_i$ un IGJ obtenu à l'aide de l'AGS1.

2: Initialiser $i$ à 2 ($i := 2$)

3: **while** ($i \le 2^n - n - 1$) et $S_G < S$ **do**

4: Soit $G_j$ l'arête suivante de $L$ qui n'a pas été sélectionnée par l'AGS1, et $S_{G_i} + S_{G_j} < S$. Si cette arête n'existe pas alors **fin de l'algorithme**.

5: Soit $\mathcal{G} = G_i \cup G_j$ et $S_G = \sum_{\forall G \in \mathcal{G}} (S_G)$.

6: Appliquer l'opération ajout $(G_j)$

7: Appliquer l'opération d'élimination $(G_j)$

8: **if** aucune opération d'ajout et d'élimination n'est possible **then**

9: Incrémenter $i$

10: **end if**

11: **end while**

12: $\mathcal{G}$ est l'ensemble des IGJs finaux
précédent. L'algorithme AGSK commence par l'index obtenu par l'algorithme AGS1 qui est $G_1 = (T \sim V_1 \sim V_2 \sim C)$. L'algorithme AGSK sélectionne une arête de L qui ne représente pas l'index $G_1$. L'arête sélectionnée représente l'index suivant: $(V_1 \sim T)$ qui réduit le coût d'exécution des requêtes. Il n'est alors plus possible d'appliquer les opérations d'ajout et d'élimination.

Finalement, cet index est sélectionné par l'algorithme. L'ensemble final des IGJs $G$ devient: $G = \{(T \sim V_1 \sim V_2 \sim C), (V_1 \sim T)\}$.

Aucun index réduisant le coût des requêtes ne peut plus être ajouté. Les deux index sélectionnés donnent un coût de requêtes de 27213 pages. L'algorithme naif génère la même solution. Dans ce cas, AGSK fournit la solution optimale.

## 3.9 Evaluation des index de graphe de jointure

Notre étude expérimentale utilise un schéma en étoile emprunté à Informix [Cor97b]. Comme dans la section 2, le schéma possède trois tables de dimensions CLIENT, TEMPS et PRODUIT et une table des faits VENTES. Les caractéristiques de cette expérience sont données dans la Table 3.4.

<table><caption>TAB. 3.4: Les paramètres utilisés dans l'expérience</caption><thead><tr><td>Paramètre</td><td>Description</td><td>Valeur</td></tr></thead><tbody><tr><td>||VENTES||</td><td>Nombre de n-uplets</td><td>100000000</td></tr><tr><td>|VENTES|</td><td>Nombre de pages</td><td>415040</td></tr><tr><td>w(VENTES)</td><td>Taille d'un n-uplet de VENTES (en bytes)</td><td>34</td></tr><tr><td>||CLIENT||</td><td>Nombre de n-uplets</td><td>3000000</td></tr><tr><td>|CLIENT|</td><td>Nombre de pages</td><td>21607</td></tr><tr><td>w(CLIENT)</td><td>Taille d'un n-uplet CLIENT (en bytes)</td><td>59</td></tr><tr><td>||PRODUIT||</td><td>Nombre de n-uplets</td><td>300000</td></tr><tr><td>|PRODUIT|</td><td>Nombre de pages</td><td>1868</td></tr><tr><td>w(PRODUIT)</td><td>Taille d'un n-uplet PRODUIT (en bytes)</td><td>51</td></tr><tr><td>||TEMPS||</td><td>Nombre de n-uplets</td><td>1094</td></tr><tr><td>|TEMPS|</td><td>Nombre de pages</td><td>5</td></tr><tr><td>w(TEMPS)</td><td>Taille d'un n-uplet TEMPS (en bytes)</td><td>30</td></tr><tr><td>||Vue_1||</td><td>Nombre de n-uplets</td><td>2000000</td></tr><tr><td>||Vue_2||</td><td>Nombre de n-uplets</td><td>4000000</td></tr><tr><td>PS</td><td>Taille de la page (en bytes)</td><td>8192</td></tr><tr><td>π</td><td>Taille du pointeur de bloc (en bytes)</td><td>8</td></tr></tbody></table>

Nous considérons cinq requêtes dont les facteurs de sélectivité sont décrits dans la Figure 3.7.

Afin d'accélérer l'exécution de ces requêtes, deux vues $V_1$ et $V_2$ sont sélectionnées en utilisant `sélect_vue` (voir section 3.3). Ces vues sont définies comme suit:

$$ - V_1 = \sigma_{E_{\text{tat}}=\text{"IL"}}(\text{CLIENT}) \boxtimes \text{VENTES}, $$

$$ - V_2 = \sigma_{\text{Type\_Paquet}=\text{"Boite"}}(\text{PRODUIT}) \boxtimes \text{VENTES}. $$

La Figure 3.16 donne la matrice de réécriture avec la fréquence d'accès de chaque requête. Étant donné que les requêtes peuvent utiliser directement ces vues, nous
<figure><img src="image_40.png" /><figcaption>FIG. 3.16: La matrice de réécriture</figcaption></figure>

commençons par évaluer l'indexation des vues et des tables de dimensions relative-ment à la réduction du coût d'évaluation des requêtes.

La Table 3.5 énumère les 11 IGJs possibles pour $n = 4$ noeuds. Ces index sont construits sur les tables de dimensions TEMPS ($T$) et CLIENT ($C$), et les vues $V_1$ et $V_2$. Rappelons que les tables de dimensions TEMPS et CLIENT ont une cardinalité de 3000000 et 1094, respectivement. Les cardinalités des vues $V_1$ et $V_2$ sont 2000000 et 4000000 n-uplets, respectivement.

<table><caption>TAB. 3.5: L'ensemble de IGJs et leurs tailles</caption><thead><tr><th>Index</th><th>V<sub>1</sub></th><th>V<sub>2</sub></th><th>TEMPS (T)</th><th>CLIENT (C)</th><th>N-uplets</th></tr></thead><tbody><tr><td>V<sub>1</sub> ~ V<sub>2</sub></td><td>1</td><td>1</td><td>0</td><td>0</td><td>4000000</td></tr><tr><td>V<sub>1</sub> ~ T</td><td>1</td><td>0</td><td>1</td><td>0</td><td>2000000</td></tr><tr><td>V<sub>1</sub> ~ C</td><td>1</td><td>0</td><td>0</td><td>1</td><td>2000000</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ T</td><td>1</td><td>1</td><td>1</td><td>0</td><td>4000000</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ C</td><td>1</td><td>1</td><td>0</td><td>1</td><td>4000000</td></tr><tr><td>V<sub>1</sub> ~ T ~ C</td><td>1</td><td>0</td><td>1</td><td>1</td><td>2000000</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ T ~ C</td><td>1</td><td>1</td><td>1</td><td>1</td><td>4000000</td></tr><tr><td>V<sub>2</sub> ~ T</td><td>0</td><td>1</td><td>1</td><td>0</td><td>4000000</td></tr><tr><td>V<sub>2</sub> ~ C</td><td>0</td><td>1</td><td>0</td><td>1</td><td>4000000</td></tr><tr><td>V<sub>2</sub> ~ T ~ C</td><td>0</td><td>1</td><td>1</td><td>1</td><td>4000000</td></tr><tr><td>T ~ C</td><td>0</td><td>0</td><td>1</td><td>1</td><td>9846000</td></tr></tbody></table>

En regardant la Table 3.6, nous pouvons constater que l'IGJ ($V_1 \sim T$) a le coût de stockage le moins élevé avec 81504731 bytes, mais il présente le plus petit coût d'évaluation pour la $Q_4$ seulement. D'un autre côté, l'IGJ ($V_1 \sim V_2 \sim T \sim C$) donne le plus petit coût d'évaluation pour les requêtes $Q_1, Q_2, Q_3$ et $Q_5$, mais pas pour la requête $Q_4$. En fait la requête $Q_4$ nécessite un accès seulement à la vue $V_1$ et à la table de dimension TEMPS, et l'IGJ ($V_1 \sim T$) correspond exactement à cette requête. Le coût de stockage de l'IGJ ($V_1 \sim V_2 \sim T \sim C$) est de 293778358 bytes (presque 0.3 GBs). Cette expérience montre qu'il n'existe pas un unique IGJ offrant le meilleur coût d'évaluation des requêtes pour toutes les requêtes. Ceci confirme l'intérêt de l'algorithme AGSK (section 3.8).

La Table 3.7 donne le coût normalisé d'évaluation de chaque requête en utilisant les différents IGJs. Cette normalisation est effectuée en prenant le coût de la jointure par hachage comme référence. L'IGJ complet ($V_1 \sim V_2 \sim T \sim C$) a un coût normalisé d'évaluation des requêtes variant de 1% (pour la requête $Q_3$) à 100% (pour la requête $Q_1$). Pour les requêtes $Q_3$ et $Q_5$, la plupart des IGJs (à l'exception de $V_1 \sim T$) donne un coût bien moindre que la jointure par hachage. Cela est dû au
<table><caption>TAB. 3.6: Le coût de stockage des IGJs et le coût d'évaluation des requêtes</caption><thead><tr><th>Index</th><th>Stockage</th><th>Q<sub>1</sub></th><th>Q<sub>2</sub></th><th>Q<sub>3</sub></th><th>Q<sub>4</sub></th><th>Q<sub>5</sub></th><th>CT</th></tr></thead><tbody><tr><td>V<sub>1</sub> ~ V<sub>2</sub></td><td>197751734</td><td>21729</td><td>41522</td><td>106343</td><td>21729</td><td>106328</td><td>297652</td></tr><tr><td>V<sub>1</sub> ~ T</td><td><b>81504731</b></td><td>21729</td><td>118683</td><td>183504</td><td><b>636</b></td><td>151248</td><td>475800</td></tr><tr><td>V<sub>1</sub> ~ C</td><td>107653595</td><td>21729</td><td>118656</td><td>141254</td><td>21729</td><td>119560</td><td>422928</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ T</td><td>232690614</td><td>21729</td><td>1158</td><td>104431</td><td>663</td><td>106328</td><td>234310</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ C</td><td>258839478</td><td>21729</td><td>41522</td><td>41522</td><td>21729</td><td>2531</td><td>129034</td></tr><tr><td>V<sub>1</sub> ~ T ~ C</td><td>125159899</td><td>21729</td><td>118683</td><td>118683</td><td>636</td><td>119560</td><td>379292</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ T ~ C</td><td>293778358</td><td>21729</td><td>1158</td><td>1158</td><td>663</td><td>2531</td><td>27240</td></tr><tr><td>V<sub>2</sub> ~ T</td><td>162853814</td><td>21729</td><td>1158</td><td>104431</td><td>65244</td><td>106328</td><td>298891</td></tr><tr><td>V<sub>2</sub> ~ C</td><td>189002678</td><td>21729</td><td>41522</td><td>41522</td><td>65190</td><td>2531</td><td>172495</td></tr><tr><td>V<sub>2</sub> ~ T ~ C</td><td>223941558</td><td>21729</td><td>1158</td><td>1158</td><td>65244</td><td>2531</td><td>91821</td></tr><tr><td>T ~ C</td><td>97060186</td><td>21729</td><td>118697</td><td>118697</td><td>65231</td><td>119580</td><td>443935</td></tr><tr><td>IJE complet</td><td>4967170048</td><td>23144</td><td>31595</td><td>31595</td><td>23147</td><td>45491</td><td>154973</td></tr><tr><td>Jointure par hachage</td><td>0</td><td>21729</td><td>118656</td><td>153846</td><td>65190</td><td>151248</td><td>510669</td></tr></tbody></table>

fait que les requêtes $Q_3$ et $Q_5$ sont réécrites en fonction de la vue $V_2$ et la table de dimension CLIENT, qui ont une taille plus importante que les autres tables (voir Table 3.5, Figure 3.16). Notons que le résultat de la requête $Q_1$ coïncide exactement avec la vue $V_1$ (la présence d'IGJ n'a pas d'influence (voir section 3.6).

<table><caption>TAB. 3.7: Coût normalisé d'évaluation des requêtes</caption><thead><tr><th>Index</th><th>Q<sub>1</sub></th><th>Q<sub>2</sub></th><th>Q<sub>3</sub></th><th>Q<sub>4</sub></th><th>Q<sub>5</sub></th><th>CT</th></tr></thead><tbody><tr><td>V<sub>1</sub> ~ V<sub>2</sub></td><td>0.00</td><td>0.35</td><td>0.69</td><td>0.33</td><td>0.70</td><td>0.58</td></tr><tr><td>V<sub>1</sub> ~ T</td><td>0.00</td><td>1.00</td><td>1.19</td><td>0.01</td><td>1.00</td><td>0.93</td></tr><tr><td>V<sub>1</sub> ~ C</td><td>0.00</td><td>1.00</td><td>0.92</td><td>0.33</td><td>0.79</td><td>0.82</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ T</td><td>0.00</td><td>0.01</td><td>0.68</td><td>0.01</td><td>0.70</td><td>0.45</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ C</td><td>0.00</td><td>0.35</td><td>0.27</td><td>0.33</td><td>0.02</td><td>0.25</td></tr><tr><td>V<sub>1</sub> ~ T ~ C</td><td>0.00</td><td>1.00</td><td>0.77</td><td>0.01</td><td>0.79</td><td>0.74</td></tr><tr><td>V<sub>1</sub> ~ V<sub>2</sub> ~ T ~ C</td><td>0.00</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.02</td><td>0.05</td></tr><tr><td>V<sub>2</sub> ~ T</td><td>0.00</td><td>0.01</td><td>0.68</td><td>1.00</td><td>0.70</td><td>0.58</td></tr><tr><td>V<sub>2</sub> ~ C</td><td>0.00</td><td>0.35</td><td>0.27</td><td>1.00</td><td>0.02</td><td>0.33</td></tr><tr><td>V<sub>2</sub> ~ T ~ C</td><td>0.00</td><td>0.01</td><td>0.01</td><td>1.00</td><td>0.02</td><td>0.17</td></tr><tr><td>T ~ C</td><td>0.00</td><td>1.00</td><td>0.77</td><td>1.00</td><td>0.79</td><td>0.86</td></tr></tbody></table>

Les résultats illustrent bien l'utilité des IGJs dans l'exécution des requêtes. Ces index permettent d'établir un bon compromis entre le coût d'exécution et le coût de stockage. De plus ils peuvent être uniformément appliqués aux tables de dimensions, à la table des faits et aux vues matérialisées. Ils sont significativement plus efficaces en présence des vues matérialisées. Par exemple en utilisant les deux vues $V_1$ et $V_2$, l'IGJ complet ($V_1 \sim V_2 \sim T \sim C$) procure un coût d'exécution de 27240 IOs pour un stockage de 0.3 GBs. Sans vues matérialisées, l'index de jointure en étoile complet ($S \sim P \sim T \sim C$) conduit à un coût d'exécution 6 fois plus grand (154973 IOs) pour un espace de stockage 17 fois plus grand (5 GB). Il est donc important de ne pas considérer la sélection des index de jointure indépendamment de la sélection des
vues matérialisées.
# Chapitre 4

## Interaction entre les vues matérialisées et les index

### 4.1 Introduction

Nombre de travaux récents concernant la sélection des vues matérialisées et la sélection des index ont été réalisés dans les contextes ROLAP et MOLAP (voir chapitre 2). De nombreux systèmes commerciaux proposent la création et l'utilisation des vues matérialisées et des index [Ora99, CN97, CN98].

Conceptuellement, 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 certaines similitudes. En effet, il s'agit de structures **redondantes** qui se **partagent** la même ressource (l'espace disque). Toutes deux peuvent entraîner des **surcharges** (overhead) 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 d'une table relationnelle dans le contexte ROLAP, et son indexation peut toujours 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. Cependant, un outil de conception physique d'un entrepôt de données doit prendre en considération l'interaction entre les vues matérialisées et les index.

Dans la littérature disponible, la sélection des vues et la sélection des index sont deux tâches **séquentielles**: la sélection des vues passe avant la sélection des index (voir Figure 4.1). La sélection séquentielle présente deux inconvénients majeurs:

- L'impossibilité de considérer plusieurs algorithmes de sélection: Nous avons vu que les algorithmes de sélection des vues à matérialiser et des index sont contraints par une contrainte donnée (parmi les trois citées dans les chapitres précédents: l'espace disque, le coût de maintenance, le coût de calcul). Rappe-lons que les PSV et PSI sont formulés de la manière suivante:

Le PSV consiste à sélectionner un ensemble de vues {$V_1, V_2, ..., V_k$} minimisant/maximisant une fonction "objectif" et satisfaisant une contrainte A. Le PSI sélectionne un ensemble d'index {$I_1, I_2, ..., I_{k'}$} minimisant/maximisant une fonction "objectif" et satisfaisant une contrainte B. Étant donné que les deux contraintes A et B peuvent être semblables ou différentes, la sélection
<figure><img src="image_41.png" /><figcaption>FIG. 4.1: Le processus de sélection des vues et des index</figcaption></figure>

séquentielle peut entraîner la considération de 9 problèmes de sélection correspondant à la combinaison de trois contraintes (voir Figure 4.2). Nous pouvons trouver, par exemple, un algorithme de sélection de vues contraint par l'espace disque, et un algorithme de sélection des index contraint par le coût de maintenance, et ainsi de suite.

- *La non prise en considération de l'interaction entre les vues et les index:* Dans le cas où les deux problèmes ont la même contrainte (c'est-à-dire, $A = B$), trois formulations séquentielles de PSV et PVI sont possibles (voir Figure 4.3). Ignorer l'interaction entre les vues et les index entraîne un problème de gestion des ressources (représentant les contraintes) entre les vues et les index. Pour éclairer ce point, supposons que l'administrateur dispose d'une capacité de stockage $S$ destinée aux vues et aux index. Étant donné que les index et les vues sont deux structures en compétition sur la même ressource (l'espace disque), la question qui se pose est de savoir comment cette capacité est distribuée d'une manière automatique entre eux afin de garantir une meilleure performance pour les requêtes.

Une mauvaise distribution peut compromettre la qualité des solutions obtenues par les algorithmes de sélection des vues et des index.

Dans ce chapitre, nous nous attachons au problème de la gestion de la ressource représentant l'espace disque. Autrement dit le problème de distribution de l'espace disque entre les vues et les index, avec pour objectif l'amélioration de la performance des requêtes.

## 4.2 Motivations

Le problème de distribution de l'espace entre les vues et les index représente un enjeu important pour les chercheurs et les industriels. En effet, il peut avoir
Contraintes

<table><caption>FIG. 4.2: La formulation séquentielle de PSV et PSI: le cas de $A \neq B$</caption><thead><tr><th>Problème</th><th>Espace</th><th>Coût de maintenance</th><th>Temps de calcul</th></tr></thead><tbody><tr><td>PSV</td><td>√</td><td></td><td></td></tr><tr><td>PSI</td><td>√</td><td></td><td></td></tr><tr><td>PSV</td><td>√</td><td></td><td></td></tr><tr><td>PSI</td><td></td><td>√</td><td></td></tr><tr><td>PSV</td><td>√</td><td></td><td></td></tr><tr><td>PSI</td><td></td><td></td><td>√</td></tr><tr><td>PSV</td><td></td><td>√</td><td></td></tr><tr><td>PSI</td><td>√</td><td></td><td></td></tr><tr><td>PSV</td><td></td><td>√</td><td></td></tr><tr><td>PSI</td><td></td><td></td><td>√</td></tr><tr><td>PSV</td><td></td><td>√</td><td></td></tr><tr><td>PSI</td><td></td><td></td><td></td></tr><tr><td>PSV</td><td></td><td></td><td>√</td></tr><tr><td>PSI</td><td></td><td></td><td>√</td></tr></tbody></table>

un effet crucial sur la performance des requêtes et poser des problèmes énormes à l’administrateur dans les cas statique et dynamique, comme nous allons le voir dans les sections qui suivent.

### 4.2.1 Le cas statique

Pour illustrer ces difficultés, considérons le scénario suivant:
Soit $S$ l'espace disque global que l'administrateur possède pour sélectionner un ensemble de vues $V$ et un ensemble d'index $I$. Pour répartir $S$ entre $V$ et $I$, l'administrateur a trois possibilités:

Contraintes

<table><caption>FIG. 4.3: La formulation séquentielle de PSV et PSI: le cas $A = B$</caption><thead><tr><th>Problème</th><th>Espace</th><th>Coût de maintenance</th><th>Temps de calcul</th></tr></thead><tbody><tr><td>PSV</td><td>√</td><td></td><td></td></tr><tr><td>PSI</td><td>√</td><td></td><td></td></tr><tr><td>PSV</td><td></td><td>√</td><td></td></tr><tr><td>PSI</td><td></td><td>√</td><td></td></tr><tr><td>PSV</td><td></td><td></td><td>√</td></tr><tr><td>PSI</td><td></td><td></td><td>√</td></tr></tbody></table>
1. Attribuer la totalité de l'espace disque $S$ aux vues matérialisées seules. Toutes les requêtes décisionnelles sont alors exprimées en fonction des vues et des relations de base. Cette attribution n'est pas efficace. En effet, plusieurs travaux ont démontré que des vues matérialisées seules sont insuffisantes pour accélérer toutes les requêtes décisionnelles [BKL99, LQA97, SSN00]. Cette possibilité est de ce fait écartée.

2. Attribuer la totalité de $S$ aux index seuls. Toutes les requêtes décisionnelles sont maintenant traitées en fonction des index et des relations de base. Or, interroger un entrepôt de données sans vues matérialisées ne garantit aucune performance [KR98, Gup99, YKL97, CY99b]. En conséquence, les index seuls sont insuffisants pour garantir une bonne performance des requêtes décisionnelles. Cette possibilité est donc également écartée.

3. La dernière possibilité consiste en un compromis entre les deux premières possibilités. Ce compromis devrait garantir une bonne performance et de ce fait est l'objet de notre étude.

Plus formellement, l'administrateur doit déterminer une fraction $f$ ($0 \le f \le 1$) tel que le quota d'espace définie par $f \times S$ soit réservé aux vues matérialisées (ou aux index) et le quota d'espace défini par $(1 - f) \times S$ soit réservé aux index (ou aux vues).

Trois possibilités de distribution sont possibles: (i) une distribution uniforme, (ii) une distribution aléatoire et (iii) une distribution calculée.

**Définition 29** La distribution uniforme présente une répartition équitable de $S$ entre les vues et les index ($f = 0.5$).

**Définition 30** La distribution aléatoire présente une répartition quelconque de $S$.

**Définition 31** La distribution calculée consiste en l'attribution de l'espace aux vues et aux index, en respectant certains critères.

Certes, les distributions uniforme et aléatoire sont faciles à obtenir, mais elles présentent plusieurs inconvénients:

- Elles ne prennent pas en compte l'interdépendance mutuelle entre les vues et les index (voir Figure 4.1).

- La distribution aléatoire peut allouer plus d'espace que nécessaire aux vues (ou aux index). Cette allocation se fait au détriment de l'espace des index et vice versa. Notons que pour une exécution efficace des requêtes, il est parfois préférable d'avoir plus d'espace pour les vues que pour les index (ou vice-versa).

- Ces deux distributions ne possèdent aucune métrique garantissant la réduction du coût de l'ensemble de requêtes.

### 4.2.2 Le cas dynamique

Étant donné que l'entrepôt de données est un environnement dynamique, le problème de redistribution d'espace entre les vues et les index doit être considéré après
les opérations de mise à jour. Ces dernières interviennent au niveau des tables des sources de l'entrepôt, et les changements correspondants doivent être répercutés 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 revoir la distribution initiale de l'espace global entre les vues et les index afin de garantir une meilleure performance. Un autre problème pouvant entraîner une redistribution de l'espace est le changement des requêtes de départ (ajout/suppression de requêtes, changement de fréquence d'accès des requêtes, etc). Cela est dû au fait que la plupart des algorithmes de sélection des vues et des index sont basés sur des requêtes connues a priori (voir Chapitre 2).

Dans ce chapitre, nous proposons des solutions au problème de distribution de l'espace entre les vues et les index dans les contextes *statique* et *dynamique*. Les contributions principales de ce chapitre sont: (1) la présentation d'une méthodologie itérative de distribution efficace de l'espace entre les vues et les index, (2) l'évaluation de cette méthodologie et l'illustration de son utilité.

## 4.3 L'intuition de notre approche de distribution

L'objectif principal à satisfaire pour la sélection des vues matérialisées et la sélection d'index est la *minimisation du coût total d'évaluation des requêtes décisionnelles* [BKS00, YKL97, Gup99, CN97]. Notre solution de distribution de l'espace entre les vues et les index doit également satisfaire cet objectif.

L'intuition sous-jacente de notre approche est la suivante: Initialement, l'administrateur estime les deux quotas d'espace $S^V$ et $S^I$ pour les vues matérialisées et les index respectivement, ($S = S^V + S^I$). Cette estimation peut être établie en utilisant une distribution uniforme ou aléatoire. En fonction du quota réservé aux vues $S^V$, l'administrateur sélectionne un ensemble de vues $V = \{V_1, V_2, ..., V_s\}$ en utilisant l'un des algorithmes de sélection de vues dirigés par la contrainte d'espace (voir Chapitre 2).

Une fois les vues sélectionnées, un ensemble d'index $I$ est construit $I = \{I_1, ..., I_r\}$ en utilisant le quota réservé aux index ($S^I$). Rappelons que deux types d'index sont possibles: (i) les index simples utilisés séparément sur des tables de base ou des vues matérialisées, (ii) les index de jointure définis conjointement sur des tables de base et des vues matérialisées. Pour les index simples, nous pouvons utiliser les techniques d'indexation décrites dans le chapitre 2, comme l'index de projection, l'index binaire, etc. Pour les index de jointure, nous pouvons utiliser les algorithmes de sélection des index de jointure introduits dans le chapitre 3.

En conséquence, nous obtenons une solution initiale pour le problème de distribution statique, qui consiste en un ensemble de vues $V$ et un ensemble d'index $I$. Toutes les requêtes de départ sont donc exécutées en utilisant les deux ensembles ($V$ et $I$). À l'aide d'un modèle de coût, le coût d'évaluation de l'ensemble des requêtes est calculé.

Le principe de notre approche est de reconsidérer itérativement cette solution initiale dans le but de réduire le plus possible le coût d'évaluation des requêtes. Elle
<figure><img src="image_42.png" /><figcaption>FIG. 4.4: L'intuition de notre approche itérative</figcaption></figure>

s'appuie sur deux agents, **l'espion des index** et **l'espion des vues** dont les rôles sont les suivants:

- L'espion des index a pour tâche de voler de l'espace réservé aux vues. L'espace ainsi récupéré sera utilisé pour créer d'autres index et les vues correspondantes seront supprimées. L'opération est validée si le coût total d'exécution des requêtes diminue.

- D'une manière similaire, l'espion des vues a pour tâche de dérober de l'espace réservé aux index afin de créer d'autre vues dans le but de minimiser le coût total d'exécution des requêtes.

Notre algorithme organise donc une sorte de "combat" entre ces deux espions. Ce combat est pour la bonne cause: *la meilleure utilisation de l'espace disque disponible dans l'objectif de minimiser le coût d'évaluation des requêtes.*

L'algorithme s'achève lorsque les deux espions ne peuvent plus réduire le coût total d'exécution des requêtes. À la fin de cet algorithme, nous obtenons deux résultats principaux:

1. Un ensemble de vues matérialisées $V' = \{V'_1, V'_2, ..., V'_{s'}\}$ et un ensemble d'index $I' = \{I'_1, I'_2, ..., I'_{r'}\}$ garantissant un coût minimal d'exécution des requêtes. Ces deux ensembles peuvent être différents des deux ensembles de départ.

2. De nouveaux quotas d'espace pour les vues matérialisées $S^{V'}$ et les index $S^{I'}$ tels que: $S^{V'} \neq S^V$ et $S^{I'} \neq S^I$.

### Un exemple d'illustration

Nous illustrons maintenant notre algorithme par un exemple. Prenons le schéma en étoile de la Figure 2.5 et supposons que nous ayons cinq requêtes fréquentes dont
les graphes sont représentés en Figure 5.1. Les cinq graphes de requêtes représentant les cinq requêtes sont fusionnés en un seul graphe appelé PMEV (voir chapitre 3) [Sel88, YKL97]. Supposons que l’administrateur dispose de 800 Mégabytes et ait affecté **600 Mégabytes** aux vues matérialisées et **200 Mégabytes** aux index.

Premièrement, nous exécutons l’algorithme *sélect_vue* pour sélectionner des vues en utilisant les 600 Mégabytes comme capacité de stockage. Les vues sélectionnées sont $V_1, V_2$ et $V_3$ comme le montre la Table 4.1. Le coût total d’évaluation de l’ensemble de requêtes (en nombre des entrées-sorties) est égal à **4054825**.

<table><caption>TAB. 4.1: Les vues matérialisées sélectionnées et leurs tailles</caption><thead><tr><td>Vues</td><td>Définition de vues</td><td>Tailles (bytes)</td></tr></thead><tbody><tr><td>V<sub>1</sub></td><td>VENTES ⋉ σ<sub>Etat</sub>=‘IL’ CLIENT</td><td>178 094 080</td></tr><tr><td>V<sub>2</sub></td><td>VENTES ⋉ σ<sub>Typepaquet</sub>=‘Bote’ PRODUIT</td><td>324 435 968</td></tr><tr><td>V<sub>3</sub></td><td>σ<sub>Sexe</sub>=‘M’ CLIENT</td><td>89 047 040</td></tr><tr><td>Total</td><td></td><td>591 577 088</td></tr></tbody></table>

Nous construisons ensuite les index (en utilisant les 200 Mégabytes) afin de réduire encore le coût obtenu par la présence des trois vues matérialisées. Les cinq requêtes sont réécrites en fonction de $V_1, V_2, V_3$, et des deux tables de dimensions CLIENT et TEMPS. En exécutant l’algorithme de sélection des index proposé dans le chapitre 3, un index de jointure entre la vue $V_2$ et la table de dimension CLIENT ($V_2 \sim CLIENT$) est sélectionné. La quantité d’espace nécessaire pour cet index est 181821440 bytes (voir chapitre 3). La présence de cet index réduit le coût total d’évaluation des requêtes de **4054825** à **3263405**.

Maintenant, l’espion des index tente de dérober de l’espace attribué aux vues matérialisées afin d’ajouter des index. Puisque la vue $V_3$ est de petite taille et qu’elle est moins utilisée que les autres vues ($V_1$ et $V_2$), son espace (89047040 bytes) est convoité par l’espion des index. L’espace attribué aux index sera donc de 289047040 bytes au total. Après l’élimination de la vue $V_3$, il ne reste plus que $V_1, V_2, CLIENT$ et TEMPS pour exécuter les cinq requêtes. En utilisant un nouvel espace, l’espion des index sélectionne un nouvel index de jointure ($V_1 \sim V_2 \sim TEMPS \sim CLIENT$). Cet index réduit le coût total d’exécution des requêtes de **3263405** à **1955305**.

Finalement, aucun des deux espions ne peut plus obtenir de réduction, d’où la fin de l’algorithme. L’ensemble des vues matérialisées et l’ensemble des index deviennent respectivement $V = \{V_1, V_2\}$ et $I = \{(V_1 \sim V_2 \sim TEMPS \sim CLIENT)\}$. 500 Mégabytes sont attribués aux vues matérialisées et 300 Mégabytes aux index. Le coût total d’exécution de l’ensemble de requêtes est de 1955305 opérations d’entrées-sorties. Le déroulement de cet algorithme est résumé par la Table 4.2.

## 4.4 Le problème de la distribution statique

Dans cette section, nous considérons le problème de distribution d’espace dans le cas statique. Tous les paramètres de l’entrepôt (les vues, les index, les tables de bases, etc.) sont connus a priori et restent inchangés. Pour décrire notre approche, nous
<table><caption>TAB. 4.2: Réduction du coût dû à l'espion des index</caption><thead><tr><th>Etape 1</th><th>Etape 2</th><th>Etape 3</th><th>Etape 4</th><th>Etape 5</th></tr></thead><tbody><tr><td>Sans vues & index</td><td>Avec vues</td><td>Avec vues et index</td><td>Espion des index</td><td>Espion des vues</td></tr><tr><td>68514928</td><td>4054825</td><td>3263405</td><td>1955305</td><td>1955305<br>Algorithme terminé</td></tr></tbody></table>

<figure><img src="image_43.png" /><figcaption>FIG. 4.5: Les éléments de notre algorithme statique et leurs interactions</figcaption></figure>

considérons un entrepôt modélisé par un schéma en étoile. Il est à noter cependant que les solutions proposées peuvent être appliquées à n'importe quel schéma (de type ROLAP ou MOLAP).

### 4.4.1 La formulation du problème

Le problème de distribution de l'espace entre les vues matérialisées et les index est formulé de la manière suivante:

- Soit un entrepôt de données modélisé par un schéma en étoile.

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

- Soit $S$ l'espace disque destiné à stocker les vues matérialisées $V$ et les index $I$, pour supporter l'ensemble des requêtes $Q$.

L'objectif du problème de distribution de l'espace est de répartir l'espace global $S$ entre les vues ($V$) et les index ($I$) afin de minimiser le coût d'évaluation de l'ensemble des requêtes.
### 4.4.2 L'architecture de notre approche

L'architecture de notre approche de distribution de l'espace est présentée dans la Figure 4.4. Les composantes de cette architecture sont: (1) un espion des vues, (2) un espion des index, (3) un contrôle d'admission de vol, (4) un contrôleur d'espion, (5) un algorithme de sélection des vues, (6) un algorithme de sélection des index, et (7) un modèle de coût. Chaque composante a sa propre tâche:

1. **L'espion des vues et l'espion des index:** Comme nous l'avons déjà mentionné, les espions des index et des vues ont pour tâche de dérober l'espace réservé aux vues matérialisées (aux index) afin de créer d'autre(s) index (vues) (voir section 4.3).

2. **Le contrôle d'admission de vol:** Il vérifie que chaque tentative de vol d'un espion (des index ou des vues) contribue à la réduction du coût des requêtes. Cette décision est basée sur un modèle de coût. Pour clarifier le rôle de contrôle d'admission de vol, soient $V$ et $I$ les ensembles des vues et des index déjà sélectionnés. Soit $CT_p$ le coût d'évaluation de l'ensemble de requêtes en présence de $V$ et de $I$ (avant la tentative de vol). Supposons que l'espion des vues tente l'opération de vol et que d'autres vues soient créées. Soient $V'$ le nouvel ensemble de vues et $I'$ le nouvel ensemble des index. Le contrôle d'admission de vol évalue alors le nouveau coût d'exécution des requêtes en présence de $V'$ et de $I'$ qui est noté par $CT_c$. Si ce dernier est inférieur à $CT_p$, la tentative de vol est validée par le contrôle d'admission de vol, sinon elle ne l'est pas.

3. **Le contrôleur d'espion:** Son rôle est d'assurer qu'à chaque moment de l'algorithme, un seul espion est actif.

4. **Un algorithme de sélection des vues:** Il représente l'algorithme de sélection des vues matérialisées utilisé. Dans cette étude, nous utilisons l'algorithme *sélect-vue* présenté dans le chapitre 3.

5. **Un algorithme de sélection des index:** Il représente l'algorithme de sélection des index utilisé. Dans cette étude, nous utilisons les techniques d'indexation présentées dans le chapitre 3.

6. **Le modèle de coût:** Il constitue le coeur de notre approche. Il est utilisé par chacune des composantes et quantifie la solution obtenue. Le modèle de coût décrit dans le chapitre 3 peut être utilisé.

### 4.4.3 Les étapes de notre algorithme

Rappelons que l'algorithme de distribution est basé sur une approche itérative dont les étapes principales sont les suivantes: (1) la détermination d'une solution initiale, (2) le mécanisme d'amélioration de la solution initiale et (3) le test d'arrêt. Dans les sections suivantes, nous décrivons plus en détail chaque étape.

### 4.4.4 La solution initiale

Pour amorcer notre algorithme, nous suivons la sélection séquentielle des vues et des index. Nous estimons (d'une manière uniforme ou aléatoire) les deux quotas
de l'espace des vues matérialisées $S^V$ et l'espace des index $S^I$. Tout d'abord, nous exécutons un algorithme de sélection des vues à matérialiser dirigé par l'espace $S^V$ [YKL97]. Comme résultat, nous obtenons un ensemble de vues $V = \{V_1, V_2, ..., V_m\}$. Ensuite, en utilisant le quota de l'espace réservé aux index, nous sélectionnons un ensemble d'index $I = \{I_1, I_2, ..., I_l\}$ (voir Chapitre 3). Finalement, nous calculons le coût d'évaluation de l'ensemble des requêtes en présence des ensembles de vues (V) et des index (I) noté par $CTER_i$.

### 4.4.5 Le processus d'amélioration de la solution initiale

Pour réaliser cette amélioration, l'algorithme utilise les deux espions décrits précédemment. La tâche des ces espions est contrôlée par les règles suivantes:

**Règle 1:** un espion doit être capable d'utiliser l'espace volé, c'est-à-dire qu'il doit trouver une vue (pour l'espion d'index) ou un index (pour l'espion des vues) à ranger dans l'espace volé.

**Règle 2:** l'espion ne peut voler que si le coût global d'exécution des requêtes est réduit après l'utilisation de l'espace volé.

**Règle 3:** un seul espion est actif à la fois.

#### 4.4.5.1 Les structures utilisées dans notre algorithme

Les structures de données nécessaires à l'algorithme itératif sont deux matrices appelées: *la matrice de réécriture* et *la matrice requête-index*.

La matrice de réécriture $W$ a déjà été définie dans le chapitre précédent (rappe-lons que cette dernière est une représentation du graphe de jointure). Nous ajoutons une autre colonne à cette matrice représentant la fréquence de chaque requête (voir Figure 4.6). Cette matrice sert à identifier les relations de base ou les vues utilisées pour une requête donnée.

Nous attribuons à chaque vue $V_i$ une fréquence d'accès dénotée par $f_{V_i}$ obtenue par la somme des fréquences des requêtes accédant à cette vue (voir équation 4.1):

$$f_{V_i} = \sum_{j=1}^{n} w_{ij} * f_j \quad (4.1)$$

Les victimes potentielles de l'espion des index sont les vues figurant dans cette matrice.

La deuxième matrice, que nous appelons requête-index $RI = \{ri_{lk} | 1 \le l \le n, 1 \le k \le m\}$, est telle que :

$$\mathbf{ri}_{lk} = \begin{cases} 1, & \text{si la requête } Q_l \text{ utilise l'index } I_k \\ 0, & \text{sinon} \end{cases}$$

D'une manière similaire, nous ajoutons une nouvelle colonne pour les fréquences et nous attribuons à chaque index $I_k$ une fréquence d'accès dénotée par $f_{I_k}$, obtenue par la sommation des fréquences des requêtes (voir équation 4.2):

$$f_{I_k} = \sum_{j=1}^{n} ri_{kj} * f_j \quad (4.2)$$
Les victimes potentielles de l'espion des vues sont les index figurant dans cette
matrice.

Notre algorithme utilise deux procédures: espion-index-vol-espace-vue et espion-vue-vol-espace-index, que nous décrivons dans les sections qui suivent.

**Procédure espion-index-vol-espace-vue** Comme son nom l'indique, cette procédure décrit la tâche de l'espion des index. Elle présente en entrée les éléments suivants:

- Un ensemble de requêtes d'interrogation;

- Un ensemble de vues matérialisées $V = \{V_1, V_2, ..., V_l\}$ et un ensemble d'index $I = \{I_1, I_2, ..., I_m\}$, obtenus par la solution initiale;

- Les deux quotas de stockage $S^V$ (pour les vues) et $S^I$ (pour les index).

Comme sortie, cette procédure génère un ensemble d'index $I' = \{I'_1, I'_2, ..., I'_{m'}\}$ qui peut être soit identique à l'ensemble initial $I$ soit différent et plus intéressant en termes de réduction du coût des requêtes.

Pour identifier les victimes des vues matérialisées, l'espion des index doit avoir une politique de sélection de vue à éliminer pour créer de nouveaux index en garantissant une bonne performance. Nous suggérons deux politiques: la **Vue la Moins Fréquemment Utilisée (VMFU)** et la **Vue de plus Petite Taille (VPPT)**.

- **La VMFU:** l'espion des index doit sélectionner la vue la moins fréquemment utilisée. Cette vue est celle qui contribue le moins à l'amélioration du coût d'exécution des requêtes.

- **La VPPT:** l'espion des index doit sélectionner la vue ayant la petite taille. En effet, la taille des vues étant en moyenne plus grande que la taille des index, une petite vue pourra être remplacée par un index.

Une fois la vue victime éliminée, les requêtes de départ doivent être réécrites en fonction des vues restantes. D'où la mise à jour de la matrice de réécriture.

**Exemple 17** Cet exemple illustre le fonctionnement de l'espion des index. Supposons que nous ayons trois vues matérialisées $V_1, V_2$ et $V_3$ comme dans l'exemple d'illustration occupant 600 Mégabytes et un index ($V_2 \sim CLIENT$). À partir de ces vues et index, nous construisons la matrice de réécriture $W$ (voir Figure 4.6). La fréquence d'accès de chaque vue $V_i$ ($1 \le i \le 3$) est calculée: $f_{V_1} = 30, f_{V_2} = 25$ et $f_{V_3} = 20$.

Étant donné que l'espion des index élimine la vue $V_3$ qui est la moins fréquente, la matrice de réécriture doit être modifiée de la manière suivante: la vue $V_3$ est remplacée par la table de dimension CLIENT comme le montre la Figure 4.7.

### 4.4.5.2 Algorithme de l'espion des index

La description détaillée de la tâche de l'espion des index est donnée dans l'algorithme 7.
<figure><img src="image_44.png" /><figcaption>FIG. 4.6: La matrice de réécriture initiale</figcaption></figure>

<figure><img src="image_45.png" /><figcaption>FIG. 4.7: La matrice de réécriture après l'exécution de l'espion des index</figcaption></figure>

**Algorithmme 7** La procédure espion-index-vol-espace-vue

1: Calculer le coût global $G_i$ d'évaluation des requêtes en utilisant les vues et les index

2: Sélectionner une vue $V_i$ en utilisant une stratégie parmi VMFU ou VPT

3: $S^I = S^I + \text{espace}(V_i) + \text{l'espace inutilisé}$

4: $S^V = S^V - \text{espace}(V_i)$

5: Éliminer la vue $V_i$

6: Mettre à jour la matrice de réécriture $W$

7: Exécuter ASI (on obtient un nouvel ensemble d'index)

8: Calculer le coût global $G_c$ d'évaluation des requêtes en utilisant le nouvel ensemble des index et les vues matérialisées restantes

9: **if** ($G_c < G_i$) **then**

10: Mettre à jour la matrice requête-index $RI$

11: **else**

12: Restaurer la vue éliminée

13: Rétablir $S^V$, $S^I$ et $G_c$ à leur valeurs précédentes

14: Rétablir la matrice $W$ à son état précédent

15: **end if**
**Procédure espion-vues-vol-espace-index** Cette procédure fonctionne comme celle de l'espion des index. Elle possède les mêmes entrées que la procédure espion-index-vol-espace-vue. Comme sortie, elle génère un ensemble de vues $V' = \{V'_1, V'_2, ..., V'_{|V'|}\}$ qui peut être soit identique à l'ensemble initial $V$ soit plus intéressant par rapport à $V$ en termes de réduction de coût des requêtes.

Pour sélectionner les victimes, l'espion des vues possède deux stratégies: **l'Index le Moins Fréquemment Utilisé (IMFU)** et **le Plus Grand Index (PGI)**.

- **L'IMFU:** l'espion des vues doit sélectionner l'index le moins fréquemment utilisé. Cet index est celui qui contribue le moins à la réduction du coût d'exécution des requêtes.

- **La PGI:** Le plus grand index est sélectionné parce que la taille des vues est en moyenne plus grande que la taille des index. En effet, un index de petite taille ne présente pas en général suffisamment d'espace pour stocker une nouvelle vue.

### 4.4.5.3 Algorithme de l'espion des vues

Les étapes principales de l'espion des vues sont illustrées par l'algorithme 8.

<table><caption>**Algorithme 8** La procédure espion-vues-vol-espace-index</caption><tr><td>1:</td><td>Calculer le coût global $G_i$ d'évaluation des requêtes en utilisant les vues et les index</td></tr><tr><td>2:</td><td>Sélectionner un index $I_i$ en utilisant une stratégie parmi IMFU ou PGI</td></tr><tr><td>3:</td><td>$S^V = S^V + \text{espace}(I_i) + \text{espace inutilisé}$</td></tr><tr><td>4:</td><td>$S^I = S^I - \text{space}(I_i)$</td></tr><tr><td>5:</td><td>Éliminer $I_i$</td></tr><tr><td>6:</td><td>Mettre à jour la matrice RI</td></tr><tr><td>7:</td><td>Exécuter Select_Vues (il fournit un nouvel ensemble de vues matérialisées)</td></tr><tr><td>8:</td><td>Exécuter l'algorithme ASI</td></tr><tr><td>9:</td><td>Calculer le coût global $G_c$ d'évaluation des requêtes en utilisant le nouvel ensemble des index et les vues matérialisées</td></tr><tr><td>10:</td><td>if ($G_c < G_i$) then</td></tr><tr><td>11:</td><td>Mettre à jour les deux matrices W et RI</td></tr><tr><td>12:</td><td>else</td></tr><tr><td>13:</td><td>Restaurer l'index éliminé</td></tr><tr><td>14:</td><td>Rétablir $S^V$, $S^I$ et $G_c$ à leur valeurs précédentes</td></tr><tr><td>15:</td><td>Rétablir la matrice RI à son état précédent</td></tr><tr><td>16:</td><td>end if</td></tr></table>
### 4.4.6 Le test d'arrêt

Nous exécutons ces deux procédures jusqu'à ce qu'aucune réduction du coût global d'évaluation de l'ensemble de requêtes ne soit constatée.

### 4.4.7 La détermination de l'espion privilégié

L'objectif principal de notre algorithme est d'améliorer la solution initiale obtenue par l'estimation de l'espace. Notons que nous possédons deux espions, chacun ayant le droit de commencer son vol. Cependant, ils ne peuvent pas commencer simultanément (voir la règle 3). Un espion doit donc recevoir le privilège de commencer le vol. Reste à identifier cet espion, car cette identification peut avoir des effets importants sur la qualité de la solution obtenue par notre algorithme.

Pour réaliser la tâche d'identification, nous suggérons un critère de sélection basé sur la notion de *contribution de chaque espion* définie par la suite dans cette section.

Soient $CT_s$, $CT_v$ et $CT_i$ le coût total d'évaluation de l'ensemble des requêtes de départ sans les vues et les index, en présence seulement des vues, ou en présence seulement des index.

Nous définissons la *contribution de l'espion des vues* $cont(V)$ par l'équation 4.3:

$$cont(V) = CT_s - CT_v \quad (4.3)$$

Elle nous donne la réduction du coût d'évaluation des requêtes obtenue par la sélection des vues matérialisées. D'une manière similaire, nous définissons la *contribution de l'espion des index* $cont(I)$ par l'équation 4.4:

$$cont(I) = CT_s - CT_i \quad (4.4)$$

Cette contribution nous offre une réduction du coût d'évaluation des requêtes obtenue par la sélection des index.

En utilisant ces deux contributions, nous définissons l'espion à privilégier comme l'espion ayant la plus grande contribution. Plus formellement, il est défini de la manière suivante:

$$\text{l'espion à privilégier} = \begin{cases} \text{l'espion des vues si } cont(V) < cont(I) \\ \text{l'espion des index, sinon} \end{cases}$$

En cas d'égalité des contributions, nous sélectionnons un espion au hasard.

### 4.4.8 Description de l'algorithmme

Maintenant, nous avons tous les ingrédients pour définir l'algorithmme itératif distribuant l'espace entre les vues et les index. Il commence par la recherche d'une solution initiale. Une fois cette solution trouvée, il construit les deux matrices $W$ et $RI$. En fonction de la contribution de chaque espion, l'algorithmme active l'espion privilégié suivi par l'autre espion. Le processus d'activation des espions est répété
jusqu'à ce qu'aucune réduction au niveau du coût total d'évaluation des requêtes ne soit plus constatée.

Les étapes principales de notre approche sont décrites dans l'algorithmme 9.

**Algorithmme 9** Algorithme statique

1: Initialisation: les deux matrice (W et RI) sont initialisées à zéro

2: Exécuter Select_Vues en respectant la contrainte d'espace $S^V$.

3: Construire la matrice W en fonction de l'ensemble des vues sélectionnées

4: Exécuter ASI en respectant la contrainte d'espace $S^I$

5: Construire la matrice RI en fonction de l'ensemble des index sélectionnés

6: Activer espion-index-vol-espace-vues et espion-vues-vol-espace-index (le choix dépend de leurs contributions respectives)

7: Répéter l'étape 6 jusqu'à ce qu'aucune réduction du coût total d'évaluation des requêtes ne soit constatée

Notre algorithme se termine parce qu'il est contrôlé par un modèle de coût.

### 4.4.9 Les caractéristiques de notre approche

Dans un entrepôt de données, le processus de traitement des requêtes possède plusieurs modules en relation; citons par exemple, des algorithmes de sélection des vues et des index, la réécriture des requêtes en fonction des vues, des algorithmes de maintenance des vues et des index, etc. L'algorithme que nous proposons ne remet pas en cause les modules existants d'un entrepôt, mais il peut les utiliser comme des primitives. Pour éclairer ce point, soient A et B deux algorithmes, le premier dédié à la sélection des vues et le deuxième à la sélection des index. Notre algorithme de distribution C se présente d'abord comme une "procédure maître" pouvant utiliser ces deux algorithmes (Figure 4.4).

De plus, notre méthodologie donne une certaine flexibilité à l'administrateur dans le choix d'un espion (des index ou des vues) pour la conception de son entrepôt. Dans cette optique, l'administrateur, selon son besoin, pourra attribuer plus d'espace aux index ou aux vues matérialisées.

## 4.5 La problème de la distribution dynamique

Dans la section précédente, nous avons étudié le problème de distribution de l'espace dans le contexte statique. Dans cette section, nous traitons ce problème dans le cas dynamique en adaptant l'algorithme statique.

### 4.5.1 Position du problème

Rappelons que les entrepôts sont construits en collectant les informations de plusieurs sources et en les intégrant dans une seule base de données. Les entrepôts
sont volumineux pour des applications fonctionnant dans des environnements de
grande échelle composées de multiples sources hétérogènes, tel que le Web. De tels
environnements sont souvent marqués par des changements dynamiques au niveau
des sources d'informations, modifiant non seulement les contenus des données, mais
également leurs schémas et leurs capacités de requêtes. Ces changements peuvent
provoquer des modifications des vues et des index définis sur l'entrepôt.

Les changements dynamiques sur les vues peuvent être classés en trois catégories :

1. Des changements au niveau des relations de base (ajout/suppression de nouveaux n-uplets) qui seront ensuite répercutés sur les vues matérialisées (cf. le problème de maintenance des vues: chapitre 2).

2. Des changements au niveau de la définition des vues: Notons que les exigences des utilisateurs de l'entrepôt changent dans le temps; elles peuvent entraîner des modifications au niveau de la définition des vues d'une manière dynamique. Dans ces applications, les utilisateurs changent les définitions des vues d'une manière dynamique et veulent voir ces changements se refléter dans le résultat de leurs requêtes.

Un autre cas entraînant un changement dans la définition des vues est celui où une relation d'un système distribué est fragmentée et/ou la localisation physique des données change; la définition des vues doit changer pour fournir l'indépendance logique des données.

Les changements de définition d'une vue peuvent être très coûteux, surtout si la vue implique des données de sources multiples. Plusieurs travaux ont considéré le problème d'adaptation des vues existantes pour répercuter les changements au niveau des vues [Bel98].

3. Changements dus à l'évolution du schéma

4. **Changements au niveau des requêtes:** Certaines requêtes peuvent être supprimées, d'autres ajoutées. Les fréquences peuvent changer. Puisque le PSV est basé sur un ensemble donné de requêtes, ces changements entraînent la sélection d'autres vues.

Quelle que soit la nature du changement, il peut avoir une forte incidence sur l'en-
semble des vues et des index. Une vue après la maintenance peut occuper plus ou
moins d'espace par rapport à son espace initial. Ceci est valable également pour
les index. La contrainte d'espace risque de ne plus être respectée. Si l'espace total
occupé par les vues et les index est plus grand (respectivement plus petit) que l'es-
pace demandé, il est nécessaire de déterminer quelle vue ou quel index doit être
éliminé (ou ajouté) <fnref n="1" />. Notre approche itérative peut facilement être adaptée pour
traiter ce problème en ajustant les espaces réservés aux vues et aux index. Dans
la section suivante, nous décrivons les étapes de l'algorithme que nous appelons
répartition_dynamique.

<footnote n="1">¹Notre approche ne prend pas en considération le coût de création et de suppression d'une vue et d'un index. Car notre objectif principal est de satisfaire la contrainte de l'espace. Il serait cependant intéressant de combiner la contrainte de l'espace et la contrainte du coût de calcul pour le problème de redistribution de l'espace entre les vues et les index.</footnote>
### 4.5.2 L'algorithme répartition_dynamique

Soient $S_i^V$ et $S_i^I$ les espaces occupés par les vues et les index avant les opérations de mise à jour. Après ces dernières, l'ensemble des vues matérialisées $V$ et l'ensemble des index $I$ occupent de nouveaux quotas d'espace nommés $S_c^V$ et $S_c^I$, respectivement. Soit $S_i (= S_i^V + S_i^I)$ et $S_c (= S_c^V + S_c^I)$ les espaces totaux avant et après les opérations de mises à jour. Notre algorithme exécute les étapes suivantes pour redistribuer et gérer les nouveaux quotas d'espace:

1. Calculer les nouveaux quotas de l'espace disque occupé par les vues ($S_c^V$) et les index ($S_c^I$)

2. Si l'espace total $S_c$ diminue (en cas d'opération de suppression par exemple), nous aurons de l'espace non utilisé qui pourrait être utilisé par les vues, les index ou les deux. Dans le cas où cet espace est utilisé pour la sélection d'autres vues, l'algorithme cherche des vues appartenant à la couche des vues potentielles (voir chapitre 3) et ayant un bénéfice supérieur à $\alpha$ (voir Section 3.3). Dans le cas où cet espace est utilisé pour sélectionner d'autres index, l'algorithme cherche à les sélectionner d'une manière incrémentale en utilisant l'algorithme AGSK (voir chapitre 3).

3. Si l'espace global $S_c$ augmente (en cas de création par exemple) et devient plus grand que l'espace initial $S_i$, il faut libérer de l'espace. On peut considérer différents cas:

- **Augmentation de la taille des vues seulement:** Si l'espace des vues $S_c^V$ dépasse son quota initial ($S_i^V$), nous devons donc éliminer certaine(s) vues afin de satisfaire la contrainte d'espace. Mais avant d'entamer le processus d'élimination, nous devons tester si l'espion des vues peut voler de l'espace réservé aux index et garder ces vues (si ces vues contribuent fortement à réduction du coût total des requêtes). Si la tentative de vol de l'espion des vues échoue, nous éliminons certaines vues en utilisant une politique parmi VMFU et VPPT.

- **Augmentation de la taille des index seulement:** Si l'espace des index $S_c^I$ dépasse son quota initial ($S_i^I$), comme dans le cas précédent, nous testons si l'espion des index peut voler de l'espace réservé aux vues et garder ces index. Si cette tentative échoue, nous éliminons les index en utilisant une politique parmi IMFU et PGI.

- **Augmentation de la taille des vues et les index:** Si les deux espaces sont plus grands que leurs espaces d'origine, nous éliminons des vues et des index en utilisant les politiques des vues et des index jusqu'à ce que la contrainte d'espace soit satisfaite.

## 4.6 Evaluation

Notre expérimentation utilise le schéma en étoile de la Figure 2.5. Nous supposons que la taille de la page est de 8192 bytes et que la taille du pointeur de bloc est de
<figure><img src="image_46.png" /><figcaption>FIG. 4.8: Le PMEV pour les requêtes: $Q_1$, $Q_2$ and $Q_3$</figcaption></figure>

8 bytes comme dans [DRT99]. À partir de ces informations et des cardinalités de chaque table, nous pouvons facilement calculer la taille de chaque table. Pour évaluer notre algorithme, nous utilisons deux ensembles de requêtes: le premier est l'ensemble des cinq requêtes {$Q_1, Q_2, Q_3, Q_4, Q_5$} (Figure 5.1) et le deuxième est l'ensemble des trois premières requêtes {$Q_1, Q_2, Q_3$}. Les PMEVs, pour le premier et le deuxième ensemble de requêtes sont illustrés par les Figures 3.8 et 4.8, respectivement. Pour le premier ensemble, la capacité de stockage $S^V = 600$ Mégabytes pour les vues matérialisées et $S^I = 200$ Mégabytes pour les index. Pour le deuxième ensemble, ces valeurs sont: $S^V = 200$ Mégabytes and $S^I = 600$ Mégabytes, respectivement.

<table><caption>TAB. 4.3: La description des solutions pour les cinq requêtes</caption><thead><tr><th>Solution</th><th>Vue & Index</th><th>CT</th><th>S<sup>V</sup></th><th>S<sup>I</sup></th></tr></thead><tbody><tr><td>Solution initiale</td><td>Sans vue & index</td><td>68514928</td><td>0</td><td>0</td></tr><tr><td>Avec vues</td><td>V<sub>1</sub>: VENTES ⋧ σ<sub>Etat='IL'</sub> CLIENT<br>V<sub>2</sub>: VENTES ⋧ σ<sub>Typepaquet='Bote'</sub> PRODUIT<br>V<sub>3</sub>: σ<sub>Sexe='M'</sub> CLIENT</td><td>4054825</td><td>600</td><td>0</td></tr><tr><td>avec vues et index</td><td>V<sub>1</sub>, V<sub>2</sub>, V<sub>3</sub> & I<sub>1</sub> (V<sub>2</sub> ~ V<sub>3</sub>)</td><td>3263405</td><td>600</td><td>200</td></tr><tr><td>Espion des vues</td><td></td><td>3263405</td><td>600</td><td>200</td></tr><tr><td>Espion des index</td><td>V<sub>1</sub> ~ V<sub>2</sub> ~ TEMPS ~ CLIENT</td><td>1955305</td><td>500</td><td>300</td></tr></tbody></table>

<table><caption>TAB. 4.4: La description des solutions pour les trois requêtes</caption><thead><tr><th>Solution</th><th>Vues et index</th><th>CT</th><th>S<sup>V</sup></th><th>S<sup>I</sup></th></tr></thead><tbody><tr><td>Solution initiale</td><td>Sans vue et index</td><td>37371780</td><td>0</td><td>0</td></tr><tr><td>Avec vue</td><td>V<sub>1</sub>: VENTES ⋧ σ<sub>Etat='IL'</sub> CLIENT</td><td>12892060</td><td>178</td><td>0</td></tr><tr><td>Avec vues et index</td><td></td><td>12892060</td><td>178</td><td>600</td></tr><tr><td>Espion des vues</td><td>V<sub>2</sub>: VENTES ⋧ σ<sub>Mois="Mars"</sub> TEMPS</td><td>2017640</td><td>345</td><td>433</td></tr><tr><td>Espion des vues</td><td>V<sub>3</sub>: VENTES ⋧ σ<sub>Typepaquet='Bote'</sub> PRODUIT</td><td>1274237</td><td>667</td><td>109</td></tr></tbody></table>
<figure><img src="image_47.png" /><figcaption>FIG. 4.9: Les effets des espions dans le cas des cinq requêtes</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>FIG. 4.10: Les effets des espions dans le cas des trois requêtes</figcaption></figure>

Pour les deux ensembles de requêtes, le coût d'évaluation des requêtes est d'abord calculé sans considérer les vues et les index (avec la technique de hachage). Nous sélectionnons un ensemble de vues en utilisant l'algorithme *sélect-vue*. Ces vues réduisent d'une manière significative le coût initial obtenu par la technique de hachage (Figure 4.9). Ensuite, nous sélectionnons des index réduisant le coût. Une fois la solution initiale obtenue, nous activons l'espion des vues car il présente une plus grande contribution que l'espion des index. Cet espion échoue dans la réduction du coût des requêtes (Figure 4.9). L'espion des index est alors activé et réduit le coût des requêtes. Les vues sélectionnées sont: $V_1$ et $V_2$, et l'index sélectionné est ($V_1 \sim V_2 \sim TEMPS \sim CLIENT$) (voir Table 4.3).

Dans la Table 4.4, nous présentons les résultats de notre algorithme pour le deuxième ensemble de requêtes. Nous constatons que le quota réservé aux index (600MB) n'est pas suffisant pour sélectionner des index. En conséquence, cet espace est utilisé par l'espion des vues qui sélectionne deux autres vues.

Dans cet exemple, nous pouvons faire l'observation suivante: l'approche espion
<figure><img src="image_49.png" /><figcaption>FIG. 4.11: La distribution d'espace pour les cinq requêtes</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>FIG. 4.12: La distribution d'espace pour les trois requêtes</figcaption></figure>

contre espion distribue l'espace avec l'objectif de minimiser le coût d'évaluation des requêtes. Dans les deux cas, nous constatons une réduction significative du coût des requêtes. Nous notons que dans cette évaluation, le coût total d'évaluation des requêtes en utilisant la solution initiale (c'est-à-dire, sans l'application de notre approche) est trois fois plus coûteuse dans le cas des cinq requêtes et dix fois plus coûteuse dans le cas des trois requêtes. On constate aussi que pour les cinq requêtes l'espion des index **réduit** davantage le coût que l'espion des vues. Dans ce cas, l'espion des index vole 100 Mégabytes sur les 600 alloués aux vues matérialisées (Figure 4.11). Mais pour les trois requêtes, l'espion des vues **réduit** davantage le coût que l'espion des index. Dans ce cas, l'espion des vues vole 491 Mégabytes d'espace des 600 Mégabytes alloués aux index (Figure 4.12). On peut donc considérer que notre approche contribue effectivement à une meilleure distribution de l'espace disponible entre les vues et les index afin de réduire le coût total d'évaluation des requêtes.

Nous évaluons maintenant notre approche itérative dans le cas dynamique. Supposons que 500 000 nouveaux n-uplets soient ajoutés à la table des faits. Ils doivent être propagés dans les vues matérialisées et les index obtenus par l'algorithme statique (Table 4.3). Nous supposons que 40% de ces n-uplets sont propagés dans la vue $V_1$ (VENTES ⋉ $\sigma_{Etat=IL'}$ CLIENT) et la vue $V_2$ (VENTES ⋉ $\sigma_{TypePAQUET=\text{Bote}'}$ PRODUIT). Après ces mises à jour, l'espace total occupé par les vues et les index est de 860 Mégabytes et la contrainte de stockage est violée. Il est nécessaire de redistribuer l'espace entre les vues et les index. Puisque les deux vues matérialisées contribuent le plus à la réduction du coût d'évaluation des cinq requêtes, l'espion des vues essaye d'abord de voler de l'espace aux index pour garder ces vues. Il n'existe qu'un seul index défini sur les vues $V_1$ and $V_2$ et les deux tables de dimension CLIENT et TEMPS. L'espion des vues s'attribue donc l'espace alloué à cet index et sélectionne une nouvelle vue $V_3$ ($\sigma_{Sexe=M'}$ CLIENT). Ces trois vues $V_1, V_2, V_3$ occupent maintenant 620 Mégabytes et il reste 180 Mégabytes. L'espion des index intervient donc en éliminant la vue $V_3$ et en récupérant l'espace disponible. Il provoque la création de l'index: ($V_2 \sim$ TEMPS $\sim$ CLIENT) qui réduit d'une manière significative le coût total des requêtes.
<table><caption>TAB. 4.5: Les vues sélectionnées et leurs tailles pour les cinq requêtes après mises à jour</caption><thead><tr><th>Solution</th><th>Vues et index</th><th>CT</th><th>S<sup>V</sup></th><th>S<sup>I</sup></th></tr></thead><tbody><tr><td>Solution statique</td><td>V<sub>1</sub>, V<sub>2</sub> &amp; (V<sub>1</sub> ~ V<sub>2</sub> ~ TEMPS ~ CLIENT)</td><td>1955305</td><td>500</td><td>300</td></tr><tr><td>Après mise à jour</td><td>V<sub>1</sub>, V<sub>2</sub> &amp; (V<sub>1</sub> ~ V<sub>2</sub> ~ TEMPS ~ CLIENT)</td><td>2022680</td><td>540</td><td>320</td></tr><tr><td>Espion des vues</td><td>V<sub>1</sub>, V<sub>2</sub> and V<sub>3</sub></td><td>4848146</td><td>800</td><td>0</td></tr><tr><td>Espion des index</td><td>V<sub>1</sub>, V<sub>2</sub> &amp; (V<sub>2</sub> ~ TEMPS ~ CLIENT)</td><td>2478150</td><td>550</td><td>250</td></tr></tbody></table>

## 4.7 Conclusion et perspectives

La conception physique des entrepôts de données est très importante pour l'efficacité des requêtes. Deux techniques ont été proposées dans la littérature pour assurer cette efficacité: les vues matérialisées et les index. Ces deux structures sont interdépendantes et contribuent au même objectif: réduire le coût d'évaluation des requêtes. Pour exploiter ces deux techniques, le concepteur de l'entrepôt doit successivement (1) réserver un espace aux vues et (2) réserver un espace aux index. Cette approche ignore complètement les effets d'interaction entre les vues et les index. Dans la littérature cette réservation n'est pas automatisée.

Dans ce chapitre, nous avons développé une nouvelle méthodologie de la distribution automatique de l'espace entre les vues et les index dans les contextes statique et dynamique en prenant en considération l'interaction entre les vues et les index. Cette méthodologie est basée sur une approche itérative. Elle commence par une sélection initiale des vues et des index, puis essaye d'améliorer cette dernière en utilisant deux algorithmes gloutons (espion des index et espion des vues).

Finalement, nous avons évalué notre approche en utilisant un schéma en étoile emprunté à Informix [Cor97b]. Les résultats ont montré que notre approche réduit d'une manière significative le coût total d'évaluation des requêtes. Dans certains cas, c'est l'espion des vues qui contribue le plus et dans d'autres, c'est l'espion des index. Cela démontre l'intérêt d'opposer les deux espions. Cependant, l'administrateur de l'entrepôt peut privilégier les vues matérialisées en exécutant seulement l'espion des vues, ou privilégier les index en exécutant seulement l'espion des index. Ainsi, cette approche peut conduire à plusieurs stratégies de conception d'un entrepôt.

Pour identifier les victimes (vues ou index à éliminer) notre algorithme utilise quatre politiques différentes basées sur la fréquence (la vue la moins fréquemment utilisée, l'index le moins fréquemment utilisé) et la taille (la vue de plus petite taille, l'index de plus grande taille). Il serait intéressant de considérer d'autres politiques en se basant sur des critères de coût (en éliminant les vues ou les index qui contribuent le moins dans la réduction du coût d'évaluation des requêtes).
# Chapitre 5

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

L'une des caractéristiques principales des entrepôts de données est leur grande taille. Cette dernière est à l'origine de contre-performance dans l'exécution des requêtes. Par exemple, Jagadish et al. [JMS95] citent le cas d'une grande compagnie de télécommunication qui collecte 75 GB de données d'appels téléphoniques chaque jour (ce qui représente 27 TB par an)! Nous avons vu dans les chapitres précédents que les vues matérialisées et les index jouent un rôle très important dans la réduction du temps d'exécution des requêtes décisionnelles. Leurs tailles peuvent être importantes et leur stockage sur mémoire secondaire et leur maintenance posent des problèmes délicats. Pour exécuter des requêtes décisionnelles, les vues et les index doivent être chargés en mémoire centrale; opération qui peut être très coûteuse.

La fragmentation horizontale semble être une réponse à ce problème. En effet elle a été introduite dans les bases de données réparties dans le but de minimiser le nombre d'entrées-sorties (ou le coût de transfert de données) pendant l'exécution des requêtes [KNM94, OV91, NR89]. Malheureusement, elle n'a pas reçu une grande attention de la part des chercheurs dans le contexte des entrepôts des données. Récemment, *Oracle8i* a introduit le concept de fragmentation horizontale de la table des faits, des vues matérialisées et des index [Ora99] et a démontré son intérêt. Notons au passage que le benchmark de Transaction Processing Concil (TPC-H), dans ses règles d'implémentation, n'autorise pas l'utilisation de la fragmentation verticale, mais accepte l'utilisation de la fragmentation horizontale.

Le partitionnement peut être utilisé à différents niveaux dans les entrepôts de données ou les très grandes bases de données pour permettre diverses améliorations dans les performances:

- On peut définir des vues matérialisées et des index sur des partitions et non pas sur la totalité de la base de données ou de l'entrepôt; chaque partition est gérée indépendamment des autres,

- On peut éliminer les partitions non valides pour réduire le temps de maintenance et d'interrogation. Admettons par exemple que la table des faits VENTES de la Figure 2.5 soit partitionnée en mois (12 partitions). Pour exécuter une requête demandant des informations sur les trois derniers mois, il
est possible d'éliminer 9 partitions,

- On peut améliorer les performances en utilisant la technique du "striping" [WLDH96]. Cette technique consiste à répartir les fragments de données sur des disques différents, ce qui permet de réduire les déplacements des têtes, et de réaliser plusieurs opérations de lecture ou d'écriture en parallèle. On peut, par exemple utiliser 5 disques de 200 MB pour obtenir un volume de 1 GB. Les performances du système à 5 disques seront, on le comprend aisément, supérieures à celles d'un disque monobloc. Par contre, la fiabilité de l'ensemble n'est pas améliorée puisqu'il faut que l'ensemble des 5 disques soit opérationnel en permanence. La défaillance d'un seul disque met le système en panne,

- Il est possible de tirer partie de la fragmentation pour concevoir des architectures efficaces d'entrepôts répartis [NB99]. Les fragments peuvent être répartis judicieusement sur des sites différents pour réduire le nombre d'accès aux données non pertinentes et les transferts de données [KNM94],

- Un outil de conception des data marts à partir d'un entrepôt de données.

Dans ce chapitre, nous répondons à la question suivante: que peut apporter la fragmentation horizontale aux entrepôts de données en terme de réduction du temps d'exécution des requêtes et à la conception des data marts?

## 5.1 Position du problème

La fragmentation contribue considérablement à la performance des entrepôts de données en rendant plus efficace les vues matérialisées, les index, les jointures, le parallélisme. Nous explicitons ci-après ces différents points.

- **Les vues matérialisées:** étant donné que les vues matérialisées sont stockées sous forme de relations de grandes tailles, il est intéressant de les fragmenter pour garantir les caractéristiques suivantes:

1. Faciliter le processus d'adaptation des vues (maintenir un fragment d'une vue est plus facile que maintenir la totalité de la vue [BM00]).

2. Réduire le coût d'exécution des requêtes en minimisant le nombre d'entrées-sorties.

3. Rendre les vues auto-maintenables [BM00].

La fragmentation des vues matérialisées peut être réalisée de deux façons différentes: directe et indirecte.

1. **La fragmentation directe:** Dans ce cas, ce ne sont pas les tables du schéma de l'entrepôt qui sont fragmentées, mais les vues matérialisées définies sur ce schéma. Cette approche a été développée par Bellahsène et al. [BM00] dans l'objectif de rendre les vues auto-maintenables en cas de modification des données.

2. **La fragmentation indirecte:** Dans ce cas, les tables du schéma sont supposées fragmentées. En conséquence, on a plusieurs sous-schémas sur chacun
des sous-schémas, des vues matérialisées peuvent être sélectionnées (en
utilisant les mêmes algorithmes décrits dans le chapitre 2).

- **Les index**: même en utilisant des index appropriés, le nombre de données non pertinentes explorées lors de l'exécution d'une requête reste très grand. Construire, par exemple, des index de jointure sur la totalité du schéma de l'entrepôt pose un problème de performance, car, à chaque exécution de requête, l'index doit être transféré en mémoire. Par contre, si l'entrepôt est partitionné, on peut construire des index pour chaque partition. Ces index, plus petits, sont plus faciles à maintenir et à charger.

- **Les jointures**: étant donné que les requêtes décisionnelles requièrent presque systématiquement des jointures entre les tables de dimensions et la table de faits, la fragmentation horizontale dérivée [CNP82] peut être utilisée pour accélérer ces jointures en éliminant les jointures inutiles.

- **Le parallélisme**: d'une manière générale le parallélisme est une bonne technique pour accélérer l'exécution des requêtes. Avec l'utilisation de la fragmentation horizontale, nous pouvons affecter les fragments horizontaux à différents processeurs et exécuter les requêtes en parallèle. Par exemple, MCI Telecommunications'IT (le Colorado Springs) a déployé un entrepôt de 2TB appelé waterhouseMCI sur une machine parallèle de 104 noeuds (de type IBM RS/6000 SP). La base de données est en croissance de 100 GB à 200 GB par mois [D.96].

La difficulté majeure de la fragmentation horizontale dans les bases de données est sa contre-performance due aux opérations de mise à jour. Lorsqu'une opération de mise à jour intervient sur une relation (fragmentée) du schéma global, elle se traduit par plusieurs sous-opérations de mise à jour dans différents fragments. Pour exécuter cette opération, il faut d'abord identifier les fragments concernés par cette opération, puis l'exécuter sur les fragments identifiés. Après l'opération de mise à jour, certains n-uplets doivent changer de fragment (ce que nous appelons la migration de n-uplets). Cette migration de n-uplets peut être une opération coûteuse.

Pour l'illustrer, prenons l'exemple d'une relation EMPLOYE qui est partitionnée en fonction de l'attribut Salaire, en deux fragments: Emp_1 et Emp_2, caractérisés par:

Emp_1: $\sigma_{Salaire \le 7000}$ (EMPLOYE)

Emp_2: $\sigma_{Salaire > 7000}$ (EMPLOYE)

Considérons un employé touchant un salaire de 6 500 FF (il appartiendrait donc au fragment Emp_1). Après une augmentation de 10% des salaires, le salaire de cet employé s'élève à 7 150 FF. Il doit donc changer de fragment.

Cependant, les problèmes de performance de mise à jour sont moins importants dans les entrepôts que dans les bases de données, pour les raisons suivantes:

1. Dans les entrepôts, la table des faits reflète l'aspect dynamique de l'entrepôt [Kim97], et la plupart des opérations de mises à jour se font au niveau de cette table. Les opérations de mise à jour dans les entrepôts sont de type *ajout* (append) de n-uplets. Si nous nous intéressons à une table des faits VENTES d'un magasin comme Carrefour, par exemple, cette table est mise à jour après
chaque achat.

L'ajout est donc l'opération la plus fréquente. La modification et la suppression peuvent intervenir également essentiellement au niveau des tables de dimensions [HMA99]: départ d'un client, changement d'adresse d'un client, arrivée d'un nouveau produit.

2. Même si les opérations de mise à jour sont nombreuses, elles sont effectuées lorsque l'entrepôt est off-line [OQ97].

Dans ce chapitre, nous proposons une méthodologie pour la fragmentation horizontale dans les entrepôts de données modélisés par un schéma en étoile. Cette méthodologie va nous permettre de dégager les problèmes liés à cette technique. Nous aborderons ensuite la partie algorithmique. L'objectif est d'élaborer un algorithme de fragmentation qui pourra fournir un bon schéma de fragmentation.

Ce chapitre est organisé comme suit:

- Dans la section 5.2, nous montrons par un exemple le rôle de la fragmentation horizontale dans la réduction du coût d'exécution des requêtes. Cet exemple, va nous permettre de dégager les principes du processus de fragmentation dans les entrepôts de données.

- Dans la section 5.3, nous décrivons notre méthodologie de fragmentation des tables de dimensions et de la table des faits.

- Dans la section 5.4, nous montrons le rôle des tables de dimensions dans la fragmentation de la table des faits. Nous développons un algorithme glouton afin de sélectionner les *meilleures tables de dimensions* pour la fragmentation de la table des faits.

- Dans la section 5.5, nous développons une stratégie d'exécution des requêtes sur un schéma en étoile fragmenté.

- Dans la section 5.6, un modèle de coût est décrit pour évaluer le coût d'un ensemble de requêtes sur un un schéma en étoile fragmenté.

- Dans la section 5.7, nous montrons l'utilité de la fragmentation dans les entrepôts à travers une évaluation.

- Finalement, dans la section 5.8, nous discutons quelques perspectives de la fragmentation.

## 5.2 Exemple d'illustration: service de ventes d'un magasin

Prenons l'exemple d'une compagnie qui s'intéresse à l'analyse de ses ventes. Pour rendre compréhensible les tables de dimensions et la table des faits qui modélisent cette compagnie, supposons que cette dernière compte des produits achetés par des clients à un moment donné. Les dirigeants de cette compagnie s'interrogent quotidiennement à la fin de chaque jour ouvrable pour récupérer les informations sur les ventes par produits et par clients. Le schéma présentant les opérations de cette compagnie contient quatre tables: trois tables de dimensions: CLIENT, PRODUIT
et TEMPS et la table des faits VENTES. Les attributs, leurs caractéristiques et la taille de chaque table sont donnés en Figure 2.5.

Considérons maintenant un exemple d'illustration afin de montrer l'intérêt de la fragmentation dans l'optimisation des requêtes. Supposons que les requêtes les plus fréquemment utilisées soient les six requêtes de jointure en étoile $Q_1$ à $Q_6$ de la Figure 5.1.

Supposons que seule la table de dimensions CLIENT soit décomposée en deux fragments horizontaux Client_1 et Client_2, résultant de deux sélections disjointes sur l'attribut Sexe :

$$Client_1 = \sigma_{Sexe='M'}(CLIENT) \qquad (5.1)$$

$$Client_2 = \sigma_{Sexe='F'}(CLIENT) \qquad (5.2)$$

La table des faits VENTES peut alors être décomposée en utilisant la fragmentation horizontale dérivée, en deux fragments horizontaux Ventes_1 et Ventes_2 tels que :

$$Ventes_1 = VENTES \times Client_1 \qquad (5.3)$$

$$Ventes_2 = VENTES \times Client_2 \qquad (5.4)$$

où $\times$ représente l'opération de semi-jointure.

Le schéma initial SED : (VENTES, CLIENT, PRODUIT, TEMPS) est la juxtaposition de deux sous-schémas en étoile SED₁ et SED₂ tels que:

SED₁ : (Ventes_1, Client_1, PRODUIT, TEMPS) (ventes des clients masculins)

SED₂ : (Ventes_2, Client_2, PRODUIT, TEMPS) (ventes des clients féminins).

A partir de la définition des six requêtes de la Figure 5.1 nous remarquons que:

- Les requêtes $Q_1$, $Q_2$ et $Q_6$ accèdent à la globalité du schéma SED, c'est à dire à $SED_1 \cup SED_2$.

- La requête $Q_4$ accède seulement au sous-schéma SED₂.

- Les requêtes $Q_3$ et $Q_5$ accèdent seulement au sous-schéma SED₁.

Ainsi, la moitié des requêtes ($Q_3$, $Q_4$ et $Q_5$) accèdent seulement à une partie du schéma en étoile S. La fragmentation pour ces requêtes pourra apporter de meilleures performances. Pour l'autre moitié des requêtes ($Q_1$, $Q_2$ et $Q_6$) qui accèdent à la totalité du schéma, nous pourrons les exécuter en parallèle.

## 5.3 Les principes de notre méthode de fragmentation

### 5.3.1 Les alternatives

La fragmentation horizontale dans les entrepôts représente un enjeu plus important que dans un contexte de base de données relationnelles ou objet. Cette importance est due au choix des tables (de dimensions ou des faits) à fragmenter. Les choix possibles sont les suivants:
<table><caption>FIG. 5.1: 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>Caractéristiques</th><th>Freq</th></tr></thead><tbody><tr><td>1</td><td>SELECT sum(V.Ventes_Dollars) FROM CLIENT C, VENTES V AND C.CID = V.CID GROUP BY CID</td><td>1 jointure</td><td>15</td></tr><tr><td>2</td><td>SELECT sum(V.Ventes_Dollar), sum(S.Coût_Unitaire) FROM PRODUIT, VENTES V, TEMPS T WHERE V.PID = P.PID AND V.TID = T.TID AND P.TypePAQUET = "Boîte" AND T.Saison = "Eté" GROUP BY PID</td><td>2 jointures<br>2 prédicats</td><td>20</td></tr><tr><td>3</td><td>SELECT sum(V.Ventes_Dollar), 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.TypePAQUET = 'Papier' AND T.Saison = "Hiver" AND C.Sexe = 'M' GROUP BY TID</td><td>3 jointures<br>3 prédicats</td><td>20</td></tr><tr><td>4</td><td>SELECT sum(V.Ventes_Dollar) FROM VENTES V, CLIENT C, TEMPS T WHERE V.TID = T.TID AND V.CID = C.CID AND C.Sexe = 'F' AND T.Saison = "Eté" GROUP BY CID</td><td>2 jointures<br>2 prédicats</td><td>15</td></tr><tr><td>5</td><td>SELECT sum(S.Ventes_Dollar) FROM VENTES V, CLIENT C, PRODUIT P WHERE V.PID = P.PID AND V.CID = C.CID AND C.Sexe = 'M' AND P.TypePAQUET = "Boîte" GROUP BY PID</td><td>2 jointures<br>2 prédicats</td><td>20</td></tr><tr><td>6</td><td>SELECT max(S.Ventes_Dollar) FROM VENTES V, CLIENT C WHERE V.CID = C.CID GROUP BY CID</td><td>1 jointure<br>0 Prédicat</td><td>10</td></tr></tbody></table>
1. Fragmenter _seulement_ quelques tables de dimensions en utilisant la fragmen-
tation horizontale primaire. Ce choix n'est pas souhaitable pour les requêtes
décisionnelles, pour deux raisons: (i) les tailles des tables de dimensions sont
généralement petites, (ii) les requêtes décisionnelles accèdent à la table des faits
qui est très volumineuse. En conséquence, toute fragmentation ne prenant pas
en considération la table des faits est à exclure.

2. Partitionner _seulement_ la table des faits en utilisant la fragmentation primaire. La table des faits est composée des clés étrangères des tables de dimensions et des données brutes. Ces dernières représentent des mesures numériques, comme le montant des ventes, le nombre d'articles soldés, etc. Généralement, dans une requête décisionnelle, nous trouvons rarement des prédicats de sélection définis sur la table des faits. De plus, une requête décisionnelle typique commence par la sélection des critères selon lesquels s'effectuera l'analyse sur les tables de dimensions, puis s'orientera sur la valeur des indicateurs pour la sélection effectuée [NB99]. Ce choix est donc moins souhaitable pour le processus de la fragmentation.

3. Fragmenter _totalement_ ou _partiellement_ les tables de dimensions en utilisant la fragmentation primaire et utiliser leurs schémas de fragmentation pour partitionner la table des faits <fnref n="1" />. Ce choix est bien adapté aux entrepôts, car il prend en considération les exigences des requêtes décisionnelles, ainsi que les relations entre les tables de dimensions et la table des faits. Dans notre proposition, nous optons donc pour ce choix.

5.3.2 Une méthodologie de fragmentation

Dans cette section nous présentons une méthodologie pour fragmenter un schéma en étoile SED ayant *d* tables de dimensions {*D*₁, *D*₂, ..., *D*₉} et une table des faits *F*. L'idée de base de cette méthodologie est de fragmenter *certaines ou toutes* les tables de dimensions en utilisant les algorithmes de fragmentation horizontale primaire (voir chapitre 2). Finalement, la table des faits sera fragmentée en utilisant la fragmentation horizontale dérivée.

Rappelons que tout algorithme de fragmentation nécessite des informations sur les applications qui utilisent la base de données [CNP82, OV91]. Deux types d'informations sont à distinguer: *qualitative* et *quantitative*. Les informations qualitatives concernent les tables de dimensions et sont représentées par les prédicats de sélection simples utilisés dans les requêtes. Les informations quantitatives concernent la sélectivité de ces prédicats et les fréquences d'accès des requêtes.

L'algorithme que nous proposons a en entrée un ensemble de n requêtes de
jointure Q = {Q₁, Q₂, ..., Qn} les plus fréquentes avec leur fréquence d'accès. Cet
algorithme comprend six étapes principales [BKM00b, Bel00b]: (1) l'énumération
des prédicats de sélection, (2) l'attribution des prédicats aux tables, (3) l'identifi-
cation des tables de dimensions à fragmenter, (4) la vérification de la règle de la

<footnote n="1">¹La table des faits est alors fragmentée en utilisant la fragmentation dérivée</footnote>
complétude et de la minimalité, (5) la fragmentation des tables de dimensions et (6) la fragmentation de la table des faits.

Par la suite, nous décrivons chaque étape en détail.

1. **L'énumération de prédicats de sélection:** Cette étape consiste à énumérer tous les prédicats de sélection simples utilisés par les $n$ requêtes de départ.

2. **L'attribution des prédicats aux tables:** Les prédicats de sélection trouvés dans l'étape précédente sont définis a priori sur l'ensemble des tables de dimensions. L'objectif de cette phase est d'attribuer à chaque table de dimensions $D_i$ ($1 \le i \le d$) un ensemble de prédicats simples $EPS^{D_i}$ qui lui est propre.

3. **L'identification des tables de dimensions à fragmenter:** Nous avons vu dans la section 5.3, que certaines tables de dimensions seront fragmentées. Cette étape consiste à les identifier. Pour ce faire, toute table de dimensions $D_i$ ayant ($EPS^{D_i} = \phi$), ne sera pas prise en compte dans le processus de fragmentation, car ce dernier est basé sur les prédicats de sélection. Par conséquent, toute table $D_i$ ayant $EPS^{D_i} = \phi$, est accédée en totalité par les requêtes. Soit $D_{candidat}$ l'ensemble de toutes les tables de dimensions ayant leur ensemble de prédicats simples non vide ($EPS^{D_i} \neq \phi$). Ces tables seront candidates pour le processus de fragmentation horizontale. Soit $g$ la cardinalité de l'ensemble $D_{candidat}$ ($g \le d$).

4. **La vérification de la règle de la complétude et de la minimalité:** L'objectif de cette étape est de s'assurer que si une table de dimensions est fragmentée en au moins deux fragments, elle sera accédée différemment par au moins une application [OV91]. Pour réaliser cette tâche, nous appliquons l'algorithme COM_MIN [OV91] à chaque ensemble de prédicats simples d'une table de dimensions $D_i$. Cet algorithme fournit en sortie une forme complète et minimale de ces ensembles (voir Chapitre 2).

5. **La fragmentation des tables de dimensions:** Chaque table de dimensions de $D_{candidat}$ est partitionnée en utilisant un algorithme parmi ceux que nous avons présentés dans le Chapitre 2 (algorithmes basés sur la complétude et la minimalité des prédicats [CP84, OV91]).

Comme résultat, chaque table de dimensions $D_i$ de $D_{candidat}$ a $m_i$ fragments $\{D_{i1}, D_{i2}, ..., D_{im_i}\}$, où chaque fragment $D_{ij}$ est défini par:

$$D_{ij} = \sigma_{cl_j^i}(D_i) \qquad (5.5)$$

avec $cl_j^i$ ($1 \le i \le g, 1 \le j \le m_i$) représentant une clause de prédicats simples.

6. **La fragmentation de la table des faits:** La table des faits est alors fragmentée en fonction de tous les schémas de fragmentation des tables de dimensions de l'ensemble $D_{candidat}$. Ainsi, chaque fragment horizontal $F_i$ de la table des faits est défini de la manière suivant:

$$F_i = F \times D_{1j} \times D_{2k} \times \dots \times D_{gl}$$

avec $\times :$ représente l'opération de semi-jointure.

La fragmentation de la table des faits entraîne la division du schéma en étoile initial $SED$ en plusieurs sous-schémas en étoile $\{SED_1, SED_2, ..., SED_N\}$, où $N$ représente le nombre de fragments horizontaux de la table des faits.
**Exemple 18** Reprenons le schéma en étoile de la Figure 2.5 avec 3 tables de dimensions: CLIENT, PRODUIT, et TEMPS et une table de faits VENTES. Sur ce schéma six requêtes décisionnelles sont exécutées, chaque requête ayant une fréquence d'accès donnée (voir Table 5.1).

À partir de ces requêtes, nous énumérons (étape 1 de l'algorithme) tous les prédicats de sélection comme le montre la Table 5.1.

<table><caption>TAB. 5.1: Les tables et leurs prédicats respectifs</caption><thead><tr><td>Tables</td><td>Prédicats simples</td></tr></thead><tbody><tr><td>CLIENT</td><td>p<sub>1</sub>: Sexe = 'M'<br/>p<sub>2</sub>: Sexe = 'F'</td></tr><tr><td>PRODUIT</td><td>p<sub>3</sub>: TypePAQUET = "Boîte"<br/>p<sub>4</sub>: TypePAQUET = "Papier"</td></tr><tr><td>TEMPS</td><td>p<sub>5</sub>: Saison = "Été"<br/>p<sub>6</sub>: Saison = "Hiver"</td></tr></tbody></table>

Les ensembles de prédicats simples correspondants aux trois tables de dimensions sont (étape 2 de l'algorithme) :

$$EPS^{CLIENT} = \{p_1, p_2\},$$

$$EPS^{PRODUIT} = \{p_3, p_4\}$$

$$EPS^{TEMPS} = \{p_5, p_6\}.$$

Dans cet exemple, toutes les tables de dimensions sont candidates pour la fragmentation.

Pour chacun de ces ensembles, nous générons l'ensemble de prédicats simples minimal et complet ($EPS_{Min-Com}^{Di}$) en appliquant l'algorithme de Özsu et al. [OV91] (étape 4 de l'algorithme). Nous obtenons ainsi les mêmes ensembles à savoir:

$$EPS_{Min-Com}^{CLIENT} = \{p_1, p_2\},$$

$$EPS_{Min-Com}^{PRODUIT} = \{p_3, p_4\}$$

$$EPS_{Min-Com}^{TEMPS} = \{p_5, p_6\}.$$

Maintenant, nous fragmentons chaque table de dimension en utilisant l'algorithme de Özsu [OV91] qui est basé sur la complétude et la minimalité des prédicats. Les fragments obtenus pour chaque table de dimension sont:

- deux fragments pour la table CLIENT :

Client_1: ayant la clause cl<sub>1</sub>: Sexe = 'M',

Client_2: ayant la clause cl<sub>2</sub>: Sexe = 'F'.

- deux fragments pour la table PRODUIT :

Prod_1: ayant la clause cl'<sub>1</sub>: TypePAQUET = "Boîte",

Prod_2: ayant la clause cl'<sub>2</sub>: TypePAQUET = "Papier".

- deux fragments pour la table TEMPS :

Temps_1: ayant la clause cl''<sub>1</sub>: Saison = "Hiver",
Temps_2: ayant la clause cl''_2: Saison = "Eté".

La table des faits est alors fragmentée en 8 fragments horizontaux dont la description est illustrée dans la Table 5.2.

<table><caption>TAB. 5.2: Les fragments de la table des faits</caption><thead><tr><td>Fragments</td><td>Clause</td></tr></thead><tbody><tr><td>Ventes_1</td><td>VENTES × Client_1 × Temps_1 × Prod_1</td></tr><tr><td>Ventes_2</td><td>VENTES × Client_1 × Temps_1 × Prod_2</td></tr><tr><td>Ventes_3</td><td>VENTES × Client_1 × Temps_2 × Prod_1</td></tr><tr><td>Ventes_4</td><td>VENTES × Client_1 × Temps_2 × Prod_2</td></tr><tr><td>Ventes_5</td><td>VENTES × Client_2 × Temps_1 × Prod_1</td></tr><tr><td>Ventes_6</td><td>VENTES × Client_2 × Temps_1 × Prod_2</td></tr><tr><td>Ventes_7</td><td>VENTES × Client_2 × Temps_2 × Prod_1</td></tr><tr><td>Ventes_8</td><td>VENTES × Client_2 × Temps_2 × Prod_2</td></tr></tbody></table>

### 5.3.3 Complexité de la fragmentation

Soit SED un schéma en étoile de d tables de dimensions et une table des faits. Soit g ($g \le d$) le nombre de tables de dimensions horizontalement fragmentées. Le nombre de fragments horizontaux (dénoté par N) de la table des faits est donné par l'équation suivante:

$$N = \prod_{i=1}^{g} m_i \qquad (5.6)$$

où $m_i$ représente le nombre de fragments de la table de dimensions $D_i$.

D'après l'équation 5.6, nous constatons que notre approche de fragmentation peut générer un très grand nombre de fragments pour la table des faits et en conséquence beaucoup de sous-schémas en étoile.

**Exemple 19** Supposons par exemple que les trois tables de dimensions du schéma de l'entrepôt de la Figure 2.5 soient partitionnées comme suit:

- CLIENT en 50 fragments en utilisant l'attribut "Etat" 2,

- TEMPS en 12 fragments en utilisant l'attribut "Mois", et

- PRODUIT en deux fragments en utilisant l'attribut "Type_Paquet".

La table des faits est donc fragmentée en 1200 (= 50 × 12 × 2) fragments et le schéma en étoile en 1200 sous-schémas. Il devient difficile pour l'administrateur de l'entrepôt de gérer tous ces fragments.

A travers l'exemple précédent, il apparaît indispensable de réduire le nombre de fragments de la table des faits pour une meilleure gestion. Nous abordons ce problème dans la section suivante.

<footnote n="2">²cas de 50 états aux U.S.A.</footnote>
<figure><img src="image_51.png" /><figcaption>FIG. 5.2: Evolution des coûts en fonction du nombre de fragments</figcaption></figure>

## 5.4 Sélection des tables de dimensions

### 5.4.1 Principes

Le nombre *N* de fragments de la table des faits augmente avec le nombre de tables de dimensions fragmentées (*g*) et le nombre de fragments de chaque table fragmentée.

Il est donc nécessaire d'introduire des méthodes de sélection des tables de dimensions à fragmenter pour :

- Éviter l'explosion du nombre de fragments de la table des faits.

- Garantir la meilleure performance d'exécution des requêtes.

Pour atteindre le premier objectif, nous donnons à l'administrateur de l'entrepôt la possibilité de choisir le nombre maximum *L* de fragments de la table des faits. Ce nombre est fixé en fonction du *coût de maintenance* de l'entrepôt fragmenté. Pour satisfaire le deuxième objectif, nous devons avoir la possibilité d'augmenter le nombre de fragments tant que la performance globale peut être améliorée. Le problème est donc de trouver un compromis entre le coût de maintenance et le coût d'exécution des requêtes, comme le montre la Figure 5.2.

Le problème de la sélection des tables de dimensions peut être formulé de la manière suivante:

- Soit $D_{candidat} = \{D_1, D_2, ..., D_g\}$ l'ensemble de tables de dimensions candidates au processus de la fragmentation.

- Soit *L* le nombre de fragments de la table des faits que l'administrateur estime pouvoir maintenir.

- Soit un ensemble de requêtes $Q = \{Q_1, Q_2, ..., Q_n\}$ et leurs fréquences d'accès $\{f_1, f_2, ..., f_n\}$.

L'objectif du problème est de sélectionner un ensemble de tables de dimensions réduisant au mieux les coûts d'évaluation de l'ensemble des requêtes et de maintenance des fragments.
5.4.2 Un algorithme “glouton”

Pour résoudre le problème de sélection des tables de dimensions à fragmenter, un algorithme “glouton” est développé. Rappelons que nous considérons seulement les tables de dimensions dont leurs ensembles de prédicats simples sont non vides.

Étant donné le nombre L, cet algorithme commence par sélectionner une table de dimensions de manière aléatoire. Cette table est alors fragmentée ainsi que la table des faits par la fragmentation dérivée. Le nombre de fragments de la table des faits peut être calculé (voir l'équation 5.6). Le coût d'évaluation de l'ensemble des n requêtes est alors calculé <fnref n="3" />.

Si le nombre de fragments *N* est inférieur à *L* et qu'il y a une amélioration dans le coût, l'algorithme sélectionne une autre table de dimensions et réitère le même processus tant que les deux conditions (amélioration de coût et *N* ≤ *L*) sont satisfaites (cf. Figure 5.3). Sinon l'algorithme dé-sélectionne cette table et considère une autre table. À la fin de l'algorithme, nous obtenons un entrepôt fragmenté offrant un bon compromis entre le coût de traitement des requêtes et le coût de maintenance.

La performance du résultat dépend bien sûr de la table de dimensions qui a été sélectionnée au départ. Pour éviter la sélection aléatoire, nous proposons trois méthodes: (1) la table de dimensions la plus fréquemment utilisée, (2) la table de dimensions ayant le plus petit nombre de fragments, et (3) la table de dimensions ayant des attributs de prédicats de cardinalité faible.

- La table de dimensions la plus fréquemment utilisée Pour déterminer cette table, dénotée par $D_{Fmax}$, nous définisons la métrique suivante: la fréquence d'une table de dimensions $D_i$ de $D_{candidat}$ notée par $F_{D_i}$ est obtenue par la sommation des fréquence d'accès des requêtes accédant à la table $D_i$.

- La table de dimensions ayant le plus petit nombre de fragments Avec ce choix, nous pouvons éviter l'explosion du nombre de fragments de la table des faits.

- La table de dimensions ayant des attributs de prédicats de cardinalité faible Cette approche consiste à sélectionner les dimensions ayant des prédicats simples définis sur des attributs ayant un domaine de faible cardinalité. Par exemple l'attribut "Sexe" de dimensions CLIENT a un domaine ayant deux valeurs: mâle et femelle. Cette solution garantit un petit nombre de fragments et permet l'utilisation d'un index binaire ( bitmap index [OQ97]) sur les fragments de la table de faits. Ces index pourront améliorer la performance de certaines opérations de sélection et minimiser le coût de stockage des index.

<footnote n="3">³Nous supposons que nous disposons d'un modèle de coût calculant le nombre d'entrées-sorties. Un tel modèle est décrit dans la section suivante</footnote>
<figure><img src="image_52.png" /><figcaption>FIG. 5.3: L’algorithme glouton</figcaption></figure>

## 5.5 Les propriétés de la fragmentation

### 5.5.1 Graphe de jointure simple

Lorsqu'une relation *S* est partitionnée en fonction d'un schéma de fragmentation d'une relation *R*, deux cas de jointure peuvent intervenir: la jointure simple et la jointure partitionnée (voir Chapitre 2).

Dans le contexte des entrepôts, lorsqu'une table des faits est fragmentée en fonction des tables de dimensions, nous ne pouvons jamais avoir une jointure partitionnée (c'est à dire un cas où un fragment de la table des faits pourrait être joint avec plus d'un fragment d'une table de dimensions), mais seulement une jointure simple comme le montre la Figure 5.4. Le théorème suivant précise cette propriété.

**Théorème 1** Soient $F$ une table des faits et $D_i$ une table de dimensions d'un schéma en étoile. Si la table de dimensions $D_i$ est fragmentée horizontalement en un ensemble disjoint de fragments horizontaux $\{D_{i1}, D_{i2}, \dots, D_{im_i}\}$, où chaque fragment est défini par une clause de prédicats : $D_{ij} = \sigma_{cl_j}(D_i)$, et si la table des faits est fragmentée en utilisant le schéma de fragmentation de $D_i$, alors, la jointure distribuée entre $D_i$ et $F$ est toujours représentée par un graphe de jointure simple [Bel00b]

**Preuve 1** Nous allons prouver ce théorème par contradiction. Soit $F_p$ un fragment horizontal de la table des faits $F$ défini par : $F_p = F \times D_{ij}$. Supposons que $F_p$ puisse être joint avec deux fragments horizontaux $D_{ij}$ et $D_{il}$ ($l \neq j$) de la table de dimensions $D_i$. En conséquence:

$$F_p \times D_{ij} \neq \emptyset \qquad (5.7)$$

$$F_p \times D_{il} \neq \emptyset \qquad (5.8)$$

Notons que les fragments de $D_i$ sont disjoints, et le fragment $F_p$ est généré en utilisant la semi-jointure entre la table des faits $F$ et la table de dimensions $D_i$ dont
<figure><img src="image_53.png" /><figcaption>FIG. 5.4: La jointure simple dans un schéma en étoile</figcaption></figure>

les attributs de jointure sont la clé étrangère de F et la clé primaire de $D_i$. En conséquence, seule une condition de semi-jointure parmi les deux définies en (4.6) et (4.7) doit être satisfaite, d'où $D_{ij} = D_{il}$. Puisque $F_p$ peut être tout fragment de F, et qu'il peut toujours être joint avec exactement un fragment de $D_i$, il en résulte que le graphe de jointure est toujours simple 4.

Il résulte de cette propriété que la fragmentation horizontale dérivée de la table des faits apporte beaucoup dans la réduction du temps d’exécution des opérations de jointure entre la table des faits et les tables de dimensions.

## 5.5.2 Complétude, reconstruction, et disjonction

Tout algorithme de fragmentation dans les bases de données ou les entrepôts doit respecter trois propriétés [CP84, OV91]: la *complétude*, la *reconstruction* et la *disjonction*.

- La complétude assure que tous les n-uplets d'une relation sont associés à au moins un fragment. Dans notre cas, il faut assurer la complétude pour les tables de dimensions et la table des faits. Pour les tables de dimensions, la complétude est garantie par l'algorithme que nous utilisons (voir Chapitre 2). La complétude pour la table des faits est garantie à travers l'intégrité référentielle entre les tables de dimensions et la table des faits du modèle d'entrepôt que nous utilisons.

- La reconstruction assure qu'une relation peut être reconstruite à partir de ses fragments [OV91]. Dans notre cas, la reconstruction de la table des faits et des tables de dimensions est obtenue par l'opération d'union, c'est à dire
  $F = \cup_{i=1}^{N} F_i$ et $D_i = \cup_{j=1}^{m_i} D_{ij}$.

<footnote n="4">⁴Le théorème est vrai lorsque nous avons une jointure distribuée entre la table des faits et plusieurs tables de dimensions.</footnote>
- La disjonction assure que les fragments d'une relation sont disjoints deux à deux. Dans notre cas, cette propriété pour les tables de dimensions résulte de l'algorithme de fragmentation utilisé (voir chapitre 2). La disjonction des fragments de la table des faits est garantie par le théorème 1.

### 5.5.3 Identification des fragments participants à une requête

Dans un schéma en étoile fragmenté nous devons assurer l'accès transparent à l'utilisateur de l'entrepôt. Dans ce but, la tâche de l'optimiseur des requêtes (interrogation ou mise à jour) est de transformer les requêtes globales (c'est à dire les requêtes définies sur le schéma en étoile non fragmenté) en requêtes locales (définies sur le schéma en étoile fragmenté). Avant d'exécuter une requête sur un schéma fragmenté, l'optimiseur doit identifier le(s) sous-schéma(s) en étoile satisfaisant cette requête. Ces derniers sont appelés les schémas valides. Une fois ces sous-schémas sélectionnés, l'unité d'exécution de cette requête devient un sous-schéma au lieu du schéma global (Figure 5.5).

**Définition 32** Un attribut de prédicat pertinent (APP) est un attribut qui participe à un prédicat définissant la fragmentation. Tout attribut qui ne participe pas à la définition d'un prédicat de fragmentation est appelé attribut de prédicat non pertinent.

Supposons que nous ayons un schéma en étoile SED fragmenté en N sous-schémas en étoile {$SED_1, SED_2, ..., SED_N$}. Les informations concernant les conditions de fragmentation de chaque table de dimensions et de la table des faits peuvent être représentées par une table que nous appelons *table de spécification de la fragmentation du schéma* (Table 5.3). Cette table a trois colonnes: la première contient la liste des noms des tables de dimensions fragmentées et de la table des faits, la deuxième fournit les fragments de chaque table de dimensions et la troisième spécifie les conditions de la fragmentation de chaque table (table de dimensions ou table des faits).

**Exemple 20** Nous reprenons l'exemple de la section 2 dans lequel la table de dimensions CLIENT est fragmentée en Client_1 et Client_2, et la table des faits VENTES en Vente_1 et Vente_2. La table de spécification de la fragmentation pour ce cas est illustrée par la Table 5.3.

A partir de cette table, nous dégageons la propriété suivante:

**Propriété 1** Tout attribut appartenant à la table de spécification est un APP. Dans notre exemple, l'attribut "Sexe" est le seul APP.

<table><caption>TAB. 5.3: La table de spécification de la fragmentation</caption><thead><tr><th>Dimension</th><th>Fragments</th><th>Condition de Fragmentation</th></tr></thead><tbody><tr><td rowspan="2">CLIENT</td><td>Client_1</td><td>Sexe = 'M'</td></tr><tr><td>Client_2</td><td>Sexe = 'F'</td></tr><tr><td rowspan="2">VENTES</td><td>ventes_1</td><td>VENTES &times; Client_1</td></tr><tr><td>Ventes_2</td><td>VENTES &times; Client_2</td></tr></tbody></table>
Par la suite, nous appellerons *EAPP(SED)* l'ensemble des attributs de prédicats pertinents d'un schéma fragmenté *SED*.

Soit une requête décisionnelle $Q$ avec $p$ prédicats de sélection, exécutée sur un schéma en étoile fragmenté $SED = \{SED_1, SED_2, ..., SED_N\}$. Le but de cette section est d'identifier les sous-schémas de $SED$ qui participeront à l'exécution de la requête $Q$ (Figure 5.5). Pour réaliser cette identification, nous suggérons de procéder comme suit:

- Pour chaque prédicat de sélection $PS_i$ ($1 \le i \le p$), nous définissons une fonction $attr(PS_i)$ qui donne le nom de l'attribut utilisé par $PS_i$. Soit $EAPR(Q)$ l'union de tous les attributs des prédicats de la requête $Q$.

- En fonction de $EAPR(Q)$ et $EAPP(SED)$, nous distinguons quatre scénarios:

1. $EAPR(Q) = \emptyset$, (la requête $Q$ ne contient pas de prédicat de sélection, c'est le cas de la requête 6 de la Table 5.1). Dans ce cas, deux approches existent pour exécuter la requête $Q$:

(a) Faire d'abord l'union de tous les schémas en étoile et ensuite exécuter la requête, comme dans le cas non partitionné.

(b) Exécuter la requête sur chaque sous-schéma $SED_i$ ($1 \le i \le N$) et ensuite faire l'union des résultats.

2. ($EAPR(Q) \neq \emptyset$) et ($EAPR(Q) \cap EAPP(SED) = \emptyset$) (la requête $Q$ a quelques prédicats de sélection sur des tables de dimensions non fragmentées, ou bien les attributs de prédicats de la requête $Q$ ne coïncident pas avec les prédicats pertinents). Pour exécuter la requête $Q$ nous utilisons l'une des approches parmi celles présentées en (1.a) et (1.b).

3. ($EAPR(Q) \cap EAPP(SED) \neq \emptyset$) (quelques attributs de la requête dans les prédicats de sélection coïncident avec certains APP). Dans ce cas, nous pouvons facilement déterminer (en utilisant les prédicats de sélection de la requête $Q$) les sous-schémas en étoile concernés par $Q$. Une fois les sous-schémas identifiés, la requête $Q$ est exécutée sur chacun. Pour obtenir le résultat final de la requête, nous faisons l'union des résultats locaux (obtenus dans chaque sous-schéma).

4. ($EAPR(Q) \subseteq EAPP(SED)$) (tous les attributs des prédicats de sélection de la requête $Q$ sont des APP). Notons que l'ensemble des prédicats simples de la fragmentation est minimal et complet d'où la garantie que l'entrepôt est fragmenté en au moins deux fragments. Le fait qu'un APP appartienne à $EAPP(SED)$, signifie que la requête $Q$ n'accède pas à la globalité de la table d'où cet attribut est issu. Dans ce cas, la requête est exécutée en utilisant la même approche que le troisième scénario.

Pour conclure, nous faisons les observations suivantes:

- La fragmentation détériore la performance d'exécution des requêtes satisfaisant les cas 1 et 2,

- Elle est favorable pour le cas 3,

- Elle est la plus avantageuse pour le cas 4.
<figure><img src="image_54.png" /><figcaption>FIG. 5.5: Identification de(s) sous-schéma(s) en étoile</figcaption></figure>

## 5.6 Modèle de coût pour l'exécution des requêtes

Pour valider les observations décrites précédemment, nous développons un modèle de coût (calculant le nombre d'entrées-sorties lors de l'évaluation d'une requête) qui peut être considéré comme une mesure de performance de la fragmentation dans les entrepôts.

Soit *SED* : ($D_1, D_2, ..., D_d, F$) un schéma en étoile d'un entrepôt ayant *d* tables de dimensions et une table des faits *F*. En suivant la stratégie de fragmentation pour laquelle nous avons optée, les tables de dimensions sont fragmentées en utilisant les algorithmes de fragmentation primaire, et la table des faits est partitionnée en utilisant la fragmentation horizontale dérivée.

Supposons donc que certaines tables de dimensions soient fragmentées. Le résultat de la fragmentation de la table des faits en fonction des fragments des tables de dimensions entraîne la division du schéma global de l'entrepôt *SED* en *N* sous-schémas en étoile (cf. section 5.3). Chaque sous-schéma possède les mêmes caractéristiques que le schéma global, la seule différence étant que chaque sous-schéma contient les n-uplets satisfaisant une clause donnée.

Sur chaque sous-schéma, nous pouvons définir des vues matérialisées, des index de jointure en utilisant les mêmes algorithmes de sélection présentés dans le Chapitre 2.

Pour quantifier le bénéfice apporté par chaque schéma de fragmentation, nous proposons d'adapter le modèle de coût présenté dans le Chapitre 3 qui considère les index de jointure et les vues matérialisées. Quelques retouches sont nécessaires:

- Pour exécuter une requête *Q* sur un schéma d'un entrepôt de données fragmenté en *m* sous-schémas de l'entrepôt {*SED*₁, *SED*₂, ..., *SED*ₘ}, nous devons identifier le(s) sous-schéma(s) valide(s) avant de l'exécuter. Pour réaliser cette identification, une variable booléenne dénotée par *valide*(*Q*, *SED*ᵢ) est définie:
$$ valide(Q, SED_i) = \begin{cases} 1 & \text{si le sous-schéma } SED_i \text{ est valide pour la requête } Q \\ 0 & \text{sinon} \end{cases} $$

- La conséquence du processus d'identification est le changement de l'unité de chargement des données de disque vers la mémoire centrale. C'est-à-dire dans un entrepôt non fragmenté, l'unité de chargement est la table, par contre dans le cas fragmenté, l'unité de chargement est le fragment.

- Il faut charger uniquement les index correspondant aux sous-schémas valides.

Le nombre d'ES va dépendre de la façon dont peuvent se dérouler les échanges avec la mémoire centrale. Nous considérons deux hypothèses.

1. **Hypothèse de Mémoire Large (HML):** Toutes les tables de dimensions peuvent être chargées intégralement dans la mémoire centrale, car leur taille est petite [Cor97a]. La table des faits et les index de jointure sont chargés par parties et à la demande en mémoire centrale. Les résultats intermédiaires restent en mémoire centrale. Cette hypothèse devient réaliste compte tenu de l'évolution des matériels et de leur coût. Sous cette hypothèse, le coût sera le nombre d'ES réalisé en chargeant en mémoire la table des faits et les index. Dans ce cas, les caractéristiques des tables dans les formules du Chapitre 3 sont remplacées par celles des fragments valides.

2. **Hypothèse de Mémoire Moyenne (HMM):** Elle diffère de la précédente dans la mesure où les résultats intermédiaires ne peuvent pas être stockés intégralement en mémoire centrale. Il faudra donc les transférer sur disque et les recharger par parties en mémoire centrale pour achever l'exécution de la requête. Donc pour exécuter une jointure multiple $M : D_1 \times F \times D_2 \times \dots \times D_j$ sur un entrepôt non fragmenté, l'optimiseur exécute la première jointure ($D_1 \times F$), et vérifie si son résultat peut être stocké dans la mémoire centrale. Si c'est le cas, il joint ce résultat avec $D_2$ et il réitère le processus jusqu'à la dernière table de dimensions $D_j$. Sinon, il doit transférer ce résultat sur disque puis le recharger en mémoire pour continuer l'opération $M$. Dans le cas où l'entrepôt est fragmenté, la jointure multiple sera une jointure distribuée, et donc les résultats intermédiaires seront moins volumineux par rapport à ceux issus d'une jointure normale (cas non fragmenté).

## 5.7 Evaluation d'un entrepôt fragmenté

Afin de démontrer l'importance de la fragmentation dans les entrepôts, nous effectuons quelques expérimentations, en utilisant le schéma en étoile de la Figure 2.5. Les caractéristiques principales de ces expérimentations sont présentées dans la Table 3.4.

Pour caractériser l'amélioration des performances d'exécution des requêtes décisionnelles en utilisant la fragmentation, nous introduisons le facteur ES normalisé qui est défini comme suit:

$$ ES \text{ normalisé} = \frac{\text{NOMBRE d'ESs dans un SCHEMA EN ETOILE FRAGMENTÉE}}{\text{NOMBRE d'ESs dans un SCHEMA en ETOILE non FRAGMENTÉE}} $$
Si la valeur de ES normalisé est inférieure à 1.0, la présence de la fragmentation dans les entrepôts est bénéfique, sinon elle ne l'est pas.

Supposons que les tables de dimensions soient fragmentées comme dans l'exemple 18. Pour situer l'impact du nombre de tables de dimensions fragmentées, nous considérons quatre cas:

- Cas 0 : Aucune table n'est fragmentée.

- Cas 1 : Une seule table de dimensions est fragmentée, par exemple CLIENT 5. La table de spécification correspondante est donnée en Table 5.3.

- Cas 2 : Deux tables de dimensions sont fragmentées, par exemple CLIENT et PRODUIT. La table de spécification correspondante est donnée en Table 5.4.

- Cas 3 : Toutes les tables de dimensions sont fragmentées. La table de spécification est présentée dans la Table 5.5.

<table><caption>TAB. 5.4: La spécification de la fragmentation (cas 2)</caption><thead><tr><th>Dimensions</th><th>Fragments</th><th>Condition de Fragmentation</th></tr></thead><tbody><tr><td rowspan="2">CLIENT</td><td>Client_1</td><td>Sexe = 'M'</td></tr><tr><td>Client_2</td><td>Sexe = 'F'</td></tr><tr><td rowspan="2">PRODUIT</td><td>Prod_1</td><td>Typepaquet = "Boîte"</td></tr><tr><td>Prod_2</td><td>Typepaquet = "Papier"</td></tr><tr><td rowspan="4">VENTES</td><td>Ventes_1</td><td>VENTES &times; Client_1 &times; Prod_1</td></tr><tr><td>Ventes_2</td><td>VENTES &times; Client_1 &times; Prod_2</td></tr><tr><td>Ventes_3</td><td>VENTES &times; Client_2 &times; Prod_1</td></tr><tr><td>Ventes_4</td><td>VENTES &times; Client_2 &times; Prod_2</td></tr></tbody></table>

<table><caption>TAB. 5.5: La spécification de la fragmentation (cas 3)</caption><thead><tr><th>Dimension</th><th>Fragments</th><th>Condition de Fragmentation</th></tr></thead><tbody><tr><td rowspan="2">CLIENT</td><td>Client_1</td><td>Sexe = 'M'</td></tr><tr><td>Client_2</td><td>Sexe = 'F'</td></tr><tr><td rowspan="2">TEMPS</td><td>Temps_1</td><td>Saison = "Hiver"</td></tr><tr><td>Temps_2</td><td>Saison = "Eté"</td></tr><tr><td rowspan="2">PRODUIT</td><td>Prod_1</td><td>Typepaquet = "Boîte"</td></tr><tr><td>Prod_2</td><td>Typepaquet = "Papier"</td></tr><tr><td rowspan="3">VENTES</td><td>Ventes_1</td><td>VENTES &times; Client_1 &times; Temps_1 &times; Prod_1</td></tr><tr><td>Ventes_2</td><td>VENTES &times; Client_1 &times; Temps_1 &times; Prod_2</td></tr><tr><td>...</td><td>...</td></tr><tr><td></td><td>Ventes_8</td><td>VENTES &times; Client_2 &times; Temps_2 &times; Prod_2</td></tr></tbody></table>

<footnote n="5">5. La table CLIENT est la table la plus fréquemment utilisée et ayant des attributs de prédicats de cardinalité faible (Sexe)</footnote>
Pour toutes ces expérimentations nous avons supposé pour simplifier que la taille des fragments des tables de dimensions et de la table des faits était la même.

Dans les Tables 5.6 et 5.7 nous donnons les résultats obtenus pour chacun des cas considérés et pour les six requêtes décisionnelles. Ces résultats appellent les commentaires suivants:

- En comparaison avec le cas non fragmenté (cas 0), la fragmentation donne souvent de meilleurs résultats. Dans tous les cas, la requête ayant bénéficié de la fragmentation est Q3. En effet elle possède des prédicats de sélection utilisés dans l'algorithme de fragmentation (voir le point 4 de la section 5.5.3).

- La fragmentation peut dégrader la performance d'exécution de certaines requêtes décisionnelles. Par exemple, tous les cas de fragmentation ne sont pas bénéfiques pour les requêtes Q1 et Q6 pour la raisons suivante: (1) Q1 et Q6 n'ont aucun prédicat de sélection, ainsi afin de l'évaluer, il faut accéder à tous les fragments de la table des faits et des tables de dimensions. Cela confirme nos propos de la section 5.5.3.

- Le nombre de tables de dimensions fragmentées a un rôle significatif dans la performance. Comme nous le voyons dans les Tables 5.6 et 5.7, la fragmentation donne de meilleurs résultats dans le cas 3 (pour Q2, Q3, Q4, Q5), pour lequel toutes les tables de dimensions de l'entrepôt sont fragmentées.

- Le total ES normalisé pour chaque cas ($ESN_i$) est toujours inférieur à 1.0. Cela signifie que la fragmentation donne de bons résultats si nous nous intéressons à la performance globale de toutes les requêtes décisionnelles. Par exemple la fragmentation n'est pas bénéfique pour les requêtes Q1, Q2 et Q6 (cas 1), mais elle est bénéfique pour les requêtes Q3, Q4 et Q5. La contre performance des requêtes non bénéficiaires de la fragmentation est compensée par la bonne performance des requêtes bénéficiaires.

- La fragmentation est toujours meilleure par rapport au cas non fragmenté (Table 5.7). Cela provient du fait que les résultats intermédiaires de la jointure distribuée peuvent être stockés dans la mémoire centrale.

<table><caption>TAB. 5.6: Le coût d'exécution des requêtes sous l'hypothèse HML</caption><thead><tr><th>Q</th><th>ES</th><th>ES<sub>1</sub></th><th>ESN<sub>1</sub></th><th>ES<sub>2</sub></th><th>ESN<sub>2</sub></th><th>ES<sub>3</sub></th><th>ESN<sub>3</sub></th></tr><tr><th>Cas</th><th>Cas 0</th><th>Cas 1</th><th>Cas 1</th><th>Cas 2</th><th>Cas 2</th><th>Cas 3</th><th>Cas 3</th></tr></thead><tbody><tr><th>Q1</th><td>175826</td><td>175856</td><td><u>1.0001</u></td><td>175948</td><td><u>1.0006</u></td><td>176124</td><td><u>1.002</u></td></tr><tr><th>Q2</th><td>5856575</td><td>5856683</td><td>1.0</td><td>2197003</td><td><strong>0.38</strong></td><td>1464232</td><td><strong>0.25</strong></td></tr><tr><th>Q3</th><td><strong>5856585</strong></td><td><strong>2197003</strong></td><td><strong>0.37</strong></td><td><strong>1464193</strong></td><td><strong>0.25</strong></td><td><strong>732127</strong></td><td><strong>0.125</strong></td></tr><tr><th>Q4</th><td>4392432</td><td>2197003</td><td>0.5</td><td>2197003</td><td>0.5</td><td>1464232</td><td><strong>0.25</strong></td></tr><tr><th>Q5</th><td>5856575</td><td>2197003</td><td><strong>0.38</strong></td><td>1464193</td><td><strong>0.25</strong></td><td>1464232</td><td><strong>0.25</strong></td></tr><tr><th>Q6</th><td>5856545</td><td>5856582</td><td><u>1.0001</u></td><td>5856643</td><td><u>1.0002</u></td><td>5856761</td><td><u>1.001</u></td></tr><tr><th>Total</th><td>27994538</td><td>18480130</td><td>0.66</td><td>13354983</td><td>0.47</td><td>11157708</td><td>0.39</td></tr></tbody></table>

Nous avons aussi étudié l'effet de la variation de la taille de la table des faits (dans la réalité cette table évolue sans cesse). Nous supposons que nous avons un entrepôt
<table><caption>TAB. 5.7: Le coût d'exécution des requêtes sous hypothèse HMM</caption><thead><tr><th>Q</th><th>ES</th><th>ES<sub>1</sub></th><th>ESN<sub>1</sub></th><th>ES<sub>2</sub></th><th>ESN<sub>2</sub></th><th>ES<sub>3</sub></th><th>ESN<sub>3</sub></th></tr><tr><th>Cas</th><th>Cas 0</th><th>Cas 1</th><th>Cas 1</th><th>Cas 2</th><th>Cas 2</th><th>Cas 3</th><th>Cas 3</th></tr></thead><tbody><tr><th>Q1</th><td>175826</td><td>175856</td><td><u>1.0001</u></td><td>175948</td><td><u>1.0006</u></td><td>176124</td><td><u>1.002</u></td></tr><tr><th>Q2</th><td>10004935</td><td>5856683</td><td><b>0.58</b></td><td>2197003</td><td><b>0.22</b></td><td>1464232</td><td><b>0.15</b></td></tr><tr><th>Q3</th><td><b>12079125</b></td><td><b>2197003</b></td><td><b>0.18</b></td><td><b>1464193</b></td><td><b>0.13</b></td><td>732127</td><td><b>0.06</b></td></tr><tr><th>Q4</th><td>7503702</td><td>2197003</td><td>0.3</td><td>2197003</td><td>0.3</td><td>1464232</td><td><b>0.2</b></td></tr><tr><th>Q5</th><td>10004935</td><td>2197003</td><td><b>0.21</b></td><td>1464193</td><td><b>0.15</b></td><td>1464232</td><td><b>0.24</b></td></tr><tr><th>Q6</th><td>5856545</td><td>5856582</td><td><u>1.0001</u></td><td>5856643</td><td><u>1.0002</u></td><td>5856761</td><td><u>1.001</u></td></tr><tr><th>Total</th><td>45625068</td><td>18840130</td><td>0.41</td><td>13354983</td><td>0.29</td><td>11157708</td><td>0.24</td></tr></tbody></table>

<figure><img src="image_55.png" /><figcaption>FIG. 5.6: L'effet de variation de la taille de la table des faits</figcaption></figure>

fragmenté en 2, 4 et 8 fragments et nous faisons varier la taille de la table des faits de $10^8$ à $10^9$. Nous remarquons que le facteur ES normalisé reste constant comme le montre la Figure 5.6. Cela nous montre que ES normalisé est indépendant de la cardinalité de la table des faits.

## 5.8 Problèmes ouverts

Plusieurs questions sont toujours ouvertes sur le rôle de la fragmentation (en général) dans l'amélioration de la performance des entrepôts de données. Parmi ces questions, nous pouvons citer: la fragmentation et les data marts, la fragmentation et l'adaptation des vues matérialisées.

### 5.8.1 Principes des data marts

Dans cette section, nous abordons l'un des points évoqués précédemment, c'est-à-dire, le rôle de la fragmentation horizontale dans la conception des data marts [BKM00b].

**Pourquoi les data marts?** Mettre en oeuvre un entrepôt de données pour une entreprise intégrée est une tâche difficile qui nécessite la collecte des données
de différents départements, leur nettoyage, et leur intégration. Certaines entreprises ont donc préféré développer des data marts. Rappelons qu'un data mart est une base de données orientée sujet à la disposition des utilisateurs dans un contexte décisionnel décentralisé [Fra97]. Les caractéristiques principales d'un data mart sont les suivantes:

- Il se concentre seulement sur un sujet et un groupe d'utilisateurs. Il présente un sous-ensemble de l'entrepôt aux utilisateurs ayant un besoin fonctionnel bien spécifique.

- une entreprise peut avoir un seul entrepôt, mais plusieurs data marts.

- les data marts contiennent moins d'informations que les entrepôts; ils sont donc plus facilement gérables et interrogeables.

- les data marts nécessitent une durée réduite de mise en oeuvre, inférieure à celle des entrepôts.

Deux approches existent pour concevoir un data mart [Fir97]: (1) une approche ascendante et (2) une approche descendante.

Dans l'approche ascendante, le data mart est conçu en intégrant des données à partir des sources. Dans cette approche, les différents data marts dont a besoin une entreprise sont mis en oeuvre indépendamment (Figure 5.7).

Dans l'approche descendante, le data mart est conçu en extrayant les données de l'entrepôt, en fonction des besoins (voir Figure 5.8). Dans cette approche, le rôle des data marts est de présenter des sous-ensembles de l'entrepôt aux utilisateurs ayant un besoin fonctionnel bien déterminé. La relation entre les data marts et l'entrepôt est unidirectionnelle [Fir97]. Les data marts sont dérivés de l'entrepôt et leur contenu est strictement limité par celui de l'entrepôt. Tout changement au niveau de l'entrepôt, doit être répercuté sur les data marts.

Pour concevoir des data marts en respectant cette approche, nous pouvons penser à la duplication de l'entrepôt dans chaque data mart. L'inconvénient majeur de cette solution est l'introduction d'une grande redondance. Pour pallier ce problème, la fragmentation pourrait être un bon moyen. Elle peut être utilisée comme un outil de division de l'entrepôt en fonction des besoins de chaque département ou du groupe d'utilisateurs. En conséquence, un data mart peut être vu comme un mini entrepôt (ou fragment d'un entrepôt). Dans un tel scénario, les tables de l'entrepôt (lorsque l'entrepôt est modélisé par un schéma relationnel) seront partitionnées et chaque data mart aura donc ses propres données.

### 5.8.1.1 Analogies entre la conception de bases de données réparties et la conception de data marts

Les entrepôts de données sont très souvent répartis, soit en raison de leur taille, soit en raison de la variété des sources qu'ils approvisionnent. Comme l'ont mentionné Garcia Molina et al. [MLJ98], même lorsque les données de l'entrepôt sont centralisées sur un même site, compte tenu de leur taille, elles sont souvent stockées sur plusieurs disques et peuvent de ce fait être considérées comme réparties.
<figure><img src="image_56.png" /><figcaption>FIG. 5.7: L'approche ascendante</figcaption></figure>

<figure><img src="image_57.png" /><figcaption>FIG. 5.8: L'approche descendante</figcaption></figure>

Pour concevoir une base de données répartie, Ceri et al. [CNP82] ont proposé deux stratégies ascendante et descendante.

- La **stratégie ascendante** est une approche selon laquelle la tâche de conception consiste à intégrer dans un schéma unique les descriptions d'un certain nombre de bases de données existantes. Très souvent les bases de données à intégrer sont hétérogènes. Cette approche est essentiellement utilisée dans la conception des base des données fédérées [GV90].

- La **stratégie descendante** est utilisée pour la création d'une nouvelle base de données ou lors de la répartition d'une base de données centralisée. Elle consiste à diviser une base de données en un ensemble de bases de données locales, chacune étant gérée par le même SGBD. On est alors dans une situation où les bases de données sont homogènes. Cette répartition se réalise en deux étapes essentielles, à savoir, la fragmentation des données de la base et l'allocation, suivie éventuellement d'une optimisation locale [CMVN94]. Chaque phase peut être résolue par plusieurs approches rendant la tâche de la conception d'une base de données répartie difficile (voir Figure 5.9).

### 5.8.1.2 Intérêt de la fragmentation

Dans un contexte distribué, la fragmentation consiste à partitionner les tables du schéma conceptuel global de la base de données en plusieurs fragments. Cette fragmentation est faite en fonction des *besoins de chaque site du système distribué*. Les fragments issus du processus de partitionnement seront ensuite alloués de façon optimale sur les sites du système réparti (voir Figure 5.9). L'optimisation est guidée par une fonction objectif (dans la plupart des cas, on cherche à minimiser les coûts de transfert des données lors de l'exécution d'un ensemble de requêtes [Ape88, KP97]). Une fois les fragments alloués aux sites, des optimisations locales peuvent être réalisées au niveau de chaque site (comme par exemple, la création d'index propres aux fragments de chaque site).
<figure><img src="image_58.png" /><figcaption>FIG. 5.9: Analogie entre la conception des bases de données réparties et la conception de data marts</figcaption></figure>

Par contre, la fragmentation dans les data marts consiste, en fonction des *besoins de chaque data mart*, à diviser l'entrepôt en sous-ensembles d'entrepôts. Ces derniers seront ensuite attribués (ou alloués) aux data marts. La fragmentation dans ce contexte, consiste donc à extraire les données de l'entrepôt nécessaires pour chaque data mart.

Le problème d'attribution des fragments aux data marts peut être vu comme un problème d'allocation classique dans les bases de données (relationnelles ou objet) [Ape88, BHY91, BKL98a], où les sites correspondraient aux data marts. Une fois les data marts construits, les mêmes techniques d'optimisation utilisées dans les entrepôts de données peuvent être utilisées.

Le problème d'attribution des fragments aux data marts reste de ce fait une question de recherche ouverte [BKM00b].

## 5.8.2 La fragmentation et l'adaptation des vues

Bellahsène et al. [BM00] travaillent maintenant sur l'utilisation de la fragmentation dans le processus d'adaptation des vues. Leurs résultats préliminaires ont montré que la fragmentation contribue d'une manière significative à l'adaptation soit après redéfinition soit lorsque les schémas des sources de données changent.

## 5.9 Conclusion

Dans ce chapitre nous avons présenté une méthodologie complète pour la fragmentation horizontale dans les entrepôts de données modélisés par des schémas en étoile. Nous avons d'abord développé un algorithme de fragmentation pour les tables de dimensions et la table des faits, en adaptant les techniques utilisées dans les bases de données relationnelles. Par la suite, nous avons présenté les problèmes liés à la fragmentation de la table des faits en fonction des tables de dimensions et nous
avons suggéré des solutions. Un modèle de coût a été développé afin de mesurer le résultat de la fragmentation. Finalement des expériences ont été conduites et ont montré qu'avec une fragmentation adéquate des tables de dimensions, il est possible d'améliorer les performances d'exécution des requêtes décisionnelles.

Nos perspectives se situent dans la considération des deux problèmes cités dans
la section 5.8.
# Chapitre 6

## Nouveaux algorithmes pour la
fragmentation horizontale

### 6.1 Introduction

Nous avons vu précédemment que la fragmentation horizontale permet de réduire
le temps d'exécution des requêtes en minimisant le nombre d'accès (non nécessaires)
aux données. Cependant, pour atteindre cet objectif, il faut disposer d'algorithmes
de fragmentation: (i) ayant une complexité raisonnable, et (2) offrant un moyen
d'évaluer la réduction du temps d'exécution des requêtes.

1. En nous penchant sur la littérature concernant la fragmentation horizontale, force est de constater que la plupart des algorithmes proposés (dans le modèle relationnel ou objet) sont d'une grande complexité (par exemple l'algorithme dirigé par la complétude et la minimalité des prédicats [CP84, OV91] génère $2^n$ fragments, $n$ représentant le nombre de prédicats simples). Pour pallier cet inconvénient, Navathe et al. [NKR95] ont montré que l'algorithme qu'ils ont proposé pour la fragmentation verticale, d'une complexité moindre, pouvait être adapté à la fragmentation horizontale [NR89]. Néanmoins, les auteurs ont simplement décrit les principes de cette adaptation, mais n'ont pas élaboré un algorithme spécifique.

2. Tout algorithme de fragmentation (verticale ou horizontale) doit permettre de quantifier sa contribution à la réduction du temps d'exécution des requêtes. Il existe des moyens pour quantifier les algorithmes de la **fragmentation verticale** comme l'évaluateur de partition proposé par Chakravarthy [CMVN94] ou le modèle de coût développé dans [FKL97]. Malheureusement, cette quantification n'est pas fournie pour les algorithmes de fragmentation horizontale actuellement disponibles [CP84, OV91, BKS97, EB95, NKR95]. Il n'est donc pas possible de comparer leurs performances.

En conclusion, en l'absence d'une mesure de quantification, personne ne peut as-
surer que tel algorithme est meilleur qu'un autre du point de vue de la rapidité
de l'exécution des requêtes. Le reproche que nous pouvons faire aux algorithmes
de fragmentation horizontale existants est l'utilisation de la **fréquence d'accès des
requêtes** comme seul critère de regroupement des n-uplets en fragments horizontaux.
<figure><img src="image_59.png" /><figcaption>FIG. 6.1: Le modèle de coût comme outil de sélection</figcaption></figure>

Or, dans les applications basées sur les entrepôts de données, d'autres paramètres sont aussi importants dans la définition des schémas de fragmentation comme: la sélectivité des prédicats, la taille des relations à fragmenter, la taille de la mémoire centrale, la taille de la page mémoire, la taille des vues matérialisées et des index, etc.

Ce chapitre est divisé en deux parties principales. La première est consacrée à l'adaptation de l'algorithmme de Navathe et al. [NR89] à la fragmentation horizontale primaire. Rappelons que cet algorithmme fait partie des algorithmes basés sur les affinités des prédicats. Dans la deuxième partie, un modèle de coût calculant le nombre d'entrées-sorties lors de l'exécution d'un ensemble des requêtes sur un schéma fragmenté est introduit. Ce modèle de coût peut avoir deux rôles différents:

- Il peut être utilisé comme outil de mesure pour quantifier le bénéfice de chaque algorithme de fragmentation proposé dans la littérature. Il est alors possible de sélectionner le meilleur algorithme pour un ensemble requêtes (Figure 6.1).

- Il peut également être utilisé pour définir de nouveaux types d'algorithmes de fragmentation horizontale. Pour éclairer ce point, considérons la situation suivante: soit *T* une table d'un entrepôt de données<fnref n="1" /> que nous souhaitons fragmenter. Supposons que cette table soit accédée par un ensemble de requêtes (les plus fréquentes). À partir des prédicats de sélection définis sur cette table, nous pouvons énumérer tous les schémas de fragmentation possibles de *T*. À l'aide de ce modèle, le coût d'exécution de l'ensemble de requêtes sur chaque schéma est calculé. Finalement, le schéma satisfaisant un coût minimal est sélectionné.

Dans cette optique, nous introduisons un nouveau type d'algorithmes pour la fragmentation horizontale primaire, à savoir: **les algorithmes dirigés par un modèle de coût**. Deux algorithmes seront proposés: (1) *un algorithme exhaustif*, et (2) *un algorithme approximatif* [BKB98].

<footnote n="1">¹L'idée de l'utilisation d'un modèle de coût dans la définition de nouveaux algorithmes de fragmentation horizontale a été, de prime abord, développée dans le contexte des bases de données orientées-objet [BKB98, BKL98b].</footnote>
## 6.2 Un algorithme dirigé par les affinités

Dans cette section, nous adaptons l'algorithm de Navathe et al. [NKR95] (que nous appelons algoVertical) développé pour la fragmentation verticale à la fragmentation horizontale. Rappelons que l'algoVertical possède cinq étapes principales (voir Chapitre 2): (i) l'énumération des attributs utilisés par les requêtes, (ii) la construction de la matrice d'usage des attributs, (iii) la construction de la matrice d'affinité des attributs, (vi) le regroupement des attributs, et (v) la construction des fragments verticaux. Cet algorithme a une complexité polynômiale ($O(n^2)$, où n est le nombre des attributs de la table à fragmenter).

On peut envisager de reprendre les mêmes principes pour regrouper les n-uplets au lieu des attributs et obtenir ainsi une fragmentation horizontale. Par analogie les cinq étapes d'un algorithme de fragmentation horizontale seraient donc: (i) l'énumération des prédicats utilisés par les requêtes, (ii) la construction de la matrice d'usage des prédicats, (iii) la construction de la matrice d'affinité des prédicats, (vi) le regroupement des prédicats, et (v) la construction des fragments horizontaux.

Cependant les prédicats n'ont pas les mêmes caractéristiques que les attributs, et cette substitution des attributs par des prédicats dans algoVertical n'est pas suf-fisante pour obtenir les fragments horizontaux. Un algorithme des affinités pour la fragmentation horizontale (que nous appelons algoAffiHoriz) doit en plus tenir compte des implications entre les prédicats qui peuvent influencer l'étape de regrou-pement.

Nous décrivons d'abord les principales étapes de algoAffiHoriz avant de discuter de sa complexité et de sa correction.

### 6.2.1 Les phases de l'algorithmes des affinités

Comme tous les algorithmes basés sur les affinités, algoAffiHoriz part d'une table T(K, A₁, A₂, ..., A_l) (appartenant à un entrepôt de données (de type ROLAP) ou à une base de données), d'un ensemble de requêtes $Q = \{Q_1, Q_2, ..., Q_n\}$ (les plus fréquemment utilisées) et de leurs fréquences d'accès $F = \{f_1, f_2, ..., f_n\}$. L'ensemble des requêtes et leurs fréquences sont déterminées par l'administrateur [Kar96].

L'algorithme algoAffiHoriz se caractérise par huit étapes, à savoir [BKA00, BKS97]: (1) l'énumération des prédicats de sélection, (2) la construction de la matrice d'usage des prédicats, (3) la construction de la matrice d'affinité des prédicats, (4) le regroupement des prédicats, (5) l'optimisation des composantes, (6) la formation des minterms, (7) la formation des fragments horizontaux, et (8) la génération des fragments disjoints.

Pour faciliter la compréhension de chaque étape, nous illustrons leur fonctionne-ment par un exemple.

1. **L'énumération des prédicats de sélection:** généralement une requête pos-sède des prédicats de sélection et des prédicats de jointure (figurant dans la clause WHERE de la syntaxe SQL de cette requête). Rappelons que tout algo-rithme de fragmentation horizontale utilise seulement les prédicats de sélection définis dans les requêtes de départ. À partir des n requêtes de départ, nous
énumérons l'ensemble de tous les prédicats de sélection simples (dénoté par PSS) définis sur la table T. Soit ATTR l'ensemble des attributs de la table T utilisés par les prédicats de PSS. Notons par N et r (r ≤ l+1) les cardinalités de PSS et ATTR, respectivement 2.

**Exemple 21** *Considérons la table de dimension CLIENT du schéma en étoile de la Figure 2.5. Cette table possède cinq attributs: l'identifiant du client (CID) (la clé primaire de CLIENT), l'Age, le Sexe, la Ville, et la Région. Supposons que quatre requêtes {Q₁, Q₂, Q₃, Q₄} accèdent à cette table avec les prédicats de sélection sont les suivants:*

- Q₁ - (p₁) : Age ≤ 30, (p₅) : Sexe = 'M'

- Q₂ - (p₂) : Age ≤ 40, (p₅) : Sexe = 'M'

- Q₃ - (p₃) : Age = 18, (p₆) : Sexe = 'F', (p₇) : Ville = "Grenoble"

- Q₄ - (p₄) : 50 ≤ Age ≤ 60, (p₆) : Sexe = 'F'

En examinant ces prédicats, nous constatons que seulement trois attributs parmi les cinq sont utilisés, à savoir: l'Age, le Sexe et la Ville, que nous re-nommons: A₁, A₂ et A₃.

Prédicats

<table><caption>FIG. 6.2: La matrice d'usage des prédicats</caption><thead><tr><th>Requêtes</th><th>p<sub>1</sub></th><th>p<sub>2</sub></th><th>p<sub>3</sub></th><th>p<sub>4</sub></th><th>p<sub>5</sub></th><th>p<sub>6</sub></th><th>p<sub>7</sub></th><th>Fréquence</th></tr></thead><tbody><tr><td>Q<sub>1</sub></td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>20</td></tr><tr><td>Q<sub>2</sub></td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>35</td></tr><tr><td>Q<sub>3</sub></td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>30</td></tr><tr><td>Q<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>15</td></tr></tbody></table>

2. **La construction de la matrice d'usage des prédicats:** comme son nom l'indique, cette matrice représente l'utilisation des prédicats dans les requêtes. Les lignes et les colonnes de cette matrice sont associés aux n requêtes de départ et les N prédicats obtenus à l'étape 1, respectivement.

Les éléments $mup_{i,j}$ ($1 \le i \le n, 1 \le j \le N$) de cette matrice sont binaires ($0$ ou $1$) et sont définis comme suit:

$$mup_{i,j} = \begin{cases} 1, & \text{si la requête } Q_i \text{ utilise le prédicat } p_j \\ 0, & \text{sinon} \end{cases}$$

**Exemple 22 (suite)** La matrice d'usage des prédicats de notre exemple est montrée dans la Figure 6.2. Elle contient 4 lignes (pour les requêtes) et 7 colonnes (pour les prédicats). Nous ajoutons à cette matrice une colonne représentant la fréquence d'accès de chaque requête.

3. **La construction de la matrice d'affinité des prédicats:** cette matrice est générée de la même manière que la matrice d'affinité des attributs de la fragmentation verticale. C'est une matrice carrée ($N \times N$) et symétrique dont

<footnote n="2">²l représente le nombre d'attributs à l'exception de la clé de la table T</footnote>
<figure><img src="image_60.png" /><figcaption>FIG. 6.3: La signification de la valeur numérique</figcaption></figure>

les lignes et les colonnes représentent les prédicats obtenus dans l'étape 1. Elle est construite à partir de la matrice d'usage des prédicats. Chaque élément $aff(p_i, p_{i'})$ ($1 \le i, i' \le N$) de cette matrice peut avoir l'une des trois valeurs suivantes (contrairement à une matrice d'affinité des attributs qui possède seulement des valeurs numériques (voir chapitre 2)):

(a) **Numérique:** qui donne la somme des fréquences d'accès (que nous notons par $\lambda$) de toutes les requêtes utilisant simultanément les deux prédicats $p_i$ et $p_{i'}$. Si nous raisonons en fonction des n-uplets de la table T, cela signifie que les n-uplets satisfaisant les prédicats $p_i$ et $p_{i'}$ sont accédés simultanément par une ou plusieurs requêtes ayant une fréquence égale à $\lambda$ (voir Figure 6.3).

(b) **Non numérique:** qui peut être soit “ $\Rightarrow$ ”, “ $\Leftarrow$ ” ou “*”.

- “ $\Rightarrow$ ” ou “ $\Leftarrow$ ” signifient que le prédicat $p_i$ implique le prédicat $p_{i'}$ ou vice versa. Les n-uplets accédés par ces deux prédicats sont obligatoirement non disjoints (voir Figure 6.4).

- La valeur “ * ” indique la “similarité” entre deux prédicats $p_i$ et $p_j$. Deux prédicats $p_i$ et $p_{i'}$ sont similaires si les conditions suivantes sont satisfaites:

i. Les deux prédicats $p_i$ et $p_{i'}$ doivent être définis sur le même attribut,

ii. Ils doivent être utilisés avec un prédicat commun $p_{i''}$, et

iii. Le prédicat $p_{i''}$ doit être défini sur un attribut différent de celui utilisé par $p_i$ et $p_{i'}$.

**Exemple 23 (suite)** À partir de la matrice d'usages des prédicats de la Figure 6.2, la matrice d'affinité des prédicats est construite (voir Figure 6.5). Cette matrice contient 7 lignes et 7 colonnes autant que de prédicats. La valeur $aff(p_1, p_5)$ est égale à 20, la fréquence de $Q_1$ car $Q_1$, est la seule requête utilisée simultanément par $p_1$ et $p_5$. Cette matrice contient trois implications entre prédicats à savoir: $p_1 \Rightarrow p_2$, $p_3 \Rightarrow p_1$, $p_3 \Rightarrow p_2$. Notons que $p_1$ et $p_2$ sont similaires, et $p_3$ et $p_4$ le sont également.

4. **Le regroupement des prédicats:** dans cette étape, nous adaptons l'algorithmique de regroupement graphique développé pour la fragmentation verticale
<figure><img src="image_61.png" /><figcaption>FIG. 6.4: La signification de la valeur des implications</figcaption></figure>

<figure><img src="image_62.png" /><figcaption>FIG. 6.5: La matrice d'affinité des prédicats</figcaption></figure>

par Navathe et al. [NR89]. La structure de données principale utilisée est un graphe complet et étiqueté, appelé "graphe d'affinité des attributs". Les noeuds de ce graphe représentent les attributs, et une arête entre deux attributs représente la valeur d'affinité (qui est numérique) (voir le chapitre 2 pour le fonctionnement de cet algorithme). L'objectif principal est la formation des cycles qui généreront par la suite des fragments verticaux.

L'adaptation de cet algorithme dans le contexte de la fragmentation horizontale, est la prise en compte des valeurs non numériques et leurs effets sur le processus de regroupement. Pour ce faire, trois règles sont introduites:

(a) Une valeur numérique (sauf 0) a une plus grande priorité que les valeurs non numériques ("⇒", "<=" et "*"), lorsque nous explorons le graphe. En effet, le but de cet algorithme est le regroupement des prédicats ayant une grande affinité représentée par la fréquence d'accès.

(b) "⇒" et "<=" ont une plus grande affinité que "*", puisque ce dernier représente seulement une connectivité logique entre deux prédicats à travers leur usage avec un prédicat commun.

(c) Si $p_i \Rightarrow p_j$ alors $p_j$ a une plus grande priorité que $p_i$ et vice versa.

L'algorithme adapté part d'une matrice d'affinité des prédicats et construit un graphe complet et étiqueté appelé "graphe d'affinité des prédicats" GAP = ($V, E$). L'ensemble $V$ représente les prédicats de la matrice d'affinité des prédicats. Chaque arête $e(p_i, p_j)$ est étiquetée par un poids représentant une valeur d'affinité entre le prédicat $p_i$ et le prédicat $p_j$ (qui peut être, soit numérique, soit non numérique). Une fois le graphe d'affinité construit, les cycles peuvent
<figure><img src="image_63.png" /><figcaption>FIG. 6.6: Les ensembles de prédicats générés par l'approche graphique</figcaption></figure>

être formés comme décrits ci-après.

L'algorithme commence par sélectionner un noeud $p_i$ du graphe d'affinité d'une manière aléatoire. Ce noeud représentera le noeud de départ du cycle $C_1$ (c'est-à-dire, $C_1 = \{p_i\}$). Ensuite il essaye d'étendre le cycle $C_1$ en ajoutant d'autres noeuds. Pendant la phase d'extension d'un cycle, les arêtes ayant les valeurs d'affinités “⇒”, “⇔”, et “*” sont ignorées; en effet ces valeurs représentent des relations logiques implicites entre les prédicats et non pas l'affinité entre ces prédicats. Ces relations implicites sont utilisées pour réduire le nombre de fragments horizontaux.

Une fois le cycle formé, ses noeuds sont écartés, et nous réitérons la même procédure sur les autres noeuds afin de former d'autres cycles. À la fin de l'algorithme de regroupement, un ensemble de cycles $C = \{C_1, C_2, ..., C_γ\}$ est obtenu. Notons par *une composante* $P_i$ l'ensemble des noeuds du cycle $C_i$.

Le fonctionnement de cet algorithme de regroupement est présenté à travers l'exemple qui suit.

**Exemple 24 (suite)** le graphe d'affinité est construit à l'aide de la matrice d'affinité des prédicats (Figure 6.5). Il possède sept noeuds, et chaque arête est étiquetée par sa valeur d'affinité. Par exemple, l'arête entre $p_1$ et $p_5$ est libellée par 20 (voir Figure 6.6). Les arêtes ayant un poids nul ne sont pas représentées dans ce graphe pour des raisons de simplicité.

Le processus de regroupement commence par le noeud 1 qui représentera le noeud de départ du premier cycle $C_1$. En examinant la matrice d'affinité, nous ne trouvons qu'un seul prédicat $p_5$ ayant une grande affinité (numérique) avec $p_1$. Le cycle $C_1$ est donc augmenté par l'ajout de $p_5$. L'algorithme cherche toujours à étendre $C_1$, selon le même principe et le prédicat $p_2$ est ensuite sélectionné. À partir du prédicat $p_2$, nous ne pouvons pas inclure de nouveaux noeuds ayant une grande affinité (numérique), mais un cycle a été formé car le prédicat $p_1$ implique le prédicat $p_2$. Le cycle obtenu est: $C_1 = p_1, p_5, p_2, p_1$, dont sa composante est égale à $P_1 = \{p_1, p_2, p_5\}$. Le cycle $C_1$ est donc écarté en coupant ses éléments du reste des noeuds du graphe (voir Figure 6.6). L'algorithme réitère le processus de formation de cycle, en utilisant les noeuds restants du graphe.

Finalement, trois cycles $C_1, C_2$ et $C_3$ sont obtenus (voir Figure 6.6) dont les composantes sont: $P_1 = \{p_1, p_2, p_5\}$, $P_2 = \{p_3, p_6, p_7\}$, et $P_3 = \{p_4\}$.
5. **L'optimisation des composantes:** dans cette étape, nous optimisons chaque composante de cycle $C_i$ ($1 \le i \le \gamma$) (obtenu dans l'étape 4) en utilisant les implications entre ses prédicats (figurant dans la matrice d'affinité). S'il existe dans une composante, deux prédicats $p_i$ et $p_j$ tel que: $p_i \Rightarrow p_j$, alors le prédicat $p_i$ sera éliminé. Cette procédure pourrait réduire le nombre de prédicats de chaque composante $P_i$.

Tous les prédicats figurant dans les composantes sont appelés **les prédicats de fragmentation**. Les attributs figurant dans tous les prédicats de fragmentation sont appelés **attributs de fragmentation**. Soient $M$ et $r$ le nombre de prédicats et d'attributs de fragmentation. Nous notons par $M_i$ le nombre de prédicats de fragmentation définis sur l'attribut $A_i$ ($1 \le i \le r$).

**Exemple 25 (suite)** Les trois composantes obtenues dans l'étape 4 sont optimisées de la manière suivante:

- la composante $P_1$ contient initialement trois prédicats: $p_1, p_2$, et $p_5$. Notons que $p_1 \Rightarrow p_2$ (voir Figure 6.5), en conséquence, $P_1$ devient $P'_1 = \{p_2, p_5\}$.

- la composante $P_2$ contient trois prédicats chacun étant défini sur un attribut différent. Donc, cette composante reste inchangée.

- la dernière composante $P_3$ contient un seul prédicat ($p_4$), donc elle est inchangée.

L'ensemble de prédicats de fragmentation est: $\{p_2, p_3, p_4, p_5, p_6, p_7\}$. Les attributs de fragmentation correspondants aux trois composantes sont: l'Age, le Sexe et la Ville.

6. **La formation des minterms:** Notons que les composantes résultant de l'étape 5 peuvent ne pas couvrir tous les attributs de fragmentation. Par exemple, la composante $P_3$ de l'exemple 25 contient seulement un prédicat $p_4$ défini sur l'attribut de fragmentation Age, mais aucun prédicat défini sur les deux autres attributs de fragmentation (le Sexe et la Ville). Cette situation peut donner des fragments non disjoints et de grosse granularité (coarse grain). Pour aborder ce problème, la notion de complétude d'une composante est introduite.

**Définition 33** Une composante est dite complète si elle couvre tous les attributs de fragmentation. Elle est dite incomplète si elle couvre seulement une partie des attributs de fragmentation.

Le but de cette étape de l'algorithme *algo_affi horiz* est de garantir que toute composante de cycle soit complète.

Dans le cas où toutes les composantes issues de l'étape 5 sont complètes, nous passons directement à l'étape suivante qui va produire les fragments horizontaux.

Dans le cas contraire, nous devons **identifier** les composantes incomplètes afin de les rendre complètes. Pour ce faire, pour chaque composante $P_i$, nous sélectionnons l'ensemble des attributs de fragmentation ($T_i$) qui ne sont pas utilisés par cette dernière.