This chapter reviews recent advances on stream XML query evaluation algorithms with stack-based encoding of intermediary data. Originally proposed for disk-resident XML, the stack-based architecture has been extended for streaming algorithms for both single and multiple query processing, ranging from XPath filtering to more complex XQuery. The key benefit of the stack-based architecture is its succinct encoding of partial query results, which can cause exponential enumeration if encoded naively. In addition, the chapter discusses opportunities to integrate benefits demonstrated in the reviewed work. For single-query processing, a sketch is given for an integrated algorithm, StreamTwig2Stack, that achieves all the benefits of existing algorithms in terms of functionality, time complexity, and buffer memory optimality.
TopIntroduction
XML has become an essential format in data exchange application domains, where an application processes data in XML documents sent from other systems. In order to ensure interoperability, XML data is usually sent as text data, which needs parsing before being consumed by the application. Various XML stream processing technologies have been developed to enable query processing over streaming XML documents for such scenarios.
XML stream processing is to evaluate queries only by a single scan over an XML document. It requires different technologies from querying over disk-resident XML data where an XML can be converted into proprietary data structure with indexing. Moreover, in this streaming environment, we should avoid materializing the entire document as a tree in the main memory. A system often needs to evaluate a query in a low memory-profile environment. In some cases, XML processing is embedded in an application as a utility component. In other cases, a system must achieve high throughput to process a large amount of documents and/or queries.
XML stream processing has been extensively studied in recent years. Motivated by a variety of applications, these studies address various issues under different assumptions and problem statements.
Earlier work typically targets information filtering applications, where a query is a pattern matching expression that returns a Boolean value. Received an XML document, the system should identify a small fraction of matching queries from a large set of registered queries. Many filtering algorithms naturally employ an automaton-based approach, where the query results are modeled as acceptance states of automaton.
As XML became pervasive in data exchange, various application needs emerged beyond filtering. Many applications use queries to express more complex patterns that extract structured data from an XML document. In such a scenario, structural pattern matching in XML queries can generate a large amount of intermediary data, which has been recognized as a challenging research issue.
In this chapter, we give a review mainly on recent advance on stream XML query evaluation algorithms that efficiently manage intermediary data in a special data structure based on multiple stacks. Originally, this succinct encoding of intermediary data was proposed for processing disk-resident XML data (Bruno, Koudas, & Srivastava, 2002). However, the proposed algorithms, PathStack and TwigStack, have inspired various streaming algorithms, which have been demonstrated to be efficient for various applications.
We categorize algorithms into two types and review them separately: single-query processing and multi-query processing. At the end of each review, we discuss approaches to integrate benefits of the reviewed algorithms. For single-query processing, we also give a sketch of an integrated algorithm, StreamTwig2Stack, that achieves all the benefits of existing algorithms (functionality, time complexity, and buffer memory optimality).