ABSTRACT
This paper focuses on selectivity estimation for SPARQL graph patterns, which is crucial to RDF query optimization. The previous work takes the join uniformity assumption, which would lead to high inaccurate estimation in the cases where properties in SPARQL graph patterns are correlated. We take into account the dependencies among properties in SPARQL graph patterns and propose a more accurate estimation model. We first focus on two common SPARQL graph patterns (star and chain patterns) and propose to use Bayesian network and chain histogram for estimating the selectivityof them. Then, for an arbitrary composite SPARQL graph pattern, we maximally combines the results of the star and chain patterns we have precomputed. The experiments show that our method outperforms existing approaches in accuracy.
- M. Stocker, A. Seaborne, A. Bernstein, C. Kiefer: SPARQL basic graph pattern optimization using selectivity estimation. In WWW, pages:595--604, 2008. Google ScholarDigital Library
- T. Neumann, G. Weikum: RDF-3X: a RISC-style engine for RDF. PVLDB 1(1): 647--659, 2008. Google ScholarDigital Library
Index Terms
- Selectivity estimation for SPARQL graph pattern
Recommendations
SPARQL basic graph pattern optimization using selectivity estimation
WWW '08: Proceedings of the 17th international conference on World Wide WebIn 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 ...
Estimating selectivity for joined RDF triple patterns
CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge managementA fundamental problem related to RDF query processing is selectivity estimation, which is crucial to query optimization for determining a join order of RDF triple patterns. In this paper we focus research on selectivity estimation for SPARQL graph ...
Selectivity estimation for hybrid queries over text-rich data graphs
EDBT '13: Proceedings of the 16th International Conference on Extending Database TechnologyMany databases today are text-rich, comprising not only structured, but also textual data. Querying such databases involves predicates matching structured data combined with string predicates featuring textual constraints. Based on selectivity estimates ...
Comments