Application of SAPSO Algorithm to Optimize SPARQL Queries with OPTIONAL Blocks

Semantic Web technology is an emerging technology developed as a result due to the rapid development of multiple web pages. Semantic web stores facts in many different formats. One of the popular formats is the Resource Description Framework (RDF) format. When the amount of semantic web data increases, querying large RDF graphs becomes a tiresome process. Also the problem of query optimization becomes a concern in querying large RDF graphs. Choosing the best query plan reduces the amount of query execution time. To address this problem, nature inspired algorithms can be used as an alternative to the traditional query optimization techniques. In this research, the optimal query plan is generated by applying the SAPSO algorithm which is a hybrid of Simulated Annealing (SA) and Particle Swarm Optimization (PSO) algorithms. In this research, the SAPSO algorithm is applied to queries having OPTIONAL blocks. The SAPSO algorithm finds the local optimistic solution and it avoids the problem of local minima. Experiments were performed on datasets with varying number of predicates. The algorithm applied in this research gives improved results compared to existing algorithms in terms of query execution time.