View Selection over Knowledge Graphs in Triple Stores

Download PDF

Abstract

Knowledge Graphs (KGs) are collections of interconnected and annotated entities that have become powerful assets for data integration, search enhancement, and other industrial applications. Knowledge Graphs such as DbPedia may contain billion of triple relations, while being intensively queried with millions of queries per day. A prominent approach to enhance query answering on Knowledge Graph databases is View Materialization, ie., the materialization of an appropriate set of computations that will improve query performance. We study the problem of view materialization and propose a view selection technique that effectively processes a query workloads with more than a million queries. Our approach heavily relies on subgraph pattern mining techniques that allow to create efficient summarizations of massive query workloads while also identifying the candidate views for materialization. In the core of our work is the correspondence between the view selection problem to that of Maximizing a Nondecreasing Submodular Set Function Subject to a Knapsack Constraint. The latter leads to a tractable view-selection process for native triple stores that allows a $(1-e^{-1})$-approximation of the optimal selection of views. Our experimental evaluation shows that a view selection process that takes a few minutes allows the creation of materialized views that accelerate the execution of specific queries within the workload more than 98%.