An XML-algebra for Efficient Set-at-a-time Execution

Maxim Lukichev1, Boris Novikov1 and Pankaj Mehra2

  1. Saint-Petersburg University
    Saint-Petersburg, Russia,
  2. Whodini,Inc.
    CA, USA


The importance of XML query optimization is growing due to the rising number of XML-intensive data mining tasks. Earlier work on algebras for XML query focused mostly on rule-based optimization and used node-at-a-time execution model. Heavy query workloads in modern applications require cost-based optimization which is naturally supported by the set-at-a-time execution model. This paper introduces an algebra with only set-at-a-time operations, and discusses expression reduction methods and lazy evaluation techniques based on the algebra. Our experiments demonstrate that, for queries with complex conditional and quantified expressions, the proposed algebra results in plans with much better performance than those produced by the state-of-the-art algebras. For relatively simple queries, the proposed methods are expected to yield plans with comparable performance.

Key words

native XML databases, XML query optimization, query alge-bras

Digital Object Identifier (DOI)

Publication information

Volume 9, Issue 1 (January 2012)
Year of Publication: 2012
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Lukichev, M., Novikov, B., Mehra, P.: An XML-algebra for Efficient Set-at-a-time Execution. Computer Science and Information Systems, Vol. 9, No. 1, 63-80. (2012),