Review

Optimizing N relations join queries by genetic algorithm

Najmeh Danesh¹, Hossein Shirgahi²* and Homayun Motameni¹

1Department of Computer, Islamic Azad University, Sari Branch, Sari, Iran.

2Department of Computer, Islamic Azad University, Jouybar Branch, Jouybar, Iran.

*Corresponding author. E-mail: hossein.shirgahi@gmail.com.

Accepted 4 June, 2010

Abstract

An important subject in optimizing queries at N relations join is the huge cost time. In web-based systems, the most important problem is obtaining answer at a minimum time. At the rank aware queries, suppliant does not need all possible answers rather having top K answers is enough. Although obtaining top K answers is time consuming in huge databases, in this paper we introduce a new concept at obtaining suitable K answers for rank aware queries. These suitable k answers are not top K answers necessarily, but they are much close to those answers. The operation is obtaining M (primal population) with length-N from the value of K that is determined in the query, N relations that are used in the query and by using genetic algorithm (GA). Then we apply GA on this primal set and repeat this algorithm until the average of different ranking value between sets elements in two sequential steps becomes less than a threshold level. So we can answer N relations join queries for obtaining suitable top K answers efficiently. We implement the proposed method and from the results obtained it was concluded that the query process time is reduced from 35 - 55% compared to traditional methods. Also, in the proposed method, by comparing the obtained suitable k answers with top K answers in traditional methods, they coincided approximately to 80%.

Key words: Relations join, query optimization, relational database, rank aware query, top K, suitable K, genetic algorithm.