Abstract
Queries on XML data usually involve selections on contents (values) of nodes and structural relationships between nodes. While querying by values can borrow from traditional database technologies, how to efficiently evaluate structural portion of a query is critical to the performance of XML query processing engines. One representative approach to evaluate the structural portion is information retrieval style processing using inverted lists. Nodes of the same label are collected in one list. The containment relationship of two nodes is evaluated by performing structural join on two lists. The major challenge of this approach is the high I/O cost to access the lists on disk. In this thesis, we proposed a new index structure on the inverted lists based on structural relationships between nodes. Nodes in one list can be further classified to sub-lists by which children/ancestors/parent they have. Thus, if we know the class to which candidate nodes belong, we can directly fetch the sub-list of the class and skip unnecessary entries. Our experiments show the benefit of the proposed approach in highly irregular XML data.