La qualité d'un plan d'exécution engendré par un optimiseur de requêtes est fortement dépendante de la qualité des estimations produites par le modèle de coûts. Malheureusement, ces estimations sont souvent imprécises. De nombreux travaux ont été menés pour améliorer la précision des estimations. Cependant, obtenir des estimations précises reste très difficile car ceci nécessite une connaissance préalable et détaillée des propriétés des données et des caractéristiques de l'environnement d'exécution. Motivé par ce problème, deux approches principales de méthodes d'optimisation ont été proposées. Une première approche s'appuie sur des valeurs singulières d'estimations pour choisir un plan d'exécution optimal. A l'exécution, des statistiques sont collectées et comparées à celles estimées. En cas d'erreur d'estimation, une ré-optimisation est déclenchée pour le reste du plan. A chaque invocation, l'optimiseur associe des valeurs spécifiques aux paramètres nécessaires aux calculs des coûts. Cette approche peut ainsi induire plusieurs ré-optimisations d'un plan, engendrant ainsi de mauvaises performances. Dans l'objectif d'éviter cela, une approche alternative considère la possibilité d'erreurs d'estimation dès la phase d'optimisation. Ceci est modélisé par l'utilisation d'un ensemble de points d'estimations pour chaque paramètre présumé incertain. L'objectif est d'anticiper la réaction à une sous-optimalité éventuelle d'un plan d'exécution. Les méthodes dans cette approche cherchent à générer des plans robustes dans le sens où ils sont capables de fournir des performances acceptables et stables pour plusieurs conditions d'exécution. Ces méthodes supposent souvent qu'il est possible de trouver un plan robuste pour l'ensemble de points d'estimations considéré. Cette hypothèse reste injustifiée, notamment lorsque cet ensemble est important. De plus, la majorité de ces méthodes maintiennent sans modification un plan d'exécution jusqu'à la terminaison. Cela peut conduire à de mauvaises performances en cas de violation de la robustesse à l'exécution. Compte tenu de ces constatations, nous proposons dans le cadre de cette thèse une méthode d'optimisation hybride qui vise deux objectifs : la production de plans d'exécution robustes, notamment lorsque l'incertitude des estimations utilisées est importante, et la correction d'une violation de la robustesse pendant l'exécution. Notre méthode s'appuie sur des intervalles d'estimations calculés autour des paramètres incertains, pour produire des plans d'exécution robustes. Ces plans sont ensuite enrichis par des opérateurs dits de contrôle et de décision. Ces opérateurs collectent des statistiques à l'exécution et vérifient la robustesse du plan en cours. Si la robustesse est violée, ces opérateurs sont capables de prendre des décisions de corrections du reste du plan sans avoir besoin de rappeler l'optimiseur. Les résultats de l'évaluation des performances de notre méthode indiquent qu'elle fournit des améliorations significatives dans la robustesse d'évaluation de requêtes. / The quality of an execution plan generated by a query optimizer is highly dependent on the quality of the estimates produced by the cost model. Unfortunately, these estimates are often imprecise. A body of work has been done to improve estimate accuracy. However, obtaining accurate estimates remains very challenging since it requires a prior and detailed knowledge of the data properties and run-time characteristics. Motivated by this issue, two main optimization approaches have been proposed. A first approach relies on single-point estimates to choose an optimal execution plan. At run-time, statistics are collected and compared with estimates. If an estimation error is detected, a re-optimization is triggered for the rest of the plan. At each invocation, the optimizer uses specific values for parameters required for cost calculations. Thus, this approach can induce several plan re-optimizations, resulting in poor performance. In order to avoid this, a second approach considers the possibility of estimation errors at the optimization time. This is modelled by the use of multi-point estimates for each error-prone parameter. The aim is to anticipate the reaction to a possible plan sub-optimality. Methods in this approach seek to generate robust plans, which are able to provide good performance for several run-time conditions. These methods often assume that it is possible to find a robust plan for all expected run-time conditions. This assumption remains unjustified. Moreover, the majority of these methods maintain without modifications an execution plan until the termination. This can lead to poor performance in case of robustness violation at run-time. Based on these findings, we propose in this thesis a hybrid optimization method that aims at two objectives : the production of robust execution plans, particularly when the uncertainty in the used estimates is high, and the correction of a robustness violation during execution. This method makes use of intervals of estimates around error-prone parameters. It produces execution plans that are likely to perform reasonably well over different run-time conditions, so called robust plans. Robust plans are then augmented with what we call check-decide operators. These operators collect statistics at run-time and check the robustness of the current plan. If the robustness is violated, check-decide operators are able to make decisions for plan modifications to correct the robustness violation without a need to recall the optimizer. The results of performance studies of our method indicate that it provides significant improvements in the robustness of query processing.

Avec l’avènement de « l'ère des données », les besoins des systèmes de traitement de l'information en ressources de calcul ont explosé, dépassant largement les évolutions technologiques des processeurs modernes. Dans le domaine de l'apprentissage statistique en particulier, les paradigmes de calcul massivement distribués représentent la seule alternative praticable.L'algorithmique distribuée emprunte la plupart de ses concepts à l'algorithmique classique, centralisée et séquentielle, dans laquelle le comportement du système est décrit comme une suite d'instructions exécutées l'une après l'autre. L'importance de la communication entre unités de calcul y est généralement négligée et reléguée aux détails d'implémentation. Or, lorsque le nombre d'unités impliquées augmente, le poids des opérations locales s'efface devant les effets émergents propres aux larges réseaux d'unités. Pour conserver les propriétés désirables de stabilité, de prédictibilité et de programmabilité offertes par l'algorithmique centralisée, les paradigmes de calcul distribué doivent dès lors intégrer cette dimension qui relève de la théorie des graphes.Cette thèse propose un cadre algorithmique pour l'apprentissage statistique large échelle, qui prévient deux défaut majeurs des méthodes classiques : la centralisation et la synchronisation. Nous présentons ainsi plusieurs algorithmes basés sur des protocoles Gossip décentralisés et asynchrones, applicables aux problèmes de catégorisation, estimation de densité, réduction de dimension, classification et optimisation convexe. Ces algorithmes produisent des solutions identiques à leurs homologues centralisés, tout en offrant une accélération appréciable sur de larges réseaux pour un coût de communication très réduit. Ces qualités pratiques sont démontrées mathématiquement par une analyse de convergence détaillée. Nous illustrons finalement la pertinence des méthodes proposées sur des tâches d'indexation multimédia et de classification d'images. / With the advent of the "data era", the amount of computational resources required by information processing systems has exploded, largely exceeding the technological evolutions of modern processors. Specifically, contemporary machine learning applications necessarily resort to massively distributed computation.Distributed algorithmics borrows most of its concepts from classical centralized and sequential algorithmics, where the system's behavior is defined as a sequence of instructions, executed one after the other. The importance of communication between computation units is generally neglected and pushed back to implementation details. Yet, as the number of units grows, the impact of local operations vanishes behind the emergent effects related to the large network of units. To preserve the desirable properties of centralized algorithmics such as stability, predictability and programmability, distributed computational paradigms must encompass this graph-theoretical dimension.This thesis proposes an algorithmic framework for large scale machine learning, which prevent two major drawbacks of classical methods, namely emph{centralization} and emph{synchronization}. We therefore introduce several new algorithms based on decentralized and asynchronous Gossip protocols, for solving clustering, density estimation, dimension reduction, classification and general convex optimization problems, while offering an appreciable speed-up on large networks with a very low communication cost. These practical advantages are mathematically supported by a theoretical convergence analysis. We finally illustrate the relevance of proposed methods on multimedia indexing applications and real image classification tasks.

Nous proposons une approche statistique de la versification de Raymond Queneau. Au cœur de notre travail se trouve une base de données MySQL, qui rassemble des informations descriptives à propos de la versification des 15.996 vers publiés par Queneau de son vivant. Jusqu’ici, les bases de données consacrées à la métrique ont exploré les vers réguliers, laissant de côté le vers libre et les questions spécifiques qu’il pose. Notre base envisage conjointement ces deux catégories de vers. Nous en tirons des statistiques, des représentations graphiques, et une approche globale du texte.La versification de Raymond Queneau a été peu étudiée. Il s’agit d’un corpus hétérogène, pour lequel la distinction entre vers libres et vers réguliers n’est pas toujours opérante. Au sein de ces formes variées, nous avons cherché des traits fixes, des motifs récurrents, des tendances, des routines. Nous proposons une typologie des vers queniens, décrivons la parenté du vers libre quenien avec le vers classique, modélisons des structures de la poésie de Queneau et étudions les significations liées à ses choix métriques.Il ressort de nos résultats que la versification de Queneau est porteuse de signification. Queneau y manifeste son refus des conventions, et son choix systématique d’une troisième voie réconciliant conservatisme et innovation.Ce travail ouvre des perspectives pour les bases de données consacrées à la versification. De nouvelles bases de données sont à développer, pour d’autres corpus, qui enrichiront les champs de la stylistique et de la poétique. / We present a statistical approach to Raymond Queneau’s versification. At the centre of the study is a MySQL database, which compiles descriptive data on the versification of the 15,996 lines of poetry published by Queneau during his lifetime. Until now databases dedicated to metrics have focussed on strict verse, leaving aside free verse and the specific issues it raises. Our database explores both categories together, providing the source for statistics, graphs and a comprehensive approach to the text.Raymond Queneau’s versification has not been studied to any great extent. It is a heterogeneous corpus, where the strict vs. free verse distinction does not apply consistently. Within these diverse forms, this study endeavours to find fixed features, recurring patterns, trends and routines. This exploration has resulted in the creation of a typology of Queneau’s verse, a description of how free and strict verse are related in his writing, the making of a model for his poems’ structures, and a study of his metrical choices’ meanings.Our results show that Queneau’s versification conveys various meanings. Through it he expresses his reluctance towards conventions and his choice of third path, bringing together conservatism and innovation.The approach behind this thesis also opens up new perspectives regarding databases dedicated to versification. Similar databases can be developed for other corpora, which will enrich both stylistics and poetics.

La recherche sur les bases de données chiffrées vise à rendre efficace une tâche apparemment simple : déléguer le stockage de données à un serveur qui ne serait pas de confiance, tout en conservant des fonctionnalités de recherche. Avec le développement des services de stockage dans le Cloud, destinés aussi bien aux entreprises qu'aux individus, la mise au point de solutions efficaces à ce problème est essentielle pour permettre leur déploiement à large échelle. Le principal problème de la recherche sur bases de données chiffrées est qu'un schéma avec une sécurité ''parfaite'' implique un surcoût en termes de calcul et de communication qui serait inacceptable pour des fournisseurs de services sur le Cloud ou pour les utilisateurs - tout du moins avec les technologies actuelles. Cette thèse propose et étudie de nouvelles notions de sécurité et de nouvelles constructions de bases de données chiffrées permettant des recherches efficaces et sûres. En particulier, nous considérons la confidentialité persistante et la confidentialité future de ces bases de données, ce que ces notions impliquent en termes de sécurité et d'efficacité, et comment les réaliser. Ensuite, nous montrons comment protéger les utilisateurs de bases de données chiffrées contre des attaques actives de la part du serveur hébergeant la base, et que ces protections ont un coût inévitable. Enfin, nous étudions les attaques existantes contre ces bases de données chiffrées et comment les éviter. / Searchable encryption aims at making efficient a seemingly easy task: outsourcing the storage of a database to an untrusted server, while keeping search features. With the development of Cloud storage services, for both private individuals and businesses, efficiency of searchable encryption became crucial: inefficient constructions would not be deployed on a large scale because they would not be usable. The key problem with searchable encryption is that any construction achieving ''perfect security'' induces a computational or a communicational overhead that is unacceptable for the providers or for the users --- at least with current techniques and by today's standards. This thesis proposes and studies new security notions and new constructions of searchable encryption, aiming at making it more efficient and more secure. In particular, we start by considering the forward and backward privacy of searchable encryption schemes, what it implies in terms of security and efficiency, and how we can realize them. Then, we show how to protect an encrypted database user against active attacks by the Cloud provider, and that such protections have an inherent efficiency cost. Finally, we take a look at existing attacks against searchable encryption, and explain how we might thwart them.

Récemment, les ontologies ont été largement adoptées par différentes entreprises dans divers domaines. Elles sontdevenues des composantes centrales dans bon nombre d'applications. Ces modèles conceptualisent l'univers du discours auxmoyens de concepts primitifs et parfois redondants (calculés à partir de concepts primitifs). Au début, la relation entreontologies et base de données a été faiblement couplée. Avec l'explosion des données sémantiques, des solutions depersistance assurant une haute performance des applications ont été proposées. En conséquence, un nouveau type de base dedonnées, appelée base de données à base ontologique (BDBO) a vu le jour. Plusieurs types de BDBO ont été proposés, ilsutilisent différents SGBD. Chaque BDBO possède sa propre architecture et ses modèles de stockage dédiés à la persistancedes ontologies et de ses instances. A ce stade, la relation entre les bases de données et les ontologies devient fortementcouplée. En conséquence, plusieurs études de recherche ont été proposées sur la phase de conception physique des BDBO.Les phases conceptuelle et logique n'ont été que partiellement traitées. Afin de garantir un succès similaire au celui connupar les bases de données relationnelles, les BDBO doivent être accompagnées par des méthodologies de conception et desoutils traitant les différentes étapes du cycle de vie d'une base de données. Une telle méthodologie devrait identifier laredondance intégrée dans l'ontologie. Nos travaux proposent une méthodologie de conception dédiée aux bases de données àbase ontologique incluant les principales phases du cycle de vie du développement d'une base de données : conceptuel,logique, physique ainsi que la phase de déploiement. La phase de conception logique est réalisée grâce à l'incorporation desdépendances entre les concepts ontologiques. Ces dépendances sont semblables au principe des dépendances fonctionnellesdéfinies pour les bases de données relationnelles. En raison de la diversité des architectures des BDBO et la variété desmodèles de stockage utilisés pour stocker et gérer les données ontologiques, nous proposons une approche de déploiement àla carte. Pour valider notre proposition, une implémentation de notre approche dans un environnement de BDBO sousOntoDB est proposée. Enfin, dans le but d'accompagner l'utilisateur pendant le processus de conception, un outil d'aide à laconception des bases de données à partir d'une ontologie conceptuelle est présenté / Recently, ontologies have been widely adopted by small, medium and large companies in various domains. Theyhave become central components in many applications. These models conceptualize the universe of discourse by means ofprimitive and sometimes redundant concepts (derived from primitive concepts). At first, the relationship between ontologiesand database was loosely coupled. With the explosion of semantic data, persistence solutions providing high performanceapplications have been proposed. As a consequence, a new type of database, called ontology-based database (OBDB) isborn. Several types of OBDB have been proposed including different architectures of the target DBMS and storage modelsfor ontologies and their instances. At this stage, the relationship between databases and ontologies becomes strongly coupled.As a result, several research studies have been proposed on the physical design phase of OBDB. Conceptual and logicalphases were only partially treated. To ensure similar success to that known by relational databases, OBDB must beaccompanied by design methodologies and tools dealing with the different stages of the life cycle of a database. Such amethodology should identify the redundancy built into the ontology. In our work, we propose a design methodologydedicated to ontology-based databases including the main phases of the lifecycle of the database development: conceptual,logical and physical as well as the deployment phase. The logical design phase is performed thanks to the incorporation ofdependencies between concepts and properties of the ontologies. These dependencies are quite similar to the functionaldependencies in traditional databases. Due to the diversity of the OBDB architectures and the variety of the used storagemodels (triplet, horizontal, etc.) to store and manage ontological data, we propose a deployment ‘à la carte. To validate ourproposal, an implementation of our approach in an OBDB environment on OntoDB is proposed. Finally, in order to supportthe user during the design process, a tool for designing databases from a conceptual ontology is presented.

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

L’augmentation globale des températures au cours de la période 1850-2012 n’est pas uniforme à l’échelle du globe et l’Arctique se réchauffe deux fois plus que la moyenne. Cependant, la couverture temporelle trop courte des données instrumentales rend difficile la distinction entre la variabilité climatique naturelle et celle liée au forçage anthropique. L’étude de la variabilité climatique « exempte » de l’influence humaine est alors réalisée à partir de données proxies indirectes provenant d’archives paléoclimatiques continentales et marines. Dans la région Arctique-subarctique, les enregistrements disponibles à haute résolution sur les derniers 2000 ans ont été centralisé dans la base de données PAGES Arctic 2k. Les objectifs de ces travaux sont l’amélioration de la caractérisation et de l’interprétation de la variabilité climatique sur les derniers 2000 ans, en allant plus loin que la tendance millénaire et les périodes climatiques majeures mais aussi en s'intéressant au rôle et l’expression spatiale de la variabilité interne du système climatique. Cette thèse s'appuie sur la base de données PAGES Arctic 2k permettant l'étude des variations de températures dans la région Arctique-subarctique mais aussi d'une nouvelle base de données permettant de reconstruire les variations hydroclimatiques (précipitations et humidité) dans la région et créée lors de cette étude. L'utilisation de méthodes d'analyse du signal climatique sur des enregistrements régionaux calculés à partir de ces deux bases de données a permis de mettre en évidence une variabilité climatique dans la région Arctique-subarctique s’exprimant depuis les échelles multi-décennales à millénaire. En particulier, les variabilités multi-décennales sont en lien avec la variabilité interne du système climatique. Les variations hydroclimatiques et de températures s'exprimant aux échelles multi-décennales dans la région sont en effet caractérisées par des fréquences spécifiques aux oscillations climatiques régionales (oscillation Atlantique Nord et oscillation Pacifique décennale), en particulier sur les derniers 200 ans. Les travaux réalisés sur la base de données de températures et la réflexion autour de la création et l’exploitation de la base de données hydroclimatiques ont également conduit à la définition d’une méthodologie de travail avec une base de données paléoclimatiques, depuis sa construction jusque la définition de ses limites, notamment en termes de représentativité spatiale des séries contenues dans la base de données et de l'assimilation de données avec des saisonnalités différentes. / The temperature increase during the 1850-2012 period is not uniform globally and the Arctic is warming twice as much as the average. However, the short time coverage of instrumental data makes it difficult to distinguish natural climate variability and anthropogenic forcing. The study of climatic variability "free" of human influence requires the use of proxies data measured in continental and marine palaeoclimatic archives. In the Arctic-subarctic region, high resolution records have been centralized in the Arctic 2k PAGES database. The objectives of this work are to improve the characterization and interpretation of climatic variability over the last 2000 years, going beyond the millennial trend and the major climatic periods, but also by focusing on the role and spatial expression of the internal variability of the climate system. This thesis is based on the Arctic 2k PAGES database, which allows the study of temperature variations in the Arctic-subarctic region, as well as a new database to reconstruct hydroclimatic variations (precipitation and humidity) in the region and created during this study. The use of climate signal analysis methods on regional records calculated from these two databases has highlighted climate variability in the Arctic-subarctic region from the multi-decadal to millennial scales.In particular, multi-decadal variability is related to the internal variability of the climate system. The hydroclimatic and temperature variations expressed at multi-decadal scales in the region are characterized by frequencies specific to regional climate oscillations (North Atlantic oscillation and decadal Pacific oscillation), particularly over the last 200 years. The work done on the temperature database and the reflection on the creation and exploitation of the hydroclimatic database have also led to the definition of a working methodology with a palaeoclimatic database, from its construction to the definition of its limits, in particular in terms of the spatial representability of the series contained in the database and the assimilation of data with different seasonings.

Dans ce document, nous adressons le problème de la réécriture de requêtes avec des vues, en adoptant une perspective à la fois théorique et pratique. Dans le premier et principal chapitre, nous approchons le sujet de la recherche de toutes les reformulations minimales (sans atomes relationnels redondants) pour une requête relationnelle conjonctive, sous des contraintes d’intégrité qui incluent la relation entre les schémas source et cible. Nous présentons un nouvel algorithme, correct et complet, le Provenance-Aware Chase & Backchase, qui résout le problème des reformulations avec des performances significatives sur le plan pratique. Nous présentons sa caractérisation théorique détaillée, son implémentation optimisée et son évaluation, montrant des gains de performance jusqu’à deux ordres de grandeur par rapport à un SGBD commercial. Nous généralisons notre algorithme pour trouver directement des reformulations de coût minimum pour les fonctions de coût monotones, et montrons les gains de performance de cette adaptation. Avec notre algorithme, nous introduisons également un nouveau type de chase, la Provenance-Aware Chase, qui comporte son propre intérêt théorique, en tant que moyen de raisonnement sur l’interaction entre la provenance et les contraintes. Dans le deuxième chapitre, nous nous plaçons dans un contexte XML et nous revisitons le travail de Cautis, Deutsch and Onose sur problème de la réécriture de requêtes XPath par un seul niveau d’intersection de plusieurs vues. Nous étendons l’analyse de ce probleme en montrant ses connexions avec les problèmes de l’équivalence DAG-arbre et de la union-freeness d’un DAG. Nous raffinons un algorithme de réécriture proposé par Cautis, Deutsch and Onose pour obtenir une complexité polynomiale et améliorer sa complétude, et présentons un ensemble d’optimisations des procedures de réécriture, necessaires pour atteindre des performances pratiques. Nous fournissons une implementation complète comprenant ces optimizations ainsi que son evaluation experimentale extensive, montrant la performance et l’utilité de la technique polynomiale de réécriture. / In this work, we address the problem of query rewriting using views, by adopting both a theoretical and a pragmatic perspective. In the first and main chapter, we approach the topic of finding all minimal (i.e. with no redundant relational atoms) conjunctive query reformulations for a relational conjunctive query, under constraints expressed as embedded dependencies, including the relationship between the source and the target schemas. We present a novel sound and complete algorithm, the Provenance-Aware Chase & Backchase, that solves the minimal reformulations problem with practically relevant performance. We provide a detailed theoretical characterization of our algorithm. We further present the optimized implementation and the experimental evaluation thereof, and exhibit natural scenarios yielding speed-ups of up to two orders of magnitude between the execution of a best view-based rewriting found by a commercial DBMS and that of a best rewriting found by our algorithm. We generalize the Provenance-Aware Chase & Backchase towards directly finding minimum-cost reformulations for monotonic cost functions, and show the performance improvements this adaptation further enables. With our algorithm, we introduce a novel chase flavour, the Provenance-Aware Chase, which is interesting on its own, as a means of reasoning about the interaction between provenance and constraints. In the second chapter, we move to an XML context and revisit the previous work of Cautis, Deutsch and Onose on the problem of finding XPath query rewritings with a single level of intersection of multiple views. We enrich the analysis of the rewriting problem by showing its links to the problems of DAG-tree equivalence and union-freeness. We refine the rule-based rewriting technique proposed by Cautis, Deutsch and Onose to ensure its polynomial complexity and improve its completeness, and present a range of optimizations on the rewriting procedures, necessary to achieve practical performance. We provide a complete implementation comprising these optimizations and a thorough experimental evaluation thereof, showing the performanceand utility of the polynomial rewriting technique.

La gestion des données incertaines peut devenir infaisable, dans le cas des bases de données probabilistes, ou même indécidable, dans le cas du raisonnement en monde ouvert sous des contraintes logiques. Cette thèse étudie comment pallier ces problèmes en limitant la structure des données incertaines et des règles. La première contribution présentée s'intéresse aux conditions qui permettent d'assurer la faisabilité de l'évaluation de requêtes et du calcul de lignage sur les instances relationnelles probabilistes. Nous montrons que ces tâches sont faisables, pour diverses représentations de la provenance et des probabilités, quand la largeur d'arbre des instances est bornée. Réciproquement, sous des hypothèses faibles, nous pouvons montrer leur infaisabilité pour toute autre condition imposée sur les instances. La seconde contribution concerne l'évaluation de requêtes sur des données incomplètes et sous des contraintes logiques, sous l'hypothèse de finitude généralement supposée en théorie des bases de données. Nous montrons la décidabilité de cette tâche pour les dépendances d'inclusion unaires et les dépendances fonctionnelles. Ceci constitue le premier résultat positif, sous l'hypothèse de la finitude, pour la réponse aux requêtes en monde ouvert avec un langage d'arité arbitraire qui propose à la fois des contraintes d'intégrité référentielle et des contraintes de cardinalité. / The management of data uncertainty can lead to intractability, in the case of probabilistic databases, or even undecidability, in the case of open-world reasoning under logical rules. My thesis studies how to mitigate these problems by restricting the structure of uncertain data and rules. My first contribution investigates conditions on probabilistic relational instances that ensure the tractability of query evaluation and lineage computation. I show that these tasks are tractable when we bound the treewidth of instances, for various probabilistic frameworks and provenance representations. Conversely, I show intractability under mild assumptions for any other condition on instances. The second contribution concerns query evaluation on incomplete data under logical rules, and under the finiteness assumption usually made in database theory. I show that this task is decidable for unary inclusion dependencies and functional dependencies. This establishes the first positive result for finite open-world query answering on an arbitrary-arity language featuring both referential constraints and number restrictions.

Plusieurs classes de solutions permettent d'exprimer des requêtes dans des langages de programmation: les interfaces spécifiques telles que JDBC, les mappings objet-relationnel ou object-relational mapping en anglais (ORMs) comme Hibernate, et les frameworks de requêtes intégrées au langage comme le framework LINQ de Microsoft. Cependant, la plupart de ces solutions ne permet de requêtes visant plusieurs bases de données en même temps, et aucune ne permet l'utilisation de logique d'application complexe dans des requêtes aux bases de données. Dans cette thèse, nous détaillons la création d'un framework de requêtes intégrées au langage nommé BOLDR qui permet d'évaluer dans les bases de données des requêtes écrites dans des langages de programmation généralistes qui contiennent de la logique d'application, et qui ciblent différentes bases de données potentiellement basées sur des modèles de données différents. Dans ce framework, les requêtes d'une application sont traduites vers une représentation intermédiaire de requêtes, puis réécrites pour éviter le phénomène "d'avalanche de requêtes" et pour profiter au maximum des capacités d'optimisation des bases de données, et enfin envoyées pour évaluation vers les bases de données ciblées et les résultats obtenus sont convertis dans le langage de programmation de l'application. Nos expériences montrent que les techniques implémentées dans ce framework sont applicables pour de véritables applications centrées données, et permettent de gérer efficacement un vaste champ de requêtes intégrées à des langages de programmation généralistes. / Several classes of solutions allow programming languages to express queries: Specific APIs such as JDBC, Object-Relational Mappings (ORMs) such as Hibernate, and language-integrated query frameworks such as Microsoft's LINQ. However, most of these solutions do not allow for efficient cross-databases queries, and none allow the use of complex application logic from the programming language in queries. In this thesis, we create a language-integrated query framework called BOLDR that, in particular, allows the evaluation in databases of queries written in general-purpose programming languages that contain application logic, and that target different databases of possibly different data models. In this framework, application queries are translated to an intermediate representation, then rewritten in order to avoid query avalanches and make the most out of database optimizations, and finally sent for evaluation to the corresponding databases and the results are converted back to the application. Our experiments show that the techniques we implemented are applicable to real-world database applications, successfully handling a variety of language-integrated queries with good performances.