An Effective Discrete Artificial Bee Colony Based SPARQL Query Path Optimization by Reordering Triples

Ozger Z. B., Uslu N. Y.

Journal of Computer Science and Technology, vol.36, no.2, pp.445-462, 2021 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 36 Issue: 2
  • Publication Date: 2021
  • Doi Number: 10.1007/s11390-020-9901-y
  • Journal Name: Journal of Computer Science and Technology
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Page Numbers: pp.445-462
  • Keywords: artificial bee colony, resource description framework (RDF), query optimization, reordering triple pattern, SPARQL
  • Yıldız Technical University Affiliated: Yes


Semantic Web has emerged to make web content machine-readable, and with the rapid increase in the number of web pages, its importance has increased. Resource description framework (RDF) is a special data graph format where Semantic Web data are stored and it can be queried by SPARQL query language. The challenge is to find the optimal query order that results in the shortest period of time. In this paper, the discrete Artificial Bee Colony (dABCSPARQL) algorithm is proposed, based on a novel heuristic approach, namely reordering SPARQL queries. The processing time of queries with different shapes and sizes is minimized using the dABCSPARQL algorithm. The performance of the proposed method is evaluated on chain, star, cyclic, and chain-star queries of different sizes from the Lehigh University Benchmark (LUBM) dataset. The results obtained by the proposed method are compared with those of ARQ (a SPARQL processor for Jena) query engine, the Ant System, the Elitist Ant System, and MAX-MIN Ant System algorithms. The experiments demonstrate that the proposed method significantly reduces the processing time, and in most queries, the reduction rate is higher compared with other optimization methods.