Optimization of SPARQL queries using artificial intelligence techniques

Today, configuring and controlling the overwhelming volumes of information on the web is an important problem. Semantic web is a paradigm that is proposed for solving this important problem. Still, semantic web can't be counted as a mature paradigm and it contains some issues that must be dealt. One important challenge in semantic web is decreasing execution times of queries. An approach for decreasing execution times of queries is reordering triple patterns.In this study, an Ant Colony Optimization approach for optimizing SPARQL queries is proposed. Different Ant Colony Optimization Meta-heuristic algorithms - Ant System, Elitist Ant system and Max-Min Ant System - are implemented based on this approach. This proposed novel optimization method is implemented using ARQ query engine and it optimizes the queries for in-memory models of ontologies.Queries are abstracted as a complete graph whose nodes represent triple patterns and whose edges represent join costs. Artifical ants that are used in ACO algorithms traverse this graph. Transition rule which effects the decision of ants for choosing the next node is provided by considering selectivity of triple patterns (candidates of the next node). In order to estimate selectivity of triple patterns, GSH which provides accurate size information, Variable Counting which is based on ranking triple pattern components and Modified Variable Counting which modified to improve the performance of chain and chain-star queries, are used.Proposed approach is examined by querying two different ontologies LUBM (includes 162.871 triples) and Factbook (includes 95.813 triples) with various structures of queries like chain, star, cyclic, chain-star, chain-cyclic, etc.Contributions of the proposed approach are optimizing order of triple patterns in SPARQL queries using ant colony optimization for lesser and nearly optimal execution time and real time optimization without requiring any prior domain knowledge. Experiments show that proposed methods reduce execution time of queries considerable.