Abstract
Existing parallel SPARQL query optimizers assume hash-based data partitioning and adopt plan enumeration algorithms with unnecessarily high complexity. Therefore, they cannot easily accommodate other partitioning methods and only consider an unnecessarily limited plan space. To address these problems, we first define a generic RDF data partitioning model to capture the common structure of various state-of-The-Art RDF data partitioning methods. Then we propose a query plan enumeration algorithm that not only has an optimal efficiency, but also accommodates different data partitioning methods. Furthermore, based on a solid analysis of the complexity of the plan enumeration algorithm, we propose two new heuristic methods that can consider a much larger plan space than the existing methods, and at the same time can still confine the search space of the algorithm. An autonomous approach is proposed to choose one of the two methods by considering the structure and the size of a complex SPARQL query. We conduct extensive experiments using synthetic and a real-world dataset, which show the superiority of our algorithms in comparing to existing ones.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 33rd IEEE International Conference on Data Engineering (ICDE) |
| Number of pages | 12 |
| Publisher | IEEE Press |
| Publication date | 16 May 2017 |
| Pages | 547-558 |
| ISBN (Print) | 978-1-5090-6544-8 |
| ISBN (Electronic) | 978-1-5090-6543-1 |
| DOIs | |
| Publication status | Published - 16 May 2017 |
| Externally published | Yes |
| Event | 33rd IEEE International Conference on Data Engineering - San Diego, United States Duration: 19 Apr 2017 → 22 Apr 2017 Conference number: 33 |
Conference
| Conference | 33rd IEEE International Conference on Data Engineering |
|---|---|
| Number | 33 |
| Country/Territory | United States |
| City | San Diego |
| Period | 19/04/2017 → 22/04/2017 |