Query optimization in XML structured-document databases |
| |
Authors: | Dunren Che Karl Aberer M Tamer Özsu |
| |
Affiliation: | (1) Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, USA;(2) School of Computer and Communication Sciences, école Polytechnique Fédérale de Lausanne, (EPFL), CH-1015 Lausanne, Switzerland;(3) School of Computer Science, University of Waterloo, N2L 3G1, Canada |
| |
Abstract: | While the information published in the form of XML-compliant documents keeps fast mounting up, efficient and effective query
processing and optimization for XML have now become more important than ever. This article reports our recent advances in
XML structured-document query optimization. In this article, we elaborate on a novel approach and the techniques developed
for XML query optimization. Our approach performs heuristic-based algebraic transformations on XPath queries, represented
as PAT algebraic expressions, to achieve query optimization. This article first presents a comprehensive set of general equivalences
with regard to XML documents and XML queries. Based on these equivalences, we developed a large set of deterministic algebraic
transformation rules for XML query optimization. Our approach is unique, in that it performs exclusively deterministic transformations
on queries for fast optimization. The deterministic nature of the proposed approach straightforwardly renders high optimization
efficiency and simplicity in implementation. Our approach is a logical-level one, which is independent of any particular storage
model. Therefore, the optimizers developed based on our approach can be easily adapted to a broad range of XML data/information
servers to achieve fast query optimization. Experimental study confirms the validity and effectiveness of the proposed approach. |
| |
Keywords: | XML query optimization XML query processing XML database Query transformation Deterministic query optimization |
本文献已被 SpringerLink 等数据库收录! |
|