Abstract FR:

Le problème d'extraction d'information dans les documents XML est un domaine de recherche important en informatique. Nous proposons deux approches pour l'évaluation de requêtes sur les documents XML, compressés ou non, et/ou assujettis à des politiques du contrôle d'accès. La première est basée sur la logique de Horn: les politiques du contrôle d'accès de même que les requêtes sont modélisées comme des clauses de Horn contraintes, et l'évaluation de requêtes s'appuie sur une technique de résolution adaptée. La deuxième approche que nous présentons vise les documents XML pouvant être présentés sous une forme compressée comme des dags. Cette approche est basée sur sept automates de mots, correspondant aux sept axes de base de XPath. Ils courent de façon top-down sur les dags, et permettent d'évaluer les requêtes sur les documents compressés sans devoir les décompresser. Cette technique d'évaluation d'une requête Q, sur un document compressé t, peut être adaptée de façon à fournir la même réponse que l'évaluation de Q sur l'arbre équivalent à t. La complexité de nos deux approches est linéaire par rapport au nombre d'arêtes du document, et la taille de la requête. Outre ces deux approches, nous avons également présenté une approche basée sur les techniques de réécriture qui permet de résoudre le problème d'inclusion de patterns, sur un fragment purement descendant de XPath ; nous déduisons ainsi une condition nécessaire et suffisante pour ce problème (pour les patterns de ce fragment). Cette vue réécriturale peut être adaptée de façon à fournir une technique d'évaluation pour les requêtes modélisées par ces patterns, sur les documents XML arborescents ou compressés comme des dags.