Pour réaliser cette sélection, une nouvelle matrice que nous appelons *matrice d'usage des attribute* est introduite. Les lignes et les colonnes de cette matrice représentent les composantes de cycles et les attributs de fragmentation, respectivement. Les valeurs des éléments de cette matrice sont binaires (1 ou 0). Chaque élément de cette matrice est défini de la manière suivante:

$$ (P_i, A_j) = \begin{cases} 1 & \text{si l'attribut de fragmentation } A_j \text{ appartient à la composante } P_i \\ 0 & \text{sinon} \end{cases} $$

Avec cette matrice, l'identification de l'ensemble $T_i$ est réalisée comme suit:

$$ T_i = \{A_j \mid 1 \le j \le r, (P_i, A_j) = 0\} $$

Soit $\Phi$ l'ensemble de toutes les composantes incomplètes.

Une fois la phase d'identification achevée, nous exécutons la procédure nommée *étendre une composante*. Cette procédure part d'une composante incomplète $P_i$ de $\Phi$. Pour chaque attribut $A_j \in T_i$, elle consiste à éclater cette composante en $M_j$ <fnref n="3" /> nouvelles composantes. Chaque nouvelle composante contient le(s) prédicat(s) actuels de $P_i$ **plus** l'un des prédicats définis sur $A_j$.

Les étapes principales de cette procédure sont décrites dans l'algorithme 10.

### Algorithme 10 étendre une composante incomplète

1. **Entrées:** une composante $P_i$ de $\Phi$

2. **for** Tout attribut $A_j \in T_i$ **do**

3. **Étendre** $P_i$ en $M_j$ nouvelles composantes, où chacune contient le(s) prédicat(s) existants de $P_i$ **plus** un prédicat défini sur $A_j$.

4. **end for**

**Exemple 26 (suite)** nous illustrons cette étape en reprenant les trois composantes résultants de l'étape 5: $P_1, P_2$, et $P_3$. Elles possèdent trois attributs de fragmentation: l'Age ($A_1$), le Sexe ($A_2$) et la Ville ($A_3$). La MUA contient alors trois lignes et trois colonnes, comme le montre la Figure 6.7. À partir de cette matrice, nous identifions facilement l'ensemble $T_i$ correspondant à chaque composante:

- La composante $P_1$ contient tous les attributs de fragmentation, à l'exception de l'attribut $A_3$. L'ensemble $T_1$ est égal à $\{A_3\}$.

- La composante $P_2$ contient tous les attributs de fragmentation. En conséquence, l'ensemble $T_2$ est égal à $\phi$.

- La composante $P_3$ contient un seul attribut de fragmentation ($A_1$). L'ensemble $T_3$ est égal à $\{A_2, A_3\}$.

Nous remarquons qu'il existe deux composantes incomplètes (correspondant à $T_1$ et $T_3$) et une complète (elle ne sera pas concernée par cette phase).

De ce fait, la procédure **étendre** est exécutée deux fois: une première fois pour la composante $P_1$ et une seconde pour la composante $P_3$. Commençons par la

<footnote n="3">³$M_j$ étant la cardinalité de l'ensemble de prédicats définis sur l'attribut $A_j$.</footnote>
<figure><img src="image_64.png" /><figcaption>FIG. 6.7: La matrice d'usage des attributs</figcaption></figure>

composante $P_1$, qui n'utilise pas l'attribut Ville. Sur ce dernier, un seul prédicat est défini, à savoir $p_7$: Ville = "Grenoble". Nous étendons $P_1$ en ajoutant ce prédicat. Une nouvelle composante $P_{11}$ est obtenue. Elle possède donc trois prédicats couvrant tous les attributs de fragmentation: $P_{11} = \{p_2, p_5, p_7\}$.

De manière similaire, la procédure étendre est appliquée sur la composante $P_3$. Deux attributs ne figurent pas dans cette composante: Sexe et Ville. Sur l'attribut Sexe, deux prédicats sont définis ($p_5$: Sexe = "M" et $p_6$: Sexe = "F"); de ce fait la composante $P_3$ est éclatée en deux nouvelles composantes $P_{31}$ et $P_{32}$, telles que: $P_{31} = \{p_4, p_5\}$, et $P_{32} = \{p_4, p_6\}$. Ces deux dernières ne couvrent pas non plus l'attribut Ville. Elles sont donc éclatées en ajoutant le prédicat $p_7$: Ville = "Grenoble". Nous obtenons donc deux composantes complètes $P_{31}$ et $P_{32}$ telles que:

$$P_{31} = \{p_4, p_5, p_7\}, P_{32} = \{p_4, p_6, p_7\}.$$

Finalement, nous obtenons quatre composantes complètes $P_1, P_2, P_3$, et $P_4$ définies comme suit:

$$P_1 = \{p_2, p_5, p_7\}, P_2 = \{p_3, p_6, p_7\}, P_3 = \{p_4, p_5, p_7\} \text{ et } P_4 = \{p_4, p_6, p_7\}.$$

7. **La formation des fragments horizontaux:** Soit $\Psi = \{P_1, P_2, \dots, P_\beta\}$ l'ensemble des composantes obtenues dans l'étape 6. Chaque composante génère un fragment. La clause de prédicat associé à un fragment est défini comme suit:

Si les prédicats d'une composante $P_i$ ($1 \le i \le \beta$) référencent le même attribut, nous lions ces prédicats par le connecteur logique OU, sinon par le connecteur logique ET.

De plus un fragment supplémentaire, que nous appelons ELSE est généré. Il représente la négation de la disjonction de toutes les clauses de prédicats définissant les $\beta$ fragments.

**Exemple 27 (suite)** L'ensemble $\Psi$ correspondant à notre exemple est égal à $\{P_1, P_2, P_3, P_4\}$. Étant donné que tous les prédicats de chaque composante sont définis sur des attributs différents, les prédicats sont liés par le connecteur logique ET. En conséquence, les fragments horizontaux générés par notre algorithme sont définis par les clauses de prédicats suivantes:

- Client_1 avec la clause $cl_1$: ($Age \le 40$) ∧ ($Sexe = 'M'$) ∧ ($Ville = "Grenoble"$)

- Client_2 avec la clause $cl_2$: ($Age = 18$) ∧ ($Sexe = 'F'$) ∧ ($Ville = "Grenoble"$)

- Client_3 avec la clause $cl_3$: ($50 \le Age \le 60$) ∧ ($Sexe = 'M'$) ∧ ($Ville = "Grenoble"$)
- Client_4 avec la clause cl₄ : (50 ≤ Age ≤ 60) ∧ (Sexe = ‘F’) ∧ (Ville = “Grenoble”)

- Client_5 avec la clause cl₅ : ¬(cl₁ ∨ cl₂ ∨ cl₃ ∨ cl₄).

Le fragment horizontal Client_5 représente la négation de la disjonction de toutes les clauses définies ci-dessus.

8. **La génération des fragments disjoints:** les fragments obtenus pourraient être non disjoints, car il n'y a aucune condition sur les prédicats de sélection définis dans les requêtes de départ. Les fragments horizontaux sont disjoints si leurs clauses sont mutuellement exclusives [KNM94, OV91]. L'objectif de cette étape est de raffiner les fragments non disjoints afin d'obtenir des fragments disjoints. Les fragments non disjoints sont donc combinés afin de former un seul fragment couvrant tous les n-uplets de ces fragments.

### 6.2.2 Complexité de l’algorithme des affinités

Notre algorithme étant constitué de huit étapes, nous décrivons la complexité de chacune d’elles:

- La complexité de la phase de construction de la matrice d’usage des prédicats est $O(n \times N)$, où $n$ et $N$ représentent le nombre des requêtes et des prédicats simples utilisés par ces dernières, respectivement.

- Notons que la matrice d’affinité des prédicats est carrée et symétrique. La complexité de sa construction est dans le pire des cas $O(N^2)$.

- L’algorithme de regroupement a une complexité de $O(N^2)$ [NR89].

- La phase d'optimisation teste chaque prédicat d'une composante, et vérifie l'existence d'une implication avec d'autres prédicats. Puisque nous avons $\gamma$ composantes, et $N$ prédicats, le pire des cas est $O(\gamma \times (N - 1))$.

- La phase de formation des minterms est basée sur la matrice d’usage des attributs qui a $\gamma$ lignes et $r$ colonnes. Sa complexité est $O(r \times \gamma)$.

- La complexité de la phase de formation et de génération des fragments disjoints est $O(\beta)$.

La complexité totale de cet algorithme est: $O(n \times N + N^2)$. Rappelons que les algorithmes basés sur la complétude et la minimalité (voir Chapitre 2) ont une complexité de $O(2^n)$.

### 6.2.3 Les règles de correction

L’algorithme que nous avons proposé vérifie les trois règles de correction: la complétude, la reconstruction, et la disjonction.

- La complétude est assurée par l’ajout du fragment ELSE qui contient tous les n-uplets ne satisfaisant pas les prédicats des autres fragments.

- La reconstruction est évidente, elle est réalisée par l'opération d'union.

- La disjonction est assurée par l'étape 8 de l'algorithme (génération des fragments disjoints).
### 6.2.4 Bilan de cette section

L'algorithme algo\_aff\_horiz que nous venons de présenter a une complexité poly-
nômiale, ce qui est raisonnable par rapport aux algorithmes basés sur la complétude
et la minimalité des prédicats de sélection (voir Chapitre 2). Notons que le seul
critère de regroupement utilisé par cet algorithme est "la fréquence d'accès des
requêtes". Ce genre d'algorithmes a été développé dans le contexte des bases de
données réparties [CP84, OV91, NR89, NKR95, BKS97] dans lequel la fréquence
d'accès des requêtes sur des sites est considérée comme un *paramètre essentiel*. Le
contexte réparti n'est pas le seul domaine d'application de la fragmentation, qui
peut être également utilisée dans un contexte centralisé pour minimiser le coût des
requêtes [Ora99].

Qui dit minimisation du coût d'exécution des requêtes, dit prise en considération de tous les paramètres physiques utilisés par l'optimiseur de requêtes. Ces paramètres contribuent fortement à l'amélioration ou à la dégradation des performances des requêtes. Par exemple, dans l'environnement des entrepôts de données, des paramètres comme la taille des vues matérialisées, la taille des index (de jointure), la taille de la mémoire centrale, etc. ont une incidence importante sur l'accélération des requêtes. Dans certaines applications, nous pouvons avoir des requête moins fréquentes, mais dont les coûts d'exécution sont très élevés.

Tout algorithme de fragmentation (horizontale, verticale et mixte) devrait prendre en considération des paramètres physiques, ce qui n'est malheureusement pas le cas des algorithmes de la fragmentation horizontale basés sur les affinités, la complétude et la minimalité des prédicats.

Dans la section suivante, nous nous attachons donc à développer un *nouveau type d'algorithme* prenant en compte les paramètres physiques de l'entrepôt.

## 6.3 Les algorithmes dirigés par un modèle de coût

Dans cette section, un nouveau type d'algorithme basé sur un modèle de coût est présenté. Grâce à ce modèle de coût, il est possible d'évaluer la qualité de la solution fournie par les algorithmes de la fragmentation horizontale basés sur les affinités, la complétude et la minimalité des prédicats. Il peut également être utilisé pour définir d'autres algorithmes de fragmentation. Deux algorithmes de ce type sont développés: (1) un *algorithme exhaustif* et (2) un *algorithme approximatif*.

### 6.3.1 Motivations

Un modèle de coût est la composante principale d'un optimiseur physique d'une
base de données [Gru96]. Recenser les modèles de coût n'est pas une chose aisée
[Gru96], car il n'existe pas un modèle unique mais une multitude de modèles adaptés
à des systèmes très particuliers. Les modèles de coût peuvent avoir plusieurs rôles:

- *Choisir le meilleur plan d'exécution pour une requête donnée:* L'optimisation des requêtes se déroule en deux phases principales pour traduire la requête initiale dans un langage de plus en plus proche du système d'exécution [Naa99].
Ces deux phases sont l'optimisation logique et l'optimisation physique. La première phase traduit la requête dans l'algèbre de l'optimiseur pour la représenter sous la forme d'un plan d'exécution, arrange la requête sous une forme normalisée en employant des règles de normalisation, puis applique plusieurs transformations algébriques au moyen de règles de transformation pour produire l'espace de recherche correspondant à la requête. La deuxième phase, génère le plan d'exécution optimal parmi les nombreux plans possibles pour exécuter la requête. La génération de ce plan est réalisée en s'appuyant sur un modèle de coût.

Ce processus d'optimisation est complexe et a fait l'objet de nombreux travaux [Gra93].

- *Outil pour l'optimisation dynamique (adaptative) des requêtes:* Dès qu'il y a des changements au niveau des paramètres sur lesquels l'optimiseur sélectionne les plans optimaux d'une requête, le modèle de coût peut être utilisé pour trouver de nouveaux plans. Une technique utilisée pour répondre à ces changements est la méthode de seuil dans laquelle la reformulation du plan de requête intervient seulement lorsque le coût de la requête dépasse un certain seuil fixé par l'administrateur [Naa99].

- *Guider les algorithmes de recherche et de sélection:* dans les bases de données ou les entrepôts de données, nous trouvons plusieurs problèmes d'optimisation ou de sélection difficiles à résoudre. Deux bons exemples sont les problèmes de sélection des vues et des index (voir Chapitre 2 et 3). Pour les résoudre, nous disposons d'heuristiques qui sont guidées par des modèles de coût (voir chapitre 2).

Comme nous le constatons, les modèles de coût jouent un rôle essentiel dans l'optimisation des requêtes, ce qui nous amène à les utiliser pour définir de bons algorithmes de fragmentation horizontale.

Les modèles de coût reposent généralement sur trois composantes (voir Chapitre 3): (1) des statistiques des données stockées dans la métabase, (2) des formules pour évaluer la cardinalité des résultats intermédiaires, (3) et des formules pour évaluer le coût des requêtes.

### 6.3.2 Le modèle de coût et les algorithmes de fragmentation

Pour introduire notre approche, nous considérons un schéma en étoile d'un entrepôt de données <fnref n="4" />. Soit $T(K, A_1, A_2, ..., A_l)$ la table de dimension d'un entrepôt à fragmenter, et $Q$ l'ensemble des requêtes les plus fréquemment utilisées.

Les composantes principales de ce type d'algorithmes sont: (i) un générateur de schémas de fragmentation, (ii) un modèle de coût, et (iii) la sélection du schéma de fragmentation optimal (voir la Figure 6.8).

<footnote n="4">⁴Les algorithmes que nous proposons peuvent être appliqués sur tout schéma de base de données (relationnelle ou objet), ou des schémas d'entrepôts de données autre que ROLAP (schéma en flocon de neige, schéma en constellation, etc.)</footnote>
<figure><img src="image_65.png" /><figcaption>FIG. 6.8: Les principales composantes des algorithmes dirigés par un modèle de coût</figcaption></figure>

- **Le générateur de schémas de fragmentation:** Les fragments horizontaux sont obtenus à partir des prédicats de sélection des requêtes définies sur la table à fragmenter (voir section 6.2).

Le générateur de schémas de fragmentation consiste à générer tous les schémas de fragmentation possibles de la table *T* en utilisant les minterms obtenus à partir des prédicats de sélection définis sur *T*.

- **Le modèle de coût:** Il constitue le noyau de ce type d'algorithmes. Le modèle de coût peut être vu comme une fonction d'une seule variable représentant le schéma de fragmentation $S_i$ et attribuant le coût d'exécution d'un ensemble de requêtes à ce schéma $C(S_i)$. L'unité de mesure du coût dépend de l'objectif de l'optimisation. Dans notre contexte, l'unité de mesure est le nombre d'entrées-sorties. L'optimalité et la qualité des solutions obtenues par ces algorithmes sont liées à ce modèle de coût. En conclusion, le modèle de coût doit être précis et prendre en compte les paramètres importants déterminés par l'administrateur de la base.

- **La sélection du schéma de fragmentation optimal:** Elle consiste à déterminer le schéma de fragmentation garantissant la meilleure performance parmi tous les schémas possibles.

Dans les sections suivantes, nous allons voir en détail les fonctionnalités de chaque composante.

### 6.3.3 Le générateur de schémas

Rappelons qu'un schéma de fragmentation représente le résultat du processus de fragmentation. Un schéma de fragmentation *S* d'une table *T* ayant *m* fragments horizontaux {*F*₁, *F*₂, ..., *F*ₘ} est dénoté par: $S : ( (F₁ : cl₁), (F₂ : cl₂), ..., (Fₘ :}$
<figure><img src="image_66.png" /><figcaption>FIG. 6.9: Les étapes du processus de génération des schémas de fragmentation</figcaption></figure>

$cl_m)$), où chaque fragment $F_i$ ($1 \le i \le m$) est défini par une clause de prédicats $cl_i$.

Le processus de génération de tous les schémas de fragmentation possibles est réalisé en trois étapes principales (voir Figure 6.9): (1) l'énumération de l'ensemble des prédicats simples, (2) la génération de l'ensemble des minterms, et (3) la combinaison de minterms.

1. **L'énumération de l'ensemble des prédicats simples:** Comme dans l'étape 1 de l'algorithme des affinités de la section 6.2, nous énumérons l'ensemble de tous les prédicats de sélection définis sur la table $T$, à savoir $\Pi = \{p_1, p_2, ..., p_N\}$. Ces prédicats doivent être minimaux et mutuellement exclusifs [OV91].

2. **La génération des minterms:** À partir des prédicats de l'ensemble $\Pi$, l'ensemble de tous les minterms $M$ est généré de la manière suivante:

$M = \{m_i | m_i = \bigwedge_{p_k \in \Pi} p_k^*\}$, avec $p_k^* = p_k$ ou $p_k^* = \neg p_k$.

3. **La combinaison des minterms:** Si nous faisons l'analogie entre les minterms et les fragments d'un schéma de fragmentation, nous pouvons dire qu'un minterm est une clause d'un fragment horizontal (voir l'étape 6 de l'algorithme de la section 6.2), d'où la propriété suivante.

**Propriété 2** *Un minterm forme un fragment horizontal potentiel.*

La combinaison des minterms se fait à l'aide de la propriété suivante:

**Propriété 3** *Une combinaison de minterms obtenue par l'opérateur de disjonction (OU dénotée par $\vee$) forme un fragment horizontal potentiel.*

En conséquence, le nombre de tous les schémas de fragmentation possibles d'une table donnée est le nombre de toutes les combinaisons possibles de minterms.

**Exemple 28** *Pour illustrer les trois étapes du processus de génération de schémas de fragmentation, considérons l'exemple suivant:*
Supposons que nous ayons six prédicats simples et disjoints {$p_1, p_2, ..., p_6$} définis sur la table de dimension CLIENT (voir Table 6.1). Les minterms de prédicats générés

<table><caption>TAB. 6.1: Les six prédicats</caption><thead><tr><td>Prédicats</td><td>Description</td></tr></thead><tbody><tr><td>$p_1$</td><td>Age ≤ 40</td></tr><tr><td>$p_2$</td><td>Age > 40</td></tr><tr><td>$p_3$</td><td>Sexe = 'M'</td></tr><tr><td>$p_4$</td><td>Sexe = 'F'</td></tr><tr><td>$p_5$</td><td>Ville = "Grenoble"</td></tr><tr><td>$p_6$</td><td>Ville = "Paris"</td></tr></tbody></table>

à partir de ces prédicats sont:

- $m_1$: ($Age \le 40$) ∧ ($Sexe$ = 'M') ∧ ($Ville$ = "Grenoble"),

- $m_2$: ($Age \le 40$) ∧ ($Sexe$ = 'M') ∧ ($Ville$ = "Paris"),

- $m_3$: ($Age \le 40$) ∧ ($Sexe$ = 'F') ∧ ($Ville$ = "Grenoble"),

- $m_4$: ($Age \le 40$) ∧ ($Sexe$ = 'F') ∧ ($Ville$ = "Paris"),

- $m_5$: ($Age > 40$) ∧ ($Sexe$ = 'M') ∧ ($Ville$ = "Grenoble"),

- $m_6$: ($Age > 40$) ∧ ($Sexe$ = 'M') ∧ ($Ville$ = "Paris"),

- $m_7$: ($Age > 40$) ∧ ($Sexe$ = 'F') ∧ ($Ville$ = "Grenoble"),

- $m_8$: ($Age > 40$) ∧ ($Sexe$ = 'F') ∧ ($Ville$ = "Paris"),

Parmi les $2^6$ minterms possibles, nous avons éliminé ceux qui sont contradictoires, par exemple: $p_1 \land p_2 \land p_3 \land p_4 \land p_5 \land p_6$. Les minterms résultats sont appelés les minterms primitifs.

Chaque minterm primitif $m_i$ ($1 \le i \le 8$) définit un fragment possible. Si c'est le cas, nous aurons un schéma de fragmentation de huit fragments (ce qui représente le même schéma obtenu par l'algorithme dirigé par la complétude et la minimalité des prédicats [OV91]). Si nous combinons par exemple, deux minterms primitifs $m_1$: ($p_1 \land p_3 \land p_5$) et $m_2$: ($p_1 \land p_3 \land p_6$) par l'opérateur logique OU, nous obtenons le minterm suivant:

($p_1 \land p_3 \land p_5$) ∨ ($p_1 \land p_3 \land p_6$) = ($p_1 \land p_3$) ∧ ($p_5 \lor p_6$) = ($p_1 \land p_3$) qui définit un autre fragment potentiel. Ce minterm avec les six autres minterms ($m_3, m_4, m_5, m_6, m_7, m_8$) forment un schéma de fragmentation de sept fragments.

Notre objectif est de générer tous les schémas de fragmentation possibles d'une table donnée $T$. On peut s'interroger sur leur nombre. Nous donnons ci-après une approche pour leur dénombrement et donc aussi leur génération.

Soient $N$ le nombre de prédicats simples définis dans les $n$ requêtes de départ, $Z$ ($Z \le 2^N$) le nombre de minterms primitifs générés à partir des $N$ prédicats. D'après les propriétés 2 et 3, le nombre total de tous les schémas de fragmentation possibles obtenus à partir des $Z$ minterms primitifs est donné par le théorème suivant:
**Théorème 2** Soit Z le nombre de minterms générés à partir des N prédicats. Alors le nombre L de tous les schémas possibles pour une fragmentation horizontale de la table T est donné par:

$$L = \sum_{k=1}^{Z} L_{Z}^{k} \qquad (6.1)$$

où : $L_Z^k$ représente le nombre de tous les schémas de fragmentation définis à partir de Z minterms et ayant k fragments.

$$L_{Z}^{k} = k * L_{Z-1}^{k} + L_{Z-1}^{k-1} \qquad (6.2)$$

**Preuve 2** On a $L_0^1 = 0$ et $L_1^1 = 1$. Les équations 6.1 et 6.2 sont vraies pour $Z = 1$ et $k = 1$ à condition de supposer que $L_0^0 = 1$. On remarque également que $L_Z^1 = 1$, $\forall Z \in \mathbb{N}$ et que $L_Z^k = 0, \forall Z \in \mathbb{N}$ et $k > Z$. Les équations 6.1 et 6.2 sont donc vraies pour $k = 1, \forall Z \in \mathbb{N}$.

Nous allons démontrer ces équations par récurrence. Nous supposons que 6.1 est vraie pour $Z \le j$ et 6.2 est vraie pour tout $k \le j$. Nous allons montrer qu'elles sont vraies pour $Z = j + 1$.

Les schémas de fragmentation à $j + 1$ minterms et $k$ partitions peuvent être obtenus de deux façons différentes à partir des schémas à $j$ minterms:

- Ajouter un minterm à chacun des $L_j^k$ schémas de $k$ partitions avec $j$ minterms. Cela revient à ajouter un minterm à l'une des partitions de chacun de ces schémas (le nombre de partitions doit rester le même). Il y a $k \times L_j^k$ façons différentes de le faire.

- Ajouter une partition construite sur l'unique minterm supplémentaire à chacun des $L_j^{k-1}$ schémas de $k-1$ partitions avec $j$ minterms. Il y a $L_j^{k-1}$ façons différentes de le faire.

On a donc : $L_j^{k+1} = k * L_j^k + L_j^{k-1}$

Enfin les deux équations sont vraies pour $Z = j + 1$ et $k > j + 1$, ce qui achève la démonstration.

**Exemple 29** Soient $m_1$ et $m_2$ deux minterms, à partir desquels, deux schémas de fragmentation $S_1$ et $S_2$ peuvent être générés. Ils sont définis comme suit:

$S_1 : (F_1 : m_1 \lor m_2)$, et $S_2 : \left( (F'_1 : m_1), (F'_2 : m_2) \right)$, tels que: $L_2^1 = 1$ et $L_2^2 = 1$.

Maintenant notre but est de générer les schémas de fragmentation pour les trois minterms $m_1, m_2$ et $m_3$ à partir des schémas précédents.

D'après le théorème, nous devons calculer $L_3^1, L_3^2$, et $L_3^3$. $L_3^1$ représente des schémas avec un seul fragment. Il est obtenu à partir du schéma $S_1$, en incluant le minterm $m_3$ à $S_1$, en conséquence nous aurons $S'_1 : (F_{11} : m_1 \lor m_2 \lor m_3)$. Le schéma de fragmentation avec trois fragments $L_3^3$ est généré en considérant le minterm $m_3$ comme un seul fragment qui sera regroupé avec $S_2$, nous aurons donc $S'_2 : (F_{21} : m_1), (F_{22} : m_2), (F_{23} : m_3)$.
Les schémas ayant deux fragments ($L_3^2$) sont générés de la manière suivante: pre-mièrement à partir de $S_2$, nous pouvons générer deux schémas, en incluant $m_3$ dans le premier fragment de $S_2$ ($m_1$) et nous aurons $S'_3 : (F_{31} : m_1 \lor m_3), (F_{32} : m_2)$, ou en incluant $m_3$ dans la deuxième fragment de $S_2$, et nous aurons le schéma $S'_4$ défini comme suit: $S'_4 : ((F_{41} : m_1), (F_{42} : m_2 \lor m_3))$.

Cela correspond au premier terme de l'équation 6.2. Le dernier schéma est généré en considérant le minterm $m_3$ comme un fragment que nous regroupons avec $S_1$, nous aurons donc $S'_5 : ((F_{51} : m_1 \lor m_2), (F_{52} : m_3))$ qui correspond au second terme de la partie droite l'équation 6.2.

Finalement, le nombre de schémas construits à partir de trois minterms est 5.

À ce stade, tous les schémas de fragmentation possibles d'une table donnée peuvent être générés. Maintenant, il nous faut évaluer le meilleur schéma de fragmentation. Cette évaluation est assurée par le modèle de coût.

### 6.3.4 Le modèle de coût

Le modèle de coût décrit dans le chapitre précédent pour un entrepôt fragmenté peut être complètement réutilisé ici.

Nous avons maintenant tous les ingrédients pour décrire deux algorithmes dirigés par un modèle de coût, à savoir: (i) l'algorithm exhaustif et (ii) l'algorithm approximation.

### 6.3.5 L'algorithm exhaustif

#### 6.3.5.1 Description de l'algorithm

Soit $D_i$ une table de dimension du schéma en étoile SED à fragmenter. Rappelons que sur cette table, nous considérons un ensemble de requêtes ($Q = \{Q_1, Q_2, ..., Q_n\}$), où chaque requête $Q_j$ possède une fréquence d'accès $fr_j$.

Cet algorithme consiste à énumérer d'une manière exhaustive tous les schémas de fragmentation possibles de $D_i$ (voir section 6.3.3). À l'aide du modèle de coût, un coût d'exécution pour l'ensemble de requêtes Q est attribué à chaque schéma de fragmentation $S_i$ ($1 \le i \le L$). Ce coût est dénoté par $CT(S_i)$. Finalement, le schéma de fragmentation offrant le coût minimum est sélectionné (voir l'algorithm de la Figure 11). Ce schéma est noté par $S_{min}$, et satisfait la condition suivante:

$$CT(S_{min}) = \min\{CT(S_i) \mid S_i \in S_{D_i}\}$$

#### 6.3.5.2 La correction de l'algorithm exhaustif

Etant donné que les prédicats de sélection utilisés dans cet algorithme sont complets, les fragments résultants le sont également [OV91]. La reconstruction est réalisée par l'opération d'union. Finalement, la disjonction est assurée par le fait que les prédicats sont mutuellement exclusifs.
**Algorithm 11** La description de l'algorithmme exhaustif

1: **coût_min:=** +∞ {ce coût représente le coût de schéma optimal}

2: **for** i := 1 to *L* {*L*: le nombre de schémas de fragmentation possibles} **do**

3: $CT(S_i):=0$;

4: **end for**

5: **for** i:= 1 to *L* **do**

6: &nbsp;&nbsp;&nbsp;&nbsp;**for** j := 1 to *n* {cette boucle parcours toutes les requêtes} **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CT(*S*<sub>*i*</sub>) := CT(*S*<sub>*i*</sub>) + CT(*Q*<sub>*j*</sub>) * fr<sub>*j*</sub>;

8: **end for**

9: **if** CT(*S*<sub>*i*</sub>) < coût_min **then**

10: coût_min:= CT(*S*<sub>*i*</sub>);

11: min := *i*;

12: **end if**

13: **end for**

14: Schéma_optimal:= *S*<sub>min</sub> {le schéma ayant le rang égal à "min"}

### 6.3.5.3 Avantages et inconvénients de l'algorithmme exhaustif

De par sa nature exhaustive, cet algorithme fournit un schéma de fragmentation optimal (optimalité relative au modèle de coût).

La complexité de cet algorithme est tirée de l'étape 5 de l'algorithmme 11 qui consiste à parcourir tous les schémas de fragmentation et à calculer pour chaque schéma le coût d'exécution de l'ensemble des requêtes. En conséquence la complexité de cet algorithme est $O(n \times L)$, où *n* et *L* représentent le nombre de requêtes et le nombre de tous les schémas de fragmentation possibles, respectivement.

Le nombre de schémas de fragmentation *L* est très élevé. Pour un petit nombre de minterms, ce nombre est raisonnable, mais pour un grand nombre de minterms, il devient très important. Par exemple, pour 15 minterms, le nombre de schémas de fragmentation est 1 382 958 545 (voir la Table 6.2). Notons que 15 minterms peuvent être facilement obtenus à partir de 4 prédicats simples, ce qui est peu pour une application réelle. Dans les entrepôts de données, les requêtes décisionnelles possèdent beaucoup de prédicats de sélection [DRT99]; cet algorithme n'est donc pas praticable dans les cas réels.

Dans la section suivante, nous présentons un autre algorithme appelé approximatif qui surmonte les difficultés de ce premier algorithme.
<table><caption>TAB. 6.2: La complexité du nombre de schémas</caption><thead><tr><th>Minterms</th><th>Nombre de schémas</th><th>Borne inférieure des schémas</th><th>Borne supérieure des schémas</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>0.5</td><td>1</td></tr><tr><td>2</td><td>2</td><td>1.167</td><td>2</td></tr><tr><td>3</td><td>5</td><td>4</td><td>12</td></tr><tr><td>4</td><td>15</td><td>11.336</td><td>32</td></tr><tr><td>5</td><td>52</td><td>49.5</td><td>607.5</td></tr><tr><td>6</td><td>203</td><td>148.5</td><td>2187</td></tr><tr><td>7</td><td>877</td><td>586.7</td><td>57344</td></tr><tr><td>8</td><td>4140</td><td>2347.01</td><td>262144</td></tr><tr><td>9</td><td>21147</td><td>8646.88</td><td>8.78906e+06</td></tr><tr><td>10</td><td>115975</td><td>43234.4</td><td>4.88281e+07</td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>.</td><td>.</td><td>.</td><td>.</td></tr><tr><td>15</td><td>13682958545</td><td>7.09592e+07</td><td>2.63883e+14</td></tr></tbody></table>

# 6.4 L'algorithme approximatif

## 6.4.1 Les étapes de l'algorithme

Pour éviter l'énumération exhaustive de tous les schémas possibles de fragmentation d'une table *T*, nous développons un algorithme, que nous appelons *approximatif*. Approximatif signifie que la solution obtenue par l'heuristique n'est pas forcément optimale, mais plutôt quasi-optimale.

Nous rappelons que si le nombre de minterms générés par les prédicats simples des requêtes est faible, alors l'algorithme exhaustif est utilisé, sinon, l'algorithme approximatif est utilisé. Cet algorithme est basé sur la technique de l'escalade (hill-climbing dans l'appellation anglo-saxonne) et un modèle de coût. Pour amorcer ce type d'algorithme, il faut une solution initiale. Ensuite l'algorithme effectue des changements graduels sur cette solution pour se rapprocher d'un *but*. La solution initiale doit avoir une complexité raisonnable. Le but est déterminé par une fonction objectif que nous désirons maximiser ou minimiser.

Toute technique de hill-climbing nécessite trois éléments principaux [Jai91]: (1) *une solution initiale*, (2) *un mécanisme d'amélioration*, et (3) *un test d'arrêt*. Plus précisément un algorithme de type hill-climbing se déroule selon le schéma suivant [Jai91]:

1. Générer une solution initiale

2. Calculer le bénéfice de la solution initiale

3. Modifier la solution initiale

4. Calculer le bénéfice de la nouvelle solution

5. Si le bénéfice de la nouvelle solution est supérieur alors en faire la solution initiale et reprendre l'étape 2;
<figure><img src="image_67.png" /><figcaption>FIG. 6.10: Le mécanisme d'amélioration du schéma initial</figcaption></figure>

6. Sinon, arrêt.

Dans les sections suivantes, nous allons expliciter chacune de ces étapes.

6.4.2 La détermination de la solution initiale

Le choix de la solution initiale contribue fortement à la qualité de la solution
finale obtenue par l’algorithme approximatif. Dans notre cas, la solution intiale est
le résultat de l’exécution de l’algorithme basé sur les affinités présenté dans la section
6.2. Nous optons pour ce choix car la complexité de cet algorithme est polynômiale.
Soit $S_{affi}$ le schéma de fragmentation obtenu par cet algorithme. Notons que les
fragments de $S_{affi}$ sont disjoints. Le schéma $S_{affi}$ est un élément de l’ensemble de
tous les schémas de fragmentation possibles de la table T (voir Figure 6.10). Le
schéma $S_{affi}$ pourrait être la solution optimale obtenue par l’algorithme exhaustif,
mais cela est peu probable. L’objectif de l’algorithme approximatif est de rapprocher
le schéma $S_{affi}$ autant que possible du schéma optimal. Ce rapprochement est décrit
dans la section suivante.

6.4.3 Un mécanisme d'amélioration de la solution initiale

La phase d'amélioration prend la solution initiale et essaye de la rapprocher le
plus possible du schéma optimal (voir Figure 6.10) en effectuant des opérations sur
la solution initiale. Dans notre cas, deux opérations sont définies sur les fragments
du schéma initial $S_{affi}$ qui sont: (1) assembler deux fragments, et (2) éclater un
fragment.

La première opération consiste à fusionner deux fragments en un seul. Elle res-
semble à l'opération **migration de tous les n-uplets** d'un fragment vers l'autre lors des
mises à jour. Ce genre d'opérations a été largement utilisé dans le partitionnement
des graphes [KL70] et les algorithmes d'allocation des fragments dans un système
distribué [BKL98c, KP97].

La deuxième opération est l'inverse de la première: elle éclate un fragment en plu-
sieurs. Cette dernière augmente le nombre de fragments et en conséquence diminue
la taille de chaque fragment.

L'intuition qui est derrière ces deux opérations provient de la propriété 3, c'est à dire, la combinaison de deux ou plusieurs minterms représentant un fragment.

Nous connaissons le principe de base de ces deux opérations, mais la question qui reste posée est de savoir quels fragments sont des candidats pour ces opérations? Pour répondre à cette question, nous devons trouver une technique de représentation des fragments. Cette technique fera l'objet de la section suivante.

### 6.4.3.1 Une représentation des fragments horizontaux

Les prédicats simples que les algorithmes de fragmentation utilisaient jusqu'à présent sont de la forme suivante [CP84, OV91, BKB98, BKA00, BKL98b]:

Attribut $\theta$ Valeur, avec $\theta \in \{=, <, \le, >, \ge, \ne\}$.

Nous considérons un autre type de prédicats appelés *prédicats de domaine* utilisés dans le système OSIRIS [SS94, SS89].

**Définition 34** *Un prédicat sur le domaine d'un attribut attr ou prédicat de domaine, est un prédicat de la forme :*

$P(attr) : attr \in Domaine$,

où attr et Domaine représentent l'attribut sur lequel le prédicat est défini et un intervalle ou un ensemble de valeurs énumérées, respectivement.

**Remarque :** Les *prédicats simples* que les algorithmes de fragmentation utilisent se présentent comme un cas particulier de prédicats de domaine. Le prédicat *Sexe* = 'M' peut aussi s'écrire en un prédicat de domaine : *Sexe* ∈ {'M'}.

**Définition 35** *Une partition d'un ensemble non vide E est une collection de sousensembles disjoints non vides de A tel que leur union est l'ensemble A lui-même [SM77]. Un élément d'une partition est appelé un bloc.*

L'analyse des clauses représentant les fragments horizontaux permet d'effectuer une partition du domaine des attributs de fragmentation en sous-domaines appelés sous-domaines stables [SS94]. Les éléments de cette partition sont déterminés par les prédicats de domaine. Ils sont désignés par cette appellation, compte tenu de la "stabilité" de la valeur de vérité de tous les prédicats de domaine d'un attribut lorsque cet attribut change de valeur en restant dans le même bloc de la partition.

**Exemple 30** *Pour montrer comment les prédicats de fragmentation définissent des partitions de chaque domaine des attributs de fragmentation, reprenons les fragments horizontaux de la table de dimension CLIENT générés par l'algorithme des affinités. Supposons que les domaines des attributs de fragmentation (qui sont l'Age, le Sexe, et Ville) sont:*

$$- \text{Dom(Age)} = [0, 120]$$

$$- \text{Dom(Sexe)} = \{\text{'M'}, \text{'F'}\},$$

$$- \text{Dom(Ville)} = \{\text{"Grenoble"}, \text{"Paris"}\}.$$

Les partitions des trois attributs de fragmentation engendrés par la clause de chaque fragment sont obtenues comme suit:
<figure><img src="image_68.png" /><figcaption>FIG. 6.11: Les SDSs des attributs de fragmentation</figcaption></figure>

<figure><img src="image_69.png" /><figcaption>FIG. 6.12: Un exemple de représentation de fragments dans le cas de deux attributs</figcaption></figure>

- Sur l'attribut *Age*, trois prédicats simples sont définis: $p_1$: $Age \le 40$, $p_2$: $Age = 20$, et $p_3$: $50 \le Age \le 60$. Ces prédicats peuvent facilement être transformés en prédicats de domaine: $p_1$: $Age \in ]0, 40]$, $p_2$: $Age \in [20, 20]$, et $p_3$: $Age \in [50, 60]$.

Le domaine de définition de l'attribut *Age* ([0, 120]) est donc partitionné en six SDSs par les trois prédicats ($p_1$, $p_2$, et $p_3$) de la manière suivante:

$Dom(Age) = d_{11} \cup d_{12} \cup d_{13} \cup d_{14} \cup d_{15} \cup d_{16}$, avec $d_{11} = ]0, 20[, d_{12} = [20, 20]$, $d_{13} =]20, 40[, d_{14} = [40, 50[, d_{15} = [50, 60], d_{16} =]60, 120]$,

- D'une manière similaire, le domaine de l'attribut *Sexe* est partitionné en deux SDSs: $Dom(Sexe) = d_{21} \cup d_{22}$, avec $d_{21} = \{'M'\}$, $d_{22} = \{'F'\}$

- Finalement, l'attribut *Ville* est partitionné en deux SDSs: $Dom(Ville) = d_{31} \cup d_{32}$, avec $d_{31} = \{"Grenoble"}$ et $d_{32} = \{"Paris"}$.

Les différents SDSs de chaque attribut de fragmentation sont représentés par la Figure 6.11.

Maintenant, nous allons voir l'utilité des SDSs dans la représentation des fragments horizontaux.

Soit $T(K, A_1, A_2, ..., A_l)$ une table de $l$ attributs dont $r$ sont des attributs de fragmentation ($r \le l$). Ces derniers forment un n-uplet ($attr_1, attr_2, ..., attr_r$), où chaque $attr_i$ possède $n_i$ SDSs dénoté par le n-uplet ($d_{i1}, d_{i2}, ..., d_{in_i}$).

Chaque fragment horizontal est valide dans un ou plusieurs SDSs d'un attribut de
fragmentation. Les SDSs valides et invalides sont marqués par 1 et 0, respectivement. En conséquence chaque fragment $F_j$ peut être représenté par un vecteur (que nous appelons *vecteur de fragmentation*) de la manière suivante:

$$F_i := ((d_{11}, d_{12}, \dots, d_{i n_1}); (d_{21}, d_{22}, \dots, d_{2n_2}); (d_{N_1}, d_{N_2}, \dots, d_{N_{n_N}})).$$

Les petites parenthèses représentent les SDSs de chaque attribut de fragmentation ($A_k$), que nous appelons *éléments du sous-vecteur* $F_{jk}$ de $F_j$. Le point virgule ($;$) est utilisé pour séparer les éléments. Cette représentation ressemble à un index binaire.

**Exemple 31** Les cinq fragments de la table de dimension CLIENT obtenus par l'algorithme des affinités (voir section 6.2) sont représentés de la façon suivante:

Client_1: ((1, 1, 1, 0, 0, 0); (1, 0); (1, 0))

Client_2: ((0, 1, 0, 0, 0, 0); (0, 1); (1, 0))

Client_3: ((0, 0, 0, 0, 1, 0); (1, 0); (1, 0))

Client_4: ((0, 0, 0, 0, 1, 0); (0, 1); (1, 0))

Client_5: ((1, 0, 0, 0, 0, 1); (1, 0); (0, 1))

Chaque fragment est représenté par un vecteur de 3 éléments (chacun correspondant à un attribut de fragmentation). Le premier correspond à l'attribut Age, le deuxième à l'attribut et le dernier à l'attribut Ville. Nous définissons la cardinalité de chaque élément par le nombre de SDSs correspondant à l'élément.

Graphiquement, les fragments peuvent être représentés par un hypercube dont les dimensions correspondent aux attributs de fragmentation. Considérons par exemple, deux attributs de fragmentation $attr_1$ et $attr_2$ possédant 4 et 3 SDSs, respectivement. Les fragments engendrés par ces SDSs sont représentés dans un espace bidimensionnel (plan) comme le montre la Figure 6.12. Si nous avons trois attributs de fragmentation $attr_1$, $attr_2$ et $attr_3$, les fragments sont représentés dans un espace tridimensionnel (cube) comme le montre la Figure 6.13.

**Définition 36** La distance de Hamming $dist(X, Y)$ entre deux vecteurs binaires: $X = (x_1, x_2, \dots, x_k)$ et $Y = (y_1, y_2, \dots, y_k)$ représente le nombre de positions dans lesquelles $X$ et $Y$ sont différents [PH89].

Étant donné que les fragments horizontaux sont représentés par des vecteurs binaires, la distance de Hamming entre fragments peut être facilement calculée. Par exemple, la distance de Hamming entre le fragment Client_1 et le fragment Client_2 est égale à 4. Elle est notée par:

$$\text{dist(Client}_1, \text{Client}_2) = 4$$

Dans la section suivante nous montrons l'utilité de cette distance dans l'application des deux opérations assembler et éclater.
<figure><img src="image_70.png" /><figcaption>FIG. 6.13: Un exemple de représentation de fragments dans le cas de trois attributs</figcaption></figure>

**Assembler:** Soit $F_i$ et $F_j$ deux fragments horizontaux définis par les clauses $cl_i$ et $cl_j$. L'opération *assembler* deux fragments est appliquée si les conditions suivantes sont satisfaites:

1. Les clauses des deux fragments $cl_i$ et $cl_j$ different au niveau d'un seul prédicat ($p_k$). Pour capturer cette différence, nous utilisons la distance de Hamming entre les deux vecteurs de fragmentation représentant les deux fragments. Cette opération est appliquée, si la distance de Hamming entre les couples d'éléments correspondants de chaque vecteur est égale à 0 sauf pour un couple.

2. Les deux fragments $F_i$ et $F_j$ sont accédés simultanément par des requêtes n'ayant pas le prédicat $p_k$.

L'intérêt de cette opération est le suivant: Si les deux fragments sont accédés simultanément par un ensemble de requêtes, nous aurons intérêt à les regrouper pour éviter d'avoir à faire ensuite l'union des résultats correspondants aux différents fragments.

**Exemple 32** Prenons les fragments Client_3 et Client_4 générés par l'algorithme des affinités et représentés comme suit:

$$ \begin{aligned} \text{Client\_3:} \quad & ( (0,0,0,0,1,0); (1,0); (1,0) ) \quad \text{et} \\ \text{Client\_4:} \quad & ( (0,0,0,0,1,0); (0,1); (1,0) ). \end{aligned} $$

La distance de Hamming pour chacun des couples d'éléments de leurs vecteurs de fragmentation est égale à 0, à l'exception des éléments situés en 2ème position. Ces deux fragments peuvent être donc assemblés en un seul fragment représenté par le vecteur suivant: $((0,0,0,0,1,0); (1,0))$.

Le premier et le deuxième élément de ce vecteur représentent les attributs Age et Ville, respectivement. L'attribut a été éliminé.

Soit $m$ le nombre de fragments horizontaux, le nombre maximum de toutes les opérations assembler est $\frac{m \times (m-1)}{2}$.
**Eclater:** Soit $F$ un fragment horizontal défini par une clause ayant $f$ prédicats simples, et $Q$ une requête accédant à la table $T$ et ayant $g$ prédicats de sélection ($g > f$). Le fragment $F_j$ peut être éclaté en incluant les prédicats qui ne sont pas définis dans la clause de $F$ mais définis dans celle de la requête. Le nombre de fragments générés par cette opération dépend des SDSs de chaque attribut défini dans la requête et non dans le fragment.

Cette opération ressemble à l'étape 6 de l'algorithme des affinités dans la section 6.2. Cette opération augmente le nombre de fragments et diminue la taille de chacun.

**Exemple 33** Dans la section 6.2, nous avons introduit trois attributs de fragmentation sur la table `CLIENT`: `Age`, `Sexe` et `Ville`. Soit `Client_1` un fragment défini par la clause de deux prédicats: (`Age` ≤ 40) ∧ (`Ville` = "Paris").

Soit $Q$ une requête ayant les trois prédicats de sélection suivants: (`Age` ≤ 30) ∧ (`Sexe` = 'M') ∧ (`Ville` = "Paris").

Le seul attribut figurant dans la clause de la requête et pas dans la clause du fragment est `Sexe`. Notons que le domaine de ce dernier possède deux valeurs "M" et "F". En conséquence, le fragment `Client_1` peut être éclaté en deux fragments horizontaux: `Client_2` et `Client_3` ayant les clauses suivantes:

`Client_2` ayant la clause (`Age` ≤ 40) ∧ (`Sexe` = 'M') ∧ (`Ville` = "Paris").

`Client_3` ayant la clause (`Age` ≤ 40) ∧ (`Sexe` = 'F') ∧ (`Ville` = "Paris").

Dans cet exemple, nous avons éclaté le fragment en deux, car l'attribut `Sexe` possède deux SDSs.

Soit $m$ le nombre de fragments horizontaux, le nombre maximum de toutes les opérations éclater est $\frac{m \times (m-1)}{2}$.

### 6.4.3.2 Identification des fragments nécessaires à une requête

Dans cette section, nous montrons l'intérêt de la distance de Hamming dans le processus d'identification des fragments nécessaires à l'exécution d'une requête. Notons qu'une requête typique, projette un ensemble d'attributs d'une table et sélectionne les n-uplets de cette table en se basant sur quelques conditions sur ses attributs de la table définis par des prédicats. Dans le cas où la requête accède à plusieurs tables (en cas de jointure ou union, etc), ces opérations sont exécutées sur les n-uplets des relations satisfaisants les prédicats de sélection. En conclusion, l'opération de jointure n'a aucun effet sur la fragmentation horizontale [Kar96].

Soit $Q_u$ une requête définie sur une table fragmentée $T$ ayant $l$ attributs de fragmentation $A_1, ..., A_l$. $Q_u$ peut être représenté par un n-uplet $(p_{u1}, p_{u2}, ..., p_{ul})$ [AGEA93], où $p_{ui}$ est le prédicat de sélection défini sur l'attribut de fragmentation $A_i$ (la valeur "*" sera utilisée si $Q$ n'utilise pas $A_i$). Etant donné que le domaine de chaque attribut de fragmentation $A_k$ est partitionné en $n_k$ SDSs, la requête $Q_u$ peut être représentée par un vecteur (vecteur de la requête) comme les fragments. Si la requête $Q_u$ ne contient aucun prédicat de sélection, elle sera représentée par le vecteur $Q_u: (*, *, ..., *)$.

Après la création de fragments horizontaux, les requêtes définies sur le schéma global (non partitionné) doivent être transformées sur le schéma partitionné. Pour ce faire, nous devons identifier les fragments nécessaires pour chaque requête. Étant
donné que la requête peut avoir des prédicats de sélection définis sur des attributs qui ne participent pas au processus de la fragmentation, ces derniers ne seront pas pris en considération. En conséquence, la requête est représentée seulement par des attributs de fragmentation. Le vecteur de requête doit être représenté dans le même ordre que le vecteur de fragmentation.

**Exemple 34** Soit Q une requête définie sur le schéma en étoile (voir Figure 2.5) dont la description est la suivante:

```sql
SELECT SUM(V.ventes_dollar)
FROM CLIENT, VENTES
WHERE CLIENT.Cid = VENTES.Cid
AND CLIENT.Sexe = 'M'
AND Région = 'Rhône'
GROUP BY PID
```

Cette requête contient deux prédicats de sélection (`C.Sexe` = 'M' et `Région` = "Rhône"). Parmi ces prédicats, un seul est un prédicat de fragmentation (celui défini sur l'attribut `Sexe`). Le prédicat défini sur l'attribut `Région` est donc écarté. En conséquence, le vecteur de la requête Q est $Q : ( *; (1,0); *) )$.

La distance de Hamming peut être également utilisée pour définir une distance $dist(Q_u, F_j)$ entre les vecteurs d'un fragment $F_j$ et celui d'une requête $Q_u$ (par le fait qu'ils ont la même représentation).

## Propriété 4 Contribution d'un fragment à une requête

Soit $n_i$ le nombre de SDSs de l'attribut $A_i$

- Si $dist(Q_u, F_j) = 0$ alors tous les n-uplets de $F_j$ participent à la requête $Q_u$.

- S'il existe un $Q_{ui}$ et $F_{ji}$ tel que: $dist(Q_{ui}, F_{ji}) = n_i$ alors aucun n-uplet de $F_j$ ne participe à la requête $Q_u$.

- Si $0 < dist(Q_{ui}, F_{ji}) < n_i$ pour tout $Q_{ui}$, et $F_{ji}$, alors certains n-uplets de $F_j$ participent à la requête $Q_u$.

À partir de la représentation binaire des requêtes et des fragments, nous pouvons facilement identifier le nom des fragments accédés par une requête donnée. Une fois ces fragments identifiés, nous définissons une nouvelle matrice que nous appelons requête-fragment, dans laquelle, les lignes représentent les requêtes et les colonnes les fragments. Si un fragment est accédé par une requête, la valeur correspondante de cette matrice est égale à 1, sinon elle est égale à 0. La fréquence d'accès de chaque requête à un fragment peut être ajoutée dans cette matrice. En fonction de cette matrice et de la représentation binaire des fragments, les deux opérations peuvent être facilement mises en oeuvre.

Dans l'algorithme approximatif, nous commençons par appliquer l'opération éclater et ensuite l'opération assembler. Ce choix est dicté par la remarque suivante: l'opération éclater génère plusieurs fragments horizontaux (de petite taille), et il est fort possible que les requêtes accèdent seulement à une partie de ces fragments, d'où la réduction de coût d'exécution de ces requêtes. Mais il faut noter que ce choix
est contre-balancé par la nécessité de faire des opérations d'union pour former les résultats des requêtes.

Comme chaque itération de cet algorithme ne provoque qu'un changement local du schéma initial, l'algorithme converge vers un minimum local.

### 6.4.4 Le test d'arrêt

L'algorithme approximatif s'achève lorsqu'il n'est plus possible d'appliquer l'une des deux opérations ou lorsque aucune réduction dans le coût d'évaluation des requêtes n'est constatée.

### 6.4.5 Description de l'algorithme

Maintenant, nous possédons tous les éléments pour décrire l'algorithme approximatif. Il débute par un schéma initial obtenu par l'algorithme des affinités décrit dans la section 6.2. Les fragments de ce schéma sont représentés sous la forme biographical. À l'aide du modèle de coût, le coût d'exécution des requêtes sur ce schéma ($CT_{initial}$) est calculé.

Ensuite, l'algorithme cherche une possibilité d'appliquer l'opération éclater au schéma initial. Si c'est le cas, nous obtenons un nouveau schéma de fragmentation, sur lequel, nous calculons le coût d'exécution des requêtes ($CT(courant)$). Si ce dernier est inférieur à celui obtenu pour le schéma initial ($CT_{initial}$), nous remettons à jour le schéma initial obtenu après l'opération éclater et le coût initial sera le coût courant. Sinon, l'algorithme essaye de voir s'il y a une autre possibilité d'appliquer l'opération éclater. Cette procédure est répétée tant qu'une réduction du coût est constatée.

Ensuite, nous passons à l'opération assembler. Elle prend le schéma courant obtenu par l'application de l'opération éclater. Sa tâche est similaire à celle de la première opération.

Nous itérons ces deux opérations tant qu'une réduction dans le coût est constatée (voir l'algorithme 12).

## 6.5 Evaluation des trois algorithmes

Nous avons implémenté les trois algorithmes (exhaustif, approximatif et basé sur les affinités) en C sur une plate-forme Unix afin de comparer leurs performances en termes de coût des entrées-sorties nécessaires pour exécuter un ensemble de requêtes. Ces algorithmes ont été testés sur un schéma d'une base de données orientée objet [BKB98]. Nous nous sommes intéressés à la fragmentation d'une seule classe de ce schéma (la classe Projet). Le modèle de coût utilisé par les algorithmes exhaustif et approximatif est différent de celui utilisé dans ce mémoire, mais il calcule le coût des entrées-sorties lors de l'exécution d'un ensemble de requêtes. La seule différence est que ce modèle ne prend pas en considération des index. Ce modèle est décrit dans [BKS98, BKL98b].
**Algorithmme 12** L'algorithmme approximatif

1: **Entrées:** (1) la table *T* à fragmenter, et (2) un ensemble de requêtes (avec leur fréquences d'accès)

2: **Sortie:** Un schéma de fragmentation

3: K: représente le nombre maximum de l'opération éclater

4: i := 1

5: schéma\_initial: = algo\_affi\_horiz

6: $CT_{initial} := \text{coût}(\text{schéma\_initial})$

7: **while** (i ≤ K) **do**

8: nouveau\_schéma: = éclater(schéma\_initial)

9: $CT_{courant} := \text{coût}(\text{nouveau\_schéma})$

10: **if** ($CT_{courant} < CT_{initial}$) **then**

11: schéma\_initial : = nouveau\_schéma

12: $CT_{initial} := CT_{courant}$

13: i := i + 1

14: end if

15: end while

16: NN:= Le nombre de fragments horizontaux résultant des opérations assembler

17: j := 1

18: **while** (j ≤ NN) **do**

19: nouveau\_schéma: = assembler(schéma\_initial)

20: $CT_{courant} := \text{coût}(\text{nouveau\_schéma})$

21: **if** ($CT_{courant} < CT_{initial}$) **then**

22: schéma\_initial : = nouveau\_schéma

23: $CT_{initial} := CT_{courant}$

24: j := j + 1

25: end if

26: end while
Ètant donné que le nombre de schémas de fragmentation générés par l'algorithme exhaustif est très grand (Table 6.2), nous avons effectué deux expérimentations. La première considère un nombre de minterms raisonnable afin de tester ensemble les trois algorithmes, et la deuxième compare les performances des deux algorithmes approchés, c'est-à-dire l'algorithme approximatif et l'algorithme basé sur les affinités.

### 6.5.1 La première expérimentation

Nous avons considéré cinq prédicats de sélection définis sur une classe Projet. À partir de ces prédicats, nous identifions 8 minterms. Premièrement, l'algorithme exhaustif est exécuté. Il génère à partir des minterms obtenus **4140** schémas de fragmentation de la classe Projet. Chaque schéma est associé à un coût d'exécution d'un ensemble de requêtes (voir Figure 6.14). Par conséquent, la sélection du meilleur schéma peut être facilement effectuée. Le schéma minimal a un coût de 2190 IOs.

Deuxièmement, l'algorithme des affinités est exécuté. Il a comme entrée les cinq prédicats de sélection et l'ensemble des requêtes avec leur fréquence d'accès. Le coût d'exécution de l'ensemble des requêtes sous le schéma sélectionné par cet algorithme est de 2830 IOs (Figure 6.14).

Finalement, nous exécutons l'algorithme approximatif, qui prend le schéma obtenu par l'algorithme des affinités et essaye de l'améliorer en appliquant les deux opération *éclater* et *assembler*. Le coût d'exécution de requêtes correspondant au schéma sélectionné est de 2250 IOs.

À partir de cette expérimentation, nous voyons clairement l'avantage d'utiliser l'algorithme approximatif, qui fournit une solution ayant un coût presque identique à celui de la solution obtenue par l'algorithme des affinités. La solution de ce dernier est 1,3 fois moins performante que la solution optimale fournie par l'algorithme exhaustif.

### 6.5.2 La deuxième expérimentation

Nous avons considéré un nombre important de prédicats, et en conséquence nous avons comparé seulement les deux algorithmes approchés.

Les résultats ont montré que l'algorithme approximatif donne des schémas de fragmentation présentant un coût d'exécution des requêtes nettement supérieur à celui obtenu par les schémas obtenus par l'algorithme des affinités. La non prise en considération des paramètres physiques utilisés par le modèle de coût de l'algorithme des affinités explique cette situation.

### 6.5.3 Discussion

Les résultats obtenus peuvent être analysés en fonction de deux critères: *le temps de calcul* et *le gain du coût d'entrées-sorties des requêtes*.

- **Le temps de calcul:** L'algorithme exhaustif nécessite un coût de calcul très élevé pour un grand nombre de minterms. L'algorithme basé sur les affinités est très efficace en termes de temps de calcul. Finalement, le coût de calcul de
<figure><img src="image_71.png" /><figcaption>FIG. 6.14: Nombre de fragments vs. coût total d'exécution de requêtes</figcaption></figure>

l'algorithmes approximatifs se situent celui de l'algorithmes exhaustifs et celui des affinités. La performance de cet algorithme dépend du nombre d'opérations "éclater" et "assembler" réalisées au cours de son exécution. Si la solution initiale est proche de l'optimum, l'algorithmes approximatifs peuvent sélectionner le schéma de fragmentation optimal dans un délai bref.

- **Le gain du coût des entrées-sorties:** Nous avons conduit une expérience dans laquelle nous calculons le coût normalisé d'exécution d'un ensemble de requêtes sur une classe (1) non fragmentée, (2) fragmentée en utilisant l'algorithmes exhaustifs, (3) fragmentée en utilisant l'algorithmes approximatifs, et (4) fragmentée en utilisant l'algorithmes des affinités.

Les résultats ont montré que le coût de la solution obtenue par l'algorithmes approximatifs est presque identique à celui de la solution obtenue par l'algorithmes exhaustifs. Les deux algorithmes donnent un schéma de fragmentation ayant un coût supérieur à celui du schéma non fragmenté [BKL98b]. Le coût de la solution fournie par l'algorithmes des affinités est supérieur à ceux des solutions des deux autres algorithmes, mais il est inférieur à celui du schéma non fragmenté [BKS98].

Pour conclure, nous pouvons dire que l'utilisation d'un bon algorithme de
fragmentation réduit considérablement le coût d'exécution de requêtes.
# Chapitre 7

# Conclusion et Perspectives

## 7.1 Conclusion

Cette thèse a concerné diverses techniques pour l'amélioration des performances des bases de données et des entrepôts de données. Dans cette section nous résumons les principaux apports de nos travaux.

### 7.1.1 Les index de jointure en présence des vues matérialisées

Le problème de la sélection d'index est sans doute le plus important dans la conception physique d'un entrepôt de données. Nous avons introduit les index de jointure qui peuvent être appliqués aux tables sources et aux vues matérialisées, ensemble ou séparément. Une stratégie d'exécution des requêtes en présence de ce type d'index a été décrite. Nous avons aussi proposé un modèle de coût pour évaluer le nombre d'entrées sorties nécessaires à l'exécution d'un ensemble de requêtes. Le problème de sélection des index de jointure a alors été formulé comme un problème d'optimisation minimisant cette fonction de coût en présence d'une contrainte d'espace. La complexité de ce problème est exponentielle. Nous avons suggéré trois algorithmes pour sélectionner des index de jointure optimaux ou quasi optimaux. Ces algorithmes consistent à réaliser un parcours du graphe de jointure de la requête. Les résultats de nos expérimentations ont montré qu'un index de jointure entre plusieurs tables peut contribuer significativement à la réduction du temps d'exécution d'un ensemble de requêtes. De plus la présence de vues appropriées peut renforcer l'efficacité d'un tel index.

### 7.1.2 Interaction entre les problèmes de sélection des vues et de sélection d'index

Les index et les vues matérialisées se partagent une même ressource : l'espace disque. Le problème de sélectionner simultanément, et non pas indépendamment, les vues et les index se pose donc. Nous avons suggéré une approche modulaire pour résoudre ce problème et avons proposé deux algorithmes approchés pour dis-
tribuer l'espace entre les vues et les index dans les cas statique et dynamique. Ces algorithmes sont basés sur une approche itérative. Nos expérimentations sur un cas réaliste ont montré que la prise en compte de l'interaction entre les vues et les index est effectivement indispensable pour atteindre de bons niveaux de performance.

### 7.1.3 La fragmentation horizontale

Même avec une utilisation appropriée des vues et des index, le coût d'exécution des requêtes peut rester important. Pour le réduire encore il est possible de recourir à la fragmentation horizontale. De nombreuses solutions pour fragmenter les tables dans un entrepôt de données ont été proposées. Nous nous sommes attachés à éla-borer une méthodologie de fragmentation horizontale de la table des faits et des tables de dimensions. Nous avons illustré son déroulement à travers un exemple. Il est apparu qu'il ne suffit pas de fragmenter la table des faits (en général la plus volumineuse). Très souvent il y a lieu également de fragmenter (par fragmentation dérivée) certaines des tables de dimensions pour obtenir les meilleures performances. Nous avons suggéré un algorithme pour sélectionner les tables de dimensions à frag-menter. Les performances de la fragmentation sont évaluées par l'intermédiaire d'un modèle de coût calculant le nombre d'entrées sorties nécessaire à l'exécution d'un ensemble de requêtes.

Quelques expérimentations ont montré que la fragmentation horizontale réduit généralement le coût total d'exécution des requêtes.

### 7.1.4 De nouveaux algorithmes de fragmentation horizontale

Les algorithmes de fragmentation horizontale existants ne garantissent pas une réduction du temps d'exécution d'un ensemble de requêtes. Nous avons développé de nouveaux algorithmes, l'un dirigé par les affinités, le deuxième dirigé par un modèle de coût pour atteindre cet objectif. L'idée d'un algorithme de fragmentation horizontale dirigé par les affinités a été introduite par Navathe pour les systèmes relationnels mais n'avait pas été exploré complètement. L'avantage principal de cet algorithme est sa complexité qui est polynômiale. Mais il utilise la fréquence d'accès des requêtes comme seul critère de regroupement. D'autres paramètres peuvent aussi jouer un rôle important (sélectivité des prédicats, taille des tables à fragmenter, etc.). Nous avons donc étudié des aménagements pour tenir compte de ces paramètres et proposé deux nouveaux algorithmes basés sur un modèle de coût. Le premier consiste à énumérer d'une façon exhaustive tous les schémas de fragmentation pouvant être générés à partir des prédicats simples définis dans les requêtes. Le schéma optimal fournissant le coût d'exécution minimum est alors sélectionné. Cet algorithme est cependant très coûteux en temps de calcul. Le deuxième algorithme est approximatif. Il est basé sur le principe du "hill-climbing". Il considère une solution initiale obtenue par l'algorithme des affinités, et essaie ensuite d'améliorer cette solution par des opérations successives sur les fragments.
## 7.2 Perspectives

De nombreuses perspectives tant à caractère théorique que pratique peuvent être envisagées. Dans cette section nous présentons succinctement celles qui nous paraissent être les plus intéressantes.

### 7.2.1 Autres types d'algorithmes

Tous les points que nous avons abordés sont en fait des problèmes d'optimisation que nous avons résolus par des algorithmes approchés de type glouton ou "hill-climbing". Il serait intéressant de considérer d'autres types d'algorithmes comme les algorithmes de recuit simulé ou les algorithmes génétiques.

### 7.2.2 Utilisation d'une représentation binaire des index

Les index de jointure tels que nous les avons exploités demandent beaucoup d'espace en mémoire secondaire pour leur représentation. Leur gestion introduit des temps d'overhead importants. Il serait intéressant d'étudier comment les techniques de représentation binaire pourraient être utilisées pour réduire ces temps.

### 7.2.3 La sélection incrémentale des vues et des index

Après les opérations de mise à jour des données de l'entrepôt, il est nécessaire de reconsidérer la sélection des vues et des index. Nous avons abordé ce type de problèmes dans le chapitre 5 pour la sélection simultanée des index et des vues. Des études complémentaires s'imposent pour privilégier systématiquement la sélection incrémentale des vues et des index.

### 7.2.4 La prise en considération du coût de maintenance

Dans cette thèse nous avons considéré que la seule contrainte à respecter était la contrainte d'espace disque. D'autres contraintes peuvent être envisagées comme par exemple le coût de maintenance des index et des vues.

En effet, supposer que les mises à jour de l'entrepôt de données se font hors ligne n'est pas une hypothèse systématiquement valide car certaines applications nécessitent une mise à jour immédiate. Il serait donc intéressant d'étudier si les algorithmes que nous avons suggérés peuvent être aménagés pour tenir compte de la contrainte de coût de maintenance des vues et des index.

### 7.2.5 La fragmentation dynamique

La plupart des algorithmes de fragmentation existants sont de nature statique : ils fragmentent une table en se basant sur un ensemble de requêtes définies préalablement. Or les applications exploitant un entrepôt de données peuvent évoluer. Il serait donc intéressant de développer ou d'aménager des algorithmes pour tenir compte de l'évolution des requêtes tant dans leurs structures que dans leurs fréquences.
### 7.2.6 La fragmentation d'un schéma en flocon de neige

Dans les bases de données orientées objet, nous avons montré l'intérêt de la fragmentation horizontale dérivée dans la réduction du coût d'exécution des requêtes [BKL98b]. La fragmentation dérivée est performante lorsqu'elle est utilisée sur tout le chemin d'une hiérarchie d'un schéma. Considérons, par exemple la hiérarchie Employé - Département - Projet. Si les classes Employé et Département sont horizontalement fragmentées en fonction des fragments de la classe Projet, alors la réduction du coût d'exécution de requêtes accédant à ces trois classes est très significative.

Dans les entrepôts de données, la notion de hiérarchie est bien présente dans le cas des schémas en flocon de neige (voir le schéma de TPC-H [Pag]). Il semble que la fragmentation dérivée peut être facilement utilisée dans ce type de schéma. Il serait important de se pencher sur son utilisation et son rôle dans la réduction du coût des requêtes.

### 7.2.7 Evaluation des algorithmes par benchmarks

Nous avons proposé d'évaluer les performances de nos algorithmes par des modèles de coût. Même si ces modèles incorporent effectivement les paramètres les plus influents, il serait important de confirmer les résultats obtenus par des expérimentations systématiques avec des benchmarks (TPC-H par exemple [Pag]).
Bibliographie

[AGEA93] K. A. S. Abdel-Ghaffar and A. El Abbadi. Optimal disk allocation for partial match queries. *ACM Transactions on Database Systems*, 18(1):132–156, March 1993.

[AGS96] R. Agrawal, A. Gupta, and S. Sarawagi. Modeling multidimensional databases. *Research Report: IBM Almaden Research Center, San Jose, CA*, 1996.

[AGS97] A. Agrawal, A. Gupta, and S. Sarawagi. Modeling multidimensional databases. Technical report research, IBM, 1997.

[AL80] M. Adiba and B. G. Lindsay. Database snapshots. *Proceedings of the International Conference on Very Large Databases*, pages 86–91, October 1980.

[Ape88] P. M. G. Apers. Data allocation in distributed database systems. *ACM Transactions on database systems*, 13(3):263–304, 1988.

[BC81] P. A. Bernstein and D-M. W. Chiu. Using semi-joins to solve relational queries. *Journal of the ACM*, 28(1):25–40, January 1981.

[BDD$^{+}$98] R. G. Bello, K. Dias, A. Downing, Feenan Jr. J., W. D. Norcott, H. Sun, A. Witkowski, and M. Ziauddin. Materialized views in oracle. *Proceedings of the International Conference on Very Large Databases*, pages 659–664, August 1998.

[Bel96] L. Bellatreche. An algorithm for vertical fragmentation in distributed object database systems. in *Proceeding of the Second International Bal- tic Workshop on Databases and Information Systems BALT’96, Tallin, June 1996.*, pages 65–74, June 1996.

[Bel98] Z. Bellahsene. View adaptation in data warehousing systems. *Proceedings of the 9th International Conference on Database and Expert Systems Applications (DEXA)*, pages 300–309, August 1998.

[Bel00a] L. Bellatreche. Logical and physical design in data warehousing en- vironments. in *proceedings of International Conference on Extending Database Technology (EDBT) PhD Workshop*, March 2000.

[Bel00b] L. Bellatreche. Une méthodologie pour la fragmentation dans les entre- pôts des données. in *18th Congrès d’Informatique Des Organisations et*
*Systèmes d'Information et de Décision (INFORSID'2000), Lyon*, pages 245-260, May 2000.

[BG93] E. Bertino and C. Guglielmina. Path-index: An approach to the efficient execution of object-oriented queries. *Data & Knowledge Engineering*, 10:1-27, 1993.

[BHY91] R. Blankinship, A. R. Hevner, and S. B Yao. An iterative method for distributed database design. *17th International Conference on Very Large Data Bases, VLDB'91*, pages 389-400, September 1991.

[BKA00] L. Bellatreche, K. Karlapalem, and Simonet A. Algorithms and support for horizontal class partitioning in object-oriented databases. *in the Distributed and Parallel Databases Journal*, 8(2):155-179, April 2000.

[BKB98] L. Bellatreche, K. Karlapalem, and G. B. Basak. Query-driven horizon-
tal class partitioning in object-oriented databases. *in 9th International
Conference on Database and Expert Systems Applications (DEXA'98)*,
*Lecture Notes in Computer Science 1460*, pages 692-701, August 1998.

[BKL98a] L. Bellatreche, K. Karlapalem, and Q. Li. Complex methods and class allocation in distributed object-oriented databases. in the 5th International Conference on Object Oriented Information Systems (OOIS'98), pages 239-256, September 1998.

[BKL98b] L. Bellatreche, K. Karlapalem, and Q. Li. Derived horizontal class partitioning in oodbss: Design strategy, analytical model and evaluation. in *the 17th International Conference on the Entity Relationship Approach (ER'98)*, pages 465-479, November 1998.

[BKL98c] L. Bellatreche, K. Karlapalem, and Q. Li. An iterative approach for rules and data allocation in distributed deductive database systems. in *the 7th International Conference on Information and Knowledge Management (CIKM'98)*, pages 356-363, November 1998.

[BKL99] L. Bellatreche, K. Karlapalem, and Q. Li. Algorithms for graph join index problem in data warehousing environments. Technical Report HKUST-CS99-07, Hong Kong University of Science & Technology, March 1999.

[BKL00] L. Bellatreche, K. Karlapalem, and Q. Li. Evaluation of indexing materialized views in data warehousing environments. *Proceeding of the International Conference on Data Warehousing and Knowledge Discovery (DAWAK'2000)*, pages 57-66, September 2000.

[BKM00a] L. Bellatreche, K. Karlapalem, and M. Mohania. Some issues in design of data warehousing systems. In *To appear in Developing Quality Complex Data Bases Systems: Practices, Techniques, and Technologies, Edited by Dr. Shirley A. Becker*. Idea Group Publishing, 2000.
[BKM00b] L. Bellatreche, K. Karlapalem, and M. Mohania. What can partitioning do for your data warehouses and data marts. *Proceedings of the International Database Engineering and Application Symposium (IDEAS'2000)*, pages 437-445, September 2000.

[BKS97] L. Bellatreche, K. Karlapalem, and A. Simonet. Horizontal class partitioning in object-oriented databases. *in 8th International Conference on Database and Expert Systems Applications (DEXA'97), Toulouse, Lecture Notes in Computer Science 1308*, pages 58-67, September 1997.

[BKS98] L. Bellatreche, K. Karlapalem, and A. Simonet. Query optimization using horizontal class partitioning in object-oriented databases. *in 16th Congrès d'Informatique Des Organisations et Systèmes d'Information et de Décision (INFORSID'98), Montpellier*, pages 405-422, May 1998.

[BKS00] L. Bellatreche, K. Karlapalem, and M. Schneider. On efficient storage space distribution among materialized views and indices in data warehousing environments. *Proceedings of the International Conference on Information and Knowledge Management (ACM CIKM'2000)*, November 2000.

[BLT86] J. A. Blakeley, P. Larson, and F. W. Tompa. Efficiently updating materialized views. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 61-71, June 1986.

[BM00] Z. Bellahsene and P. Marot. Materializing a set of views: Dynamic strategies and performance evaluation. *Proceedings of the International Database Engineering and Application Symposium (IDEAS'2000)*, pages 424-428, September 2000.

[BPT97] E. Baralis, S. Paraboschi, and E Teniente. Materialized view selection in a multidimensional database. *Proceedings of the International Conference on Very Large Databases*, pages 156-165, August 1997.

[BS95] J. C. Bontempo and C. M. Saracco. *Database Management: Principles and Products*. Prentice Hall, 1995.

[BS96] L. Bellatreche and A. Simonet. A horizontal fragmentation algorithm in object database design. *in Third International Conference of the Austrian Center for Parallel Computation (ACPC'96), with Special Emphasis on Parallel Databases and Parallel I/O, Lecture Note in Computer Science (LNCS), 1127*, pages 223-226, September 1996.

[BSS96] L. Bellatreche, A. Simonet, and M. Simonet. An algorithm for vertical fragmentation in distributed object database systems with complex attributes and methods. *in International Workshop on Database and Expert Systems Applications (DEXA'96), Zurich*, pages 15-21, September 1996.
[CCS93] E. F. Codd, S. B. Codd, and C. T. Salley. Providing olap (on-line analytical processing) to user-analysts: An it mandate. *White paper*, http://www.arborsoft.com/essbase/wht_paper/coddTOC.html, 1993.

[CD97] S. Chaudhuri and U. Dayal. An overview of data warehousing and olap technology. *Sigmod Record*, 26(1):65-74, March 1997.

[Cha82] J. Chang. A heuristic approach to distributed query processing. *Proceedings of the International Conference on Very Large Databases*, pages 54-61, September 1982.

[CMVN94] S. Chakravarthy, J. Muthuraj, R. Varadarajan, and S. B. Navathe. An objective function for vertically partitioning relations in distributed databases and its analysis. *in Distributed and Parallel Databases Journal*, 2(2):183-207, April 1994.

[CN97] S. Chaudhuri and V. Narasayya. An efficient cost-driven index selection tool for microsoft sql server. *Proceedings of the International Conference on Very Large Databases*, pages 146-155, August 1997.

[CN98] S. Chaudhuri and V. Narasayya. Autoadmin 'what-if' index analysis utility. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 367-378, June 1998.

[CN99] S. Chaudhuri and V. Narasayya. Index merging. *Proceedings of the International Conference on Data Engineering (ICDE)*, pages 296-303, March 1999.

[CN00] S. Chaudhuri and V. Narasayya. Automating statistics management for query optimizers. *Proceedings of the International Conference on Data Engineering (ICDE)*, pages 339-348, March 2000.

[CNP82] S. Ceri, M. Negri, and G. Pelagatti. Horizontal data partitioning in database design. *Proceedings of the ACM SIGMOD International Conference on Management of Data. SIGPLAN Notices*, pages 128-136, 1982.

[Cod70] E. F. Codd. A relational model of data for large shared data banks. *Communications of the ACM*, 13(6):377-387, June 1970.

[Cor97a] Oracle Corp. Star queries in oracle8. *White Paper*, June 1997.

[Cor97b] Informix Corporation. Informix-online extended parallel server and informix-universal server: A new generation of decision-support indexing for enterprise data warehouses. *White Paper*, 1997.

[Cor98] Oracle Corp. Oracle warehouse: Unleash the power of information. *White Paper: http://www.oracle.com/tools/datawarehouse*, November 1998.

[CP84] S. Ceri and G. Pelagatti. *Distributed Databases: Principles & Systems*. McGraw-Hill International Editions, 1984.
[CPW89] S. Ceri, B. Pernici, and G. Wiederhold. Optimization problems and solution methods in the design of data distribution. *Information Systems*, 14(3):261-272, 1989.

[CW81] S. Ceri and J. Widom. Deriving production rules for incremental view maintenance. *Proceedings of the International Conference on Very Large Databases*, pages 577-589, September 1981.

[CY87] D. Cornell and P. S. Yu. A vertical partitioning algorithm for relational databases. *Proceedings of the Third International Conference on Data Engineering (ICDE'87)*, pages 30-35, 1987.

[CY99a] C. Chee-Yong. Indexing techniques in decision support systems. Phd. thesis, University of Wisconsin - Madison, 1999.

[CY99b] C. Chee-Yong. Indexing techniques in decision support systems. Ph.d. thesis, University of Wisconsin - Madison, 1999.

[D.96] Simpson D. Build your warehouse on mpp. Available at http://www.datamation.com/servr/12mpp.html, December 1996.

[Dar99] J. Darmont. Étude des performances de méthodes de regroupement dynamique dans les bases de données orientées-objet. Thèse de doctorat, Université Clermont-Ferrand II, Janvier 1999.

[DRSN98] P. Deshpande, K. Ramasamy, A. Shukla, and J. F. Naughton. Caching multidimensional queries using chunks. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 259-270, June 1998.

[DRT99] A. Datta, K. Ramamritham, and H. Thomas. Curio: A novel solution for efficient storage and indexing in data warehouses. *Proceedings of the International Conference on Very Large Databases*, pages 730-733, September 1999.

[EB95] C. I. Ezeife and K. Barker. A comprehensive approach to horizontal class fragmentation in distributed object based system. *International Journal of Distributed and Parallel Databases*, 3(3):247-272, 1995.

[EN94] R. ElMasri and S. B. Navathe. *Fundamentals of Database Systems*. Benjamin Cummings, Redwood City, CA, 1994.

[ES76] M. J. Eisner and D. G. Severance. Mathematical techniques for efficient record segmentation in large shared databases. *Journal of the ACM*, 23(4):619-635, October 1976.

[Fir97] J. M. Firestone. Data warehouses and data marts: A dynamic view. White Paper 3, Executive Information Systems, Inc., March 1997.

[FKL97] C. W. Fung, K. Karlapalem, and Q. Li. Cost-driven evaluation of vertical class partitioning in object oriented databases. *in Fifth International Conference On Database Systems For Advanced Applications (DASFAA'97)*, Melbourne, Australia, pages 11-20, April 1997.
[FKL98] C. W. Fung, K. Karlapalem, and Q. Li. Structural join index hierarchy: A mechanism for efficient complex object retrieval. in the 5th International Conference on Foundations of Data Organization and Algorithms (FODO'98), November 1998.

[Fra97] J-M. Franco. Le Data Warehouse, Le Data Mining. Eyrolles, 1997.

[FST88] S. Finkelstein, M. Schkolnick, and P. Tiberio. Physical database design for relational databases. ACM Transactions on Database Systems, 13(1):91-128, March 1988.

[Gar83] G. Gardarin. Bases de Données : Les Systèmes et Leurs Langages. Editions Eyrolles, 1983.

[GCA01] E. B. Guerrero, C. Collet, and M. Adiba. Entrepôts de données: caractéristiques et problématique. Technique et Science Informatiques, 20(2-2001):145-178, 2001.

[GGT96] G. Gardarin, J.-R. Gruser, and Z.-H. Tang. A cost-based selection of path expression processing algorithms in object-oriented databases. 22th International Conference on Very Large Data Bases, VLDB'96, pages 390-401, 1996.

[GHRU97] H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman. Index selection for olap. Proceedings of the International Conference on Data Engineering (ICDE), pages 208-219, April 1997.

[GM95] A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques, and applications. Data Engineering Bulletin, 18(2):3-18, June 1995.

[GMR99] M. Golfarelli, D. Maio, and S. Rizzi. Vertical fragmentation of views in relational data warehouses. Proceedings of Sistemi Evoluti per Basi di Dati, pages 19-33, 1999.

[GMS93] A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 157-166, June 1993.

[GO96] G. Gardarin and Gardarin O. Le Client-Serveur. Edition Eyrolles, 1996.

[Gra93] G. Graefe. Query evaluation technique for large databases. ACM Computing Surveys, 25(2):73-170, June 1993.

[Gru96] J. R. Gruser. Modèle de coût pour l'optimisation de requête objet. Thèse de doctorat, Université de Paris VI, Décembre 1996.

[Gup97] H. Gupta. Selection of views to materialize in a data warehouse. Proceedings of the 6th International Conference on Database Theory (ICDT '97), pages 98-112, 1997.

[Gup99] H. Gupta. Selection and maintenance of views in a data warehouse. Ph.d. thesis, Stanford University, September 1999.
[GV90] G. Gardarin and P. Valduriez. SGBD AVANCEES : Bases de données objets, déductives, réparties. Edition Eyrolles, 1990.

[HMA99] C. A. Hurtado, O. A. Mendelzon, and Vaisman A. A. Maintaining data cubes under dimension updates. Proceedings of the International Conference on Data Engineering (ICDE), pages 346-355, March 1999.

[HN79] M. Hammer and B. Niamir. A heuristic approach to attribute partitioning. Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 93-101, 1979.

[HRU96] V. Harinarayan, A. Rajaraman, and J. Ullman. Implementing data cubes effeciently. Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 205-216, June 1996.

[HS75] J. A. Hoffer and D. G. Severance. The 1st international conference on very large databases (vldb'75). In The Use of Cluster Analysis in Physical Database Design, pages 69-86. Morgan Kaufman, 1975.

[HS95] P. J. Haas and A. N. Swami. Sampling-based selectivity estimation for joins using augmented frequent value statistics. Proceedings of the International Conference on Data Engineering (ICDE), pages 522-531, 1995.

[Huy97] N. Huyn. Multiple-view self-maintenance in data warehousing environments. Proceedings of the International Conference on Very Large Databases, pages 26-35, August 1997.

[Hyp] Hyperion. Hyperion Essbase OLAP Server. http://www.hyperion.com/.

[IC91] Y. E. Ioannidis and S. Christodoulakis. On the propagation of errors in the size of join results. Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 268-277, June 1991.

[Inm92] W. H. Inmon. Building the Data Warehouse. John Wiley, 1992.

[Ioa93] Y. E. Ioannidis. Universality of serial histograms. Proceedings of the International Conference on Very Large Databases, pages 256-267, August 1993.

[Jai91] R. Jain. The Art of Computer Systems Performance Analysis. Willey Professional Computing, 1991.

[JLS99a] H. Jagadish, L. V. S. Lakshmanan, and D. Srivastava. Snakes and sandwiches: Optimal clustering strategies for a data warehouse. Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 37-48, June 1999.

[JLS99b] H. Jagadish, L. V. S. Lakshmanan, and D. Srivastava. What can hierarchies do for your data warehouses. Proceedings of the International Conference on Very Large Databases, pages 530-541, September 1999.
[JMS95] H. Jagadish, I. S. Mumick, and A. Silberschatz. Maintenance issues for the chronicle data model. *proceedings of the Symposium on Principles of Databases Systems (PODS'95)*, pages 113-124, May 1995.

[Kar96] K. Karlapalem. Redesign of distributed relational databases. Ph.d. thesis, Georgia Institute of Technology, November 1996.

[Ked99] Z. Kedad. Techniques d'intégration dans les systèmes d'information multi-source. Thèse de doctorat, Université de Versailles Saint-Quentin-en-Yvelines, Janvier 1999.

[Kim96] R. Kimball. *The Data Warehouse Toolkit*. John Wiley & Sons, 1996.

[Kim97] R. Kimball. A dimensional modeling manifesto. *DBMS Magazine*, August 1997.

[KL70] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. *The Bell System Technical Journal*, pages 291-307, February 1970.

[KL90] O. Kiyoshi and G. M. Lohman. Measuring the complexity of join enumeration in query optimization. *Proceedings of the International Conference on Very Large Databases*, pages 314-325, August 1990.

[KL95] K. Karlapalem and Q. Li. Partitioning schemes for object oriented databases. *in Proceeding of the Fifth International Workshop on Research Issues in Data Engineering- Distributed Object Management, RIDE-DOM'95*, pages 42-49, March 1995.

[KLV96] K. Karlapalem, Q. Li, and S. Vieweg. Method induced partitioning schemes in object-oriented databases. *in 16th International Conference on Distributed Computing System (ICDCS'96)*, Hong Kong, pages 377-384, May 1996.

[KNM94] K. Karlapalem, S.B. Navathe, and M. M. A. Morsi. Issues in distributed design of object-oriented databases. In *Distributed Object Management*, pages 148-165. Morgan Kaufman Publishers Inc., 1994.

[KP97] K. Karlapalem and N. M Pun. Query driven data allocation algorithms for distributed database systems. *in 8th International Conference on Database and Expert Systems Applications (DEXA'97), Toulouse, Lecture Notes in Computer Science 1308*, pages 347-356, September 1997.

[KR98] Y. Kotidis and N. Roussopoulos. An alternative storage organization for rolap aggregate views based on cubetrees. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 249-258, June 1998.

[KR99] Y. Kotidis and N. Roussopoulos. Dynamat: A dynamic view management system for data warehouses. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 371-382, June 1999.
[KS95] R. Kimball and K. Strehlo. Why decision support fails and how to fix it. *SIGMOD Record*, 24(3):92–97, September 1995.

[LDH$^{+84}$] M. G. Lohman, D. Daniels, L. M. Haas, R. Kistler, and P. G. Selinger. Optimization of nested queries in a distributed relational database. *Proceedings of the International Conference on Very Large Databases*, pages 403–415, August 1984.

[Lev] A. Levy. Answering queries using views: a survey. *To appear in the VLDB Journal*.

[LHM$^{+86}$] B. G. Lindsay, L. M. Haas, C. Mohan, H. Pirahesh, and P. F. Wilms. A snapshot differential refresh algorithm. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 53–60, June 1986.

[LQA97] W. Labio, D. Quass, and B. Adelberg. Physical database design for data warehouses. *Proceedings of the International Conference on Data Engineering (ICDE)*, 1997.

[LR98] H. Lei and K. A. Ross. Faster joins, self-joins and multi-way joins using join indices. *Data and Knowledge Engineering*, 28(3):277–298, November 1998.

[Mar98] P. Marcel. Manipulation de données multidimensionnelles et langages de règles. Thèse de doctorat, Institut National des Sciences Appliquées de Lyon, Décembre 1998.

[Men97] A. Mendelzon. Olap: Concepts and products. *Talk at University of Toronto*, 1997.

[Mic98] MicroStrategy. The case for relational olap. Technical report, White paper: http://www.microstrategy.com, 1998.

[MK00] M. Mohania and Y. Kambayashi. Making aggregate views self-maintainable. *Data and Knowledge Engineering*, 32(1):87–109, January 2000.

[MLJ98] H. G. Molina, W. J. Labio, and Yang J. Expiring data in a warehouse. *Proceedings of the International Conference on Very Large Databases*, pages 500–511, August 1998.

[MLWZ98] H. Molina, W. J. Labio, J. L. Wiener, and Y. Zhuge. Distributed and parallel computing issues in data warehousing. *Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing*, page 7, June 1998.

[MSRK00] M. Mohania, S. Samtani, J. F. Roddick, and Y. Kambayashi. Advances and research directions in data warehousing technology. *To appear in the Australian Journal of Information Systems*, 2000.
[MSW72] W. T. McCormick, P. J. Schweitzer, and T. W. White. Problem decomposition and data reorganization by a clustering technique. *Operation Research*, 20(5):993-1009, September 1972.

[MW89] A. O. Mendelzon and P. T. Wood. Finding regular simple paths in graph database. *Proceedings of the International Conference on Very Large Databases*, pages 185-193, August 1989.

[Naa99] H. Naacke. Modèles de coût pour médiateurs de bases de données hétérogènes. Thèse de doctorat, Université de Versailles Saint-Quentin-en-Yvelines, Séptembre 1999.

[NB99] A. Y. Noaman and K. Barker. A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse. *in the 8th International Conference on Information and Knowledge Management (CIKM'99)*, pages 154-161, November 1999.

[NCWJ84] S.B. Navathe, S. Ceri, G. Wiederhold, and Dou J. Vertical partitioning algorithms for database design. *ACM Transaction on Database Systems*, 9(4):681-710, December 1984.

[Nic91] J-C. Nicolas. Machines bases de données parallèles: Contribution aux problèmes de la fragmentation et de la distribution. Thèse de doctorat, Université des Sciences et Techniques de Lille, Flandres Artois, Janvier 1991.

[Nil80] N. J. Nilsson. *Principles of Artificial Intelligence*. Morgan Kaufman Publishers Inc., 1980.

[NKR95] S.B. Navathe, K. Karlapalem, and M. Ra. A mixed partitioning methodology for distributed database design. *Journal of Computer and Software Engineering*, 3(4):395-426, 1995.

[NR89] S.B. Navathe and M. Ra. Vertical partitioning for database design: a graphical algorithm. *ACM SIGMOD*, pages 440-450, 1989.

[ODV92] M. T. Özsu, Dayal, and P. Valduriez. An introduction to distributed object management. *International Workshop on Distributed Object Management*, pages 1-24, August 1992.

[OQ97] P. O'Neil and D. Quass. Improved query performance with variant indexes. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 38-49, May 1997.

[Ora99] *Oracle8i Concepts*. Oracle Corporation, Release 8.1.5, 1999.

[OV91] M. T. Özsu and P. Valduriez. *Principles of Distributed Database Systems*. Prentice Hall, 1991.

[OV99] M. T. Özsu and P. Valduriez. *Principles of Distributed Database Systems: Second Edition*. Prentice Hall International, Inc., 1999.

[Pag] TPC Home Page. Tpc benchmark™d (decision support). http://www.tpc.org.
[Pas00] N. Pasquier. Data mining : Algorithmes d'extraction et de réduction des règles d'association dans les bases de données. Thèse de doctorat, Université Clermont-Ferrand II, Janvier 2000.

[PC98] N. Pendse and R. Creeth. The olap report, business intelligence inc. http://www.olapreport.com, 1998.

[PH89] A. Poli and L. Huguet. *Codes Correcteurs: Théorie et Applications.* Masson, 1989.

[PKN91] G Pernul, K. Karlapalem, and S. B. Navathe. Relational database organization based on views and fragments. in *International Workshop on Database and Expert Systems Applications (DEXA'91)*, pages 380-386, 1991.

[PS91] G. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules. in *Knowledge Discovery in Databases, AAAI/MIT Press*, pages 229-248, 1991.

[QGMW96] D. Quass, A. Gupta, I. S. Mumick, and J. Widom. Making views self-maintainable for data warehousing. in *Proceedings of the Fourth International Conference on Parallel and Distributed Information Systems*, pages 158-169, December 1996.

[QW97] D. Quass and J. Widom. On-line warehouse view maintenance for batch updates. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 393-404, May 1997.

[Ram98] R. Ramakrishnan. *Database Management Systems*. WCB/McGraw Hill, 1998.

[Rav96] R. Ravat. od³: contribution méthodologique à la conception de bases de données orientées objet réparties. Thèse de doctorat, Université Paul Sabatier, September 1996.

[RSS96] K. Ross, D. Srivastava, and S. Sudarshan. Materialized view maintenance and integrity constraint checking: Trading space for time. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 447-458, June 1996.

[SAD+79] P. G. Selinger, M. M. Astrahan, Chamberlin D. D., R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. *Proceedings of the ACM SIGMOD International Conference on Management of Data*, pages 23-34, 1979.

[SDJL96] D. Srivastava, S. Dar, H. Jagadish, and A. Y. Levy. Answering queries with aggregation using views. *Proceedings of the International Conference on Very Large Databases*, pages 318-329, September 1996.

[SDN98] A. Shukla, P. Deshpande, and J. F. Naughton. Materialized view selection for multidimensional datasets. *Proceedings of the International Conference on Very Large Databases*, pages 488-499, August 1998.
[Sel88] T. K. Sellis. Multiple-query optimization. *ACM Transactions on Database Systems*, 13(1):23-52, March 1988.

[SM77] D. Stanat and D. McAllister. *Discrete Mathematics in Computer Science*. Printice Hall, 1977.

[SP89] A. Segev and J. Park. Maintaining materialized views in distributed databases. *Proceedings of the International Conference on Data Engineering (ICDE)*, pages 262-270, February 1989.

[SS89] A. Simonet and M. Simonet. Les classes d'équivalence induites par des dépendances inter-attributs: fondements pour une représentation des objets partagés dans les bases de connaissances. Technical Report R.R. 769-I, Laboratoire Artemis - Grenoble, 1989.

[SS94] A. Simonet and M. Simonet. Objects with views and constraints: From databases to knowledge bases. *in the Proceeding of the International Conference on Object Oriented Information Systems, OOIS'94*, pages 182-195, December 1994.

[SSN00] A. Sanjay, C. Surajit, and V. R. Narasayya. Automated selection of materialized views and indexes in microsoft sql server. *To appear in VLDB'2000*, September 2000.

[Sys97] Red Brick Systems. Star schema processing for complex queries. *White Paper*, July 1997.

[TK78] D. Tsichritzis and A. Klug. The ansi/x3/sparc framework. *AFIPS Press, Montval, N.J.*, 1978.

[TS97] D. Theodoratos and T. K. Sellis. Data warehouse configuration. *Proceedings of the International Conference on Very Large Databases*, pages 126-135, August 1997.

[Ull89] J. D. Ullman. *Principles of Database and Knowledge-Base Systems*. vol. II. Computer Science Press, 1989.

[Ull96] J. Ullman. Efficient implementation of data cubes via materialized views. *in the Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96)*, pages 386-388, 1996.

[Val85] P. Valduriez. Optimisation des opérateurs relationnels dans les machines bases de données. Docteur ès sciences, Université Pierre et Marie Curie, September 1985.

[Val87] P. Valduriez. Join indices. *ACM Transactions on Database Systems*, 12(2):218-246, June 1987.

[VS99] P. Vassiliadis and T Sellis. A survey of logical models for olap databases. *SIGMOD Record*, 28(4):64-69, December 1999.

[WB97] M-C. Wu and A. Buchmann. Research issues in data warehousing. *in Datenbanksysteme in Büro, Technik und Wissenschaft(BTW'97)*, pages 61-82, March 1997.
[WLDH96] Y. Wang, J. C.L. Liu, Du, and J. Hsieh. Video file allocation over disk arrays for video-on-demand. in *Proceedings of the International Conference on Multimedia Computing and Systems (ICMCS'96)*, pages 160-173, June 1996.

[YC84] C. T. Yu and Chang C. C. Distributed query processing. *ACM Computing Surveys*, 16(4):399-433, December 1984.

[YKL97] J. Yang, K. Karlapalem, and Q. Li. Algorithms for materialized view design in data warehousing environment. *Proceedings of the International Conference on Very Large Databases*, pages 136-145, August 1997.

[ZO94] Y. Zhang and M-E. Orlowska. On fragmentation for distributed database design. *Information Sciences*, 1(3):117-132, 1994.