Odysseus

The Interoperable System's Group (ISG) are conducting research into XML database query performance. In order to integrate data from multiple heterogeneous sources such as sensor data or digital libraries, a common model with high interopable properties is necessary. For this reason, XML has emerged as the model of choice for many systems although the poor query performance associated with XML databases is a limiting factor.

Despite some novel indexing schemes, problems with join algorithms particularly where intermediate results are large, prevent the efficient use of XML data. A new algorithm TwigStack, has emerged as an alternative to conventional joins. It works by adopting a stack-based approach to twig manipulation (where twigs form the intermediate result set) and uses a specific sorting method to ensure an efficient result traversal. It also eliminates costly joins in situations where the joined twigs will not form part of the final result set.

This proposal is to build a TwigStack implementation in order to improve the ISG's Indexing Method for XML databases. It is anticipated that such a prototype will offer insights into how one can fine-tune and customise TwigStack variations to suit different domains and data types.

Relevance of Project to the Host Laboratories:

The ISG have developed a novel indexing structure to support fast retrieval of results for XPath queries but the longer term goal is to provide a full Query Processing mechanism, and this requires manipulation of intermediate query results, to provide the final result set. This requires an efficient means of merging sub-trees (or twigs) returned by our Indexing Method. By developing a TwigStack prototype, this will provide the project with a first version of a fully functional indexing method.

Supervisors:

Dr. Mark Roantree (Computing, DCU)

Keywords:

XML Databases, XPath, Query Processing, Indexing.