A Dual-Store Structure for Knowledge Graphs

To effectively manage increasing knowledge graphs in various domains, a hot research topic, knowledge graph storage management, has emerged. Existing methods are classified to relational stores and native graph stores. Relational stores are able to store large-scale knowledge graphs and convenient in updating knowledge, but the query performance weakens obviously when the selectivity of a knowledge graph query is large. Native graph stores are efficient in processing complex knowledge graph queries due to its index-free adjacent property, but they are inapplicable to manage a large-scale knowledge graph due to limited storage budgets or inflexible updating process. Motivated by this, we propose a dual-store structure which leverages a graph store to accelerate the complex query process in the relational store. However, it is challenging to determine
what
data to transfer from relational store to graph store at
what
time. To address this problem, we formulate it as a Markov Decision Process and derive a physical design tuner
${{\sf DOTIL}}$
based on reinforcement learning. With
${{\sf DOTIL}}$
, the dual-store structure is adaptive to dynamic changing workloads. Experimental results on real knowledge graphs demonstrate that our proposed dual-store structure improves query performance up to average 50.11 percent compared with the most commonly used relational stores.