FR 2701322 A1 19940812 FR 9301320 A 19930205 PROCEDE D'EXECUTION PARALLELE DE REQUETE DE BASES DE DONNEES RELATIONNELLES ET UTILISATION DU PROCEDE. La présente invention concerne un procédé d'exécution parallèle de requête de bases de données relationnelles dans un environnement à multi processeurs à mémoire distribuée et l'utilisation d'un tel procédé. S'il a été envisagé de traiter des requêtes de bases de données relationnelles de façon parallèle pour augmenter soit le nombre de transaction qu'il est possible de traiter par seconde, soit réduire le temps de réponse des requêtes complexes, une telle possibilité soulève des problèmes liés au contrôle nécessaire à la synchronisation des différentes parties de la requête et à la répartition du travail entre les différents processeurs d'une machine multi processeurs parallèles à mémoire distribuée. Un premier but de l'invention est donc de résoudre les problèmes soulevés cidessus. Ce but est atteint par le fait que le procédé d'exécution parallèle de requête de bases de données relationnelles dans un environnement multi processeurs parallèle à mémoire distribuée consiste à intégrer le contrôle dans la requête lors de sa compilation, le contrôle étant obtenu en combinant un jeu d'opérations atomiques de contrôle pour matérialiser un graphe de contrôle qui se superpose au graphe de la requête, ce graphe exprimant les dépendances entre les données par les liens entre les noeuds d'opérations et les types de dépendance de séquencement par des noeuds constructeur de deux types. Selon une autre particularité, le graphe de contrôle exprime le groupement des noeuds en foyer (home) d'une relation de la base, la colocalisation de plusieurs opérations sur un même foyer de l'architecture multiprocesseur, la réunion de plusieurs opérations en opération locale et la réunion de plusieurs opérations locales en association. Selon une autre particularité, le premier type de noeud constructeur (PIPE) permet l'exécution d'une opération suivante dès que l'opération précédente a produit un tuple. Selon une autre particularité, le deuxième type de noeud constructeur (SEQ) ne permet l'exécution de l'opération suivante qu'après l'achèvement complet de l'opération précédente. Selon une autre particularité, la synchronisation entre des opérations exécutées sur des groupes de noeuds différents et des opérations exécutées sur un même groupe est effectuée par deux familles de primitives de contrôle permettant la mise en place d'un mécanisme de contrôle. Selon une autre particularité, la première famille est constituée de primitives de propagation (stp, gp, mp, sp), l'autre famille de primitives d'attente (1w, gw, mw, sw), le mécanisme de contrôle ne pouvant être constitué que par la connexion de deux primitives de type opposé (attente,propagation). Selon une autre particularité, les primitives d'attente envoient à l'opération de contrôle suivante qui est une primitive de propagation, un message d'activation lorsqu'au moins un message de type fin de flot (EOS) est reçu. Selon une autre particularité, une primitive d'attente multiple vérifie que le nombre de message fin de flot reçu est égal au nombre d'opération locale exécutées par un même noeud et produisant le message fin de flot. Selon une autre particularité, une primitive d'attente globale vérifie que le nombre de message de fin de flot reçu est égal au nombre de noeud du foyer (home) sur lequel une ou plusieurs opérations s'exécutent en parallèle. Selon une autre particularité, les primitives de propagation envoient un message de fin de flot à au moins une instance de l'opération de contrôle suivante lorsque le message d'activation est reçu. Selon une autre particularité, une primitive de propagation multiple envoie autant de message de fin de flot que d'opération locale suivante. Selon une autre particularité, une primitive de propagation globale envoie autant de message de fin de flot qu'il y a de noeuds de le foyer (home) sur lequel s'exécute la ou les opérations locales suivante(s). Selon une autre particularité, une primitive de propagation et de déclenchement envoie en outre un message de déclenchement à l'opération locale suivante, pour déclencher celle-ci. Selon une autre particularité, des tables de portion de programme constituées à partir des primitives permettent de reconstituer par l'association successives de plusieurs tables le graphe correspondant à l'exécution parallèle d'une requête sur une base de données relationnelle dans un environnement multi processeurs à mémoire distribuée. Un autre but de l'invention est de proposer une utilisation du procédé selon l'invention. Ce but est atteint par le fait que l'utilisation du procédé est effectué dans la phase de parallèlisation d'un gestionnaire de requêtes chargé de compiler les requêtes exprimées en langage E.S.Q.L. en exécutant une phase d'analyse, une phase d'optimisation physique une phase de parallèlisation et une phase de génération de code en langage C+ +. D'autres caractéristiques et avantages de la présente invention apparaitront plus clairement à la lecture de la description ci-après faite en référence aux dessins annexés dans lesquels La figure 1 représente un graphe représentant une requête sur une base de données associé au graphe de contrôle, La figure 2A représente la répartition d'une requête sur les noeuds d'un système multi processeurs parallèle, La figure 2B représente un système multi processeurs parallèle à mémoire distribuée, La figure 2C représente de façon schématique sous-forme de graphe les différentes possibilités de liaison entre les noeuds d'opérations et les noeuds constructeurs, La figure 2D représente la matérialisation des graphes de la requête représentée à la figure 2C sous forme d'un graphe de contrôle représentant la séquence des primitives de contrôle, La figure 3 représente de façon schématique une opération locale et l'allocation des processus à cette opération, La figure 4 représente une requête contenant deux opérations locales regroupées dans deux associations, Les figures 5 à 13 représentent les différentes possibilités de graphes de requêtes associant les différentes combinaisons entre les noeuds d'opérations et les noeuds constructeurs, et la traduction sous forme de graphe de contrôle est formée d'une séquence de primitives de contrôle correspondant au graphe de requête. La figure 14 représente le schéma de principe d'un gestionnaire de requête dans lequel le procédé de parallèlisation est utilisé. L'invention qui concerne un procédé d'exécution parallèle de requête de bases de données dans un environnement multi processeurs à mémoire distribuée tel que celui représenté à la figure 2B. Dans un tel environnement, chaque processeur 31, 3i, 3n est associé à une mémoire distribuée 11, 1i, 1n et les processeurs communiquent entre eux par des noeuds 41, 4i, 4n. Un système de gestion de base de données relationnelle étendue développé sur une telle machine à processeurs parallèles permet de tirer profit du parallélisme pour à la fois augmenter le nombre de transactions qu'il est possible de traiter par seconde et réduire le temps de réponse des requêtes complexes. Un exemple de base de données relationnelles est représenté à l'annexe 1. Cette base comprend trois relations, une première "voiture" comportant les attributs suivants : numéro du véhicule (nO véh.), marque, type distribué par hachage sur l'attribut (nO véh.). Une deuxième relation "achète" comprend les attributs d'identification de la personne (nO de sécurité sociale), identification de l'auto (nO véh.) et la date (date). La relation achète est distribuée par hachage sur l'attribut n0 de véh. en association avec la relation voiture. Une troisième relation "contrôle" comporte les attributs identifieur d'auto (n véh.), identifieur d'organisation (nO d'organisme), et la date (date). Cette relation est distribuée par hachage sur l'attribut d'identification de l'organisme. Chaque processeur (3i) a donc sa propre mémoire locale (li) et est le seul à accéder aux données dans la mémoire. Les processeurs communiquent par envoi de messages à travers les- noeuds (4i). Le stockage des données constituées par les attributs de la base est réparti sur l'ensemble des noeuds de la machine. Ainsi, chaque relation de la base est partitionnée en paquet, chaque paquet étant placé sur un noeud de la machine. Pour une relation donnée, par exemple voiture, un sous-ensemble des noeuds de la machine est utilisé pour le stockage de la relation. Ainsi la relation voiture sera par exemple stockée sur les trois premiers noeuds, 41, 42, 43 de la machine associée aux mémoires Ml, M2, M3. Ce sous-ensemble de noeuds de la machine est appelé le "home" (foyer) de la relation. De même comme représenté à la figure 2A, une relation R est stockée sur un ensemble de noeuds Ni à Nn. Sur cette relation et par les processus associés au "home" de la relation on effectue une opération "select" de sélection qui est utilisée comme résultat dans une opération de jointure "join" avec une relation S stockée sur un ensemble Ni à Ni + n de noeuds constituant le "home" (foyer) de la relation S. La méthode la plus simple d'allocation de processus pour obtenir l'exécution parallèle de la requête consiste à attribuer à chaque noeud, opération du graphe de la requête, un ensemble de processus chargé de l'exécuter. Le nombre de processus utilisé pour le traitement d'une opération sur une relation dépendra en fait du nombre de noeuds utilisé pour le stockage de la relation, c'est-à-dire de la taille du "home" de la relation. Le modèle d'exécution parallèle de l'invention supporte trois types de parallélisme. Le premier est le parallélisme intra-opération qui repose sur le partitionnement horizontal d'une relation en plusieurs paquets. Ceci permet d'effectuer un traitement (par ex. opération "select") sur une relation (R) par plusieurs processus qui s'exécutent en parallèle chacun sur un paquet (Sel 1, Seli, Selm). Le modèle d'exécution parallèle de l'invention supporte deux autres types de parallélisme, le parallélisme inter-opération et le pipeline. Le parallélisme interopération peut être mis en oeuvre lorsque deux ou plusieurs opérations sont indépendantes en terme de partage de données intermédiaires par exemple les opérations "select" de sélection sur le "home" CONTROLE et sur le "home" (ACHETE) figure 1. Le pipeline (figure 3) est une forme de parallélisme à grain fin où deux opérations par exemple "Select" et "store" figure 3 échangent des données intermédiaires en mode producteurconsommateur. Lorsque l'on formule une requête en langage SQL qui consiste par exemple à rechercher les automobiles Renault qui ont été achetées et non contrôlées depuis le ler Janvier 1986, une telle requête s'exprime en langage SQL comme représenté à la figure 2D. Un plan possible d'exécution d'une telle requête peut être généré par un programme optimiseur physique et correspondre au plan représenté à l'annexe 2. Ceci conduit à un programme représenté à l'annexe 3 et correspondant à la requête qui est représentée par un graphe à la figure 1 sur lequel la séquence du programme est représentée. Ce graphe de la figure 1 comporte dans les zones grisées en sombre, la représentation des opérations locales et dans les boites en gris plus clair, les constructions d'association. Les constructions d'opérations locales isolent une entité d'exécution dans le programme par exemple le processeur Pj sur lequel s'exécute la sélection Selj du noeud Nj comme représenté à la figure 3. Cette construction regroupe les opérations de données qui communiquent localement avec chaque noeud d'un "home" donné, par exemple en échangeant des données intermédiaires dans un mode pipeline local que l'on nomme, pipeline local interne (internal local pipeline). Les opérations de données qui font partie de l'opération locale représentent un sous-graphe qui a une racine simple, (soit à flux de données ou à messages d'activation) et une ou plusieurs feuilles (opération de communication de données : envoi, envoi local ou stockage). A chaque message reçu, toutes les opérations de données dans l'opération locale sont exécutées de façon synchrone. Une association (Al, A2, figure 4) isole dans le graphe du plan d'exécution parallèle un composant qui est un sous-graphe de données et d'opérations de commandes localisées sur un "home". Ce composant A1 est composé d'opérations locales (Select, diff, transmit) et d'opérations de commandes associées qui communiquent localement sur chaque noeud du "home". Chaque élément d'une association est distribué sur tous les noeuds du "home" où l'association est située: Deux opérations locales situées dans la même association échangent des données dans un ou deux modes : le premier mode est un mode local pipeline (13, 16) appelé pipeline local externe (external local pipeline) et le second mode est à travers une relation intermédiaire stockée (SI). Dans une variante de l'invention, il est possible que l'opération soit exécutée sur un "home" appelé flottant où les noeuds faisant partie du "home" sont choisis au moment de l'exécution de la requête en fonction de critère tel que la charge des processeurs à cet instant et non en fonction de la localisation des données. Dans ce cas, les données utilisées par l'opération sont transférées vers ce "home" flottant. La figure 2A illustre l'allocation de processus pour une requête comportant une sélection et une jointure. La sélection s'effectue sur le "home" de R, c'est-à-dire qu'un processus sur chaque noeud du "home" exécute la sélection sur un paquet de R et la jointure s'exécute sur le "home" de S, les résultats de la sélection étant envoyés sur le "home" de S. Il existe donc autant de processus exécutant la sélection que de noeuds "m" stockant la relation R et autant de processus exécutant la jointure que de noeuds stockant la relation S. Les processus correspondant à deux opérations distantes c'est-à-dire localisées sur des "homes" différents de la machine, telles que les opérations de sélection et de jointure de la figure 2A ont besoin d'échanger des données intermédiaires.Cette fonctionnalité est assurée par des opérations de communication qui permettent notamment de redistribuer les données d'un "home" vers un autre. Les envois de données s'effectuent toujours en pipeline, c'est-à-dire que les tuples sont envoyés à l'opération destinataire au fur et à mesure de leur production. Dans le modèle d'exécution, les données intermédiaires peuvent être soient consommées en pipeline (ex : 11, 12, 13, 16 figure 1) au fur et à mesure de leur arrivée sur le "home" de l'opération destinataire, soient stockées dans des relations intermédiaires (S1, S2, figure 1) dans le "home" de l'opération qui utilise la relation matérialisée. Dans ce cas, l'opération destinataire du pipeline est une opération "store" (loc op3, loc op4, figure 1) qui matérialise la relation intermédiaire. L'arrivée de données destinées à une opération provoque l'activation du processus qui est chargé d'exécuter cette opération. Les processus producteur et consommateur sont donc actifs simultanément et ne nécessitent pas de synchronisation. Lorsque deux ou plusieurs opérations (Select, diff, figure 4) de la requête sont localisées sur le même "home" (ACHETE, VOITURE), exemple les noeuds i, a, n, M de la relation voiture (figure 4) et échangent localement sur ce "home" des données intermédiaires en pipeline 13, 16, l'exécution de ces opérations peut être effectuée par un processus unique sur chaque noeud du "home". C'est le cas des opérations "Select" et "Diff" sur les noeuds i, a, m qui sont effectuées par les processus Pi à Pm. Dans ce cas, le processus exécute successivement par appel de procédures, toutes les opérations pour un tuple en entrée de la première opération, avant que le tuple suivant ne soit traité. Ce mode d'exécution des opérations est appelé "Pipeline local interne". Le sous-graphe d'opération est appelé "Opération localisée" ou "local op" . Un tel sous-graphe représenté à la figure 4 constitue l'entité minimale de synchronisation. Les résultats intermédiaires produits sur un noeud par l'opération de sélection sont donc les seuls qui peuvent joindre avec les tuples provenant de la relation Si présents sur le même noeud. Les deux opérations "select" et "Diff" appartiennent à la même opération locale "local op1" et sont donc exécutées par un seul processus pour chaque noeud. Par ailleurs, deux opérations locales ("localppl", "local~op2") peuvent échanger localement des données intermédiaires comme représentées à la figure 4. La localité des échanges est délimitée par un constructeur association qui permet d'isoler dans le graphe de la requête un ensemble d'opérations qui échangent localement des données. Ainsi les opérations "locppl", "loc~op2"et "loc~op4" (figure 1) échangent des données, et sont regroupées dans l'association A3. Les opérations locales peuvent échanger les données soit en pipeline (pipeline locale asynchrone) (ex "loc~op1" avec "locpp2, fig 1), soit à travers une relation intermédiaire ("loc~op 4" avec "loc pp2 à travers S2).Les processus alloués aux deux opérations "loc op1" "loc#op2" sont différents et les communications entre ces processus sont explicites. Des mécanismes de synchronisation local sont alors nécessaires entre ces processus. En outre des opérations de communication permettent de redistribuer les données d'un "home" vers un autre ou d'envoyer les résultats d'une association sur une autre local~op d'une autre association. Seules des opérations racine et feuille d'un sous-graphe peuvent communiquer avec des processus éloignés. Un exemple d'utilisation d'opération de communication "transmit, local~transmit, and, store" est donné ci-après pour une opération de communication qui transmet le résultat Il d'une opération précédente au noeud du "home" S par adressage calculé (hachage) "hash" sur le second attribut de Il. L'opération d'envoi est distribuée sur le "home" de R comme l'opération qui produit Il. Il = {home(R)} 12 = {home(R)} tansmit (Il, home(S), hash on 11.2) La requête de la figure 4 qui se traduit par le programme ci-après donne également un exemple d'utilisation de l'opération local~transmit thome(achète, voiture)}, Assoc A3 (loc~op1) 13 = Select (voiture, voiture.marque= "Renault", (voiture n0 véh.)) 16 = Difference (13, S1)Join thome(S)} (12, H on ..) 17 = local transmit (16) End~loc opi loc~op 2 Result= join (S2, 17, 17.nOvéh.=S2, novéh. (17.n véh)) End loc op 2 End assoc A3 Par ailleurs, la synchronisation des instances parallèles d'une même opération telles que par exemple les instances parallèles des différentes opération locales "loc~op1 (fig. 1) sur chaque noeud du "home" (voiture) ainsi que plus globalement la synchronisation des opérations d'une requête requièrent des mécanismes de contrôle. En effet, le déclenchement d'une opération est obtenu par le déclenchement de tous les processus associés à son exécution et sa terminaison est équivalente à la terminaison de tous ces processus. De plus, lorsqu'une opération consomme des données en pipeline, son déclenchement est lié à l'arrivée de tuple sur le pipeline et sa terminaison est liée à la fin des données pipelinée. Or, la fin des données pipelinées dépend elle-même de la fin de l'opération qui les produit.Les mécanismes de contrôle assurent toutes ces fonctionnalités par l'intermédiaire d'opérations de contrôle qui échangent des messages de contrôle. Certains de ces opérateurs de contrôle sont centralisés alors que d'autre sont distribués. Il existe trois classes d'opérations correspondant à trois types de parallélisme intra-requête supportés à savoir les opérations de contrôle liées au parallélisme intra-opération, celles liées au parallélisme inter-opération et celles liées au pipeline. La mise en oeuvre d'une requête se traduit par un programme qui lui-même peut être représenté par une structure de graphe de séquencement. Un tel graphe est représenté à la figure 2C et comporte deux types de noeuds, des noeuds d'opération mentionnée opl, op2, op3, op4, op5, op6 et des noeuds constructeur qui comportent une étiquette (START, END, LPIPE, PIPE, SEQ, LSEQ) qui correspond au type de dépendance de séquencement que le noeud constructeur représente. Un noeud constructeur tel que LPIPE ou PIPE à n entrées et p sorties qui sont des noeuds d'opération. Chacune des entrées d'opérations s'exécute avec la dépendance de séquencement spécifiée par le constructeur. Il est très important de noter qu'une opération de données ne peut jamais être la sortie d'un constructeur séquentiel tel que SEQ, LSEQ et d'un constructeur pipeline tel que PIPE, LPIPE. Nous avons indiqué précédemment comment chaque opération est divisée en sous-opérations localisées. Toutes ces sous-opérations nécessitent d'être synchronisées et commandées pour garantir une exécution globale correcte. Chaque mode d'exécution décrit précédemment nécessite un mécanisme de commande différent. En particulier, pour garantir une exécution séquentielle entre deux opérations, il faut garantir que la seconde opération soit seulement initialisée après la fin de la première. Ceci implique la capacité de détecter l'achèvement de l'exécution d'une opération et la capacité de lancer une opération. Pour la détection de l'achèvement, sachant qu'une opération est distribuée dans un nombre de sous-opérations, chacune localisée sur un noeud, il faut détecter l'achèvement local de chaque sous-opération et l'achèvement global de l'opération. Pour le lancement, il faut être apte à lancer toutes les sous-opérations d'une opération.Ceci implique la capacité de notifier explicitement la fin d'un flot de données par un signal (EOS) (End of Stream) à chaque sous-opération, la réception de ce signal autorisant alors la détection de l'achèvement local de se produire. Pour permettre les opérations de détection d'achèvement d'opérations, de lancement d'opération et de synchronisation entre les opérations, on a été amené à créer des opérations atomiques de commandes qui sont divisées en deux groupes d'opérations, les opérations d'attente et les opérations de propagation. Rappelons qu'une opération ou un élément atomique ne peut pas être décomposé. C'est le plus petit composant. Les opérations d'attente attendent les messages (EOS) de fin de flot de données et ensuite activent un propagateur qui propage les messages de fin de flot de données (EOS) et parfois initialise des messages. Les opérations d'attente consomment toujours des messages de fin de flot de données et produisent des messages d'activation, tandis que les propagateurs consomment des messages d'activation et produisent des messages de fin de flot de données, parfois avec une activation. Les opérations d'attente sont Iw qui signifie attente locale, est une opération de commande distribuée associée à une opération distribuée. Chaque instance de l'attente locale exécute la détection de l'achèvement local de l'une des sous-opérations de l'opération. Elle attend un message de fin de flot (EOS) pour l'accomplissement de la sous-opération. C2:act = Iw(Cî :EOS,stream) équivaut à envoyer le message C2 d'activation (act) à l'opération de contrôle suivante lorsque le message Cl de type EOS est reçu, signifiant que l'opération produisant le flot (stream) est terminée. Sinon attendre la fin de l'opération produisant le flot (stream) pour envoyer C2. gw qui signifie attente globale, est une opération de commande centralisée qui attend l'achèvement global d'une opération donnée, c'est à dire l'achèvement de toutes les sous-opérations. Chaque achèvement local est notifié par un message de fin de flot (EOS) produit par un propagateur. C2:act = gw(Cî :EOS) équivaut à envoyer le message C2 d'activation (act) à l'opération de contrôle suivante si le nombre de messages C1 de type EOS reçus est égale au nombre de noeuds dans le home de l'opération de contrôle produisant les messages Cl. Le nombre de noeud du home est déterminé à l'initialisation du programme de traitement de la requête et mémorisé par un paramètre qui est le home de l'opération locale précédente. mw qui signifie attente multiple, est une opération de commande utilisée pour la synchronisation de la détection de l'achèvement. Elle attend n messages EOS, n étant le nombre d'opérations à synchroniser qui peuvent être soient centralisées, soient distribuées. C2:act = mw(Cî :EOS) équivaut à envoyer le message C2 d'activation (act) à l'opération de contrôle suivante si le nombre de messages Cl de type EOS est égal au nombre d'opérations de contrôle produisant le message Cl. N.B.: le nombre d'opérations de contrôle produisant Cl est > 1. sw qui signifie attente simple, attend un message de fin de flot (EOS). Cette opération est essentiellement utilisée pour la conversion d'un message de type EOS en un message d'activation. Elle peut être soit centralisée soit distribuée. C2:act = sw(C1:EOS) équivaut à envoyer le message C2 d'activation (act) à l'opération de contrôle suivante lorsque le message Cl de type EOS est reçu. Les opérations de propagation sont sp qui signifie propagation simple, est une opération de propagation d'un message de fin de flot EOS à une opération d'attente. C2:EOS =sp(Cl :act) équivaut à envoyer le message C2 de fin de flot à l'opération de contrôle suivant lorsque le message d'activation (act) est reçu. stp qui signifie simple activation et propagation, est opération de commande distribuée associée à une opération distribuée. Chaque instance de l'opération stp effectue l'activation locale d'une sous-opération de l'opération et propage un message de fin de flot EOS à son opération d'attente (Iw) associée. (D2:trigger,C2:EOS) = stp(CA:act) équivaut à envoyer le message D2 de déclenchement à la local op consommatrice du message D2 et le message C2 de fin de flot à l'opération de contrôle suivante lorsque le message Cl d'activation (act) est reçu. gp qui signifie opération de propagation globale, est une opération centralisée qui propage des messages de fin de flot EOS à une opération d'attente distribuée sur chaque noeud du home. C2:EOS = gp(C1:act) équivaut à envoyer le message C2 de fin de flot à toutes les instances de l'opération de contrôle suivante lorsque le message Cl d'activation (act) est reçu. Il y a autant de messages envoyés que de noeuds dans le home de l'opération locale suivante, le nombre de message étant mémorisé par un paramètre déterminé à l'initialisation du programme par le cardinal du home de l'opération locale suivante. mp qui signifie propagation multiple, est utilisée pour la propagation de messages de fin de flot EOS de synchronisation. Cette opération propage n messages EOS, n étant le nombre d'opération à synchroniser. Cette opération peut être soit centralisée, soit distribuée. C2:EOS mp(Cî:act) équivaut à envoyer le message C2 de fin de flot à toutes les opérations de contrôle suivantes lorsque le message Cl d'activation (act) est reçu. N.B.: le nombre d'opérations de contrôle consommant C2 est > 1. Nous allons maintenant examiner les différents schémas de commande d'opération ou de constructeur qui sont représentés aux figures 5 à 13. La figure SA représente un exemple de graphe d'opération rattaché à des noeuds constructeur associés qui correspond au schéma d'opération de commande représenté à la figure 5B. Dans la figure 5 une opération 1 reçoit des entrées en mode séquentiel (SEQ) ou séquentiel local (LSEQ) et émet des sorties en mode pipeline (PIPE) ou pipeline local (LPIPE). L'opération recevant deux entrées constructeur, le schéma de contrôle associé de la figure 5B utilise une opération SP par entrée constructeur, ce qui permet pour chaque entrée constructeur de propager un message EOS à une opération d'attente qui est constitué par l'opération (mw) dans le cas où l'opération a plus d'une entrée constructeur.Cette opération atomique de commande (mw) active ensuite soit une opération de propagation (stp) qui déclenche l'exécution de chaque instance dans les sous-opérations d'une opérations dans le cas où les entrées constructeur sont séquentielle, soit lance une simple propagation (sp) représentée en pointillé fig. 5B dans le cas où les entrées constructeur sont du type pipeline (PIPE, LPIPE) représentée en pointillé fig. 5A. L'une de ces deux commandes de propagation envoie le message EOS à une commande d'attente locale (local wait) (Iw) qui envoie un message d'activation à l'opération atomique suivante qui est une commande de propagation multiple (mp) dans le cas où l'opération opî a plus d'une sortie constructeur. Cette opération de propagation multiple (mp) est associée avec une commande d'attente (sw) pour chaque branche de sortie. Dans le cas où l'opération (ope) a une seule sortie, l'opération atomique (mp) est remplacée, comme représenté à la figure 5B en pointillé par une opération de propagation simple (sp) associée à une opération d'attente simple (sw). La figure 6A représente le schéma d'une opération constructeur de type pipeline local (LPIPE), ayant comme entrée une opération (opi) et deux opérations en sortie (op2, op3). La figure 6B représente le schéma d'opérations atomiques de commande générées par le graphes correspondant au schéma de la figure 6A. Ce schéma est également valable dans le cas d'un constructeur local du type séquentiel (LSEQ). La fin d'une opération opi génère comme on l'a vu pour la figure 5B une opération atomique (sw) qui active une opération atomique (mp) à propagation multiple pour propager deux messages EOS vers les opérations d'attente simple (sw) associées chacune avec le début des opérations respectives op2 et op3. La figure 7A représente un graphe de séquence d'opération débutant par un constructeur (START) qui lance trois opérations (opi, op2, op3) dont deux opl et op2 sont co-locales. On rappellera qu'un groupe d'opérations colocales désigne des opérations qui sont localisées sur le même "home" c'est à dire sur le même jeu de noeud (Ni à Nm). Ces opérations co-locales sont représentées sur la figure 7A par le fait qu'elles sont entourées d'un pointillé, et sont exécutées par le même processeur. Comme le constructeur start apparait au sommet d'un graphe de séquencement, ce constructeur n'a pas d'entrée d'opérations. C'est pourquoi aucune partie locale d'entrée apparait dans le schéma de contrôle. Les figures 7B et 7C représentent la traduction de ce graphe de séquencement en opérations atomiques. La figure 7B représente la partie globale du noeud constructeur, le rôle du message sw est de recevoir le message système début. L'opération de propagation multiple (mp) duplique si nécessaire ce message en autant de messages qu'il y a de groupes d'opérations co-locales. Dans le cadre de la figure 7A, il y a deux groupes d'opérations co-locales, l'opération op3 et le groupe des opérations opi, op2 qui sont des opérations associées. L'opération atomique (mp) est associée à autant d'opérations atomiques d'attente simple (sw), qu'il y a d'opérations co-locales. Puis une opération de propagation globale par groupe (gp) est utilisée pour distribuer les informations de commande à tous les noeuds d'un "home" du groupe. Ainsi une première opération atomique (gp) distribue l'information de commande au noeud N1, Nm du "home" des opérations opl et op2, alors que l'autre opération atomique (gp) distribue l'information de commande au noeud Ni, Nn du "home" de l'opération op3. La figure 7C représente la partie locale des sorties sur les noeuds d'opérations co-locales (ope, op2). Une opération (sw) rassemble simplement localement sur chaque noeud N1, Nm du "home" du groupe concerné par les opérations, les informations de commande envoyées par la partie globale de l'opération (gp). Cette information de commande est dupliquée par la propagation multiple mp pour toutes les opérations du groupe. Chaque opération de propagation (mp) associée à un noeud (N1, Nm) génère deux opérations d'attente simple (sw) sur chaque noeud pour les deux opérations opi et op2. Les figures 8 à 12 représentent le schéma de commande correspondant à deux constructeur globaux, l'un (SEQ) sur la figure 12, l'autre (PIPE) sur la figure 8 pipe. La seule différence entre le constructeur SEQ et le constructeur PIPE est que le constructeur SEQ implique que les opérations de sortie doivent être activées, mais cette fonctionnalité apparait au niveau du schéma de commande d'opération. Ici le schéma de commande est composé de trois parties : la partie entrée locale, la partie globale et la partie sortie locale. La partie entrée locale de la figure 8 comporte deux opérations co-locales (ope, op2) car entourées d'un pointillé. La partie entrée locale illustrée à la figure 9A comprend une opération de simple propagation (sp) (single propagate) pour chaque opération (ope, op2) d'un groupe. Cette opération de propagation (sp) est suivie d'une opération mw (multiple wait) dans le cas où les entrées du groupe d'opérations colocalisées a plus d'une opération, ce qui est représentée à la figure iOA où les opérations opl et op2 sont co-localisées ou autrement dit associées et donc chaque (sp) provenant d'une opération est attendu par l'opération (mw). Cette opération est suivie d'une propagation simple (sp) vers la partie globale représentée à la figure 1 OA. Dans le cas où l'opération est répartie sur plusieurs noeuds comme représentée à la figure 9B, chaque noeud génère après l'exécution de l'opération, par exemple l'opération op3 de la figure 9B ou l'opération opî de la figure 9C une opération atomique de simple propagation (sp) (single propagate). La partie globale est représentée pour une opération PIPE à la figure 10A et pour une opération SEQ à la figure 10B. Cette partie globale comporte un rassemblement global effectué par deux opérations de rassemblement (gw) dans le cas de la figure 10A qui permettant d'attendre les signaux EOS de la fin des opérations co-localisées opl, op2 ou des opérations op3 réparties sur plusieurs noeuds. Dans le cas où plusieurs opérations de rassemblement global sont utilisées, chaque opération d'attente globale (gw) est suivie d'une opération sp (single propagate) qui se regroupent sur une opération d'attente multiple (mw) (multiple wait) dans le cas où il y a plus d'un groupe d'entrée pour les opérations co-localisées. L'opération (mw) est suivie par une opération gp de propagation globale associée à chaque groupe d'opérations co-localisées. La figure 10B représente le cas d'une partie globale ayant plusieurs graphes d'opérations en sortie, et une opération en entrée . Dans ce cas le schéma débute par une opération de rassemblement global (gw) à laquelle succède une opération de propagation multiple (mp) qui permet d'initialiser plusieurs opérations d'attente simple (sw), par groupe d'opérations de sortie. Chaque attente simple (sw) est suivie d'une opération de propagation globale (gp) par groupe d'opérations co-localisées qui permet d'initialiser les opérations de chaque groupe. La partie locale de sortie du schéma de contrôle est représentée à la figure il 8 pour plusieurs groupes d'opération en sorties. Ce schéma comporte à la suite de l'opération de propagation global (gp), une opération de rassemblement simple (sw), suivie d'une opération de propagation multiple (mp) qui permet d'initialiser une opération d'attente simple (sw) par opération du groupe d'opérations co-localisées. Pour les autres opérations (op2, figure 1 1 C, ou op4, figure il A) la partie locale de sortie est constituée par une opération atomique de simple attente (sw). Le dernier élément est constitué par l'élément constructeur FIN dont le schéma est représentée fig. 13A et les commandes correspondantes représentées fig. 13B comportent une opération de rassemblement global (gw) par groupe d'entrée d'opérations co-localisées. Chaque opération (gw) active une opération de rassemblement multiple (mw) qui commence par une opération de simple propagation (sp) associée à chaque (gw). Les différentes opérations (sp) activent une opération d'attente multiple (mw) qui elle-même active l'opération de propagation simple (sp) lancant l'opération de fin de traitement par le message de fin de flot (EOS).Ainsi, grâce aux schémas de commande correspondants aux différentes figures 5 à 13 et aux tables d'opération de commande correspondant aux commandes associées à ces graphes, on arrive dans le cas d'un graphe de séquencement tel que celui représenté à la figure 2C, à traduire ce graphe de séquencement en une succession d'opérations de commandes qui sont représentée à la figure 2D et qui consistent en un regroupement des différentes opérations de commandes élémentaires que nous avons vu précédemment. Le noeud de début, qui est le premier noeud du programme est le premier noeud à être traité. Ce traitement utilise la table qui stocke le schéma global des constructeurs globaux et génère une opération (sw) pour l'entrée du constructeur et ensuite une opération (mp), étant donné que le constructeur a deux opérations de sortie qui ne seront pas co-localisées, ensuite, une opération (sw) suivie par une opération (gp) sont produites pour chaque opération de sortie et associée avec l'opération (mp). Toutes les opérations de commandes produites à ce moment sont globales, la table correspondant au schéma local de sortie des constructeurs globaux appliqués à la sortie du constructeur START indique alors qu'une opération (sw) pour chaque opération co-localisée avec cette opération est produite et associée à l'opération (gp) correspondante.Le noeud suivant à être traiter est le noeud de l'opération opl. Pour cette opération qui a une entrée constructeur START et sortie constructeur LPIPE, une opération (stp) est alors générée lorsque l'on traite le début de l'opération (opl) Cette opération (stp) est associée à l'opération (sw) générée précédemment. Le traitement de la sortie de l'opération (ope) produit une opération (Iw). Toutes les opérations générées sont co-locales avec l'opération opi. Le contexte de l'opération op2 étant exactement le même que l'opération opl, avec simplement le remplacement d'un constructeur PIPE par un constructeur LPIPE, les opérations de commandes générées sont identiques. Le noeud constructeur LPIPE ayant une entrée et une opération de sortie. Ainsi, aucune opération de commande n'est à ajouter car les seules commandes nécessitées par les constructeurs locaux concernent la synchronisation. Le traitement du noeud PIPE qui a aussi une entrée et une opération de sortie génère une opération (sp) suivie par deux opérations globales (gw) et (gp) qui assurent respectivement la détection de l'achèvement global de l'opération op2 sur les différents noeuds (N1 à Nn) et la propagation globale à l'opération op3 sur les noeuds (N1 à Nm). Une opération (sw) co-locale avec l'opération op3 est alors générée lors du traitement de sortie du constructeur PIPE. L'opération suivante est l'opération op3 qui a deux constructeurs pipeline en entrée et une sortie constructeur séquentielle (SEQ). Les informations EOS issues des deux constructeurs pipeline ont besoin d'être synchronisées. Cette synchronisation est assurée par les deux opérations (sp), une pour chaque constructeur suivie par une opération (mw) et une opération (sp) introduite pendant le traitement de la partie globale utilisant la table globale. Pour la sortie du traitement de l'opération op3, une opération (Iw) est générée. Finalement, on notera que toutes les opérations de commandes introduites dans cette phase sont co-locales avec l'opération op3 et donc distribuées sur la même association. Le constructeur SEQ a une entrée et deux opérations (op4, op5) de sortie co-locales. Ceci signifie qu'une propagation multiple se produira. Pour l'entrée, une opération (sp) est introduite pour propager l'achèvement local de l'opération op3. Les opérations globales correspondant au constructeur SEQ sont introduites en utilisant la table globale. Ces opérations sont respectivement une opération (gw) qui détecte l'achèvement de l'opération op3 suivie par une opération globale (gp) (les opérations de sortie de SEQ appartiennent au même groupe d'opérations co-locales).Le traitement des sorties du constructeur génère alors les opérations de commandes distribuées relatives aux opérations de sortie du constructeur et co-locales avec ces opérations. Elles consistent en des opérations (sw) et (mp) suivies par une opération (sw) pour chacune des opérations op4 et op5. Le traitement des opérations op4 et op5 génère les mêmes opérations de commandes, sachant que chacune de ces opérations a une entrée constructeur SEQ et une sortie constructeur LSEQ. Ces opérations de commandes co-locales avec les opérations op4 et op5 sont une première opération (stp) et ensuite une opération (Iw) pour chacune des opérations op4 et op5. Le constructeur LSEQ a deux opérations d'entrée et une opération de sortie. Les deux opérations d'entrée doivent être synchronisées chacune par une opération (sp) et une opération (mu). Aucune commande pour la sortie est nécessaire. L'opération op6 est prévue en entrée avec un constructeur LSEQ et en sortie avec un constructeur FIN. Le traitement de l'entrée de ce noeud introduit une opération (stp) et la sortie une opération (il). Finalement le constructeur FIN avec l'aide des tables d'entrée et du constructeur global achève le graphe de commande avec une opération distribuée (sp) relative à l'opération op6 et les opérations centralisées (gw) et (sp). Ce procédé d'exécution parallèle de requête de base permet aisément à l'aide d'un graphe de séquencement et de tables traduisant à chacun des noeuds constructeur ou des noeuds d'opération de transformer ce graphe de séquencement en séquence d'instruction permettant l'exécution d'une requête sur des processus parallèles. Ainsi on a vu comment à partir d'une requête représentée par un graphe transformer cette requête en une succession d'opérations de commande atomique permettant l'exécution parallèle de cette requête dans un environnement multi processeurs à l'aide d'un langage parallèle-lera (langage for extended relational algebra). Ce procédé sera utilisé dans un gestionnaire de requêtes qui compile les requêtes formulées en langage ESQL (Extended queries langage) en une version de code généré de langage parallèle LERA. Cette compilation s'effectue en plusieurs phases successives comme représentées à la figure 14 qui sont respectivement l'analyse, l'optimisation, la parallèlisation et la génération du code. Les résultats de ces transformations diverses effectués par ces étapes de compilation sont toutes exprimées dans différentes variantes du même langage intermédiaire (LERA). L'analyse de la requête ESQL génère un programme LERA-SEM (SEM pour sémantique) qui est ensuite optimiser par un optimiseur physique en un programme LERA-PHY (PHY pour physique). Le résultat de l'optimisation est un plan d'exécution de la requête qui minimise une fonction coût exprimée en terme des caractéristiques d'environnement de l'exécution parallèle. Le plan d'exécution décrit en LERA consiste en de simples opérations atomiques pour lesquelles les opérations de localisation et les algorithmes globaux et locaux utilisés sont exprimés par des annotations. Ceci est formulé sous forme de graphes. L'étape de parallèlisation ensuite compile le plan d'exécution de façon à générer un programme d'exécution parallèle où les communications de données et les processus de commande nécessaires pour le séquencement du programme sont explicités.Une phase de génération de code transforme ensuite le programme LERA-PAR en code C + + qui est compilé par un compilateur standard C+ +. Les modules résultant sont soit stockés dans un catalogue pour exécution ultérieure, soit directement exécutés par le gestionnaire de données. Ainsi, si l'on reprend l'exemple de la requête figurant à l'annexe 1, qui peut générer par l'optimiseur physique un plan d'exécution correspondant à l'annexe 2, ce plan d'exécution s'exprimera sous la forme d'un graphe représenté à la figure 1 dans lequel les associations et les opérations locales sont représentées ainsi que les pipelines globaux et les algorithmes locaux correspondant à la requête. A ce graphe les tables qui correspondent à chacun des graphes élémentaires représentés aux figures SA à 13 et traduisant ces graphes sous forme de séquence d'opérations atomiques de communication et de commande vont permettre la traduction du graphe en différentes séquences d'opérations atomiques qui seront chacune adressée au processeur des noeuds correspondant au traitement à effectuer.Ceci permet de générer la succession d'opérations atomiques figurant en annexe 3. Le programme qui incorpore à la fois les opérations correspondant à l'exécution de la requête et les opérations atomiques de contrôle qui permettent une exécution parallèle de cette requête avec le séquencement souhaité. D'autres modifications à la portée de l'homme de métier font également partie de l'esprit de l'invention. ANNEXE 1 SELECT ACHETE.n veh FROM ACHETE, VOITURE WHERE ACHETE.date > '010186' and ACHETE.n veh = VOITURE.n veh and VOlTURE.marque = "Renault" and VOlTURE.n veh not in select C.n)veh from CONTROLE C where C.date > '010186' ANNEXE 2 Selectionner les véhicules contrôlés depuis Je 01/01/86 Il = select #home(CONTROLE), allselect, scanselect} (CONTROLE C, C.date > '010186", (C.n veh)) Sélectionner les véhicules achetés depuis le 01/01/86 12 = select{home(VOITURE,01/01/86 ACHETE), allselect, scanselect} (ACHETE, ACHETE.date > '010186', (ACHETE.n veh)) Sélectionner les véhicules Renault 13 = select {home(VOITURE, ACHETE), allselect, scanselect} (VOITURE, VOITURE. marque = "Renault", (VOITURE.n veh)) Sélectionner tes véhicules Renauit non contrôlés depuis le 01/01/86 par différence des résultats intermédiaires 14 = difference {home(VOlTURE, ACHETE), assocdiff (|1.n veh), scandiff} (@3{| pipe~int},@1 (materialized}) Joindre le résultat avec le résultat de la sélection sur Achat 15 = join {home(VOITURE, ACHETE), assocjoin (14.n veh), nestedloop} (12 {materialized}, 14{|pipe~ext},12 .n veh = 14.n veh, (12.n veh)) ANNEXE 3 {Spread(l)} ASSOC C1 = sw (START) C2 = mp(C1) C23 = sw (C2) C3 = gp (C23) C24 = sw(C2) C4 = gp(C24) End~ASSOC {home(CONTROL)} ASSOC C5 = sw(C4) (T1 ,C6) =stp(C5) Local~op(T1) I1 = select{scanselect}(CONTROL C, C.date > '010186".(C.n veh)) 12 = send(ll, home(ACHETE), distribute~on I1.n veh) End~Local~op C7 = Iw(C6,12) C8 = sp(C7) End~ASSOC {spread(1 )} ASSOC C9 = gw(C8) C10 = gp (C9) End~ASSOC {home(ACHETE,VOITURE)} ASSOC C11=sw(C3) (T2,C12) = stp (C11) Local~op(T2) 13 = select {scanselect}(ACHETE, ACHETE.date > '010186", (ACHETE,n veh)) S2 = store(l3) End~Local~op C13 = Iw (C12,S2) C14 = sp (Cl 3) Local~op(12 ) Si = store(12) End~Local~op C15 = |w (C10,S1) C14 = sp (C15) ANNEXE 3 (suite) C15 = Iw (C10,S1) C14 = sp (C15) C16 = mw (C14) (T3,C17) = stp (C16) Local~op (T3) 14 = select {scanselect} (VOITURE, VOITURE.marque = 'Renault", (VOITURE,n veh)) 15 = difference (14,S1) 16 = local~send (15) End~Local~op C18 = Iw (C17,16) C19 = sp (C18) Loca~op (16) Result = join {nestedloop} (S2,#6, #6.n veh = S2.n veh, (#6.n veh)) End~Loca~op C20 = #w (C19, Result) C21 = sp (C20) End~ASSOC {spread (1)} ASSOC C22 = gw (C21) END = sp (C22) End~ASSOC REVENDICATIONS: 1. Procédé d'exécution parallèle de requête de bases de données relationnelles dans un environnement multi processeurs parallèle à mémoire distribuée consistant à intégrer le contrôle dans la requête lors de sa compilation, le contrôle étant obtenu en combinant un jeu d'opérations atomiques (Iw, sw, gw, stp, sp, gp, mp) de contrôle pour matérialiser un graphe de contrôle qui se superpose au graphe de la requête, ce graphe exprimant les dépendances entre les données par les liens entre les noeuds (11, 12, 3, 16) d'opérations et les types de dépendance de séquencement par des noeuds constructeur de deux types (SEQ, PIPE). 2. Procédé selon la revendication 1 caractérisé en ce que le graphe de contrôle exprime le groupement des noeuds en foyer (home, achète, voiture) d'une relation de la base, la colocalisation de plusieurs opérations sur un même noeud (select, store, figure 3) de l'architecture multi processeur, la réunion de plusieurs opérations (selected store, selected diff local transmit) en opération locale (loc~op4, loc~opl) et la réunion de plusieurs opérations locales (loc~op1, loc~op2, loc~op4) en association (A3). 3. Procédé selon la revendication 1 ou 2 caractérisé en ce que le premier type de noeud constructeur (PIPE) permet l'exécution d'une opération suivante dès que l'opération précédente à produit un tuple. 4. Procédé selon la revendication 2 caractérisé en ce que le deuxième type de noeud constructeur (SEQ) ne permet l'exécution de l'opération suivante qu'après l'achèvement complet de l'opération précédente. 5. Procédé selon la revendication 3 ou 4 caractérisé en ce que la synchronisation entre des opérations exécutées sur des groupes de noeuds différents et des opérations exécutées sur un même groupe est effectuée par deux familles de primitives de contrôle permettant la mise en place d'un mécanisme de contrôle. 6. Procédé selon la revendication 5 caractérisé en ce que une première famille est constituée de primitives de propagation (stp, gp, mp, sp), l'autre famille de primitives d'attente (Iw, gw, mw, sw), le mécanisme de contrôle ne pouvant être constitué que par la connexion de deux primitives de type opposé (attente,propagation). 7. Procédé selon la revendication 6 caractérisé en ce que les primitives d'attente envoient à l'opération de contrôle suivante qui est une primitive de propagation, un message d'activation lorsqu'au moins un message de type fin de flot (EOS) est reçu. 8. Procédé selon la revendication 7 caractérisé en ce que une primitive d'attente multiple vérifie que le nombre de messages fin de flot reçu est égal au nombre d'opérations locales exécutées par un même noeud et produisant le message fin de flot. 9. Procédé selon la revendication 7 caractérisé en ce que une primitive d'attente globale (gw) vérifie que le nombre de messages de fin de flot reçu est égal au nombre de noeuds du foyer (home) sur lequel une ou plusieurs opérations s'exécutent en parallèle. 10. Procédé selon la revendication 6, caractérisé en ce que les primitives de propagation envoient un message de fin de flot à au moins une instance de l'opération de contrôle suivante lorsque le message d'activation est reçu. 11. Procédé selon la revendication 10 caractérisé en ce que une primitive de propagation multiple (mp) envoie autant de message de fin de flot que d'opération locale suivante. 12 Procédé selon la revendication 10 caractérisé en ce que une primitive de propagation globale (gp) envoie autant de message de fin de flot qu'il y a de noeuds de le foyer (home) sur lequel s'exécute une ou plusieurs opérations locales suivante(s). 13. Procédé selon la revendication 10 caractérisé en ce que une primitive de propagation et de déclenchement (stp) envoie en outre un message de déclenchement à l'opération locale suivante, pour déclencher celle-ci. 14. Procédé selon la revendication 5 caractérisé en ce que des tables de portion de programme constituées à partir des primitives et correspondant au séquence de primitive de contrôle décrivant des morceaux de graphe formés de noeuds d'opérations associés au noeud constructeur permettent de reconstituer par l'association successive de plusieurs tables le graphe correspondant à l'exécution parallèle d'une requête sur une base de données relationnelle dans un environnement multi processeurs à mémoire distribuée. 15. Utilisation du procédé selon l'une des revendications précédentes caractérisé en ce qu'elle est effectuée dans la phase de parallèlisation d'un gestionnaire de requêtes chargé de compiler les requêtes exprimées en langage E.S.Q.L. par exécution d'une phase d'analyse, d'une phase d'optimisation physique, d'une phase de parallèlisation et d'une phase de génération de code en langage C+ +.