.

Présentation du système POLYPHEME-MOGADOR : un modèle pour la conception de bases de données reparties. Points de vue utilisateur pour la définition et la manipulation d'une bases de données reparties. Le problème de décomposition. Spécifications de réalisation.

L'accroissement rapide de la puissance des calculateurs actuels et leur interconnexion en grappes et grilles de calcul à l'aide de réseaux rapides, permettent d'envisager, en mode de production, l'utilisation de plusieurs codes de calculs numériques couplés pour la simulation de phénomènes physiques plus complexes. Dans le but d'obtenir des résultats toujours plus précis, un nouveau type de simulation numérique, dont l'objectif est de simuler plusieurs<br />physiques en même temps, est apparu. Ce type d'application est appelé "couplage de code". En effet, plusieurs codes (physiques) sont couplés ou interconnectés an qu'ils communiquent pour réaliser la simulation.<br />Cette thèse s'intéresse aux problématiques liées au couplage à hautes performances de codes parallèles et distribués. L'obtention des performances repose sur la conception d'applications distribuées dont certains composants sont parallélisés et dont les communications sont efcaces. L'idée de bas de cette thèse est d'utiliser un langage de programmation parallèle orienté flot de données (ici Athapascan) dans deux modèles de conception d'applications distribuées ; "modèle appel de procédure à distance (RPC)" et "modèle orienté flux de données (stream-oriented)". Les contributions apportées par ce travail de recherche sont les suivants :<br /><br />- Utilisation d'un langage de flot de données dans un grille RPC de calcul ;<br />Dans le cadre de projet HOMA, les extensions au modèle RPC ont porté d'une part sur la sémantique de contrôle et de communication et d'autre part sur les supports exécutifs pour mieux exploiter le parallélisme. Les résultats théoriques de ces extensions pour une implantation sur le bus logiciel CORBA à l'aide du moteur exécutif KAAPI d'Athapascan et pour l'architecture homogène comme grappe de PC, sont présentés sous la forme d'un modèle de coût d'exécution. Les expériences (élémentaires et sur une application réelle) ont validé ce modèle de coût.<br /><br />- Extension d'un modèle mémoire partagée pour couplage de codes ;<br />An d'étendre la sémantique d'accès aux données partagées du langage Athapascan, nous avons proposé la notion de "collection temporelle". Ce concept permet de décrire la sémantique d'accès de type flux de données. La "collection spatiale" permet de mieux exploiter les données parallèles. Pour préciser la sémantique associée à ces nouvelles notions, nous avons donné une nouvelle définition pour la donnée partagée. Puis dans le cadre de cette définition, nous avons défini trois types de données partagées ; "séquentielle", "collection temporelle" et "collection spatiale".

Ce manuscrit présente certains de mes travaux de recherche en matière de gestion de données, réalisés au sein de l'équipe bases de données STORM du laboratoire Logiciels, Systèmes, Réseaux de l'IMAG. Ils ont été effectués depuis 1995 (et jusqu'à 2003), année de ma prise de fonctions en tant que Maître de Conférences à l'Institut National Polytechnique (INP) de Grenoble, en poste à l'Ecole Nationale Supérieure d'Informatique et de Mathématiques Appliquées de Grenoble(ENSIMAG). Mes travaux concernent des aspects système --- gestion de cache et duplication de données, support transactionnels, parmi d'autres. Ils contribuent d'une part à l'extension des fonctions des SGBD et d'autre part à la conception de services séparés utilisables indépendamment d'un SGBD. Mon point de vue porte sur la diversification du panorama des architectures des systèmes de gestion de données. J'ai d'abord travaillé dans l'introduction de fonctions déductives et actives dans les SGBD pour ensuite m'orienter vers des solutions plus ouvertes, des intergiciels de gestion de données distribuées sur des unités fixes et mobiles.

Les données temporelles sont fréquemment manipulées dans plusieurs domaines d'application (bancaire, clinique, géographique, etc.). Malgré la diversité des techniques proposées pour visualiser ce type de données, nous constatons un manque d'approches et de méthodes de conception. Dans cette thèse, nous proposons une approche de conception de techniques de visualisation et plus généralement d'interaction avec des espaces de données temporelles. Pour garantir l'utilisabilité de ces techniques, nous proposons de prendre en compte les caractéristiques des données manipulées et les tâches utilisateur, nous situant ainsi à la jonction de deux domaines de l'informatique : les Bases de Données et les Interfaces Homme-Machine. Ce travail contribue donc à la conception de systèmes interactifs pour l'analyse visuelle de données temporelles. Dans ce contexte, nous proposons une taxonomie qui organise les travaux existants de visualisation de données temporelles selon leur processus de visualisation. Cette taxonomie est construite à partir du processus de visualisation proposé par Chi. En collaboration avec des utilisateurs géographes, nous avons identifié une liste de tâches utilisateur pertinentes pour la manipulation de données temporelles. A partir de cette liste, nous avons conçu et implémenté cinq techniques d'interaction adaptées aux tâches identifiées. Nous avons intégré ces techniques pour développer INVEST (Interactive Visualization and Explorative System of Temporal data) qui est une plate-forme multi-techniques pour l'analyse visuelle de données temporelles. Chaque technique de visualisation est une vue du même espace de données. INVEST inclut un moteur de sélection de techniques de visualisation en fonction des tâches utilisateur spécifiées.

Les communautés en ligne pair-a-pair (P2P), comme les communautés professionnelles (p. ex., médicales ou de recherche) deviennent de plus en plus populaires a cause de l'augmentation des besoins du partage de données. Alors que les environnements P2P offrent des caractéristiques intéressantes (p. ex., passage a l'échelle, disponibilité, dynamicité), leurs garanties en termes de protection des données sensibles sont limitées. Ils peuvent être considérés comme hostiles car les données publiées peuvent être consultées par tous les pairs (potentiellement malicieux) et utilisées pour tout (p. ex., pour le commerce illicite ou tout simplement pour des activités contre les préférences personnelles ou éthiques du propriétaire des données). Cette thèse propose un service qui permet le partage de données sensibles dans les systèmes P2P, tout en assurant leur confidentialité. La première contribution est l'analyse des techniques existant pour la confidentialité de données dans les architectures P2P. La deuxième contribution est un modèle de confidentialité, nommé PriMod, qui permet aux propriétaires de données de spécifier leurs préférences de confidentialité dans de politiques de confidentialité et d'attacher ces politiques a leurs données sensibles. La troisième contribution est le développement de PriServ, un service de confidentialité, basé sur une DHT qui met en oeuvre PriMod afin de prévenir la violation de la confidentialité de données. Entre autres, PriServ utilise de techniques de confiance pour prédire le comportement des pairs.

La phase de préparation du processus de fouille des données est critique pour la qualité des résultats et consomme typiquement de l'ordre de 80% d'une étude. Dans cette thèse, nous nous intéressons à l'évaluation automatique d'une représentation, en vue de l'automatisation de la préparation des données. A cette fin, nous introduisons une famille de modèles non paramétriques pour l'estimation de densité, baptisés modèles en grille. Chaque variable étant partitionnée en intervalles ou groupes de valeurs selon sa nature numérique ou catégorielle, l'espace complet des données est partitionné en une grille de cellules résultant du produit cartésien de ces partitions univariées. On recherche alors un modèle où l'estimation de densité est constante sur chaque cellule de la grille. Du fait de leur très grande expressivité, les modèles en grille sont difficiles à régulariser et à optimiser. Nous avons exploité une technique de sélection de modèles selon une approche Bayesienne et abouti à une évaluation analytique de la probabilité a posteriori des modèles. Nous avons introduit des algorithmes d'optimisation combinatoire exploitant les propriétés de notre critère d'évaluation et la faible densité des données en grandes dimensions. Ces algorithmes ont une complexité algorithmique garantie, super-linéaire en nombre d'individus. Nous avons évalué les modèles en grilles dans de nombreux contexte de l'analyse de données, pour la classification supervisée, la régression, le clustering ou le coclustering. Les résultats démontrent la validité de l'approche, qui permet automatiquement et efficacement de détecter des informations fines et fiables utiles en préparation des données.

Les domaines de la médecine, du web, du commerce ou de la nance génèrent et stockent de grandes masses d'information sous la forme de séquences d'événements. Ces archives représentent des sources d'information très riches pour des analystes avides d'y découvrir des perles de connaissance. Par exemple, les biologistes cherchent à découvrir les facteurs de risque d'une maladie en analysant l'historique des patients, les producteurs de contenu web et les bureaux de marketing examinent les habitudes de consommation des clients et les opérateurs boursiers suivent les évolutions du marché pour mieux l'anticiper. Cependant, ces applications requièrent l'exploration de séquences d'événements très volumineuses, par exemple, la nance génère quotidiennement des millions d'événements, où les événements peuvent être décrits par des termes extraits de riches contenus textuels. La variabilité des descripteurs peut alors être très grande. De ce fait, découvrir des connaissances non triviales à l'aide d'approches classiques de fouille de données dans ces sources d'information prolixes est un problème dicile. Une étude récente montre que les approches classiques de fouille de données peuvent tirer prot de formes condensées de ces données, telles que des résultats d'agrégation ou encore des résumés. La connaissance ainsi extraite est qualiée de connaissance d'ordre supérieur. À partir de ce constat, nous présentons dans ces travaux le concept de résumé de séquence d'événements dont le but est d'amener les applications dépendantes du temps à gagner un facteur d'échelle sur de grandes masses de données. Un résumé s'obtient en transformant une séquence d'événements où les événements sont ordonnés chronologiquement. Chaque événement est précisément décrit par un ensemble ni de descripteurs symboliques. Le résumé produit est alors une séquence d'événements, plus concise que la séquence initiale, et pouvant s'y substituer dans les applications. Nous proposons une première méthode de construction guidée par l'utilisateur, appelée TSaR. Il s'agit d'un processus en trois phases : i) une généralisation, ii) un regroupement et iii) une formation de concepts. TSaR utilise des connaissances de domaine exprimées sous forme de taxonomies pour généraliser les descripteurs d'événements. Une fenêtre temporelle est donnée pour contrôler le processus de regroupement selon la proximité temporelle des événements. Dans un second temps, pour rendre le processus de résumé autonome, c'est- à-dire sans paramétrage, nous proposons une redénition du problème de résumé en un nouveau problème de classication. L'originalité de ce problème de classication tient au fait que la fonction objective à optimiser dépend simultanément du contenu des événements et de leur proximité dans le temps. Nous proposons deux algorithmes gloutons appelés G-BUSS et GRASS pour répondre à ce problème. Enn, nous explorons et analysons l'aptitude des résumés de séquences d'événements à contribuer à l'extraction de motifs séquentiels d'ordre supérieur. Nous analysons les caractéristiques des motifs fréquents extraits des résumés et proposons une méthodologie qui s'appuie sur ces motifs pour en découvrir d'autres, à granularité plus ne. Nous évaluons et validons nos approches de résumé et notre méthodologie par un ensemble d'expériences sur un jeu de données réelles extraites des archives d'actualités nancières produites par Reuters.

Dans une base de données répartie, la réplication de données peut servir à augmenter la fiabilité et la disponibilité de données ainsi que les performances d'accès. En général, l'unité de réplication (copie ou replique) est un table relationnelle (ou un fragment), un document ou un fichier. La réplication consiste alors en placer plusieurs copies sur différents noeuds distincts. Cela fournit une grande disponibilité de données. Si un noeud devient non opérationnel à la suite d'une panne par exemple, une autre copie est toujours accessible sur un autre noeud. La réplication permet aussi aussi de améliorer les performances d'accès en augmentant la localité des références. Lorsque le coût de communication est un facteur dominant, le placement d'une copie sur le noeud où il est le plus souvent accédé favorise les accès locaux et évite l'accès au réseau. Les avantages apportés par la réplication sont à comparer avec la complexité et les coûts supplémentaires de maintenance des copies qui doivent, en théorie rester identiques à tout moment. La mise à jour d'une copie doit être répercutée automatiquement sur toutes ses repliques. Le problème est compliqué par la présence de pannes de noeud ou réseau. Le compromis recherché entre performance d'accès en consultation et en mise à jour des données rend difficile le choix du niveau de réplication. Celui-ci est très dépendant de la charge de travail demandée par les applications. Face à ces défis dans mes travaux de recherche nous avons focalisé sur la gestion de la cohérence pour réplication asynchrone pour plusieurs contextes : entrepôts de données, grappes et applications collaboratives et en pair à pair (P2P). 1. Entrepôts de Données Dans les architectures proposes pour la gestion de entrepôts de données les configurations mono- maître sont souvent utilisés. Dans la réplication mono-maître, plusieurs types configurations acycliques dirigés sont possibles: diffusion, mono-consolidation multi-consolidation, triangulaire. La gestion de la cohérence se pose surtout pour certaines configurations comme dans la multi-consolidation et triangulaire et ses généralisations en combinant les configurations de base. 2. Grappes Les applications dans lesquelles sont utilisées les grappes sont typiquement des applications de lectures intensives, ce qui rend plus facile l'exploitation du parallélisme. Cependant, les grappes peuvent également être utilisées dans un nouveau modèle économique, les Fournisseurs de Services d'Applicatons ASP - Application Service Providers. Dans un contexte ASP, les applications et les bases de données des clients sont stockées chez le fournisseur et sont disponibles, typiquement depuis Internet, aussi efficacement que si elles étaient locales pour les clients. Pour améliorer les performances, les applications et les données peuvent être répliquées sur plusieurs noeuds. Ainsi, les clients peuvent être servis par n'importe quel noeud en fonction de la charge. Cet arrangement fournit également une haute disponibilité: dans le cas de la panne d'un noeud, d'autres noeuds peuvent effectuer le même travail. Le défie est de gérer la réplication multimaître totale et partiel en assurant la cohérence forte et toute en passant à l'échelle. 3 Applications Collaboratives en P2P Les systèmes P2P adoptent une approche complètement décentralisée au partage des ressources. En distribuant données et traitements sur tous les pairs du réseau, ils peuvent passer à très grande échelle sans recourir à des serveurs très puissants. La réplication de données dans les systèmes P2P devient un enjeu majeur pour les applications collaboratives, comme les forums de discussion, les calendriers partagés, ou les catalogues e-commerce, etc. En effet, les données partagées doivent pouvoir être mises à jour en parallèle par différents pairs. Les premiers systèmes P2P existants supposent que les données sont statiques et n'intègrent aucun mécanisme de gestion des mises à jour et de réplication. Une mise à jour d'une donnée par le pair qui la possède implique une nouvelle version non propagée à ceux répliquant cette donnée. Cela résulte en diverses versions sous le même identifiant et l'utilisateur accède à celle stockée par le pair qu'il contacte. Aucune forme de cohérence entre les répliques n'est alors garantie. Le défi est gérer la cohérence éventuelle face au dynamisme des pairs tout en passant à l'échelle.

One of the main current research activities in Software engineering is concerned about modelling the development process of huge softwares in order to bring some help to the engineer to design and maintain an application. In general, every design process is seen as rational application of transformation operators to one or more products (mainly specifications) in order to produce new products that satisfy to some given criteria. This modelling mainly allows a methodological guidance. Indeed, at each step of the process, the set of pertinent activities and types of products are proposed to the designer, without any other. This guidance may possibly be reinforced with some help. Furthermore, this modelling allows to document the process with its history, ie with a representation of performed actvities. This history is itself the basis of maintenance activities. Two examples : a Replay function that allows, during a modification, to do (automatically or assisted) the same activities as during the design, and Reverse Engineering that allows to recover not only some technical and functional documentation of an application, but also a plausible history of its design. The thesis aims at elaborating a general model of design processes, applying it to database engineering and implementing it in the DB-MAIN CASE tool. It will be done in four phases : 1. elaboration of a model, a method specification language and a history representation 2. evaluation of this model with the specification of classical methods and case studies 3. methodological recommandation proposals for the elaboration of design methods 4. development and integration of some methodological control functions in the DB-MAIN CASE tool; this includes an extension of the repository, the definition of the interface of the methodological functions, the development of the methodological engine and the development of an history processor (analysis, replay,...)./Un des principaux sujets de recherche actuels dans le monde de l'ingénierie logicielle concerne la modélisation des processus de développement de grosses applications afin d'apporter de l'aide aux ingénieurs pour concevoir et maintenir leurs applications. En général, un processus de conception est vu comme l'application rationnelle d'opérateurs de transformation à un ou plusieurs produits (généralement des spécifications) pour obtenir de nouveaux produits qui satisfont une série de critères donnés. Cette modélisation permet principalement une aide méthodologique: à chaque étape du processus, seul l'ensemble des outils pertinents est mis à disposition du concepteur. Ce guidage peut être renforcé par des messages d'aide. Cette aide s'étend l'enregistrement de l'historique du processus, c'est-à-dire d'une représentation des actions entreprises. Cet historique peut lui-même être à la base d'activités de maintenance. Deux exemples: une fonction qui permet de rejouer, lors d'une modification, de manière automatique ou assistée, les mêmes actions que pendant la conception, et la rétro-ingénierie qui permet de recouvrer non seulement la documentation technique et fonctionnelle d'une application, mais aussi un historique plausible de la conception originelle. La thèse s'attache à élaborer un modèle général de processus de conception, à l'appliquer au monde des bases de données et à l'implémenter dans l'AGL DB-MAIN. Cela, en 4 phases: 1. Élaboration d'un modèle, d'un langage de spécification (MDL) et d'une représentation des historiques 2. Évaluation de ce modèle avec des méthodes de spécification classiques et études de cas 3. Propositions de recommandations méthodologiques pour l'élaboration de méthodes d'ingénierie 4. Développement et intégration de fonctions de contrôle méthodologique dans l'atelier DB-MAIN; ceci inclut l'extension du référentiel, la définition de l'interface homme-machine des fonctions méthodologiques et le développement du moteur méthodologique.