Québec Université Laval, Bibliothèque 2014

Ces dernières années ont vu un regain d’intérêt dans l’utilisation de données semi-structurées, grâce à la standardisation de formats d’échange de données sur le Web tels que XML et RDF. On notera en particulier le Linking Open Data Project qui comptait plus de 31 milliard de triplets RDF à la fin de l’année 2011. XML reste, pour sa part, l’un des formats de données privilégié de nombreuses bases de données de grandes tailles dont Uniprot, Open Government Initiative et Penn Treebank. <p><p>Cet accroissement du volume de données semi-structurées a suscité un intérêt croissant pour le développement de bases de données adaptées. Parmi les différentes approches proposées, on peut distinguer les approches relationnelles et les approches graphes, comme détaillé au Chapitre 3. Les premières visent à exploiter les moteurs de bases de données relationnelles existants, en y intégrant des techniques spécialisées. Les secondes voient les données semistructurées comme des graphes, c’est-à-dire un ensemble de noeuds liés entre eux par des arêtes étiquetées, dont elles exploitent la structure. L’une des techniques de ce domaine, connue sous le nom d’indexation structurelle, vise à résumer les graphes de données, de sorte à pouvoir identifier rapidement les données utiles au traitement d’une requête.<p><p>Les index structurels classiques sont construits sur base des notions de simulation et de bisimulation sur des graphes. Ces notions, qui sont d’usage dans de nombreux domaines tels que la vérification, la sécurité, et le stockage de données, sont des relations sur les noeuds des graphes. Fondamentalement, ces notions caractérisent le fait que deux noeuds partagent certaines caractéristiques telles qu’un même voisinage. <p><p>Bien que les approches graphes soient efficaces en pratique, elles présentent des limitations dans le cadre de RDF et son langage de requêtes SPARQL. Les étiquettes sont, dans cette optique, distinctes des noeuds du graphe .Dans le modèle décrit par RDF et supporté par SPARQL, les étiquettes et noeuds font néanmoins partie du même ensemble. C’est pourquoi, les approches graphes ne supportent qu’un sous-ensemble des requêtes SPARQL. Au contraire, les approches relationnelles sont fidèles au modèle RDF, et peuvent répondre au différentes requêtes SPARQL. <p><p>La question à laquelle nous souhaitons répondre dans cette thèse est de savoir si les approches relationnelles et graphes sont incompatible, ou s’il est possible de les combiner de manière avantageuse. En particulier, il serait souhaitable de pouvoir conserver la performance des approches graphe, et la généralité des approches relationnelles. Dans ce cadre, nous réalisons un index structurel adapté aux données relationnelles. <p><p>Nous nous basons sur une méthodologie décrite par Fletcher et ses coauteurs pour la conception d’index structurels. Cette méthodologie repose sur trois composants principaux. Un premier composant est une caractérisation dite structurelle du langage de requêtes à supporter. Il s’agit ici de pouvoir identifier les données qui sont retournées en même temps par n’importe quelle requête du langage aussi précisément que possible. Un second composant est un algorithme qui doit permettre de grouper efficacement les données qui sont retournées en même temps, d’après la caractérisation structurelle. Le troisième composant est l’index en tant que tel. Il s’agit d’une structure de données qui doit permettre d’identifier les groupes de données, générés par l’algorithme précédent pour répondre aux requêtes. <p><p>Dans un premier temps, il faut remarquer que le langage SPARQL pris dans sa totalité ne se prête pas à la réalisation d’index structurels efficaces. En effet, le fondement des requêtes SPARQL se situe dans l’expression de requêtes conjonctives. La caractérisation structurelle des requêtes conjonctives est connue, mais ne se prête pas à la construction d’algorithmes efficaces pour le groupement. Néanmoins, l’étude empirique des requêtes SPARQL posées en pratique que nous réalisons au Chapitre 5 montre que celles-ci sont principalement des requêtes conjonctives acycliques. Les requêtes conjonctives acycliques sont connues dans la littérature pour admettre des algorithmes d’évaluation efficaces. <p><p>Le premier composant de notre index structurel, introduit au Chapitre<p>6, est une caractérisation des requêtes conjonctives acycliques. Cette<p>caractérisation est faite en termes de guarded simulation. Pour les graphes la<p>notion de simulation est une version restreinte de la notion de bisimulation.<p>Similairement, nous introduisons la notion de guarded simulation comme une<p>restriction de la notion de guarded bisimulation, une extension connue de la<p>notion de bisimulation aux données relationelles. <p><p>Le Chapitre 7 offre un second composant de notre index structurel. Ce composant est une structure de données appelée guarded structural index qui supporte le traitement de requêtes conjonctives quelconques. Nous montrons que, couplé à la caractérisation structurelle précédente, cet index permet d’identifier de manière optimale les données utiles au traitement de requêtes conjonctives acycliques. <p><p>Le Chapitre 8 constitue le troisième composant de notre index structurel et propose des méthodes efficaces pour calculer la notion de guarded simulation. Notre algorithme consiste essentiellement en une transformation d’une base de données en un graphe particulier, sur lequel les notions de simulation et guarded simulation correspondent. Il devient alors possible de réutiliser les algorithmes existants pour calculer des relations de simulation. <p><p>Si les chapitres précédents définissent une base nécessaire pour un index structurel visant les données relationnelles, ils n’intègrent pas encore cet index dans le contexte d’un moteur de bases de données relationnelles. C’est ce que propose le Chapitre 9, en développant des méthodes qui permettent de prendre en compte l’index durant le traitement d’une requête SPARQL. Des résultats expérimentaux probants complètent cette étude. <p><p>Ce travail apporte donc une première réponse positive à la question de savoir s’il est possible de combiner de manière avantageuse les approches relationnelles et graphes de stockage de données RDF.<p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Nous nous intéressons au développement de méthodes qui répondent aux difficultés posées par l’analyse des séries temporelles. Nos contributions se focalisent sur deux tâches : la prédiction de séries temporelles et la classification de séries temporelles. Notre première contribution présente une méthode de prédiction et de complétion de séries temporelles multivariées et relationnelles. Le but est d’être capable de prédire simultanément l’évolution d’un ensemble de séries temporelles reliées entre elles selon un graphe, ainsi que de compléter les valeurs manquantes dans ces séries (pouvant correspondre par exemple à une panne d’un capteur pendant un intervalle de temps donné). On se propose d’utiliser des techniques d’apprentissage de représentation pour prédire l’évolution des séries considérées tout en complétant les valeurs manquantes et prenant en compte les relations qu’il peut exister entre elles. Des extensions de ce modèle sont proposées et décrites : d’abord dans le cadre de la prédiction de séries temporelles hétérogènes puis dans le cas de la prédiction de séries temporelles avec une incertitude exprimée. Un modèle de prédiction de séries spatio-temporelles est ensuiteproposé, avec lequel les relations entre les différentes séries peuvent être exprimées de manière plus générale, et où ces dernières peuvent être apprises.Enfin, nous nous intéressons à la classification de séries temporelles. Un modèle d’apprentissage joint de métrique et de classification de séries est proposé et une comparaison expérimentale est menée. / This thesis deals with the development of time series analysis methods. Our contributions focus on two tasks: time series forecasting and classification. Our first contribution presents a method of prediction and completion of multivariate and relational time series. The aim is to be able to simultaneously predict the evolution of a group of time series connected to each other according to a graph, as well as to complete the missing values ​​in these series (which may correspond for example to a failure of a sensor during a given time interval). We propose to use representation learning techniques to forecast the evolution of the series while completing the missing values ​​and taking into account the relationships that may exist between them. Extensions of this model are proposed and described: first in the context of the prediction of heterogeneous time series and then in the case of the prediction of time series with an expressed uncertainty. A prediction model of spatio-temporal series is then proposed, in which the relations between the different series can be expressed more generally, and where these can be learned.Finally, we are interested in the classification of time series. A joint model of metric learning and time-series classification is proposed and an experimental comparison is conducted.

Cette thèse présente un modèle de base de données relationnel étendu : SHIVA, conçu pour permettre la mise en ouvre de bases de connaissances centrées objets. Le modèle SHIVA a été développé dans le cadre du projet SHIRKA : des bases de connaissances centrées objets et, un interpréteur de ce modèle sera utilisé pour écrire le système de gestion de bases de connaissances du système SHIRKA.<br /><br />Le premier chapitre est une description du système SHIRKA et de la représentation des connaissances centrée objets. Dans le deuxième chapitre, les principales extensions du mode relationnel sont exposées. Enfin, le troisième chapitre est consacré au modèle SHIVA.

Présentation d'une telle interface (IMREL) permettant la transformation des structures de base de données hiérarchiques (IMAGE) afin de la consulter de manière relationnelle. Proposition d'une stratégie d'optimisation de requête par la recherche du chemin de cout minimal. Réalisation d'un compilateur de requête (CORREL).

Cette thèse présente le sous-système ISIS, une méthode d'expression et de contrôle de l'intégrité sémantique, dans les bases de données relationnelles. Celle-ci est réglée par un ensemble de lois appelées contraintes d'intégrité sémantique (CIS). Une réalisation est effectuée dans le cadre du projet MICROBE

Les utilisateurs des bases de données doivent faire face au problème de surcharge d'information lors de l'interrogation de leurs données, qui se traduit par un nombre de réponses trop élevé à des requêtes exploratoires. Pour remédier à ce problème, nous proposons un algorithme efficace et rapide, ap- pelé ESRA (Explore-Select-Rearrange Algorithm), qui utilise les résumés SAINTETIQ pré-calculés sur l'ensemble des données pour regrouper les réponses à une requête utilisateur en un ensemble de classes (ou résumés) organisées hiérarchiquement. Chaque classe décrit un sous-ensemble de résul- tats dont les propriétés sont voisines. L'utilisateur pourra ainsi explorer la hiérarchie pour localiser les données qui l'intéressent et en écarter les autres. Les résultats expérimentaux montrent que l'al- gorithme ESRA est efficace et fournit des classes bien formées (i.e., leur nombre reste faible et elles sont bien séparées). Cependant, le modèle SAINTETIQ, utilisé par l'algorithme ESRA, exige que les données soient disponibles sur le serveur des résumés. Cette hypothèse rend inapplicable l'algo- rithme ESRA dans des environnements distribués où il est souvent impossible ou peu souhaitable de rassembler toutes les données sur un même site. Pour remédier à ce problème, nous proposons une collection d'algorithmes qui combinent deux résumés générés localement et de manière autonome sur deux sites distincts pour en produire un seul résumant l'ensemble des données distribuées, sans accéder aux données d'origine. Les résultats expérimentaux montrent que ces algorithmes sont aussi performants que l'approche centralisée (i.e., SAINTETIQ appliqué aux données après regroupement sur un même site) et produisent des hiérarchies très semblables en structure et en qualité à celles produites par l'approche centralisée.

De nos jours, les applications informatiques autonomes sont au centre de grandes préoccupations de la recherche scientifique. Ces dernières sont destinées initialement à des systèmes d'aide à la décision dans des environnements contraints et dynamiques, communément appelés environnements complexes. Elles peuvent dès à présent, à l'aide des avancées de la recherche, permettre de construire et déduire leurs connaissances propres afin d'interagir en temps réel avec leur environnement. Cependant, elles sont confrontées à la difficulté d'avoir une modélisation fidèle du monde réel et des entités qui le composent. L'un des principaux objectifs de nos recherches est de capturer et modéliser la sémantique associée aux entités spatio-temporelles afin d'enrichir leur expressivité dans les SIG ou les systèmes d'aide à la décision. Un service de routage maritime dynamique a été déployé en exploitant cette modélisation. Cet algorithme a été démontré comme optimal en termes d'espace mémoire et de temps de calcul. La sémantique capturée se compose de l'affordance et de la saillance visuelle de l'entité spatiale. Les connaissances associées à cette sémantique sont par la suite représentées par une ontologie computationnelle qui intègre des approches spatio-temporelles. Ces connaissances sont soit déduites du savoir de l'expert du domaine, soit extraites de gros volumes de données textuelles en utilisant des techniques de traitement automatique du langage. L'ontologie computationnelle proposée nous a permis de définir un algorithme de routage maritime dynamique (fonction des évènements ou objets présents dans l'environnement) fondé sur une heuristique itérative monocritère de plus courte distance et bidirectionnelle. L'algorithme BIDA* proposé s'applique sur un graphe itératif qui est une conceptualisation d'une grille hexagonale itérative recouvrant la zone de navigation. Cet algorithme permet aussi la gestion de différents niveaux de résolution. Toujours dans l'initiative de produire un modèle aussi proche que possible du monde réel, l'algorithme BIDA* a été enrichi des stratégies multicritères afin de prendre en compte les différentes contraintes de la navigation maritime. Les contraintes globales et locales auxquelles nous nous sommes intéressés sont la profondeur des eaux, la distance de navigation et la direction de navigation. Le modèle proposé permet ainsi d'enrichir les capacités cognitives des utilisateurs évoluant dans les environnements maritimes et peut aussi être utilisé pour construire des systèmes complètement autonomes explorant ces environnements. Un prototype expérimental de navigation intelligente mettant en oeuvre cette modélisation et proposant un service de routage maritime a été développé dans le cadre de cette thèse. / No

Pour pallier le manque de connaissances sur la biogéographie des diatomées nordiques, le recueil d'un maximum d'informations est encouragé. Rassembler les données paléolimnologiques régionales permet d'effectuer des analyses écologiques et environnementales dans un contexte géographique plus large. La Circumpolar Diatom Database (CDD), un projet initié en 1997 par le Laboratoire de Paléoécologie Aquatique (LPA), tente de répondre à ces besoins. Toutefois, cette première version de la CDD comporte certaines lacunes, dont l'insertion de données de type « Z » (niveau de carottage) et l'implantation dans un système d'information géographique (SIG). L'objectif principal de cette étude est de développer une nouvelle structure de base de données relationnelle particulièrement adaptée aux données paléolimnologiques favorisant l'archivage, la consultation et la représentation cartographique des données à l'échelle circumpolaire. En second lieu, ce projet vise à tester le potentiel d'implantation de la CDD dans un SIG et d'entrevoir sa diffusion au sein de la communauté scientifique. Les étapes méthodologiques de développement d'un système d'information ont mené à la création d'un modèle de base de données relationnel composé par langage SQL. Une liste de références taxonomiques a été réalisée par l'unification de plusieurs listes existantes. Une interface utilisateur a été développée sous forme de formulaires MS Access facilitant la consultation des résultats. L'utilisation de la CDD a été testée dans ArcGIS par une connexion OLE DB et par conversion en « Personal Geodatabase ». La collecte de données a permis de tripler le volume d'informations de la nouvelle CDD. Elle renferme maintenant quelque 572 sites d'échantillonnage, 39 350 données d'occurrence et 15 000 données limnologiques. Sa couverture s'étale sur huit régions circumpolaires arctiques réparties sur trois continents : Amérique du Nord, Europe et Asie. Jusqu'à maintenant, la couverture spatiale de la CDD permet difficilement d'effectuer des analyses sur une vaste échelle. Il est donc primordial d'encourager la communauté paléolimnologique à contribuer davantage au projet. Ce projet a généré un système d'information exploitable, et les phases d'implantation et de distribution pourront être entreprises en fonction de l'avenir souhaité pour la CDD et des ressources disponibles.

Avec l’avènement du cloud computing et des big data, de nouveaux systèmes de gestion de bases de données sont apparus, connus en général sous le vocable systèmes NoSQL. Par rapport aux systèmes relationnels, ces systèmes se distinguent par leur absence de schéma, une spécialisation pour des types de données particuliers (documents, graphes, clé/valeur et colonne) et l’absence de langages de requêtes déclaratifs. L’offre est assez pléthorique et il n’y a pas de standard aujourd’hui comme peut l’être SQL pour les systèmes relationnels. De nombreuses applications peuvent avoir besoin de manipuler en même temps des données stockées dans des systèmes relationnels et dans des systèmes NoSQL. Le programmeur doit alors gérer deux (au moins) modèles de données différents et deux (au moins) langages de requêtes différents pour pouvoir écrire son application. De plus, il doit gérer explicitement tout son cycle de vie. En effet, il a à (1) coder son application, (2) découvrir les services de base de données déployés dans chaque environnement Cloud et choisir son environnement de déploiement, (3) déployer son application, (4) exécuter des requêtes multi-sources en les programmant explicitement dans son application, et enfin le cas échéant (5) migrer son application d’un environnement Cloud à un autre. Toutes ces tâches sont lourdes et fastidieuses et le programmeur risque d’être perdu dans ce haut niveau d’hétérogénéité. Afin de pallier ces problèmes et aider le programmeur tout au long du cycle de vie des applications utilisant des bases de données multiples, nous proposons un ensemble cohérent de modèles, d’algorithmes et d’outils. En effet, notre travail dans ce manuscrit de thèse se présente sous forme de quatre contributions. Tout d’abord, nous proposons un modèle de données unifié pour couvrir l’hétérogénéité entre les modèles de données relationnelles et NoSQL. Ce modèle de données est enrichi avec un ensemble de règles de raffinement. En se basant sur ce modèle, nous avons défini notre algèbre de requêtes. Ensuite, nous proposons une interface de programmation appelée ODBAPI basée sur notre modèle de données unifié, qui nous permet de manipuler de manière uniforme n’importe quelle source de données qu’elle soit relationnelle ou NoSQL. ODBAPI permet de programmer des applications indépendamment des bases de données utilisées et d’exprimer des requêtes simples et complexes multi-sources. Puis, nous définissons la notion de bases de données virtuelles qui interviennent comme des médiateurs et interagissent avec les bases de données intégrées via ODBAPI. Ce dernier joue alors le rôle d’adaptateur. Les bases de données virtuelles assurent l’exécution des requêtes d’une façon optimale grâce à un modèle de coût et un algorithme de génération de plan d’exécution optimal que nous définis. Enfin, nous proposons une approche automatique de découverte de bases de données dans des environnements Cloud. En effet, les programmeurs peuvent décrire leurs exigences en termes de bases de données dans des manifestes, et grâce à notre algorithme d’appariement, nous sélectionnons l’environnement le plus adéquat à notre application pour la déployer. Ainsi, nous déployons l’application en utilisant une API générique de déploiement appelée COAPS. Nous avons étendue cette dernière pour pouvoir déployer les applications utilisant plusieurs sources de données. Un prototype de la solution proposée a été développé et mis en œuvre dans des cas d'utilisation du projet OpenPaaS. Nous avons également effectué diverses expériences pour tester l'efficacité et la précision de nos contributions / The production of huge amount of data and the emergence of Cloud computing have introduced new requirements for data management. Many applications need to interact with several heterogeneous data stores depending on the type of data they have to manage: traditional data types, documents, graph data from social networks, simple key-value data, etc. Interacting with heterogeneous data models via different APIs, and multiple data stores based applications imposes challenging tasks to their developers. Indeed, programmers have to be familiar with different APIs. In addition, the execution of complex queries over heterogeneous data models cannot, currently, be achieved in a declarative way as it is used to be with mono-data store application, and therefore requires extra implementation efforts. Moreover, developers need to master and deal with the complex processes of Cloud discovery, and application deployment and execution. In this manuscript, we propose an integrated set of models, algorithms and tools aiming at alleviating developers task for developing, deploying and migrating multiple data stores applications in cloud environments. Our approach focuses mainly on three points. First, we provide a unified data model used by applications developers to interact with heterogeneous relational and NoSQL data stores. This model is enriched by a set of refinement rules. Based on that, we define our query algebra. Developers express queries using OPEN-PaaS-DataBase API (ODBAPI), a unique REST API allowing programmers to write their applications code independently of the target data stores. Second, we propose virtual data stores, which act as a mediator and interact with integrated data stores wrapped by ODBAPI. This run-time component supports the execution of single and complex queries over heterogeneous data stores. It implements a cost model to optimally execute queries and a dynamic programming based algorithm to generate an optimal query execution plan. Finally, we present a declarative approach that enables to lighten the burden of the tedious and non-standard tasks of (1) discovering relevant Cloud environments and (2) deploying applications on them while letting developers to simply focus on specifying their storage and computing requirements. A prototype of the proposed solution has been developed and implemented use cases from the OpenPaaS project. We also performed different experiments to test the efficiency and accuracy of our proposals