Brevet FR2791790A1 — publié le 20001006

Procédé de préconditionnement et de codage d'une table de données, et procédé de mise en oeuvre de requêtes tabulaires sur une machine à capacités vectorielles. La présente invention concerne un procédé de préconditionnement d'une table de données destinée à être utilisé par un moteur de recherche répondant à des requêtes de sélection d'articles sur des critères déterminés. Elle concerne également un procédé de recherche d'articles, en réponse à une requête déterminée, dans une table de données et un moteur de recherche io agissant sur une table de données contenant un ensemble d'articles cible, activé par des requêtes de sélection d'articles sur des critères déterminés. Le domaine d'application est celui de l'entrepôt de données plus connu sous la terminologie anglo-saxonne de "data warehousing". Il s'adresse plus particulièrement à de grandes bases de données historiques, relativement stables dans le temps à partir desquelles on veut pouvoir extraire des populations définies par critères avec une sollicitation très fréquente et des temps de réponse les plus faibles possibles. Typiquement ces bases peuvent contenir plusieurs millions d'articles pouvant comporter chacun plusieurs centaines de champs et les temps de réponse à des requêtes standards peuvent être longs alors que l'utilisateur souhaiterait qu'ils soient de l'ordre de la seconde. Elles sont mises à jour périodiquement, au plus chaque nuit. Les clients potentiels de ce type de bases sont par exemple, la grande distribution, les banques et les assurances. La grande distribution manipule des bases historiques des caisses et des cartes d'achat pour rechercher des populations cible pour le marketing direct. Les banques et les assurances manipulent également de telles bases historiques relatives à des ordres client, pour des recherches de populations, clientes potentielles de nouveaux produits, etc. On connaît des solutions reposant sur la mise en ceuvre du parallélisme pour l'extraction d'articles sur unités de stockage. Toutes les solutions connues utilisent un mécanisme de gestion de bases de données relationnelles mises à jour et consultées depuis un environnement réseau. Ce mécanisme est connu sous l'acronyme RDBMS (Relational DataBase Management System). Dans un premier type de solution, un moteur de recherche SQL (Search Query Language), complètement propriétaire, est construit sur une architecture hautement parallèle à base de noeuds multiprocesseurs pilotant des disques sur lesquels la base de données est répartie. Les requêtes sont fractionnées sur les différents noeuds, puis sur les processeurs. Cette solution a comme principal inconvénient d'avoir un rapport prix/performance qui reste élevé. Ainsi, pour atteindre de hautes performances, les configurations doivent être importantes, donc très coûteuses. Un deuxième type de solutions utilise des logiciels de bases de données relationnelles standards sur des machines standards généralement multiprocesseurs. Dans ce deuxième type de solutions, un moteur de recherche SQL standard met en oeuvre le parallélisme élevé suivant les mêmes principes que les solutions du premier type mais avec des variantes d'architecture 'sur les mécanismes de fractionnement des requêtes et sur la gestion des antémémoires. Les inconvénients de ce deuxième type de solutions sont les mêmes que ceux du premier type, aggravés d'une perte de performance due à la lourdeur du logiciel qui est une conséquence de sa généralité. L'invention a notamment pour but de pallier ces inconvénients en fournissant un moteur de recherche assez puissant pour effectuer dans des délais très courts, de l'ordre de quelques secondes, sur des tables de données de grande dimension mais stables dans le temps (mises à jour périodiques, au plus chaque nuit), des requêtes de sélection d'articles sur critères. A cet effet, l'invention a pour premier objet un procédé de préconditionnement d'une ou plusieurs tables de données d'un serveur applicatif décisionnel, destinée à être traitée par un moteur de recherche répondant à des requêtes de sélection d'articles sur des critères déterminés, émises par le serveur applicatif décisionnel. Le procédé selon l'invention consiste à: - analyser les prédicats contenus dans les champs des articles destinés à remplir la base de données relationnelle en fonction de relations autorisée déterminés; - créer une nomenclature des prédicats à partir de cette analyse; - coder numériquement les prédicats conformément à la nomenclature, en tenant compte de la nature des prédicats et des relations à mettre en ceuvre io sur les prédicats dans les requêtes. Il consiste enfin à présenter les prédicats codés, sous la forme d'une table de valeurs numériques. L'invention a pour deuxième objet un procédé de recherche d'articles, en réponse à une requête déterminée, dans une table de données, consistant à installer une copie de la table de valeurs numériques obtenue par le procédé précédent, sur une machine à capacité vectorielle opérant le traitement des valeurs numériques du tableau en fonctions de la requête servie par le serveur applicatif décisionnel. Enfin elle a pour troisième objet un système de recherche mis en ceuvre par un serveur applicatif décisionnel comportant une base de données relationnelle contenant un ensemble d'articles cible, et un moteur de recherche couplé au serveur applicatif décisionnel, activé par une requête de sélection d'articles sur des critères déterminés émise par le serveur applicatif décisionnel. Selon l'invention, le système est caractérisé en ce que le moteur comporte des moyens de préconditionnement des données de la base et d'installation d'une table codée, correspondant à la base, sur une machine à capacités vectorielles, ces moyens comportant: - des moyens de lecture d'un fichier de données correspondant à la base; - des moyens pour constituer une nomenclature des valeurs des champs contenus dans le fichier précédent; des moyens de codage des champs conformément à la nomenclature en tenant compte de la nature des champs et des relations à mettre en oeuvre sur les prédicats dans la requête; - des moyens d'analyse des requêtes émises par le serveur applicatif décisionnel, en tenant compte de relations autorisées, de contraintes sur les prédicats et de la nomenclature; et des moyens de codage de la requête filtrée, en un ensemble de vecteurs contenant les valeurs à trouver dans les champs selon les relations associées, sous forme d'un fichier d'entrée exploitable par la machine à capacités o vectorielle. Le système comporte en outre des moyens pour extraire en clair les données recherchées dans le fichier résultat obtenu en sortie de la machine à capacités vectorielle à partir de moyens de recherche installés dans le serveur applicatif décisionnel. Des synthèses statistiques peuvent être en outre opérées sur les résultats de la recherche. L'invention a notamment pour avantage de fournir des temps de réponse très courts, inaccessibles par les techniques RDBMS, et un débit de requêtes élevé. Elle a pour autres avantages d'être transparente pour l'application existante et de n'avoir aucun impact au niveau applicatif. D'autres avantages et caractéristiques de la présente invention apparaîtront à la lecture de la description qui suit faite en référence aux figures annexées qui représentent: - la figure 1, un schéma de principe d'un système de recherche mettant en oeuvre un moteur de recherche selon l'invention; - la figure 2, un schéma de principe d'un module de préconditionnement et d'installation de la base de données, selon l'invention; et - la figure 3, un schéma de principe d'un agent SELECT selon l'invention. Dans ces figures, les éléments homologues sont désignés par les mêmes références numériques. Le principe de l'invention est décrit ci-après en s'appuyant pour son illustration, sur l'utilisation d'une machine vectorielle connue sous l'appellation de supercalculateur. Une telle machine est caractérisée, d'une part, par des processeurs possédant plusieurs unités arithmétiques, "pipelines" en terminologie anglo-saxonne et, d'autre part, par une bande passante mémoire suffisante pour assurer l'alimentation de tous les processeurs à chaque top d'horloge. L'invention n'est cependant pas limitée à ce type de machine et s'applique à toute machine à capacités vectorielles, c'est-à-dire des machines dont les performances se rapprochent de celles des supercalculateurs vectoriels. En effet, les calculateurs scalaires actuels comportent plusieurs opérateurs arithmétiques et les bandes passantes mémoire progressent grâce à l'usage d'une technologie, connue sous la terminologie anglo- saxonne "crossbar" (autocommutateur). On peut donc envisager dans un avenir proche que les performances des calculateurs scalaires se rapprochent de celles des supercalculateurs vectoriels. Les supercalculateurs vectoriels offrent dès maintenant une réponse aux demandes toujours grandissantes de performances dans les domaines des sciences et de l'industrie en général. Les machines vectorielles sont aujourd'hui les seules à pouvoir répondre aux contraintes déjà exprimées dans le préambule de la présente description. L'idée de base de l'invention est de tirer parti de la puissance exceptionnelle des machines à capacités vectorielles pour effectuer des comparaisons sur les vecteurs numériques, images codées des champs de la table de données. La transformation en nombres des données de la table à traiter, et la formation d'une nomenclature à partir de ces nombres sont réalisées lors de l'installation de la base de données relationnelle. Le codage des données en nombres a pour autre effet avantageux de compacter les données de la base. Ainsi par rapport aux solutions de type RDBMS qui manipulent le contenu en clair de chaque champ, le procédé selon l'invention n'agit que sur un nombre représentatif de ce champ. La table ainsi compactée peut être en général contenue en mémoire (pas d'entrée-sortie disque), ou bien peut être chargée en mémoire par colonne ce qui ne représente que des volumes réduits d'entrées/sorties. Enfin l'invention offre la possibilité d'adapter le codage au type de requêtes qui seront servies. Elle permet en outre la mise en oeuvre d'une optimisation efficace du traitement. La figure 1 illustre un schéma de principe d'un système de recherche mettant en oeuvre un moteur de recherche selon l'invention. Le système de recherche comporte, à gauche de la figure, un système o applicatif décisionnel 1, représentatif du cas général, délimité par une ligne fermée discontinue, et le moteur de recherche 2, à droite de la figure, délimité par une ligne fermée discontinue. Le système applicatif décisionnel 1 est couplé à un poste utilisateur (ou client) 3. Le serveur applicatif décisionnel 1 comporte un serveur applicatif 4 générant des requêtes prédéfinies, un RDBMS 5 gérant une base de données 6, et un agent SQL 7 chargé d'analyser les requêtes soumises par le serveur applicatif 4 et, éventuellement, d'extraire les articles cible de la base 6 en s'appuyant sur le RDBMS 5. L'utilisateur (le client) émet, via le serveur applicatif 4, des requêtes correspondant à des caractéristiques des articles cible répondant à des critères déterminés et reçoit du même serveur 4 le résultat des requêtes sous la forme soit d'une liste d'articles satisfaisant les critères soit de synthèses statistiques, ou les deux. Le moteur 2 met en oeuvre un module 8 de préconditionnement de la table de données et exploite les ressources d'un supercalculateur 9 pour le traitement d'un copie 10 de la table préconditionnée en vue d'en extraire les articles cible. Le module 8 de préconditionnement de la table de données reçoit les données importées par exemple d'une banque de données 11. Ces données sont organisées sous forme d'un tableau et codées numériquement selon un format directement exploitable par le supercalculateur 9 et exécutable de façon optimale par les requêtes. Une copie de cette table est accessible par le supercalculateur 9. Elle réside, par exemple, dans l'espace mémoire du supercalculateur 9 et peut être partionnée si sa taille dépasse celle de la mémoire disponible. Le supercalculateur 9 reçoit de l'agent SQL 7 la traduction des requêtes soumises par le serveur applicatif 4 sous forme d'un fichier d'entrée. Le supercalculateur 9 traite ensuite ce fichier d'entrée selon un programme de recherche déterminé tirant le parti maximum de la puissance des pipelines du o supercalculateur 9 en travaillant sur les colonnes de la copie 10 de la table. A l'issue du traitement, il délivre en sortie sous forme d'un fichier, les résultats du traitement effectué correspondant à la liste des numéros de ligne des articles sélectionnés par la recherche et, éventuellement, aux synthèses statistiques demandées sur les articles trouvés. Si les articles en clair sont demandés, I'agent SQL 7 exploite le fichier résultat pour extraire les articles sélectionnés en clair, à partir de la base de données relationnelle 6. L'agent SQL 7 transmet ensuite les résultats (articles sélectionnés et/ou synthèses statistiques) sous forme de réponse SQL au serveur applicatif 4 émetteur de la requête. Un module 12 de cohérence de tables, accessible à l'agent SQL 7, contient la liste des identifiants des tables présentes et la nomenclature des prédicats pour chacune d'entre elles. La figure 2 illustre un schéma de principe du module 8 de préconditionnement et d'installation de la table, selon l'invention, délimité par une ligne fermée discontinue. Il comporte des premiers moyens 13 de lecture des données importées sur un support quelconque, article par article, à l'entrée du module, et provenant par exemple d'une banque de données 11. Les articles lus sont ensuite, d'une part, complétés de leur numéro et transmis au système de gestion de base de données relationnelle 5 qui crée la base de données en clair 6 dans le serveur applicatif décisionnel 1. Il comporte, d'autre part, des deuxièmes moyens 14 qui analysent les prédicats sur les articles en fonction de relations autorisées et de contraintes sur les prédicats. On donne ci-après deux exemples de contraintes sur les prédicats: Dans un premier exemple, une colonne de la base de données ne comporte que des valeurs numériques. Dans cet exemple, il n'est pas nécessaire de coder numériquement ce qui est déjà numérique. Dans un deuxième exemple, une colonne de la base de données ne contient que des mots pour lesquels l'ordre alphabétique sera utilisé dans les recherches. Dans cet exemple, I'analyse du prédicat tiendra compte de cette relation pour le codage numérique du prédicat.(préservation de l'ordre) s Des troisièmes moyens 15 codent les valeurs des prédicats issus des deuxièmes moyens 14. Ce codage consiste à remplacer les valeurs des champs par leurs index dans la nomenclature des valeurs possibles. Des quatrièmes moyens 16 créent une nomenclature des prédicats issus des deuxièmes moyens 14 en fonction du codage par les troisièmes moyens 15. Le module de préconditionnement 8 fournit d'autre part l'identifiant de la base codée. La table codée, la nomenclature des prédicats et l'identifiant de la base se présentent sous la forme de fichiers, respectivement référencés 10, 17 et 18 sur la figure. La figure 3 illustre un schéma de principe d'un agent SELECT 19 selon l'invention. Il se substitue à l'agent SQL 7 du serveur applicatif décisionnel 1 qui l'héberge. Il comporte des moyens 20 de transformation des requêtes, délimités par une ligne fermée en pointillés, lesquelles requêtes sont soumises par le serveur applicatif 4 en fonction de la nomenclature des prédicats 17, des contraintes sur les prédicats et des relations autorisées. Les moyens 20 de transformation comportent des moyens 21 d'analyse de la requête SELECT et des moyens 22 de codage des prédicats. Les moyens 21 d'analyse de la requête traduisent la requête en un ensemble de vecteurs représentatifs des champs à trouver et des relations mises en ceuvre en tenant compte des relations autorisées. Les vecteurs sont ensuite codés par les moyens de codage des prédicats en fonction de la nomenclature des prédicats, des contraintes sur les prédicats et des relations autorisées. Il y a autant de vecteurs que de valeurs possibles dans les champs de la table. io L'analyse permet de construire, par ailleurs, pour chacun de ces vecteurs un vecteur définissant quel type de comparaison effectuer pour chacune des valeurs de champ. Les vecteurs sont agencés sous forme d'un fichier d'entrée exploitable par le supercalculateur 9. i5 Un programme de recherche intégré au supercalculateur exécute les comparaisons entre les vecteurs et toutes les lignes du tableau. Ces comparaisons sont effectuées colonne par colonne. En cas de coïncidence d'une ligne, son numéro est conservé et la réponse fournie par le supercalculateur à l'agent SQL 7 se présente sous la forme d'un fichier résultat comportant la liste des numéros correspondant aux lignes sélectionnées. C'est à partir de ce fichier que les synthèses statistiques demandées sont calculées. Un module d'extraction 23 construit ensuite, si elle est demandée, la réponse en clair destinée au serveur applicatif 4 émetteur de la requête, en extrayant de la base de données relationnelle 6, les articles correspondant à la liste des numéros de lignes du fichier résultat du supercalculateur 9 en utilisant le numéro d'article ajouté à la base 6. L'agent SELECT 19 fournit en outre l'identifiant de la table. C'est le module de cohérence de tables 12 qui contrôle l'identité de la table à traiter en cas de pluralité de tables. Un agent d'administration 24 est en outre couplé à l'agent SELECT 19 et permet de contrôler l'activité du supercalculateur 9 et gérer les anomalies. Il active en outre le chargement du programme de recherche dans le supercalculateur 9. l REVENDICATIONS 1. Procédé de préconditionnement d'une ou plusieurs tables de données d'un serveur applicatif décisionnel (1), destinée à être traitée par un moteur de recherche (2) répondant à des requêtes de sélection d'articles sur des critères déterminés, émises par le serveur applicatif décisionnel (1), caractérisé en ce qu'il consiste à: - analyser (14) les prédicats contenus dans les champs des articles destinés à remplir la base de données relationnelle (6) en fonction de relations io autorisée déterminés; créer (16) une nomenclature (17) des prédicats à partir de cette analyse; - coder (15) numériquement les prédicats conformément à la nomenclature (17), en tenant compte de la nature des prédicats et des relations à mettre en ceuvre sur les prédicats dans les requêtes; et - en ce qu'il consiste à présenter les prédicats codés, sous la forme d'une table (10) de valeurs numériques. 2. Procédé selon la revendication 1, caractérisé en ce que le codage consiste à remplacer les valeurs des prédicats par leur index dans la nomenclature des valeurs possibles. 3. Procédé selon la revendication 1, caractérisé en ce que le codage compacte les données. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que le codage prend en compte le type de requête servie. 5. Procédé de recherche d'articles, en réponse à une requête déterminée, dans une table de données, caractérisé en ce qu'il consiste à installer une copie (10) de la table de valeurs numériques obtenue par le procédé selon l'une quelconque des revendications 1 à 4, sur une machine à capacité vectorielle (9) opérant le traitement des valeurs numériques du tableau en fonctions de la requête servie par le serveur applicatif décisionnel (1). 6. Procédé selon la revendication 5, caractérisé en ce que la requête est exprimée par un ou plusieurs vecteurs représentatifs des valeurs recherchées dans un champ, et en ce que le traitement consiste à comparer le ou les vecteurs à toutes les lignes du tableau, colonne par colonne, en conservant pour chaque coïncidence le numéro de la ligne. 7. Procédé selon la revendication 6, caractérisé en ce qu'il consiste, à partir de l'ensemble des numéros des lignes sélectionnées et de la base de données relationnelle (6) comprenant un champ additionnel contenant le numéro des lignes, à extraire de la base de données relationnelle (6) les articles recherchés en clair dont les numéros correspondent, en réponse à une s requête. 8. Procédé selon les revendications 6 ou 7, caractérisé en ce qu'il consiste à exprimer les résultats du traitement sous forme statistique dont une synthèse est fournie en réponse à une requête. 9. Procédé selon l'une quelconque des revendications 5 à 8, caractérisé en ce que la machine à capacités vectorielles (9) est un supercalculateur. 10. Système de recherche mis en oeuvre par un serveur applicatif décisionnel (1) comportant une base de données relationnelle (6) contenant un ensemble d'articles cible, et un moteur de recherche (2) couplé au serveur applicatif décisionnel (1), activé par une requête de sélection d'articles sur des critères déterminés émise par le serveur applicatif décisionnel (1), caractérisé en ce que le moteur (2) comporte des moyens (8) de préconditionnement des données de la base (6) et d'installation d'une table codée (10), correspondant à la base (6), sur une machine à capacités vectorielles (9), ces moyens (8) comportant: - des moyens (13) de lecture d'un fichier de données correspondant à la base; - des moyens (16) pour constituer une nomenclature (17) des valeurs des champs contenus dans le fichier; - des moyens (15) de codage des champs conformément à la nomenclature (17) en tenant compte de la nature des champs et des relations à mettre en oeuvre sur les prédicats dans la requête; - des moyens (21) d'analyse des requêtes émises par le serveur applicatif décisionnel (1), en tenant compte de relations autorisées, des contraintes sur les prédicats et de la nomenclature (17); et - des moyens (22) de codage de la requête filtrée, en un ensemble de vecteurs contenant les valeurs à trouver dans les champs selon les relations associées, sous forme d'un fichier d'entrée exploitable par la machine à capacités vectorielle (9). 11. Système selon la revendication 10, caractérisé en ce qu'il comporte en outre des moyens (23) pour extraire en clair les données recherchées dans le fichier résultat obtenu en sortie de la machine à capacités vectorielle (9) à partir de moyens de recherche installés dans le serveur applicatif décisionnel (1). 12. Système selon l'une quelconque des revendications 10 et 11, caractérisé en ce qu'il comporte en outre, un agent d'administration (24) surveillant l'activité de la machine à capacités vectorielles, gérant les anomalies, et activant les moyens de recherche sur la machine à capacités vectorielles (9).