Path Based Storage and Metadata Guided XPath Evaluation

of data, efficient evaluation of queries on XML data
is a major research issue. Structural join based techniques
are well known for XPath evaluation. For the long path expressions,join techniques are not efficient as they increase
the number of joins and disk I/O cost. Whereas, path based
techniques try to reduce the number of joins. In this talk,
we propose a metadata guided query evaluation technique
which uses path based storage. We propose a new way of
organizing the node data of an XML file. We use interval encoding
for the nodes. In addition, we use Strong DataGuide
to assign integer path labels to distinct paths in the data
tree. An element list is maintained for each distinct path
consisting of nodes that can be reached by that path. The
Element-Map gives the one-to-many mapping between element
names (or tag names) to element lists with nodes
having that tag-name. The Path-Map gives the root-to-leaf
path for a given path label. Using these structures, we find
that we can combine top-down path matching and bottom-up
node selections to efficiently perform linear path expression
evaluation. For twig queries, we perform structural
joins at branch points. Through experimental evaluation on
standard data sets, we show that our approach outperforms
the existing path-index based approaches which in turn outperform
structural join methods.