A Decision Procedure for XPath Containment

Pierre Genevès 1 Nabil Layaïda 1
1 WAM - Web, adaptation and multimedia
Inria Grenoble - Rhône-Alpes
Abstract : XPath is the standard language for addressing parts of an XML document. We present a sound and complete decision procedure for containment of XPath queries. The considered XPath fragment covers most of the language features used in practice. Specifically, we show how XPath queries can be translated into equivalent formulas in monadic second-order logic. Using this translation, we construct an optimized logical formulation of the containment problem, which is decided using tree automata. When the containment relation does not hold between two XPath expressions, a counter-example XML tree is generated. We provide a complexity analysis together with practical experiments that illustrate the efficiency of the decision procedure for realistic scenarios.
Type de document :
Article dans une revue
ACM Transactions on Information Systems, Association for Computing Machinery, 2005
Liste complète des métadonnées

https://hal.inria.fr/inria-00000391
Contributeur : Pierre Genevès <>
Soumis le : mardi 4 octobre 2005 - 14:58:57
Dernière modification le : lundi 19 janvier 2015 - 11:49:49
Document(s) archivé(s) le : mardi 2 juin 2015 - 14:10:14

Fichier

 Accès restreint
Fichier visible le : jamais

Connectez-vous pour demander l'accès au fichier

Identifiants

  • HAL Id : inria-00000391, version 1

Collections

Citation

Pierre Genevès, Nabil Layaïda. A Decision Procedure for XPath Containment. ACM Transactions on Information Systems, Association for Computing Machinery, 2005. <inria-00000391>

Partager

Métriques

Consultations de la notice

108