In this figure, the SQL statement was analyzed to identify the involved entities (tables). Then, the database statistics are associated with the identified table extracted from the database category tables. These statistics include the field’s length and type, the entity tuple length and number of tuples in every entity, and number of pages required to store the entity data. In addition, the entity site locations and relations between entities are also obtained from the database category tables. The next step is using the information obtained from the database category tables to create the search space. Finally, our search method will be applied to the search space to obtain the best join order. The major component of the model is described in the following sections.
4.3. Search Strategy
The search methodology for our proposed model depends on QIACO metaheuristic. The cost of every journey for each ant to locate the minimal spanning graph, which represents the query search space, will be dynamically calculated while building that graph as in [
15]. The dynamic calculation of query cost depends on an additional virtual vertex that will be added to the graph to carry the intermediate join process outcome. The cost, in this case, is calculated between the virtual node and the next chosen entity in the join order. In the proposed algorithm, each entity is reformed as one qubit representation as in the form of Equation (5) and quantum partial negation gate will be used to identify the next entity in the join order. The flow of QIACO is described in the following steps:
Step 1. Initialization. In this phase, all the parameters used in the model are initialized, depending on work in [
31], experimentally. Minor changes were done to the constant values α, β, and ρ. The value of α used as 3 instead of 1, the value of β used as 2 instead of 5, and the value of ρ used as 0.02 instead of 0.1. These changes in the values increased the dependence of our work on the cost, instead of pheromone, and give a better result, while identifying the next entity in the join order. The number of ants will be determined, and pheromone trails will be initialized. All pheromone values will be initialized by an arbitrary small value equal to
. The query graph that links the tables (entities) is generated such that every table is connected to all other tables. In this phase, each entity will be associated with a qubit and all entities’ qubit probability amplitudes will be initialed as
which satisfy Equations (5) and (6):
All the parameters of the algorithm are initialized in this phase according to
Table 1.
Step 2. For each ant, select random entity and uses it as the start-up point for the journey of the ant. This entity transfers to the virtual vertex and waits to choose the following entity to implement the join process.
Step 3. Use a partial negation quantum gate to choose the next entity in join sequence. The selection will be done by applying the negation gate, as operator, on all entities’ qubit that have a connection path with the current entity. This process will be applied many times according to the amount of pheromone that is raised on the path between the current entity and the connected entities. Then, the entity with best probability will be selected as the next entity. Let
X be the Pauli-X gate, which is the quantum equivalent to the NOT gate and represented as:
The
cth partial negation for operator
V is the
cth root of the
X gate and can be calculated using diagonalization as follows:
where
, and:
Applying the operator
V on a qubit
d times is equivalent to:
such that if
d =
c, then
Vd =
X. When
d =
c = 2, this will give
and so:
In our model, the
V gate is used as an operator and is conditionally applied for
c times on every entity’ qubit. The number of times,
c, the
V gate will be applied on entity’ qubit is based on pheromone value and join cost. Here,
c will be defined using Equation (3) as:
where
is the pheromone trail on the arc that connects entity
i with entity
j and,
is the heuristic desirability and computed as the inverse of the intermediate join cost between entities
i and
j. Here, the join total cost is identified by Equations (4) and (7). The amplitudes for each entity will be updated at time
t +1 as:
After that, the suggested system uses the tensor product ⊗, a way of putting vector spaces together to obtain a larger vector space, so that for
n number of entities:
The vector obtained in Equation (19) will normalize to the number of elements similar to the number of entities in the model. In this case, each element in the normalized vector will represent the probability of the corresponding entity to be the next entity in the query join order.
Step 4. Instead of selecting the entity with better probability in the normalized vector as the next entity in the join order, the roulette wheel method is used to give the entities with small probability a chance to share in building the query join order.
Step 5. After choose the next entity, the join cost is determined and the outcome of the join process is transferred to the virtual vertex and afterward utilized as the beginning up entity for the following ant’s cycle. Equations (7)–(11) are used to determine the join cost.
Step 6. Repeat steps from 3 to 5 till all entities are handled and then the journey cost for the ant is calculated.
Step 7. Select the best journey cost from all the journeys for ants.
Step 8. Pheromone update. At the point when all the ants build their solutions and, in each cycle, the update of pheromone is performed. Every pheromone amount is reduced, to simulate the pheromone evaporation, and raised, to simulate the ant’s pheromones deposit on the trail. The modification of pheromone on all graphs’ arcs is done using Equation (1). The modifications of the pheromone are also dependent on in Equation (2) that symbolize the total cost of the better tour created by ant k.
Step 9. Repeat steps from 2 to 8 until maximum iterations and when the cycles complete, the best trail for all ants is chosen.
The pseudo-code for the suggested model is represented in Algorithm 1, the partial negation gate is represented in Algorithm 2 and the selection of next entity represented in Algorithm 3.
Algorithm 1. QIACO |
(1) Max-Iteration, Ant-Numbers // (step 1) |
(2) . // (step1) |
(3)
= [1/sqrt(2); 1/sqrt(2)] // (step 1) |
(4) |
(5) Loop (cycle < Max-Iteration) |
(6) |
(7) StartEntity = random beginning entity // (step2) |
(8) Loop (ant < Ant-Numbers) |
partialStep = NegationGate(ant, StartEntity) // (step 3) |
NextEntity = ChooseNextEnity (partialStep) // (step 4) |
CalculateCost(StartEntity, NextEntity) // (step 5) |
StartEntity = NextEntity |
(9) EndLoop // (step 6) |
(10) Identify best trail for ants. // (step 7) |
(11) Modify the pheromones. // (step 8) |
(12) EndLoop // (step 9) |
(13) Identifybest trail for the solution |
Convergence of the Model. In [
33], the author proves that the convergence of ACO depends on the pheromone value
from Equation (1) and heuristic information
ηij, from Equation (4). The suggested model still depends on Equation (1) for updating the pheromone. Additionally, Equation (4) represents the inverse of cost which is used in the suggested model to find the best route obtained by ants. So, the convergence of the suggested model is guaranteed.
Complexity analysis. As in [
34], the computational complexity of the most classical ant colony algorithms depends on the number of nodes
n, the number of ants
m, and the number of iterations
T (the colony lifetime). Considering Equation (3) in more detail, we can notice that the computational complexity of the algorithm also depends on the parameters
α and
β. Here, the computational complexity was explained as:
In our proposed QACO algorithm, a single quantum superposed state is prepared to encode each node
n in the search space, thus exploration of all nods in a single iteration is
O(n) time. The selection of the next entity in the join order depends on the negation gate which is represented mathematically by vectors product with
O(n) time. Here, the vector product will be applied to all
n nods, so the selection process running time is
O(n x n) = O(n2). So, the overall computational time for the quantum part in our model is
O(n) + O(n2) which can reduced to
O(n2). Hence, the computational complexity for our QACO algorithm is:
QACO has a computational complexity greater than the classical ant colony, but gives better results as will be explained in the experimental results section.
Algorithm 2. Partial Negation Gate |
Function NegationGate(antX, currentEntity) |
(1) QGate = [0 1;1 0] |
(2) For (entity = 1 to Number-of-Entities) |
If entity is visited then |
partialStep[entity] = ; very small value |
continue |
End IF |
cost = CalcCost(currentEntity, entity) |
ph = GetPheromone(currentEntity, entity) |
|
|
partialStep[entity] = |
(3) End For |
(4) Return partialStep[entity] |