A Hybrid Nature Inspired Algorithm for Generating Optimal Query Plan

Authors: R. Gomathi, D. Sharmila

Abstract:

The emergence of the Semantic Web technology increases day by day due to the rapid growth of multiple web pages. Many standard formats are available to store the semantic web data. The most popular format is the Resource Description Framework (RDF). Querying large RDF graphs becomes a tedious procedure with a vast increase in the amount of data. The problem of query optimization becomes an issue 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 the proposed SAPSO algorithm which is a hybrid of Simulated Annealing (SA) and Particle Swarm Optimization (PSO) algorithms. The proposed SAPSO algorithm has the ability to find the local optimistic result and it avoids the problem of local minimum. Experiments were performed on different datasets by changing the number of predicates and the amount of data. The proposed algorithm gives improved results compared to existing algorithms in terms of query execution time.

Keywords: Semantic web, RDF, Query optimization, Nature inspired algorithms, PSO, SA.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1096275

References:

[1] Michael Schmidt, Michael Meier, Georg Lausen,” Foundations of SPARQL Query Optimization”, Proceedings of the 13th International Conference on Database Theory, pp.4-33, 2010.
[2] Kirkpatrick, S, Gelatt Jr, C. D, Vecchi, M. P, "Optimization by Simulated Annealing". Science vol.220 No.4598, pp. 671–680, 1983.
[3] Alexander Hogenboom, Ewout Niewenhuijse, Frederik Hogenboom, and Flavius Frasincar,” RCQ-ACS: RDF Chain Query Optimization Using an Ant Colony System”, IEEE/WIC/ACM International Conferences On Web Intelligence and Intelligent Agent Technology, vol.1, pp.74-81, 2012
[4] Alexander Hogenboom, Viorel Milea, Flavius Frasincar, and Uzay Kaymak,” RCQ-GA: RDF Chain Query Optimization using Genetic Algorithms”, Lecture notes in Computer Science, vol.5692, pp.181-192, 2009.
[5] Andrey Gubichev, Thomas Neumann,” Exploiting the query structure for efficient join ordering in SPARQL queries”, Proceedings of the 17th international conference on Extending Database Technology, 2014.
[6] Tansel Dokeroglu, Umut Tosun, Ahmet Cosar,”Particle Swarm Intelligence as a New Heuristic for the Optimization of Distributed Database Queries”, 6th International Conference on Application of Information and Communication Technologies (AICT), pp.1-7, 2012.
[7] Juerg Senn,” Parallel Join Processing on Graphics Processors for the Resource Description Framework”, 23rd International Conference on Architecture of Computing Systems (ARCS), pp.1-8, 2010
[8] Sherif sakr, Sameh Elnikety, Yuxiong He, "Hybrid query execution engine for large attributed graphs”, Journal of Information Systems, vol.41, pp.45–73, 2014.
[9] Michael Steinbrunn, Guido Moerkotte, Alfons Kemper,”Heuristic and randomized optimization for the join ordering problem”, The VLDB Journal, vol.6, pp.191-208, 1997.
[10] Kennedy, J.; Eberhart, R."Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks vol.IV. pp. 1942–1948, 1995.
[11] C.Liu, H.Wang,”Towards efficient SPARQL query processing on RDF data”, Tsinghua science and technology, vol.15, No.6, pp.613-622, 2010.
[12] X. Zhang, L. Chen, and M. Wang, "Towards efficient join processing over large RDF graph using map reduce,” in Scientific and Statistical Database Management,vol.7338 of Lecture Notes in Computer Science, pp. 250–259, 2012.
[13] Xin-She Yang, Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press. ISBN 1-905986-10-6, 2008.
[14] X.-S. Yang; S. Deb, "Cuckoo search via Lévy flights", World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). IEEE Publications. pp. 210–214, 2009.