Cours complet pour apprendre les systèmes de gestion de bases de données

Les bases de données objet et plus encore relationnel-objet permettent de formuler des requêtes classiques, c'est-à-dire exprimables en SQL de base. En conséquence, l'optimiseur d'un SGBD doit toujours être capable d'effectuer les optimisations étudiées pour le relationnel. Au-delà, les requêtes objet intègrent des constructions inexprimables en relationnel. À ce titre, elles posent des problèmes d'optimisation spécifiques. Les points nouveaux sont pour l'essentiel :

1. Le support de méthodes et opérateurs définis par l'utilisateur. Dans les systèmes objet, l'utilisateur peut définir ses propres méthodes, ses propres comparateurs et aussi surcharger les opérateurs du langage de requêtes, par exemple l'addition. Ceci pose au moins trois problèmes d'optimisation : comment utiliser des accélérateurs, par exemple des index pour accélérer l'évaluation de requêtes ? Comment générer toutes les séquences de méthodes ou d'opérateurs possibles pour calculer la réponse à une requête ? Comment évaluer le coût d'une méthode programmée par l'utilisateur ?
2. Les traversées de chemins. Celles-ci sont des extensions des jointures relationnelles effectuées directement par parcours de pointeurs. Ces pointeurs implémentent les associations. Il n'est pas toujours évident de les utiliser efficacement et parfois des jointures classiques peuvent être plus performantes.
3. Les manipulations de collections. Les collections sont implémentées par des structures de données spécifiques et supportent des opérateurs spécifiques aux ensembles, par exemple union, intersection, différence, inclusion, recherche d'appartenance. Des règles de transformation nouvelles sont applicables aux collections. Il faut pouvoir en donner connaissance à l'optimiseur, qui doit être capable de les prendre en compte. De plus, évaluer le coût d'un opérateur sur collections n'est pas chose évidente.
4. La prise en compte de l'héritage et du polymorphisme. L'héritage stipule que tout objet d'une sous-classe est membre implicite de la classe dont il hérite. Cette règle doit pouvoir être prise en compte lors de l'optimisation. Elle introduit des difficultés lors des surcharges ou redéfinitions de méthodes possibles grâce au polymorphisme dans les sous-classes. Les calculs de coût à la compilation des requêtes deviennent alors très difficiles, les méthodes réellement appliquées n'étant connues qu'à la compilation.

Nous illustrons le concept de requête objet par quelques exemples sur la base représentée figure XIV.1. Celle-ci est une interprétation objet de la situation bien connue où des clients passent des commandes de produits à des fournisseurs. Une commande contient plusieurs lignes. Clients et fournisseurs sont des personnes. Les chemins de traversée sont implémentés par des attributs portant le nom des associations contenant des identifiants d'objets. Ils sont marqués par des flèches.

XIX-2-2-1. Parcours de chemins▲

SELECT P.NOM, P.VENDU.ADRESSE
FROM PRODUITS P
WHERE P.PRIX > 10.000
  AND P.VENDU.AGE > 50
  AND P.VENDU.HABITE.PAYS = "FRANCE"

SELECT C.NOM, C.ADRESSE
FROM CLIENTS C, C.PASSE M, M.LIGNE P
WHERE P.PRIX > 10.000

XIX-2-2-2. Méthodes et opérateurs▲

TYPE POINT (ATTRIBUTS X, Y COORDONNÉES ;
          REAL FUNCTION DISTANCE(P1 POINT, P2 POINT));
TYPE ZONE (ATTRIBUTS P1, P2 POINT ;
          BOOLEAN FUNCTION INCLUS(Z ZONE, P POINT));

FOURNISSEURS (NUMFOU INT, NOM VARCHAR, ADR ADRESSE, NUMPAYS INT, TEL
   TELEPHONES, LOCALISATION POINT);
CLIENTS (NUMCLI INT, NOM VARCHAR, ADR ADRESSE, NUMPAYS INT, TEL
   TELEPHONE, LOCALISATION POINT);

SELECT NUMFOU, NOM, ADRESSE
FROM CLIENTS C, FOURNISSEURS F
WHERE C.NUMCLI = :N AND INCLUS( :Z, F.LOCALISATION)
  AND DISTANCE(C.LOCALISATION, F. LOCALISATION) < 100;

TYPE FIGURE (ATTRIBUT CONTOUR LIST<POINT>;
            BOOLEAN FUNCTION INCLUS (P POINT, F FIGURE))
TYPE CERCLE (ATTRIBUT CENTRE POINT, RAYON REAL;
            CERCLE FUNCTION CERCLE(C POINT, R REAL);
            FIGURE FUNCTION INTERSECTION(C CERCLE, Z ZONE));

SELECT NUMFOU, NOM, ADRESSE
FROM CLIENTS C, FOURNISSEURS F
WHERE C.NUMCLI = :N
  AND INCLUS(F.LOCALISATION, INTERSECTION(CERCLE(C.LOCALISATION,100),:Z)

XIX-2-2-3. Manipulation de collections▲

SELECT C.NOM, C.ADRESSE
FROM CLIENTS C
WHERE :N IN
UNION(SELECT S.TELEPHONES
    FROM CLIENTS C
    WHERE ADRESSE LIKE "PARIS")

XIX-2-2-4. Héritage et polymorphisme▲

SELECT NOM, ADRESSE
FROM PERSONNES
WHERE REVENUS() > 50.000

La plupart des SGBD stockent les objets dans des pages à fentes (slotted pages). Chaque page contient en fin de page un tableau de taille variable adressant les objets de la page. La figure XIV.2 illustre une page à fentes. Le déplacement conduisant du début de la page au début de chaque objet est conservé dans un petit index en fin de page.

Comme nous l'avons déjà vu, dans les SGBDO, les objets sont désignés par des identifiants d'objets. Il est possible de distinguer identifiants physiques et identifiants logiques.

Les identifiants physiques sont rapides à décoder pour atteindre l'objet référencé. Par contre, ils ne permettent pas le déplacement libre des objets dans la base. En cas de déplacement, une technique de chaînage doit être mise en place : l'entrée de la page initiale doit indiquer que l'objet n'est plus dans la page et pointe sur son nouvel identifiant physique. Cette technique de suite (forwarder) est très lourde à gérer, surtout si les objets se déplacent souvent. On lui préférera les identifiants logiques, plus coûteux lors de l'accès, mais invariants au déplacement d'objet.

En cas de déplacement de l'objet, seule l'entrée dans la table est changée ; elle est positionnée à la nouvelle adresse de l'objet. En général, les SGBD gèrent une table d'identifiants logiques par type d'objets. La taille de la table est ainsi limitée. Pour la limiter plus encore et éviter les entrées inutiles, la table est souvent organisée comme une table hachée : chaque identifiant logique est affecté à une entrée déterminée par une fonction de hachage ; chaque entrée contient des couples de correspondance <identifiant logique-identifiant physique>. La figure XIV.3 illustre le décodage d'un identifiant logique.

Un bon modèle de stockage permet à la fois les identifiants physiques (OIDP) et les identifiants logiques (OIDL). Le choix du type d'identifiants affecte directement le coût de traversée des pointeurs.

Pour accélérer l'évaluation de requêtes avec prédicats de sélection, les systèmes offrent des index, généralement organisés comme des arbres-B contenant dans les feuilles des listes d'identifiants d'objets. Un index peut être perçu comme une fonction donnant une liste d'identifiants d'objets à partir d'une valeur d'attributs. Le coût de traversée d'un index est généralement de deux E/S, voire trois pour des très grosses collections d'objets.

Au-delà des index classiques, certains systèmes à objets offrent des index de chemins.

Il existe différents types d'index de chemins [Bertino89, Kim89]. Les index de chemin simples [Bertino89] [Kemper90] associent pour chaque valeur figurant à la fin du chemin tous les identifiants d'objets suffixes du chemin. Ils peuvent être implémentés comme des relations : chaque colonne d'un tuple correspond à une collection du chemin, en remontant depuis la fin du chemin. Le premier attribut contient la valeur figurant à la fin du chemin, les suivants contiennent des identifiants d'objets désignant les objets successivement rencontrés en parcourant le chemin à l'envers. La figure XIV.4 illustre un index de chemins simple pour le chemin Produits → Fournisseurs → Pays de la base représentée figure XIV.1.

Une première variante consiste à imbriquer les chemins, en évitant ainsi de répéter plusieurs fois un même identifiant d'objet pour chacun de ses parents. Par exemple, pour le fournisseur F1, on indiquera directement la liste des parents, pour F2 de même, si bien que l'entrée Allemagne de l'index précédent devient (Allemagne(F1(P1, P2) F2 (P1, P3) …). Un tel index est appelé index de chemin imbriqué [Bertino91]. De tels index sont plus difficiles à maintenir et à utiliser que des tables lors des mises à jour.

Les multiindex [Kim89] sont une alternative aux index de chemin. Pour chaque couple de collections (C_i, C_i+1) consécutives du chemin, on gère un index de jointure [Valduriez87] contenant les couples identifiants d'objets liés par le chemin. Le dernier index est un index classique donnant pour chaque valeur terminale du chemin l'identifiant de l'objet contenant cette valeur. Le parcours du chemin s'effectue alors par des intersections de listes d'identifiants. Chaque index est finalement un index classique qui peut être implémenté comme un arbre B. Le problème des multiindex est que chaque index doit être lu ou écrit indépendamment, ce qui nécessite des entrées-sorties supplémentaires par rapport aux index de chemin. L'utilisation de tels index est par contre plus large, par exemple pour accélérer des jointures de collections intermédiaires sur le chemin ou des sélections sur la collection feuille.

Dans les SGBD modernes, les objets associés peuvent être stockés ensemble comme un objet composite (c'est-à-dire composés d'autres objets), ou séparément comme plusieurs objets reliés par des identifiants logiques ou physiques. On distingue alors la liaison de l'incorporation d'objets.

La liaison peut être effectuée dans les deux sens, l'objet référencé pointant lui-même son ou ses objets associés. Il existe alors pour chaque objet cible un ou plusieurs liens inverses vers l'objet source. La liaison est une technique classique pour représenter les associations nécessitant le parcours d'identifiants pour retrouver les objets associés. La liaison inverse permet le parcours de l'association dans les deux sens. La liaison a le mérite de rendre les objets liés quasiment indépendants, ce qui n'est pas le cas avec l'incorporation.

L'incorporation rend les objets incorporés dépendants de l'objet englobant : ils sont détruits avec lui. Le choix entre liaison ou incorporation est donc aussi un problème de sémantique : un objet incorporé a le même cycle de vie que l'objet incorporant. Du point de vue du stockage, l'incorporation présente l'avantage de rendre les objets incorporant et incorporé accessibles simultanément. En outre, elle permet le placement des objets dans une même page, ce qui est aussi possible avec la liaison, comme nous le verrons ci-dessous. Elle présente par contre l'inconvénient de ne pas supporter le partage référentiel des objets dépendants, qui sont de fait copiés s'ils sont référencés ailleurs. La figure XIV.5 illustre la liaison et l'incorporation dans le cas de commandes et de lignes de commandes.

Pour permettre la navigation rapide d'un objet maître vers des objets liés (par exemple, des commandes aux lignes de commandes) ou pour accélérer les jointures dans le cas d'une implémentation relationnelle, il est possible de grouper différents objets liés dans une même page.

Le groupage est plus souple que l'incorporation, car il permet une vie autonome des objets liés, qui peuvent exister sans objets associés. En cas d'objets sans maître ou d'objets partagés par plusieurs maîtres, le choix de la page de stockage n'est pas évident. Pour capturer une large classe de stratégies de groupage, il est possible de définir les groupes par des prédicats de sélection ou d'association. Un prédicat de sélection permet par exemple de définir le groupe des commandes de prix supérieur à 10 000 (Commandes.prix > 10.000). Un prédicat d'association permet par exemple de définir un groupe pour chaque produit (Produits vendu Fournisseurs). Ces prédicats sont utilisés pour définir les ensembles d'objets à stocker ensemble dans une même page ou au moins dans des pages à proximité.

Les prédicats n'étant pas forcément disjoints, un objet peut appartenir logiquement à plusieurs groupes. Si l'on exclut les duplications d'objets, il faut lors du chargement choisir un groupe. Une technique possible consiste à associer des priorités à chaque prédicat de liens. Si un objet appartient à deux groupes ou plus, celui de priorité supérieure est retenu. Pour pouvoir discriminer les groupes, les priorités doivent être différentes, définies par exemple par un nombre de 0 à 10.

Afin de visualiser les informations de spécifications des groupes, il a été proposé [Amsaleg93] d'utiliser un graphe de groupage défini comme suit :

Un graphe de groupage est correct si tous les arcs pointant vers un même nœud ont une priorité différente. Les objets pointés par plusieurs liens de groupage sont donc assignés au groupe de plus forte priorité. La figure XIV.6 présente différents graphes de groupage possibles pour les fournisseurs, les produits et les commandes. Elle suppose que l'association directe des fournisseurs aux produits est gérée par le SGBD. À droite du graphe de groupage, les groupes de différents types possibles sont représentés, par exemple les groupes de fournisseurs, de produits ou les groupes mixtes.

La figure XIV.6 montre quatre possibilités de groupage des objets de collections :

1. Le groupage simple. C'est le groupage classique de deux collections selon un prédicat de lien. Ce type de groupage existe dans les bases de données en réseaux (maître et membres via un lien) et est possible dans les bases de données relationnelles selon un prédicat de jointure. Figure XIV.6a, les objets de la collection produits sont groupés simplement avec les objets de la collection fournisseurs, avec une priorité maximale de 10. Tous les produits sans fournisseurs seront groupés ensemble.
2. Le groupage conjonctif. Il permet de grouper plusieurs objets de collections différentes avec ceux d'une collection maître. Figure XIV.6b, tous les objets produits et commandes sont groupés avec leurs fournisseurs.
3. Le groupage disjonctif. Dans le cas où plusieurs maîtres se partagent un objet qui devrait être groupé avec eux, un choix doit être fait afin d'éviter les duplications d'objets. Selon le mécanisme de priorité, l'objet est alors placé dans le groupe déterminé par l'objet maître selon l'arc de poids maximal. Par exemple, figure XIV.6c, chaque objet commande sera stocké près de son fournisseur s'il existe.

Afin de regrouper et visualiser toutes les informations permettant de stocker les objets dans la base et d'y accéder, nous avons proposé [Gardarin95] d'introduire un graphe de stockage plus complet que le graphe de groupage vu ci-dessus. Ce graphe permet de représenter un schéma objet de données avec des notations proches d'UML (voir chapitre sur la conception), avec en plus les informations suivantes :

1. Les objets incorporés liés aux objets incorporants par des flèches doubles en pointillés ;
2. Les objets groupés liés aux objets groupants par des flèches simples en pointillés étiquetées par la priorité du groupage et l'éventuel prédicat, s'il ne s'agit de l'association existant entre les objets ;
3. Les index par des réseaux de lignes pointillées issus de l'attribut indexé et pointant vers la ou les collections indexées.

La figure XIV.7 représente un exemple de graphe de stockage pour la base dont le schéma a été défini figure XIV.1. Pays est incorporé dans Personnes, dont les attributs sont eux-mêmes incorporés dans Clients et Fournisseurs. Les lignes de commandes sont incorporées dans les commandes. Elles référencent les produits. Les commandes sont placées en priorité à proximité des clients, sinon à proximité des produits. Les produits sont placés à proximité des fournisseurs. Il existe un index de chemin depuis nom de produit vers produits et fournisseurs. Deux index primaires classiques sont gérés, respectivement sur numéro de commande (numco) et numéro de produit (numpro).

Un graphe de stockage induit une organisation physique des données. Il représente en fait le modèle interne de la base et est donc un élément essentiel à prendre en compte pour l'optimiseur. Le problème de l'optimiseur est de trouver le meilleur plan d'accès pour exécuter une requête compte tenu du modèle interne représenté par le graphe de stockage. Pour ce faire, l'optimiseur doit aussi prendre en compte la taille des collections et groupes. Il doit bien sûr optimiser la navigation via des pointeurs, comme nous allons le voir ci-dessous. Notez que la plupart des systèmes objet ne distinguent pas clairement le graphe de stockage et n'ont guère d'optimiseur élaboré capable de bien prendre en compte le modèle interne.

La traversée en profondeur d'abord (Depth-First-Fetch, DFF) est la méthode la plus naturelle pour évaluer une expression de chemins avec prédicats. L'algorithme suit le chemin depuis la collection racine vers la collection terminale. Chaque objet est traversé en allant toujours vers le premier objet du niveau supérieur non encore traversé, vers l'objet de même niveau s'il n'en existe pas, et en remontant lorsqu'il n'y a plus d'objet voisin. L'opérateur correspondant est un opérateur n-aire, qui s'applique sur N collections avec un prédicat possiblement vrai (tous les objets qualifient alors) pour chaque collection. DFF peut être vu comme un opérateur de jointures en cascade utilisant une méthode pipeline. La figure XIV.9 donne un sketch de l'algorithme.

// Recherche des objets d'un chemin C1.C2…Cn vérifiant les prédicats P1,P2…Pn
DFF(C1(P1).C2(P2)….Cn(Pn)) {
    i = 1 ;
    while (i≤n) {
        for each x in (Ci) {
            if Pi(x) = VRAI {
                if i < n return (x + DFF(FETCH(x.Ci+1)(Pi+1)….Cn(Pn)))
                else return(x) 
            }
        }
        i = i+1 ;
    }
}

L'avantage de DFF est qu'il s'agit d'un opérateur n-aire qui ne génère pas de résultats intermédiaires. L'algorithme assemble les objets en accédant via les OID, ce qui est efficace dans la plupart des SGBD. Les résultats sont obtenus l'un après l'autre en pipeline. L'algorithme est d'ailleurs très analogue à celui de jointures n-aire en pipeline vu dans le cadre relationnel, à ceci près qu'il navigue en suivant les pointeurs. Ainsi le SGBD peut-il retourner une réponse avant d'avoir traversé tous les objets. Intuitivement, cet opérateur est très efficace lorsque la taille mémoire est suffisante pour contenir tous les objets sur un chemin de la racine aux feuilles, c'est-à-dire au moins une page par collection. Cependant, si les objets ne sont pas groupés selon le chemin et si la taille mémoire est insuffisante, le système peut être conduit à relire de nombreuses fois une même page.

La traversée en largeur d'abord (Breadth-First-Fetch, BFF) parcourt l'arbre d'objets par des jointures binaires en avant (Forward Join, FJ) successives. Les jointures sont effectuées par parcours des pointeurs de la collection C_i vers la collection C_i+1. Ainsi, soit une expression de chemin qualifiée C₁(P₁).C₂(P₂)…C_n(P_n). Pour trouver les objets qualifiants, (n-1) jointures par références successives du type S_{i+1 =} FJ(S_i→C_i+1(P_i+1)) sont accomplies, où Si désigne une table mémorisant les objets satisfaisant le sous-chemin C₁(P₁).C₂(P₂)…C_i(P_i). Le critère de jointure est une simple traversée de pointeurs. Le prédicat P_i+1 doit être vérifié sur les objets cibles de C_i+1. L'algorithme est proche de celui réalisant la traversée en profondeur vue ci-dessus (DFF), mais réduit à deux collections, c'est-à-dire à un chemin de longueur 1. Une table intermédiaire répertoriant les identifiants d'objets qualifiants doit être générée en résultat de chaque jointure en avant. Dans la suite, nous appelons cette table table support. La jointure en avant suivante repart de la table support. La figure XIV.10 illustre l'algorithme de traversée en largeur d'abord pour trois collections, C₁, C₂ et C₃, dont les objets sont notés a_i, b_i et c_i respectivement.

L'avantage de l'algorithme en largeur d'abord est d'être basé sur des jointures binaires par référence, donc précalculées. Le coût de calcul est donc réduit. Cependant, pour accomplir la jointure entre les collections C_i et C_i+1, les états des objets de la première collection C_i doivent être chargés en mémoire pour trouver les pointeurs vers les objets de C_i+1 (contenus dans l'attribut A_i) ; les états de la seconde C_i+1 doivent aussi être chargés en mémoire pour tester le prédicat P_i+1. Si aucun groupage selon l'association n'est réalisé, des accès multiples aléatoires aux pages peuvent être nécessaires. Un tri des identifiants des objets de la deuxième collection sera alors souvent avantageux. Contrairement à l'algorithme DFF, l'algorithme BFF nécessite de conserver si possible en mémoire des résultats intermédiaires. Si l'on veut délivrer tous les objets sur les chemins qualifiants, la table support doit être étendue avec un attribut contenant les identifiants d'objets par collection traversée. L'algorithme ne permet guère de délivrer des résultats avant la traversée totale au moins des n-1 premières collections. Soulignons que dans le cas réduit de deux collections, les algorithmes DFF et BFF sont similaires.

La traversée à l'envers, c'est-à-dire en partant par la dernière collection du chemin, est aussi possible en utilisant un algorithme de jointure binaire classique, de type jointure relationnelle. Comme l'algorithme BFF, la traversée en largeur d'abord à l'envers (Reverse-Breadth-First-Fetch, RBFF) accomplit une séquence de jointures binaires entre collections voisines sur le chemin, mais procède en ordre inverse, donc à reculons. Chaque jointure est appelée une jointure inverse (Reverse Join, RJ). S'il n'y a pas de lien inverse, il s'agit d'une jointure par valeur, c'est-à-dire que le critère est l'appartenance de l'identifiant de l'objet de la seconde collection aux valeurs de l'attribut de liens de la première collection. Pour traiter une expression de chemin qualifiée C₁(P₁).C₂(P₂)…C_n(P_n) de la collection C1 à collection Cn, (n-1) jointures successives Si = RJ(Si←Ci(Pi)) sont accomplies, où Si désigne la table support des objets satisfaisant le sous-chemin C_i(P_i)…C_n(P_n) ; RJ est l'algorithme de jointure inverse testant l'appartenance de l'identifiant aux pointeurs. Une technique de jointure par hachage ou par tri-fusion peut être appliquée. La traversée à l'envers est illustrée figure XIV.11.

La traversée à l'envers est avantageuse lorsqu'une sélection directe est possible sur la dernière collection (par exemple par un index) et que cette sélection retrouve un nombre faible d'objets (forte sélectivité). Pour mémoriser le parcours, une table support est générée (voir figure XIV.11). Un avantage de la méthode est qu'à chaque pas la jointure est faite entre cette table support et la collection précédente sur le chemin. L'algorithme est bon si la table support est petite (expression de chemin sélective).

Soulignons qu'une expression de chemins peut toujours être divisée en plusieurs sous-expressions, chacune pouvant être traitée avec un algorithme différent, DFF, BFF ou RBFF. Si un prédicat très sélectif est rapidement évaluable sur une collection du chemin, on aura avantage à considérer RBFF pour la partie préfixant cette collection, puis BFF ou DFF pour la partie suffixe. Le choix d'un algorithme ou d'un autre n'est pas évident et nécessite un modèle de coût, comme nous le verrons plus loin.

La traversée par index de chemin (Path Index Traversal, PIT) bénéficie de l'existence d'un index suivant le chemin. Comme vu ci-dessus, pour une valeur d'attribut de la collection cible, l'index donne tous les sous-chemins qualifiants. Il suffit donc d'accéder à l'index pour trouver les associations d'objets satisfaisant le prédicat. Cependant, si d'autres prédicats figurent dans les collections précédant la collection indexée, il faut accéder aux objets associés dont les identifiants sont trouvés dans l'index. Cela peut être très pénalisant si les accès sont éparpillés sur les disques. Des tris sur les identifiants physiques d'objets seront souvent avantageux, car ils permettront de grouper les accès aux objets d'une même page. Une autre faiblesse des index de chemins est bien sûr les coûts de maintenance lors des mises à jour, souvent importants.

Plus qu'en relationnel, la génération de plans équivalents doit se faire par application de règles de transformation. En effet, à la différence des systèmes relationnels, les systèmes objet ou objet-relationnels ne sont pas fermés : l'implémenteur de bases de données peut ajouter ses propres types de données obéissant à des règles spécifiques de transformation, comme les types géométriques (point, cercle, etc.) vus ci-dessus. Un optimiseur d'un SGBD objet ou objet-relationnel doit donc être extensible.

Cette notion d'optimiseur extensible a été bien formalisée pour la première fois dans [Grafe93]. Un optimiseur extensible est construit autour d'une base de connaissance mémorisant les définitions de types et opérateurs associés, de méthodes d'accès, de fonctions de coût et de règles de transformation de plans d'exécution. Toutes les transformations de plans peuvent être exprimées sous la forme de règles. Comme en relationnel, les règles permettent de transformer les arbres d'opérateurs de l'algèbre représentant les requêtes en arbres équivalents. Au-delà du relationnel, pour supporter les types de données utilisateurs, l'algèbre relationnelle doit être étendue en une algèbre d'objets complexes, avec en particulier les fonctions dans les expressions de qualification et de projection, et le support d'opérations sur collections imbriquées telles que Nest, Unnest et Flatten. Une telle algèbre a été présentée au chapitre XI.

Nous représentons figures XIV.12 et XIV.13 les questions Q1 et Q3 du paragraphe 2.2 sous la forme d'arbres algébriques. L'arbre de la figure XIV.12 contient trois restrictions sur attributs ou méthodes, suivies de deux jointures par références qui traduisent le parcours de chemin. Ces deux jointures peuvent par exemple être remplacées par un opérateur de parcours du graphe en profondeur d'abord (DFF) vu ci-dessus, ou par des jointures en arrière (RBFF). Une projection finale gagnerait à être descendue par les règles classiques vues en relationnel.

L'arbre de la figure XIV.13 présente une restriction sur prédicats utilisateurs (Inclus) et une jointure sur fonction utilisateur (Distance < 100). L'optimisation de telles requêtes est difficile et nécessite des connaissances spécifiques sur les fonctions utilisateur [Hellerstein93], ici des fonctions géométriques.

Comme pour le relationnel, un plan d'exécution est un arbre annoté, l'annotation associée à chaque opérateur spécifiant l'algorithme choisi. Une règle exprime que lorsqu'un sous-arbre annoté est rencontré dans un plan d'exécution, il peut être remplacé par un autre sous-arbre annoté sous certaines conditions. Le choix d'un langage de règles pour écrire les règles de transformation est un problème difficile [Finance94]. Certaines sont simplement des règles d'équivalence, conduisant à des transformations applicables dans les deux sens. Nous les noterons simplement :

<SOUS-ARBRE> ⇔ <SOUS-ARBRE>

D'autres règles ne sont applicables que dans un sens et peuvent nécessiter des conditions. À titre d'exemple, nous les écrirons sous la forme suivante :

<SOUS-ARBRE> [<CONDITION>] ⇒ <SOUS-ARBRE>

Une telle règle signifie que lorsqu'un sous arbre est rencontré, si la condition optionnelle est satisfaite, il peut être réécrit dans le sous-arbre figurant après l'implication. En pratique, il faut en plus appliquer quelques procédures, par exemple pour changer des variables ou des annotations ; celles-ci sont supposées attachées à la règle ; elles ne sont pas mentionnées pour des raisons de simplicité.

XIX-5-2-1. Règles syntaxiques▲

JOIN(JOIN(X,Y),Z) ⇔ JOIN(X,JOIN(Y,Z));

PROJECT(JOIN(X,Y), Z) [X∩Y ∈ Z] ⇒
JOIN(PROJECT(X,Z∩X),PROJECT(Y,Z∩Y);

RESTRICT(NEST(X, G, N), Q) [ ∃ ATTRIBUT(Q) ∈ G ] ⇒
RESTRICT(NEST(RESTRICT(X, Q1), G, N), Q2);

XIX-5-2-2. Règles sémantiques▲

[FOR ALL [<VARIABLE> OF TYPE <TYPE>]*] <EXPRESSION> ⇔ <EXPRESSION>

INTERFACE CLIENTS {
    ATTRIBUT INT NUMCLI KEY, STRING NOM,
        ADRESSE CADRESSE, REF(PAYS) CPAYS, INT TELEPHONE,
        INT SEGMENT, STRING COMMENTAIRE
}
INTERFACE PAYS {
    ATTRIBUT INT NUMPAYS KEY, STRING NOM, INT NUMCONT,
        STRING COMMENTAIRE, RESIDENTS SET <CLIENTS>
}

FOR ALL C OF TYPE CLIENTS, P OF TYPE PAYS
C.CPAYS = P ⇔ C IN P.RESIDENTS

INTERFACE ADRESSE {
    ATTRIBUT INT NUM, STRING RUE,
        STRING VILLE, INT ZIP, STRING PAYS
}

FOR ALL C OF TYPE CLIENTS
C.CADRESSE.PAYS ⇔ C.CPAYS.NOM

FOR ALL C OF TYPE CLIENTS C
C.CPAYS = NIL ⇔

FOR ALL C1,C2 OF TYPE CLIENTS
C1.NUMCLI = C2.NUMCLI ⇔ C1 = C2

INTERFACE IMAGE {
    ATTRIBUT NUMCLI INT, CONTENT ARRAY[1024,1024] INT,
    OPERATION
        ARRAY[10] SUMMARY(IMAGE),
        IMAGE ROTATE (IMAGE, ANGLE),
        IMAGE CLIP (REGION)
}

SELECT CLIP(ROTATE(I,90),$ZONE)
FROM CLIENTS C, IMAGES I
WHERE C.NUMCLI = I.NUMCLI
      AND C.SEGMENT = 5 ;

FOR ALL I OF IMAGE, F OF FENETRE
CLIP(ROTATE(I,$A), F) ⇔ ROTATE(CLIP(I,ROTATE(F,-$A),$A)

SELECT ROTATE (CLIP(I, ROTATE($ZONE,-90)),90)
FROM CLIENTS C, IMAGES I
WHERE C.NUMCLI = I.NUMCLI
      AND C.SEGMENT = 5;

XIX-5-2-3. Règles de planning▲

JOIN SORT-MERGE (X,Y) ⇔ JOIN NESTED-LOOP (X,Y)
JOIN SORT-MERGE (X,Y) ⇔ JOIN HASH-TABLE(X,Y)

JOINFJ(X,Y) [PATH-INDEX(X,Y)] ⇒ JOINPATH-INDEX(X,Y)
DFF(A,B,C…N)[PATH-INDEX(A,B,C…N)] ⇒ JOINPATH-INDEX(X,Y)

Quelle est la taille de l'espace de recherche des plans pour une question donnée ? Tout dépend bien sûr de la forme de la question et des règles qui s'y appliquent. En général, l'optimisation de requêtes objet conduit à des espaces de recherche plus grands que pour les requêtes relationnelles. Cela provient surtout du fait que les requêtes sont souvent plus complexes et les règles de transformation plus nombreuses.

Prenons par exemple le cas d'une expression de chemin linéaire qualifiée. De telles requêtes s'appellent des requêtes chaînes (voir figure XIV.14). Le profil de requêtes OQL correspondant est :

SELECT (X1, X2….Xn)
FROM X1 IN C1, X2 IN C1.AC2….Xn IN Cn-1.ACn
WHERE …

Pour simplifier, supposons l'absence d'index de chemins. Chaque collection est reliée à chacune de ses voisines par une association multivaluée (le cas monovalué est un cas dégénéré).

FJ et RJ sont les deux algorithmes de jointures, l'un par parcours de référence en avant (FJ), l'autre par jointure sur valeur de référence en arrière (RJ). DFF est l'opérateur n-aire de jointure par référence parcourant le graphe en profondeur d'abord. Dans le cas où DFF n'est pas utilisé, le problème revient à calculer le nombre d'ordres de jointures possibles avec deux opérateurs de jointures en évitant les produits cartésiens [Tan91], [Lanzelotte93]. On obtient pour l'espace de recherche de jointures binaires de n collections :

Si l'on introduit l'opérateur DFF, la taille de l'espace de recherche devient bien sûr plus grande. Soit SS(n-1) l'espace de recherche pour traverser (n-1) collections. On a :

SS(n) = BJ_SS(n) + PC_SS(n)

BJ_SS(n) est l'espace de recherche pour les jointures binaires et PC_SS(n) est le nombre d'arbres annotés avec au moins un nœud DFF. Pour déterminer la valeur de PC_SS(n), supposons tout d'abord un seul DFF avec trois collections : celles-ci sont traitées ensemble par cet opérateur DFF et peuvent être vues comme une unique collection ; pour le reste, la longueur du chemin est réduite de 2, ce qui signifie que SS(n - 2) plans peuvent être générés. Il existe n - 2 positions parmi les n collections où il est possible d'appliquer l'opérateur DFF sur trois collections. Pour la même raison, il existe n - 3 positions où appliquer DFF sur quatre collections ; et ainsi de suite ; finalement, il existe 2 positions où appliquer DFF sur n - 1 collections et 1 position pour appliquer DFF sur les n collections. En sommant tous les cas analysés, on obtient une borne supérieure de PC_SS(n). Ainsi, une bonne approximation du nombre de plans est :

avec SS(1) = 1, SS(2) = 2, SS(3) = 9.

Ainsi, la table présentée figure XIV.15 donne une approximation du nombre de plans pour des chemins de longueur 1 à 8. On constate qu'au-delà de 8, l'espace devient rapidement important. Il est donc très coûteux pour un optimiseur de considérer toutes les solutions, surtout dans les cas de requêtes plus complexes que les requêtes chaînes.

Un optimiseur extensible doit donc permettre la prise en compte complète de nouveaux types de données, avec opérateurs, règles, etc. Il s'agit donc d'un véritable système expert spécialisé. La figure XIV.16 représente une architecture possible pour un optimiseur extensible [Lanzelotte91]. Celui-ci explore l'espace des plans d'exécution. Un tel optimiseur accepte de l'administrateur la définition de règles de transformation d'arbres algébriques annotés. Il est extensible, en ce sens qu'il est possible d'ajouter de nouveaux types et de nouvelles règles. Il transforme un arbre algébrique d'entrée en un plan d'exécution quasiment optimal. Pour cela, il utilise le schéma de stockage de la base. Le générateur de plan applique les règles. La stratégie d'évaluation est basée sur un modèle de coût et tend à réduire le nombre de plans explorés afin d'atteindre le but qui est un plan de coût proche du minimal possible, dit quasi optimal.

Le modèle de coût utilise des statistiques sur les données de la base pour estimer le coût d'une opération. Ces statistiques se composent d'informations sur les collections de la base comme la cardinalité (nombre d'objets) de ces collections, la taille moyenne des objets, le nombre de valeurs distinctes d'un attribut, la présence d'index et de groupes d'objets. Un bon modèle de coût doit prendre en compte le placement des objets dans des groupes (clustering). En effet, une collection C peut être divisée en n groupes notés C₁, C₂…C_n. Les techniques de groupage permettent de placer dans un même groupe des objets de collections différentes.

Plus précisément, pour chaque collection d'objets C nous utilisons les statistiques suivantes :

• ||C|| la cardinalité de la collection C,
• |C| le nombre de pages de la collection C,
• ||C_i|| la cardinalité du groupe i de la collection C,
• |C_i| le nombre de pages du groupe i de la collection C,
• SC la taille moyenne des objets dans la collection C.

Afin d'évaluer le coût de la navigation entre objets, il est nécessaire d'estimer finement les cardinalités des associations entre collections. Soient deux collections C1 et C2 reliées par un chemin de traversée implémenté par des pointeurs de C1 vers C2. Un tel chemin C1 → C2 sera caractérisé par les statistiques suivantes :

• Fan_C1,C2 le nombre moyen de références d'un objet de C1 vers des objets de C2 ;
• D_C1,C2 le nombre moyen de références distinctes d'un objet de C1 vers des objets de C2 ;
• X_C1,C2 le nombre d'objets de C1 n'ayant pas de références (ou des références nulles) vers des objets de C2.

À partir de ces paramètres, nous pouvons calculer le nombre de références distinctes des objets de C1 ayant au moins une référence non nulle vers des objets de C2 par la formule :

De plus, nous supposons connus les paramètres suivants, dépendant essentiellement de choix d'implémentation du système :

• b le degré moyen des arbres-B utilisés (par exemple 256 clés par page) ;
• BLevel(I) le nombre de niveaux d'un index I (souvent 3) ;
• S_p la taille d'une page (par exemple 4K) ;
• Proj_Cost le coût moyen d'extraction d'un attribut d'un objet ;
• m la taille mémoire disponible en page ;
• Cost_load_page le coût de chargement d'une page en mémoire (une E/S).

Tous ces paramètres sont donc utilisés par le modèle de coût détaillé ci-dessous.

Lorsque plusieurs collections sont groupées ensemble par des associations, il n'est pas évident de déterminer le nombre de pages à balayer pour trouver les objets dans l'une d'elles. Si une collection A n'est pas groupée avec d'autres collections, il y a objets au plus dans une page et le nombre total de pages après chargement séquentiel peut être calculé comme suit :

Dans le cas de plusieurs collections groupées, certaines pages peuvent être homogènes, d'autres contenir des objets de différentes collections. Une méthode pour estimer le nombre total de pages d'une collection groupée avec d'autres a été proposée dans [Tang96]. Supposons que la collection B soit groupée avec la collection A (voir figure XIV.17). Rappelons que nous notons respectivement S_A et S_B les tailles moyennes des objets des collections A et B, et que S_A et S_B sont supposées inférieures à la taille de la page. Estimons tout d'abord la taille de la collection A qui est la racine de l'arbre de groupage. Il existe deux partitions physiques pour A après le placement des deux collections, l'une contenant des objets groupés avec des objets de B notée Cl_A→B, l'autre ne contenant que des objets de A notée Cl_A.

La partition Cl_A contient les objets A ne référençant pas d'objets B, donc ||Cl_A||=X_A,_B, d'où l'on déduit la taille de cette partition :

Pour Cl_A→B, le nombre d'objets de A dans cette partition est ||A||-X_A,B. La taille d'un groupe autour d'un objet A est S_ClA→B = S_A+(Z_A,B*S_B), d'où l'on déduit :

Le nombre total de pages de la collection A est donc donné par :

|A| = |A|ClA + |A|ClA→B

D'une manière similaire, nous pouvons estimer le nombre de pages de la collection B, une collection non-racine dans le graphe de placement. Les différentes partitions composant la collection B sont notées Cl_A→B et Cl_B.

• Pour Cl_B, le nombre d'objets de B non référencés par un quelconque objet de A est ||B||-(||A||*D_A,B), d'où nous déduisons :

  

• Pour Cl_A→B, la taille et le nombre d'objets par groupe reste le même que celui calculé ci-dessus, mais le nombre de groupes auxquels accéder est maintenant X'_ClA→B= Min(Z_A,B*X_A,B, X_A,B). Nous obtenons donc :

Le nombre total de pages de la collection B est obtenu par :

|B| = |B|ClA + |B|ClA→B

Ainsi, en étudiant la taille des différentes partitions, il est possible de calculer la taille globale en nombre de pages d'une collection groupée.

Le modèle de coût doit permettre de calculer le nombre de pages auxquelles accéder lors d'une sélection d'une collection par un prédicat. Dans le cas de bases de données relationnelles, la formule de Yao [Yao77] permet de calculer le nombre de blocs contenant au moins un enregistrement lors d'une sélection de k enregistrements parmi n.

Dans le cas d'une collection C groupée avec d'autres, il n'est pas possible d'appliquer simplement la formule de Yao pour estimer le nombre de pages auxquelles accéder lors d'une sélection par un prédicat P par Yao(||C||,|C|,Sel(P)*||C||). Le problème est qu'une collection groupée est composée de plusieurs partitions. Certains objets sont groupés avec des objets de collections différentes. Ainsi, la distribution des objets dans les pages n'est pas uniforme, bien que les collections soient supposées indépendantes d'un point de vue probabiliste. Il est possible d'appliquer la formule de Yao à chaque partition, après avoir déterminé la taille de chaque partition comme vu ci-dessus, soit ||C||_i objets et |C|_i pages pour la partition i. Nous obtenons alors la formule de Tang pour le calcul des entrées-sorties [Tang96].

Si les objets à sélectionner sont placés uniformément dans les partitions, on sélectionne k_i = (||C_i||/||C||)*k dans la partition i. Quand les objets qui satisfont le prédicat de recherche ne sont pas placés uniformément, il faut calculer la sélectivité du prédicat dans chaque partition pour calculer k_i. Bien que dérivée de la formule de Yao, la formule de Tang est plus générale que celle de Yao, qui en est un cas particulier pour une collection avec une seule partition.

Avec l'approche objet, les attributs peuvent être publics ou privés. Les attributs publics sont directement accessibles et le coût d'extraction peut être assimilé à une constante. Il peut aussi être plus précisément déterminé en fonction du type de l'attribut et de sa longueur en octets.

Les attributs privés sont manipulés par des méthodes. Déterminer le coût d'une méthode n'est pas chose simple. Deux approches ont été proposées pour cela.

Par exemple, si une classe Géométrie publie une fonction distance(géométrie), elle pourra aussi publier une fonction coût_distance(géométrie). Le coût pourra être très différent selon les géométries sur lesquelles s'applique la fonction : il est par exemple beaucoup plus simple de calculer la distance de deux points que celle de deux polygones.

Au départ, le coût de la méthode est inconnu, et estimé par exemple comme une projection sur attribut. Puis, suite aux requêtes ou à des demandes d'estimation de l'administrateur (par une requête spécifique ANALYZE <méthode>), la méthode est exécutée sur un échantillon de N objets. Une table est gérée dans la métabase pour maintenir le coût moyen observé, de schéma simplifié COSTMETHOD (coût real, nombre int), coût étant le coût moyen et nombre le nombre d'exécutions observées. La table peut aussi mémoriser le type des paramètres, les heures d'appels, etc., afin d'obtenir des statistiques plus fines.

Ce coût dépend évidemment de l'algorithme de traversée de chemin utilisé. Nous analysons ici le cas où une expression de chemin avec prédicats est évaluée en utilisant l'algorithme en profondeur d'abord (DFF) vu ci-dessus. Soit une expression de chemin entre des collections C₁, C₂…C_n qualifiée par des prédicats P₁, P₂…P_n à chaque niveau. Une telle expression est notée C₁ (P₁).C₂ (P₂)… C_n(P_n). Désignons par Ai l'attribut de C_i-1 référençant un ou plusieurs objets de la collection C_i. Soit Si la sélectivité du prédicat P_i (S_i = Sel(P_i)). L'algorithme DFF accède successivement, pour chaque objet de la collection de niveau i satisfaisant le prédicat P_i, à l'attribut pointant sur les objets de la collection (i+1). Suivant ces liens, il lit les pages successives des collections en profondeur d'abord. Pour simplifier, nous supposons qu'il existe au moins une page disponible en mémoire par collection.

Calculons tout d'abord le nombre de références Refi distinctes moyennes pointant d'un objet de la collection C_i-1 vers un objet de C_i dans le chemin, soit Refi = (1-Prob_i)*||C_i||. Prob_i est la probabilité qu'un objet de la collection Ci ne soit pas pris en compte dans le chemin, probabilité calculée par la formule :

Selon la taille mémoire disponible, trois cas sont possibles :

• Si la mémoire disponible p est assez grande pour contenir toutes les pages du chemin, chaque page est chargée une fois et une seule. Selon que le groupage est effectué par la référence ou non, on effectue l'accès à Ref_i objet de la collection en 0 ou en Tang(C_i,Ref_i) entrées-sorties, d'où l'on calcule le nombre de pages lues :
  
• Si le nombre de pages disponibles en mémoire p est exactement la taille du chemin (p = n), nous obtenons le cas limite très défavorable :
  
• Si le nombre de pages disponibles en mémoire p est compris entre n et Page_min, la mémoire ne peut contenir toutes les pages nécessaires à l'évaluation de l'expression de chemin. Le coût d'entrées-sorties dépend de la politique de remplacement des pages du SGBD. Certaines pages devront être lues plusieurs fois. Il est possible d'approcher le nombre d'entrées-sorties par une fonction linéaire entre Page_min et Page_max, comme suit :
  

Finalement, le coût d'évaluation d'un prédicat P constitué d'une expression de chemin qualifiée avec p pages disponibles en mémoire centrale est :

Le coût de calcul associé à l'évaluation d'un tel prédicat est le coût de projection plus le coût d'évaluation des prédicats élémentaires pour chaque objet traversé, soit :

CPU_Eval_Cost(P) = ||C1|| * (CPU_Pr oj_Cost)

En dehors des parcours de références évalués ci-dessus pour l'algorithme DFF, les algorithmes de jointures sont analogues à ceux des bases relationnelles. Vous pouvez donc vous reporter au chapitre concernant l'optimisation de requêtes dans les BD relationnelles pour trouver les formules de coût applicables. Des formules plus détaillées pourront être trouvées dans [Harris96]. Plus généralement, en dehors du groupage des objets, des parcours de références et des index de chemins, les BD objet n'ont guère d'autres spécificités d'implémentation.

Les algorithmes combinatoires accomplissent une marche au hasard dans l'espace de recherche sous la forme d'une suite de déplacements. Un déplacement dans cet espace est généré par application d'une règle de transformation sur le plan d'exécution. Un déplacement est appelé descendant s'il diminue le coût du plan, montant s'il l'augmente. Un état (donc un plan) est un minimum local si tout déplacement unitaire augmente son coût. Le minimum global est celui parmi les minima locaux qui a le plus faible coût. Cette classe d'algorithmes inclut l'amélioration itérative (Iterative Improvement [Nahar86]), le recuit simulé (Simulated Annealing [Ioannidis87]), l'optimisation deux phases (Two Phase Optimization [Ioannidis90]) et la recherche taboue (Tabu Search [Glover89, Glover90]). Nous présentons en détail ces méthodes ci-dessous.

L'amélioration itérative commence par un plan d'exécution initial choisi plus ou moins aléatoirement, par exemple celui résultant de la compilation directe de la requête utilisateur. Ensuite, seuls les déplacements descendants sont acceptés. C'est l'optimisation locale. Quand le minimum local est atteint, l'algorithme génère au hasard un nouveau plan, et recommence l'optimisation locale à partir de ce nouveau plan. Le processus est répété jusqu'à atteindre une condition d'arrêt, par exemple l'épuisement du temps d'optimisation. Le minimum global est le meilleur minimum local trouvé lors de l'arrêt. L'algorithme est donné en pseudocode figure XIV.18.

Procedure II(Question) {
    p = Initial(Question); // générer un plan initial
    PlanOptimal = p; // Initialiser le plan optimal
    while not(condition_arrêt) do { // Boucle d'optimisation globale
        while not (condition_locale) do { // Boucle d'optimisation locale
            p' = déplacer(p); // Appliquer une transformation valide à p
            if (Coût(p')<Coût(p)) then p = p'; // Garder si moins coûteux
        }
        // Sélectionner le plan optimal
        if coût(p)<coût(PlanOptimal) then PlanOptimal = p;
        p = Random(p); // Se déplacer au hasard vers un autre plan
    }
    Return(PlanOptimal);
}

Le recuit simulé part également d'un plan initial choisi plus ou moins aléatoirement et génère des plans successifs par application de règles de transformation valide de ce plan. À la différence de l'amélioration itérative, le recuit simulé accepte à la fois des déplacements descendants et montants. L'idée originelle est de simuler le refroidissement d'un métal recuit : tant que le métal est chaud, les mouvements de molécules sont nombreux, puis ils décroissent comme la température. Donc, quand le système est chaud, les déplacements montants qui détériorent le coût du plan sont admis afin de permettre une exploration plus large de l'espace autour du plan en cours d'analyse, pour découvrir d'autres minima locaux. Ces déplacements sont permis avec une probabilité qui décroît avec la température : P = e^{- DeltaCoût/Température}. Le paramètre Température représente la température du système. Il décroît au fur et à mesure de l'avancement de l'optimisation, si bien que les mouvements ascendants sont acceptés avec une probabilité de plus en plus faible. DeltaCoût est la différence de coût entre les deux plans. Quand la condition d'arrêt est atteinte (temps épuisé), le meilleur plan traversé est sélectionné et retenu comme pseudooptimal. La figure XIV.19 donne la procédure correspondante en pseudocode.

Procédure SA(Question) {
    p = Initial(Question); // générer un plan initial
    PlanOptimal = p; // Initialiser le plan optimal
    T = T0; // Initialiser la température
    while not(condition_arrêt) do { // Boucle d'optimisation globale
        while not(equilibrium) do { // Boucle d'optimisation locale
            p' = déplacer(p); // Appliquer une transformation valide à p
            delta = cost(p')-cost(p); // Calculer la différence de coût
            if (delta<0) then p = p'; // Si coût réduit prendre le nouveau plan
            // Si coût accru, accepté si chaud
            if (delta>0) then p = p' with probability e- delta/T;
            // Maintenir le plan optimal
            if cost(p)<cost(PlanOptimal) then PlanOptimal = p;
        }
        T = reduce(T); // Réduire la température
    }
    Return(PlanOptimal);
}

L'amélioration itérative travaille efficacement pour couvrir de grands espaces et trouver rapidement des minima locaux. Elle ne garantit guère une couverture fine autour de ces minima. Le recuit simulé est bien adapté pour explorer autour d'un minimum local. D'où l'idée de combiner les deux [Ioannidis90], ce qui conduit à l'optimisation deux phases. Tout d'abord, une phase amélioration itérative (II) est exécutée pour trouver les états initiaux de la phase recuit simulé (SA) suivante. Ainsi, l'optimisation deux phases travaille comme suit [Steinbrunn97] :

1. Pour un petit nombre de plans aléatoirement sélectionnés, des minima locaux sont cherchés en appliquant II, puis
2. À partir du (ou des) moins coûteux de ces minima locaux, SA est appliqué afin d'explorer le voisinage pour trouver de meilleures solutions.

Cette méthode mixte peut donner de bons résultats à condition de bien régler les différents paramètres (temps de chaque phase, température).

La recherche taboue (TS) est une procédure du type métaheuristique très efficace pour l'optimisation globale [Glover89]. L'idée principale est de faire à chaque pas le meilleur déplacement possible, tout en évitant une liste de plans tabous. L'utilisation d'une liste de tabous permet d'éviter des recherches inutiles et de converger plus vite vers des solutions proches de l'optimal. TS part d'un plan initial généré aléatoirement, et accomplit les meilleurs mouvements non interdits successivement. À chaque itération, la procédure génère un sous-ensemble V* de l'ensemble des voisins non interdits du plan courant. Le sous-ensemble ne contient donc pas de plans de la liste des tabous. Les plans déjà explorés sont généralement retenus, au moins pour un temps, dans la liste des tabous, ce qui évite en général de boucler. La liste des tabous est mise à jour chaque fois qu'un nouveau plan est exploré pour mémoriser les plans déjà vus. La figure XIV.20 donne le pseudocode correspondant à cet algorithme.

Procedure TS(Question) {
    p = Initial(Question); // générer un plan initial
    PlanOptimal = p; // Initialiser le plan optimal
    T = φ; // initialiser la liste taboue
    while not(condition_arrêt) do { // boucle globale
        // accepter tous les mouvements non tabous
        générer V*⊆N(p)-T en appliquant déplacer(p);
        choisir le meilleur plan p ∈ V*; // Prendre le meilleur plan
        T = (T-(plus vieux))∪{p}; // Mettre à jour la taboue liste
        // maintenir le plan optimal
        if coût(p)<coût(PlanOptimal) then PlanOptimal = p;
    }
    return(PlanOptimal);
}

La performance de tous les algorithmes précédents dépend fortement de la distribution de la fonction de coût sur l'espace de recherche. Alors que le recuit simulé (SA) et la recherche taboue (TS) dépendent fortement du plan initial, l'amélioration itérative (II) et l'optimisation deux phases (TP) utilisent une transformation aléatoire pour explorer cet espace. Pour améliorer les performances de ces algorithmes, des méthodes de transformation d'arbres introduisant une meilleure couverture de l'espace de recherche ont été mises au point. Ce sont par exemple l'échange de jointures et le swap [Swami89, Lanzelotte93]. L'échange de jointure permute aléatoirement des relations alors que le swap échange des parties d'arbres. De telles méthodes ont été introduites seulement pour les jointures relationnelles. Il est possible de les étendre au cas objet.

Suite aux mouvements ascendants, SA est généralement plus lente que les autres méthodes, mais trouve souvent de meilleurs plans que II quand le temps de recherche est suffisant. TP combine les avantages de SA et II. Il a été montré [Ioannidis90] que TP trouve en général de meilleurs plans que SA et II. TS est rapide, mais accomplit une recherche agressive. En conséquence, l'algorithme peut rester bloqué sur un minimum local. Ceci peut être évité avec une longue liste taboue, mais la recherche ralentit alors l'algorithme.

II, SA, TP et TS utilisent tous une fonction appelée déplacer. Celle-ci applique l'une des règles de transformation pour trouver un plan équivalent. Comme vu ci-dessus, dans une base de données objet ou objet-relationnelle avec beaucoup de types, le nombre de règles peut être important. Certaines ne provoquent que de petits déplacements dans l'espace des plans, d'autres de beaucoup plus larges. Il faudrait donc pouvoir introduire des transformations permettant d'appliquer des séquences de règles, et donc de faire de grands sauts dans l'espace des plans. Nous allons étudier une méthode permettant de telles transformations dans la section suivante.

L'algorithme génétique (GA) est un algorithme d'optimisation basé sur les principes d'évolution des organismes dans la nature : l'algorithme cherche à générer les meilleurs éléments d'une population en combinant les meilleurs gènes ensemble. C'est une famille d'algorithmes utilisés dans la recherche d'extrêmes (minimum ou maximum) de fonctions à plusieurs variables [Holland75, Goldberg89]. Ces fonctions sont généralement définies sur des domaines discrets vastes et complexes. Dans notre cas, il s'agit de retrouver idéalement le minimum global de la fonction de coût dans l'espace des plans. Au lieu de travailler sur une solution particulière à chaque étape, l'algorithme considère une population de solutions. Diverses sortes d'algorithmes génétiques ont été proposées pour différentes tâches d'optimisation. La figure XIV.21 représente un algorithme type utilisable pour la recherche du meilleur plan.

Voici les fonctions des principaux blocs d'un tel algorithme :

• Initialisation génère une petite population initiale de solutions (dans notre cas, des plans d'exécution) couvant l'espace de recherche.
• Mutation choisit une solution (c'est-à-dire un plan) de la population, et lui applique des règles de transformation.
• Croisement choisit deux solutions dans la population et échange leurs gènes communs (dans notre cas, des sous-arbres équivalents) pour générer deux nouvelles solutions.
• Évaluation évalue, pour chaque solution, la fonction à optimiser, dans notre cas la fonction de coût.
• Tri trie la population en fonction du coût.
• Sélection choisit un certain nombre des meilleurs éléments comme parents pour la prochaine génération.
• Fin test le critère d'arrêt afin de stopper l'optimisation.

Le cœur de l'algorithme est la génération d'une nouvelle population par les opérateurs de mutation et de croisement. À chaque génération, une partie de la population subit la mutation et l'autre le croisement. La mutation est identique au déplacement des algorithmes vus ci-dessus. Ce qui est nouveau, c'est le croisement qui permet de construire une solution à partir de deux solutions. Avec la sélection naturelle, il est permis de penser que le croisement ne laissera se propager que les bons gènes, pour converger vers les bons plans. En résumé, la notion d'algorithme génétique peut être définie comme suit :

Nous appliquons maintenant l'algorithme génétique à l'optimisation des expressions de chemins. Comme vu ci-dessus, différentes méthodes de jointures peuvent être appliquées : la jointure n-aire DFF en profondeur d'abord, la jointure binaire en largeur d'abord notée FJ (plusieurs jointures peuvent être exécutées successivement, ce qui donne l'algorithme BFF), la jointure en arrière notée RJ, et la traversée d'un index de chemins lorsqu'il en existe un, notée PI. Toutes ces méthodes apparaissent comme des gènes permettant de générer la population des plans. La figure XIV.22figure XIV.22 représente la base de gènes avec cinq collections liées par une chaîne d'association. S'il n'y a ni lien inverse, ni index de chemin, le nombre total de gènes est le nombre de cellules dans le triangle supérieur de la généralisée à n, soit :

Genes = Σ 1 + 2 + … + (n - 1) + 2 * (n - 1) = (n2 + 3 * n - 2)/2

Dans tous les cas, le nombre de gènes est de l'ordre de O(n²). Un plan d'exécution peut être vu comme une combinaison de gènes dont le résultat permet le parcours du chemin, dans un sens ou dans l'autre, ceci afin de trouver le résultat de la requête. L'objectif de l'optimiseur est de trouver la meilleure combinaison de gènes pour obtenir le plan de coût minimal.

L'étape d'initialisation consiste à générer aléatoirement une population initiale de plans. Notons qu'une telle population est générée par des parcours aléatoires dans la base de gènes de la figure XIV.22, depuis la collection source jusqu'à la collection cible. De tels parcours évitent les produits cartésiens, ce qui est généralement sage.

La mutation est un des opérateurs importants d'une méthode génétique. À chaque étape, un certain pourcentage des plans doit subir une mutation. Cette procédure consiste simplement à sélectionner un sous-arbre et à lui appliquer une règle de transformation valide. Quelques exemples de mutation possibles sont représentés figure XIV.23. La mutation apporte de nouveaux gènes qui peuvent ne pas exister dans la population courante.

Cet opérateur consiste à mixer deux éléments de la population pris plus ou moins au hasard. Par exemple, deux plans sont choisis et leurs sous-arbres communs sont échangés. Deux sous-arbres sont équivalents s'ils ont les mêmes feuilles et génèrent les mêmes résultats. La figure XIV.24 illustre un croisement. Alors que la mutation transforme un plan en l'un de ses voisins, en accomplissant de petits mouvements, le croisement peut accomplir de plus larges transformations. Il permet ainsi de sortir de zone voisine d'un minimum local, en sautant vers une autre partie de l'espace de recherche.

La figure XIV.25 donne le pseudocode de l'algorithme génétique appliqué à l'optimisation des expressions de chemins. Nous utilisons le tableau Popu pour représenter la population. Chaque élément contient deux variables : un plan et son coût. BasePopu contient les plans subissant le croisement ou la mutation. Comme la population s'accroît après le croisement, la procédure de sélection est appliquée avant de passer à la nouvelle génération. Celle-ci conserve les plans de coûts minimaux. Pendant le croisement, le plus grand sous-arbre commun des deux parents est choisi. Si deux parents n'ont pas de sous-arbre commun, ils sont soumis à la mutation. Les plans résultants du croisement sont placés de BasePopu + 1 à NewPopu. Part est le pourcentage de la population effectuant un croisement.

Procedure GA(Question) {
    Générer(Popu[BasePopu]) ; // Initialiser la population aléatoirement
    Sort(Popu) ; // Trier la population des plans par coût croissant
    PlanOptimal = Popu[0] ; // Garder le meilleur plan trouvé
    While not (condition_arrêt) do {
        Pourcent = 0;
        While Pourcent < Part * BasePopu do {
            // Appliquer croisement à Part de la population
            p1 = Popu[Random(BasePopu)] ; // Choisir p1 et p2 de Popu
            p2 = Popu[Random(BasePopu)] ; // aléatoirement
            Croisement(p1, p2) ; // Les croiser si possible
            Pourcent = Pourcent + 2 ;
        }
        For le reste de Popu do Mutation ; // Mutation pour les autres
        For (i=0 ; i < NewPopu ; i++) do evaluate(Popu[i]) ; // Calcul du coût
        Trier(Popu) ; // Trier la population par coût croissant
        PlanOptimal = Popu[0] ; // Garder le meilleur plan trouvé
    }
    return(PlanOptimal) ;
}

Des expériences effectuées avec cet algorithme ont montré qu'il pouvait être amélioré en ajoutant des plans aléatoirement générés à chaque génération, ceci afin de garantir la diversité des plans explorés [Tang96]. Les limites de tels algorithmes d'optimisation appliqués aux bases de données, notamment dans le cas d'un très grand nombre de règles, restent encore à découvrir.