  Given a document D in the form of an unordered node-labeled tree, we study
the expressiveness on D of various basic fragments of XPath, the core
navigational language on XML documents. Working from the perspective of these
languages as fragments of Tarski's relation algebra, we give characterizations,
in terms of the structure of D, for when a binary relation on its nodes is
definable by an expression in these algebras. Since each pair of nodes in such
a relation represents a unique path in D, our results therefore capture the
sets of paths in D definable in each of the fragments. We refer to this
perspective on language semantics as the "global view." In contrast with this
global view, there is also a "local view" where one is interested in the nodes
to which one can navigate starting from a particular node in the document. In
this view, we characterize when a set of nodes in D can be defined as the
result of applying an expression to a given node of D. All these definability
results, both in the global and the local view, are obtained by using a robust
two-step methodology, which consists of first characterizing when two nodes
cannot be distinguished by an expression in the respective fragments of XPath,
and then bootstrapping these characterizations to the desired results.
