SPARQL basic graph pattern optimization using selectivity estimation

TLDR

The paper formalizes Basic Graph Pattern optimization for SPARQL queries on main‑memory RDF graphs and defines selectivity‑based heuristics to address it. The authors devise heuristics ranging from simple variable counting to sophisticated selectivity estimation, employing customized RDF summary statistics to estimate joined triple‑pattern selectivity and guide efficient optimization. Evaluation on the Lehigh University Benchmark demonstrates the heuristics’ performance and provides detailed discussion of selected cases.

Abstract

In this paper, we formalize the problem of Basic Graph Pattern (BGP) optimization for SPARQL queries and main memory graph implementations of RDF data. We define and analyze the characteristics of heuristics for selectivity-based static BGP optimization. The heuristics range from simple triple pattern variable counting to more sophisticated selectivity estimation techniques. Customized summary statistics for RDF data enable the selectivity estimation of joined triple patterns and the development of efficient heuristics. Using the Lehigh University Benchmark (LUBM), we evaluate the performance of the heuristics for the queries provided by the LUBM and discuss some of them in more details.