Research On Reachability Query And Optimization Method For Large-Scale Directed Acyclic Graphs

As a complex structure of common data structures, graphs are widely used in the emerging fields of XML databases, social networks, geographical navigation and ontology queries. With the explosive growth of graph data in the formation technologies, the structures of graph data become increasingly complex.And analysis, storage and management of graph data are facing an unprecedented challenge. As a common analysis technology in the large-scale DAG graph data, reachability query plays the most fundamental role. Facingthe large-scale graphs, however,most existing reachability queryschemesshow the defect of query inefficiency. Thus, for large-scale DAG graphs, efficient reachability query and optimizationof databases management are crucial.To solve the above problems, this paper intensive studied the research on reachability query and optimization method for large-scale DAG graphs.First, the paper proposes a labeling index method based on graph stratification(GSL, Graph Stratification Labeling), which uses the graph stratification as the pretreatment process. Using the maximum matching properties of bipartite graph to link each level of node which sets into a disjoint chain structure and minimize the original large-scale graph. Then, according to the properties of each node and the reachability relationship between nodes, we create labels for node, contains single chain-in label and chain-out labels.Then, this paper presents two new reachability query methods based on the GSL index method, namely chain-in reachability query methodand chain-out reachability querymethod. Meanwhile, based on the properties of graph stratification and maximum matching graph, two optimization methods on reachability query are proposed, namely the optimization method based on graph stratification and the optimization method based on transitivity.Finally, by experimenting onthe simulated data sets and real data sets, analyze and compare the reachability queryalgorithmsand its index algorithm in this paper with the existing algorithms. Experiments have been performed, showing that our reachability query approach has a very good query performance on the real graph network, large-scale sparse graphs and dense graphs, and greatly improves the reachability query efficiency.