Topological Queries on Graph-structured XML Data: Models and Implementations

Authors: Hongzhi Wang, Jianzhong Li, Jizhou Luo

Abstract:

In many applications, data is in graph structure, which can be naturally represented as graph-structured XML. Existing queries defined on tree-structured and graph-structured XML data mainly focus on subgraph matching, which can not cover all the requirements of querying on graph. In this paper, a new kind of queries, topological query on graph-structured XML is presented. This kind of queries consider not only the structure of subgraph but also the topological relationship between subgraphs. With existing subgraph query processing algorithms, efficient algorithms for topological query processing are designed. Experimental results show the efficiency of implementation algorithms.

Keywords: XML, Graph Structure, Topological query.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1063086

References:

[1] S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The lorel query language for semistructured data. Int. J. on Digital Libraries, 1(1):68-88, 1997.
[2] A. Bonifati and S. Ceri. Comparative analysis of five xml query languages. SIGMOD Record, 29(1):68-79, 2000.
[3] L. Chen, A. Gupta, and M. E. Kurul. Stack-based algorithms for pattern matching on dags. In VLDB, pages 493-504, 2005.
[4] J. Clark and S. DeRose. XML path language (XPath). In W3C Recommendation, 16 November 1999, http://www.w3.org/TR/xpath, 1999.
[5] I. F. Cruz, A. O. Mendelzon, and P. T. Wood. A graphical query language supporting recursion. In SIGMOD Conference, pages 323-330, 1987.
[6] R. H. G¨uting. Graphdb: Modeling and querying graphs in databases. In J. B. Bocca, M. Jarke, and C. Zaniolo, editors, VLDB-94, Proceedings of 20th International Conference on Very Large Data Bases, September 12- 15, 1994, Santiago de Chile, Chile, pages 297-308. Morgan Kaufmann, 1994.
[7] P. Haase, J. Broekstra, A. Eberhart, and R. Volz. A comparison of rdf query languages. In International Semantic Web Conference, pages 502- 517, 2004.
[8] H. He and A. K. Singh. Closure-tree: An index structure for graph queries. In ICDE, page 38, 2006.
[9] H. V. J. Rakesh Agrawal, Alexander Borgida. Efficient management of transitive relationships in large data and knowledge bases. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (SIGMOD 1989), pages 253-262, Portland, Oregon, May 1989.
[10] A. Schmidt, F. Waas, M. L. Kersten, M. J. Carey, I. Manolescu, and R. Busse. XMark: A benchmark for XML data management. In Proceedings of 28th International Conference on Very Large Data Bases (VLDB 2002), pages 974-985, 2002.
[11] L. Sheng, Z. M. O¨ zsoyoglu, and G. O¨ zsoyoglu. A graph query language and its query processing. In Proceedings of the 15th International Conference on Data Engineering, 23-26 March 1999, Sydney, Austrialia, pages 572-581. IEEE Computer Society, 1999.
[12] J. P. Tim Bray, C. M. Sperberg-McQueen, and F. Yergeau. Extensible markup language (xml) 1.0 (third edition). In W3C Recommendation 04 February 2004, http://www.w3.org/TR/REC-xml/, 2004.
[13] H.Wang,W.Wang, X. Lin, and J. Li. Subgraph join: Efficient processing subgraph queries on graph-structured xml document. In WAIM, pages 68- 80, 2005.
[14] X. Yan, P. S. Yu, and J. Han. Graph indexing: A frequent structure-based approach. In SIGMOD Conference, pages 335-346, 2004.
[15] X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD Conference, pages 766-777, 2005.
[16] V. J. T. Zografoula Vagena, Mirella Moura Moro. Twig query processing over graph-structured xml data. In Proceedings of the Seventh International Workshop on the Web and Databases(WebDB 2004), pages 43-48, 2004.