Efficient Approximation of Well-Designed SPARQL Queries
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{song2016efficient,
author = {Zhenyu Song and Zhiyong Feng and Xiaowang Zhang and Xin Wang and Guozheng Rao},
title = {{Efficient Approximation of Well-Designed SPARQL Queries}},
booktitle = {WAIM Workshops},
year = {2016},
doi = {10.1007/978-3-319-47121-1\_27},
}| On tractable query evaluation for SPARQL | arXiv · 2017 |
| Complexity and Expressive Power of Weakly Well-Designed SPARQL | Theory Comput. Syst · 2018 |
| Semantics and Complexity of SPARQL | arXiv · 2006 |
| Completeness Guaranteed Approximations for OWL-DL Query Answering | Description Logics · 2009 |
| The tractability frontier of well-designed SPARQL queries | arXiv · 2017 |
| Efficient Query Answering Through Approximation | Description Logics · 2007 |