SPARQL basic graph pattern optimization using selectivity estimation
Markus Stocker, Andy Seaborne, Abraham Bernstein et al. · International World Wide Web Conference (WWW) · 2008
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.
Cited by 329 works. doi:10.1145/1367497.1367578 Open-access PDF
Authors
References
- Lecture Notes in Computer Science 1205
- Access path selection in a relational database management system
- Decomposition—a strategy for query processing
- OWL Web Ontology Language Reference
- SPARQL query language for RDF
- Resource Description Framework (RDF): Concepts and Abstract Syntax
- The design of POSTGRES
- Accurate estimation of the number of tuples satisfying a condition
- LUBM: A benchmark for OWL knowledge base systems
- Jena