HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Contributor : Pierre Genevès Connect in order to contact the contributor
Submitted on : Tuesday, October 4, 2005 - 2:58:57 PM
Last modification on : Wednesday, April 6, 2022 - 3:48:36 PM
Long-term archiving on: : Tuesday, June 2, 2015 - 2:10:14 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : jamais

Please log in to resquest access to the document


  • HAL Id : inria-00000391, version 1



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



Record views