Welcome to DiSC 2003
SIGMOD 2002
PODS 2002
SIGMOD RECORD 2002
ADBIS 2002
CIKM 2002
= CIKM'02 Website
= CIKM'02 Papers
= CIKM Workshop_1
= GIS'02 Papers
= CIKM Workshop_2
= DOLAP'02 Papers
= CIKM Workshop_3
<<< = WIDM'02 Papers>>>
CoopIS 2002
EDBT 2002
ER 2002
Data Engineering Bul
DEXA_EC-WEB 2002
DMKD 2002
DPDJ 2002
HYPERTEXT 2002
ICDE 2002
ICDM 2002
JCDL 2002
KDD 2002
KDD_EXPLORATIONS 20
KRDB 2002
MDM 2002
MIS 2002
RIDE 2002
SBBD 2002
SIGIR 2002
SIGIR FORUM 2002
SSDBM 2002
TODS 2002
TIME 2002
VLDB 2002
VLDBJ 2002

Honey, I shrunk the XQuery!: an XML algebra optimization approach


Xin Zhang, Bradford Pielech, and Elke A. Rundensteiner

  View Paper (PDF)  

Return to Advanced XML technologies and applications


Abstract

A lot of work is being done in the database community on mapping of XML data into and out of relational database systems, specifically, the query processing over such data using XQuery. We discuss our solution, the XML Algebra Tree (XAT), as part of our larger XML management system called Rainbow.Rainbow uses XQuery to describe the loading and extracting of XML data into relational systems and also for the execution of queries against pre-defined XML views of that stored data. The XML algebra tree of the query against those views is merged with the queries that define the views to form a larger tree. Because the XML formatting operators are interleaved with the computation operators, this XAT must then be optimized before being translated into one or more SQL statements that can be executed on the database. SQL translation is composed of computation pushdown and SQL generation.The computation pushdown splits the tree into the XML-specific and SQL-doable operators, which is then going to be converted into SQL statements. However, the XAT after computation pushdown may contain unreferenced columns or unused operators. Leaving these operators in the tree will create unnecessarily large SQL statements and will slow down the overall execution.Our main contributions to XML query processing, outlined in this paper, are threefold. One, we describe an algebra based on XATs for modeling XQuery expressions. Two, we propose rewriting rules to optimize XQueries by XAT operator cancel out. Lastly, we show a cutting algorithm to remove unreferenced columns and operators from the trees. We have fully implemented the techniques discussed in this paper in the Rainbow system. A preliminary experimental study compares the performance of execution before and after operator cancel out and cutting.


DiSC'03 © 2003 Association for Computing Machinery