Efficient XPath Tree Pattern Matching Algorithms over XML Data Stream

摘要

XPath is a language for specifying the selection of element nodes within XML documents. The essential part of XPath is tree-shaped queries, referred to as the XPath trees in this paper. Formally, an XPath tree is an unordered tree whose nodes and edges are, labeled with 'node-tests' and 'navigational axes', respectively. This paper considers the tree matching problem over streaming XML data for subclasses of the XPath trees. First we present a streaming algorithm for the regular XPath trees that runs O(|Q||D|) time using O(|Q|height(D)) space, where |Q|, |D|, and height(D) are the query size, the data size, and the height of the data tree, respectively. Then, we extend the algorithm to larger subclasses with/without keeping the computational complexities.