Abstract
The structure queries of XQuery result in structural joins of various relationships. While several efficient algorithms have been proposed in evaluating ancestor–descendant and parent–child relationships, few efforts are put on the study on sibling relationship. In this paper, we study the structural joins of preceding-sibling–following-sibling relationship. To accelerate structural joins of parent–child and preceding-sibling–following-sibling relationships, optimizing techniques are employed to filter out and minimize unnecessary reads of elements using parent’s structural information. Then, two efficient structural join algorithms in evaluating sibling relationship are proposed, in which nodes that do not participate in the join can be judged beforehand and then skipped using B+-tree index. Besides, each element list joined is scanned sequentially once at most. Furthermore, output of join results is sorted in document order. Our experimental results not only demonstrate the effectiveness of our optimizing techniques for sibling axes, but also validate the efficiency of our algorithms. To the best of our knowledge, this is the first effort that addresses this problem.
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
W3C. XQuery 1.0: A XML Query Language. W3C Working Draft
W3C. XML Path Language (XPath) Version 2.0. W3C Working Draft, http://www.w3.org/TR/xpath20/
Zhang, C., Naughton, J., DeWitt, D., et al.: On Supporting Containment Queries in Relational Database Management Systems. In: Proc of the SIGMOD Conf., 2001, pp. 426–437 (2001)
Li, Q., Moon, B.: Indexing and Querying XML Data for Regular Path Expressions. In: Proc of the VLDB Conf., 2001, pp. 361–370 (2001)
Yun-sheng, L., Chang-xuan, W., Sheng-hua, X.: Efficiently Implementing RPE Query in a RDBMS. Mini-Micro Systems 24(10), 1764–1771 (2003) (In Chinese)
Al-Khalifa, S., Jagadish, H.V., Koudas, N., et al.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching. In: Proc of the ICDE Conf., 2002, pp. 141–152 (2002)
Shu-yao, C., Vagena, Z., Donghui, Z., et al.: Efficient Structural Joins on Indexed XML Documents. In: Proc. of the VLDB Conf., 2002, pp. 263–274 (2002)
Bruno, N., Koudas, N., Srivastava, D.: Holistic Twig Joins: Optimal XML Pattern Matching. In: Proc. of the SIGMOD Conf., 2002, pp. 310–321 (2002)
Jiang, H., Wang, W., Lu, H., et al.: Holistic Twig Joins on Indexed XML Documents. In: Proc. of the VLDB Conf., 2003, pp. 273–284 (2003)
Wu, Y., Patel, J.M., Jagadish, H.V.: Structural Join Order Selection for XML Query Optimization. In: Proc. of the ICDE Conf., 2003, pp. 443–454 (2003)
Jiang, H., Lu, H., Wang, W., et al.: XR-Tree: Indexing XML Data for Efficient Structural Joins. In: Proc. of the ICDE Conf., 2003, pp. 253–264 (2003)
Wang, W., Jiang, H., Lu, H., et al.: PBiTree Coding and Efficient Processing of Containment Joins. In: Proc. of the ICDE Conf., 2003, pp. 391–402 (2003)
Grust, T.: Accelerating XPath Location Steps. In: Proc. of the SIGMOD Conf., 2002, pp. 109–120 (2002)
Dietz, P.F.: Maintaining order in a linked list. In: Proc. of the Annual ACM Symposium on Theory of Computing, pp. 122–127 (1982)
Wan, C., Liu, Y.: Efficient Supporting XML Query and Keyword Search in Relational Database Systems. In: Meng, X., Su, J., Wang, Y. (eds.) WAIM 2002. LNCS, vol. 2419, pp. 1–12. Springer, Heidelberg (2002)
Chang-xuan, W., Yun-sheng, L., Sheng-hua, X., Da-hai, L.: Indexing XML Data based on Region Coding for Efficient Processing of Structural Joins. Chinese Journal of Computers 28(1), 113–127 (2005) (In Chinese)
Grust, T., van Keulen, M., Teubner, J.: Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps. In: Proc. of the VLDB Conf., 2003, pp. 524–525 (2003)
Li, H., Lee, M.-L., Hsu, W., Chen, C.: An Evaluation of XML Indexes for Structural Join. SIGMOD Record 33(3), 28–33 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wan, C., Liu, X., Lin, D. (2005). Efficient Evaluation of Sibling Relationship in XPath Queries. In: Grumbach, S., Sui, L., Vianu, V. (eds) Advances in Computer Science – ASIAN 2005. Data Management on the Web. ASIAN 2005. Lecture Notes in Computer Science, vol 3818. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11596370_18
Download citation
DOI: https://doi.org/10.1007/11596370_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30767-9
Online ISBN: 978-3-540-32249-8
eBook Packages: Computer ScienceComputer Science (R0)