A New Reachability Query Method for Graph-Structured XML Data


Article Preview

Query processing of graph-structured XML data is a rising topic in XML research field. This paper focuses on reachability query methods of graph-structured XML data. Encoding scheme of CDGX (Coding Directed Graph-structured XML data) is proposed in this paper, which not only can effectively solve the circle problem, but also avoiding a large number of intermediate data and saving storage space. And based on encoding scheme of CDGX, a new reachability query method RJDG (Reachability Judgment on Directed Graph) is put forward to. In RJDG, adjacent nodes in a same graph-structured XML document are got and stored beforehand. RJDG only needs to deal with the adjacent nodes to decide the reachability relationship between XML nodes. Experiments illustrate that RJDG is an efficient reachability query method.



Edited by:

Yuning Zhong




Y. Lu et al., "A New Reachability Query Method for Graph-Structured XML Data", Applied Mechanics and Materials, Vol. 235, pp. 394-398, 2012

Online since:

November 2012




[1] CHunhe Zhang: Efficient Structural Query Processing on Dynamic Graph-structured XML Data. Journal of Computer Research and Development. 44(Suppl. ), pp.374-378, (2007).

[2] SHuguang Xiong: Research on Query Processing of Graph-Structured XML Data. Master Thesis (2006).

[3] Chen L, Gupta A, Kurul ME: Stack-Based Algorithms for Pattern Matching on DAGs. Proc. of the Conf. on Very Large DataBases. Trondheim: ACM, pp.493-504, (2005).

[4] Hongzhi Wang, Jizhou Luo, Jianzhong Li: Efficient Subgraph Query Processing Algorithms on Graph-Structured XML Documents. Journal of Software, 20(9), pp.2436-2449, (2009).

DOI: https://doi.org/10.3724/sp.j.1001.2009.03421

[5] Hongzhi Wang,Jianzhong Li,Jizhou Luo, Hong Gao: Hash-based Subgraph Query Processing Method for Graph-structured XML Documents. Proc. of the Conf. on Very Large DataBases, pp.478-489, (2008).

DOI: https://doi.org/10.14778/1453856.1453909

[6] Schmidt A, Waas F, Kersten ML: XMark: A benchmark for XML data management. In: Bressan S, Chaudhri AB, Lee ML, etal., eds. Proc. of the 28th Int'l Conf. on Very Large Data Bases. Hong Kong: Morgan Kaufmann Publishers, pp.974-985, (2002).