Cette thèse se concentre autour du problème de l'évaluation des requêtes. Étant donné une requête q et une base de données D, l'objectif est de calculer l'ensemble q(D) des uplets résultant de l'évaluation de q sur D. Toutefois, l'ensemble q(D) peut être plus grand que la base de données elle-même car elle peut avoir une taille de la forme n^l où n est la taille de la base de données et l est l'arité de la requête. Calculer entièrement q(D) peut donc nécessiter plus que les ressources disponibles. L'objectif principal de cette thèse est une solution particulière à ce problème: une énumération de q(D) avec un délai constant. Intuitivement, cela signifie qu'il existe un algorithme avec deux phases: une phase de pré-traitement qui fonctionne en temps linéaire dans la taille de la base de données, suivie d'une phase d'énumération produisant un à un tous les éléments de q(D) avec un délai constant (indépendant de la taille de la base de données) entre deux éléments consécutifs. En outre, quatre autres problèmes sont considérés: le model-checking (où la requête q est un booléen), le comptage (où on veut calculer la taille |q(D)|), les tests (où on s'intéresse à un test efficace pour savoir si un uplet donné appartient au résultat de la requête) et la j-ième solution (où on veut accéder directement au j-ième élément de q(D)). Les résultats présentés dans cette thèse portent sur les problèmes ci-dessus concernant: - les requêtes du premier ordre sur les classes de structures de degré borné, - les requêtes du second ordre monadique sur les classes de structures de largeur d'arborescente bornée, - les requêtes du premier ordre sur les classes de structures avec expansion bornée. / This thesis is concentrated around the problem of query evaluation. Given a query q and a database D it is to compute the set q(D) of all tuples in the output of q on D. However, the set q(D) may be larger than the database itself as it can have a size of the form n^l where n is the size of the database and l the arity of the query. It can therefore require too many of the available resources to compute it entirely. The main focus of this thesis is a particular solution to this problem: a scenario where in stead of just computing, we are interested in enumerating q(D) with constant delay. Intuitively, this means that there is a two-phase algorithm working as follows: a preprocessing phase that works in time linear in the size of the database, followed by an enumeration phase outputting one by one all the elements of q(D) with a constant delay (which is independent from the size of the database) between any two consecutive outputs. Additionally, four more problems related to enumeration are also considered in the thesis. These are model-checking (where the query q is boolean), counting (where one wants to compute just the size |q(D)| of the output set), testing (where one is interested in an efficient test for whether a given tuple belongs to the output of the query or not) and j-th solution (where, one wants to be able to directly access the j-th element of q(D)). The results presented in the thesis address the above problems with respect to: - first-order queries over the classes of structures with bounded degree, - monadic second-order queries over the classes of structures with bounded treewidth, - first-order queries over the classes of structures with bounded expansion.

L’intérêt sans cesse croissant des données RDF disponibles sur le Web a conduit à l’émergence de multiple et importants efforts de recherche pour enrichir le formalisme traditionnel des données RDF à des fins d’exploitation et d’analyse. Le travail de cette thèse s’inscrit dans la continuation de ces efforts en abordant la problématique de la gestion des données RDF en présence d’imperfections (manque de confiance/validité, incertitude, etc.). Les contributions de la thèse sont comme suit: (1) Nous avons proposé d’appliquer l’opérateur skyline sur les données RDF pondérées par des mesures de confiance (Trust-RDF) dans le but d’extraire les ressources les plus confiantes selon des critères définis par l’utilisateur. (2) Nous avons discuté via des méthodes statistiques l’impact des mesures de confiance sur le Trust-skyline.(3) Nous avons intégré à la structure des données RDF un quatrième élément, exprimant une mesure de possibilité. Pour gérer cette mesure de possibilité, un cadre langagier appropriée est étudié, à savoir Pi-SPARQL, qui étend le langage SPARQL aux requêtes permettant de traiter des distributions de possibilités. (4) Nous avons étudié une variante d’opérateur skyline pour extraire les ressources RDF possibilistes qui ne sont éventuellement dominées par aucune autre ressource dans le sens de l’optimalité de Pareto. / The ever-increasing interest of RDF data on the Web has led to several and important research efforts to enrich traditional RDF data formalism for the exploitation and analysis purpose. The work of this thesis is a part of the continuation of those efforts by addressing the issue of RDF data management in presence of imperfection (untruthfulness, uncertainty, etc.). The main contributions of this dissertation are as follows. (1) We tackled the trusted RDF data model. Hence, we proposed to extend the skyline queries over trust RDF data, which consists in extracting the most interesting trusted resources according to user-defined criteria. (2) We studied via statistical methods the impact of the trust measure on the Trust-skyline set.(3) We integrated in the structure of RDF data (i.e., subject-property-object triple) a fourth element expressing a possibility measure to reflect the user opinion about the truth of a statement.To deal with possibility requirements, appropriate framework related to language is introduced, namely Pi-SPARQL, that extends SPARQL to be possibility-aware query language.Finally, we studied a new skyline operator variant to extract possibilistic RDF resources that are possibly dominated by no other resources in the sense of Pareto optimality

Durant la dernière décennie, l’évolution du Web a été marquée par une forte croissance des services publiés et qui s’est accompagnée d’une explosion considérable du nombre d’usagers dont les profils et contextes sont divers et variés. Les travaux présentés dans cette thèse traitent de l’optimisation de requêtes de services Web où le profil/contexte de l’utilisateur joue un rôle central. Il s’agit de sélectionner un service ou une combinaison de services pertinents parmi une masse importante de candidats compétitifs et capables de réaliser une tâche requise. Ces services candidats devant répondre au mieux aux exigences demandées par l’utilisateur selon un ensemble de critères non-fonctionnels. Dans notre approche, les critères non-fonctionnels considérés sont tous associés aux préférences du demandeur de service. Un intérêt plus important est alors porté à l’utilisateur qui se trouve au coeur du processus de sélection. La diversité du profil et du contexte de l’utilisateur, et également ceux des services cibles,rend ce processus encore plus complexe. Notre étude se focalise, dans un premier lieu,sur l’analyse des différentes approches de sélection de services Web existant dans la littérature. Nous mettons, notamment, en évidence leur contribution à la résolution des problèmes inhérents à la sélection des meilleurs services dans le but de satisfaire les critères non-fonctionnels formulés dans la requête. Dans un second temps, notre intérêt s’est porté sur la modélisation de spécification de l’offre et la demande de services,de leurs contextes et profils ainsi que les deux classes de préférences utilisateurs :explicites et implicites. Enfin, nous proposons une nouvelle famille d’approches d’optimisation qui intègre une stratégie de reformulation de requêtes par introduction des préférences implicites. Le concept clé de ces approches est un mécanisme d’inférence flou permettant d’accomplir un raisonnement déductif sur les informations liées au profil et contexte de l’utilisateur. Le principe consiste à combiner les deux familles de préférences utilisateur, tout en considérant conjointement les profils et les contextes des services et de l’utilisateur. L’application de la théorie des ensembles flous dans l’optimisation des requêtes à préférences des utilisateurs, en intégrant un module de raisonnement sur les informations liées à l’utilisateur, s’avère d’un intérêt majeur dans l’amélioration des qualités des résultats retournés. Nous présentons à la fin de l’étude une série d’expérimentations pour montrer la validité et la pertinence des approches proposées. / The internet has completely transformed the way how we communicate (access toinformation). Its evolution was marked by strong growth of published services which has been accompanied by a large explosion in the number of users and a diversity oftheir profiles and their contexts.The work presented in this thesis deal with the adaptive optimization of Web services queries to user needs. This problem is to select a service or a combination of relevant services from a collection of candidates able to perform a required task. These candidate services must meet the requirements requested by the user, the selection makes his/herchoice from non-functional criteria. In our approach, non-functional criteria considered are all associated with preferences of service requester. A significant interest is therefore carried to the user who is at the core of the selection system. This selection is generally considered a complex task because of the diversity of profile and context of the service,which it is performed.Our study focuses mainly on the analysis of different service selection approaches.We especially highlight their contribution to solving the problems inherent in selecting the best services in order to meet the non-functional parameters of the request. Second, our interest has focused on modeling the specification of supply and demand for services, their context and profile as well as the two families preferences : explicit and implicit. Finally, we propose a novel optimization approach that integrates a query reformulation strategy by introducing implicit preferences based on the fuzzy inference process. The idea is to combine the two families of preferences required by the user with consideration of profiles and contexts of services and the user simultaneously. The application of fuzzy set theory in the optimization of preference query of customers by integrating reasoning module on information related to the user leads of great interest in improving the quality of results. We present at the end a set of experiments to demonstrate the validity and relevance of the proposed approach.

RDF et SPARQL se sont imposés comme modèle de données et langage de requêtes standard pour décrire et interroger les données sur la Toile. D’importantes quantités de données RDF sont désormais disponibles, sous forme de jeux de données ou de méta-données pour des documents semi-structurés, en particulier XML. La coexistence et l’interdépendance grandissantes entre RDF et XML rendent de plus en plus pressant le besoin de représenter et interroger ces données conjointement. Bien que de nombreux travaux couvrent la production et la publication, manuelles ou automatiques, d’annotations pour données semi-structurées, peu de recherches ont été consacrées à l’exploitation de telles données. Cette thèse pose les bases de la gestion de données hybrides XML-RDF. Nous présentons XR, un modèle de données accommodant l’aspect structurel d’XML et la sémantique de RDF. Le modèle est suffisamment général pour représenter des données indépendantes ou interconnectées, pour lesquelles chaque nœud XML est potentiellement une ressource RDF. Nous introduisons le langage XRQ, qui combine les principales caractéristiques des langages XQuery et SPARQL. Le langage permet d’interroger la structure des documents ainsi que la sémantique de leurs annotations, mais aussi de produire des données semi-structurées annotées. Nous introduisons le problème de composition de requêtes dans le langage XRQ et étudions de manière exhaustive les techniques d’évaluation de requêtes possibles. Nous avons développé la plateforme XRP, implantant les algorithmes d’évaluation de requêtes dont nous comparons les performances expérimentalement. Nous présentons une application reposant sur cette plateforme pour l’annotation automatique et manuelle de pages trouvées sur la Toile. Enfin, nous présentons une technique pour l’inférence RDFS dans les systèmes de gestion de données RDF (et par extension XR). / Since the beginning of the Semantic Web, RDF and SPARQL have become the standard data model and query language to describe resources on the Web. Large amounts of RDF data are now available either as stand-alone datasets or as metadata over semi-structured documents, typically XML. The ability to apply RDF annotations over XML data emphasizes the need to represent and query data and metadata simultaneously. While significant efforts have been invested into producing and publishing annotations manually or automatically, little attention has been devoted to exploiting such data. This thesis aims at setting database foundations for the management of hybrid XML-RDF data. We present a data model capturing the structural aspects of XML data and the semantics of RDF. Our model is general enough to describe pure XML or RDF datasets, as well as RDF-annotated XML data, where any XML node can act as a resource. We also introduce the XRQ query language that combines features of both XQuery and SPARQL. XRQ not only allows querying the structure of documents and the semantics of their annotations, but also producing annotated semi-structured data on-the-fly. We introduce the problem of query composition in XRQ, and exhaustively study query evaluation techniques for XR data to demonstrate the feasibility of this data management setting. We have developed an XR platform on top of well-known data management systems for XML and RDF. The platform features several query processing algorithms, whose performance is experimentally compared. We present an application built on top of the XR platform. The application provides manual and automatic annotation tools, and an interface to query annotated Web page and publicly available XML and RDF datasets concurrently. As a generalization of RDF and SPARQL, XR and XRQ enables RDFS-type of query answering. In this respect, we present a technique to support RDFS-entailments in RDF (and by extension XR) data management systems.

Dans cette thèse, nous proposons un cadre générique d'optimisation de requêtes dans les environnements hétérogènes répartis. Nous proposons un modèle générique de description de sources (GSD), qui permet de décrire tous les types d'informations liées au traitement et à l'optimisation de requêtes. Avec ce modèle, nous pouvons en particulier obtenir les informations de coût afin de calculer le coût des différents plans d'exécution. Notre cadre générique d'optimisation fournit les fonctions unitaires permettant de mettre en œuvre les procédures d'optimisation en appliquant différentes stratégies de recherche. Nos résultats expérimentaux mettent en évidence la précision du calcul de coût avec le modèle GSD et la flexibilité de notre cadre générique d'optimisation lors du changement de stratégie de recherche. Notre cadre générique d'optimisation a été mis en œuvre et intégré dans un produit d'intégration de données (DVS) commercialisé par l'entreprise Xcalia - Progress Software Corporation. Pour des requêtes contenant beaucoup de jointures inter-site et interrogeant des sources de grand volume, le temps de calcul du plan optimal est de l'ordre de 2 secondes et le temps d'exécution du plan optimal est réduit de 28 fois par rapport au plan initial non optimisé.

Les récents progrès réalisés en matière de communication (réseaux hauts débits, normalisation des protocoles et des architectures à objets répartis, explosion de l'internet) conduisent à l'apparition de systèmes de gestion de données et services largement répartis. Les données sont produites à la demande ou de manière continue au travers de divers dispositifs statiques ou mobiles. Cette thèse présente une approche pour l'évaluation de requêtes dites hybrides car intégrant différents aspects des données mobiles, continues, cachées rencontrées dans des environnements dynamiques. Notre approche consiste à représenter une telle requête comme une coordination de services comprenant des services de données et de calcul. Une telle coordination est définie par le flux de la requête et ceux d'opérateurs sur les données (e.g. join, select, union). Un flux de requête représente une expression construite avec les opérateurs de notre modèle de données. Ce flux est construit par un algorithme de ré-écriture à partir de la requête spécifiée dans notre langage de requête HSQL Les flux dit opérateurs composent des services de calcul afin de permettre l'évaluation d'un opérateur particulier. Le processeur de requêtes basées sur les services hybrides que nous avons développé met en mise en œuvre et valide nos propositions.

Depuis quelques années, l'évolution des terminaux nomades et des réseaux mobiles et/ou sans fil favorise le développement de nouveaux services et de nouvelles applications dédiées aux usagers mobiles. Parmi ces applications, nous définissons le concept d'applications de proximité. Celles-ci permettent à différents usagers physiquement proches les uns des autres de partager certaines de leurs informations et de localiser les données disponibles. Ces applications s'inscrivent dans un contexte fortement distribué et dynamique où l'ensemble de l'information disponible est répartie sur les terminaux des différents participants et subit de fréquentes variations dûes à la mobilité des participants. Dans cet environnement, les services de localisation actuels présentent d'importantes limites. Nous avons donc proposé ISLANDS (Information and Services LocalizAtioN and Discovery Service), un service de localisation adapté à l'environnement des applications de proximité, en particulier à la distribution de l'information. Ce service ISLANDS repose sur notre modèle d'évaluation des requêtes dépendantes de la localisation. Un exemple de requêtes dépendantes de la localisation est « quel est l'arrêt de bus le plus proche de moi ? ». Le modèle d'évaluation proposé permet de considérer la mobilité des utilisateurs et en particulier leur localisation géographique dans l'évaluation des requêtes. Ce modèle d'évaluation a été optimisé afin de pouvoir être pleinement exploité dans un environnement contraint en terme de ressources. Le processus d'évaluation d'une requête dépendante de la localisation s'articule autour de différentes étapes dont l'évaluation de la localisation géographique du client qui émet la requête. Aujourd'hui, les techniques de localisation ne sont pas toujours exploitables : par exemple, le GPS qui est la solution la plus répandue , ne fonctionne généralement pas à l'intérieur d'un bâtiment, nous proposons donc une solution de localisation reposant sur les métadonnées de l'environnement. Notre solution permet de localiser un utilisateur de façon approximative mais avec une précision suffisante pour évaluer des requêtes dépendantes de la localisation. Cette solution a été optimisée de façon à minimiser la consommation des ressources sur les terminaux nomades et à réduire le nombre de communications entre les participants. Un prototype d'ISLANDS a été implémenté et démontré aux 19èmes journées de bases de données avancées (BDA'03) dans le but de valider nos propositions.

La technologie de base de données est un environnement adéquat pour l’interaction. Elle peutconcerner plusieurs composantes du SGBD : (a) les données, (b) les requêtes, (c) les techniques d’optimisationet (d) les supports de stockage. Au niveau des données, les corrélations entre les attributs sont très communesdans les données du monde réel, et ont été exploitées pour définir les vues matérialisées et les index. Au niveaurequêtes, l’interaction a été massivement étudiée sous le problème d’optimisation multi-requêtes. Les entrepôtsde données avec leurs jointures en étoile augmentent le taux d’interaction. L’interaction des requêtes a étéemployée pour la sélection des techniques d’optimisation comme les index. L’interaction contribue égalementdans la sélection multiple des techniques d’optimisation comme les vues matérialisées, les index, lepartitionnement et le clustering. Dans les études existantes, l’interaction concerne une seule composante. Danscette thèse, nous considérons l’interaction multi-composante, avec trois techniques d’optimisation, où chacuneconcerne une composante : l’ordonnancement des requêtes (niveau requêtes), la fragmentation horizontale(niveau données) et la gestion du buffer (niveau support de stockage). L’ordonnancement des requêtes (OR)consiste à définir un ordre d’exécution optimal pour les requêtes pour permettre à quelques requêtes debénéficier des données pré-calculées. La fragmentation horizontale (FH) divise les instances de chaque relationen sous-ensembles disjoints. La gestion du buffer (GB) consiste à allouer et remplacer les données dans l’espacebuffer disponible pour réduire le coût de la charge. Habituellement, ces problèmes sont traités soit de façonisolée ou par paire comme la GB et l’OR. Cependant, ces problèmes sont similaires et complémentaires. Uneformalisation profonde pour le scénario hors-ligne et en-ligne des problèmes est fournie et un ensembled’algorithmes avancés inspirés du comportement naturel des abeilles sont proposés. Nos propositions sontvalidées en utilisant un simulateur et un SGBD réel (Oracle) avec le banc d’essai star schema benchmark àgrande échelle. / The database technology is an adequate environment for the interaction. It may concern severalcomponents of the DBMS: (a) the data, (b) the queries, (c) the optimization techniques and (d) the devices. Atthe data level, correlations between attributes are extremely common in the real world relational data, and havebeen exploited to define materialized views and indexes. At the query level, interaction has been massivelystudied under the problem of multi-query optimization. The data warehouses with their star join queriesincrease the rate of the interaction. The query interaction has been used for selecting optimization techniquessuch as indexes. The interaction also contributes in selecting multiple optimization techniques such asmaterialized views, indexes, data partitioning and the clustering. In existing studies, the interaction concernsonly one component. In this thesis, we consider the multi-component interaction, with three optimizationtechniques, where each one concerns one component: the query scheduling (query level), the horizontal datapartitioning (data level) and the buffer management (device level). The query scheduling (QS) consists indefining an optimal order of executing queries to allow some queries to get benefit from already processed data.The horizontal data partitioning (HDP) divides the instances of each relation into disjoint subsets. The buffermanagement (BM) consists in allocating and replacing data in the buffer pool to lower the cost of queries.Usually, these problems are treated either in isolation or pairwise such as BM and QS. However, these problemsare similar and complementary. A deep formalization for off-line and online scenario of these problems is givenand advanced algorithms inspired from natural bees behavior are proposed. Our proposal has been validatedusing a simulator and real DBMS (Oracle) using a large scale of star schema benchmark.

Cette thèse concerne la gestion de données de biodiversité à large échelle. Elle a pour objectifs d’optimiser les requêtes pour les chercheurs qui peuvent accéder gratuitement aux données mondiales de biodiversité. Ces données partagées par des laboratoires de recherche du monde entier, sont mises à disposition du GBIF qui les fédère et les rend accessibles aux chercheurs, décideurs, grand public. Avec une quantité importante et une croissance rapide des données et des utilisateurs qui expriment de nouveaux besoins, le GBIF est confronté à un double problème d’expressivité des requêtes et d’efficacité. Ainsi, nous proposons une solution décentralisée pour l’interrogation des données de biodiversité. La solution cumule les ressources de plusieurs machines éloignées et peu puissantes pour offrir la puissance de calcul et de stockage nécessaire pour garantir la réactivité du système pour les usagers. En outre, elle fournit une interface d’interrogation de haut niveau qui est plus expressif pour les usagers. Puis, nous mettons en œuvre un mécanisme de répartition dynamique des données à la demande. Cette approche qui est basée sur la structure des données de biodiversité et les spécificités des requêtes d’analyse des usagers, adapte dynamiquement les capacités des machines aux demandes des usagers. Ensuite, nous proposons une approche d’optimisation de requêtes qui adapte dynamiquement le placement des données et la charge de chaque machine en fonction de ses performances pour traiter les requêtes des usagers dans des délais impartis. Nous avons validé expérimentalement cette solution avec des données réelles du GBIF concernant 100 millions observations. / This thesis concerns large scale biodiversity data management. Its objectives are to optimize queries for researchers who have free access to biodiversity worldwide data. These data which are shared by worldwide research laboratories are federated in GBIF data warehouse. GBIF makes accessible its data to researchers, policy makers and general public. With a significant amount of data and a rapid growth of data and users that express new needs, the GBIF portal is facing a double problem of expressiveness of queries and of efficiency. Thus, we propose a decentralized solution for biodiversity data interrogation. Our solution combines the resources of several of remote and limited machines to provide the needed computing and storage power to ensure system responsiveness for users. It also provides high-level query interface which is more expressive for users. Then, we propose a dynamic data distribution on demand approach. This approach which is based on data properties and characteristics of users analysis queries adapts dynamically machines capacities to users demands. Then, we propose a queries optimization approach that adapts dynamically data placement and machines loads according to performances in order to process users queries within deadlines. We experimentally validated our solution with real GBIF data concerning 100 million observation data.

Nous proposons une méthode de groupement en clusters d'objets multidimensionnels étendus, basée sur un modèle de co^ut adaptatif aux requêtes, pour accélérer l'exécution des requêtes spatiales de type intervalle (e.g., intersection, inclusion). Notre travail a été motivé par l'émergence de nombreuses applications de dissémination sélective d'informations posant de nouveaux défis au domaine de l'indexation multidimensionnelle. Dans ce contexte, les approches d'indexation existantes (e.g., R-trees) ne sont pas adaptées aux besoins applicatifs tels que scalabilité (beaucoup d'objets avec des dimensions élevées et des extensions spatiales), performance de recherche (taux élevés de requêtes), performance de mise à jour (insertions et suppressions fréquentes d'objets) et adaptabilité (à la distribution des objets et des requêtes, et aux paramètres systèmes). Dans notre méthode, nous relâchons plusieurs propriétés spécifiques aux structures d'indexation arborescentes classiques (i.e. équilibrage de l'arbre et du partitionnement, englobement minimal des objets) en faveur d'une stratégie de groupement basée sur un modèle de co^ut adaptatif. Ce modèle de co^ut tient compte des caractéristiques de la plateforme d'exécution, de la distribution spatiale des objets et surtout de la distribution spatiale des requêtes. Plus précisément, la distribution des requêtes permet de déterminer les dimensions les plus sélectives et discriminantes à utiliser dans le regroupement des objets. Nous avons validé notre approche par des études expérimentales de performance impliquant de grandes collections d'objets et des requêtes d'intervalles avec des distributions uniformes et non-uniformes.