Formulation and efficient execution of frequent queries in RDF databases

Abstract

In this dissertation we first study issues regarding the formulation of frequent queries using semantic data models. We have conducted an extensive empirical analysis for the domain of cultural heritage which led us to identify a set of frequent/recurrent queries that can be considered as predefined queries for the specific domain. By representing such information in the form of RDF graphs, we identify a set of structural types, further developed as query patterns, that are sufficient to represent all the recorded predefined questions. These query patterns are expressed as Datalog rules and SPARQL queries, the variables of which can represent the various domain concepts. We then focus on the efficient execution of frequent queries in RDF databases. We define the notion of shortcut as a one-step substitute for a path query over RDF data, and we study the problem of selecting the most beneficial shortcuts to materialize given a data graph and a query workload. Materializing shortcuts requires additional space thus giving rise to a trade-off between space consumption and speed of query execution. We formulate the shortcut selection problem under a space constraint, which is reduced to a variation of the knapsack problem, known to be NP-hard. To address this problem we develop a greedy algorithm that incrementally selects the most beneficial shortcut to materialize, based on the per unit space benefit, that does not exceed the remaining budget. We also explore an alternative approach whereby, instead of considering a space constraint, we penalize space consumption by the shortcuts through appropriate cost terms in the objective function. The bi-criterion integer linear optimization problem thus obtained is subsequently relaxed to yield a totally unimodular linear optimization problem. Exploiting this feature, which guarantees integrality of the solutions, we develop an additional algorithm that includes the totally unimodular problem as a subproblem and introduces cuts to cope with violated constraints of the original problem. Two different heuristic methods for generating cuts are explored. The performance of all the proposed algorithms is extensively evaluated through a set of experiments, which demonstrate that shortcut materialization significantly reduces the query execution time, while keeping space requirements low.