Sahil Saharan; J.S. Lather; R. Radhakrishnan

Optimization of Different Queries using Optimization Algorithm (DE)

Full Text (PDF, 869KB), PP.52-59

Views: 0 Downloads: 0

Author(s)

Sahil Saharan ^1,* J.S. Lather ² R. Radhakrishnan ³

1. Department of Computer Applications, National Institute of Technology, Kurukshetra, India

2. Department of Electrical Engineering, National Institute of Technology, Kurukshetra, India

3. Department of Computer Science and Engineering, ABES Ghaziabad (Uttar Pradesh), India

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2018.03.06

Received: 30 Nov. 2017 / Revised: 1 Jan. 2018 / Accepted: 16 Jan. 2018 / Published: 8 Mar. 2018

Index Terms

RDF query optimization, Differential Evolution(DE), SPARQL, Reordering triple patterns, Semantic Web

Abstract

The biggest challenge in modern web is to tackle tremendous growth of data, scattered and continuously updating in nature. Processing of such unscattered data by human or machine remains a tedious task. Semantic Web; as a solution has already been invented. But, still there are some other challenges, like as optimization of the query. We introduce a new approach for real–time SPARQL query optimization with different forms and different triple patterns. The strategy introduces rearrangement of order of triple pattern using Differential Evolution(DE). The experimental study focus on main-memory model of RDF data and ARQ query engine of Jena. We compare the result of proposed approach with the Ant Colony Optimization(ACO) different versions and some other approaches. Results shows that proposed approach provides better execution time as compare to the other approaches.

Cite This Paper

Sahil Saharan, J.S. Lather, R. Radhakrishnan, "Optimization of Different Queries using Optimization Algorithm (DE)", International Journal of Computer Network and Information Security(IJCNIS), Vol.10, No.3, pp.52-59, 2018. DOI:10.5815/ijcnis.2018.03.06

Reference

[1]T. Berners-Lee, J. Hendler, O. Lassila, “The semantic web”, Sci. Am. vol 284, no.5, pp: 34–43, 2001.
[2]J.J. Carroll, G. Klyne, “Resource description framework (RDF): Concepts and abstract syntax”– W3C recommendation, 2004.
[3]Y.E. Ioannidis, “Query optimization,” ACM Computing Surveys, vol/issue:28(1), pp.121–123, 1996.
[4]S. Chaudhuri, “An overview of query optimization in relational systems,” in Proceedings of the 17th Symposium on Principles of Database Systems, PODS'98, ACM, Seattle, Washington, pp.34– 43, 1998.
[5]T. Neumann, G. Weikum, “RDF-3X: a RISC- style engine for RDF,” Proc. VLDB Endow, vol/issue:1(1), pp.647–659, 2008.
[6]G. Mitchell, S.B. Zdonik, U. Dayal, “Object-oriented Query Optimization: What's the Problem?”, Technical Report, Brown University, Providence, RI, USA, 1991.
[7]M.T. ?zsu, J.A. Blakeley, “Query processing in object-oriented database systems,” Modern Database Systems, ACM Press, Addison-Wesley, New York, NY, USA, pp.146–174, 1995.
[8]D. Che, K. Aberer, T. Ozsu, “Query optimization in XML structured- document databases,” VLDB J,vol/issue:15(3), pp.263–289, 2006.
[9]R. Abdel Kader, M. van Keulen, “Overview of query optimization in XML database systems,” URL: ?http://doc.utwente.nl/64449/?, 2007.
[10]H. Stuckenschmidt, R. Vdovjak, J. Broekstra, G. Houben, “Towards distributed processing of RDF path queries,” Int. J. Web Eng. Technol.vol/issue:2(2/3), pp.207–230, 2005.
[11]M.M. Astrahan, M.W. Blasgen, D.D. Chamberlin, K.P. Eswaran, J.N. Gray, P.P. Griffiths, W.F. King, R.A. Lorie, P.R. McJones, J.W. Mehl, G.R. Putzolu, I.L. Traiger, B.W. Wade, V. Watson, “System R: relational approach to database management,” ACM Trans. Database Syst.vol/issue:1(2) pp.97–137, 1976.
[12]N. Li, Y. Liu, Y. Dong, J. Gu, “Application of ant colony optimization algorithm to multi-join query optimization,” in Proceedings of the 3rd International Symposium on Advances in Computation and Intelligence, ISICA’08, Springer-Verlag, Berlin, Heidelberg, pp.189–197, 2008.
[13]P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T.G. Price, “Access path selection in a relational database management system,” in Proceedings of the International Conference on Management of Data, SIGMOD'79, ACM, New York, NY, USA, pp.23–34, 1979.
[14]M. Steinbrunn, G. Moerkotte, & A. Kemper, “Heuristic and randomized optimization for the join ordering problem”, The VLDB Journal, vol:6, pp.191–208, 1997.
[15]T. Ibaraki, & T. Kameda, “On the optimal nesting order for computing N relational joins”. ACM Transactions on Database Systems, vol:9, pp.482–502, 1984.
[16]Y. E. Ioannidis, & E. Wong, “Query optimization by simulated annealing,” SIGMOD Rec.16, pp.9–22, 1987.
[17]A. Hogenboom, V. Milea, F. Frasincar, U. Kaymak, “RCQ-GA: RDF chain query optimization using genetic algorithms,” in Proceedings of the 10th International Conference on EC-Web, pp.181–192, 2009.
[18]A. Hogenboom, F. Frasincar, U. Kaymak, “Ant colony optimization for RDF chain queries for decision support,” Expert Syst. Appl,vol/issue:40(5),2013.
[19]R. Gomathi, D. Sharmila, “A novel adaptive cuckoo search for optimal query plan generation,” The Scientific World Journal, 2014.
[20]R. Storn, K. Price, “Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces,” J Glob Optim, vol/issue: 11(4), pp.341–359, 1997.
[21]V. Plagianakos, D. Tasoulis, M. Vrahatis, “A Review of Major Application Areas of Differential Evolution,” Advances in Differential Evolution, Springer, Berlin, vol:143 pp.19- 238, 2008.
[22]J. Ilonen, J.K. Kamarainen, J. Lampinen, “Differential Evolution Training algorithm for Feed-Forward Neural Networks,” Neural Process Lett, vol/issue: 17(1), pp.93–105, 2003.
[23]http://jena.apache.org.
[24]J. Broekstra, A. Kampman, F. Van Harmelen, “Sesame: A generic architecture for storing and querying rdf and rdf schema,” in: International semantic web conference, Springer Berlin Heidelberg, pp. 54-68, 2002.
[25]A. Maduko, K. Anyanwu, A. Sheth, P. Schliekelman, “Estimating the cardinality of RDF graph patterns,” in Proceedings of the 16th International Conference on World Wide Web, ACM, Banff, AB, Canada, pp.1233–1234, 2007.
[26]M. Stocker, A. Seaborne, A. Bernstein, C. Kiefer, D. Reynolds, “SPARQL basic graph pattern optimization using selectivity estimation,” in Proceedings of the 17th International Conference on WWW, ACM, Beijing, China, pp:595–604, 2008.
[27]A. Hogenboom, V. Milea, F. Frasincar, U. Kaymak, “RCQ-GA: RDF chain query optimization using genetic algorithms,” in Proceedings of the 10th International Conference on EC-Web, pp:181–192, 2009.
[28]T. Neumann, G. Weikum, “Scalable join processing on very large RDF graphs,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD'09, ACM, New York, NY, USA, pp:627–640, 2009.
[29]Z. Kaoudi, K. Kyzirakos, M. Koubarakis, “SPARQL query optimization on top of DHTs,” in Proceedings of the 9th International Conference on the Semantic Web, ISWC'10, Springer-Verlag, Berlin, Heidelberg, pp:418–435, 2010.
[30]T. Neumann and G. Moerkotte, “Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins,” in ICDE, Hannover, Germany, pp:984-994, 2011.
[31]D. Ouyang, X. Wang, Y. Ye, and X. Cui, “A GA-based SPARQL BGP reordering optimization method,” Advances in Information Sciences and Service Sciences, vol/issue:4(9), pp:139–147, 2012.
[32]A. Gubichev and T. Neumann, Exploiting the query structure for efficient join ordering in SPARQL queries. in: EDBT, 2014, pp. 439–450.
[33]E. Guzel Kalayci, T.E. Kalayc?, D. Birant, “An ant colony optimization approach for optimising SPARQL queries by reordering triple patterns,” Information Systems, vol:50 pp:51–68, 2015.
[34]Meimaris M, Papastefanatos G. Distance-Based Triple Reordering for SPARQL Query Optimization. in: Proceedings of the 33rd International Conference on Data Engineering (ICDE), IEEE, 2017, pp. 1559-1562.
[35]J.G. Sauer, L dos Santos Coelho, V.C. Mariani, L. de Macedo Mourelle, N. Nedjah, “A discrete differential evolution approach with local search for traveling salesman problems,” in Innovative Computing Methods and Their Applications to Engineering Problems, Springer Berlin Heidelberg, pp. 1-12, 2011.
[36]S. Harris, A. Seaborne, “SPARQL1.1querylanguage” – W3C working draft 05 January 2012.
[37]G.H.L. Fletcher, “An algebra for basic graph patterns,” in: Proceedings of the Workshop on Logic in Databases, 2008.
[38]http://jena.apache.org/documentation/query.
[39]http://www.cia.gov/library/publications/download/
[40]B Hegerty, CC Hung, K Kasprak, “A comparative study on differential evolution and genetic algorithms for some combinatorial problems,” in Proceedings of 8th Mexican International Conference on Artificial Intelligence, pp. 9-
13, 2009.
[41]S. N. Sivanandam, S.N. Deepa, “Introduction to Genetic Algorithm,” ISBN 978-3-540-73189-4 Springer Berlin Heidelberg New York, Springer ? Verlag Berlin Heidelberg 2008.

International Journal of Computer Network and Information Security (IJCNIS)