Implementation And Test Of Graph Database Query Compiler Based On Cypher

Over the past decades,with the development of the Internet of things,social networks and other fields,an increasing number of massive mesh topology data sets are faced.The original mature and sound relational database does not do well in dealing with this kind of data.The main reason is that the relational model will cause a large number of table connection operations,resulting in great computational costs.Most No SQL databases,whether key value database,document database or column database,they are difficult to be used to associate data and graphs,so graph database comes into being.Graph database embraces connection,which is the best choice for storing and processing this kind of data.This thesis studies the query engine of graph database,designs and implements the query compilation system of graph database based on some query optimization technologies of mature relational database,aiming at cypher query language of graph database Neo4 j,and puts forward an innovative and feasible design for the correctness test of query compiler.The main points of this thesis are as follows:1.A query compiler of graph database based on cypher query language is designed and implemented.The query optimization adopts the model based on cost estimation.In the cost estimation,parameters reflecting the concurrent access of nodes and edges in the storage engine are introduced for specific transaction mechanism,so as to further optimize the performance of plan execution2.Design and implement a random statement generator based on cypher statement, and use the random coverage algorithm based on cypher grammar production t generate a series of random cypher statements.3.A pseudo execution algorithm is designed and implemented to verify the correctness of the execution plan.It can verify the correctness of the results of the query engine without the underlying computing and storage engine.The pseudo execution algorithm includes two execution stages.One is to check whether each operator in the execution plan can be executed and update the query graph and filter tree in the execution stage as the execution result according to the information in the operator.The other is to compare the result with the query graph and filter tree in the original cypher statement and judge whether the current execution plan can be executed correctly according to the comparison results.The test algorithm in this thesis has strong practical value in engineering practice.The testing method for graph query compiler proposed in this thesis helps to locate many errors in the query compilation,simplifies the testing difficulty of graph database kernel development,and has strong practical value in engineering practice.