# Query Optimization in Distributed Database Based on Improved Artificial Bee Colony Algorithm
## 2 Proposed Method
### Improved Artificial Bee Colony Algorithm
The traditional artificial bee colony algorithm starts the searching phase with leader bees searching around the food source \(X_{i}\) according to Equation (3) to produce a new food source \(Y_{i}=Y_{i1}\), \(Y_{i2}\),..., \(Y_{id}\):  
\[Y_{id}=X_{id}+\delta\cdot(X_{id}-X_{jd}) \tag{3}\]  
where \(d\) is a random integer in [1, D], denoting a dimension of the random selection search by the leader bees; \(j\subseteq 1\), \(2\),..., \(N\), \(j\
eq i\), denotes a random selection of a food source not equal to \(i\) among the current \(N\) food sources; and \(\delta\) = [\(-1\),1] is a uniformly distributed random number that determines the magnitude of the random selection perturbation. However, in this study, the problem to be solved by query optimization is to find a query execution plan with the fewest number of sites involved, which is equivalent to the highest site concentration, and where each dimension in each food source \(X\) only represents the label of a data site, with no size. Therefore, there is no concept of distance between food sources in this problem. Following the traditional search method, it is equivalent to re-performing a random search at each iteration, which leads to an algorithm without directional optimization, making the convergence speed extremely slow. In this paper, a greedy artificial bee colony algorithm in the face of a discrete feasible domain without the concept of distance is proposed to improve the optimization strategy of the traditional artificial bee colony algorithm. The strategy for leader bees to generate a new food source \(Y_{i}\) based on food source \(X_{i}\) in the search initiation phase of the improved artificial bee colony algorithm is as follows: first, calculating and sorting the number of times that the sites involved in the food source \(X_{i}\) were used. The sites with a high number of use times are retained according to the perturbation coefficient \(\delta\) by using the greedy idea, and the sites with a low number of use times are perturbed. Then, the data shardings corresponding to the lesser-used sites re-select data sites according to Equation (1). Finally, the obtained new food source \(Y_{i}\) is compared with \(X_{i}\). If the fitness value of \(Y_{i}\) is better than \(X_{i}\), then replace \(X_{i}\) with \(Y_{i}\); otherwise, keep \(X_{i}\) unchanged. The details are shown in Algorithm 1:  
```
0:\(X_{i}\) and \(\delta\)\(\triangleright\) A food source in the population and the perturbation coefficient \(Y_{i}\)\(\triangleright\) A new food source generated by \(X_{i}\)
1:\(N\)\(\leftarrow\) the number of sites used in \(X_{i}\);
2:\((n_{1},n_{2},\,\ldots,\,n_{N})\)\(\leftarrow\) the number of each site used in \(X_{i}\)\(\triangleright\) Calculate the number of times each site is used
3:sort(\(n_{1},n_{2},\,\ldots,\,n_{N}\)); \(\triangleright\) sort them from largest to smallest
4:N\({}^{\prime}\)\(\leftarrow\)\([N\cdot\delta]\); \(\triangleright\) the number of sites that need to be updated is calculated as based on the perturbation coefficient \(\delta\)
5: re-select (\(N\)' sites); \(\triangleright\) reselect the \([N\cdot\delta]\) sites for data shardings corresponding to sites with smaller usage counts in \(X_{i}\) by Equation (1), and the rest remain unchanged
6:\(Y_{i}\)\(\leftarrow\) the new food source;
7:return\(Y_{i}\)
```  
**Algorithm 1** Improved Optimization Strategy Logical Pseudo-Code  
For example, suppose a food source \(X=\{1,\,1,\,1,\,1,\,1,\,2,\,3,\,3,\,3,\,3,\,4,\,4,\,5,\,5,\,5,\,5,\,5,\,6\}\) is a query plan involving 15 data shardings across 6 sites, and the number of times each site has been used is sorted in descending order as \(\{\)S\({}_{1}\):4; S\({}_{5}\):4; S\({}_{3}\):3; S\({}_{4}\):2; S\({}_{2}\):1; S\({}_{6}\):1\(\}\), with the perturbation coefficient \(\delta\) = 0.5.