XML Query Based on Indexed Sequential Table

Abstract:

The current study based on XML index and query mostly focuses on encoding and the structural relation. Region codings are widely used to improve XML query. In this paper postorder-traversal region coding is proposed. The postorder of a node’s all descendants consists of the region. Judging and ensuring structural relation of any two nodes just depend on this region, if the postorder of a node is in a region, ancestor/descendant structural relation can be ensured. Consequently, postorder-traversal region coding can effectively judge structural relation and avoid traversing the XML document tree. Based on region coding, many constructive structural query algorithms have been put forward. As we all know that Stack-Tree-Desc algorithm is one of these fine algorithms, AList and DList only need separately scan one time to judge structural relation, however some unnecessary nodes still be scanned. In order to solve this problem, Indexed Sequential Table algorithm is introduced. The optimized algorithm introduces Indexed Sequential Table to avoid scanning unwanted nodes when the two lists join to locate next node which participates in structural join. In this case, some nodes of AList and DList which don’t participate in structural joins can be jumped, the query efficiency is enhanced. As a result, ordered scanning is prevented, the consuming time of XML query shortens accordingly. Experiment results demonstrate the effectiveness of the improved coding and algorithm.

• Periodical: Advanced Materials Research (Volumes 532-533)
• Pages: 1177-1181
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.532-533.1177
• Online since: June 2012
• Authors: Yang Yang, Hai Ge Li
• Keywords: Indexed Sequential Table, Postorder-Traversal Region Coding, XML, XML Query

References

[1] Zhang C, Naughton J, De Witt D, et al. On supporting Containment queries in relational database management systems. In: Proceedings of the 2001 ACM SIGMOD international conference on management of data. Santa Barbara, California, United States. May 21-24, 2001. ACM Press. 425-436.

DOI: 10.1145/376284.375722

[2] Al-Khalifa S, Jagadish HV, Koudas N, Patel JM, Srivastava D, Wu Y. Structural joins: A primitive for efficient XML query pattern matching. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the 18th Int'l Conf. on Data Engineering (ICDE). San Jose: IEEE Computer Society, 2002. 141-152.

DOI: 10.1109/icde.2002.994704

[3] Li Q, Moon B. . Indexing and querying xml data for regular path expressions. In: Proceedings of the VLDB Conference, Roma, 2001, 361-370.

[4] Chien S-Y, Vagena Z, Zhang D, et al. Efficient Structural Joins on Indexed XML Documents. In: Proceedings of 28th International Conference on Very Large Data Bases (VLDB'02). Hong Kong, China. August 20-23, 2002. Morgan Kaufmann. 263-274.

DOI: 10.1016/b978-155860869-6/50031-7

[5] Jiang H, Lu H, Wang W, et al. XR-Tree: Indexing XML Data for Efficient Structural Joins. In: Proceedings of the 19th International Conference on Data Engineering (ICDE'03). Bangalore, India. March 5-8, 2003. IEEE Computer Society. 253-263.

DOI: 10.1109/icde.2003.1260797

[6] HU Jiang-ming, LI Jian-hua, DU Zhang-hua, WEI Feng. Efficient Labeling Mechanism for Dynamic XML Document Trees. Computer Engineering, 2010(19).

[7] IBM Corporation. XML data generator. http: /www. alphaworks. ibm. com/tech/xmlgenerator.