An efficient branch query rewriting algorithm for XML query optimization

Hyoseop Shin, Minsoo Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationOn the Move to Meaningful Internet Systems 2005
Subtitle of host publicationCoopIS, DOA, and ODBASE - OTM Confederated International Conferences, CoopIS, DOA, and ODBASE 2005, Proceedings
Pages1629-1639
Number of pages11
DOIs
StatePublished - 2005
EventOTM Confederated International Conferences, CoopIS, DOA, and ODBASE 2005 - On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE - Agia Napa, Cyprus
Duration: 31 Oct 20054 Nov 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3761 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceOTM Confederated International Conferences, CoopIS, DOA, and ODBASE 2005 - On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE
Country/TerritoryCyprus
CityAgia Napa
Period31/10/054/11/05

Fingerprint

Dive into the research topics of 'An efficient branch query rewriting algorithm for XML query optimization'. Together they form a unique fingerprint.

Cite this