论文标题
嵌套文档上的流列
Streaming enumeration on nested documents
论文作者
论文摘要
在线使用的一些最相关的文档模式，例如XML和JSON具有嵌套格式。在过去的十年中，从流中提取嵌套文档的数据的任务变得特别相关。我们专注于对嵌套文档的各种大小输出的查询的流评估。我们将此类查询建模为可见的下降传感器（VPT），它是一种计算模型，可通过输出扩展明显的下降自动机，并且在嵌套文档上具有与MSO相同的表达能力。由于通过VPT处理文档可以产生大量的结果，因此我们有兴趣以流式传输方式阅读输入，并尽可能有效地枚举输出，即持续延迟。本文提出了一种算法，该算法在单个通行证中处理文档流后，用恒定延迟列举了这些元素。此外，我们表明该算法在每个符号和内存使用情况方面最佳案例最佳。
Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the last decade, the task of extracting data from nested documents over streams has become especially relevant. We focus on the streaming evaluation of queries with outputs of varied sizes over nested documents. We model queries of this kind as Visibly Pushdown Transducers (VPT), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as MSO over nested documents. Since processing a document through a VPT can generate a massive number of results, we are interested in reading the input in a streaming fashion and enumerating the outputs one after another as efficiently as possible, namely, with constant-delay. This paper presents an algorithm that enumerates these elements with constant-delay after processing the document stream in a single pass. Furthermore, we show that this algorithm is worst-case optimal in terms of update-time per symbol and memory usage.
