Comparing XML Path Expressions

Pierre Genevès 1 Nabil Layaïda 1
1 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes
Abstract : XPath is the standard declarative language for navigating XML data and returning a set of matching nodes. In the context of XSLT/XQuery analysis, query optimization, and XML type checking, XPath decision problems arise naturally. They notably include XPath comparisons such as equivalence (whether two queries always return the same result), and containment (whether for any tree the result of a particular query is included in the result of a second one). XPath decision problems have attracted a lot of research attention, especially for studying the computational complexity of various XPath fragments. However, what is missing at present is the constructive use of an expressive logic which would allow capturing these decision problems, while providing practically effective decision procedures. In this paper, we propose a logic-based framework for the static analysis of XPath. Specifically, we propose the alternation free modal \mu-calculus with converse as the appropriate logic for effectively solving XPath decision problems. We present a translation of a large XPath fragment into \mu-calculus, together with practical experiments on the containment using a state-of-the-art EXPTIME decision procedure for \mu-calculus satisfiability. These preliminary experiments shed light, for the first time, on the cost of checking the containment in practice. We believe they reveal encouraging results for further static analysis of XML transformations.
Type de document :
Communication dans un congrès
D. Brailsford. Proceedings of the 2006 ACM Symposium on Document Engineering, DocEng 2006, Oct 2006, Amsterdam, Netherlands. ACM, pp.65-74, 2006, 〈10.1145/1166160.1166182〉
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00423062
Contributeur : Vincent Quint <>
Soumis le : vendredi 9 octobre 2009 - 12:13:40
Dernière modification le : vendredi 27 novembre 2009 - 16:56:20
Document(s) archivé(s) le : mercredi 16 juin 2010 - 00:32:39

Fichier

CompXPathExp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Genevès, Nabil Layaïda. Comparing XML Path Expressions. D. Brailsford. Proceedings of the 2006 ACM Symposium on Document Engineering, DocEng 2006, Oct 2006, Amsterdam, Netherlands. ACM, pp.65-74, 2006, 〈10.1145/1166160.1166182〉. 〈inria-00423062〉

Partager

Métriques

Consultations de la notice

221

Téléchargements de fichiers

88