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.