• Articles •     Next Articles

Structural Join and Staircase Join Algorithms of Sibling Relationship

Chang-Xuan Wan and Xi-Ping Liu   

  1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China Jiangxi Key Laboratory of Data and Knowledge Engineering, Nanchang 330013, China
  • Received:2006-05-01 Revised:2006-12-18 Online:2007-03-10 Published:2007-03-10

The processing of XML queries can result in evaluation of various structural relationships. Efficient algorithms for evaluating ancestor-descendant and parent-child relationships have been proposed. Whereas the problems of evaluating preceding-sibling-following-sibling and preceding-following relationships are still open. In this paper, we studied the structural join and staircase join for sibling relationship. First, the idea of how to filter out and minimize unnecessary reads of elements using parent's structural information is introduced, which can be used to accelerate structural joins of parent-child and preceding-sibling-following-sibling relationships. Second, two efficient structural join algorithms of sibling relationship are proposed. These algorithms lead to optimal join performance: 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. We also discussed the staircase join algorithm for sibling axes. Studies show that, staircase join for sibling axes is close to the structural join for sibling axes and shares the same characteristic of high efficiency. Our experimental results not only demonstrate the effectiveness of our optimizing techniques for sibling axes, but also validate the efficiency of our algorithms. As far as we know, this is the first work addressing this problem specially.

Key words: Polymorphic types; type theory.;

[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.
[1] Fu Yuxi;. Structures Definable in Polymorphism [J]. , 1998, 13(6): 579-587.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved