Brevet FR2651344A1 — publié le 19910301

La présente invention concerne les processeurs d'assemblage destinés à grouper des relations basées sur des champs d'assemblage de bases de données relationnelles. Un processeur classique d'assemblage pour des bases de données relationnelles tel que celui représenté dans "Principles of Database Systems" de J.D. Ullman, Computer Science Press Inc., Sec. 8.1 (p. 328, ligne 5 à page 331, ligne 6 dans la version japonaise traduite par Kunii, T. et Ookubo, N., et publiée par Nippon Computer Institute) est représenté en figure 5. Le processeur comporte un ordinateur 24 et une unité de disques 25 qui est reliée à l'ordinateur 24. Deux relations 5 et 6 sont stockées dans l'unité de disques 25. Chaque enregistrement de la relation 5 ou 6 comporte un champ d'assemblage 7 ou 8 et une adresse 11 ou 12. Dans l'ordinateur 24, il y a deux tables d'adresses 15 et 16, chacune étant constituée du champ 7 ou 8 et de l'adresse 11 ou 12 qui sont extraits des relations 5 et 6 et triés en fonction des valeurs des champs 7 et 8 (ou disposés dans l'ordre des nombres croissants). Une table d'adresses 17 ou 18 ne comporte que les adresses 11 ou 12 des enregistrements qui satisfont les conditions de l'assemblage (correspondance) déterminées par la comparaison entre les champs 7 et 8 dans les tables 15 et 16. Un ensemble 21 ou 22 d'enregistrements comporte des enregistrements qui sont extraits de la relation 5 ou 6 de manière à satisfaire les conditions de l'assemblage. Un ensemble d'enregistrements 23 contient les résultats d'un processus de l'assemblage. Dans une telle base de données relationnelles, toutes les données sont gérées sous la forme d'une table qu'on appelle "relation". Chaque relation est constituée d'une multitude de champs dans lesquels l'information caractéristique est décrite. Le processus de l'assemblage est un processus dans lequel un ensemble d'enregistrements ayant les mêmes valeurs des champs d'assemblage dans une multitude de relations 2 2651344 est déterminé, et les champs nécessaires sont extraits de l'ensemble pour fournir l'information caractéristique sur les relations. Par exemple, on décrira en liaison avec la figure 5, comment assembler deux relations. La relation "employé" comporte un champ "nom de l'employé" et un champ "numéro du titre". La relation 6 "titre" comporte un champ "numéro de titre" et un champ "titre". Lorsque le nom complet et le titre d'un employé ayant le nom de famille "Tanaka" sont extraits de ces deux relations 5 et 6, il est nécessaire de grouper les relations 5 et 6 conformément aux champs d'assemblage 7 ou 8 ou "numéro du titre". Tout d'abord, une valeur cible du "nom de l'employé", soit "Tanaka", est entrée dans l'ordinateur 24 (étape Si). Alors, l'ordinateur extrait de la relation 5 dans l'unité de disques 25 les valeurs du champ d'assemblage 7 et les adresses 11 des enregistrements ayant la chaîne de caractères "Tanaka" dans le champ nom de l'employé (soit 1001, 1004, 1005, et 1008) et les trie dans l'ordre des valeurs croissantes du champ 7 pour fournir une table d'adresses (étape S2). D'une façon similaire, l'ordinateur 24 extrait de la relation 6 dans l'unité de disques 25 les valeurs du champ d'assemblage 8 et les adresses d'enregistrement 12 et les trie dans l'ordre des valeurs croissantes du champ 8 pour fournir une table d'adresses 16 (étape S3). Alors, les champs d'assemblage 7 et 8 des tables d'adresses 15 et 16 sont comparés de manière à extraire les adresses 11 et 12 des enregistrements qui satisfont les conditions d'assemblage ou ont les mêmes valeurs du champ d'assemblage dans les tables 15 et 16 (1005, 1001, 1008 et 1004 de la table 15 et 2002, 2004, et 2001 de la table 16), produisant les tables d'adresses 17 et 18 (étape S4). Alors, les champs nécessaires des enregistrements ayant les adresses dans les tables 17 et 3 2651344 18;. à savoir le champ nom de l'employé de la relation 5 et le champ titre de la relation 6 sont extraits des relations 5 et 6 pour fournir deux ensembles d'enregistrements 21 et 22 qui satisfont les conditions d'assemblage (étape S5). Enfin, la comparaison des champs 7 et 8 des ensembles 21 et 22 fournit les résultats final 23 de l'assemblage (étape S6). Dans un tel processeur d'assemblage, qui est seul à exécuter le processus précédent, le nombre des étapes du processus augmente avec la taille des relations à grouper. Par conséquent, il s'est avéré difficile de fournir un processeur d'assemblage rapide pour un grand nombre de relations. Par conséquent, la présente invention a pour objet un processeur d'assemblage rapide pour un grand nombre de relations devant être rassemblées. Selon la présente invention, on prévoit un processeur d'assemblage pour des bases de données relationnelles, qui comprend un processeur principal, pour traiter l'information, une mémoire principale reliée au processeur principal pour stocker des informations; une multitude de processeurs auxiliaires commandée par le processeur principal; une multitude de mémoires auxiliaires connectées chacune au processeur auxiliaire, et un ensemble pour diviser et stocker les relations des bases de données relationnelles dans les mémoires auxiliaires en unités d'enregistrement de façon que les champs d'assemblage des relations devant être rassemblées soient extraits des mémoires auxiliaires et triés en parallèle dans les processeurs auxiliaires. La présente invention sera bien comprise lors de la description suivante faite en liaison avec les dessins ci-joints dans lesquels: Les figures 1 et 2 sont des schémas sous forme de blocs de processeurs d'assemblage pour bases de données relationnelles selon des modes de réalisation de l'invention; 4 2651344 La figure 3 est un organigramme permettant d'expliquer le fonctionnement du processeur principal des figures 1 et 2; La figure 4 est un organigramme permettant d'expliquer le fonctionnement de chacun des processeurs auxiliaires des figures 1 et 2; La figure 5 est un schéma sous forme de blocs d'un processeur d'assemblage classique pour bases de données relationnelles; et La figure 6 est un organigramme permettant d'expliquer le fonctionnement du processeur d'assemblage classique. En figures 1 et 2, le processeur d'assemblage est constitué d'un processeur principal 1; d'une unité principale 2 de disques reliée au processeur principal 1; de quatre processeurs auxiliaires 3a-3d commandés par le processeur principal 1; et de quatre unités auxiliaires de disques 4a-4d, chacune étant connectée au processeur auxiliaire 3a-3d correspondant. Les relations 5a-5d et 6a-6d sont divisées et stockées dans les unités auxiliaires de disques 4a-4d, respectivement. En figure 1, les référence 7a-7d et 8a-8d désignent les champs d'assemblage F1 des relations 5a-5d et 6a-6d. 9a-9d sont les autres champs F2 des relations a-5d.10a-lOd sont les autres champs F3 des relations 6a-6d. lla-lld et 12a-12d sont les adresses d'enregistrement des relations 5a-5d et 6a-6d, respectivement. 13a-13d et 14a-14d sont des tables d'adresses qui sont constituées des champs d'assemblage (F1), 7a-7d, 8a-8d et des adresses d'enregistrement lla- lld et 12a-12d qui sont stockées dans l'ordre des valeurs croissantes des champs (F1) 7a-7d et 8a-8d. L'expression "ordre des valeurs croissantes" qu'on emploie ici veut dire l'ordre des nombres naturels 1, 2, 3,... ou l'ordre des lettres alphabétiques a, b, c, et 16 sont des tables d'adresses dans lesquelles les tables d'adresses 13a-13d et 14a-14d transférées des 2651344 processeurs auxiliaires 3a-3d au processeur principal 1 sont interclassées et triées par le processeur principal 1 dans l'ordre des valeurs croissante des champs (F1) 7 et 8. 17a-17d et 18a-18d sont des tables d'adresses réalisées pour chacun des processeurs auxiliaires 3a-3d en comparant les champs (F1) 7 et 8 dans les tables d'adresses 15 et 16 afin de déterminer les adresses d'enregistrement qui satisfont les conditions d'assemblage. En figure 2, 19a-19d et 20a-20d sont des ensembles d'enregistrements qui satisfont les conditions d'assemblage lues par les processeurs auxiliaires 3a-3d à partir des relations 5a-5d et 6a-6d dans les unités auxiliaires de disques 4a-4d. 21 et 22 sont des ensembles des enregistrements 19a-19d et 20a-20d obtenus dans les processeurs auxiliaires 3a-3d et transférés au processeur principal 1. 23 est un ensemble d'enregistrements donnés par le processus d'assemblage. Le processus d'assemblage est caractérisé en ce que les relations d'une base de données relationnelles sont divisées et stockées dans les unités respectives auxiliaires de disques 4a-4d et en ce que les champs d'assemblage sont extraits des unités auxiliaires 4a-4d et triés ou disposés en parallèle dans l'ordre des valeurs croissantes dans les processeurs auxiliaires respectifs 3a-3d. Plus précisément, chaque processeur auxiliaire 3a-3d lit le champ d'assemblage dans l'unité auxiliaire de disques 4a-4d pour former une table d'adresses qui est constituée des champs d'assemblage et des adresses d'enregistrement contenant le numéro du processeur auxiliaire 3a-3d. La table d'adresses est triée dans l'ordre des valeurs croissantes du champ d'assemblage et transférée au processeur principal 1. Le processeur 1 choisit les adresses d'enregistrement qui satisfont les conditions d'assemblage et les renvoie aux processeurs auxiliaires 3a-3d. Le processeur auxiliaire 3a-3d lit les champs nécessaires dans l'unité auxiliaire de disques 4a-4d et G 2651344 transfère au processeur principal un ensemble d'enregistrements qui sont constitués des champs d'assemblage et des autres champs caractéristiques nécessaires. Le processeur principal 1 exécute un processus d'assemblage en conformité avec les enregistrements transférés par les unités auxiliaires respectives de disques 4a-4d. On décrira, en liaison avec les figures 3 et 4, les opérations dans lesquelles la relation 5 constituée du champ (F1) 7 et du champ (F2) 9 et la relation 6 comprenant le champ (F1) 8 et le champ (F3) sont assemblées conformément aux champs (F1) 7 et 8 et comment les champs (F1) 7, (F2) 9 et (F3) 10 sont extraits. Tout d'abord, le processeur principal 1 donne comme instructions aux processeurs auxiliaires respectifs 3a-3d d'extraire les valeurs-cibles F1, F2 et F3 (étape T1 en figure 3). En figure 4, chaque processeur auxiliaire 3a-3d extrait de l'unité auxiliaire de disques 4a-4d les champs d'assemblage (F1) 7a-7d et les adresses d'enregistrement lla-lld et les trie dans l'ordre des valeurs croissantes du champ d'assemblage (F1) 7a-7d pour fournir une table d'adresses 13a-13d (étape T2). D'une façon similaire, les champs d'assemblage (F1) 8a-8d et les adresses d'enregistrement 12a-12d de chaque relation 6a-6d sont extraits et triés dans l'ordre des valeurs croissantes du champ (F1) 8a-8d pour fournir une table d'adresses 14a-14d (étape T3). Les processeurs auxiliaires respectifs 3a-4d transfèrent les tables d'adresses obtenues 13a-13d et 14a-14d au processeur principal 1 (étape T4). Ces processus sont exécutés en parallèle dans les processeurs auxiliaires respectifs 3a-3d. En figure 3, le processeur principal 1 interclasse et trie les tables d'adresses 13a-13d transférées à partir des processeurs auxiliaires 3a-4d conformément aux champs (F1) 7a-7d pour fournir une table d'adresses 15 concernant la relation 5 (étape T5). 7 2651344 D'une façon similaire, les tables d'adresses 14a-14d sont interclassées et triées conformément aux champs (F1) 8a-8d pour fournir une table d'adresses 16 concernant la relation 6 (étape T6). Les champs d'assemblage (F1) 7 et 8 des tables 15 et 16 sont comparés de manière à déterminer un ensemble d'enregistrements qui satisfont les conditions d'assemblage et ont les mêmes valeurs du champ d'assemblage comme cela est représenté par les flèches en figure 1. Le processeur principal 1 classe alors les adresses des enregistrements satisfaisant les conditions d'assemblage sur la base du numéro d'un processeur auxiliaire 3a-3d qui est contenu dans l'adresse d'enregistrement pour former de nouvelles tables d'adresses 3aA-3dD pour les processeurs auxiliaires respectifs 3a-3d (étape T7) et les transfère aux processeurs auxiliaires 3a-3d (étape T8). Dans le mode de réalisation de la figure 1, le chiffre le plus haut des adresses d'enregistrement 17a-17d et 18a-18d dans les tables d'adresses 3aA-adD représente le numéro d'un processeur auxiliaire dans lequel l'enregistrement est stocké. Plus précisément, les nombres 1-4 dans le chiffre le plus haut d'une adresse d'enregistrement correspondent aux processeurs auxiliaires respectifs 3a-3d. En figure 4, les processeurs auxiliaires respectifs 3a-3d lisent les champs d'assemblage (F1) 7a- 7d des enregistrements aux adresses d'enregistrement lla-lld dans les tables d'adresses 17a-17d et les autres champs caractéristiques nécessaires (F2) 9a-9d à partir des relations 5a-5d dans les unités auxiliaires de disques 4a-4d pour déterminer des ensembles d'enregistrements 19a-19d qui satisfont les conditions d'assemblage (étape Tg), et les transfère au processeur principal 1 (étape T1o). D'une façon similaire, les champs d'assemblage (F1) 8a-8d des enregistrements aux adresses d'enregistrement 12a-12d dans les tables d'adresses 18a-18d et les autres champs caractéristiques 8 2651344 nécessaires (F3) lOa-lOd sont lus à partir des relations 6a-6d dans les unités auxiliaires de disques respectives 4a-4d pour déterminer des ensembles d'enregistrements a-20d qui satisfont les conditions d'assemblage (étape Tg) et les transfèrent au processeur principal 1 (étape T10). Ces processus sont exécutés en parallèle dans les processeurs auxiliaires respectifs 3a-3d pour chaque relation affectée. En figure 3, le processeur principal 1 compare les champs (F1) 7a-7d des ensembles d'enregistrements 19a-19d transférés à partir des processeurs auxiliaires 3a-3d pour trier ceux qui satisfont les conditions d'assemblage dans l'ordre des valeurs croissantes pour fournir un ensemble d'enregistrements 21 (étape T11). D'une façon similaire, les champs d'assemblage (F1) 8a-8d et (F3) lOa-lOd des ensembles d'enregistrements 20a-20d sont comparés pour trier ceux qui satisfont les conditions d'assemblage dans l'ordre des valeurs croissantes afin de fournir un ensemble d'enregistrements 22 (étape T11). Alors, les champs (F1) 7 et 8 des ensembles 21 et 22 sont comparés pour fournir les résultats de l'assemblage ou ensemble d'enregistrements 23 (étape T12). En variante, le nombre des processeurs auxiliaires, qui est de quatre dans le mode de réalisation précédent, peut être de deux ou plus. Le nombre des unités de disques connectées au processeur principal ou auxiliaire peut être de deux ou plus. Lorsque les champs d'assemblage sont indexés, l'index constitué des champs d'assemblage et des adresses d'enregistrement triées en fonction des champs d'assemblage est stocké dans l'unité principale de disques 2 reliée au processeur principal 1. Plus précisément, les tables d'adresses 15 et 16 de la figure 1 sont identiques à l'index décrit par J. D. Ullman, "Principles of Database Systems", Sec. 2.5 (page 79, lignes 3 à page 81, ligne 7 dans la traduction japonaise), qui sont stockées dans l'unité principale de 9 2651344 disques 2. Comme le processeur principal 1 compare les valeurs des champs d'assemblage dans l'index afin d'extraire les enregistrements qui satisfont les conditions d'assemblage, il est possible d'assembler les relations en répétant le processus précédent. Par exemple, dans le cas o les champs d'assemblage 7 et 8 des relations 5 et 6 sot indexés en figure 1, les index sont triés conformément aux champs 7 et 8 de la même manière que dans les tables d'adresses 15 et 16 de la figure 1, de sorte qu'il y a comparaison des champs 7 et 8. En répétant le processus précédent, il est possible d'assembler les relations 5 et 6. Dans ce cas, il n'est pas nécessaire de faire les tables d'enregistrement 15 et 16, d'o l'obtention d'un processus plus rapide d'assemblage que dans le précédent mode de réalisation. Dans des ordinateurs ordinaires en parallèle, les ressources de l'ordinateur, telles que l'unité centrale de traitement, la mémoire et les disques, sont affectées de manière à exécuter des opérations en parallèle de façon efficace, d'o l'obtention d'un traitement à haute vitesse. Cependant, avec de tels processeurs simples fonctionnant en parallèle, il est difficile de fournir un traitement à haute vitesse pour obtenir la conclusion désirée. D'autre part, dans le processeur de la présente invention, le processeur principal affecte plusieurs opérations aux processeurs auxiliaires respectifs pour l'exécution simultanée d'une opération d'assemblage sur une base de données relationnelles, d'o l'obtention d'un traitement à haute vitesse. On décrira maintenant les résultats d'un essai effectué par la demanderesse. Les mesures de 000 et 1 OOO assemblages effectués par des machines à base de données à haute vitesse (MBH) qui comportent trois unités centrales de traitement (un processeur central et deux processeurs auxiliaires) et cinq unités centrales de traitement (un processeur principal et 2651344 quatre processeurs auxiliaires), respectivement, sont les suivantes: IDM 500,1-UCT MBH, 3-UCT MBH, 5-UCT Temps de traite- ment (s) 114 7,46 5,45 Rapport de vitesse 1 15,28 20,91 Les données relatives à une unité centrale de traitement (UCT) concernent une machine à base de données à un seul processeur IDM500 de la société U.S. Britton Lee Corp. (devenue Share Base Corp.). Des unités centrales de traitement MBH et de l'IDM500 sont des unités de 32 bits dites MC-68020 de la société Motorola et Zilog Z-8000 à 16 bits, respectivement, mais il reste évident que la présente invention donne des effets importants. La présente invention n'est pas limitée aux exemples de réalisation qui viennent d'être décrits, elle est au contraire susceptible de modifications et de variantes qui apparaîtront à l'homme de l'art. il 2651344 REVEND I CATIONS 1 - Processeur d'assemblage pour bases de données relationnelles, caractérisé en ce qu'il comprend: - un processeur principal (1) pour traiter l'information; - une mémoire principale (2) reliée au processeur principal pour stocker l'information; - une multitude de processeurs auxiliaires (3) commandés par le processeur principal; - une multitude de mémoires auxiliaires (4) connectées chacune au processeur principal; - un moyen pour diviser et stocker des relations des bases de données relationnelles dans les mémoires auxiliaires en unités d'enregistrement; chacun des processeurs auxiliaires extrayant des champs d'assemblage de relations devant être assemblées à partir de la mémoire auxiliaire, les triant dans un ordre prédéterminé et les transférant au processeur principal; - le processeur principal triant les champs d'assemblage et sélectionnant ceux qui satisfont des conditions complètes d'assemblage, classant les champs d'assemblage sélectionnés pour chacun des processeurs auxiliaires, et transférant les champs d'assemblage classés aux processeurs auxiliaires correspondants; - le processeur auxiliaire formant de nouveaux champs d'assemblage qui satisfont de nouvelles conditions d'assemblage correspondant aux champs d'assemblage transférés, triant les nouveaux champs d'assemblage et les transférant au processeur principal; et - le processeur principal triant les nouveaux champs d'assemblage et sélectionnant les champs qui satisfont des conditions complètes des champs d'assemblage. 2 - Processeur selon la revendication 1, caractérisé en ce que les processeurs auxiliaires 12 2651344 comportent chacun une multitude de mémoires auxiliaires (4a-4d) pour stocker lesdites relations. 3 - Processeur selon la revendication 1, caractérisé en ce que le processeur principal exécute une multitude de cycles de transfert de données avec les processeurs auxiliaires pour fournir les nouveaux champs d'assemblage. 4 - Processeur selon la relation 1, caractérisé en ce que le tri est exécuté dans l'ordre de nombres croissants ou décroissants. - Processeur selon la revendication 1, caractérisé en ce que le tri est effectué dans l'ordre direct ou inverse des lettres de l'alphabet.