Contrairement aux données traditionnelles, les données semi-structurées sont irrégulières : des données peuvent manquer, des concepts similaires peuvent être représentés par différents types de données, et les structures même peuvent être mal connues. Cette absence de schéma prédéfini, permettant de tenir compte de toutes les données du monde extérieur, présente l'inconvénient de complexifier les algorithmes d'intégration des données de différentes sources. Nous proposons une architecture de médiation basée entièrement sur XML. L'objectif de cette architecture de médiation est de fédérer des sources de données distribuées de différents types. Elle s'appuie sur le langage XQuery, un langage fonctionnel conçu pour formuler des requêtes sur des documents XML. Le médiateur analyse les requêtes exprimées en XQuery et répartit l'exécution de la requête sur les différentes sources avant de recomposer les résultats. L'évaluation des requêtes doit se faire en exploitant au maximum les spécificités des données et permettre une optimisation efficace. Nous décrivons l'algèbre XAlgebre à base d'opérateurs conçus pour XML. Cette algèbre a pour but de construire des plans d'exécution pour l'évaluation de requêtes XQuery et traiter des tuples d'arbres XML. Ces plans d'exécution doivent pouvoir être modélisés par un modèle de coût et celui de coût minimum sera sélectionné pour l'exécution. Dans cette thèse, nous définissons un modèle de coût pour les données semi-structurées adapté à notre algèbre. Les sources de données (SGBD, serveurs Web, moteur de recherche) peuvent être très hétérogènes, elles peuvent avoir des capacités de traitement de données très différentes, mais aussi avoir des modèles de coût plus ou moins définis. Pour intégrer ces différentes informations dans l'architecture de médiation, nous devons déterminer comment communiquer ces informations entre le médiateur et les sources, et comment les intégrer. Pour cela, nous utilisons des langages basés sur XML comme XML-Schema et MathML pour exporter les informations de métadonnées, de formules de coûts et de capacité de sources. Ces informations exportées sont communiquées par l'intermédiaire d'une interface applicative nommée XML/DBC. Enfin, des optimisations diverses spécifiques à l'architecture de médiation doivent être considérées. Nous introduisons pour cela un cache sémantique basé sur un prototype de SGBD stockant efficacement des données XML en natif.

Vues de sécurité xml : requêtes, mises à jour, et schémas. Les évolutions technologiques ont consacré l'émergence des services web et du stockage des données en ligne, en complément des bases de données traditionnelles. Ces évolutions facilitent l'accès aux données, mais en contrepartie soulèvent de nouvelles problématiques de sécurité. La mise en œuvre de politiques de contrôle d'accès appropriées est une des approches permettant de réduire ces risques.Nous étudions ici les politiques de contrôle d'accès au niveau d'un document XML, politiques que nous modélisons par des vues de sécurité XML (non matérialisées) à l'instar de Fan et al. Ces vues peuvent être représentées facilement par des alignements d'arbres grâce à l'absence d'opérateurs arithmétiques ou de restructuration. Notre objectif est par conséquent d'examiner comment manipuler efficacement ce type de vues, à l'aide des méthodes formelles, et plus particulièrement des techniques de réécriture de requêtes et la théorie des automates d'arbres. Trois directions principales ont orienté nos recherches: nous avons tout d'abord élaboré des algorithmes pour évaluer l'expressivité d'une vue, en fonction des requêtes qui peuvent être exprimées à travers cette vue. Il s'avère que l'on ne peut décider en général si une vue permet d'exprimer une requête particulière, mais cela devient possible lorsque la vue satisfait des hypothèses générales. En second lieu, nous avons considéré les problèmes soulevés par la mises à jour du document à travers une vue. Enfin, nous proposons des solutions pour construire automatiquement un schéma de la vue. En particulier, nous présentons différentes techniques pour représenter de façon approchée l'ensemble des documents au moyen d'une DTD.

Ces travaux portent sur l'étude de la complexité en requêtes de <br />problèmes symétriques, dans les cadres du calcul probabiliste classique <br />et du calcul quantique.<br /><br />Il est montré, dans le cas quantique, une application de la méthode de <br />bornes inférieures dite "polynomiale" au calcul de la complexité en <br />requêtes des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation".<br /><br />Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie <br />transitive" des problèmes, il est donné une formule combinatoire <br />permettant de calculer la complexité en requêtes exacte du meilleur <br />algorithme non-adaptatif. De plus, il est mis en évidence que sous <br />certaines hypothèses de symétrie, ce meilleur algorithme non-adaptatif <br />est optimal même parmi les algorithmes probabilistes plus généraux, ce qui donne pour la classe de problèmes correspondante une expression exacte de la complexité en requêtes.

Dans cette thèse, nous nous intéressons à des problèmes à la croisée de deux domaines, les bases de données et les bases de connaissances. Nous considérons deux problèmes équivalents concernant les requêtes conjonctives avec négation : l'inclusion de requêtes et l'évaluation d'une requête booléenne sous l'hypothèse du monde ouvert. Nous reformulons ces problèmes sous la forme d'un problème de déduction dans un fragment de la logique du premier ordre. Puis nous raffinons des schémas d'algorithmes déjà existants et proposons de nouveaux algorithmes. Pour les étudier et les comparer expérimentalement, nous proposons un générateur aléatoire et analysons l'influence des différents paramètres sur la difficulté des instances du problème étudié. Finalement, à l'aide de cette méthodologie expérimentale, nous comparons les apports des différents raffinements et les algorithmes entre eux.

Ces deux dernières décennies les systèmes P2P de partage de fichiers sont devenus très populaires grâce aux accès à des ressources diverses, distribuées sur Internet. Parallèlement à l'évolution de cette catégorie de systèmes, les dispositifs mobiles (téléphones cellulaires, PDA et autres appareils portatifs) ont eu un grand succès sur le marché. Équipés d'une technologie de communication sans fil (Bluetooth, et Wifi), ils peuvent communiquer sans nécessiter une infrastructure particulière en utilisant un réseau mobile adhoc (Mobile Adhoc NETwork -MANET). De la même manière, les systèmes P2P peuvent être aussi déployés sur ce type de réseau et deviennent des systèmes P2P mobiles (Mobile 2P systems). Dans le cadre de cette thèse, nous nous intéressons essentiellement à la recherche d'information dans les systèmes P2P et plus précisément au problème de routage de requêtes. La première partie de la thèse, s'est focalisée sur le routage de requêtes dans les systèmes P2P sur Internet. Nous avons proposé (i) un modèle de routage sémantique basé sur l'historique des requêtes. Ce modèle est ensuite instancié pour définir une nouvelle méthode de routage par apprentissage. Pour pallier le problème de démarrage à froid, (ii) nous avons proposé une méthode prédictive de l'intention de l'utilisateur qui construit une base de connaissances à priori pour chaque pair. Enfin, (iii) nous avons proposé une méthode de routage hybride pour traiter le problème d'échec de sélection. Cette méthode est basée sur l'historique des requêtes et le regroupement de pairs dans des groupes sémantiques. La deuxième partie de la thèse, s'est focalisée sur le routage de requêtes dans les systèmes P2P mobiles. L'apparition des MANETs, a soulevé de nouveaux challenges de routage. Ces réseaux souffrent de plusieurs contraintes liées aux supports de transmission ou bien aux dispositifs mobiles. Dans ce cadre, nous avons proposé une méthode de routage pour les systèmes P2P non structurés mobiles basée sur le contexte de l'utilisateur. D'un point de vue technique, toutes ces propositions ont été développées, validées et évaluées grâce aux simulateurs PeerSim et NS2

Le cloud computing a eu un impact majeur sur la gestion des données, conduisant à une prolifération de nouvelles solutions évolutives de gestion des données telles que le stockage distribué de fichiers et d’objets, les bases de données NoSQL et les frameworks de traitement de données. Cela a conduit également à une grande diversification des interfaces aux SGBD et à la perte d’un paradigme de programmation commun, ce qui rend très difficile pour un utilisateur d’intégrer ses données lorsqu’elles se trouvent dans des sources de données spécialisées, par exemple, relationnelle, document et graphe.Dans cette thèse, nous abordons le problème du traitement de requêtes avec plusieurs sources de données dans le cloud, où ces sources ont des modèles, des langages et des API différents. Cette thèse a été préparée dans le cadre du projet européen CoherentPaaS et, en particulier, du système multistore CloudMdsQL. CloudMdsQL est un langage de requête fonctionnel capable d’exploiter toute la puissance des sources de données locales, en permettant simplement à certaines requêtes natives portant sur les systèmes locauxd’être appelées comme des fonctions et en même temps optimisées, par exemple, en exploitant les prédicats de sélection, en utilisant le bindjoin, en réalisant l’ordonnancement des jointures ou en réduisant les transferts de données intermédiaires.Dans cette thèse, nous proposons une extension de CloudMdsQL pour tirer pleinement parti des fonctionnalités des frameworks de traitement de données sous-jacents tels que Spark en permettant l’utilisation ad hoc des opérateurs de map/filter/reduce (MFR) définis par l’utilisateur en combinaison avec les ordres SQL traditionnels. Cela permet d’effectuer des jointures entre données relationnelles et HDFS. Notre solution permet l’optimisation en permettant la réécriture de sous-requêtes afin de réaliser des optimisations majeures comme le bindjoin ou le filtrage des données le plus tôt possible.Nous avons validé notre solution en implémentant l’extension MFR dans le moteur de requête CloudMdsQL. Sur la base de ce prototype, nous proposons une validation expérimentale du traitement des requêtes multistore dans un cluster pour évaluer l’impact sur les performances de l’optimisation. Plus précisément, nous explorons les avantages de l’utilisation du bindjoin et du filtrage de données dans des conditions différentes. Dans l’ensemble, notre évaluation des performances illustre la capacité du moteur de requête CloudMdsQL à optimiser une requête et à choisir la stratégie d’exécution la plus efficace. / Cloud computing is having a major impact on data management, with a proliferation of new, scalable data management solutions such as distributed file and object storage, NoSQL databases and big data processing frameworks. This also leads to a wide diversification of DBMS interfaces and the loss of a common programming paradigm, making it very hard for a user to integrate its data sitting in specialized data stores, e.g. relational, documents and graph data stores.In this thesis, we address the problem of query processing with multiple cloud data stores, where the data stores have different models, languages and APIs. This thesis has been prepared in the context of the CoherentPaaS European project and, in particular, the CloudMdsQL multistore system. CloudMdsQL is a functional query language able to exploit the full power of local data stores, by simply allowing some local data store native queries to be called as functions, and at the same time be optimized, e.g. by pushing down select predicates, using bind join, performing join ordering, or planning intermediate data shipping.In this thesis, we propose an extension of CloudMdsQL to take full advantage of the functionality of the underlying data processing frameworks such as Spark by allowing the ad-hoc usage of user defined map/filter/reduce (MFR) operators in combination with traditional SQL statements. This allows performing joins between relational and HDFS big data. Our solution allows for optimization by enabling subquery rewriting so that bind join can be used and filter conditions can be pushed down and applied by the data processing framework as early as possible.We validated our solution by implementing the MFR extension as part of the CloudMdsQL query engine. Based on this prototype, we provide an experimental validation of multistore query processing in a cluster to evaluate the impact on performance of optimization. More specifically, we explore the performance benefit of using bind join and select pushdown under different conditions. Overall, our performance evaluation illustrates the CloudMdsQL query engine’s ability to optimize a query and choose the most efficient execution strategy.

Devant des collections massives et hétérogènes de données, les systèmes de RI doivent désormais pouvoir appréhender des comportements d'utilisateurs aussi variés qu'imprévisibles. L'objectif de notre travail est d'évaluer la façon dont un même utilisateur verbalise un besoin informationnel à travers un énoncé de type « expression libre » (appelé langage naturel) et un énoncé de type mots-clés (appelé langage de requêtes). Pour cela, nous nous situons dans un contexte applicatif, à savoir des demandes de remboursement des utilisateurs d'un moteur de recherche dédié à des études économiques en français. Nous avons recueilli via ce moteur, les deux types d'énoncés sur 5 années consécutives totalisant un corpus de 1398 demandes en langage naturel et de 3427 requêtes. Nous avons alors comparé l'expression en tant que tel du besoin informationnel et mis en avant ce qu'apportait, en termes d'informations et de précisions, le recours à l'un ou l'autre du langage utilisé. / With the massive and heterogeneous web document collections, IR system must analyze the behaviors of users which are unpredictable and varied. The approach described in this thesis provides a comparison of the verbalizations for both natural language and web query for the same information need by the same user. For this, we used data collected (i.e. users' complaints in natural language and web queries) through a search engine dedicated to economic reports in French over 5 consecutive years totaling a corpus of 1398 natural language requests and 3427 web queries. Then, we compared the expression of the information need and highlighted the contributions in terms of information and clarification, the use of either language used.

Dans cette thèse, nous étudions le problème d’optimisation du temps de transfert de données dans les systèmes de gestion de données distribuées, en nous focalisant sur la relation entre le temps de communication de données et la configuration du middleware. En réalité, le middleware détermine, entre autres, comment les données sont divisées en lots de F tuples et messages de M octets avant d’être communiqués à travers le réseau. Concrètement, nous nous concentrons sur la question de recherche suivante : étant donnée requête Q et l’environnement réseau, quelle est la meilleure configuration de F et M qui minimisent le temps de communication du résultat de la requête à travers le réseau?A notre connaissance, ce problème n’a jamais été étudié par la communauté de recherche en base de données.Premièrement, nous présentons une étude expérimentale qui met en évidence l’impact de la configuration du middleware sur le temps de transfert de données. Nous explorons deux paramètres du middleware que nous avons empiriquement identifiés comme ayant une influence importante sur le temps de transfert de données: (i) la taille du lot F (c’est-à-dire le nombre de tuples dans un lot qui est communiqué à la fois vers une application consommant des données) et (ii) la taille du message M (c’est-à-dire la taille en octets du tampon du middleware qui correspond à la quantité de données à transférer à partir du middleware vers la couche réseau). Ensuite, nous décrivons un modèle de coût permettant d’estimer le temps de transfert de données. Ce modèle de coût est basé sur la manière dont les données sont transférées entre les noeuds de traitement de données. Notre modèle de coût est basé sur deux observations cruciales: (i) les lots et les messages de données sont communiqués différemment sur le réseau : les lots sont communiqués de façon synchrone et les messages dans un lot sont communiqués en pipeline (asynchrone) et (ii) en raison de la latence réseau, le coût de transfert du premier message d’un lot est plus élevé que le coût de transfert des autres messages du même lot. Nous proposons une stratégie pour calibrer les poids du premier et non premier messages dans un lot. Ces poids sont des paramètres dépendant de l’environnement réseau et sont utilisés par la fonction d’estimation du temps de communication de données. Enfin, nous développons un algorithme d’optimisation permettant de calculer les valeurs des paramètres F et M qui fournissent un bon compromis entre un temps optimisé de communication de données et une consommation minimale de ressources. L’approche proposée dans cette thèse a été validée expérimentalement en utilisant des données issues d’une application en Astronomie. / In this thesis, we take a complementary look to the problem of optimizing the time for communicating query results in distributed query processing, by investigating the relationship between the communication time and the middleware configuration. Indeed, the middleware determines, among others, how data is divided into batches and messages before being communicated over the network. Concretely, we focus on the research question: given a query Q and a network environment, what is the best middleware configuration that minimizes the time for transferring the query result over the network? To the best of our knowledge, the database research community does not have well-established strategies for middleware tuning. We present first an intensive experimental study that emphasizes the crucial impact of middleware configuration on the time for communicating query results. We focus on two middleware parameters that we empirically identified as having an important influence on the communication time: (i) the fetch size F (i.e., the number of tuples in a batch that is communicated at once to an application consuming the data) and (ii) the message size M (i.e., the size in bytes of the middleware buffer, which corresponds to the amount of data that can be communicated at once from the middleware to the network layer; a batch of F tuples can be communicated via one or several messages of M bytes). Then, we describe a cost model for estimating the communication time, which is based on how data is communicated between computation nodes. Precisely, our cost model is based on two crucial observations: (i) batches and messages are communicated differently over the network: batches are communicated synchronously, whereas messages in a batch are communicated in pipeline (asynchronously), and (ii) due to network latency, it is more expensive to communicate the first message in a batch compared to any other message that is not the first in its batch. We propose an effective strategy for calibrating the network-dependent parameters of the communication time estimation function i.e, the costs of first message and non first message in their batch. Finally, we develop an optimization algorithm to effectively compute the values of the middleware parameters F and M that minimize the communication time. The proposed algorithm allows to quickly find (in small fraction of a second) the values of the middleware parameters F and M that translate a good trade-off between low resource consumption and low communication time. The proposed approach has been evaluated using a dataset issued from application in Astronomy.

Cette thèse porte sur la définition d'une approche flexible pour interroger des graphes RDF à la fois classiques et flous. Cette approche, basée sur la théorie des ensembles flous, permet d'étendre SPARQL qui est le langage de requête standardisé W3C pour RDF, de manière à pouvoir exprimer i) des préférences utilisateur floues sur les données (par exemple, l'année de publication d'un album est récente) et sur la structure du graphe (par exemple, le chemin entre deux amis doit être court) et ii) des préférences utilisateur plus complexes, prenant la forme de propositions quantifiées floues (par exemple, la plupart des albums qui sont recommandés par un artiste, sont très bien notés et ont été créés par un jeune ami de cet artiste). Nous avons effectué des expérimentations afin d'étudier les performances de cette approche. L'objectif principal de ces expérimentations était de montrer que le coût supplémentaire dû à l'introduction du flou reste limité/acceptable. Nous avons également étudié, dans un cadre plus général, celui de bases de données graphe, la question de l'intégration du même type de propositions quantifiées floues dans une extension floue de Cypher qui est un langage déclaratif pour l'interrogation des bases de données graphe classiques. Les résultats expérimentaux obtenus montrent que le coût supplémentaire induit par la présence de conditions quantifiées floues dans les requêtes reste également très limité dans ce cas. / This thesis concerns the definition of a flexible approach for querying both crisp and fuzzy RDF graphs. This approach, based on the theory of fuzzy sets, makes it possible to extend SPARQL which is the W3C-standardised query language for RDF, so as to be able to express i) fuzzy user preferences on data (e.g., the release year of an album is recent) and on the structure of the data graph (e.g., the path between two friends is required to be short) and ii) more complex user preferences, namely, fuzzy quantified statements (e.g., most of the albums that are recommended by an artist, are highly rated and have been created by a young friend of this artist). We performed some experiments in order to study the performances of this approach. The main objective of these experiments was to show that the extra cost due to the introduction of fuzziness remains limited/acceptable. We also investigated, in a more general framework, namely graph databases, the issue of integrating the same type of fuzzy quantified statements in a fuzzy extension of Cypher which is a declarative language for querying (crisp) graph databases. Some experimental results are reported and show that the extra cost induced by the fuzzy quantified nature of the queries also remains very limited.

La forte volumétrie des données décrites par des ontologies a conduit à la naissance des basesde données à base ontologique (BDBO). Plusieurs communautés se sont intéressées à cette technologieet ont proposé des solutions pour persister les données sémantiques dans des SGBD.Parallèlement, la conception physique est devenue une étape primordiale dans le cycle de viede conception des bases de données (BD). Durant cette phase, des structures d’optimisation sontsélectionnées. Si de nombreux travaux ont été menés sur la conception physique dans le contexte desBD traditionnelles, peu se sont intéressés à la conception physique dans les BDBO qui est pluscomplexe. Cette complexité est due à la diversité des BDBO qui porte sur des formalismes supportés,des modèles de stockage et des architectures utilisés.Pour guider la sélection des structures d’optimisation et mesurer sa qualité, nous avonsdéveloppé un modèle de coût pour estimer le coût des requêtes dans les BDBO. Les résultatsthéoriques sont confrontés avec les résultats pratiques obtenus à partir de six BDBO dont troisindustrielles (Oracle et IBM SOR, DB2RDF) et trois académiques (Jena, Sesame et OntoDB du LIASde l'ISAE-ENSMA). Ce modèle de coût a été utilisé dans le processus de sélection des vuesmatérialisées. Nous avons proposé deux approches de matérialisation : une approche conceptuelle oùla sélection des vues matérialisées est faite sur les classes et les propriétés utilisées par les requêtes etune approche simulée où la sélection prend en compte la diversité des BDBO. Des expérimentationsont été conduites pour évaluer la qualité de nos approches en les confrontant avec les principauxtravaux existants / The high volume of data described by ontologies led to the creation of Ontology-BasedDatabase (OBDB). Many communities are interested in this technology and have proposed solutionsto persist semantic data in DBMS.Meanwhile, the physical design has become an essential step in the life cycle of databasedesign, in which optimization structures are selected. While many studies have been conducted on thephysical design in the context of traditional databases, few have focused on the physical design inOBDB which is more complex. This complexity is due to the diversity of OBDB which focuses onformalisms supported, storage models and architectures used.To guide the selection of optimization structures, we have developed a cost model to estimatethe cost of queries in OBDB. The theoretical results are compared with the practical results obtainedfrom six OBDB including three industrial (Oracle, IBM SOR and DB2RDF) and three academic (Jena,Sesame and OntoDB of the LIAS Lab of ISAE-ENSMA). This cost model was used in thematerialized views selection process. We proposed two approaches of materialized views selection: aconceptual approach where the selection of materialized views is made on the classes and propertiesused by queries and a simulated approach where the selection takes into account the diversity ofOBDB. Experiments were conducted to evaluate the quality of our approaches and compare them withthe main existing work