Edinburgh Research Explorer

Taming XPath Queries by Minimizing Wildcard Steps

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publication(e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31 - September 3 2004
Pages156-167
Number of pages12
Publication statusPublished - 2004

Abstract

This paper presents a novel and complementary technique to optimize an XPath query by minimizing its wildcard steps. Our approach is based on using a general composite axis called the layer axis, to rewrite a sequence of XPath steps (all of which are wildcard steps except for possibly the last) into a single layer-axis step. We describe an efficient implementation of the layer axis
and present a novel and efficient rewriting algorithm to minimize both non-branching as well as branching wildcard steps in XPath queries. We
also demonstrate the usefulness of wildcard-step elimination by proposing an optimized evaluation strategy for wildcard-free XPath queries that enables
selective loading of only the relevant input XML data for query evaluation. Our experimental results not only validate the scalability and efficiency
of our optimized evaluation strategy, but also demonstrate the effectiveness of our rewriting algorithm for minimizing wildcard steps in XPath queries. To the best of our knowledge, this is the first effort that addresses this new optimization
problem.

ID: 19841603