Streaming Enumeration on Nested Documents

Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the past 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 nes...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on database systems 2024-12, Vol.49 (4), p.1-39, Article 15
Main Authors: Muñoz, Martín, Riveros, Cristian
Format: Article
Language:English
Subjects:
Database theory
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the past 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 Annotators (VPAnn), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as monadic second-order logic over nested documents. Since processing a document through a VPAnn 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 article 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.
ISSN:0362-5915
1557-4644
DOI:10.1145/3701557