Abstract
A structural join evaluates structural relationship (parent-child or ancestor-descendant) between xml elements. It serves as an important computation unit in xml pattern matching, such as twig joins. There exists many work on efficient structural joins. In particular, indexes can expedite structural joins by skipping unmatchable elements. A typical use of indexes is to retrieve, for a given element, all its ancestor (or descendant) elements from an indexed set. However we observed two possible limitations with such index probes, namely false hit and false locate. A false hit means that an index probe touches unnecessary data besides real results; a false locate stands for a (wasted) probe that has zero answers. Obviously false hit and false locate can affect negatively the efficiency of structural joins. In this paper, we challenge ourselves to develop new structural join algorithm with no false hit and no false locate. We illustrate that R − Tree has the no false hit property (in contrast to B + -Tree) and hence is a good candidate for our algorithm. For no false locate, we propose a new function called Location which tells the probing points that will result in matches. We design and implement the Location function using a space-efficient structure, and present our algorithm using R − Tree together with the Location function. Extensive experiments show the efficiency of our algorithm.
This work is partially supported by the CUHK strategic grant (numbered 4410001) and the grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (CUHK418205).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Al-Khalifa, S., Jagadish, H.V., Koudas, N., Patel, J.M., Srivastava, D., Wu, Y.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching. In: Proceedings of ICDE (2002)
Chien, S.-Y., Vagena, Z., Zhang, D., Tsotras, V.J., Zaniolo, C.: Efficient structural joins on indexed XML documents. In: Proceedings of VLDB 2002 (2002)
Jiang, H., Lu, H., Wang, W., Ooi, B.C.: XR-Tree: Indexing XML data for efficient stuctural join. In: Proceedings of ICDE 2003 (2003)
Kamel, I., Faloutsos, C.: Updates for structure indexes. In: Proceedings of the 2nd Int’l Conference on Information and Knowledge Management(CIKM) (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tang, N., Yu, J.X., Wong, KF., Jiang, H. (2006). Fast Structural Join with a Location Function. In: Li Lee, M., Tan, KL., Wuwongse, V. (eds) Database Systems for Advanced Applications. DASFAA 2006. Lecture Notes in Computer Science, vol 3882. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11733836_55
Download citation
DOI: https://doi.org/10.1007/11733836_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33337-1
Online ISBN: 978-3-540-33338-8
eBook Packages: Computer ScienceComputer Science (R0)