An Efficient Structural Index for Branching Path Queries

Structural index, which acts as a schema, plays an important role in query optimization over XML and semi-structured data. On the basis of the inter-relevant successive trees (IRST), we extend IRST to the XML data graph, introduce the new equivalence relation of k-l-similarity, and propose IRST (k, l)-index, an adaptive structural index that can support branching or simple path queries efficiently. Compared with the same kind of indexes, our experiments show that IRST (k, l)-index performs more efficiently in terms of space consumption and query performance for branching or simple paths, while using significantly less construction time.