root/traduc/branches/bv747/manuel/geqo.sgml

<!--
$Header: /var/lib/cvs/pgsql-fr/sgml/geqo.sgml,v 1.5.2.1 2005/03/20 22:34:40 guillaume Exp $
Genetic Optimizer
-->

 <chapter id="geqo">
  <docinfo>
   <author>
    <firstname>Martin</firstname>
    <surname>Utesch</surname>
    <affiliation>
     <orgname>
      University of Mining and Technology
     </orgname>
     <orgdiv>
      Institute of Automatic Control
     </orgdiv>
     <address>
      <city>
       Freiberg
      </city>
      <country>
       Germany
      </country>
     </address>
    </affiliation>
   </author>
   <date>1997-10-02</date>
  </docinfo>

  <title id="geqo-title">Optimiseur génétique de requêtes
    (<foreignphrase>Genetic Query Optimizer</foreignphrase>)</title>

  <para>
   <note>
    <title>Auteur</title>
    <para>
     Écrit par Martin Utesch (<email>utesch@aut.tu-freiberg.de</email>)
     de l'institut de contrôle automatique de l'université des mines et de 
     technologie de Freiberg, Allemagne.
    </para>
   </note>
  </para>

  <sect1 id="geqo-intro">
   <title>Gestion des requêtes comme un problème complexe d'optimisation</title>

   <para>
    Parmi tous les opérateurs relationnels, le plus difficile à exécuter et à
    optimiser est la jointure (<firstterm>join</firstterm>). Le nombre de plans
    alternatifs pour répondre à une requête croît de façon exponentielle avec le
    nombre de jointures inclus. Un effort supplémentaire d'optimisation est dû
    au support d'une variété de <firstterm>méthodes de jointure</firstterm>
    (par exemple les boucles imbriquées, les jointures de découpage, les
    jointures d'assemblage dans <productname>PostgreSQL</productname>) pour
    exécuter des jointures individuelles et une diversité
    d'<firstterm>index</firstterm> (par exemple R-tree, B-tree, découpage 
    dans <productname>PostgreSQL</productname>) comme chemins d'accès des
    relations.
   </para>

   <para>
    L'implémentation de l'optimiseur de <productname>PostgreSQL</productname>
    réalise une <firstterm>recherche pratiquement exhaustive</firstterm> sur
    tout l'espace des stratégies alternatives. Cet algorithme, tout d'abord
    introduit dans la base de données <quote>System R</quote>, produit un ordre
    de jointure presque optimal mais peut prendre beaucoup de temps et d'espace
    mémoire lorsque le nombre de jointures dans une requête devient important.
    Ceci rend inapproprié l'optimiseur ordinaire de requêtes de
    <productname>PostgreSQL</productname> pour les domaines d'applications des
    bases de données ayant besoin de requêtes complexes, comme en intelligence
    artificielle.
   </para>

   <para>
    L'institut de contrôle automatique de l'université des mines et de 
    technologie, basé à Freiberg, Allemagne, a rencontré les problèmes décrits
    car ces employés voulaient utiliser le DBMS
    <productname>PostgreSQL</productname> comme moteur pour leur système de
    support pour la maintenance d'une grille de courant électrique. Le DBMS
    avait besoin de gérer des requêtes comprenant des jointures larges pour la
    machine d'inférence du système de connaissances.
   </para>

   <para>
    Les difficultés en terme de performance pour l'exploration des plans de
    requêtes possibles ont créé la demande du développement d'une nouvelle
    technique d'optimisation.
   </para>

   <para>
    Dans la suite, nous décrivons l'implémentation d'un <firstterm>algorithme
    génétique</firstterm> pour résoudre le problème des ordres de jointure
    d'une façon efficace pour les requêtes impliquant un grand nombre de ces
    jointures.
   </para>
  </sect1>

  <sect1 id="geqo-intro2">
   <title>Algorithmes génétiques</title>

   <para>
    L'algorithme génétique (<acronym>GA</acronym>) est une méthode
    heuristique d'optimisation qui opère via des recherches déterminées au
    hasard. L'ensemble des solutions possibles pour le problème d'optimisation
    est considéré comme une <firstterm>population</firstterm>
    d'<firstterm>individus</firstterm>. Le degré d'adaptation d'un individu
    dans son environnement est spécifié par sa <firstterm>forme
    physique</firstterm>.
   </para>

   <para>
    Les coordonnées d'un individu dans l'espace de recherche sont représentées
    par des <firstterm>chromosomes</firstterm>, en fait un ensemble de chaînes
    de caractères. Un <firstterm>gène</firstterm> est une sous-section d'un
    chromosome qui code la valeur d'un seul paramètre en cours d'optimisation.
    Les codages typiques pour un gène pourraient être
    <firstterm>binary</firstterm> ou <firstterm>integer</firstterm>.
   </para>

   <para>
    À travers la simulation des opérations évolutives
    (<firstterm>recombinaison</firstterm>, <firstterm>mutation</firstterm> et
    <firstterm>sélection</firstterm>), de nouvelles générations de points de
    recherche sont trouvées affichant une meilleure forme physique que leurs
    ancêtres.
   </para>

   <para>
    D'après la <acronym>FAQ</acronym> de <systemitem
    class="resource">comp.ai.genetic</>, il ne peut pas être dit plus fortement
    qu'un <acronym>GA</acronym> n'est pas une recherche effectuée seulement au
    hasard. Un <acronym>GA</acronym> utilise des processus stochastiques mais
    le résultat n'est pas du tout dû au hasard (mieux que cela). 
   </para>

   <figure id="geqo-diagram">
    <title>Diagramme structuré d'un algorithme génétique</title>

    <informaltable frame="none">
     <tgroup cols="2">
      <tbody>
       <row>
        <entry>P(t)</entry>
        <entry>génération des ancêtres au temps t</entry>
       </row>

       <row>
        <entry>P''(t)</entry>
        <entry>génération des descendants au temps t</entry>
       </row>
      </tbody>
     </tgroup>
    </informaltable>

<literallayout class="monospaced">
+=========================================+
|>>>>>>>>>>>  Algorithme GA <<<<<<<<<<<<<<|
+=========================================+
| INITIALISE t := 0                       |
+=========================================+
| INITIALISE P(t)                         |
+=========================================+
| évalue FORMEPHYSIQUE de P(t)            |
+=========================================+
| tant que pas ARRET CRITERE faire        |
|   +-------------------------------------+
|   | P'(t)  := RECOMBINAISON{P(t)}       |
|   +-------------------------------------+
|   | P''(t) := MUTATION{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := SELECTION{P''(t) + P(t)}  |
|   +-------------------------------------+
|   | évalue FORMEPHYSIQUE de P''(t)      |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+
</literallayout>
   </figure>
  </sect1>

  <sect1 id="geqo-pg-intro">
   <title>Optimisation génétique des requêtes (<acronym>GEQO</acronym>) avec
     PostgreSQL</title>

   <para>
    Le module <acronym>GEQO</acronym> est la solution du problème
    d'optimisation des requêtes, une solution similaire au problème du voyageur
    de commerce (<acronym>TSP</acronym>). Les plans de requêtes possibles sont
    codés comme des chaînes d'entiers. Chaque chaîne représente l'ordre de
    jointure d'une relation de la requête à une autre. Par exemple, l'arbre de
    requêtes
<literallayout class="monospaced">
   /\
  /\ 2
 /\ 3
4  1
</literallayout>
    est codé avec la chaîne d'entiers '4-1-3-2', ce qui signifie&nbsp;:
    première jointure entre les relations '4' et '1', puis '3' et enfin
    '2', avec 1, 2, 3, 4 les identifiants des relations pour l'optimiseur de
    <productname>PostgreSQL</productname>.
   </para>

   <para>
    Des parties du module <acronym>GEQO</acronym> sont adaptées de l'algorithme
    Genitor de D. Whitley.
   </para>

   <para>
    Les caractéristiques spécifiques de l'implémentation de
    <acronym>GEQO</acronym> dans <productname>PostgreSQL</productname>
    sont&nbsp;:

    <itemizedlist spacing="compact" mark="bullet">
     <listitem>
      <para>
       Utilisation d'un <firstterm>état d'équilibre</firstterm> du
       <acronym>GA</acronym> (remplacement des individus les moins performants
       d'une population, pas un remplacement d'une génération complète) qui
       permet une convergence rapide vers les plans de requêtes améliorés. C'est
       essentiel pour une gestion des requêtes sur un temps raisonnable&nbsp;;
      </para>
     </listitem>

     <listitem>
      <para>
       Utilisation d'un <firstterm>croisement de recombinaison de
       bord</firstterm> qui convient tout spécialement pour garder bas le
       nombre de pertes aux bords pour la solution du <acronym>TSP</acronym> en
       utilisant un <acronym>GA</acronym>;
      </para>
     </listitem>

     <listitem>
      <para>
       La mutation comme opérateur génétique est obsolète d'une telle façon
       qu'aucun mécanisme de réparation n'est nécessaire pour générer des tours
       <acronym>TSP</acronym> légaux.
      </para>
     </listitem>
    </itemizedlist>
   </para>

   <para>
    Le module <acronym>GEQO</acronym> permet à l'optimiseur de requêtes de
    <productname>PostgreSQL</productname> de supporter les requêtes disposant
    de jointures importantes de manière efficace via une recherche non
    exhaustive.
   </para>

  <sect2 id="geqo-future">
   <title>Tâches pour la future implémentation de <acronym>GEQO</acronym> pour
    <productname>PostgreSQL</></title>

     <para>
      Un gros travail est toujours nécessaire pour améliorer les paramètres de
      l'algorithme génétique.
      Dans le fichier <filename>backend/optimizer/geqo/geqo_params.c</filename>,
      pour les routines <function>gimme_pool_size</function> et
      <function>gimme_number_generations</function>, nous devons trouver un
      compromis dans les paramètres pour satisfaire deux demandes
      concurrentes&nbsp;:
      <itemizedlist spacing="compact">
       <listitem>
        <para>
         Plan de requête optimum
        </para>
       </listitem>
       <listitem>
        <para>
         Temps de calcul
        </para>
       </listitem>
      </itemizedlist>
     </para>

   </sect2>
  </sect1>

 <sect1 id="geqo-biblio">
  <title>Lectures supplémentaires</title>

  <para>
   Les ressources suivantes contiennent des informations supplémentaires sur
   les algorithmes génétiques&nbsp;:

   <itemizedlist>
    <listitem>
     <para>
      <ulink url="http://surf.de.uu.net/encore/www/">The Hitch-Hiker's
      Guide to Evolutionary Computation</ulink> (FAQ de <ulink
      url="news://comp.ai.genetic">comp.ai.genetic</ulink>)
     </para>
    </listitem>
   
    <listitem>
     <para>
      <ulink url="http://www.red3d.com/cwr/evolve.html">Evolutionary
       Computation and its application to art and design</ulink> par
      Craig Reynolds
     </para>
    </listitem>

    <listitem>
     <para>
      <xref linkend="ELMA99">
     </para>
    </listitem>

    <listitem>
     <para>
      <xref linkend="FONG">
     </para>
    </listitem>
   </itemizedlist>
  </para>

 </sect1>
</chapter>

<!-- Keep this comment at the end of the file
Local variables:
mode:sgml
sgml-omittag:nil
sgml-shorttag:t
sgml-minimize-attributes:nil
sgml-always-quote-attributes:t
sgml-indent-step:1
sgml-indent-data:t
sgml-parent-document:nil
sgml-default-dtd-file:"./reference.ced"
sgml-exposed-tags:nil
sgml-local-catalogs:("/usr/lib/sgml/catalog")
sgml-local-ecat-files:nil
End:
-->