Article Preview
TopIntroduction
RDF (Resource Description Framework) (Decker, 2000) is a data model for data interchange on the web, plenty of research fields begin to use RDF to represent data for knowledge sharing. SPARQL (Simple Protocol and RDF Query Language) (Guha, 2003) is a standard RDF query language. In many cases, users are more interested in the most valuable results in the huge datasets, which is named as top-k query (Ilyas, 2008). Top-k join query is a kind of top-k query which involves multiple tables or several datasets and the results are sorted by the aggregation score. In the actual query, ORDER BY and LIMIT phrases can easily complete the extraction of top-k results. However, they are often used as a result modifier and completed at the last stage of the query in the SPARQL algebra expression. This kind of sorting mechanism is always insufficient.
In recent years, there are increasing research interests in the query optimization (Ci, 2014). For example, ite can be used in service selection (Ngoko, 2015) and service recommendation (Zhang, 2016). Since the query process involves many complex connections and sort operations, an accurate top-k join query is a time-consuming work. With the rapid development of semantic web technology, the amount of RDF datasets continues growing, thus brings a huge challenge to query performance. Classic methods of top-k join query on RDF datasets are designed on single machine, which have bottlenecks in memory space and computing performance that may affect the further development and application of semantic web query technology.
Cloud computing has become one of the most popular research fields due to its high performance and easy extension of mass data storage and computing power (Armbrust, 2010). SPARK, developed by AMP lab of Berkeley, is chosen for this research as an ideal new generation of distributed processing framework for big data process (Zaharia, 2010).
SPARQL top-k query optimization is a relatively comprehensive research area. The existing methods are mainly focus on the optimization of top-k join query algorithms (Hwang, 2007; Liu, 2006; Martinenghi, 2012) and relational algebra (Bozzon, 2012; Pérez, 2006; Schmidt, 2010;). Within that, optimization of top-k join algorithm is crucial. The typical example is HRJN (Ilyas, 2004) algorithm, which can only support accessing tuples sequentially thus it needs additional hash table to store the input tuples and causing the calculation of threshold is quite complex. RSEQ (Rank Sequence Operator) algorithm (Magliacane, 2012) optimized of the HRJN algorithm which uses the single ordered set to support random access to minimize sequential access thus enhance the efficiency. Wagner introduced the PBRJ (Wagner, 2012) algorithm which includes boundary pattern B and tuple access strategy P. P is used to select which set should be chose to read data and B is used to calculate the threshold. However, all above algorithms can only be used in a single machine hence cannot be directly applied to large-scale RDF dataset query in the distributed environment. How to optimize the traditional SPARQL top-k query algorithm and make it adapt to the distributed computing framework of cloud computing has become the key problem to be solved in this paper.