Efficient Approximation of Well-Designed SPARQL Queries

摘要

Query response time often influences user experience in the real world. However, the time of answering a SPARQL query with its all exact solutions in large scale RDF dataset possibly exceeds users' tolerable waiting time, especially when it contains the OPT operations since the OPT operation is the least conventional operator in SPARQL. So it becomes essential to make a trade-off between the query response time and the accuracy of their solutions. That is, partial answers can be provided for users to reduce the response query time within their tolerable waiting time. In this paper, based on the depth of the OPT operation occurring in a query, we propose an approach to obtain its all approximate queries with less depth of the OPT operation. Although queries are approximated in this method, it remains the "non-optional" query patterns from users, This paper mainly discusses those queries with well-designed patterns since the OPT operation in a well-designed pattern is really "optional". We remove "optional" triple patterns with less depth of the OPT operation and then obtain approximate queries with different depths of the OPT operation. Furthermore, we evaluate the approximate query efficiency and solutions precision with the degree of approximation. It shows that users can keep the balance between query efficiency and solutions precision by changing the degree of approximation.