Optimizing SPARQL query evaluation with a worst-case cardinality estimation based on statistics on the data

SPARQL is the w3c standard query language for querying data expressed in the Resource Description Framework (rdf). There exists a variety of sparql evaluation schemes and, in many of them, estimating the cardinality of intermediate results is key for performance, especially when the computation is distributed and the datasets very large. For example it helps in choosing join orders that minimize the size of intermediate subquery results. In this context, we propose a new cardinality estimation based on statistics about the data. Our cardinality estimation is a worst-case analysis tailored for sparql and capable of taking advantage of the implicit schema often present in rdf datasets (e.g. functional dependencies). This implicit schema is captured by statistics therefore our method does not need for the schema to be explicit or perfect (our system performs well even if there are a few " violations " of these implicit dependencies). We implemented our cardinality estimation and used it to optimize the evaluation of sparql queries: equipped with our cardinality estimation, the query evaluator performs better against most queries (sometimes by an order of magnitude) and is only ever slightly slower