Semantic Characterizations of Navigational XPath Maarten Marx and Maarten de Rijke   View Paper (PDF)   Return to June 2005, Volume 34, Number 2 Abstract We give semantic characterizations of the expressive power of navigational XPath (a.k.a. Core XPath) in terms of first order logic. XPath can be used to specify sets of nodes and sets of paths in an XML document tree. We consider both uses. For sets of nodes, XPath is equally expressive as first order logic in two variables. For paths, XPath can be defined using four simple connectives, which together yield the class of first order definable relations which are safe for bisimulation. Furthermore, we give a characterization of the XPath expressible paths in terms of conjunctive queries. ©2006 Association for Computing Machinery