Research On Algorithm Of SPARQL Run-Time Query Optimization

SPARQL is the W3C recommendation query language that based on RDF graph matching mechanism. As increasingly large RDF data sets have been published on the Web, the existing query algorithms can not meet the demand for efficient access to query results.This paper first presented a run-time optimization solution for SPARQL. This paper designed a Join Graph model to represent the SPARQL query plan at run time. Through the implementation of join operation using sampling, the estimated size of the results could be found. Then we could get the estimated value of the edge. The premise of the program was to build the Join Graph. The algorithm proposed to visit the Join Graph using breadth-first way, determine the best query plan, execute it, update the Join Graph with results. Repeated the steps of choosing the best path, executing and updating the Join Graph until all the paths in the Join Graph were executed. At the same time it could detect data relation so as to reduce the unused intermediate result. In this paper, it used the open source RDF query engine Sesame to achieve the above design and used SP2Bench to do experiment between ROS and the original algorithm in Sesame. The test results showed that comparing with the existing optimization algorithms in Sesame, ROS could reduce the join numbers and improve the performance.In summary, the solution which using sampling techniques to estimate the value of query plans, intersecting the query plan selection, implementation and Join Graph update together, can reduce the number of Join operation, and make better performance in optimizing complex SPARQL queries.