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é. / This thesis proposes a generic framework for query optimization in heterogeneous and distributed environments. We propose a generic source description model (GSD), which allows describing any type of information related to query processing and optimization. With GSD, we can use cost information to calculate the costs of execution plans. Our generic framework for query optimization provides a set of unitary functions used to perform optimization by applying different search strategies. Our experimental results show the accuracy of cost calculus when using GSD, and the flexibility of our generic framework when changing search strategies. Our proposed approach has been implemented and integrated in a data integration product (DVS) licensed by Xcalia – Progress Software Corporation. For queries with many inter-site joins accessing large size data sources, the time used for finding the optimal plan is in the order of 2 seconds, and the execution time of the optimized plan is reduced by 28 times, as compared with the execution time of the non optimized original plan.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse présente une approche pour la construction d'évaluateurs de requêtes adaptés aux besoins des applications et/ou à l'environnement d'exécution. L'approche proposée distingue trois types d'adaptation : statique (à la construction de l'évaluateur), personnalisée (avant l'exécution de requête ayant des contraintes spécifiques) et dynamique (pendant l'exécution de la requête). Nous avons présenté une analyse systématique des différentes dimensions d'un évaluateur. La principale contribution de cette thèse est un canevas d'évaluation de requêtes nommé QBF (Query Broker Framework). QBF présente les fonctionnalités d'un évaluateur de requêtes de manière abstraite et séparée dans le but de favoriser leur réutilisation et leur adaptation. En s'appuyant sur QBF, nous avons proposé les mécanismes pour assurer les trois types d'adaptation, à savoir l'instanciation de QBF, l'évaluation personnalisée et l'évaluation interactive de requêtes. Une implémentation de QBF ainsi que de quelques instances (i.e. évaluateurs) ont été réalisées. Elles nous ont permis de montrer la faisabilité de notre approche et le bénéfice de la séparation et de l'abstraction des fonctionnalités proposées dans QBF. Nous avons également mené une évaluation expérimentale des mécanismes implémentés (i.e. opérateurs, surveillances) afin de mesurer le surcoût de l'adaptation dans QBF et d'aider les programmeurs à choisir des éléments (ou composants) appropriés pour construire leurs évaluateurs.

La révolution Web 2.0 a transformé l'Internet, une infrastructure auparavant en lecture seule, en une plate-forme collaborative en lecture-écriture. La forte augmentation des donnés générées par les utilisateurs des systèmes collaboratifs constitue désormais une source considérable d'informations. Pourtant, effectuer efficacement des recherches dans un tel environnement est devenu plus difficile, en particulier lorsque ces recherches engendrent des ambiguïtés. Personnaliser les recherches permet d'éviter ces écueils en limitant les recherches au sein d'un réseau très réduit de participants ayant des intérêts similaires. Toutefois, les solutions centralisées pour mettre en œuvre cette personnalisation s'avèrent difficile compte tenu du volume important d'informations qui doit être maintenu pour chaque utilisateur. La nature dynamique de ces systèmes, dans lesquels les utilisateurs changent potentiellement souvent d'intérêt, complique la tâche. Cette thèse propose de nouveaux algorithmes permettant d'effectuer des recherches personnalisées de manière efficace dans des systèmes dynamiques, centralisés ou décentralisés, selon deux axes majeurs : (i) la personnalisation hors ligne qui s'appuie sur le comportement passé des utilisateurs et (ii) la personnalisation en ligne qui s'appuie sur le comportement passé et la requête en cours. Nous présentons d'abord l'algorithme P3K, qui décentralise une approche existante et réalise le traitement personnalisé des requêtes top-k hors ligne dans les systèmes pair-à-pair. Ensuite, nous présentons P4Q, une extension de P3K qui améliore les performances du système en termes de stockage, bande passante et la robustesse en distribuant le traitement des requêtes. Les deux algorithmes, P3K et P4Q, reposent sur des protocoles épidémiques pour capturer la similarité implicite entre les utilisateurs et associer ainsi à chaque utilisateur un "réseau personnel" dans lequel traiter la requête. Nos évaluations analytiques et expérimentales démontrent leur efficacité pour le traitement des requêtes top-k, y compris dans les systèmes dynamiques, en particulier que la capacité inhérente de P4Q à faire face aux mises à jours des profils des utilisateurs. Dans le but d'améliorer encore la qualité des résultats pour les requêtes représentant les intérêts émergents des utilisateurs, et donc non représentés dans son profil, nous proposons un modèle hybride d'intérêt, prenant en compte à la fois le profil des utilisateurs mais également la requête elle-même. Nous avons proposé une solution à la fois en centralisé, l'algorithme DT², qui effectue une recherche de type top-k à deux reprises: le premier top-k consiste à sélectionner dynamiquement un sous-réseau (le réseau personnel) le plus adapté à la requête et à l'utilisateur la générant. Le second top-k consiste à effectuer la recherche dans ce sous réseau. L'algorithme DT²P², exécute efficacement la personnalisation en ligne de manière entièrement décentralisée. Les résultats expérimentaux sur des traces réelles de systèmes collaboratifs, montrent que la personnalisation en ligne est prometteuse pour répondre aux préférences diverses des utilisateurs.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Le Web sémantique est la vision de la prochaine génération de Web proposé par Tim Berners-Lee en 2001. Avec le développement rapide des technologies du Web sémantique, de grandes quantités de données RDF existent déjà sous forme de données ouvertes et liées et ne cessent d'augmenter très rapidement. Les outils traditionnels d'interrogation et de raisonnement sur les données du Web sémantique sont conçus pour fonctionner dans un environnement centralisé. A ce titre, les algorithmes de calcul traditionnels vont inévitablement rencontrer des problèmes de performances et des limitations de mémoire. De gros volumes de données hétérogènes sont collectés à partir de différentes sources de données par différentes organisations. Ces sources de données présentent souvent des divergences et des incertitudes dont la détection et la résolution sont rendues encore plus difficiles dans le big data. Mes travaux de recherche présentent des approches et algorithmes pour une meilleure exploitation de données dans le contexte big data et du web sémantique. Nous avons tout d'abord développé une approche de résolution des identités (Entity Resolution) avec des algorithmes d'inférence et d'un mécanisme de liaison lorsque la même entité est fournie dans plusieurs ressources RDF décrite avec différentes sémantiques et identifiants de ressources URI. Nous avons également développé un moteur de réécriture de requêtes SPARQL basé le modèle MapReduce pour inférer les données implicites décrites intentionnellement par des règles d'inférence lors de l'évaluation de la requête. L'approche de réécriture traitent également de la fermeture transitive et règles cycliques pour la prise en compte de langages de règles plus riches comme RDFS et OWL. Plusieurs optimisations ont été proposées pour améliorer l'efficacité des algorithmes visant à réduire le nombre de jobs MapReduce. La deuxième contribution concerne le traitement d'incohérence dans le big data. Nous étendons l'approche présentée dans la première contribution en tenant compte des incohérences dans les données. Cela comprend : (1) La détection d'incohérence à base de règles évaluées par le moteur de réécriture de requêtes que nous avons développé; (2) L'évaluation de requêtes permettant de calculer des résultats cohérentes selon une des trois sémantiques définies à cet effet. La troisième contribution concerne le raisonnement et l'interrogation sur la grande quantité données RDF incertaines. Nous proposons une approche basée sur MapReduce pour effectuer l'inférence de nouvelles données en présence d'incertitude. Nous proposons un algorithme d'évaluation de requêtes sur de grandes quantités de données RDF probabilistes pour le calcul et l'estimation des probabilités des résultats. / Semantic Web is the vision of next generation of Web proposed by Tim Berners-Lee in 2001. Indeed, with the rapid development of Semantic Web technologies, large-scale RDF data already exist as linked open data, and their number is growing rapidly. Traditional Semantic Web querying and reasoning tools are designed to run in stand-alone environment. Therefor, Processing large-scale bulk data computation using traditional solutions will result in bottlenecks of memory space and computational performance inevitably. Large volumes of heterogeneous data are collected from different data sources by different organizations. In this context, different sources always exist inconsistencies and uncertainties which are difficult to identify and evaluate. To solve these challenges of Semantic Web, the main research contents and innovative approaches are proposed as follows. For these purposes, we firstly developed an inference based semantic entity resolution approach and linking mechanism when the same entity is provided in multiple RDF resources described using different semantics and URIs identifiers. We also developed a MapReduce based rewriting engine for Sparql query over big RDF data to handle the implicit data described intentionally by inference rules during query evaluation. The rewriting approach also deal with the transitive closure and cyclic rules to provide a rich inference language as RDFS and OWL. The second contribution concerns the distributed inconsistency processing. We extend the approach presented in first contribution by taking into account inconsistency in the data. This includes: (1)Rules based inconsistency detection with the help of our query rewriting engine; (2)Consistent query evaluation in three different semantics. The third contribution concerns the reasoning and querying over large-scale uncertain RDF data. We propose an MapReduce based approach to deal with large-scale reasoning with uncertainty. Unlike possible worlds semantic, we propose an algorithm for generating intensional Sparql query plan over probabilistic RDF graph for computing the probabilities of results within the query.

Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour lesquelles nous améliorons un résultat de Papadimitriou et Yannakakis en montrant que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de matrices booléennes ne peut pas être calculé en temps linéaire alors toute requête conjonctive acyclique est évaluable à délai constant après prétra itement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous montrons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée. D'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat.

Le thème de cette thèse concerne le domaine de la recherche d'information distribuée (RID). Un système de RID (SRID) de recherche d'information distribuée gère la recherche sur un ensemble de collections de documents distribuées soit sur un réseau local, soit sur un ensemble plus étendu. Un SRID se compose, en général, d'un courtier et d'un ensemble de serveurs. Chaque serveur détient une collection de documents et un système de recherche d'information qui assure la recherche dans cette collection. Le courtier représente la composante avec laquelle l'utilisateur communique. A la réception d'une requête, le courtier choisit un sous-ensemble de serveurs parmi ceux qu'il connaît, auxquels il achemine la requête. Cette opération est appelée sélection de serveurs. Nous proposons dans cette thèse trois méthodes de sélection de serveurs. Ces méthodes ne nécessitent aucune coopération des serveurs interrogés, et aucune mise à jour de données au niveau du courtier.

La popularisation de la technologie a permis d'implanter des dispositifs et des applications de plus en plus développés à la portée d'utilisateurs non experts. Ces systèmes produisent des flux ainsi que des données persistantes dont les schémas et les dynamiques sont hétérogènes. Cette thèse s'intéresse à pouvoir observer les données de ces systèmes pour aider à les comprendre et à les diagnostiquer. Nous proposons tout d'abord un modèle algébrique Astral capable de traiter sans ambiguïtés sémantiques des données provenant de flux ou relations. Le moteur d'exécution Astronef a été développé sur l'architecture à composants orientés services pour permettre une grande adaptabilité. Il est doté d'un constructeur de requête permettant de choisir un plan d'exécution efficace. Son extension Asteroid permet de s'interfacer avec un SGBD pour gérer des données persistantes de manière intégrée. Nos contributions sont confrontées à la pratique par la mise en œuvre d'un système d'observation du réseau domestique ainsi que par l'étude des performances. Enfin, nous nous sommes intéressés à la mise en place de la personnalisation des résultats dans notre système par l'introduction d'un modèle de préférences top-k.