Présentation d'une telle interface (IMREL) permettant la transformation des structures de base de données hiérarchiques (IMAGE) afin de la consulter de manière relationnelle. Proposition d'une stratégie d'optimisation de requête par la recherche du chemin de cout minimal. Réalisation d'un compilateur de requête (CORREL).

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

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

Les travaux présentés dans cette thèse traitent des apports de l'algorithmique génétique à la conception de systèmes de recherche d'information adaptatifs aux besoins des utilisateurs.<br>Notre étude se focalise en premier lieu, sur l'analyse des différents modèles et stratégies de représentation et de recherche d'information. Nous mettons notamment en évidence, leur contribution à la résolution des problèmes inhérents à la recherche d'information. <br>En second lieu, notre intérêt s'est porté sur l'étude des algorithmes génétiques. Nous basant alors sur leur robustesse, théoriquement et expérimentalement prouvée, nous intégrons ces algorithmes à la mise en oeuvre de notre approche d'optimisation de requête.<br>Nous présentons une approche de recherche d'information qui intègre une stratégie de reformulation de requête par injection de pertinence, fondée sur l'hybridation d'un processus d'optimisation génétique, à un modèle de recherche de base. Nous proposons un algorithme spécifique à la recherche d'information, par l'intégration d'opérateurs génétiques augmentés par la connaissance du domaine d'une part, et d'une heuristique permettant de résoudre le problème de multimodalité de la pertinence d'autre part. L'heuristique de nichage en l'occurrence, est diffusée globalement lors de l'évolution de l'AG. La population est alors organisée en niches de requêtes effectuant une recherche parallèle et coopérative d'informations.<br>Nous évaluons enfin notre approche de recherche d'information, au travers d'expérimentations réalisées à l'aide du système Mercure, sur la collection de référence TREC.

XML probabiliste est un modèle probabiliste pour les bases de données incertaines semi-structurées, avec des applications telles que l'intégration incertaine de données, l'extraction d'informations ou le contrôle probabiliste de versions. Nous explorons dans cette thèse une solution efficace pour l'évaluation des requêtes tree-pattern avec jointures sur ces documents, ou, plus précisément, pour l'approximation de la probabilité d'une requête booléenne sur un document probabiliste. L'approche repose sur, d'une part, la production de la provenance probabiliste de la requête posée, et, d'autre part, la recherche d'une stratégie optimale pour estimer la probabilité de cette provenance. Cette deuxième partie s'inspire des approches des optimiseurs de requêtes: l'exploration de différents plans d'évaluation pour différentes parties de la formule et l'estimation du coût de chaque plan, suivant un modèle de coût établi pour les algorithmes de calcul utilisés. Nous démontrons l'efficacité de cette approche sur des jeux de données utilisés dans des travaux précédents sur l'interrogation des bases de données XML probabilistes, ainsi que sur des données synthétiques. / Probabilistic XML is a probabilistic model for uncertain tree-structured data, with applications to data integration, information extraction, or uncertain version control. We explore in this dissertation efficient algorithms for evaluating tree-pattern queries with joins over probabilistic XML or, more specifically, for approximating the probability of each item of a query result. The approach relies on, first, extracting the query lineage over the probabilistic XML document, and, second, looking for an optimal strategy to approximate the probability of the propositional lineage formula. ProApproX is the probabilistic query manager for probabilistic XML presented in this thesis. The system allows users to query uncertain tree-structured data in the form of probabilistic XML documents. It integrates a query engine that searches for an optimal strategy to evaluate the probability of the query lineage. ProApproX relies on a query-optimizer--like approach: exploring different evaluation plans for different parts of the formula and predicting the cost of each plan, using a cost model for the various evaluation algorithms. We demonstrate the efficiency of this approach on datasets used in a number of most popular previous probabilistic XML querying works, as well as on synthetic data. An early version of the system was demonstrated at the ACM SIGMOD 2011 conference. First steps towards the new query solution were discussed in an EDBT/ICDT PhD Workshop paper (2011). A fully redesigned version that implements the techniques and studies shared in the present thesis, is published as a demonstration at CIKM 2012. Our contributions are also part of an IEEE ICDE

Ma thèse porte sur la compilation des langages de requêtes orientés web des données. Plus particulièrement, ma thèse s'intéresse à l'analyse, l'optimisation et l'évaluation distribuée d'un tel langage : SPARQL. Ma contribution principale est l'élaboration d'une méthode nouvelle particulièrement intéressante pour des requêtes contenant de la récursion ou dans le cadre d'une évaluation distribuée. Cette nouvelle méthode s'appuie sur un nouvel outil que nous introduisons : la μ-algèbre. C'est une variation de l'algèbre relationnelle équipée d'un opérateur de point fixe. Nous présentons sa syntaxe et sémantique ainsi qu'une traduction vers la μ-algèbre depuis SPARQL avec Property Paths (une fonctionnalité introduite dans le dernier standard SPARQL qui autorise une forme de récursion).Nous présentons ensuite un système de types et nous montrons comment les termes de la μ-algèbre peuvent être réécrits en d'autres termes (de sémantique équivalente) en utilisant soit des règles de réécriture provenant de l'algèbre relationnelle soit des règles nouvelles, spécifiques à la μ-algèbre. Nous démontrons la correction des nouvelles règles qui sont introduites pour réécrire les points fixes : elles permettent de pousser les filtres, les jointures ou les projections à l'intérieur des points fixes (dépendant des certaines conditions sur le terme).Nous présentons ensuite comment ces termes peuvent être évalués, d'abord de manière générale, puis en considérant le cas particulier d'une évaluation sur une plateforme distribuée. Nous présentons aussi un modèle de coût pour l'évaluation des termes. À l'aide du modèle de coût et de l'évaluateur, plusieurs termes qui sont équivalents d'un point de vue sémantiques peuvent maintenant être vus comme différentes manières d'évaluer les termes avec différents coûts estimés. Nous montrons alors que les termes qui sont considérés grâce aux nouvelles règles de réécritures que nous avons introduites, permettent une exécution plus efficace que ce qui était possible dans les autres approches existantes. Nous confirmons ce résultat théorique par une expérimentation comparant plusieurs exécuteurs sur des requêtes SPARQL contenant de la récursion.Nous avons investigué comment utiliser une plateforme de calcul distribuée (Apache Spark) pour produire un évaluateur efficace de requêtes SPARQL. Cet évaluateur s'appuie sur un fragment de la μ-algèbre, limité aux opérateurs qui ont une traduction en code Spark efficace. Le résultat de ces investigations à résultat en l'implémentation de SPARQLGX, un évaluateur SPARQL distribué en pointe par rapport à l'état de l'art.Pour finir, ma dernière contribution concerne l'estimation de la cardinalité des solutions à un terme de la μ-algèbre. Ces estimateurs sont particulièrement utiles pour l'optimisation. En effet, les modèles de coût reposent généralement sur de telles estimations pour choisir quel sera le terme le plus efficace parmi plusieurs termes équivalents. Pour cette estimation nous nous intéressons tout particulièrement au fragment conjonctif de la μ-algèbre (ce qui correspond au fragment bien connu Basic Graph Pattern de SPARQL). Notre nouvelle estimation de cardinalité s'appuie sur des statistiques sur les données et a été implémenté dans SPARQLGX. Nos expériences montrent que cette méthode permet de grandement accélérer l'évaluation de SPARQL sur SPARQLGX. / The topic of my PhD is the compilation of web data query languages. More particularly, the analysisand the distributed evaluation of a such language: SPARQL. My main contributions concern theevaluation of web data queries especially for recursive queries or for distributed settings.In this thesis, I introduce μ-algebra: it is a kind of relational algebra equipped with a fixpointoperator. I present its syntax, semantics, and a translation from SPARQL with Property Paths (anew feature of SPARQL allowing some form of recursion) to this μ-algebra.I then present a type system and show how μ-algebra terms can be rewritten to terms withequivalent semantics using either classical rewrite rules of the relational world or new rules that arespecific to this μ-algebra. We demonstrate the correctness of these new rules that are introduced tohandle the rewriting of fixpoints: they allow to push filters, joins and projections inside fixpointsor to combine several fixpoints (when some condition holds).I demonstrate how these terms could be evaluated both from a general perspective and in thespecific case of a distributed evaluation. I devise a cost model for μ-algebra terms inspired by thisevaluation. With this cost model and this evaluator, several terms that are semantically equivalentcan be seen as various Query Execution Plans (QEP) for a given query. I show that the μ-algebraand its rewrite rules allow the reach of QEP that are more efficient than all QEP considered in otherexisting approaches and confirm this by an experimental comparison of several query evaluators onSPARQL queries with recursion.I investigate the use of an efficient distributed framework (Spark) to build a fast SPARQL dis-tributed query evaluator. It is based on a fragment of μ-algebra, limited to operators that havea translation into fast Spark code. The result of this has been used to implement SPARQLGX, astate of the art distributed SPARQL query evaluator.Finally, my last contribution concerns the estimation of the cardinality of solutions to a μ-algebraterm. Such estimators are key in the optimization. Indeed, most cost models for QEP rely on suchestimators and are therefore necessary to determine the most efficient QEP. I specifically considerthe conjunctive query fragment of μ-algebra (which corresponds to the well-known Basic GraphPattern fragment of SPARQL). I propose a new cardinality estimation based on statistics about thedata and implemented the method into SPARQLGX. Experiments show that this method improvesthe performance of SPARQLGX.

Le travail présenté dans cette thèse aborde la problématique de la personnalisation des analyses OLAP au sein des bases de données multidimensionnelles. Une analyse OLAP est modélisée par un graphe dont les noeuds représentent les contextes d'analyse et les arcs traduisent les opérations de l'utilisateur. Le contexte d'analyse regroupe la requête et le résultat. Il est décrit par un arbre spécifique qui est indépendant des structures de visualisation des données et des langages de requête. Par ailleurs, nous proposons un modèle de préférences utilisateur exprimées sur le schéma multidimensionnel et sur les valeurs. Chaque préférence est associée à un contexte d'analyse particulier. En nous basant sur ces modèles, nous proposons un cadre générique comportant deux mécanismes de personnalisation. Le premier mécanisme est la personnalisation de requête. Il permet d'enrichir la requête utilisateur à l'aide des préférences correspondantes afin de générer un résultat qui satisfait au mieux aux besoins de l'usager. Le deuxième mécanisme de personnalisation est la recommandation de requêtes qui permet d'assister l'utilisateur tout au long de son exploration des données OLAP. Trois scénarios de recommandation sont définis : l'assistance à la formulation de requête, la proposition de la prochaine requête et la suggestion de requêtes alternatives. Ces recommandations sont construites progressivement à l'aide des préférences de l'utilisateur. Afin valider nos différentes contributions, nous avons développé un prototype qui intègre les mécanismes de personnalisation et de recommandation de requête proposés. Nous présentons les résultats d'expérimentations montrant la performance et l'efficacité de nos approches. Mots-clés: OLAP, analyse décisionnelle, personnalisation de requête, système de recommandation, préférence utilisateur, contexte d'analyse, appariement d'arbres de contexte.

Dans le monde du Web, on retrouve les formats RSS et Atom (feeds) qui sont, sans doute, les formats XML les plus populaires et les plus utilisés. Ces formats permettent aux, entre autres, communautés Web, industriels, et services web de publier et d'échanger des documents XML. En outre, ils permettent à un utilisateur de consulter librement des données/informations sans avoir à basculer d'un site à un autre, et cela à l'aide d'applications logicielles. Dans ce cas, l'utilisateur enregistre ses fournisseurs de flux favoris, chaque fournisseur diffuse la liste des nouveaux éléments qui ont été modifiés depuis le dernier téléchargement. Cependant, l'enregistrement d'un certain nombre de sources de flux dans un agrégateur de flux engendre à la fois des problèmes d'hétérogénéité (à cause des différences structurelles et de contenu) et des problèmes de surcharges d'information. Par ailleurs, aucun des agrégateurs de flux existants n'offre une approche qui intègre (ou fusionne) les flux en tenant compte de leurs similarités, du contexte de l'utilisateur et de ses préférences. Dans cette thèse, nous proposons un framework formel qui permet de traiter l'hétérogénéité, l'intégration et l'interrogation des flux d'actualités. Ce framework est fondé sur une représentation arborescente d'un flux et possède trois éléments principaux qui sont les suivants: comparateur de flux, intégrateur de flux, et processeur de requêtes. Le comparateur de flux permet de mesurer le degré de similarité entre deux éléments/flux en utilisant une base de connaissance intégrant une approche ascendante et progressive. Nous proposons une mesure de similarité à base de concept capable de calculer la similarité entre les flux selon le nombre de leurs concepts communs (et différents) et leurs proximités sémantiques. Nous montrons également comment définir et identifier la relation exclusive entre deux textes ou éléments. L'intégrateur de flux permet de fusionner plusieurs flux provenant de différentes sources tout en tenant compte du contexte de l'utilisateur. Nous montrons dans notre étude comment représenter le contexte d'utilisateur ainsi que ses préférences. Nous fournissons un ensemble prédéfini de règles de fusion qui peuvent être enrichies et adaptées par chaque utilisateur. Quant au processeur de requêtes, il se base sur une étude formelle et plus précisément sur une algèbre dédiée à la fusion des flux continus d'actualités que nous proposons ici. Les opérateurs proposés dans cette algèbre sont aidés par des fonctions à base de similarité. Nous catégorisons les opérateurs de flux selon trois catégories: opérateurs d'extraction, opérateurs ensemblistes et opérateur de fusion. Nous montrons que l'opérateur de fusion généralise l'opération de jointure et les opérateurs ensemblistes. Nous fournissons également un ensemble de règles de réécriture et d'équivalence de requêtes pour la simplification et l'optimisation des requêtes. Enfin, nous présentons un prototype nommé "Easy RSS Manager" (EasyRSSManager). Ce prototype est un lecteur sémantique de flux et un composant sémantique pour l'interrogation des fenêtres de flux. EasyRSSManager a été utilisé pour valider, démontrer et tester la faisabilité des différentes propositions de notre étude. En particulier, nous avons testé la complexité en temps et la pertinence de nos approches en utilisant à la fois des données réelles et syntaxiques.

Dans le monde du Web, on retrouve les formats RSS et Atom (feeds) qui sont, sans doute, les formats XML les plus populaires et les plus utilisés. Ces formats permettent aux, entre autres, communautés Web, industriels, et services web de publier et d’échanger des documents XML. En outre, ils permettent à un utilisateur de consulter librement des données/informations sans avoir à basculer d’un site à un autre, et cela à l'aide d’applications logicielles. Dans ce cas, l'utilisateur enregistre ses fournisseurs de flux favoris, chaque fournisseur diffuse la liste des nouveaux éléments qui ont été modifiés depuis le dernier téléchargement. Cependant, l'enregistrement d'un certain nombre de sources de flux dans un agrégateur de flux engendre à la fois des problèmes d'hétérogénéité (à cause des différences structurelles et de contenu) et des problèmes de surcharges d’information. Par ailleurs, aucun des agrégateurs de flux existants n’offre une approche qui intègre (ou fusionne) les flux en tenant compte de leurs similarités, du contexte de l’utilisateur et de ses préférences. Dans cette thèse, nous proposons un framework formel qui permet de traiter l'hétérogénéité, l'intégration et l'interrogation des flux d’actualités. Ce framework est fondé sur une représentation arborescente d'un flux et possède trois éléments principaux qui sont les suivants: comparateur de flux, intégrateur de flux, et processeur de requêtes. Le comparateur de flux permet de mesurer le degré de similarité entre deux éléments/flux en utilisant une base de connaissance intégrant une approche ascendante et progressive. Nous proposons une mesure de similarité à base de concept capable de calculer la similarité entre les flux selon le nombre de leurs concepts communs (et différents) et leurs proximités sémantiques. Nous montrons également comment définir et identifier la relation exclusive entre deux textes ou éléments. L’intégrateur de flux permet de fusionner plusieurs flux provenant de différentes sources tout en tenant compte du contexte de l’utilisateur. Nous montrons dans notre étude comment représenter le contexte d’utilisateur ainsi que ses préférences. Nous fournissons un ensemble prédéfini de règles de fusion qui peuvent être enrichies et adaptées par chaque utilisateur. Quant au processeur de requêtes, il se base sur une étude formelle et plus précisément sur une algèbre dédiée à la fusion des flux continus d’actualités que nous proposons ici. Les opérateurs proposés dans cette algèbre sont aidés par des fonctions à base de similarité. Nous catégorisons les opérateurs de flux selon trois catégories: opérateurs d'extraction, opérateurs ensemblistes et opérateur de fusion. Nous montrons que l’opérateur de fusion généralise l’opération de jointure et les opérateurs ensemblistes. Nous fournissons également un ensemble de règles de réécriture et d'équivalence de requêtes pour la simplification et l’optimisation des requêtes. Enfin, nous présentons un prototype nommé «Easy RSS Manager» (EasyRSSManager). Ce prototype est un lecteur sémantique de flux et un composant sémantique pour l’interrogation des fenêtres de flux. EasyRSSManager a été utilisé pour valider, démontrer et tester la faisabilité des différentes propositions de notre étude. En particulier, nous avons testé la complexité en temps et la pertinence de nos approches en utilisant à la fois des données réelles et syntaxiques. / In the Web, RSS and Atom (feeds) are probably the most popular and highly utilized XML formats which allow web communities, publishing industries, web services, etc. to publish and exchange XML documents. In addition, they allow a user to consume data/information easily without roaming from site to site using software applications. Here, the user registers her favorite feed providers; and each provider sends the list of news items changed since the last download. However, registering a number of feed sources in feed aggregators cause both heterogeneity and information overloading problems. Besides, none of the existing RSS/feed aggregators provide an approach that integrates (merges) feeds from different sources considering similarity, user contexts and preferences. In this research, we provide a formal framework that handles the heterogeneity, integration and querying feeds. The framework is based a tree representation of a feed and has three main components: feed comparator, merger and query processor. The feed comparator addresses the issue of measuring the relatedness between news items using a Knowledge Base, a bottom-up and incremental approaches. We proposed a concept-based similarity measure based on the function of the number of shared and different concepts in their global semantic neighborhoods. Here, we use the concept similarity value and relationship as a building block for texts, simple elements and items relatedness algorithms. We show also how to define and identify the exclusive relationship between any two texts and elements. The feed merger addresses the issue of integrating news items from different sources considering a user context. We show here how to represent a user context and her preferences. Also, we provide a set of predefined set of merging rules that can be extended and adapted by a user. The query processor is based on a formal study on RSS query algebra that uses the notion of semantic similarity over dynamic content. The operators are supported by a set of similarity-based helper functions. We categorize the RSS operators into extraction, set membership and merge operators. The merge operator generalizes the join and the set membership operators. We also provide a set of query rewriting and equivalence rules that would be used during query simplification and optimization. Finally, we present a desktop prototype called Easy RSS Manager (EasyRSSManager) having a semanticaware RSS Reader, and semantic-aware and window-based RSS query components. It is designed to validate, demonstrate and test the practicability of the different proposals of this research. In particular, we test the timing complexity and the relevance of our approaches using both a real and syntactic dataset.

Le web est maintenant devenu une importante source d’information et de divertissement pour un grand nombre de personnes et les techniques pour accéder au contenu désiré ne cessent d’évoluer. Par exemple, en plus de la liste de pages web habituelle, certains moteurs de recherche présentent maintenant directement, lorsque possible, l’information recherchée par l’usager. Dans ce contexte, l’étude des requêtes soumises à ce type de moteur de recherche devient un outil pouvant aider à perfectionner ce genre de système et ainsi améliorer l’expérience d’utilisation de ses usagers. Dans cette optique, le présent document présentera certaines techniques qui ont été développées pour faire l’étude des requêtes de recherche web soumises à un moteur de recherche. En particulier, le travail présenté ici s’intéresse à deux problèmes distincts. Le premier porte sur la classification non-supervisée d’un ensemble de requêtes de recherche web dans le but de parvenir à regrouper ensemble les requêtes traitant d’un même sujet. Le deuxième problème porte quant à lui sur la détection non-supervisée des entités nommées contenues dans un ensemble de requêtes qui ont été soumises à un moteur de recherche. Les deux techniques proposées utilisent l’information supplémentaire apportée par la connaissance des pages web qui ont été visitées par les utilisateurs ayant émis les requêtes étudiées.