Search

In this thesis, we study semistructured data. A semistructured datumis modelled by multi-rooted edge-labeled directed graphs. We study indexes preserving inclusion constraints.These constraints are binary relations over regular path expressions and are interpreted on a datum as "for this datum, the answer to query q is included in the answer to query r". So we use them to optimize queries. On an other hand, we define graph queries in order to study the expressibility of languages derived from XPath and Query. Experiments validate theoretical results.; La notion de données semi-structureées est liée au monde du web. On appelle donnée semi-structurée une donnée dont le schéma n'est pas défini a priori. Par exemple, il peut s'agir d'une page HTML, d'un site Web tout entier ou encore d'un document XML. Cette thèse étudie les requêtes sur les données modélisées par des graphes. Plus précisément, on s'intéresse à différents langages de requêtes associés. Dans le cas des graphes orientés, on utilise des techniques de réécriture et d'automates pour étudier - à des fins d'optimisation de requêtes - les contraintes d'inclusions. Elles portent sur les chemins qui permettent de naviguer dans la donnée. Par ailleurs, on génère un index d'une donnée qui préserve toutes les contraintes d'inclusions. Ensuite, on étend cette étude pour obtenir le concept de requête graphe. Appliqué au cas des documents "XML coloré", elles permettent d'étudier formellement l'expressivité et la complexité de langages de requêtes inspirés de XPath et de XQuery. Enfin, les résultats théoriques sont validés par des expérimentations.

International audience; We consider in this paper rooted labeled directed graphs as models for semistructured data. A path inclusion constraint, in such graphs, is an expression p