Title: Distributed query plan generation using multi-objective ant colony optimisation

Authors: Rahul Singh; Amit Kumar; T.V. Vijay Kumar

Addresses: School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi – 110067, India ' School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi – 110067, India ' School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi – 110067, India

Abstract: In distributed relational databases, relations are fragmented and replicated at multiple disparate sites. As a result, for a distributed relational query, the number of possible query plans increases exponentially with an increase in the number of sites containing these relations. This leads to a large search space from which effective and efficient query plans are to be computed. This problem has already been addressed as a single objective optimisation problem using ant colony optimisation. In this paper, this problem is addressed as a bi-objective optimisation problem and solved using multi-objective ant colony optimisation (MOACO). Accordingly, a MOACO-based distributed query plan generation (DQPG) algorithm is proposed herein that generates Top-K query plans for a distributed query. Experimental comparisons of the proposed MOACO-based DQPG algorithm with the existing ACO-based DQPG algorithm show that for higher numbers of relations, the former is able to generate, comparatively, cost-effective Top-K query plans.

Keywords: query processing; multi-objective optimisation; multi-objective ACO; ant colony optimisation; MOACO; distributed databases; query plans; query plan generation; relational databases.

DOI: 10.1504/IJAISC.2016.078528

International Journal of Artificial Intelligence and Soft Computing, 2016 Vol.5 No.3, pp.241 - 262

Received: 11 May 2015
Accepted: 28 Feb 2016
Published online: 22 Aug 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article