XR-tree: indexing XML data for efficient structural joins

XML documents are typically queried with a combination of value search and structure search. While querying by values can leverage traditional database technologies, evaluating structural relationship, specifically parent-child or ancestor-descendant relationship, between XML element sets has impose...

Full description

Saved in:
Bibliographic Details
Main Authors: Haifeng Jiang, Hongjun Lu, Wei Wang, Ooi, B.C.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Cost function
Councils
Database languages
Indexing
Information retrieval
Query processing
Spatial databases
Web sites
XML
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:XML documents are typically queried with a combination of value search and structure search. While querying by values can leverage traditional database technologies, evaluating structural relationship, specifically parent-child or ancestor-descendant relationship, between XML element sets has imposed a great challenge on efficient XML query processing. We propose XR-tree, namely, XML region tree, which is a dynamic external memory index structure specially designed for strictly nested XML data. The unique feature of XR-tree is that, for a given element, all its ancestors (or descendants) in an element set indexed by an XR-tree can be identified with optimal worst case I/O cost. We then propose a new structural join algorithm that can evaluate the structural relationship between two XR-tree indexed element sets by effectively skipping ancestors and descendants that do not participate in the join. Our extensive performance study shows that the XR-tree based join algorithm significantly outperforms previous algorithms.
DOI:10.1109/ICDE.2003.1260797