Dans cette thèse, nous nous intéressons au problème de la confidentialité des données. Nous proposons une nouvelle approche pour faciliter l'administration des règles de contrôle d'accès pour assurer la confidentialité des données au niveau des vues matérialisées. Dans les bases de données relationnelles, une vue est une table virtuelle représentant le résultat d'une requête. À la différence d'une vue simple, une vue matérialisée stocke le résultat de la requête dans une table. Cette dernière peut être alors interrogée comme une table quelconque. Il est donc important d'y contrôler l'accès. Parmi les différents modèles proposés pour contrôler l'accès aux relations de base, nous nous basons dans notre approche sur l'utilisation des vues d'autorisations pour exprimer des règles de contrôle d'accès à grains fins. Nous proposons d'inférer, à partir des vues d'autorisations attachées aux tables de base, les vues d'autorisations qui doivent être attachées aux vues matérialisées. Répondre à ce problème revient à répondre à un problème fondamental dans les bases de données relationnelles : Comment caractériser les informations calculables à partir de deux ensembles de vues ? Nous répondons à cette question en nous appuyant sur la réécriture de requêtes. Nous adaptons l'algorithme de réécriture de requêtes M iniCon aux spécificités de notre problème et nous proposons l'algorithme 1-l M iniCon+ qui se base sur un enchainement de réécritures. Nous nous intéressons aux vues représentées par des requêtes conjonctives en autorisant les égalités. Nous nous sommes intéressés par la suite aux propriétés de cet algorithme. Nous démontrons que cet algorithme permet de calculer un ensemble de vues correctes, c.-à-d. toute information calculable à partir de l'ensemble de vues générées est cal­ culable à partir de chacun des deux ensembles de vues de départ / In this thesis, we address the problem of data confidentiality. We propose a new approach to facilitate the administration of access control policies to ensure confidentiality of data in materialized views. In relational databases, a view is a virtual table representing the result of a query. Unlike a simple view, a materialized view persistently stores the data in a table. The latter can be queried like any other database table. We then need to control the access to the materialized view. Among the various models proposed for controlling access to base relations, we choose to express fine-grained access control through authorization views. We propose to infer, from the basic authorization views attached to the base tables, authorization views that will be attached to the materialized views. Tackling this problem amounts to address a fundamental problem in relational databases : How to characterize computable information from two sets of views ? We handle this problem by resorting to query rewriting. We adapt the query rewriting algorithm MiniCon to the context of materialized views with access control and propose the H MiniCon+ algorithm which is based on successive rewritings. We mainly consider conjunctive queries with equalities. We study the properties of our approach. We show that our algorithm can calculate a correct set of views, i.e. any computable information from the generated views is calculable from the two sets of views. In order to prove the termination of our algorithm, we define rewriting trees generated by the application of 1-l MiniCon+ and we study their features. We characterize in which case a tree is finite and show that the approach is maximal, i.e., any derivable information from the two sets of views can be derived from the set of generated views. We characterize in which case the algorithm could not terminate i.e., infinite application of the query rewriting algorithm. In this case, it is impossible to determine the maximality of results and this remains an open problem. We implemented a prototype of the approach and we led some experiments by using synthetic data sets

La complexité et la dynamique de l'environnement dans lequel évolue chaque entreprise requiert de la part de ses managers la capacité de prendre des décisions pertinentes dans un laps de temps très court afin de s'accroître. Pour cela, l'analyse des données générées par l'activité de l'entreprise peut être une précieuse source d'information. L'Intelligence Opérationnelle (IO) est une classe de systèmes d'aide à la décision permettant aux managers d'avoir une très bonne compréhension de la situation de l'entreprise, à travers l'analyse de l'activité passée et présente. Dans ce contexte, les notions de temps et de traçabilité sont primordiales dans la compréhension de l'évolution de l'activité de l'entreprise à travers le temps. Dans cette thèse, nous présentons Axway Decision Insight (ADI), une solution d'IO développée par Axway. Son composant clé est un SGBD orienté-colonnes et bi-temporel développé en interne par l'entreprise pour répondre aux besoins spécifiques de l'IO. Ses capacités bi-temporelles lui permettent de gérer nativement aussi bien l'évolution des données dans la réalité modélisée (temps de validité) que l'évolution des données dans la base de données (temps de transaction). Nous commencerons par présenter la solution ADI en nous focalisant sur deux éléments importants: 1) l'interface graphique qui permet la conception et l'utilisation d'ADI sans écrire la moindre ligne de code. 2) L'approche adoptée pour modéliser les données bi-temporelles. Ensuite, nous présenterons un benchmark bi-temporel destiné ADI.Après cela, nous présenterons deux optimisations pour ADI. La première permet de pré-calculer et matérialiser les opérations d'agrégation, ce qui permet de réduire le temps nécessaire à la mise à jour de interface graphique d'ADI. La deuxième optimisation ordonne l'exécution des opérateurs de jointure des plans de requêtes en utilisant un modèle coût basé sur des statistiques sur des données bi-temporelles. Pour ces optimisations, nous avons effectué des expérimentations en utilisant notre benchmark, et qui ont démontré leurs intérêts. / Nowadays, every company is operating in very dynamic and complex environments which require from its managers to have a deep understanding of its business in order to take rapid and relevant decisions, and thus maintain or improve their company's activities. They can rely on analyzing the data deluge generated by the company's activities. A new class of systems has emerged in the decision support system galaxy called "Operational Intelligence" (OI) to meet this challenge. The objective is to enable operational managers to understand what happened in the past as well as what is currently happening in their business. In this context, the notions of time and traceability turns out to play a crucial role to understand what happened in the company and what is currently happening in the company. In this thesis, we present "Axway Decision Insight" (ADI), an "Operational Intelligence" solution developed by Axway. ADI's key component is a proprietary bi-temporal and column-oriented DBMS that has specially been designed to meet OI requirements. Its bi-temporal capabilities enable to catch both data evolution in the modeled reality (valid time) and in the database (transaction time).We first introduce ADI by focusing on two topics: 1) the GUI that makes the platform "code-free". 2) The adopted bi-temporal modeling approaches. Then we propose a performance benchmark that meets ADI's requirements. Next, we present two bi-temporal query optimizations for ADI. The first one consists in redefining a complex bi-temporal query into: 1) a set of continuous queries in charge of computing aggregation operations as data is collected. 2) A bi-temporal query that accesses the continuous queries' results and feeds the GUI. The second one is a cost-based optimization that uses statistics on bi-temporal data to determine an "optimal" query plan. For these two optimizations, we conducted some experiments, using our benchmark, which show their interests.

Cette thèse porte sur la mise en place d'un système de requêtage sur des flux sous contraintes de capacités. Ce système est porté par ses utilisateurs-trices et basé sur les similitudes entre requêtes. Les relations d'équivalences entre les différentes requêtes permettent de réunir les participants au sein de communautés d'intérêt. Celles-ci forment alors une abstraction permettant de séparer le problème d'organisation du système en plusieurs sous-problèmes plus simples et de taille réduite. Afin de garantir une généricité vis-à-vis du langage, l'organisation repose sur une API simple et modulable. Nous avons ainsi recours au mécanisme de réécritures de requêtes utilisant des vues matérialisées, connu en bases de données, pour déterminer les relations possibles entre les communautés. Le choix entre ces différentes possibilités est ensuite effectué à l'aide d'un modèle de coût paramétrable. Les relations entre communautés sont concrétisées par un échange de ressources entre elles, un participant de l'une venant contribuer à l'autre. Cela permet de s'affranchir des limitations de capacités au niveau abstrait, tout en en tenant hautement compte pour la mise en relation effective des participants. Au sein des communautés, un arbre de diffusion permet à l'ensemble des participants de récupérer les résultats requis. L'approche, mise en œuvre de manière incrémentale, permet une réduction efficace des coûts de calcul et de diffusion (l'optimalité est atteinte, notamment, dans le cas de l'inclusion de requête) pour un coût d'organisation limité et une latence raisonnable. Les expérimentations réalisées ont montré une grande adaptabilité aux variations concernant les requêtes exprimées et les capacités des participants. Le démonstrateur mis en place peut être utilisé à la fois pour des simulations (automatiques ou interactives) et pour un déploiement réel, par une implémentation commune générique vis-à-vis du langage. / This thesis addresses the problem of the organization of querying system on data streams under capacity constraints, such system being user-powered and based on the queries' similarity. Equivalence relations between queries allow to group the participants into communities. Those communities are then used as an abstraction to split the general organization problem into several easier and smaller subproblems. In order to stay language-independent, the organization is based on a simple and modular API, that rely on a query answering using views mechanism, well known in databases. Choice between the different rewritten queries is done using an adjustable cost model. Relations between communities are thus materialized by a spreading mechanism, a participant from one community joining the other(s) to contribute. This allows to avoid the capacities problem on the organization's abstract level, while efficiently taking care of it on the concrete one. Inside the communities, all the participants receive the common results they need using a spanning tree. The QTor approach, incrementally built, allows an efficient reduce of the processing and diffusion costs (processing cost being optimal in some cases, e.g. containment) with a reasonable latency, for a limited organization cost. Experiments have shown that the organization is flexible, regarding both the expressed queries and the participants' capacities. A demonstrator was built, allowing to both perform (automatic or interactive) simulations, and deploy the system over a real network, with a single.

L’externalisation de données d’entreprise ou individuelles chez un fournisseur de cloud, par exemple avec l’approche Database-as-a-Service, est pratique et rentable. Mais elle introduit un problème majeur: comment préserver la confidentialité des données externalisées, tout en prenant en charge les requêtes expressives des utilisateurs. Une solution simple consiste à crypter les données avant leur externalisation. Ensuite, pour répondre à une requête, le client utilisateur peut récupérer les données cryptées du cloud, les décrypter et évaluer la requête sur des données en texte clair (non cryptées). Cette solution n’est pas pratique, car elle ne tire pas parti de la puissance de calcul fournie par le cloud pour évaluer les requêtes.Dans cette thèse, nous considérons un type important de requêtes, les requêtes top-k, et le problème du traitement des requêtes top-k sur des données cryptées dans le cloud, tout en préservant la vie privée. Une requête top-k permet à l’utilisateur de spécifier un nombre k de tuples les plus pertinents pour répondre à la requête. Le degré de pertinence des tuples par rapport à la requête est déterminé par une fonction de notation.Nous proposons d’abord un système complet, appelé BuckTop, qui est capable d’évaluer efficacement les requêtes top-k sur des données cryptées, sans avoir à les décrypter dans le cloud. BuckTop inclut un algorithme de traitement des requêtes top-k qui fonctionne sur les données cryptées, stockées dans un nœud du cloud, et retourne un ensemble qui contient les données cryptées correspondant aux résultats top-k. Il est aidé par un algorithme de filtrage efficace qui est exécuté dans le cloud sur les données chiffrées et supprime la plupart des faux positifs inclus dans l’ensemble renvoyé. Lorsque les données externalisées sont volumineuses, elles sont généralement partitionnées sur plusieurs nœuds dans un système distribué. Pour ce cas, nous proposons deux nouveaux systèmes, appelés SDB-TOPK et SD-TOPK, qui permettent d’évaluer les requêtes top-k sur des données distribuées cryptées sans avoir à les décrypter sur les nœuds où elles sont stockées. De plus, SDB-TOPK et SD-TOPK ont un puissant algorithme de filtrage qui filtre les faux positifs autant que possible dans les nœuds et renvoie un petit ensemble de données cryptées qui seront décryptées du côté utilisateur. Nous analysons la sécurité de notre système et proposons des stratégies efficaces pour la mettre en œuvre.Nous avons validé nos solutions par l’implémentation de BuckTop, SDB-TOPK et SD-TOPK, et les avons comparé à des approches de base par rapport à des données synthétiques et réelles. Les résultats montrent un excellent temps de réponse par rapport aux approches de base. Ils montrent également l’efficacité de notre algorithme de filtrage qui élimine presque tous les faux positifs. De plus, nos systèmes permettent d’obtenir une réduction significative des coûts de communication entre les nœuds du système distribué lors du calcul du résultat de la requête. / Outsourcing corporate or individual data at a cloud provider, e.g. using Database-as-a-Service, is practical and cost-effective. But it introduces a major problem: how to preserve the privacy of the outsourced data, while supporting powerful user queries. A simple solution is to encrypt the data before it is outsourced. Then, to answer a query, the user client can retrieve the encrypted data from the cloud, decrypt it, and evaluate the query over plaintext (non encrypted) data. This solution is not practical, as it does not take advantage of the computing power provided by the cloud for evaluating queries.In this thesis, we consider an important kind of queries, top-k queries,and address the problem of privacy-preserving top-k query processing over encrypted data in the cloud.A top-k query allows the user to specify a number k, and the system returns the k tuples which are most relevant to the query. The relevance degree of tuples to the query is determined by a scoring function.We first propose a complete system, called BuckTop, that is able to efficiently evaluate top-k queries over encrypted data, without having to decrypt it in the cloud. BuckTop includes a top-k query processing algorithm that works on the encrypted data, stored at one cloud node,and returns a set that is proved to contain the encrypted data corresponding to the top-k results. It also comes with an efficient filtering algorithm that is executed in the cloud on encypted data and removes most of the false positives included in the set returned.When the outsourced data is big, it is typically partitioned over multiple nodes in a distributed system. For this case, we propose two new systems, called SDB-TOPK and SD-TOPK, that can evaluate top-k queries over encrypted distributed data without having to decrypt at the nodes where they are stored. In addition, SDB-TOPK and SD-TOPK have a powerful filtering algorithm that filters the false positives as much as possible in the nodes, and returns a small set of encrypted data that will be decrypted in the user side. We analyze the security of our system, and propose efficient strategies to enforce it.We validated our solutions through implementation of BuckTop , SDB-TOPK and SD-TOPK, and compared them to baseline approaches over synthetic and real databases. The results show excellent response time compared to baseline approaches. They also show the efficiency of our filtering algorithm that eliminates almost all false positives. Furthermore, our systems yieldsignificant reduction in communication cost between the distributed system nodes when computing the query result.

La matérialisation de vues est une technique très utilisée dans les systèmes de gestion bases de données ainsi que dans les entrepôts de données pour améliorer les performances des requêtes. Elle permet de réduire de manière considérable le temps de réponse des requêtes en pré-calculant des requêtes coûteuses et en stockant leurs résultats. De ce fait, l'exécution de certaines requêtes nécessite seulement un accès aux vues matérialisées au lieu des données sources. En contrepartie, la matérialisation entraîne un surcoût de maintenance des vues. En effet, les vues matérialisées doivent être mises à jour lorsque les données sources changent afin de conserver la cohérence et l'intégrité des données. De plus, chaque vue matérialisée nécessite également un espace de stockage supplémentaire qui doit être pris en compte au moment de la sélection. Le problème de choisir quelles sont les vues à matérialiser de manière à réduire les coûts de traitement des requêtes étant donné certaines contraintes tel que l'espace de stockage et le coût de maintenance, est connu dans la littérature sous le nom du problème de la sélection de vues. Trouver la solution optimale satisfaisant toutes les contraintes est un problème NP-complet. Dans un contexte distribué constitué d'un ensemble de noeuds ayant des contraintes de ressources différentes (CPU, IO, capacité de l'espace de stockage, bande passante réseau, etc.), le problème de la sélection des vues est celui de choisir un ensemble de vues à matérialiser ainsi que les noeuds du réseau sur lesquels celles-ci doivent être matérialisées de manière à optimiser les coût de maintenance et de traitement des requêtes.Notre étude traite le problème de la sélection de vues dans un environnement centralisé ainsi que dans un contexte distribué. Notre objectif est de fournir une approche efficace dans ces contextes. Ainsi, nous proposons une solution basée sur la programmation par contraintes, connue pour être efficace dans la résolution des problèmes NP-complets et une méthode puissante pour la modélisation et la résolution des problèmes d'optimisation combinatoire. L'originalité de notre approche est qu'elle permet une séparation claire entre la formulation et la résolution du problème. A cet effet, le problème de la sélection de vues est modélisé comme un problème de satisfaction de contraintes de manière simple et déclarative. Puis, sa résolution est effectuée automatiquement par le solveur de contraintes. De plus, notre approche est flexible et extensible, en ce sens que nous pouvons facilement modéliser et gérer de nouvelles contraintes et mettre au point des heuristiques pour un objectif d'optimisation.Les principales contributions de cette thèse sont les suivantes. Tout d'abord, nous définissons un cadre qui permet d'avoir une meilleure compréhension des problèmes que nous abordons dans cette thèse. Nous analysons également l'état de l'art des méthodes de sélection des vues à matérialiser en en identifiant leurs points forts ainsi que leurs limites. Ensuite, nous proposons une solution utilisant la programmation par contraintes pour résoudre le problème de la sélection de vues dans un contexte centralisé. Nos résultats expérimentaux montrent notre approche fournit de bonnes performances. Elle permet en effet d'avoir le meilleur compromis entre le temps de calcul nécessaire pour la sélection des vues à matérialiser et le gain de temps de traitement des requêtes à réaliser en matérialisant ces vues. Enfin, nous étendons notre approche pour résoudre le problème de la sélection de vues à matérialiser lorsque celui-ci est étudié sous contraintes de ressources multiples dans un contexte distribué. A l'aide d'une évaluation de performances extensive, nous montrons que notre approche fournit des résultats de qualité et fiable. / View selection is important in many data-intensive systems e.g., commercial database and data warehousing systems to improve query performance. View selection can be defined as the process of selecting a set of views to be materialized in order to optimize query evaluation. To support this process, different related issues have to be considered. Whenever a data source is changed, the materialized views built on it have to be maintained in order to compute up-to-date query results. Besides the view maintenance issue, each materialized view also requires additional storage space which must be taken into account when deciding which and how many views to materialize.The problem of choosing which views to materialize that speed up incoming queries constrained by an additional storage overhead and/or maintenance costs, is known as the view selection problem. This is one of the most challenging problems in data warehousing and it is known to be a NP-complete problem. In a distributed environment, the view selection problem becomes more challenging. Indeed, it includes another issue which is to decide on which computer nodes the selected views should be materialized. The view selection problem in a distributed context is now additionally constrained by storage space capacities per computer node, maximum global maintenance costs and the communications cost between the computer nodes of the network.In this work, we deal with the view selection problem in a centralized context as well as in a distributed setting. Our goal is to provide a novel and efficient approach in these contexts. For this purpose, we designed a solution using constraint programming which is known to be efficient for the resolution of NP-complete problems and a powerful method for modeling and solving combinatorial optimization problems. The originality of our approach is that it provides a clear separation between formulation and resolution of the problem. Indeed, the view selection problem is modeled as a constraint satisfaction problem in an easy and declarative way. Then, its resolution is performed automatically by the constraint solver. Furthermore, our approach is flexible and extensible, in that it can easily model and handle new constraints and new heuristic search strategies for optimization purpose. The main contributions of this thesis are as follows. First, we define a framework that enables to have a better understanding of the problems we address in this thesis. We also analyze the state of the art in materialized view selection to review the existing methods by identifying respective potentials and limits. We then design a solution using constraint programming to address the view selection problem in a centralized context. Our performance experimentation results show that our approach has the ability to provide the best balance between the computing time to be required for finding the materialized views and the gain to be realized in query processing by materializing these views. Our approach will also guarantee to pick the optimal set of materialized views where no time limit is imposed. Finally, we extend our approach to provide a solution to the view selection problem when the latter is studied under multiple resource constraints in a distributed context. Based on our extensive performance evaluation, we show that our approach outperforms the genetic algorithm that has been designed for a distributed setting.

La recherche sémantique de l'information a connu un nouvel essor avec les nouvelles technologies du Web sémantique. Des langages standards permettent aujourd'hui aux logiciels de communiquer par le biais de données écrites dans le vocabulaire d'ontologies de domaine décrivant une sémantique explicite. Cet accès ``sémantique'' à l'information requiert la disponibilité de bases de connaissances décrivant les instances des ontologies de domaine. Cependant, ces bases de connaissances, bien que de plus en plus riches, contiennent relativement peu d'information par comparaison au volume des informations contenu dans les documents du Web.La recherche sémantique de l'information atteint ainsi certaines limites par comparaison à la recherche classique de l'information qui exploite plus largement ces documents. Ces limites se traduisent explicitement par l'absence d'instances de concepts et de relations dans les bases de connaissances construites à partir des documents du Web. Dans cette thèse nous étudions deux directions de recherche différentes afin de permettre de répondre à des requêtes sémantiques dans de tels cas. Notre première étude porte sur la reformulation des requêtes sémantiques des utilisateurs afin d'atteindre des parties de document pertinentes à la place des faits recherchés et manquants dans les bases de connaissances. La deuxième problématique que nous étudions est celle de l'enrichissement des bases de connaissances par des instances de relations.Nous proposons deux solutions pour ces problématiques en exploitant des documents semi-structurés annotés par des concepts ou des instances de concepts. Un des points clés de ces solutions est qu'elles permettent de découvrir des instances de relations sémantiques sans s'appuyer sur des régularités lexico-syntaxiques ou structurelles dans les documents. Nous situons ces deux approches dans la littérature et nous les évaluons avec plusieurs corpus réels extraits du Web. Les résultats obtenus sur des corpus de citations bibliographiques, des corpus d'appels à communication et des corpus géographiques montrent que ces solutions permettent effectivement de retrouver de nouvelles instances relations à partir de documents hétérogènes tout en contrôlant efficacement leur précision. / Semantic information retrieval has known a rapid development with the new Semantic Web technologies. With these technologies, software can exchange and use data that are written according to domain ontologies describing explicit semantics. This ``semantic'' information access requires the availability of knowledge bases describing both domain ontologies and their instances. The most often, these knowledge bases are constructed automatically by annotating document corpora. However, while these knowledge bases are getting bigger, they still contain much less information when comparing them with the HTML documents available on the surface Web.Thus, semantic information retrieval reaches some limits with respect to ``classic'' information retrieval which exploits these documents at a bigger scale. In practice, these limits consist in the lack of concept and relation instances in the knowledge bases constructed from the same Web documents. In this thesis, we study two research directions in order to answer semantic queries in such cases. The first direction consists in reformulating semantic user queries in order to reach relevant document parts instead of the required (and missing) facts. The second direction that we study is the automatic enrichment of knowledge bases with relation instances.We propose two novel solutions for each of these research directions by exploiting semi-structured documents annotated with concept instances. A key point of these solutions is that they don't require lexico-syntactic or structure regularities in the documents. We position these approaches with respect to the state of the art and experiment them on several real corpora extracted from the Web. The results obtained from bibliographic citations, call-for-papers and geographic corpora show that these solutions allow to retrieve new answers/relation instances from heterogeneous documents and rank them efficiently according to their precision.

Ce travail de thèse porte sur l’exploitation des données temporelles en présence d’imperfections. Il s’agit de définir, concevoir et développer un système intelligent pour l’interrogation des bases de données temporelles où la dimension temps (des relations ou des entités) est définie d’une manière imprécise et floue. Ce type de base de données se manifeste fréquemment dans les applications issues du domaine médical, de l’historique et de l’archive, de la planification, etc.Nous rappelons tout d’abord les différents formalismes utilisés dans le traitement des informations temporelles, puis, nous présentons les travaux antérieurs qui ont abordé la problématique de la gestion et de traitement de l’information temporelle imparfaite dans le domaine des bases de données. Nous décrivons ensuite une première contribution apportée sur la définition d’un nouveau modèle de représentation de données temporelles entachées d’imprécision. Des relations d’Allen étendues ont été introduites ainsi qu’un ensemble de règles de composition permettant de raisonner. Cette contribution a permis de développer un premier prototype nommé Fuzz-TIME pour le traitement des requêtes contenant des critères temporels flous/imprécis. Un des points forts de ce système est qu’il possède un module de raisonnement lui permettant de traiter, d’une manière intelligente, une famille de requêtes temporelles de nature complexe.La plupart des travaux menés sur l’exploitation et la manipulation des informations temporelles considèrent que les entités temporelles (i.e., intervalles) sont définies d’une manière précise (non floue). Or dans le monde des applications réelles, les bornes des intervalles de temps manipulés sont souvent entachées d’imprécision. Nous avons ainsi proposé une nouvelle sémantique des relations temporelles d’Allen (i.e., relations d’Allen tolérantes) dans ce contexte. L’élément clé de cette sémantique est une relation de tolérance convenablement choisie. Une troisième partie de notre travail est consacrée à la modélisation d’une nouvelle extension des relations temporelles d’Allen où les intervalles de temps sont interprétés d’une manière conjonctive. Enfin, nous décrivons l’architecture du système Fuzz-TIME et discutons l’étude expérimentale menée pour valider les contributions proposées. / This work focuses on the exploitation of temporal data in presence of imperfections. The aim is to define, design and develop an intelligent system for the interrogation of temporal databases where the time dimension (of relationships or entities) is defined in an imprecise and fuzzy way. This type of databases is frequently found in applications from the medical field, history and archive, planning, etc.We first recall the different formalisms used in the processing of temporal in formation, and then we present the previous work which has addressed the problem of managing and processing of imperfect temporal information in the field of databases.We describe then a first contribution related to the definition of a new model for the representation of imprecise temporal data. Extended Allen relations have been introduced as well as a set of composition rules for reasoning. This contribution has allowed developing a first prototype called Fuzz-TIME for processing queries containing fuzzy /imprecise time criteria. One of the major interests of this system is that it exhibits a reasoning module to intelligently process a family of temporal queries of a complex nature.Most work on the exploitation and manipulation of temporal in formation considers that the temporal entities (i.e.,intervals) are defined in a precise (non-fuzzy) manner. ln the world of real applications, the bounds of the manipulated time intervals are often pervaded by imprecision. We have proposed a new semantics of Allen's temporal relations (i .e., Allen Tolerant Relations) in this context. The key element of this semantics is a suitably chosen relationship of tolerance. A third part of our work is devoted to the modeling of a new extension of Allen's temporal relations where the time intervals are interpreted in a conjunctive way. Finally, we describe the architecture of the Fuzz-TIME system and discuss the experimental study carried out to validate the proposed contributions.

Ces dernières années, la popularité croissante des applications, e.g. les expériences scientifiques, Internet des objets et les réseaux sociaux, a conduit à la génération de gros volumes de données. La gestion de telles données qui de plus, sont hétérogènes et distribuées à grande échelle, constitue un défi important. Dans les systèmes traditionnels tels que les systèmes distribués et parallèles, les systèmes pair-à-pair et les systèmes de grille, répondre à des objectifs tels que l'obtention de performances acceptables tout en garantissant une bonne disponibilité de données constituent des objectifs majeurs pour l'utilisateur, en particulier lorsque ces données sont réparties à travers le monde. Dans ce contexte, la réplication de données, une technique très connue, permet notamment: (i) d'augmenter la disponibilité de données, (ii) de réduire les coûts d'accès aux données et (iii) d'assurer une meilleure tolérance aux pannes. Néanmoins, répliquer les données sur tous les nœuds est une solution non réaliste vu qu'elle génère une consommation importante de la bande passante en plus de l'espace limité de stockage. Définir des stratégies de réplication constitue la solution à apporter à ces problématiques. Les stratégies de réplication de données qui ont été proposées pour les systèmes traditionnels cités précédemment ont pour objectif l'amélioration des performances pour l'utilisateur. Elles sont difficiles à adapter dans les systèmes de cloud. En effet, le fournisseur de cloud a pour but de générer un profit en plus de répondre aux exigences des locataires. Satisfaire les attentes de ces locataire en matière de performances sans sacrifier le profit du fournisseur d'un coté et la gestion élastiques des ressources avec une tarification suivant le modèle 'pay-as-you-go' d'un autre coté, constituent des principes fondamentaux dans les systèmes cloud. Dans cette thèse, nous proposons une stratégie de réplication de données pour satisfaire les exigences du locataire, e.g. les performances, tout en garantissant le profit économique du fournisseur. En se basant sur un modèle de coût, nous estimons le temps de réponse nécessaire pour l'exécution d'une requête distribuée. La réplication de données n'est envisagée que si le temps de réponse estimé dépasse un seuil fixé auparavant dans le contrat établi entre le fournisseur et le client. Ensuite, cette réplication doit être profitable du point de vue économique pour le fournisseur. Dans ce contexte, nous proposons un modèle économique prenant en compte aussi bien les dépenses et les revenus du fournisseur lors de l'exécution de cette requête. Nous proposons une heuristique pour le placement des répliques afin de réduire les temps d'accès à ces nouvelles répliques. De plus, un ajustement du nombre de répliques est adopté afin de permettre une gestion élastique des ressources. Nous validons la stratégie proposée par une évaluation basée sur une simulation. Nous comparons les performances de notre stratégie à celles d'une autre stratégie de réplication proposée dans les clouds. L'analyse des résultats obtenus a montré que les deux stratégies comparées répondent à l'objectif de performances pour le locataire. Néanmoins, une réplique de données n'est crée, avec notre stratégie, que si cette réplication est profitable pour le fournisseur. / In recent years, growing popularity of large-scale applications, e.g. scientific experiments, Internet of things and social networking, led to generation of large volumes of data. The management of this data presents a significant challenge as the data is heterogeneous and distributed on a large scale. In traditional systems including distributed and parallel systems, peer-to-peer systems and grid systems, meeting objectives such as achieving acceptable performance while ensuring good availability of data are major challenges for service providers, especially when the data is distributed around the world. In this context, data replication, as a well-known technique, allows: (i) increased data availability, (ii) reduced data access costs, and (iii) improved fault-tolerance. However, replicating data on all nodes is an unrealistic solution as it generates significant bandwidth consumption in addition to exhausting limited storage space. Defining good replication strategies is a solution to these problems. The data replication strategies that have been proposed for the traditional systems mentioned above are intended to improve performance for the user. They are difficult to adapt to cloud systems. Indeed, cloud providers aim to generate a profit in addition to meeting tenant requirements. Meeting the performance expectations of the tenants without sacrificing the provider's profit, as well as managing resource elasticities with a pay-as-you-go pricing model, are the fundamentals of cloud systems. In this thesis, we propose a data replication strategy that satisfies the requirements of the tenant, such as performance, while guaranteeing the economic profit of the provider. Based on a cost model, we estimate the response time required to execute a distributed database query. Data replication is only considered if, for any query, the estimated response time exceeds a threshold previously set in the contract between the provider and the tenant. Then, the planned replication must also be economically beneficial to the provider. In this context, we propose an economic model that takes into account both the expenditures and the revenues of the provider during the execution of any particular database query. Once the data replication is decided to go through, a heuristic placement approach is used to find the placement for new replicas in order to reduce the access time. In addition, a dynamic adjustment of the number of replicas is adopted to allow elastic management of resources. Proposed strategy is validated in an experimental evaluation carried out in a simulation environment. Compared with another data replication strategy proposed in the cloud systems, the analysis of the obtained results shows that the two compared strategies respond to the performance objective for the tenant. Nevertheless, a replica of data is created, with our strategy, only if this replication is profitable for the provider.

Les systèmes d'information font face à un problème de pertinence dans les recherches dû à l'augmentation considérable des données accessibles. De plus, le nombre d'appareils communicants ne cesse de croître et de menacer le modèle client/serveur. Une nouvelle architecture distribuée tend donc à s'imposer : les réseaux pair-à-pair (P2P). Mais ils sont peu économes en ressource réseau (une requête inonde le réseau) et offrent des fonctionnalités limitées (recherche par mots-clés). Dans les deux communautés, RI et systèmes P2P, les recherches penchent vers l'utilisation de sémantique. En informatique, les approches basées sur la sémantique nécessitent souvent de définir des ontologies. Le développement important et distribué des ontologies génère une hétérogénéité sémantique. La solution classique est d'utiliser des correspondances entre parties de deux ontologies. Mais c'est une solution qui est difficile à obtenir et qui n'est pas toujours complète. Souvent les parties non-partagées de deux ontologies ne sont pas gérées, ce qui entraîne une perte d'information. Notre solution : EXSI2D, utilise une expansion particulière, appelée expansion structurante, du côté de l'initiateur de requêtes. Cela lui permet de préciser les dimensions de sa requête sans modifier la requête elle-même. EXSI2D offre aussi la possibilité au fournisseur d'information d'interpréter l'expansion structurante dans sa propre ontologie. Ainsi, il est possible à chaque participant d'un système d'information sémantiquement hétérogène d'utiliser toute son ontologie, y compris les parties non partagées. Nous montrons aussi l'utilisation d'EXSI2D dans un système P2P, grâce à SPARTANBFS, un protocole « frugal » pour systèmes P2P non structurés.

RDF est un langage de représentation des connaissances dédié à l'annotation des ressources dans le Web Sémantique. Bien que RDF peut être lui-même utilisé comme un langage de requêtes pour interroger une base de connaissances RDF (utilisant la conséquence RDF), la nécessité d'ajouter plus d'expressivité dans les requêtes a conduit à définir le langage de requêtes SPARQL. Les requêtes SPARQL sont définies à partir des patrons de graphes qui sont fondamentalement des graphes RDF avec des variables. Les requêtes SPARQL restent limitées car elles ne permettent pas d'exprimer des requêtes avec une séquence non-bornée de relations (par exemple, Existe-t-il un itinéraire d'une ville A à une ville B qui n'utilise que les trains ou les bus?"). Nous montrons qu'il est possible d'étendre la syntaxe et la sémantique de RDF, définissant le langage PRDF (pour Path RDF) afin que SPARQL puisse surmonter cette limitation en remplaçant simplement les patrons de graphes basiques par des graphes PRDF. Nous étendons aussi PRDF à CPRDF (pour Constrained Path RDF) permettant d'exprimer des contraintes sur les sommets des chemins traversés (par exemple, "En outre, l'une des correspondances doit fournir une connexion sans fil."). Nous avons fourni des algorithmes corrects et complets pour répondre aux requêtes (la requête est un graphe PRDF ou CPRDF, la base de connaissances est un graphe RDF) basés sur un homomorphisme particulier, ainsi qu'une analyse détaillée de la complexité. Enfin, nous utilisons les graphes PRDF ou CPRDF pour généraliser les requêtes SPARQL, définissant les extensions PSPARQL et CPSPARQL, et fournissons des tests expérimentaux en utilisant une implémentation complète de ces deux langages.