Min Soo Lee , Yun Mi Kim , Soo Kyung Song

The KIPS Transactions:PartD, Vol. 14, No. 6, pp. 585-596, Oct. 2007
10.3745/KIPSTD.2007.14.6.585,   PDF Download:

Abstract

XML data generally consists of a hierarchical tree-structure which is reflected in mechanisms to store and retrieve XML data.Therefore, when storing XML data in the database, the hierarchical relationships among the XML elements are taken into consideration during the restructuring and storing of the XML data. Also, in order to support the search queries from the user, a mechanism is needed to compute the hierarchical relationship between the element structures specified by the query. The structural join operation is one solution to this problem, and is an efficient computation method for hierarchical relationships in an XML database based on the node numbering scheme. However, in order to process a tree structured XML query which contains a complex nested hierarchical relationship it still needs to carry out multiple structural joins and results in another problem of having a high query execution cost. Therefore, in this paper we provide a preprocessing mechanism for effectively reducing the cost of multiple nested structural joins by applying the concept of equivalence classes and suggest a query path reduction algorithm to shorten the path query which consists of a regular expression. The mechanism is especially devised to reduce path queries containing branch nodes. The experimental results show that the proposed algorithm can reduce the time required for processing the path queries to 1/3 of the original execution time.

Statistics
Cite this article