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.

DANS CETTE THÈSE, NOUS NOUS POSITIONNONS DANS UN CONTEXTE DYNAMIQUE, OÙ LES DONNÉES XML ÉVOLUENT AU COURS DU TEMPS ET SONT SOUMISES À UN ENSEMBLE DE MISES À JOUR, ET NOUS NOUS INTÉRESSONS À DEUX PROBLÈMES MAJEURS, LARGEMENT ÉTUDIÉS DANS LE CADRE RELATIONNEL : -LA DÉTECTION DE L'IMPACT D'UN ENSEMBLE DE MISE À JOUR SUR UNE VUE, DÉFINIE PAR UNE REQUÊTE.-LA DÉTECTION DE L'IMPACT D'UN ENSEMBLE DE MISE À JOUR SUR LA SATISFACTION D'UNE DÉPENDANCE FONCTIONNELLE. DANS LE PREMIER CAS, L'OBJECTIF EST DE DÉTECTER SI L'ENSEMBLE DE MISES À JOUR A MODIFIÉ LA VUE. DANS LE DEUXIÈME CAS, L'OBJECTIF EST DE DÉTECTER SI L'ENSEMBLE DE MISE À JOUR A PRODUIT UN NOUVEAU DOCUMENT QUI NE SATISFAIT PLUS LES CONTRAINTES QU'IL SATISFAISAIT AVANT LES MISES À JOUR. NOUS NOUS DIFFÉRENCIONS DES TRAVAUX ANTÉRIEURS PRINCIPALEMENT SUR DEUX POINTS : (1) NOUS SUPPOSONS QUE LES DONNÉES SOURCES SONT À PRIORI INDISPONIBLES ET NOUS ÉTUDIONS LES DEUX PROBLÈMES EN EFFECTUANT UNE ANALYSE STATIQUE DES DÉFINITIONS DES MISES À JOUR, ET DE LA VUE (CAS1) OU DE LA DÉPENDANCE FONCTIONNELLE (CAS 2). DE PLUS, DANS LE CAS OÙ UN SCHÉMA XML CONTRAIGNANT LA STRUCTURE DES DONNÉES, EST DISPONIBLE NOUS UTILISONS CETTE INFORMATION SUPPLÉMENTAIRE DANS NOTRE ANALYSE AFIN DE DÉTECTER ÉVENTUELLEMENT PLUS DE CAS D'INDÉPENDANCES ENTRE LES MISES À JOUR ET LA VUE OU LA DÉPENDANCE FONCTIONNELLE SELON LE CAS. (2) NOUS PRENONS L'OPTION D'UTILISER, COMME MÉCANISME DE SÉLECTION DE NŒUDS, DANS LA DÉFINITION DES MISES À JOUR, DES VUES ET DES DÉPENDANCES FONCTIONNELLES, UN LANGAGE FORMEL BASÉ SUR L'UTILISATION DE MOTIFS RÉGULIER ARBORESCENTS, PERMETTANT DE DÉFINIR DES REQUÊTES APPELÉES 'REQUÊTES ARBRES RÉGULIÈRES' (EN ABRÉGÉ RARS).

Cette thèse porte sur la classification et le traitement des invariants lexicaux arabes qui expriment un aspect temporel afin de créer un modèle qui présente chaque invariant sous la forme d’un schéma de grammaire (automates à états finis). Dans ce travail nous avons limité notre traitement seulement pour 20 invariants lexicaux. Notre hypothèse part du principe que les invariants lexicaux sont situés au même niveau structural (formel) que les schèmes dans le langage quotient (squelette) de la langue arabe. Ils cachent beaucoup d’informations et entraînent des attentes syntaxiques qui permettent de prédire la structure de la phrase.Au début de cette thèse, nous abordons la notion « invariant lexical » en exposant les différents niveaux d’invariance. Ensuite, nous classons les invariants étudiés dans cette thèse selon plusieurs critères.La deuxième partie de cette thèse fait l’objet de notre propre étude concernant les invariants lexicaux temporels dans laquelle nous commençons par une présentation de notre méthode d’étude linguistique ainsi que la modélisation par schémas de grammaires des invariants lexicaux temporels étudiés. Ensuite, nous abordons l’analyse proprement dite des invariants lexicaux simples comme « ḥattā, baʿda » et complexes comme « baʿdamā, baynamā ».Enfin, une application expérimentale « Kawâkib » a été employée pour détecter et identifier les invariants lexicaux en montrant leurs points forts aussi bien que leurs lacunes. Nous proposons également une nouvelle vision de la prochaine version de « Kawâkib » qui peut représenter une application pédagogique de l'arabe sans lexique. / This thesis focuses on the classification and the treatment of Arabic lexical invariants that express a temporal aspect. Our aim is to create a diagram of grammar (finite state machine) for each invariant. In this work, we limited our treatment to 20 lexical invariants. Our assumption is that the lexical invariants are located at the same structural level (formal) as the schemes in the language quotient (skeleton) of the Arabic language. They hide much information and involve syntactic expectations that make it possible to predict the structure of the sentence.In the first part of our research tasks, we present the concept of “invariant lexical” by exposing the various levels of invariance. Then, we classify the invariants according to several criteria.The second part is the object of our own study concerning the temporal lexical invariants. We present our linguistic method as well as our approach of modelling using diagrams of grammars. Then, we analyze the simple lexical invariants such “ḥattā, baʿda” and the complexes ones such “baʿdamā, baynamā”.Finally, an experimental application “Kawâkib” was used to detect and identify the lexical invariants by showing their strong points as well as their gaps. We also propose a new vision of the next version of “Kawâkib” that can represent a teaching application of Arabic without lexicon.

Ce travail de thèse adresse le problème de la désambiguïsation lexicale automatique à l'aide de méthodes d'apprentissage supervisé. Dans une première partie, nous proposons un ensemble de puissants outils de manipulation de corpus linguistiques étiquetés. Pour réaliser ces outils, nous avons développé une bibliothèque C++ qui implémente un langage élaboré et expressif d'interrogation de corpus, basé sur des méta-expressions régulières. Dans une seconde partie, nous comparons divers algorithmes d'apprentissage supervisé, que nous utilisons ensuite pour mener à bien une étude systématique et approfondie de différents critères de désambiguïsation, basés sur la cooccurrence de mots et plus généralement de n-grammes. Nos résultats vont parfois à l'encontre de certaines pratiques dans le domaine. Par exemple, nous montrons que la suppression des mots grammaticaux dégrade les performances et que les bigrammes permettent d'obtenir de meilleurs résultats que les unigrammes.

Ce travail de thèse adresse le problème de la désambiguïsation lexicale automatique à l'aide de<br />méthodes d'apprentissage supervisé. Dans une première partie, nous proposons un ensemble de<br />puissants outils de manipulation de corpus linguistiques étiquetés. Pour réaliser ces outils, nous<br />avons développé une bibliothèque \texttt{C\fup{++}} qui implémente un langage élaboré et expressif<br />d'interrogation de corpus, basé sur des \emph{méta-expressions régulières}. Dans une seconde<br />partie, nous comparons divers algorithmes d'apprentissage supervisé, que nous utilisons ensuite<br />pour mener à bien une étude systématique et approfondie de différents critères de désambiguïsation,<br />basés sur la cooccurrence de mots et plus généralement de n-grammes. Nos résultats vont parfois à<br />l'encontre de certaines pratiques dans le domaine. Par exemple, nous montrons que la suppression<br />des mots grammaticaux dégrade les performances et que les bigrammes permettent d'obtenir de<br />meilleurs résultats que les unigrammes.