隨著語義網絡、社交網絡、生物信息網絡等新興應用的涌現及普及,圖數據的規模不斷增大,針對大規模圖數據的研究成為當今的研究熱點和難點。可達查詢是圖數據處理中頻繁使用的基礎性查詢,一些復雜的查詢能夠分解成包含多個可達查詢的操作集合,其高效處理具有重要意義。針對大規模圖的可達查詢,提出了一種基于平面圖覆蓋的大規模圖可達查詢處理方法。首先給出了一種基于平面圖覆蓋的可達標簽索引方法(planar graph cover based reachability labeling index method,PGCL)。該方法將最優樹作為預處理應用于平面圖覆蓋,通過最優樹創建、最優樹分解以及樹分解平面化處理,得到有向無環圖(directed acyclic graph,DAG)的平面圖覆蓋,最大限度地保留了原圖的可達性信息,從而基于覆蓋頂點創建二維標簽,用于壓縮可達傳遞閉包。設計了基于PGCL的可達查詢算法,有效實現了大規模圖的可達查詢。通過大量實驗證明了提出的查詢方法在保證查詢的高效性情況下,更好地壓縮了傳遞閉包,提高了可達查詢的處理效率。 With the springing up and wide use of emerging applications, such as semantic networks, social networks and bioinformatics networks, the research on increasingly large-scale graph data has become a hot and difficult problem. Reachability query is a fundamental query frequently used in graph data analysis and processing which has important effectiveness. Some complex queries can be decomposed into operation sets containing multiple reachability queries. For processing the reachability query of large graph, this paper proposes planar graph cover based reachability query processing in large graph. Firstly, this paper presents a planar graph cover based reachability labeling index method (PGCL). PGCL uses the optimal tree as the preprocessing to process the planar graph cover. By creating the optimal tree, optimal tree decomposition and some plane processing, this paper obtains the planar graph cover of a DAG (directed acyclic graph), which maximally retains the accessibility information of the original image, and creates labels for vertexes and compresses the reachability transitive closure. Then, this paper designs a reachability query algorithm based on PGCL to effectively process the reachability query of large graph. The experimental results on real data sets show that the proposed query method has better performance of compressing the transitive closure, and enhances the performance of reachability query