Binary Queries
Binary Queries
复制标题
二进制查询
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
H. Seidl
中科院分区：
文献类型：
--
作者：
A. Berlea;H. Seidl
查询XML文档是许多XML应用程序的基本任务。通常，查询的匹配被单独定位，即，匹配是被查询文档中的单个节点。相比之下，k元查询同时标识文档中的k个位置，这些位置经由某种指定关系连接。例如，在基于规则的变换（如XML变换）中，规则被应用到的节点和在第一节点的上下文中由规则选择的另一节点可以通过定义这两个节点之间的关系的二进制查询来一起标识。这样的二进制查询将分别替换用于标识第一节点和第二节点的匹配和选择模式。通过消除对选择模式的需求，二进制查询不仅可以减少转换中的模式数量，而且还可以允许所有的模式匹配都是静态完成的，即在转换实际开始之前。我们使用的正规森林文法的形式主义来定义查询的任意arities。下推森林自动机在过去已经被用来有效地实现使用森林文法表示的一元查询。本文的主要贡献是基于下推森林自动机评估二进制查询的算法。在最坏的理论情况下，算法评估二进制查询的时间与输入文档大小的平方成正比。然而在实践中，复杂性在输入大小方面大多是线性的。甚至可以沿着输入文档的解析来评估不需要检查其正确上下文的文档。除了使用森林语法之外，还可以使用类似于XML的语法以更直观的模式语言来表示查询。由www.RenderX.com呈现二进制文件
Querying XML documents is a basic task for many XML applications. Typically, matches of queries are located individually, i.e. a match is a single node in a queried document. k-ary queries, in contrast, simultaneously identify k locations in the document, which are connected via some specified relation. For example, in rule-based transformations (like XSLT transformations), a node to which a rule is applied and another node which is selected by the rule in the context of the first node could be identified together by a binary query defining the relation between these two nodes. Such a binary query would replace the match and the select pattern used to identify the first and the second node respectively. By eliminating the need for select patterns, binary queries would not only reduce the number of patterns in a transformation, but would also allow that all the pattern matching is done statically, i.e. before the transformation actually begins. We use the formalism of regular forest grammars to define queries of arbitrary arities. Pushdown forest automata have been used in the past to efficiently implement unary queries expressed by using forest grammars. The main contribution of this paper is an algorithm based on pushdown forest automata which evaluates binary queries. In the worst theoretical case the algorithm evaluates binary queries in time proportional to the square of the size of the input document. In practice however, the complexity is mostly rather linear in the input size. Queries for which the right context does not need to be checked can be evaluated even along with the parsing of the input document. Rather than using forest grammars, queries can be also expressed in a more intuitive pattern language using a syntax similar to XPath. Rendered by www.RenderX.com Binary Queries Table of