Rewriting Queries over Summaries of Big Data Graphs.
Mariano P. Consens, Valeria Fionda, Shahan Khatchadourian, Giuseppe Pirrò · 2014
This short paper reports on the benefits that traversal queries over existing graph stores (such as RDF databases) can gain from a class of optimizations based on summaries. Summaries, also known as structural indexes, have been extensively covered in the literature (see [2] for a brief overview). Despite this, summary-based optimizations are not widely implemented. To make both graph traversal queries and summaries readily available in existing RDF stores, we have devised a translation that outputs SPARQL queries that execute over sum-maries directly represented in RDF. In what follows, we give an overview of our proposal, illustrate it with an example, and mention preliminary evaluation results on real-world data. Overview. Our approach to summary-based optimization of graph traversal queries on top of SPARQL processors consists of three components. First, we have developed and implemented an algorithm that translates graph traversal queries (see [1, 6] for recent surveys) into SPARQL expressions. The graph traversal language we selected extends the expressiveness of Nested Regular Expressions [5] without compromis-ing the language’s low combined data and query complexity. Second, we construct and store summaries alongside the original graph in the RDF store.