Efficient Algorithms for Evaluating Xpath over Streams*

摘要

In this paper we address the problem of evaluating Xpath queries over streaming XML data. We consider a practical Xpath fragment called Univariate Xpath, which includes the commonly used '/' and '//' axes and allows ?-node tests and arbitrarily nested predicates. It is well known that this Xpath fragment can be efficiently evaluated in O(|D||Q|) time in the non-streaming environment [18], where |D| is the document size and |Q| is the query size. However, this is not necessarily true in the streaming environment, since streaming algorithms have to satisfy stricter requirement than non-streaming algorithms, in that all data must be read sequentially in one pass. Therefore, it is not surprising that state-of-the-art stream-querying algorithms have higher time complexity than O(|D||Q|). In this paper we revisit the Xpath stream-querying prob- lem, and show that Univariate Xpath can be efficiently eval- uated in O(|D||Q|) time in the streaming environment. Spe- cifically, we propose two O(|D||Q|)-time stream-querying al- gorithms, LQ and EQ, which are based on the lazy strategy and on the eager strategy, respectively. To the best of our knowledge, LQ and EQ are the first Xpath stream-querying algorithms that achieve O(|D||Q|) time performance. Fur- ther, our algorithms achieve O(|D||Q|) time performance without trading off space performance. Instead, they have better buffering-space performance than state-of-the-art str- eam-querying algorithms. In particular, EQ achieves opti- mal buffering-space performance. Our experimental results show that our algorithms have not only good theoretical complexity but also considerable practical performance ad- vantages over existing algorithms.