Memory-Efficient Query Processing over XML Fragment Stream with Fragment Labeling

Abstract

The portable/hand-held devices deployed in mobile computing environment are mostly limited in memory. To make it possible for them to locally process queries over a large volume of XML data, the data needs to be streamed in fragments of manageable size and the queries need to be processed over the stream with as little memory as possible. In this paper, we report a considerable improvement of the state-of-the-art techniques of query processing over XML fragment stream in memory efficiency. We use XML fragment labeling (XFL) as a method of representing XML fragmentation, and show that XFL is much more effective than the popular hole-filler (HF) model employed in the state-of-the-art in reducing the amount of memory required for query processing. The state-of-the-art with the HF model requires more memory as the stream size increases. With XFL, we overcome this fundamental limitation, proposing the techniques to make query processing scalable in the sense that memory requirement is not affected by the size of the stream as long as the stream is bounded. The improvement is verified through implementation and a detailed set of experiments.