Validating XML documents in the streaming model with external memory

DOI10.1145/2504590MaRDI QIDQ2943557zbMATH OpenOpenAlexFDO

Authors Christian Konrad, Frédéric Magniez

Publication date 3 September 2015

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.3311

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Nonnumerical algorithms (68W05)

Abstract: We study the problem of validating XML documents of size $N$ against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which $p$-pass streaming algorithms require $Omega(N/p)$ space. We show that when allowing access to external memory, there is a deterministic streaming algorithm that solves this problem with memory space $O(lo{g}^{2}N)$, a constant number of auxiliary read/write streams, and $O(logN)$ total number of passes on the XML document and auxiliary streams. An important intermediate step of this algorithm is the computation of the First-Child-Next-Sibling (FCNS) encoding of the initial XML document in a streaming fashion. We study this problem independently, and we also provide memory efficient streaming algorithms for decoding an XML document given in its FCNS encoding. Furthermore, validating XML documents encoding binary trees in the usual streaming model without external memory can be done with sublinear memory. There is a one-pass algorithm using $O(sqrtNlogN)$ space, and a bidirectional two-pass algorithm using $O(lo{g}^{2}N)$ space performing this task.

Recommendations

• On the memory requirements of XPath evaluation over XML streams
• Worst-case optimal algorithm for XPath evaluation over XML streams
• scientific article; zbMATH DE number 1953123
• Memory lower bounds for XPath evaluation over XML streams
• Sublinear DTD validity

Cited in

(12)

• Deciding definability by deterministic regular expressions
• Efficient testing and matching of deterministic regular expressions
• Sublinear DTD validity
• Automata theory on sliding windows
• scientific article; zbMATH DE number 1953123 (Why is no real title available?)
• Streaming partitioning of sequences and trees
• Streamability of nested word transductions
• Visibly Pushdown Transducers for Approximate Validation of Streaming XML
• Fundamentals of Computation Theory
• Database Programming Languages
• Validating streaming JSON documents with learned VPAs
• Regular languages in the sliding window model

This page was built for publication: Validating XML documents in the streaming model with external memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943557)