| The methods for graph data management have become a hot topic in the research area.By studying this topic,the knowledge in graph data can be extracted more efficiently.Therefore,this study focuses on the methods for graph data management,and proposes three research problems from the perspectives of graph theory and key technologies for graph query processing.Specifically,in terms of the graph theory,this study proposes the problem of designing a more expressive graph data model and a graph query language based on second-order logic.Then,in terms of the key technologies for graph query processing,in order to implement the selection operator in the graph data model based on the second-order logic and accelerate the process of subgraph matching query,which is a common query related to the graph query language,this study proposes the problem of subgraph matching optimization.Moreover,this study proposes the problem of discovering efficient analysis methods on temporal graphs,which is a more practical and common query related to the graph query language based on the second-order logic.Finally,a graph database management system is proposed based on the results of the above research problems.The primary contributions of this study are summarized as follows:1.About the problem of designing a more expressive graph data model and a graph query language based on second-order logic,this study presents a new graph data model,which has a stronger expressive power than the existing graph data models.Then,a corresponding graph query language named SOGQL is proposed.In detail,the graph algebra of the proposed graph data model can express more useful queries,and has the same expressive power as the graph calculus proposed based on the second-order logic.Besides,a prototype system named SOGDB is implemented based on SOGQL,and the experimental results on the real-world datasets confirm its efficiency.2.About the problem of subgraph matching optimization,this study presents a generalized community-structure-aware optimization framework for efficient subgraph matching,and the framework is named GCF.GCF obtains the results of subgraph matching by dealing with the community distribution schemes,and it contains three optimization strategies,i.e.,two-level symmetry-breaking,community-path-based pruning,and community-structure-based boundary pruning strategies.The experimental results on real-world datasets suggest that GCF can optimize different subgraph matching algorithms,and accelerate the process of subgraph matching significantly.In detail,for the existing subgraph matching algorithms used as the baselines,after they are optimized with GCF,the obtained new algorithms can be at least twice as fast as the original ones.In the best conditions,the algorithms obtained by optimizing the existing subgraph matching algorithms with GCF can be 3,000× faster than the original ones at most.3.About the problem of discovering efficient analysis methods on temporal graphs,this study proposes to consider the features of temporal graphs in the time dimension and topology dimension at the same time,and perform time-topology analysis.This study takes the temporal-and-topological cohesiveness as an example,and designs a new evaluation metric to measure the cohesiveness of temporal subgraphs.Then,based on the metric,this study presents two efficient time-topology analysis methods,i.e.,temporaland-topological cohesiveness evolution tracking and cohesive subgraph searching.For cohesive subgraph searching,this study proposes to compute the upper bounds of the temporal-and-topological cohesiveness values of the supergroups of vertex groups,and prune invalid vertex groups with the upper bounds.The experimental results demonstrate that the proposed metric and time-topology analysis methods are effective.Besides,the experimental results suggest that the proposed optimization method can accelerate the process of cohesive subgraph searching significantly.In detail,at the time that subgraphs are considered cohesive when their temporal-and-topological cohesiveness values are at least 0.9,the proposed optimization method can make the cohesive subgraph searching algorithm more than 1,000× faster.In conclusion,this study deals with the problems related to the theories and key technologies for query processing of graph data management based on second-order logic,and implements a graph database management system,to improve the efficiency of graph data management. |
