Abstract FR:

L'interet du traitement parallele devient tres fort dans les applications qui exigent des performances de plus en plus elevees et en particulier dans les applications de bases de donnees, des entrepots de donnees et d'aide a la decision. Le parallelisme peut considerablement augmenter les performances de telles applications. Toutefois il n'est utile qu'en presence d'algorithmes realisant des requetes complexes sur des donnees dynamiques, irregulieres et distribuees. De tels algorithmes doivent etre concus pour repartir de maniere equitable la charge des differents processeurs tout en reduisant au minimum les couts des calculs locaux et de communication inherents aux machines multi-processeurs. Les recherches ont montre que l'operation de jointure ne peut etre parallelisable avec une acceleration lineaire sur des architectures shared nothing que sous des conditions ideales d'equilibre des donnees. Le desequilibre des donnees peut avoir un effet devastateur sur la performance. Dans le cadre de cette these, nous nous interessons au probleme d'equilibre de charge pour le traitement de la jointure et de la multi-jointure sur des architecture shared nothing. Dans ce contexte, avons propose une variete d'algorithmes pour le traitement de la jointure et la multi-jointure permettant de reduire les couts de redistribution (et donc les couts de communication) tout en traitant de maniere tres efficace les problemes de desequilibre des valeurs de l'attribut de jointure et des resultats de jointures. Nous avons etendu notre etude aux applications d'entrepots de donnees par la proposition d'un algorithme efficace pour la maintenance des vues materialisees dans un environnement shared nothing. L'analyse de complexite des differents algorithmes