Query evaluation on compressed trees
Query evaluation on compressed trees
复制标题
压缩树的查询评估
DOI：
10.1109/lics.2003.1210058
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Christoph E. Koch
中科院分区：
文献类型：
--
作者：
Markus Frick;Martin Grohe;Christoph E. Koch
本文研究了通过共享公共子树来评估以自然结构保留方式压缩的未排序树上的一元（或节点选择）查询的问题。研究未排序树上的一元查询的动机来自数据库领域，其中查询可被视为未排序标记树的 XML（可扩展标记语言）文档是一项重要任务。我们给出了用于评估 XPath 和单子数据记录查询的算法和复杂性结果。此外，我们提出了一种用于查询树的新的自动机理论形式，并给出了用于评估由此类自动机定义的查询的算法。
This paper studies the problem of evaluating unary (or node-selecting) queries on unranked trees compressed in a natural structure-preserving way, by the sharing of common subtrees. The motivation to study unary queries on unranked trees comes from the database field, where querying XML (Extensible Markup Language) documents, which can be considered as unranked labeled trees, is an important task. We give algorithms and complexity results for the evaluation of XPath and monadic datalog queries. Furthermore, we propose a new automata-theoretic formalism for querying trees and give algorithms for evaluating queries defined by such automata.