We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A relational model for XML structural joins and their size estimations.
- Authors
Luo, Cheng; Jiang, Zhewei; Hou, Wen-Chi; Yan, Feng; Zhu, Qiang
- Abstract
XML structural joins, which evaluate the containment (ancestor-descendant) relationships between XML elements, are important operations of XML query processing. Estimating structural join size accurately and quickly is crucial to the success of XML query plan selection and the query optimization. XML structural joins are essentially complex θ-joins, which render well-known estimation techniques for relational equijoins, such as discrete cosine transform, wavelet transform, and sketch, not applicable. In this paper, we model structural joins from a relational point of view and convert the complex θ-joins to equijoins so that those well-known estimation techniques become applicable to structural join size estimation. Theoretical analyses and extensive experiments have been performed on these estimation methods. It is shown that discrete cosine transform requires the least memory and yields the best estimates among the three techniques. Compared with state-of-the-art method IM-DA-Est, discrete cosine transform is much faster, requires less memory, and yields comparable estimates.
- Subjects
DATABASES; XML (Extensible Markup Language); INTERNET; DOCUMENT markup languages; ESTIMATION theory
- Publication
Knowledge & Information Systems, 2008, Vol 16, Issue 1, p97
- ISSN
0219-1377
- Publication type
Article
- DOI
10.1007/s10115-007-0089-z