Research On Query Processing Of Graph-Structured XML Data

Because graph structure has powerful ability of data representation, it has been widely used in many aspects. With the development of computer science and web technology, the area of management and query over graph-structured data attracts more and more attention. XML can represent complex graph-structured data and has been one of data exchange standard. And the most important problem is how to efficiently store and query large XML data in database research area.The reachability query is an important kind query on XML data, for which some query methods based on reachability code and methods with index and other structures are proposed to improve query efficiency. Because the time spent on coding a graph is usually high, and these methods require large storage on disk, however, these methods are not able to deal with reachability query on large amount of data well. The path-based approaches break down a query into a set of paths, and join the original joint nodes, but this type of methods usually produce large middle result, therefore seriously reduce query efficiency.In this paper, a storage strategy and a query process method are presented, with the methods to represent and convert the query result. The storage model, which is composed of the reachability code of the two spanning trees and an efficient reachability index, can be used to determine the reachable relation between any two nodes in nearly constant time. Experiment shows the storage size is nearly linear to the number of nodes in the graph.The query processing method is holistic and for graph-structured query, the basic idea of which is to get the query result by traversing all the nodes of the query graph twice in different topologic order. Query result is represented by sets of result nodes, whose advantage lies in small storage space without any edge information of the result. If necessary, the sets of result nodes can be reconstructed to the sets of result graphs. Considering this, we proposed a result converting method. The analysis and experiment prove the time spent on query processing is nearly linear to the number of nodes in the graph, and the extra storage space used by query processing and the result storage space is low.This paper also gives the strict definition of reachability query and query...