"Improving the Efficiency of XPath Execution on Relational Systems"

Χάρης Γεωργιάδης, Υποψήφιος Διδάκτορας στο τμήμα Πληροφορικής του Ο.Π.Α.


In the past few years the adoption of XML for a variety of roles in 
e-business applications has increased significantly and continues to 
increase, stimulating the development of XML Management Systems. A 
large category of those systems is based on relational back-ends, 
shredding XML documents into relations.  These systems incorporate 
a mechanism for processing XML-specific queries, usually in XPath or 
XQuery, and translating them into equivalent SQL statements which 
are executed in the relational engine.

This work describes a novel XPath processing approach that yields 
significant performance benefits while being quite easy to implement 
and combine with existing techniques. A key novel concept of our 
approach is the Primitive Path Fragment (PPF), which is a syntactic 
unit of an XPath expression. PPFs can be efficiently evaluated in 
a holistic fashion using a root-to-node path index and regular 
expression matching, to eliminate the need for structural joins. 
The second important part of our approach is a method based on the 
properties of Dewey encoding  for efficiently performing the 
necessary structural joins between PPFs.  

PPF-based XPath processing can be applied both to schema-oblivious 
and schema aware XML shredding. In schema-aware shredding, data 
are apportioned into several relations. The existence of schema 
information and its utilization in the translation, allows for 
optimizations, such as avoiding redundant root-to-node path filtering.

The experimental evaluation confirms the benefits of applying the 
PPF-based processing in conjunction with schema-aware XML shredding. 
Hence this work focuses on such a translation scheme. Our 
implementation of PPF-based processing is built on top of an Oracle 
10g-based XML management system using schema-aware XML shredding. 
In our experimental study, we are comparing our technique to the 
latest version of MonetDB/XQuery, our implementation of XPath 
accelerator on top of Oracle 10g, and the built-in XPath processor 
of a major commercial RDBMS, on a large number of representative 
XPath queries on different data sets.