2.3.2 L'algorithme QT
Son rôle est de trouver la combinaison des offres de
données les plus intéressantes à la requête de
l'acheteur, et ce à moindre coût.
Cet algorithme tourne itérativement et tente
d'améliorer le plan d'exécution d'une requête à
chaque itération.
Dans chaque itération l'acheteur fait un appel d'offre
pour trouver les données relevantes à sa requête, et les
vendeurs répondent avec leurs offres contenant l'estimation des
propriétés de leurs réponses. Les vendeurs peuvent ne pas
avoir la totalité des données nécessaires pour une
requête, c'est pourquoi ils font des offres qui ne concernent que la part
de données qu'ils possèdent localement. A la fin de chaque
itération l'acheteur utilise ces offres pour trouver, si c'est possible,
un meilleur plan d'exécution, et l'algorithme recommence une nouvelle
fois avec un nouvel ensemble de requêtes dans le but de reconstruire un
nouveau plan d'exécution plus optimal que le précédent.
L'algorithme d'optimisation est une sorte de négociation entre le pair
acheteur et les pairs vendeurs.
|
Algorithme coté Acheteur
|
Algorithme coté Vendeur
|
|
B0. Initialisation Q= {{q,C}}
B1.faire une estimation stratégique des coûts
pour requêtes de l'ensemble Q
B2.faire un appel d'offre des requêtes de Q
B3.choisir les meilleures offres {qi,
ci}
B4. En utilisant les meilleures offres, trouver les plans
d'exécution Pm et leurs coûts Cm.
B5. Chercher des sous requêtes qe, et leurs
coûts ce respectifs, si elles existent, elles
peuvent être utilisées à l'étape B.4.
B.6 mettre à jour l'ensemble Q avec les sous
requêtes {qe, ce}.
B.7 soit P* le meilleur plan d'exécution
parmi Pm. Si P* est meilleur que celui produit dans la
précédente itération de l'algorithme, ou bien si
l'étape B6 a modifié l'ensemble Q, alors aller à
l'étape B.1.
B.8 informer les pairs vendeurs, qui, leurs requêtes
sont utilisées dans le meilleur plan d'exécution P*,
qu'ils commencent l'exécution de ces requêtes.
|
S1.pour chaque requête q dans l'ensemble Q
faire :
S2.1 trouver les sous requêtes qk de q qui
peuvent être exécutées localement.
S2.2 faire une estimation pour chaque sous requête
qk
S2.3 faire offre et essayer de vendre les requêtes de
l'étape S2.1
|
Figure 2 : L'algorithme QT
La figure 2 représente le détail de l'algorithme
d'optimisation des requêtes. L'entrée de cet algorithme est une
requête q, et la sortie est le meilleur plan d'exécution
P* et son coût C* (étape B8).
L'algorithme au niveau de l'acheteur tourne itérativement
(étape B1 à B7). Chaque itération commence avec un
ensemble Q de pairs et de requêtes et leurs coûts correspondant,
que l'acheteur veut acheter. Dans la première étape (B1),
l'acheteur estime stratégiquement le coût qu'il doit demander
concernant les requêtes dans l'ensemble Q, et lance après un appel
d'offre aux pairs distants (étape B2). Les vendeurs (candidats)
après avoir reçu cet appel d'offre, ils vont faire leurs offres
qui contiennent les réponses concernant des parties des requêtes
dans l'ensemble Q (étapes S2.1 - S2.2). Ensuite les offres gagnantes
seront sélectionnées (étapes B3 S3). Le pair acheteur
utilise ces offres afin de trouver un ensemble de plans d'exécution
candidats Pm et leurs coûts respectifs Cm (étape B4), et enrichit
l'ensemble Q avec de nouvelles requêtes et leurs coûts
(qe, ce) (étape B5 B6), qui peuvent être
utilisées dans la prochaine itération pour améliorer
davantage les plans d'exécution produits dans l'étape B4.
Finalement, à l'étape 7, le meilleur plan d'exécution
P*, parmi les plans d'exécution candidats Pm est
sélectionné. Si P* n'est pas meilleur par rapport au
plan d'exécution produit dans la précédente
itération (amélioration impossible) et à l'étape
B5, il n'y a pas eu de nouvelles requêtes, alors l'algorithme
s'arrête.
Exemple :
Considérons l'exemple précédent de la
société de télécommunication, et la requête
posée par le bureau de paris :
q=SELECT SUM(Montant) FROM FACTURE F, CLIENT C
WHERE F.IDClient=C.IDClient AND Bureau in (`Lyon',`Metz');
Etape B0 :
Q={q,c}
Etapes B1, B2:
Regarder figure 3
Etape S1 :
Etape S2.1 :
Les pairs lyonnais et Messins répondent à
l'appel d'offre de l'acheteur respectivement avec q1, q2
q1=SELECT SUM(amount) FROM invoiceline i, customer c
WHERE i.custid=c.custid AND office=`Lyon';
q2= SELECT SUM(amount) FROM invoiceline i, customer c
WHERE i.custid=c.custid AND office=`Metz';
Etape S2.1, S2.3 :
Regarder figure 3
Etape B3 :
Supposant que les pairs Lyonnais et Messins aient fait les
meilleures offres pour répondre à la requête du bureau de
Paris {{q1, c1}, {q2, c2}}
Etape B4 :
Le meilleur plan d'exécution P* comprend q1 et q2.
Etapes B5, B6:
Mettre à jour l'ensemble Q avec les nouvelles sous
requêtes
Q= {{q, c}, {q1, c1}, {q2, c2}}
Etape B7:
Puisqu'il s'agit de la première itération, il
n'y a pas encore de plan d'exécution aller à B1
v La prochaine itération de l'algorithme va faire un
appel d'offre des requêtes de l'ensemble Q, et va essayer
d'améliorer P*.
o Si amélioration possible c'est-à-dire le plan
d'exécution de la deuxième itération est mieux que P*
aller à B1.
o Sinon aller à B8.
| 
