On the Optimality of Holistic Algorithms for Twig Queries

Byron Choi, Malika Mahoui, Derick Wood

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

31 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications
Subtitle of host publication14th International Conference, DEXA 2003, Prague, Czech Republic, September 1-5, 2003, Proceedings
EditorsVladimír Mařík, Werner Retschitzegger, Olga Štěpánková
PublisherSpringer Berlin Heidelberg
Number of pages10
ISBN (Electronic)9783540452270
ISBN (Print)9783540408062
Publication statusPublished - 21 Aug 2003
Event14th International Conference on Database and Expert Systems Applications - Prague, Czech Republic
Duration: 1 Sept 20035 Sept 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameDEXA: International Conference on Database and Expert Systems Applications


Conference14th International Conference on Database and Expert Systems Applications
Abbreviated titleDEXA 2003
Country/TerritoryCzech Republic
Internet address

User-Defined Keywords

  • Data Streaming
  • Multiple Scan
  • Node Test
  • Complete Binary Tree
  • Descendent Node


Dive into the research topics of 'On the Optimality of Holistic Algorithms for Twig Queries'. Together they form a unique fingerprint.

Cite this