Structural characterizations of the navigational expressiveness of relation algebras on a tree

• Natural variations of Tarski's classic relation algebra are studied on trees.
• The notion of instance expressibility is introduced and studied for these languages.
• A robust methodology is given and used for characterizing instance expressivity.
• Our characterizations are given for both global and local views on query semantics.
• These characterizations are effectively computable and hence can be used in practice.

We study the expressiveness on a given document of various fragments of XPath, the core navigational language on XML documents. Viewing these languages as fragments of Tarski's relation algebra, we give characterizations for when a binary relation on the document's nodes (i.e., a set of paths) is definable by an expression in these algebras. In contrast with this “global view” on language semantics, there is also a “local view” where one is interested in the nodes to which one can navigate starting from a particular node. In this view, we characterize when a set of nodes can be defined as the result of applying an expression to a given node. All of these global and local definability results are obtained using a two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the language, and then bootstrapping these characterizations to the desired results.