An XML algebra for online processing of XML documents
In the last decade XML became a ubiquitous standard for representation of data. Despite the significant research efforts invested in the efficient processing techniques of XML documents we still need the operators of XML algebra specifically optimized for online processing of XML data. Online processing means that operators act on theoretically infinite sequences of XML documents and they never "see" an entire set of data. Most of XML algebras proposed so far are too resource expensive for online processing of XML documents. This paper proposes a new system of XML operators based on a formal model of extended tree grammars. We define a minimal set of basic operators and we show how the other operators can be derived from the basic ones. Our system of operators allows for processing of XML documents to any possible depth. The system eliminates the limitations of the previous approaches to online processing XML documents by allowing each operator be computed in the incremental and/or decremental way. The paper compares the functionality of the new system of operators with a number of XML algebras defined earlier.