Paper Info
Title
An efficient branch query rewriting algorithm for XML query optimization
Abstract
XML data usually consists of tree-structured hierarchical data, which affects the storing and searching mechanisms for XML. When storing XML data into databases the hierarchical relationships among XML nodes need to be considered. User’s search queries that specify hierarchical relationships among the nodes also require appropriate processing mechanisms. Structural join operations provide a solution to this problem by efficiently computing hierarchical relationships in XML databases based on the node numbering storage scheme. However, in order to process a branch query containing several hierarchical relationships on XML data, many structural joins need to be sequentially carried out and result in a high query execution cost. This paper proposes mechanisms to reduce the cost of processing branch pattern XML queries requiring multiple structural joins. We discuss two approaches for rewriting a query composed of a single branch, and then apply these approaches to general branch queries. The first approach uses the concept of equivalence class relationships among regular path expression queries. The second approach uses a bottom-up approach to reduce the overhead identified in the first scheme. Experimental results show that the proposed schemes can reduce the query execution cost by up to an order of magnitude of the original execution cost.
Year
DOI
Venue
2005
10.1007/11575801_45
OTM Conferences (2)
Keywords
Field
DocType
xml query optimization,tree-structured hierarchical data,general branch query,high query execution cost,hierarchical relationship,branch query,xml data,xml databases,xml node,storing xml data,processing branch pattern xml,efficient branch query,xml database,bottom up,path expressions,tree structure,hierarchical data,query optimization
Query optimization,XML framework,Efficient XML Interchange,XML Encryption,XML validation,Computer science,XML database,Algorithm,Theoretical computer science,XML schema,XML Signature
Conference
Volume
ISSN
ISBN
3761
0302-9743
3-540-29738-3
Citations 
PageRank 
References 
0
0.34
15
Authors
2
Name
Order
Citations
PageRank
Hyoseop Shin100.34
Minsoo Lee231531.33