HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/732
Title: On the optimality of holistic algorithms for twig queries
Authors: Choi, Byron
Mahoui, Malika
Wood, Derick
Keywords: TwigStack
XML
Twig queries
Issue Date: 2003
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2003-06
Abstract: Streaming XML documents has many emerging applications. However, in this paper, we show that the restrictions imposed by data streaming are too restrictive for processing twig queries - the core operation for XML query processing. Previous proposed algorithm TwigStack is an optimal algorithm for processing twig queries with only descendent edges over streams of nodes. The cause of the suboptimality of the TwigStack algorithm is the structurally recursions appearing in XML documents. We show that without relaxing the data streaming model, it is not possible to develop an optimal holistic algorithm for twig queries. Also the computation of the twig queries is not memory bounded. This motivates us to study two variations of the data streaming model: (1) offline sorting is allowed and the algorithm is allowed to select the correct nodes to be streamed and (2) multiple scans on the data streams are allowed. We show the lower bounds of the two variations.
URI: http://hdl.handle.net/1783.1/732
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200306.pdf223KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.