Given a document D in the form of an unordered labeled tree, we study the expressibility on D of various fragments of XPath, the core navigational language on XML documents. We give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an XPath expression in these fragments. 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 XPath. We refer to this perspective on the semantics of XPath 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 XPath expression to a given node of D. All these definability results, both in the global and the local view, are obtained by using arobust 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.
展开▼
机译：给定无序标记树形式的文档 D ，我们研究了XML文档的核心导航语言XPath的各种片段在 D 上的可表达性。我们用 D 的结构来描述这些片段中的XPath表达式何时可以定义其节点上的二进制关系。由于这种关系中的每对节点代表 D 中的唯一路径，因此我们的结果捕获了XPath中可定义的 D 中的路径集。我们将有关XPath语义的这种观点称为“全局视图”。与这种全局视图相反，还有一个“局部视图”，其中人们对可以从文档中的特定节点开始导航到的节点感兴趣。在此视图中，我们表征了何时可以将 D 中的一组节点定义为将XPath表达式应用于 D 的给定节点的结果。所有这些可定义性结果（无论是全局视图还是局部视图）都是通过使用稳健的两步方法获得的，该方法首先包括：在无法通过XPath各自片段中的表达式来区分两个节点时进行特征化，然后对这些特征进行引导达到理想的结果。
展开▼
