Research On Key Technologies Of Access Structure Selection For Knowledge Graphs Based On Machine Learning

With the continuous development of modern knowledge extraction technology,various domains have constructed and published knowledge graphs.Although a large number of graph data management approaches are proposed,they are hard to address the challenges for large-scale,complex-pattern and frequently updating knowledge graphs.These challenges are summarized as the following two aspects.First,the complex pattern makes the access mode of knowledge graphs more complicated than that of relational data.The database administrators are usually responsible for the selection of graph data storage structure and index.However,the manual access structure selection method is difficult to meet the requirements of various applications due to the large scale of a knowledge graph.Also,it is hard for human to obtain the general view of a graph.Second,if the knowledge graph and its workloads change,the access structure of a knowledge graph needs to recognize the changes and adjust the storage structure and indexes in time to ensure the efficiency of query processing.However,it is hard for humans to complete the task since a knowledge graph is updated frequently.Therefore,the automatic access structure selection technique for knowledge graphs is needed,which automatically designs the storage structure based on the characteristics of both knowledge graph data and its workloads,and dynamically adjusts the storage structure and indexes according to the changes of data and workloads.In recent years,the rapid development of machine learning technology has provided opportunities for the automatic access structure selection of knowledge graph data.Considering that machine learning,especially deep learning,is suitable to describe the complex patterns and solve the complex optimization problems,this paper adopts machine learning techniques to predict the performance of knowledge graph storage structures,tune the storage structure of a knowledge graph,and select the index configurations for a knowledge graph automatically.The main research contents of this paper are summarized as follows:1.This paper studies the performance prediction problem for storage structure of a knowledge graph.That is,given a knowledge graph and its workload,predict the time costs to execute the workload under a specific storage structure.This paper proposes a machine-learning-based knowledge graph storage performance predictor,called Pre Kar,which is able to predict the performance of storage structures based on historical data.This paper proposes a candidate storage structure generator,which contains the maximum star subquery identification,predicate connected graph construction,and predicate combination search techniques.The storage structure generator is helpful to multiple the amount of training data.In addition,this paper designs a lightweight and effective embedding strategy for workloads and storage structures,which not only embeds the main features into the training model,but also guarantees the efficiency of the performance predictor.2.This paper studies the automatic tuning of storage structure for knowledge graphs based on reinforcement learning.That is,given a knowledge graph and its workload,the current storage structure,and the upper limit of graph database storage capacity,optimize the storage structure of the knowledge graph to minimize the workload costs and meet the graph database storage capacity budget.This paper designs a novel dual-store structure for knowledge graphs,which uses both graph store and relational store.To ensure the efficiency and adaptivity of the dual-store structure,this paper proposes a solution to the physical design tuning problem of the dual-store structure,called DOTIL,which is a reinforcement-learning-based dual-store physical design tuner.DOTIL automatically decides when and which data partition needs to be migrated from relational store to graph store based on dynamic workloads.DOTIL not only ensures the adaptability of the dualstore structure,but also accelerates the complex query processing.3.This paper studies the automatic index selection for knowledge graphs based on reinforcement learning.That is,given a knowledge graph,workloads,and the size constraint of indexes,produce the index configuration to minimize the workload costs.This paper proposes a reinforcement-learning-based index selector,called ANSWER,which is able to automatically determine the index configuration based on the historical workloads.This paper designs an efficient predicate filter,which not only determines which vertical partition tables are suitable to create indexes,but also reduces the action space size of the reinforcement learning model.In addition,this paper designs a lightweight index encoder,which only embeds the main features of the candidate index structures into the model,but also ensures the high efficiency of knowledge graph index selector.4.Based on the advancements in the above three key issues,this paper develops an automatic knowledge graph access structure selection system to enable automatic knowledge graph storage structure tuning and index selection,called APRIL.This system is able to automatically build the storage structure and index configuration for knowledge graphs with a user-friendly interface.APRIL is an automatic knowledge graph access structure selection system based on reinforcement learning,which includes three major functions,namely automatic storage structure selection,automatic index selection,and knowledge graph query processing.It provides the services of both automatic and user-customized knowledge graph access structure selection.The above four researches cover three important steps in machine-learning-based knowledge graph access structure selection,including “performance prediction of storage structure,automatic storage structure tuning and automatic index selection”respectively.This paper brings about solutions for each of the above aspects.Finally,an automatic knowledge graph access structure selection system based on reinforcement learning is implemented,by which the correctness,effectiveness and availability of the proposed solutions are verified.