Randomized Optimization of Quantified Path Expressions in Object Databases.
Zhaohui Tang, Georges Gardarin · BDA · 1997
Les systemes de bases de donnees objets et relationnelles sont de plus en plus utilises dans de vraies applications, cela grâce a leurs types de donnees riches et extensibles ainsi qu'a leur langage de requetes melangeant les affirmations declaratives et les navigations. Les requetes peuvent souvent permettre de nombreuses collectes transversales (i.e., expression de chemin ), potentiellement distribuees. De plus, des predicats avec des quantificateurs comme « exist, any, all » peuvent etre inclus dans ces expressions de chemin. Cela apporte de nouveaux defis pour l'optimisation de requetes a objets. Pour optimiser efficacement ces requetes, nous definissons le concept d'expressions de chemin quantifiees et introduisons les operateurs algebriques de navigation qui se melent de maniere correcte avec l'algebre a objets classique. Nous etudions egalement plusieurs algorithmes combinatoires pour explorer l'espace de recherche genere par les expressions de chemin. Au travers de cette experience, nous trouvons une procedure amelioree d'algorithme genetique qui est plus efficace comparee aux classiques du genre. Nous fournissons une comparaison analytique et experimentale entre notre algorithme genetique et d'autres algorithmes et la methode tabou. Dans la plupart de nos experiences, notre algorithme genetique trouve de meilleurs « plans » de requetes que les autres algorithmes.