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

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.

Authors:

• Hongzhi Wang
• Jianzhong Li
• Jizhou Luo

Keywords:

• XML
• Graph Structure
• Topological query.

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.