Back To Top
University of Computer Studies, Yangon
Since XML (eXtensible Markup) is the popular language for the data over the Internet, managing and querying XML data are interested topic in research area. Based on the tree-structured XML data model, XML query is divided into two types such as simple path query and twig (branch) query. Moreover, XML query consists of two parts: structural constraints and value constraints for processing the tree-structured XML data. Therefore, in order to efficiently processing the XML data, indexing schemes are vital role in XML query processing systems. There are many indexing schemes are proposed in literature. Among them, structural path summary indexing scheme is efficiently support for path queries and achieve precise answer. It is also capable for solving the twig queries but additional join processing steps are needed to achieve precise answer. In this paper, we propose the extendible hashing scheme that is used as twig indexing scheme and is combined into existing 1-index (backward bisimilarity) structural path indexing scheme for processing twig queries that can be achieved precise answer. In this proposed system, structural and content search of twig query are processed on backward bisimilarity indexing scheme (1-index) and results of the twig query are extracted from twig hash indexing scheme. As a result, precise answers for twig query can be achieved without additional join processing steps. We have conducted on a series of experiments on the DBLP XML datasets to evaluate the performance of the proposed system
2. W3C XML Query Specification, Latest. http://www.w3.org/TR/xquery
3. W3C XML Path Language Specification, Latest. http://www.w3.org/TR/xpath
4. S. Abiteboul et al. The Lorel Query Language for Semistructured Data. In International Journal on Digital Libraries, 1(1):68-88.1997.
5. S. Abiteboul, P. Buneman, and D. Suciu, Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, 1999.
6. S.Al-Khalifa, H.V.Jagadish, J.M.Patel, Y.Wu, N.Koudas and D.Srivastava. Structural Joins: A primitive for efficient XML query pattern matching. In Proc.of ICDE, 2002, pp.141-154.
7. N.Bruno, N.Koudas and D.Srivastava. Holistic twig joins: Optimal XML pattern matching. In Proc.of SIGMOD, 2002, pp.310-321.
8. S.Chein,Z.Vagena, D.Zhang, V.Tsotras, C.Zaniolo. Efficient structural joins on indexed XML documents. In Proc. of 28th International Conference on Very Large Data Bases, 2002, pp. 263-274.
9. T. Chinenyanga and N. Kushmerick. An Expressive and Efficient Language for XML Information Retrieval. In Journal of the American Society for Inf.Sci. and Tech., 53 (6):438-453, 2002.
10. Q. Chen, A. Lim, and K.W. Ong, “D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data,” Proc. of 22nd ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’03), 2003.
11. Deutsch, M. Fernandez, D. Florescu, A.Levy and D.Suciu. XML-QL:A query language for XML.In Proc.of 8th Interntational World Wide Web Conference,1999.
12 G.Gou, R.Chirkova. Efficiently Querying Large XML Data Repositories: A Survey. Transactions on Knowledge and Data Engineering, 2007, 19(10), 1381-1403.
13 R. Goldman and J. Widom, “DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases,”Proc. 23rd Int’l Conf. Very Large Data Bases (VLDB ’97), 1997.
14 D.K.Fisher, F.Lam, W.M.Shui and R.K.Wong. Dynamic Labeling Schemes for Ordered XML Based on Type Information. In Proc.of the 17th Australasian Database Conference, 2006, pp. 59-68.
15 R. Kaushik, P. Shenoy, P. Bohannon, and E. Gudes, “Exploiting Local Similarity for Indexing Paths in Graph-Structured Data,” Proc. 18th IEEE Int’l Conf. Data Eng. (ICDE ’02), 2002.
16 R. Kaushik, P. Bohannon, J.F. Naughton, and H.F. Korth, “Covering Indexes for Branching Path Queries,” Proc. of 21st ACM SIGMOD Int’l Conf. Management of Data SIGMOD ’02), 2002.
17 Q.Li, B.Moon. Indexing and querying XML data for regular path expressions. In Proc. of 27th International Conference on Very Large Data Bases, 2001, pp. 361-370.
18 S.Mohammad and P.Martin. XML Structural Indexes. Technical Report 2009-560, School of Computing, Queen's University, June 2009.
19 T. Milo and D. Suciu, “Index Structures for Path Expressions,” Proc. of 7th Int’l Conf. Database Theory (ICDT ’99), 1999.
20 P.O’Neil, E.O’Neil, S.Pal, I.Cseri, G.Schaller and N.Westbury. ORDPATHs: Insert-Friendly XML Node Labels. In Proc.of SIGMOD, 2004, pp. 903-908.
21 D. Park. Concurrency and automata on infinite sequences. In Theoretical Computer Science, 5th GI-Conf., LNCS 104, pages 167–183. Springer-Verlag, Karlsruhe, Mar. 1981.
22 J. Robie et al. XQL (XML Query Language). http://www.ibiblio.org/xql/xql-proposal.html. August 1999.
23 I.Tatarinov, S.D.Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita and C.Zhang. Storing and Querying Ordered XML Using a relational Database System. In Proc. of SIGMOD, 2002, pp. 204-215.
24 H.Wu, T.W.Ling, B.Chen and L.Xu. Twig Table: Using Semantics in XML Twig Pattern Query Processing. Journal on Data Semantics (JoDS) XV, 2011.
25 W. Wang, H. Wang, H. Lu, H. Jiang, X. Lin, and J. Li, “Efficient Processing of XML Path Queries Using the Disk-Based F&B Index,” Proc. of 31st Int’l Conf. Very Large Data Bases (VLDB ’05), 2005.
26 C.Zhang, J.Naughton, D.DeWitt, Q.Luo and G.Lohman. On Supporting containment Queries in Relational Database Management Systems. In Proc. of SIGMOD, 2001, pp.425-436.