Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 22 Issue 2
March  2007
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Chang-Xuan Wan, Xi-Ping Liu. Structural Join and Staircase Join Algorithms of Sibling Relationship[J]. Journal of Computer Science and Technology, 2007, 22(2): 171-181.
Citation: Chang-Xuan Wan, Xi-Ping Liu. Structural Join and Staircase Join Algorithms of Sibling Relationship[J]. Journal of Computer Science and Technology, 2007, 22(2): 171-181.
shu

Structural Join and Staircase Join Algorithms of Sibling Relationship

  • School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, ChinaJiangxi Key Laboratory of Data and Knowledge Engineering, Nanchang 330013, China

More Information
  • Received Date: April 30, 2006
  • Revised Date: December 17, 2006
  • Published Date: March 14, 2007
    Abstract
  • The processing of XML queries can result in evaluationof various structural relationships. Efficient algorithms forevaluating ancestor-descendant and parent-child relationships have beenproposed. Whereas the problems of evaluatingpreceding-sibling-following-sibling and preceding-following relationshipsare still open. In this paper, we studied the structural join andstaircase join for sibling relationship. First, the idea of how tofilter out and minimize unnecessary reads of elements using parent'sstructural information is introduced, which can be used to acceleratestructural joins of parent-child and preceding-sibling-following-siblingrelationships. Second, two efficient structural join algorithms ofsibling relationship are proposed. These algorithms lead to optimaljoin performance: nodes that do not participate in the join can bejudged 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. Wealso discussed the staircase join algorithm for sibling axes. Studiesshow that, staircase join for sibling axes is close to the structuraljoin for sibling axes and shares the same characteristic of highefficiency. Our experimental results not only demonstrate theeffectiveness of our optimizing techniques for sibling axes, but alsovalidate the efficiency of our algorithms. As far as we know, this isthe first work addressing this problem specially.
    • FullText(HTML)
    • References (20)
  • [1]
    World Wide Web Consortium. XQuery 1.0: An XML query language. W3C Candidate Recommendation. http://www. w3.org/TR/2006/CR-xquery-20060608/.
    [2]
    World-Wide Web Consortium. XML path language (XPath) version 1.0. W3C Recommendation. http://www.w3. org/TR/1999/REC-xpath-19991116.
    [3]
    Zhang C, Naughton J, DeWitt D -\it et al}. On supporting containment queries in relational database management systems. In -\it Proc. 2001 ACM Int. Conf. Management of Data} (-\it SIGMOD}), Santa Barbara, USA, May 21--24, 2001, pp.426--437.
    [4]
    Li Q, Moon B. Indexing and querying XML data for regular path expressions. In -\it Proc. 27th VLDB Conf.}, Roma, Italy, September 11--14, 2001, pp.361--370.
    [5]
    Liu Y, Wan C, Xu S. Efficiently implementing RPE query in an RDBMS. -\it Mini-Micro Systems}, 2003, 24(10): 1764--1771. (In Chinese)
    [6]
    Al-Khalifa S, Jagadish H V, Koudas N -\it et al}. Structural joins: A primitive for efficient XML query pattern matching. In -\it Proc. 18th Int. Conf. Data Engineering}, San Jose, California, USA, February 26--March 1, 2002, pp.141--152.
    [7]
    Chien S, Vagena Z, Zhang D -\it et al}. Efficient structural joins on indexed XML documents. In -\it Proc. 28th VLDB Conf.}, Hong Kong, China, August 20--23, 2002, pp.263--274.
    [8]
    Lam F, Shui W M, Fisher D K -\it et al}. Skipping strategies for efficient structural joins. In -\it Proc. 9th Int. Conf. Database Systems for Advanced Applications} (-\it DASFAA}). Jeju Island, Korea, March 17--19, 2004, pp.196--207.
    [9]
    Wang G, Sun B, Lv J -\it et al}. RPE query processing and optimization techniques for XML databases. -\it J. Comput. Sci. Technol.} 2004, 19(2): 224--237.
    [10]
    Catania B, Ooi B C, Wang W -\it et al}. Lazy XML updates: Laziness as a virtue of update and structural join efficiency. In -\it Proc. 2005 ACM Int. Conf. Management of Data} (-\it SIGMOD}), Baltimore, Maryland, June 14--16, 2005, pp.515--526.
    [11]
    Wan C, Liu Y, Xu S -\it et al}. Indexing XML data based on region coding for efficient processing of structural joins. -\it Chinese J. of Comput.}, 2005, 28(1): 113--127. (In Chinese)
    [12]
    Grust T. Accelerating XPath location steps. In -\it Proc. 2002 ACM Int. Conf. Management of Data} (-\it SIGMOD}), Madison, Wisconsin, June 03--06, 2002, pp.109--120.
    [13]
    Grust T, Keulen M V, Teubner J. Staircase join: Teach a relational DBMS to watch its (axis) steps. In -\it Proc. 29th VLDB Conf.}, Berlin, Germany, September 9--12, 2003, pp.524--525.
    [14]
    Dietz P F. Maintaining order in a linked list. In -\it Proc. Annual ACM Symp. Theory of Computing}, San Francisco, California, May 5--7, 1982, pp.122--127.
    [15]
    Che D R. Accomplishing deterministic XML query optimization. -\it J. Comput. Sci. Technol.} 2005, 20(3): 357--366.
    [16]
    Bruno N, Koudas N, Srivastava D. Holistic twig joins: Optimal XML pattern matching. In -\it Proc. 2002 ACM Int. Conf. Management of Data} (-\it SIGMOD}), Madison, Wisconsin, June 3--6, 2002, pp.310--321.
    [17]
    Jiang H, Wang W and Lu H -\it et al}. Holistic twig joins on indexed XML documents. In -\it Proc. 29th VLDB Conf}., Berlin, Germany, September 9--12, 2003, pp.273--284.
    [18]
    Chen T, Lu J and Ling T W. On boosting holism in XML twig pattern matching. In -\it Proc. 2005 ACM Int. Conf. Management of Data} (-\it SIGMOD}), Baltimore, Maryland, USA, June 14--16, 2005, pp.455--466.
    [19]
    Lu J, Ling T W, Chan C Y -\it et al}. From region encoding to extended Dewey: On efficient processing of XML twig pattern matching. In -\it Proc. 31st VLDB Conf.}, Trondheim, Norway, August 30--September 2, 2005, pp.193--204.
    [20]
    TreeBank. Available at http://www.cs.washington.edu/ research/xmldatasets/data/treebank.
    • Relative Articles

  • Related Articles

    [1]Hong-Bo Yin, Dong-Hua Yang, Kai-Qi Zhang, Hong Gao, Jian-Zhong Li. Indoor Uncertain Semantic Trajectory Similarity Join[J]. Journal of Computer Science and Technology, 2024, 39(6): 1441-1465. DOI: 10.1007/s11390-023-2418-4
    [2]Jun-Hua Fang, Peng-Peng Zhao, An Liu, Zhi-Xu Li, Lei Zhao. Scalable and Adaptive Joins for Trajectory Data in Distributed Stream System[J]. Journal of Computer Science and Technology, 2019, 34(4): 747-761. DOI: 10.1007/s11390-019-1940-x
    [3]Ji-Zhou Luo, Sheng-Fei Shi, Guang Yang, Hong-Zhi Wang, Jian-Zhong Li. O2iJoin: An Efficient Index-Based Algorithm for Overlap Interval Join[J]. Journal of Computer Science and Technology, 2018, 33(5): 1023-1038. DOI: 10.1007/s11390-018-1872-x
    [4]Shuo Shang, Kexin Xie, Kai Zheng, Jiajun Liu, Ji-Rong Wen. VID Join: Mapping Trajectories to Points of Interest to Support Location-Based Services[J]. Journal of Computer Science and Technology, 2015, 30(4): 725-744. DOI: 10.1007/s11390-015-1557-7
    [5]Fang-Fang Dong, Zhen Liu. A New Gradient Fidelity Term for Avoiding Staircasing Effect[J]. Journal of Computer Science and Technology, 2009, 24(6): 1162-1170.
    [6]Yong-Xuan Lai, Yi-Long Chen, Hong Chen. PEJA: Progressive Energy-Efficient Join Processing for Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(6): 957-972.
    [7]Dong-Hong Han, Guo-Ren Wang, Chuan Xiao, Rui Zhou. Load Shedding for Window Joins over Streams[J]. Journal of Computer Science and Technology, 2007, 22(2): 182-189.
    [8]LIU Tian. Some Structural Properties of SAT[J]. Journal of Computer Science and Technology, 2000, 15(5): 439-444.
    [9]Kian-Lee Tan. Optimization of Multi-Join Queries in Shared-Nothing Systems[J]. Journal of Computer Science and Technology, 1995, 10(2): 149-162.
    [10]Jin Hongping, Gu Junzhong. The Optimization of Distributed Join in C-POREL System[J]. Journal of Computer Science and Technology, 1987, 2(4): 276-286.
    • Supplements (0)

  • Cited by

    Periodical cited type(4)

    1. Zirui Liu, Hailin Zhang, Boxuan Chen, et al. CAFE+: Towards Compact, Adaptive, and Fast Embedding for Large-scale Online Recommendation Models. ACM Transactions on Information Systems, 2025. DOI:10.1145/3713072
    2. Hailin Zhang, Zirui Liu, Boxuan Chen, et al. CAFE: Towards Compact, Adaptive, and Fast Embedding for Large-scale Recommendation Models. Proceedings of the ACM on Management of Data, 2024, 2(1): 1. DOI:10.1145/3639306
    3. Dongdong Yan, Xiaofang Li, Qin Yang, et al. Key Technologies of Government Data Heterogeneity and Interoperation: A Survey. 2024 IEEE 7th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), DOI:10.1109/IAEAC59436.2024.10503635
    4. Bo Zhou, Yuwei Bao, Shuai Zhu. Information Extraction Algorithms and Semantic Understanding in Natural Language Processing. 2024 First International Conference on Software, Systems and Information Technology (SSITCON), DOI:10.1109/SSITCON62437.2024.10796174

    Other cited types(0)

Catalog

    Get Citation
    XML
    Article views (24) PDF downloads (5384) Cited by(4)
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return