With respect to current methods for query evaluation over
XML data streams, adoption of certain types of buffering
techniques is unavoidable. Under lots of circumstances,
the buffer scale may increase exponentially, which can
cause memory bottleneck. Some optimization techniques
have been proposed to solve the problem. However, the
limit of these techniques has been defined by a
concurrency lower bound and been theoretically proved.
In this paper, we show through an empirical study that
this lower bound can be broken by taking semantic
information into account for buffer reduction. To
demonstrate this, we build a SAX-based XML stream
query evaluation system and design an algorithm that
consumes buffers in line with the concurrency lower
bound. After a further analysis of the lower bound, we
design several semantic rules for the purpose of breaking
the lower bound and incorporate these rules in the lower
bound algorithm. Experiments are conducted to show that
the algorithms deploying semantic rules individually and
collectively all significantly outperform the lower bound
algorithm that does not consider semantic information. |
Cite as: Yang, C., Liu, C., Li, J., Yu, J.X. and Wang, J. (2008). Semantics based Buffer Reduction for Queries over XML Data Streams. In Proc. Nineteenth Australasian Database Conference (ADC 2008), Wollongong, NSW, Australia. CRPIT, 75. Fekete, A. and Lin, X., Eds. ACS. 145-153. |
(from crpit.com)
(local if available)
|