Research On Conjunctive Regular Path Queries Over Large-Scale Knowledge Graphs

On the one hand,the inconsistent problem of knowledge graph in data model,query language,etc.,hinders its wider application.A unified knowledge graph data management system is urgently needed to integrate the advantages of existing knowledge graph data models and query languages and eliminate the shortcomings.On the other hand,with the growing popularity and application of artificial intelligence,the scale of knowledge graph data is dramatically increasing.Since the complexity of conjunctive regular path query(CRPQ),the core operator on knowledge graphs,is in polynomial time with respect to the scale of the knowledge graphs,currently,there has been no efficient method to process CRPQs on large-scale knowledge graphs.A unified relational knowledge graph conjunctive regular path query processing method is proposed in this thesis,which can be adapted to any relational knowledge graph data management system where entities and edges are type-clustered.Furthermore,frequent path indexes are constructed to improve query efficiency and reducing query cost.For the regular expression included in the conjunctive regular path queries,the path decomposition method based on the Brzozowski’s derivatives is used to decompose the paths.Meanwhile,the histogram of the data is utilized to determine the join orders between the relational tables to accelerate queries.Based on the proposed conjunctive regular path query processing method and frequent path indexing method,a unified knowledge graph data management system is developed.SPARQL and Cypher statements are transformed into unified query semantics in the form of relational algebra.Users are allowed to query with different languages to operate the same knowledge graph without knowing its underlying data model.Moreover,a unified Web interface is provided to visualize the results of the conjunctive regular path queries.The final results of the queries are displayed in the form of graphs,and the query plans behind the queries are in the form of trees.In addition,the translation feature between SPARQL and Cypher is provided in the Web interface to intuitively display the alignment process for two languages.Extensive experiments on large-scale synthetic data sets and real-world data sets were conducted.The experimental results show that the conjunctive regular path query processing method and frequent path indexing method proposed in this thesis are effective,and have significant advantages over the existing knowledge graph data management systems.The query efficiency of the basic conjunctive regular path query processing method can generally higher than that of g Store and Neo4 j,and the CPRQs can be accelerated by at most 2 orders of magnitude.After constructing the frequent path indexes,the query efficiency of the existing knowledge graph data management system can be improved by 2 to 3 orders of magnitude.